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 $\forall xP(x)$

(be aware of what the domain is)

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

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

Equivalence of Predicates

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

Example

${\begin{aligned}\neg \forall x(P(x)\rightarrow Q(x))&\equiv \exists x(P(x)\wedge \neg Q(x))\\&\equiv \exists x\neg (P(x)\rightarrow Q(x))\\&\equiv \exists x\neg (\neg P(x)\vee Q(x))\\&\equiv \exists x(\neg (\neg P(x))\wedge \neg Q(x))\\&\equiv \exists x(P(x)\wedge \neg Q(x))\end{aligned}}$