MATH 302 Lecture 4

« previous | Wednesday, September 7, 2011 | next »

Predicate Calculus

"1 + 3 = 5" is a proposition (which happens to be false), but "x + 3 = 5" is not a proposition because it depends on the value of x.

Let's create a propositional function ($P(x)$) to represent the predicate ($x+3=5$) that takes a value and returns a Boolean result:

• x is a member of a domain of definition or universe of discourse

Quantifiers

universal

"for all x" (injected and)

$\mathrm{\forall }x(P(x))$ only if $P(x)$ is true for all $x$ in the domain.

existential

"there exists" (injected or)

$\mathrm{\exists }x(P(x))$ only if $P(x)$ is true for some $x$ in the domain.

unique existential

"there exists exactly one" (injected "xor")

$\mathrm{\exists }!x(P(x))$ only if $P(x)$ is true for only one $x$ in the domain.

Quantifiers can be chained to perform "iteration" over domains:

$\mathrm{\exists }x\mathrm{\forall }yQ(x,y)$