Study sheet: Logic and Mathematical Reasoning

📋 Course Outline

1. Propositions and Quantifiers
2. Negation of Quantified Statements
3. Logical Connectives
4. Implication and Equivalence
5. Logical Distributivity
6. Proof Methods
7. Simple and Double Induction
8. Strong Induction

📖 1. Propositions and Quantifiers

🔑 Key Concepts & Definitions

• Proposition : a sentence for which it is possible to determine whether it is true or false
• Universal Quantifier : The symbol ∀ means “for every” or “whatever the value of,” and asserts that a proposition holds for every element of the specified set.
• Existential Quantifier : The symbol ∃ means “there exists at least one,” while ∃! means “there exists exactly one.”
• Predicate : When a proposition depends on a variable x belonging to a set E, it can be written P(x), with E typically equal to N, Z, Q, R, C, or a subset of one of these sets.

★ Must-know

📌 The order of quantifiers is fundamental because changing ∀x ∃y into ∃y ∀x can change the truth value of a statement.

Further detail

📌 The truth of a quantified statement can depend on the set considered, as shown by ∃! x ∈ R*, x = x² being true whereas ∃! x ∈ R, x = x² is false.

💡 Memory Hook

∀ covers every element, whereas ∃ requires at least one.

📖 2. Negation of Quantified Statements

🔑 Key Concepts & Definitions

• Negation : true when P is false and false when P is true

★ Must-know

• To negate a quantified proposition, exchange every ∀ and ∃ in the variable conditions and negate the conclusion.

• The negation of a conjunction satisfies $\neg(P \land Q) \iff (\neg P) \lor (\neg Q)$.

• The negation of a disjunction satisfies $\neg(P \lor Q) \iff (\neg P) \land (\neg Q)$.

• The negation of an implication satisfies $\neg(P \Rightarrow Q) \iff P \land (\neg Q)$.

Further detail

• The negation of “∀x ∈ R, f(x) > 0” is “∃x ∈ R, f(x) ≤ 0.”

💡 Memory Hook

Exchange quantifiers, then negate the conclusion.

📖 3. Logical Connectives

🔑 Key Concepts & Definitions

• Conjunction : true if and only if both P and Q are true
• Disjunction : true if and only if at least one of P or Q is true, including the case where both are true
• Implication : The implication P ⇒ Q means that if P is true, then Q is true.
• Contrapositive : The contrapositive of P ⇒ Q is (¬Q) ⇒ (¬P).
• Reciprocal Implication : The reciprocal implication of P ⇒ Q is Q ⇒ P.

💡 Memory Hook

AND requires both propositions, whereas OR requires at least one.

📖 4. Implication and Equivalence

🔑 Key Concepts & Definitions

• Equivalence : P ⇔ Q means that both P ⇒ Q and Q ⇒ P are true, so P is true if and only if Q is true.

★ Must-know

• An implication is equivalent to its contrapositive: $(P \Rightarrow Q) \iff (\neg Q \Rightarrow \neg P)$.

Further detail

• For real x, $x^2 \le 1 \iff -1 \le x \le 1$.

💡 Memory Hook

P ⇒ Q is one-way, whereas P ⇔ Q requires both directions.

📖 5. Logical Distributivity

📝 Essential Points

• The distributive laws are $((P \land Q) \lor R) \iff ((P \lor R) \land (Q \lor R))$ and $((P \lor Q) \land R) \iff ((P \land R) \lor (Q \land R))$.

📖 6. Proof Methods

★ Must-know

• To prove P ⇒ Q directly, assume P is true and derive Q directly.

• To prove P ⇒ Q by contraposition, assume that Q is false and show that P is false.

• To prove a statement by contradiction, assume that the desired result is false and derive a contradiction.

• To prove P ⇔ Q, prove P ⇒ Q and then prove Q ⇒ P.

• Analysis–synthesis first derives necessary conditions from a supposed solution, then checks that the candidate solutions obtained are sufficient.

Further detail

• To prove ∀x ∈ E, P(x), begin with an arbitrary x ∈ E and prove P(x), possibly by splitting into cases.

💡 Memory Hook

Direct proof, contraposition, contradiction, then analysis–synthesis.

📖 7. Simple and Double Induction

★ Must-know

• Simple induction proves P(n) for every n ≥ n0 by establishing P(n0) and showing that P(n) implies P(n+1) for any n ≥ n0.

• Double induction proves P(n) for every n ≥ n0 by establishing P(n0) and P(n0+1), then showing that P(n) and P(n+1) imply P(n+2) for any n ≥ n0.

Further detail

📌 In an induction hypothesis P(n), it is forbidden to insert a universal quantifier such as “∀n ∈ N”; the hypothesis must concern the specific index n.

💡 Memory Hook

Simple induction uses one base case and one predecessor; double induction uses two base cases and two predecessors.

📖 8. Strong Induction

★ Must-know

• Strong induction proves P(n) for every n ≥ n0 by establishing P(n0), then showing that if P(k) is true for every k ∈ {n0,…,n}, P(n+1) is true.

Further detail

• For the sequence defined by u1 = 1 and u(n+1) = (u1 + u2 + ··· + un)/n, strong induction can prove that un = 1 for every n ∈ N*.

💡 Memory Hook

All previous cases hold → the next case follows.

📊 Synthesis Tables

Induction Methods

Method	Initialisation	Induction hypothesis	Step
Simple	P(n0)	P(n)	P(n+1)
Double	P(n0) and P(n0+1)	P(n) and P(n+1)	P(n+2)
Strong	P(n0)	P(k) for every k from n0 to n	P(n+1)