discrete math 1 midterm

Question 1

proposition

Answer 1

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. All the following declarative sentences are propositions. 1. Washington, D.C., is the capital of the United States of America. 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3.

Question 2

propositional variables

Answer 2

variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are p, q, r, s, . . . . The truth value of a proposition is true, denoted by T, if it is a true proposition, and the truth value of a proposition is false, denoted by F, if it is a false proposition.

Question 3

propositional calculus

Answer 3

The area of logic that deals with propositions The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.

Question 4

compound propositions

Answer 4

formed from existing propositions using logical operators

Question 5

truth table

Answer 5

a diagram in rows and columns showing how the truth or falsity of a proposition varies with that of its components.

Question 6

negation operator

Answer 6

¬p

Question 7

conjunction operator

Answer 7

ᐱ

Question 8

disjunction operator

Answer 8

ᐯ

Question 9

p ∧ q

Answer 9

conjunction “and”

Question 10

p ∨ q

Answer 10

disjunction “or”

Question 11

¬p

Answer 11

negation “not”

Question 12

inclusive or

Answer 12

p ∨ q “disjunction” p or q (but not both)”

Question 13

conditional operator

Answer 13

→ The conditional statement p → q is false when p is true and q is false, and true otherwise

Question 14

→

Answer 14

conditional statement

Question 15

implication

Answer 15

→ A conditional statement is also called an implication

Question 16

“If I am elected, then I will lower taxes.”

Answer 16

conditional statement

Question 17

if 2 + 2 = 4 then x := x + 1

Answer 17

conditional statement

Question 18

CONVERSE

Answer 18

one of three related conditional statements that occur so often that they have special names q → p is called the converse of p → q

Question 19

CONTRAPOSITIVE

Answer 19

one of three related conditional statements that occur so often that they have special names p → q is the proposition ¬q →¬p

Question 20

INVERSE

Answer 20

one of three related conditional statements that occur so often that they have special names ¬p →¬q is called the inverse of p → q

Question 21

equivalent

Answer 21

When two compound propositions always have the same truth value. conditional statement and its contrapositive are equivalent: p → q = ¬q →¬p “If it is raining, then the home team wins.” “If the home team does not win, then it is not raining.”

Question 22

biconditional statement

Answer 22

p ↔ q proposition “p if and only if q.” also called bi-implications

Question 23

p ↔ q

Answer 23

biconditional proposition “p if and only if q.”

Question 24

bi-implications

Answer 24

p ↔ q proposition “p if and only if q.” also called biconditional statement

Question 25

“if and only if”

Answer 25

biconditional statement p ↔ q

Question 26

“q whenever p”

Answer 26

→ conditional statement

Question 27

"not"

Answer 27

negation operator ¬p

Question 28

p → q “p only if q” Is Same As ?

Answer 28

“if p, then q,”

Question 29

¬p →¬q

Answer 29

inverse

Question 30

q → p is considered what of p → q

Answer 30

converse

Question 31

p → q is considered what of ¬q →¬p

Answer 31

contrapositive

Question 32

¬p →¬q is considered what of p → q

Answer 32

inverse

Question 33

What are the contrapositive, the converse, and the inverse of the conditional statement “The home team wins whenever it is raining?”

Answer 33

Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.” The converse is “If the home team wins, then it is raining.” The inverse is “If it is not raining, then the home team does not win.” Only the contrapositive is equivalent to the original statement.

Question 34

“iff”

Answer 34

“if and only if.” biconditional statement p ↔ q

Question 35

(p → q) ∧ (q → p).

Answer 35

Note that p ↔ q has exactly the same truth value as (p → q) ∧ (q → p). \*\*\*\* biconditional statement \*\*\*\*

Question 36

What is the Precedence of Logical Operator →

Answer 36

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

Question 37

What is the Precedence of Logical Operator ¬

Answer 37

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

Question 38

What is the Precedence of Logical Operator ↔

Answer 38

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

Question 39

What is the Precedence of Logical Operator ∨

Answer 39

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

Question 40

What is the Precedence of Logical Operator ∧

Answer 40

¬ 1 ∧ 2 ∨ 3 → 4 ↔ 5

Question 41

What logic gate is this?

Answer 41

Inverter

Question 42

What logic gate is this?

Answer 42

OR gate

Question 43

what logic gate is this?

Answer 43

AND gate

Question 44

What is a A combinatorial circuit?

Answer 44

Complicated digital circuits can be constructed from three basic circuits, called gates, shown in Figure 1. The inverter, or NOT gate, takes an input bit p, and produces as output °˛p. The OR gate takes two input signals p and q, each a bit, and produces as output the signal p ∨ q. Finally, the AND gate takes two input signals p and q, each a bit, and produces as output the signal p ∧ q.

Question 45

tautology

Answer 45

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology

Question 46

contradiction.

Answer 46

A compound proposition that is always false is called a contradiction.

Question 48

contingency.

Answer 48

A compound proposition that is neither a tautology nor a contradiction is called a contingency

Question 49

logically equivalent

