p.8
Principle of Mathematical Induction
What must appear in an induction proof in this course?
All other elements of the template, with equivalent wording being acceptable.
p.1
Implication and Biconditional
What is a biconditional in logic?
A biconditional p ↔ q (read 'p if and only if q') is true if and only if (p → q) and (q → p) are both true.
p.1
Tautology and Contradiction
What is a contradiction in logic?
A compound proposition that is false for all truth value assignments of its components.
p.7
Principle of Mathematical Induction
What is the conclusion of the induction step in an induction proof template?
Therefore S(k) → S(k + 1).
How are statements that are the conclusion of a rule of inference justified?
By the appropriate Rule of Inference and a reference to the line numbers of the premises.
What is the Rule of Contradiction?
The Rule of Contradiction states that if ¬p → F0 is true, then p is true. [(¬p → F0) ⇒ p]
p.2
Compound and Primitive Propositions
What is a proposition?
A proposition is a declarative sentence that is either true or false.
p.2
Truth Tables and Truth Values
What is the disjunction of propositions p and q?
The disjunction of p and q, p ∨ q, is true if and only if p is true or q is true (or both are true).
How are Fibonacci numbers defined recursively?
F0 = 0, F1 = 1, and for n > 1, Fn = Fn-1 + Fn-2.
p.7
Principle of Mathematical Induction
What does the Principle of Mathematical Induction require for proving?
Considerations of the axioms of the integers.
p.7
Principle of Mathematical Induction
What is the inductive hypothesis in an induction proof template?
Let k ≥ N and suppose S(k) is true.
How are statements that are logically equivalent to an earlier statement justified?
By the appropriate Law of Logic and a reference to the line number of the earlier statement.
What is the Rule of Conjunctive Simplification?
The Rule of Conjunctive Simplification states that if p ∧ q is true, then p is true. [(p ∧ q) ⇒ p]
p.2
Truth Tables and Truth Values
What is the conjunction of propositions p and q?
The conjunction of p and q, p ∧ q, is true if and only if both p and q are true.
p.8
Principle of Mathematical Induction
What is the base case in the template for a strong induction proof?
S(n0), ..., S(n1) are true because [Justification].
p.7
Principle of Mathematical Induction
What is the first condition in the strong form of the Principle of Mathematical Induction?
S(n0), S(n0 + 1), ..., S(n1) are true.
What is the Rule of the Destructive Dilemma?
[(p → q) ∧ (r → s) ∧ (¬q ∨ ¬s)] ⇒ (¬p ∨ ¬r)
What is Modus Ponens?
Modus Ponens is a rule of inference where if p and p → q are true, then q is true. [(p ∧ (p → q)) ⇒ q]
p.2
Truth Tables and Truth Values
What symbols are used to represent 'false' and 'true' in truth tables?
0 represents 'false' and 1 represents 'true'.
p.8
Principle of Mathematical Induction
What does the end of the induction step generally not show explicitly?
The implied application of the Law of Universal Generalization: ∀ x ≥ N, S(x) → S(x + 1).
p.7
Principle of Mathematical Induction
What is the PMI conclusion in an induction proof template?
By the principle of mathematical induction, S(n) is true for all integers n ≥ N.
p.5
Quantifiers and Open Statements
What is an open statement?
A declarative sentence that contains one or more variables, is not a proposition, and becomes a proposition when variables are replaced with allowable values.
What is the Rule of Proof by Cases?
The Rule of Proof by Cases states that if p → r and q → r are true, then (p ∨ q) → r is true. [(p → r) ∧ (q → r)] ⇒ [(p ∨ q) → r]
p.1
Implication and Biconditional
What is an implication in logic?
An implication p → q (read 'p implies q' or 'if p, then q') is true if and only if p being true implies q is true.
p.2
Truth Tables and Truth Values
What is the truth table for the conjunction of p and q?
p | q | p ∧ q
0 | 0 | 0
0 | 1 | 0
1 | 0 | 0
1 | 1 | 1
p.8
Principle of Mathematical Induction
What is the conclusion of the induction step in the template for a strong induction proof?
Therefore (S(n0) ∧ ... ∧ S(k)) → S(k + 1).
What is the second step in a proof by contradiction?
Use definitions and previously proven results to deduce a contradiction.
p.7
Principle of Mathematical Induction
What is the conclusion of the strong form of the Principle of Mathematical Induction?
For all n ≥ n0, S(n) is true.
What is the format for a proof by rules of inference?
Numbered lines in two columns: statements on the left and justifications on the right. The last line is the conclusion.
What is the Law of Syllogism?
The Law of Syllogism states that if p → q and q → r are true, then p → r is true. [(p → q) ∧ (q → r)] ⇒ (p → r)
p.1
Compound and Primitive Propositions
What is a primitive proposition?
A proposition that is not a compound proposition.
p.8
Principle of Mathematical Induction
What is the risk of invoking S(k + 1) as an assumption in an induction proof?
It invalidates the inductive step and may result in losing marks.
p.7
Principle of Mathematical Induction
What is the inductive hypothesis in a proof invoking the Principle of Mathematical Induction?
The assumption that p(k) is true.
What is the Rule of the Constructive Dilemma?
[(p → q) ∧ (r → s) ∧ (p ∨ r)] ⇒ (q ∨ s)
p.4
Implication and Biconditional
What does it mean for p to logically imply q?
p logically implies q, written p ⇒ q, if the proposition p → q is a tautology.
p.1
Truth Tables and Truth Values
What is the truth table for the biconditional p ↔ q?
0 0 1, 0 1 0, 1 0 0, 1 1 1
p.2
Truth Tables and Truth Values
What is the truth table for the disjunction of p and q?
p | q | p ∨ q
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1
p.7
Principle of Mathematical Induction
What is the second condition in the Principle of Mathematical Induction?
∀ k ≥ N, p(k) → p(k + 1) is true.
What is the Rule of Conjunction?
The Rule of Conjunction states that if p and q are true, then p ∧ q is true. [(p ∧ q) → (p ∧ q)]
p.1
Compound and Primitive Propositions
Why are parentheses required when building compound propositions?
To make the definition unambiguous. For example, (a ∧ b) ∨ c is different from a ∧ (b ∨ c).
p.8
Principle of Mathematical Induction
What is the inductive hypothesis (IH) in the template for a strong induction proof?
Let k ≥ n1 and suppose S(n0), S(n0 + 1), ..., S(k) are true.
What is the first step in a proof by contradiction?
Assume p is true and that q is false. Introduce all necessary variables.
p.7
Principle of Mathematical Induction
What is the second condition in the strong form of the Principle of Mathematical Induction?
For any k ≥ n1, if S(n0), ..., S(k) are all true, then S(k + 1) is also true.
What is Modus Tollens?
Modus Tollens is a rule of inference where if p → q and ¬q are true, then ¬p is true. [(p → q) ∧ ¬q] ⇒ ¬p
p.2
Truth Tables and Truth Values
What is the negation of a proposition p?
The negation of p, ¬p, is true if and only if the proposition p is false.
What does it mean for two propositions to be logically equivalent?
Propositions s1 and s2 are logically equivalent (written s1 ⇔ s2) if s1 is true whenever s2 is true, and vice versa.
p.5
Quantifiers and Open Statements
What are the two types of quantifiers?
Universal and existential quantifiers.
p.4
Compound and Primitive Propositions
What are the premises in an argument?
p1, p2, ..., pn are the premises.
p.1
Truth Tables and Truth Values
What is the truth table for the implication p → q?
0 0 1, 0 1 1, 1 0 0, 1 1 1
p.1
Tautology and Contradiction
What is a tautology in logic?
A compound proposition that is true for all truth value assignments of its components.
p.8
Principle of Mathematical Induction
What is the PMI conclusion in the template for a strong induction proof?
By the principle of mathematical induction, S(n) is true for all integers n ≥ n0.
What is the final step in a proof by contradiction?
Conclude that p → q is true.
p.7
Principle of Mathematical Induction
What is the base case in an induction proof template?
S(N) is true because ... [Justification]
How are premises introduced in a proof by rules of inference?
With the justification 'Premise'.
What is the Rule of Disjunctive Syllogism?
The Rule of Disjunctive Syllogism states that if p ∨ q and ¬p are true, then q is true. [(p ∨ q) ∧ ¬p] ⇒ q
p.1
Compound and Primitive Propositions
What is a compound proposition?
A proposition formed by connecting two propositions with conjunction, disjunction, implication, or biconditional or by the negation of a proposition.
p.8
Principle of Mathematical Induction
What elements in the induction proof template are optional to show?
Italicized elements in square parentheses and underlined headings explaining the template.
p.7
Principle of Mathematical Induction
What is the base step in a proof invoking the Principle of Mathematical Induction?
The step where p(N) is shown to be true.
p.7
Principle of Mathematical Induction
What is the inductive step in a proof invoking the Principle of Mathematical Induction?
The step where p(k) is assumed to be true and used to prove p(k + 1).
What is the Rule of Conditional Proof?
[(p ∧ q) ∧ [p → (q → r)]] ⇒ r
When is an argument considered valid?
An argument is valid if the conclusion is true whenever all of the premises are true.
