Lesson 3: Predicate Logic and Quantifiers

Why Predicate Logic?

Propositional logic handles individual statements, but it cannot express relationships involving general quantities like "all" or "some." Predicate logic extends propositional logic to handle these kinds of statements.

For example, from "Every computer on a network is functioning normally" and "Machine X is on the network," we can conclude "Machine X is functioning normally." Propositional logic alone cannot make this deduction — predicate logic can.

Predicates

In everyday grammar, a sentence has a subject and a predicate. In logic, a predicate describes a property that a subject (variable) may or may not have. Predicates are functions that return a truth value.

Example:

• Statement: "Y is greater than 5."
• Subject: Y
• Predicate: "is greater than 5" → K(Y)
• K(Y) is true when Y > 5 and false otherwise.

The domain of a predicate variable is the set of all values the variable can take.

Quantifiers

Quantifiers specify how broadly a predicate applies across a domain.

Universal Quantifier (∀)

Means "for all" or "for every." The expression ∀x ∈ D, P(x) is true only if P(x) holds for every element in the domain D.

Example: "All foxes are sly."

• F(x): x is a fox.
• S(x): x is sly.
• Symbolic form: ∀x[F(x) → S(x)]

Existential Quantifier (∃)

Means "there exists at least one." The expression ∃x ∈ D, P(x) is true if P(x) holds for at least one element in D.

Example: "Some students are attending online classes."

• S(x): x is a student.
• O(x): x attends online classes.
• Symbolic form: ∃x[S(x) ∧ O(x)]

Rules of Inference for Quantifiers

Universal Instantiation says: if something is true for all elements of a domain, it is true for any specific element.

Worked example:

• All fish are orange. (∀x)[F(x) → O(x)]
• Nemo is a fish. F(n)

Proof:

1. (∀x)[F(x) → O(x)] — Hypothesis
2. F(n) — Hypothesis
3. F(n) → O(n) — Universal Instantiation (1)
4. O(n) — Modus Ponens (2, 3)

Proof Techniques

A proof is a logical argument that uses hypotheses, definitions, axioms, and inference rules to demonstrate that a conclusion is true.

Direct Proof

Assume the hypothesis is true, then use logical reasoning to show the conclusion follows.

Example: Prove that if k and g are both odd integers, then k + g is even.

• Let k = 2h + 1 and g = 2b + 1
• k + g = (2h + 1) + (2b + 1) = 2h + 2b + 2 = 2(h + b + 1)
• Since this is twice an integer, k + g is even.

Proof by Contrapositive

To prove P → Q, instead prove ¬Q → ¬P.

Example: Prove that if rl is even, then r is even or l is even.

• Contrapositive: If both r and l are odd, then rl is odd.
• Let r = 2a + 1 and l = 2b + 1
• rl = (2a+1)(2b+1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1 (odd) ✓

Proof by Cases

When the hypothesis can be divided into separate cases, prove each case separately.

Example: Prove that if integer y is not divisible by 3, then y² = 3k + 1 for some integer k.

• Case 1: y = 3m + 1 → y² = (3m+1)² = 3(3m² + 2m) + 1 ✓
• Case 2: y = 3m + 2 → y² = (3m+2)² = 3(3m² + 4m + 1) + 1 ✓

Existence Proof

Proves ∃x P(x). Two types:

1. Constructive: Find a specific value c and show P(c) is true.
2. Nonconstructive (Proof by Contradiction): Show that the negation leads to a contradiction.

Biconditional Proof

To prove P ↔ Q, prove both P → Q and Q → P separately.

Example: Prove that for any integer h, h is odd if and only if h² is odd.

• (→) Direct proof: h = 2a + 1 → h² = 4a² + 4a + 1 = 2(2a² + 2a) + 1, which is odd.
• (←) Contrapositive: If h is even (h = 2a), then h² = 4a², which is even.