Answer 49

Compound propositions that have the same truth values in all possible cases are called logically equivalent. ## Footnote **≡**

Question 50

≡

Answer 50

Compound propositions that have the same truth values in all possible cases are called logically equivalent

Question 51

p ≡ q

Answer 51

is the statement that p ↔ q is a tautology

Question 52

De Morgan’s Laws.

Answer 52

named after the English mathematician Augustus De Morgan, of the mid-nineteenth century ¬(p ∧ q) ≡ ¬p ∨¬q ¬(p ∨ q) ≡ ¬p ∧¬q

Question 53

Identity laws

Answer 53

Question 54

Domination laws

Answer 54

Question 55

Idempotent laws

Answer 55

Question 56

Double negation law

Answer 56

Question 57

Commutative laws

Answer 57

Question 58

Associative laws

Answer 58

Question 59

Distributive laws

Answer 59

Question 60

De Morgan’s laws

Answer 60

Question 61

Absorption laws

Answer 61

Question 62

Negation laws

Answer 62

Question 63

De Morgan’s laws are particularly important because?

Answer 63

They tell us how to negate conjunctions and how to negate disjunctions. In particular, the equivalence ¬(p ∨ q) ≡ ¬p ∧¬q tells us that the negation of a disjunction is formed by taking the conjunction of the negations of the component propositions. Similarly, the equivalence ¬(p ∧ q) ≡ ¬p ∨¬q tells us that the negation of a conjunction is formed by taking the disjunction of the negations of the component propositions

Question 64

Propositional Satisfiability

Answer 64

A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true

Question 65

Propositional unsatisfiable.

Answer 65

when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable. to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false.

Question 66

Propositional solution

Answer 66

When we find a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisfiable; such an assignment is called a solution of this particular satisfiability problem

Question 67

predicate

Answer 67

refers to a property that the subject of the statement can have

Question 68

propositional function

Answer 68

The statement P(x) is also said to be the value of the propositional function P at x. Let P(x) denote the statement “x \> 3.”

Question 69

preconditions

Answer 69

The statements that describe valid input are known as preconditions

Question 70

postconditions.

Answer 70

the conditions that the output should satisfy when the program has run are known as postconditions.

Question 71

quantification

Answer 71

Quantification expresses the extent to which a predicate is true over a range of elements. In English, the words all, some, many, none, and few are used in quantifications.

Question 72

universal quantification

Answer 72

tells us that a predicate is true for every element under consideration,

Question 73

existential quantification

Answer 73

tells us that there is one or more element under consideration for which the predicate is true

Question 74

predicate calculus

Answer 74

The area of logic that deals with predicates and quantifiers

Question 75

domain of discourse

Answer 75

Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain Ref: THE UNIVERSAL QUANTIFIER

Question 76

∀

Answer 76

universal quantifier "EVERY" “P(x) for all values of x in the domain.” The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier.We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element for which P(x) is false is called a counterexample of ∀xP(x).

Question 77

∃

Answer 77

existential quantification universal quantifier "Exists" “There exists an element x in the domain such that P(x).” We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the existential quantifier.

Question 78

“there is exactly one” and “there is one and only one.”

Answer 78

**uniqueness quantifier,** denoted by ∃! or ∃1. ∃!x(x − 1 = 0),

Question 79

uniqueness quantifier

Answer 79

∃! or ∃1

Question 80

What are the Precedence of Quantifiers?

Answer 80

The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional calculus. For example, ∀xP(x) ∨ Q(x) is the disjunction of ∀xP(x) and Q(x). In other words, it means (∀xP(x)) ∨ Q(x) rather than ∀x(P(x) ∨ Q(x)).

Question 81

bound variable

Answer 81

When a quantifier is used on the variable x, we say that this occurrence of the variable is bound.

Question 82

free variable

Answer 82

An occurrence of a variable that is not bound by a quantifier or set equal to a particular value

Question 83

scope

Answer 83

The part of a logical expression to which a quantifier is applied is called the scope of this quantifier.

Question 84

Statements involving predicates and quantifiers are logically equivalent.... **S ≡ T**

Answer 84

**if and only if** they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.

Question 85

De Morgan’s Laws for Quantifiers.

Answer 85

**_The rules for negations for quantifiers_** When the domain of a predicate P(x) consists of n elements, where n is a positive integer greater than one, the rules for negating quantified statements are exactly the same as De Morgan’s laws discussed in Section 1.3. *_This is why these rules are called De Morgan’s laws for quantifiers_*.

Question 87

Prolog facts

Answer 87

Prolog facts define predicates by specifying the elements that satisfy these predicates.

Question 88

Prolog rules

Answer 88

Prolog rules are used to define new predicates using those already defined by Prolog facts.

Question 89

nested quantifiers

Answer 89

where one quantifier is within the scope of another, such as ∀x∃y(x + y = 0).

Question 91

it is sometimes helpful to think of me in terms of nested loops... What am I?

Answer 91

Nested Quantifiers

Question 92

Logical Equivalences and biconditional Statements

Answer 92