C959 Flashcards (Master set) questions
and answers
Proof by Exhaustion - answer Prove the statement by checking each element individually. Unlike proof by
cases, exhaustive proof looks at every case in a way that is not general.
Proof by Counterexample - answer Used to disprove a universal statement. For example, to disprove the
statement, "All prime numbers are odd" find one example where this statement is false—the number 2
—which is both even and prime.
Direct Proof - answer In the direct proof, we assume the hypothesis p is true and we try to prove that q is
true. Thus making p→q true.
Proof by Contrapositive - answer A proof that makes use of the fact that p→q is equivalent to its
contrapositive ¬q→¬p. So we assume that ¬q is true and try to prove that ¬p is true.
Proof by Contradiction - answer An indirect proof where if the theorem being proven has the form p →
q, then the beginning assumption is p ∧ ¬q which is logically equivalent to ¬(p → q).
Proof by Cases - answer In proof by case, we are looking at all the possible cases that might arise in a
theorem.
∴ - answer Means "therefore".
Conditional Statements - answer If p then q. p → q. Only not true when p is true and q is false. It breaks
the contract.
Converse - answer Converse of p → q is q → p.
Contrapositive - answer Contrapositive of p → q is ¬q → ¬p.
, Inverse - answer Inverse of p → q is ¬p → ¬q.
Biconditional Statement - answer p if and only if q. p ↔ q. True when p and q have the same truth value
(including False ↔ False) and is false when p and q have different truth values.
Logical Equivalence - answer p is logically equivalent to q. p ≡ q. Logically equivalent if they have the
same truth value regardless of the truth values of their individual propositions. So p ≡ ¬¬p or ¬p ≡ p →
¬q.
Logical Operator - answer Conjunction — p ∧ q. True only if p and q are true.
Disjunction — p ∨ q. True when either of p or q, or both is true.
Exclusive or — p ⊕ q. True if either one of p or q is true but not both.
Negation — ¬p. Negates value. If True then not True, if False then not False.
Order of Operations - answer 1. ¬ (not)
2. ∧ (and)
3. ∨ (or)
4. →
5. ↔
Predicate - answer Logical statement whose truth value is a function of one or more variables.
Free Variable - answer Variable is free to take on any value in the domain. In (∀x P(x)) ∧ Q(x), Q(x) is the
free variable.
Bound Variable - answer Variable is bound to a quantifier. In (∀x P(x)) ∧ Q(x), P(x) is the bound variable.
DeMorgan's Laws for Quantifiers - answer ¬∀ x F(x) as "Not every bird can fly." Which is logically
equivalent (≡) to ∃ x ¬ F(x) as "There exists a bird that cannot fly."
¬∃ x Q(x) as "It is not true that there is a child in the class who is absent today." Which is logically
equivalent (≡) to ∀ x ¬ Q(x) as "Every child in the class is not absent today."
and answers
Proof by Exhaustion - answer Prove the statement by checking each element individually. Unlike proof by
cases, exhaustive proof looks at every case in a way that is not general.
Proof by Counterexample - answer Used to disprove a universal statement. For example, to disprove the
statement, "All prime numbers are odd" find one example where this statement is false—the number 2
—which is both even and prime.
Direct Proof - answer In the direct proof, we assume the hypothesis p is true and we try to prove that q is
true. Thus making p→q true.
Proof by Contrapositive - answer A proof that makes use of the fact that p→q is equivalent to its
contrapositive ¬q→¬p. So we assume that ¬q is true and try to prove that ¬p is true.
Proof by Contradiction - answer An indirect proof where if the theorem being proven has the form p →
q, then the beginning assumption is p ∧ ¬q which is logically equivalent to ¬(p → q).
Proof by Cases - answer In proof by case, we are looking at all the possible cases that might arise in a
theorem.
∴ - answer Means "therefore".
Conditional Statements - answer If p then q. p → q. Only not true when p is true and q is false. It breaks
the contract.
Converse - answer Converse of p → q is q → p.
Contrapositive - answer Contrapositive of p → q is ¬q → ¬p.
, Inverse - answer Inverse of p → q is ¬p → ¬q.
Biconditional Statement - answer p if and only if q. p ↔ q. True when p and q have the same truth value
(including False ↔ False) and is false when p and q have different truth values.
Logical Equivalence - answer p is logically equivalent to q. p ≡ q. Logically equivalent if they have the
same truth value regardless of the truth values of their individual propositions. So p ≡ ¬¬p or ¬p ≡ p →
¬q.
Logical Operator - answer Conjunction — p ∧ q. True only if p and q are true.
Disjunction — p ∨ q. True when either of p or q, or both is true.
Exclusive or — p ⊕ q. True if either one of p or q is true but not both.
Negation — ¬p. Negates value. If True then not True, if False then not False.
Order of Operations - answer 1. ¬ (not)
2. ∧ (and)
3. ∨ (or)
4. →
5. ↔
Predicate - answer Logical statement whose truth value is a function of one or more variables.
Free Variable - answer Variable is free to take on any value in the domain. In (∀x P(x)) ∧ Q(x), Q(x) is the
free variable.
Bound Variable - answer Variable is bound to a quantifier. In (∀x P(x)) ∧ Q(x), P(x) is the bound variable.
DeMorgan's Laws for Quantifiers - answer ¬∀ x F(x) as "Not every bird can fly." Which is logically
equivalent (≡) to ∃ x ¬ F(x) as "There exists a bird that cannot fly."
¬∃ x Q(x) as "It is not true that there is a child in the class who is absent today." Which is logically
equivalent (≡) to ∀ x ¬ Q(x) as "Every child in the class is not absent today."
