DM-02

Course 2

Predicate Logic and Proofs

Extend propositional logic to predicate logic with quantifiers, master rules of inference, and learn rigorous proof techniques that form the foundation of mathematical reasoning.

Learning Objectives

Understand predicates and propositional functions with multiple variables
Master universal and existential quantifiers and their properties
Work with nested quantifiers and understand quantifier precedence
Apply rules of inference including Modus Ponens, Modus Tollens, and syllogisms
Construct proofs using direct proof, contraposition, and contradiction methods
Recognize and construct existence, uniqueness, and equivalence proofs

1. Predicates and Quantifiers

Definition 2.1: Predicate (Propositional Function)

A predicate (or propositional function) is a statement involving variables. When variables are replaced with specific values from a domain, the predicate becomes a proposition with a truth value.

We denote a predicate as $P(x)$ , $Q(x, y)$ , etc., where:

$P(x)$ is a unary predicate (one variable)
$Q(x, y)$ is a binary predicate (two variables)
$R(x_1, x_2, \ldots, x_n)$ is an n-ary predicate (n variables)

Example: Predicates

Example 1: Let $P(x)$ be "x > 3" where the domain is integers.

$P(5)$ is true (since 5 > 3)
$P(2)$ is false (since 2 ≯ 3)

Example 2: Let $Q(x, y)$ be "x + y = 10" where the domain is real numbers.

$Q(3, 7)$ is true
$Q(5, 4)$ is false

Definition 2.2: Domain of Discourse

The domain of discourse (or universe of discourse) is the set of all possible values that variables in a predicate can take. It must be specified to determine the truth value of quantified statements.

Quantifiers

Definition 2.3: Universal Quantifier

The universal quantifier $\forall$ (read "for all" or "for every") expresses that a predicate is true for all values in the domain.

$\forall x P(x)$ means "P(x) is true for all x in the domain."

This is equivalent to the conjunction: $P(x_1) \land P(x_2) \land P(x_3) \land \cdots$ for all $x_i$ in the domain.

Definition 2.4: Existential Quantifier

The existential quantifier $\exists$ (read "there exists" or "for some") expresses that a predicate is true for at least one value in the domain.

$\exists x P(x)$ means "There exists an x in the domain such that P(x) is true."

This is equivalent to the disjunction: $P(x_1) \lor P(x_2) \lor P(x_3) \lor \cdots$ for all $x_i$ in the domain.

Definition 2.5: Uniqueness Quantifier

The uniqueness quantifier $\exists!$ (read "there exists a unique") expresses that there is exactly one value in the domain for which the predicate is true.

$\exists! x P(x)$ can be expressed as: $\exists x (P(x) \land \forall y (P(y) \rightarrow y = x))$

Note

Precedence of Quantifiers:

The quantifiers $\forall$ and $\exists$ have higher precedence than all logical operators ( $\land, \lor, \rightarrow, \leftrightarrow$ ).

For example, $\forall x P(x) \lor Q(x)$ means $(\forall x P(x)) \lor Q(x)$ , not $\forall x (P(x) \lor Q(x))$ .

Example: Quantifier Statements

Let the domain be all real numbers:

$\forall x (x^2 \geq 0)$
True - "For all real numbers x, x² is non-negative."
$\exists x (x^2 = -1)$
False - "There exists a real number x such that x² = -1." (No real number satisfies this)
$\forall x \exists y (x + y = 0)$
True - "For every real number x, there exists a y such that x + y = 0." (y = -x works)
$\exists x \forall y (xy = y)$
True - "There exists an x such that for all y, xy = y." (x = 1 works)

2. Nested Quantifiers

When multiple quantifiers appear in a statement, they are called nested quantifiers. The order of quantifiers matters and can significantly change the meaning of a statement.

Theorem 2.1: Order of Quantifiers

The order of nested quantifiers is important unless all quantifiers are of the same type:

