Predicate Logic

Predicates

A predicate is a statement containing variables that becomes a proposition when values are substituted.

Notation

• $P(x)$: predicate with one variable
• $Q(x, y)$: predicate with two variables

Example

Let $P(x)$: "$x > 3$"

• $P(4)$ is true
• $P(2)$ is false

Quantifiers

Universal Quantifier ($\forall$)

$\forall x \, P(x)$

Means: "For all $x$, $P(x)$ is true"

True when: $P(x)$ is true for every element in the domain.

Existential Quantifier ($\exists$)

$\exists x \, P(x)$

Means: "There exists an $x$ such that $P(x)$ is true"

True when: $P(x)$ is true for at least one element in the domain.

Uniqueness Quantifier ($\exists!$)

$\exists! x \, P(x)$

Means: "There exists exactly one $x$ such that $P(x)$ is true"

$\exists! x \, P(x) \equiv \exists x (P(x) \land \forall y (P(y) \rightarrow y = x))$

Domain of Discourse

The domain (or universe of discourse) specifies what values variables can take.

Example

If domain is $\mathbb{Z}^+$ (positive integers):

• $\forall x (x > 0)$ is true
• $\exists x (x < 0)$ is false

Negating Quantifiers

De Morgan's Laws for Quantifiers

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

Example

$\neg$"All students passed" $\equiv$ "Some student did not pass"

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

Nested Quantifiers

Order Matters!

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

Examples

Let $L(x, y)$: "$x$ loves $y$"

Statement	Meaning
$\forall x \, \forall y \, L(x,y)$	Everyone loves everyone
$\exists x \, \exists y \, L(x,y)$	Someone loves someone
$\forall x \, \exists y \, L(x,y)$	Everyone loves someone
$\exists y \, \forall x \, L(x,y)$	Someone is loved by everyone
$\exists x \, \forall y \, L(x,y)$	Someone loves everyone

Negating Nested Quantifiers

Move negation inward, flipping each quantifier:

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

Example

$\neg$"Every student has taken some course" = "Some student has taken no courses"

$\neg \forall s \, \exists c \, \text{Taken}(s,c) \equiv \exists s \, \forall c \, \neg \text{Taken}(s,c)$

Translating English to Logic

Common Patterns

English	Logical Form
All $A$ are $B$	$\forall x (A(x) \rightarrow B(x))$
Some $A$ are $B$	$\exists x (A(x) \land B(x))$
No $A$ are $B$	$\forall x (A(x) \rightarrow \neg B(x))$
Some $A$ are not $B$	$\exists x (A(x) \land \neg B(x))$

Example

"Every prime greater than 2 is odd"

Let $P(x)$: "$x$ is prime", $G(x)$: "$x > 2$", $O(x)$: "$x$ is odd"

$\forall x ((P(x) \land G(x)) \rightarrow O(x))$

Bound and Free Variables

• Bound variable: Quantified variable
• Free variable: Not quantified

In $\forall x (P(x) \land Q(x, y))$:

• $x$ is bound
• $y$ is free

Rules of Inference for Quantifiers

Universal Instantiation

$\frac{\forall x \, P(x)}{P(c)} \text{ for any } c \text{ in domain}$

Universal Generalization

$\frac{P(c) \text{ for arbitrary } c}{\forall x \, P(x)}$

Existential Instantiation

$\frac{\exists x \, P(x)}{P(c) \text{ for some element } c}$

Existential Generalization

$\frac{P(c) \text{ for some element } c}{\exists x \, P(x)}$