CSCE 222 Chapter 1.3

« previous | Sunday, February 20, 2011 | next »

Predicates

A "function" that takes one or more inputs and evaluates to either true or false

EX: Let $P(x)=x>3$; $P(1)=\text{false}$; $P(5)=\text{true}$

Quantifiers

• Higher precedence than all logical operators
• Distribute across parenthesized terms: $\mathrm{\forall }x(P(x)\wedge Q(x))\equiv \mathrm{\forall }xP(x)\wedge \mathrm{\forall }xQ(x)$

Universal Quantification

If a predicate $P(x)$ is true for all values of $x$ in the domain,

$\mathrm{\forall }xP(x)\equiv P(x_1)\wedge P(x_2)\wedge \dots \wedge P(x_n)$

To be contradicted, we need to find only one value of $x$ such that $P(x)$ is false.

Existential Quantification

If a predicate $P(x)$ is satisfiable for at least one value of $x$ in the domain,

$\mathrm{\exists }xP(x)\equiv P(x_1)\vee P(x_2)\vee \dots \vee P(x_n)$

To be contradicted, every value of $x$ has to be false.

Variable Binding

A variable is bound if a quantifier is used on that variable. For example, in $\mathrm{\exists }x(x+y=1)$, $x$ is bound, but $y$ is free (not bound). To fix this, we would write $\mathrm{\exists }x\mathrm{\exists }y(x+y=1)$.

Negating Quantifiers

"Every student in your class has taken a course in calculus" could be written as $\mathrm{\forall }xP(x)$.

Negation would be "There is a student in your class who has not taken a course in calculus", which could be written $\mathrm{\exists }x\mathrm{\neg }P(x)$

$\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)\end{array}$