Notes by Lex Toumbourou

An extension of Propositional Logic that uses variables and quantifiers to represent and analyse Statement.

Predicate

Is a Statement that includes a variable.

• $P(x)$: "x is a prime number"

A predicate becomes a proposition when the variable are substituted for values.

• $P(2)$: "2 is a prime number" (True)

Quantifiers

Quantifiers describe how many of a thing there are.

Universal Quantifier

Symbol: $\forall$

Means "For all" or "Every".

Example:

$\forall x, P(x)$: "For every x, x is a prime number"

Existential Quantifier

Symbol: $\exists$

Means "There exists" or "Some".

Example:

$\exists x, P(x)$: "There exists an x such that x is a prime number"

DeMorgan's Laws for negating quantifiers

∼[(∀x)P(x)] ≡ (∃ x)[∼P(x)] ∼[(∀x)P(x)] ≡ (∀x)[∼P(x)]