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

First law

The negation of "for all x, P(x)" is equivalent to "there exists an x such that not P(x)"

$\sim[(\forall x)P(x)] \equiv (\exists x)[\sim P(x)]$

Second law

The negation of "there exists an x such that P(x)" is equivalent to "for all x, not P(x)"

$\sim[(\exists x)P(x)] \equiv (\forall x)[\sim P(x)]$