Chapter 1 - The Foundations: Logic and Proofs

Question 1

proposition

Answer 1

a statement that is true or false

Question 2

propositional variable

Answer 2

a variable that represents a proposition

Question 3

truth value

Answer 3

true or false

Question 4

¬ p (negation of p)

Answer 4

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

Question 5

logical operators

Answer 5

operators used to combine propositions

Question 6

compound propositions

Answer 6

a proposition constructed by combining propositions using logical operators

Question 7

truth table

Answer 7

a table displaying all possible truth cakes of propositions

Question 8

p ⋎ q (disjunction of p and q)

Answer 8

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

Question 9

p ⋏ q (conjunction of p and q)

Answer 9

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

Question 10

p ⊕ q (exclusive or of p and q)

Answer 10

the proposition “p XOR q,” which is true when exactly one of p and q is true

Question 11

p → q (p implies q)

Answer 11

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

Question 12

converse of p → q

Answer 12

the conditional statement q → p

Question 13

contrapositive of p → q

Answer 13

the conditional statement ¬q → ¬p

Question 14

inverse of p → q

Answer 14

the conditional statement ¬p → ¬q

Question 15

p ⇄ q (biconditional)

Answer 15

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

Question 16

bit

Answer 16

either a 0 or 1

Question 17

Boolean variable

Answer 17

a variavle that has a value of 0 or 1

Question 18

bit operation

Answer 18

an operation on a bit or bits

Question 19

bit string

Answer 19

a list of bits

Question 20

bitwise operations

Answer 20

operations on bit strings that operate on each bit in one strong and the corresponding bit in the other string

Question 21

logic gate

Answer 21

a logic element that performs a logical operation on one or more bits to produce an output bit

Question 22

logic circuit

Answer 22

a switching circuit made up of logic gates that produces one or more output bits

Question 23

tautology

Answer 23

a compound proposition that is always true

Question 24

contradiction

Answer 24

a compound proposition that is always false

Question 25

contingency

Answer 25

a compound proposition that is sometimes true and sometimes false

Question 26

consistent compound propositions

Answer 26

compound propositions for which there is an assignment of truth values to the variables that makes all these propositions true

Question 27

satisfiable compound proposition

Answer 27

a compound proposition for which there is an assignment of truth values to its variables that makes all these propositions true

Question 28

logically equivalent compound propositions

Answer 28

compound propositions that always have the same truth values

Question 29

predicate

Answer 29

part of a sentence that attributes a property to the subject

Question 30

propositional function

Answer 30

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 31

domain (or universe) of discourse

Answer 31

the values a variable in a propositional function may take

Question 32

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

Answer 32

the proposition that is true if and only if there exists an x in the domain such that P(x) is true

Question 33

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

Answer 33

the proposition that is true if and only if P(x) is true for every x in the domain

Question 34

logically equivalent expressions

Answer 34

expressions that have the same truth value no matter which propositional functions and domains are used

Question 35

free variable

Answer 35

a variable not bound in a propositional function

Question 36

bound variable

Answer 36

a variable that is quantified

Question 37

scope of a quantifier

Answer 37

portion of a statement where the quantifier binds its variable

Question 38

argument

Answer 38

a sequence of statements

Question 39

argument form

Answer 39

a sequence of compound propositions involving propositional variables

Question 40

premise

Answer 40

a statement, in an argument, or argument form, other than the final one

Question 41

conclusion

Answer 41

the final statement in an argument or argument form

Question 42

valid argument form

Answer 42

a sequence of compound propositions involving propositional variables where the truth of all the premises implies the truth of the conclusion

Question 43

valid argument

Answer 43

an argument with a valid argument form

Question 44

rule of inference

Answer 44

a valid argument form that can be used in the demonstration that arguments are valid

Question 45

fallacy

Answer 45

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

Question 46

circular reasoning or begging the question

Answer 46

reasoning where one or more steps are based on the truth of the statement being proved

Question 47

theorem

Answer 47

a mathematical assertion that can be shown to be true

Question 48

conjecture

Answer 48

a mathematical assertion proposed to be true, but that has not been proven

Question 49

proof

Answer 49

a demonstration that a theorem is true

Question 50

axiom

Answer 50

a statement that is assumed to be true and that can be used as a basis for proving theorems

Question 51

lemma

Answer 51

a theorem used to prove other theorems

Question 52

corollary

Answer 52

a proposition that can be proved as a consequence of a theorem that has just been proved

Question 53

vacuous proof

Answer 53

a proof that p → q is true based on the fact that p is false

Question 54

trivial proof

Answer 54

a proof that p → q is true based on the fact that q is true

Question 55

direct proof

Answer 55

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

Question 56

proof by contraposition

Answer 56

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

Question 57

proof by contradiction

Answer 57

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

Question 58

exhaustive proof

Answer 58

a proof that establishes a result by checking a list of all possible cases

Question 59

proof by cases

Answer 59

a proof broken into separate cases. where these cases cover all possibilities

Question 60

without loss of generality

Answer 60

an assumption in a proof that makes it possible to prove a theorem by reducing the number of cases to consider in the proof

Question 61

counterexample

Answer 61

an element x such that P(x) is false

Question 62

constructive existence proof

Answer 62

a proof that an element with a specified property exists that explicitly finds such an element

Question 63

nonconstructive existence proof

Answer 63

a proof that an element with a specified property exists that does not explicitly find such an element

Question 64

rational number

Answer 64

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

Question 65

uniqueness proof

Answer 65

a proof that there is exactly one element satisfying a specific property