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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall x P(x)}

(be aware of what the domain is)

If a predicate holds for any one or more element of a domain, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exist x\ P(x)} Avoid using set notation (∈)

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exist x P(x)} returns false if no value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} satisfies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(x)}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall x P(x)} is false if one value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} satisfies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(x)}

Equivalence of Predicates

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \neg \forall x P(x) & \equiv \exist x \neg P(x) \\ \neg \exist x P(x) & \equiv \forall x \neg P(x) \\ \forall x (P(x) \wedge Q(x)) & \equiv \forall x P(x) \wedge \forall x Q(x) \end{align}}

Example

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \neg \forall x (P(x) \rightarrow Q(x)) & \equiv \exist x (P(x) \wedge \neg Q(x)) \\ & \equiv \exist x \neg(P(x) \rightarrow Q(x)) \\ & \equiv \exist x \neg(\neg P(x) \vee Q(x)) \\ & \equiv \exist x (\neg (\neg P(x)) \wedge \neg Q(x)) \\ & \equiv \exist x (P(x) \wedge \neg Q(x)) \end{align}}