$\forall x \forall y P(x, y) \equiv \forall y \forall x P(x, y)$ (order doesn't matter)
$\exists x \exists y P(x, y) \equiv \exists y \exists x P(x, y)$ (order doesn't matter)
$\forall x \exists y P(x, y) \not\equiv \exists y \forall x P(x, y)$ (order DOES matter!)

Example: Importance of Quantifier Order

Let P(x, y) mean "x loves y" where the domain is all people:

$\forall x \exists y P(x, y)$

"For every person x, there exists a person y that x loves."

Meaning: Everyone loves someone (possibly different people).

$\exists y \forall x P(x, y)$

"There exists a person y such that for every person x, x loves y."

Meaning: There is someone who is loved by everyone.

These two statements have very different meanings! The first can be true even if there's no universally loved person.

Definition 2.6: Prenex Normal Form

A formula is in Prenex Normal Form (PNF) if all quantifiers appear at the beginning:

Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \phi(x_1, x_2, \ldots, x_n)

where each $Q_i$ is either $\forall$ or $\exists$ , and $\phi$ is a quantifier-free formula.

Theorem 2.2: De Morgan's Laws for Quantifiers

The negation of quantified statements follows these rules:

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

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

To negate a quantified statement: change the quantifier type and negate the predicate.

Example: Negating Quantified Statements

Example 1: Negate "All students passed the exam."

Original: $\forall x \text{Passed}(x)$

Negation: $\neg \forall x \text{Passed}(x) \equiv \exists x \neg \text{Passed}(x)$

"There exists a student who did not pass."

Example 2: Negate $\forall x \exists y (x + y = 0)$

$\neg \forall x \exists y (x + y = 0)$

$\equiv \exists x \neg \exists y (x + y = 0)$ (negate outer quantifier)

$\equiv \exists x \forall y \neg(x + y = 0)$ (negate inner quantifier)

$\equiv \exists x \forall y (x + y \neq 0)$

3. Rules of Inference

Rules of inference are logical rules that allow us to derive conclusions from premises. A valid argument is one where the conclusion follows logically from the premises using these rules.

Definition 2.7: Valid Argument

An argument consists of premises (hypotheses) and a conclusion. An argument is valid if whenever all premises are true, the conclusion must also be true.

For premises $p_1, p_2, \ldots, p_n$ and conclusion $q$ , the argument is valid if $(p_1 \land p_2 \land \cdots \land p_n) \rightarrow q$ is a tautology.

Propositional Rules of Inference

Theorem 2.3: Basic Rules of Inference

Modus Ponens

Premises: $p$ , $p \rightarrow q$

Conclusion: $q$

Modus Tollens

Premises: $\neg q$ , $p \rightarrow q$

Conclusion: $\neg p$

Hypothetical Syllogism

Premises: $p \rightarrow q$ , $q \rightarrow r$

Conclusion: $p \rightarrow r$

Disjunctive Syllogism

Premises: $p \lor q$ , $\neg p$

Conclusion: $q$

Addition

Premise: $p$

Conclusion: $p \lor q$

Simplification

Premise: $p \land q$

Conclusion: $p$

Conjunction

Premises: $p$ , $q$

Conclusion: $p \land q$

Resolution

Premises: $p \lor q$ , $\neg p \lor r$

Conclusion: $q \lor r$

Quantifier Rules of Inference

Theorem 2.4: Quantifier Inference Rules

Universal Instantiation (UI)

Premise: $\forall x P(x)$

Conclusion: $P(c)$ for any c in the domain

Universal Generalization (UG)

Premise: $P(c)$ for an arbitrary c

Conclusion: $\forall x P(x)$

(c must be arbitrary, not a specific element)

Existential Instantiation (EI)

Premise: $\exists x P(x)$

Conclusion: $P(c)$ for some particular c

(c is a specific witness, not used elsewhere)

Existential Generalization (EG)

Premise: $P(c)$ for some specific c

Conclusion: $\exists x P(x)$

Example: Using Rules of Inference

Problem: Given the premises "If it rains, the ground is wet" and "It is raining," what can we conclude?

Let $p$ = "It is raining", $q$ = "The ground is wet"

Premise 1: $p \rightarrow q$

Premise 2: $p$

Conclusion: $q$ (by Modus Ponens)

Therefore, "The ground is wet."

4. Proof Methods

A proof is a valid argument that establishes the truth of a statement. Mathematical proofs use logical reasoning, axioms, definitions, and previously proven theorems.

Definition 2.8: Mathematical Proof Terminology

Theorem: A statement that can be shown to be true
Axiom (Postulate): A statement assumed to be true without proof
Lemma: A helping theorem used to prove other theorems
Corollary: A theorem that follows directly from another theorem
Conjecture: A statement believed to be true but not yet proven

4.1 Direct Proof

Definition 2.9: Direct Proof

A direct proof of $p \rightarrow q$ proceeds as follows:

Assume p is true
Use rules of inference, axioms, and known theorems to show that q must be true

Example: Direct Proof

Theorem: If n is an odd integer, then n² is odd.

Proof of Theorem

Assume: n is odd

By definition of odd integer, $n = 2k + 1$ for some integer k.

Then: $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

Let $m = 2k^2 + 2k$ . Then $n^2 = 2m + 1$ , which is the form of an odd integer.

Conclusion: Therefore, n² is odd.

∎

4.2 Proof by Contraposition

Definition 2.10: Proof by Contraposition

To prove $p \rightarrow q$ by contraposition:

Prove the contrapositive: $\neg q \rightarrow \neg p$
Since $p \rightarrow q \equiv \neg q \rightarrow \neg p$ , this proves the original statement

Example: Proof by Contraposition

Theorem: If n² is even, then n is even.

Proof of Theorem (by contraposition)

Contrapositive: If n is odd, then n² is odd.

Assume n is odd. Then $n = 2k + 1$ for some integer k.

$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

Therefore n² is odd (of the form 2m + 1).

Conclusion: We've proven the contrapositive, so the original statement is true.

∎

4.3 Proof by Contradiction

Definition 2.11: Proof by Contradiction

To prove a statement p by contradiction (reductio ad absurdum):

Assume $\neg p$ (the opposite of what we want to prove)
Show that this assumption leads to a logical contradiction
Conclude that $\neg p$ must be false, so p must be true

Example: Proof by Contradiction

Theorem: $\sqrt{2}$ is irrational.

Proof of Theorem (by contradiction)

Assume the opposite: $\sqrt{2}$ is rational.

Then $\sqrt{2} = \frac{a}{b}$ where a and b are integers with no common factors (in lowest terms), and $b \neq 0$ .

Squaring both sides: $2 = \frac{a^2}{b^2}$ , so $a^2 = 2b^2$

This means a² is even, which implies a is even (by previous theorem). So $a = 2k$ for some integer k.

Substituting: $(2k)^2 = 2b^2$ , which gives $4k^2 = 2b^2$ , so $b^2 = 2k^2$

This means b² is even, which implies b is even.

Contradiction: Both a and b are even, which contradicts our assumption that they have no common factors.

Conclusion: Our assumption must be false, so $\sqrt{2}$ is irrational.

∎

4.4 Other Proof Methods

Definition 2.12: Additional Proof Methods

Vacuous Proof:

To prove $p \rightarrow q$ , show that p is false. Since $F \rightarrow q$ is always true, the implication holds vacuously.

Trivial Proof:

To prove $p \rightarrow q$ , show that q is true. Since $p \rightarrow T$ is always true, the implication holds trivially.

Proof by Cases:

To prove $p$ , partition the cases as $p_1 \lor p_2 \lor \cdots \lor p_n$ and prove p in each case separately.

Existence Proof:

Constructive: Exhibit a specific element with the desired property.

Nonconstructive: Prove existence without explicitly finding the element (often by contradiction).

Uniqueness Proof:

Prove both: (1) Existence - at least one element satisfies the property, and (2) Uniqueness - if x and y both satisfy it, then x = y.

Example: Proof by Cases

Theorem: For any integer n, $n^2 + n$ is even.

Proof of Theorem (by cases)

Every integer is either even or odd. We consider both cases:

Case 1: n is even

Then $n = 2k$ for some integer k.

$n^2 + n = (2k)^2 + 2k = 4k^2 + 2k = 2(2k^2 + k)$

This is even (divisible by 2).

Case 2: n is odd

Then $n = 2k + 1$ for some integer k.

$n^2 + n = (2k+1)^2 + (2k+1) = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1)$

This is even (divisible by 2).

Conclusion: In both cases, $n^2 + n$ is even.

∎

Practice Quiz

Predicate Logic and Proofs Quiz

Questions

Correct

Accuracy

What is the negation of

\forall x P(x)

Medium

Not attempted

What is the negation of

\exists x (P(x) \land Q(x))

Hard

Not attempted

Which rule of inference is represented by: 'p is true, p → q is true, therefore q is true'?

Easy

Not attempted

To prove 'If p then q' by contraposition, we actually prove:

Medium

Not attempted

In a proof by contradiction, to prove p is true, we:

Easy

Not attempted

The statement

\forall x \exists y P(x, y)

means:

Medium

Not attempted

Universal Instantiation (UI) allows us to conclude:

Easy

Not attempted

Which proof method is most appropriate when the hypothesis is simpler than proving the conclusion directly?

Medium

Not attempted

A vacuous proof proves

p \rightarrow q

by showing:

Hard

Not attempted

To prove uniqueness of an element with property P, we must show:

Hard

Not attempted

Frequently Asked Questions

What's the difference between ∀x∃y and ∃y∀x?

∀x∃y P(x,y): "For each x, there exists a y (which may depend on x) such that P(x,y)."

∃y∀x P(x,y): "There exists a single y that works for all x such that P(x,y)."

Example: If P(x,y) means "y is greater than x", the first is true (for any x, we can find a larger y), but the second is false (no single y is greater than all x).

When should I use proof by contraposition vs. contradiction?

Proof by contraposition is best when:

The contrapositive is easier to work with than the original statement
You're proving an implication p → q

Proof by contradiction is best when:

You're proving something is impossible or doesn't exist
The statement is not in implication form
Assuming the opposite leads to an obvious contradiction

How do I know which proof method to use?

Direct proof: Default choice when the statement is straightforward
Contraposition: When the negations are simpler to work with
Contradiction: When proving irrationality, infinitude, or impossibility
Cases: When the domain naturally splits into disjoint categories
Induction: When proving statements about all natural numbers

With practice, you'll develop intuition for which method suits each problem!

What's the difference between UI, UG, EI, and EG?

UI (Universal Instantiation): From ∀x P(x), conclude P(c) for any specific c
UG (Universal Generalization): From P(c) for arbitrary c, conclude ∀x P(x)
EI (Existential Instantiation): From ∃x P(x), conclude P(c) for some witness c
EG (Existential Generalization): From P(c) for specific c, conclude ∃x P(x)

Key difference: UG requires c to be arbitrary (not specific), while EI introduces a new specific witness.

Why can't we switch the order of different quantifiers?

The order matters because it determines dependency. In ∀x∃y P(x,y), y can depend on x (different x values can have different y values). But in ∃y∀x P(x,y), y must be fixed before we consider all x values.

Mathematical example: Let P(x,y) mean "y > x" over real numbers.

∀x∃y (y > x) is TRUE: For any x, we can find a larger y (like x+1)
∃y∀x (y > x) is FALSE: No fixed y is larger than all x