Back to Subject

Practice MCQ

Unit 1 - Notes

MTH401

Unit 1: Logic and Proofs

1. Propositional Logic

Logic forms the basis of all mathematical reasoning and automated reasoning (computing).

1.1 Basic Definitions

Proposition: A declarative sentence that is either true (T) or false (F), but not both.
- Example: "Paris is in France" (Proposition, True).
- Example: " $x + 1 = 2$ " (Not a proposition; depends on variable $x$ ).
Atomic Proposition: A proposition that cannot be broken down into simpler propositions.
Compound Proposition: Formed by combining atomic propositions using logical operators.

1.2 Logical Operators (Connectives)

Given propositions $p$ and $q$ :

Connective	Name	Notation	Meaning	Truth Condition
Negation	NOT	$\neg p$	"It is not the case that p"	True when $p$ is False.
Conjunction	AND	$p \land q$	"p and q"	True only if both $p$ and $q$ are True.
Disjunction	OR	$p \lor q$	"p or q"	True if at least one of $p$ or $q$ is True. (Inclusive).
Exclusive OR	XOR	$p \oplus q$	"p or q, but not both"	True if exactly one of $p$ or $q$ is True.
Implication	IMPLIES	$p \rightarrow q$	"If p, then q"	False only when $p$ is True and $q$ is False.
Biconditional	IFF	$p \leftrightarrow q$	"p if and only if q"	True when $p$ and $q$ have the same truth value.

1.3 The Conditional Statement ( $p \rightarrow q$ )

This is often the source of confusion. In $p \rightarrow q$ :

$p$ is the hypothesis (antecedent/premise).
$q$ is the conclusion (consequence).
Crucial Concept: The statement is considered true if the hypothesis is false (Vacuous Truth). "If pigs can fly, then I am the King of England" is a true statement logically.

Related Conditionals:

Converse: $q \rightarrow p$
Inverse: $\neg p \rightarrow \neg q$
Contrapositive:
- Note: A conditional statement and its contrapositive are logically equivalent.

2. Propositional Equivalences

2.1 Classification of Compound Propositions

Tautology: A compound proposition that is always true, regardless of the truth values of its variables (e.g., $p \lor \neg p$ ).
Contradiction: A compound proposition that is always false (e.g., $p \land \neg p$ ).
Contingency: A proposition that is neither a tautology nor a contradiction.

2.2 Logical Equivalence

Two propositions $p$ and $q$ are logically equivalent (denoted $p \equiv q$ ) if $p \leftrightarrow q$ is a tautology. They have identical truth tables.

2.3 Important Laws of Logic

These laws are used to simplify complex logical expressions algebraically.

Identity Laws: $p \land T \equiv p$ ; $p \lor F \equiv p$
Domination Laws: $p \lor T \equiv T$ ; $p \land F \equiv F$
Idempotent Laws: $p \lor p \equiv p$ ; $p \land p \equiv p$
Double Negation Law: $\neg(\neg p) \equiv p$
Commutative Laws: $p \lor q \equiv q \lor p$ ; $p \land q \equiv q \land p$
Associative Laws: $(p \lor q) \lor r \equiv p \lor (q \lor r)$
Distributive Laws:
- $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
- $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
De Morgan's Laws (CRITICAL):
- $\neg(p \land q) \equiv \neg p \lor \neg q$
- $\neg(p \lor q) \equiv \neg p \land \neg q$
Absorption Laws: $p \lor (p \land q) \equiv p$ ; $p \land (p \lor q) \equiv p$
Implication Equivalence: $p \rightarrow q \equiv \neg p \lor q$

3. Predicates and Quantifiers

3.1 Predicates

A predicate is a statement involving variables, such as $P(x): x > 3$ .

$P$ is the predicate logic.
$x$ is the subject.
The statement becomes a proposition only when a value is assigned to $x$ .

3.2 Quantifiers

Quantifiers define the "scope" of the variables in a predicate.

Universal Quantifier ( $\forall$ ):
- Notation: $\forall x P(x)$
- Meaning: "For all $x$ , $P(x)$ is true."
- True if $P(x)$ is true for every element in the domain.
- False if there is at least one $x$ for which $P(x)$ is false (Counterexample).
Existential Quantifier ( $\exists$ ):
- Notation: $\exists x P(x)$
- Meaning: "There exists an $x$ such that $P(x)$ is true."
- True if there is at least one $x$ in the domain for which $P(x)$ is true.
- False if $P(x)$ is false for every $x$ in the domain.

3.3 De Morgan's Laws for Quantifiers

When negating a quantified expression, flip the quantifier and negate the predicate.

$\neg \forall x P(x) \equiv \exists x \neg P(x)$
$\neg \exists x P(x) \equiv \forall x \neg P(x)$

3.4 Nested Quantifiers

When multiple quantifiers are used (e.g., $\forall x \exists y (x + y = 0)$ ):

Order matters if the quantifiers are different ( $\forall \exists$ vs $\exists \forall$ ).
$\forall x \exists y$ : For every $x$ , you can find a specific $y$ .
$\exists y \forall x$ : There is one specific $y$ that works for every single $x$ .

