Chapter 1 - The Foundations: Logic and Proofs

Question 1

¬ p (negation of p)

Answer 1

th proposition with truth value opposite to the truth value of p

Question 2

compound propositions

Answer 2

a proposition constructed by combining propositions using logical operators

Question 3

p ⋎ q (disjunction of p and q)

Answer 3

the proposition “p or q,” which is true if and only if at least one of p and q is true

Question 4

p ⋏ q (conjunction of p and q)

Answer 4

the proposition “p and q,” which is true if and only of both p and q are true

Question 5

p → q (p implies q)

Answer 5

the proposition “if p, then q,” which is false if and only of p is true and q is false

Question 6

converse of p → q

Answer 6

the conditional statement q → p

Question 7

contrapositive of p → q

Answer 7

the conditional statement ¬q → ¬p

Question 8

inverse of p → q

Answer 8

the conditional statement ¬p → ¬q

Question 9

p ⇄ q (biconditional)

Answer 9

the proposition “p if and only if q,” which is true if and only if p and q have the same truth value

Question 10

bit

Answer 10

either a 0 or 1

Question 11

Boolean variable

Answer 11

a variavle that has a value of 0 or 1

Question 12

tautology

Answer 12

a compound proposition that is always true

Question 13

contradiction

Answer 13

a compound proposition that is always false

Question 14

contingency

Answer 14

a compound proposition that is sometimes true and sometimes false

Question 15

logically equivalent

Answer 15

compound propositions that always have the same truth values

Question 16

propositional function

Answer 16

a statement containing one or more variables that becomes a proposition when each of its variables is assignrd a value or is bound by a quantifier

Question 17

domain (or universe) of discourse

Answer 17

the values a variable in a propositional function may take

Question 18

∃xP(x) (existential quantification of P(x))

Answer 18

There exists

Question 19

∀xP(x) (universal quantification of P(x))

Answer 19

For all

Question 20

logically equivalent expressions

Answer 20

Both arguments have the same meaning

Question 21

valid argument

Answer 21

an argument with a valid argument form

Question 22

fallacy

Answer 22

an invalid argument form often used incorrectly as a rule of inference (or sometimes, more generally, an incorrect argument)

Question 23

proof by contraposition

Answer 23

a proof that p → q is true that proceeds by showing that p must be false when q is false

Question 24

proof by contradiction

Answer 24

a proof that p is true based on the truth of the conditional statement ¬p → ¬q, where q is a contradiction

Question 25

counterexample

Answer 25

an element x such that P(x) is false

Question 26

rational number

Answer 26

a number that can be expressed as the ratio of two integers p and q such that q ≠ 0