CSCE 222 Lecture 5

« previous | Friday, January 28, 2011 | next »

Predicate Logic

A Predicate is a function that filters from a domain by returning true or false:

EX: domain is all integers; predicate could be P(x) → x > 3

P(4) is true, but P(2) is false

"Predicate holds for all elements of a domain" written as $\mathrm{\forall }xP(x)$

(be aware of what the domain is)

If a predicate holds for any one or more element of a domain, then $\mathrm{\exists }xP(x)$ Avoid using set notation (∈)

• $\mathrm{\exists }xP(x)$ returns false if no value of $x$ in $D$ satisfies $P(x)$
• $\mathrm{\forall }xP(x)$ is false if one value of $x$ in $D$ satisfies $P(x)$

Equivalence of Predicates

$\begin{array}{rl}\mathrm{\neg }\mathrm{\forall }xP(x)& \equiv \mathrm{\exists }x\mathrm{\neg }P(x)\\ \mathrm{\neg }\mathrm{\exists }xP(x)& \equiv \mathrm{\forall }x\mathrm{\neg }P(x)\\ \mathrm{\forall }x(P(x)\wedge Q(x))& \equiv \mathrm{\forall }xP(x)\wedge \mathrm{\forall }xQ(x)\end{array}$

Example

$\begin{array}{rl}\mathrm{\neg }\mathrm{\forall }x(P(x)\to Q(x))& \equiv \mathrm{\exists }x(P(x)\wedge \mathrm{\neg }Q(x))\\ & \equiv \mathrm{\exists }x\mathrm{\neg }(P(x)\to Q(x))\\ & \equiv \mathrm{\exists }x\mathrm{\neg }(\mathrm{\neg }P(x)\vee Q(x))\\ & \equiv \mathrm{\exists }x(\mathrm{\neg }(\mathrm{\neg }P(x))\wedge \mathrm{\neg }Q(x))\\ & \equiv \mathrm{\exists }x(P(x)\wedge \mathrm{\neg }Q(x))\end{array}$