Chapter 1

Question 1

premise

Answer 1

the statement(s) preceding the conclusion

Question 2

nested quantifier

Answer 2

one quantifier is within the scope of another

Question 3

E!xP(x)

Answer 3

unique quantification of P(x)

“there exists only one”

Question 4

unsatisfiable

Answer 4

when the compound proposition is false for all assignments of truth values to its propositional variables (contradiction)

Question 5

satisfiable

Answer 5

if there is an assignment of truth values to its propositional variables that makes the compound proposition true (tautology or contingency)

Question 6

tautology

Answer 6

a compound proposition that is always true, no matter what the truth values of its propositional variables are

Question 7

precedence rules

Answer 7

existential/ universal, negation, conjunction, disjunction, conditional, biconditional

Question 8

atomic proposition

Answer 8

a proposition that cannot be expressed in terms of simpler propositions

Question 9

truth values

Answer 9

true or false

Question 10

propositional variables

Answer 10

variables that represent propositions

Question 11

proposition

Answer 11

a statement that is either true or false, not both

Question 12

proof by contradiction

Question 13

formal proof

Answer 13

all steps are supplied and the rules for each step in the argument is given

Question 14

!p

Answer 14

negation of p

the truth value of !p is the opposite of p

“not p”

Question 15

p <–> q

Answer 15

biconditional statement

true when both p and q have the same truth value and false otherwise

“p if and only if q”

Question 16

p XOR q

Answer 16

exclusive or

true when only one proposition is true and false otherwise

“p or q, not both”

Question 17

p || q

Answer 17

disjunction of p and q

false when both p and q are false and true otherwise

“p or q”

Question 18

p && q

Answer 18

conjunction of p and q

true when both p and q are true and false otherwise

“p and q”

Question 19

ExP(x)

Answer 19

existential quantification of P(x)

“there exists”

Question 20

AxP(x)

Answer 20

universal quantification of P(x)

“for all”
“for each”

Question 21

p == q

Answer 21

logically equivalent

compound propositions that have the same truth values in all cases

(if p <–> q is a tautology)

Question 22

theorem

Answer 22

a statement that has been proven to be true

Question 23

lemma

Answer 23

a less important theorem that is helpful in the proof of other results

Question 24

definition of an even number

Answer 24

the integer n is even if there exists an integer k, such that n = 2k

Question 25

definition of an odd number

Answer 25

the integer n is odd if there exists an integer k, such that n = 2k - 1

Question 26

proof by contraposition

Question 27

p –> q

Answer 27

conditional statement

false when p is true and q is false, and true otherwise

“if p, then q”

p is the hypothesis
q is the conclusion

Question 28

compound proposition

Answer 28

the combination of one or more propositions to form new propositions using logical operators

Question 29

contradiction

Answer 29

a compound proposition that is always false, regardless of the truth values of its propositional variables

Question 30

solution

Answer 30

when a particular assignment of truth values makes the compound proposition true

Question 31

postconditions

Answer 31

the statements that the output should satisfy

Question 32

domain of discourse

Answer 32

asserts that a property is true for all values of a variable in a particular set of values

Question 33

definition of a rational number

Answer 33

the real number r is rational if there exists integers p and q, where q != 0, such that r = p / q

Question 34

counterexample

Answer 34

an element for which P(x) is false is a counterexample of AxP(x)

Question 35

informal proof

Answer 35

more than one rule of inference may be used in each step, the axioms being assumed and the rules of inference used are not explicitly stated

Question 36

argument form

Answer 36

a sequence of compound propositions involving propositional variables

Question 37

clause

Answer 37

a disjunction of variables or the negations of these variables

Question 38

contingency

Answer 38

a compound proposition that is neither a tautology nor a contradiction

Question 39

q –> p

Answer 39

converse of p –> q

false when p is false and q is true

Question 40

!p –> !q

Answer 40

inverse of p –> q

false when p is false and q is true

Question 41

!q –> !p

Answer 41

contrapositive of p –> q

false when p is true and q is false

Question 42

predicate

Answer 42

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

P(x), where P denotes the predicate

Question 43

preconditions

Answer 43

the statements that describe valid input

Question 44

quantification

Answer 44

expresses the extent to which a predicate is true over a range of values

Question 45

argument

Answer 45

a sequence of statements that end with a conclusion

Question 46

valid

Answer 46

the conclusion must follow from the truth of the preceding statements

Question 47

fallacies

Answer 47

common forms of incorrect reasoning that lead to invalid arguments

Question 48

conjecture

Answer 48

a statement that is being proposed as true

Question 49

corollary

Answer 49

a theorem that can be established directly from a theorem that has been proven

Question 50

axioms

Answer 50

also called postulates

statements we assume to be true

Question 51

proof

Answer 51

a valid argument that establishes the truth of a theorem