4. Introduction to Proofs

4.1 Terminology

Theorem: A mathematical statement that can be shown to be true.
Proof: A valid argument that establishes the truth of a theorem.
Axioms/Postulates: Statements assumed to be true without proof.
Lemma: A "helper" theorem used to prove a larger theorem.
Corollary: A result that follows almost immediately from a theorem.
Conjecture: A statement believed to be true but not yet proven.

4.2 Rules of Inference

Proofs rely on valid argument forms. The most common is Modus Ponens:

Premise 1: $p \rightarrow q$
Premise 2: $p$
Conclusion: $\therefore q$

5. Methods of Proof

5.1 Direct Proof

Used to prove implications of the form $p \rightarrow q$ .

Method:
1. Assume that $p$ (hypothesis) is true.
2. Use axioms, definitions, and logical rules to deduce that $q$ must also be true.
Example: Prove "If is an odd integer, then is odd."
- Assume $n$ is odd. By definition, $n = 2k + 1$ for some integer $k$ .
- $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ .
- This is of the form $2(\text{integer}) + 1$ , which is the definition of an odd integer. $\blacksquare$

5.2 Proof by Contraposition (Indirect Proof)

Based on the equivalence $p \rightarrow q \equiv \neg q \rightarrow \neg p$ .

Method:
1. Assume $\neg q$ (negation of conclusion) is true.
2. Show that $\neg p$ (negation of hypothesis) must be true.
Usage: Useful when "not $q$ " provides more algebraic structure than " $p$ ".
Example: Prove "If is odd, then is odd."
- Contrapositive: If $n$ is even (not odd), then $3n + 2$ is even (not odd).
- Assume $n = 2k$ . Then $3n + 2 = 3(2k) + 2 = 2(3k + 1)$ .
- This is logically even. Since the contrapositive is true, the original statement is true.

5.3 Vacuous Proof

Used to prove $p \rightarrow q$ when $p$ is known to be False.

Since an implication is only false when $T \rightarrow F$ , if $p$ is False, the statement is automatically True.
Example: proving a property for the empty set.

5.4 Trivial Proof

Used to prove $p \rightarrow q$ when $q$ is known to be True.

If the conclusion is true, the implication is true regardless of the hypothesis.
Example: "If it is raining, then $1+1=2$ ." Since $1+1=2$ is always true, the implication holds.

5.5 Proof by Contradiction

Based on the fact that a proposition cannot be both true and false.

Method:
1. To prove $p$ , assume $\neg p$ is true.
2. Show that this assumption leads to a logical contradiction (e.g., $r \land \neg r$ or $0=1$ ).
3. Conclude that $\neg p$ must be false, so $p$ implies true.
Classic Example: Prove is irrational.
- Assume $\sqrt{2}$ is rational ( $\sqrt{2} = a/b$ in lowest terms).
- Algebra leads to both $a$ and $b$ being even, which contradicts the "lowest terms" assumption.

5.6 Proof of Equivalence (Biconditionals)

To prove "p if and only if q" ( $p \leftrightarrow q$ ):

Method: You must prove two parts:
1. $p \rightarrow q$
2. $q \rightarrow p$ (The converse)

5.7 Counterexamples

Used to disprove a universal statement ( $\forall x P(x)$ ).

Method: Find a single element $c$ in the domain where $P(c)$ is false.
Example: Disprove "For all real numbers , ."
- Counterexample: Let $x = 0.5$ . $0.5^2 = 0.25$ .
- $0.25$ is not greater than $0.5$. The statement is false.

6. Proof Strategy

6.1 Forward Reasoning

Starting with the premises and moving toward the conclusion. This is the standard method for Direct Proofs.

6.2 Backward Reasoning

Starting with the conclusion and asking "What is required to prove this is true?" Work backward until you reach the hypothesis.

Warning: Ensure the steps are reversible when writing the final proof.

6.3 Proof by Cases (Exhaustion)

If the domain is finite or can be divided into distinct categories (e.g., $n$ is strictly positive, negative, or zero), prove the theorem separately for each case.

$(p_1 \lor p_2 \lor \dots \lor p_n) \rightarrow q$
You must prove $(p_1 \rightarrow q) \land (p_2 \rightarrow q) \dots$

7. Common Mistakes in Proofs

Affirming the Consequent (Fallacy):
- Assuming $p \rightarrow q$ is true and $q$ is true, then concluding $p$ is true.
- Error: "If I have the flu, I cough. I am coughing. Therefore, I have the flu." (Incorrect; you could have a cold).
Denying the Antecedent (Fallacy):
- Assuming $p \rightarrow q$ is true and $\neg p$ is true, then concluding $\neg q$ is true.
- Error: "If I have the flu, I cough. I do not have the flu. Therefore, I am not coughing." (Incorrect; you could be choking).
Begging the Question (Circular Reasoning):
- Using the statement you are trying to prove as an assumption in the proof steps.
Arithmetic/Algebraic Errors:
- Simple calculation mistakes that invalidate the logic chain.
Generalizing from Specific Examples:
- Showing $P(1)$ is true and $P(2)$ is true does not prove $\forall x P(x)$ .