Discrete Mathematics : Predicate Logic

Contents

• Predicates and quantified statements
• Statements with multiple quantifiers
• Arguments with quantified statements

What is a propositional function or predicate?

A propositional function or predicate is a sentence that contains one or more variables.

A predicate is neither true nor false.

A predicate becomes a proposition when the variables are substituted with specific values.

The domain of a predicate variable is the set of all values that may be substituted for the variable.

Examples:

Symbol	Predicate	Domain	Propositions
$p(x)$	$x > 5$	$x \in \mathbb{R}$	$p(6), p(-3.6), p(0), \ldots$
$p(x, y)$	$x+y$ is odd	$x \in \mathbb{Z}, y \in \mathbb{Z}$	$p(4,5), p(-4,-4), \ldots$
$p(x, y)$	$x^2 + y^2 = 4$	$x \in \mathbb{R}, y \in \mathbb{R}$	$p(-1.7,8.9), p(-\sqrt{3},-1), \ldots$

What is a truth set?

Definition: A truth set of a predicate is the set of all values of the predicate that makes the predicate true

If $p(x)$ is a predicate and $x$ has domain $D$, then the truth set of $p(x)$ is the set of all elements of $D$ that makes $p(x)$ true when the values are substituted for $x$.
Truth set of $p(x) = \{ x \in D ~|~ p(x) \}$

Examples:

Symbol	Predicate	Domain	Truth set
$p(x)$	$x > 5$	$x \in \mathbb{R}$	$\{ p(6), p(13.6), p(5.001), \ldots \}$
$p(x, y)$	$x+y$ is odd	$x \in \mathbb{Z}, y \in \mathbb{Z}$	$\{ p(4,5), p(-4,-3), \ldots \}$
$p(x, y)$	$x^2 + y^2 = 4$	$x \in \mathbb{R}, y \in \mathbb{R}$	$\{ p(-2,2), p(-\sqrt{3},-1), \ldots \}$

Predicates to propositions

There are two methods to obtain propositions from predicates

1. Assign specific values to variables
2. Add quantifiers

What are quantifiers?

Quantifiers are words that refer to quantities such as "all" or "some" and they tell for how many elements a given predicate is true

Two types of quantifiers:

1. Universal quantifier $(\forall)$
2. Existential quantifier $(\exists)$

Universal quantifier $(\forall)$

Forms:

• "$p(x)$ is true for all values of $x$"
• "For all $x$, $p(x)$"
• "For each $x$, $p(x)$"
• "For every $x$, $p(x)$"
• "Given any $x$, $p(x)$"

It is true if $p(x)$ is true for each $x$ in $D$; It is false if $p(x)$ is false for at least one $x$ in $D$

A counterexample to the universal statement is the value of $x$ for which $p(x)$ is false

Universal statements	Domain	Truth value	Method
$\forall x \in D, x^2 \ge x$	$D = \{ 1,2,3 \}$	True	Method of exhaustion
$\forall x \in \mathbb{R}, x^2 \ge x$	$\mathbb{R}$	False	Counterexample $x = 0.1$

Note that method of exhaustion cannot be used to prove universal statements for infinite sets

Existential quantifier $(\exists)$

Forms:

• "There exists an $x$ such that $p(x)$"
• "For some $x$, $p(x)$"
• "We can find an $x$, such that $p(x)$"
• "There is some $x$ such that $p(x)$"
• "There is at least one $x$ such that $p(x)$"

It is true if $p(x)$ is true for at least one $x$ in $D$;
It is false if $p(x)$ is false for all $x$ in $D$

A counterproof to the existential statement is the proof to show that $p(x)$ is true is for no $x$

Universal statements	Domain	Truth value	Method
$\exists x \in D, x^2 \ge x$	$D = \{ 1,2,3 \}$	True	Method of exhaust.
$\exists x \in \mathbb{R}, x^2 \ge x$	$\mathbb{R}$	True	Example
$\exists x \in \mathbb{Z}, x + 1 \le x$	$\mathbb{Z}$	False	How?

Formal and informal languages

Formal language statement = Mathematical statement using mathematical symbols and variables.
Example: $\forall x \in \mathbb{R}, x^2 \ge 0$

Informal language statement = English statement equivalent to a mathematical statement.
Examples:

• Every real number has a nonnegative square
• All real numbers have nonnegative squares
• Any real number has a nonnegative square
• The square of each real number is nonnegative
• No real numbers have negative squares
• $x^2$ is nonnegative for every real $x$
• $x^2$ is not less than zero for each real number $x$

Universal conditional statement $(\forall, \rightarrow)$

A universal conditional statement is of the form
$\forall x, \text{ if } p(x) \text{ then } q(x)$

Examples:

• $\forall x \in \mathbb{R}$, if $x > 2$ then $x^2 > 4$
• $\forall$ real number $x$, if $x$ is an integer then $x$ is rational
  $\equiv \forall$ integer $x$, $x$ is rational
• $\forall x$, if $x$ is a square then $x$ is a rectangle
  $\equiv \forall$ square $x$, $x$ is a rectangle
• $\forall x \in U$, if $p(x)$ then $q(x)$
  $\equiv \forall x \in D$, $q(x)$
  (where, $D = \{ x \in U ~|~ p(x) \text{ is true}\}$)

Similarly, we can define existential conditional statement $(\exists, \rightarrow)$

Implicit quantification $(\Rightarrow, \Leftrightarrow)$

Definition: Let $p(x)$ and $q(x)$ be predicates and $D$ be the common domain of $x$.
Then implicit quantification symbols $\Rightarrow, \Leftrightarrow$ are defined as:
$p(x) \Rightarrow q(x) \equiv \forall x, p(x) \rightarrow q(x)$
$p(x) \Leftrightarrow q(x) \equiv \forall x, p(x) \leftrightarrow q(x)$

Examples:

• If a number is an integer, then it is a rational number
  $\equiv \forall$ number $x$, if $x$ is an integer, $x$ is rational
• The number 10 can be written as a sum of two prime numbers
  $\equiv \exists$ prime numbers $p$ and $q$ such that $10 = p + q$
• If $x > 2$, then $x^2 > 4$
  $\equiv \forall$ real $x$, if $x > 2$, then $x^2 > 4$

Solution:

• Truth set of $q(n) = \{ 1, 2, 4, 8 \} $
  Truth set of $r(n) = \{ 1, 2, 4 \} $
  Truth set of $s(n) = \{ 1, 2, 4 \} $
• $\forall n$ in $\mathbb{Z}^{+}, r(n) \rightarrow q(n)$
  $\equiv r(n) \Rightarrow q(n)$
  $\equiv$ "$n$ is a factor of 4" $\Rightarrow$ "$n$ is a factor of 8"
• $\forall n$ in $\mathbb{Z}^{+}, r(n) \leftrightarrow s(n)$
  $\equiv r(n) \Leftrightarrow s(n)$
  $\equiv$ "$n$ is a factor of 4" $\Leftrightarrow$ "$n < 5$ and $n \ne 3$"
• $\forall n$ in $\mathbb{Z}^{+}, s(n) \rightarrow q(n)$
  $\equiv s(n) \Rightarrow q(n)$
  $\equiv$ "$n < 5$ and $n \ne 3$" $\Rightarrow$ "$n$ is a factor of 8"

Negation of quantified statements $(\sim)$

Examples:

• All mathematicians wear glasses
  Negation (incorrect): No mathematician wears glasses
  Negation (incorrect + ambiguous): All mathematicians do not wear glasses
  Negation (correct): There is at least one mathematician who does not wear glasses
• Some snowflakes are the same
  Negation (incorrect):: Some snowflakes are different
  Negation (correct):: All snowflakes are different
• $\forall$ primes $p$, $p$ is odd
  Negation: $\exists$ primes $p$, $p$ is even
• $\exists$ triangle $T$, sum of angles of $T$ equals $200^{\circ}$
  $\forall$ triangles $T$, sum of angles of $T$ does not equal $200^{\circ}$
• No politicians are honest
  Formal statement: $\forall$ politicians $x$, $x$ is not honest
  Formal negation: $\exists$ politician $x$, $x$ is honest
  Informal negation: Some politicians are honest
• 1357 is not divisible by any integer between 1 and 37
  Formal statement: $\forall n \in [1, 37]$, 1357 is not divisible by $n$
  Formal negation: $\exists n \in [1, 37]$, 1357 is divisible by $n$
  Informal negation: 1357 is divisible by some integer between 1 and 37

Negation of universal conditional statements

Examples:

• $\forall$ real $x$, if $x > 10$, then $x^2 > 100$.
  Negation: $\exists$ real $x$ such that $x > 10$ and $x^2 \le 100$.
• If a computer program has more than 100,000 lines, then it contains a bug.
  Negation: There is at least one computer program that has more than 100,000 lines and does not contain a bug.

Relation between quantifiers $(\forall, \exists)$ and $(\land, \lor)$

Universal statements are generalizations of and statements
Existential statements are generalizations of or statements

If $p(x)$ is a predicate and $D = \{x_1, x_2, \ldots, x_n\}$ is the domain of $x$, then
$\forall x \in D, p(x) \equiv p(x_1) \land p(x_2) \land \cdots \land p(x_n)$
$\exists x \in D, p(x) \equiv p(x_1) \lor p(x_2) \lor \cdots \lor p(x_n)$

Vacuous truth of universal statements

Solution:

• The statement is false if and only if its negation is true
• Negation: There exists a ball in the bowl that is not blue
• The negation is false; So, the statement is true, by default

Universal conditional statements $(\forall x, p(x) \rightarrow q(x))$

Definitions:

• Statement: $\forall x$, if $p(x)$ then $q(x)$
• Contrapositive of the statement is $\forall x$, if $\sim q(x)$ then $\sim p(x)$
• Converse of the statement is $\forall x$, if $q(x)$ then $p(x)$
• Inverse of the statement is $\forall x$, if $\sim p(x)$ then $\sim q(x)$

Identities:

• Conditional $\equiv$ Contrapositive (Useful for proofs)
• Conditional $\not\equiv$ Converse
• Conditional $\not\equiv$ Inverse
• Converse $\equiv$ Inverse

Formulas:

• $\forall x, p(x) \rightarrow q(x) \equiv \forall x, \sim q(x) \rightarrow \sim p(x) $ (Useful for proofs)
• $\forall x, p(x) \rightarrow q(x) \not\equiv \forall x, q(x) \rightarrow p(x) $
• $\forall x, p(x) \rightarrow q(x) \not\equiv \forall x, \sim p(x) \rightarrow \sim q(x) $
• $\forall x, q(x) \rightarrow p(x) \equiv \forall x, \sim p(x) \rightarrow \sim q(x) $

Definitions:

• $\forall x, p(x)$ is a sufficient condition for $q(x)$ means
  $\forall x$, if $p(x)$ then $q(x)$
• $\forall x, p(x)$ is a necessary condition for $q(x)$ means
  $\forall x$, if $\sim p(x)$ then $\sim q(x) \equiv \forall x$, if $q(x)$ then $p(x)$
• $\forall x, p(x)$ only if $q(x)$ means
  $\forall x$, if $\sim q(x)$ then $\sim p(x) \equiv \forall x$, if $p(x)$ then $q(x)$

Examples:

• For real $x$, $x = 1$ is a sufficient condition for $x^2 = 1$
  $\equiv \forall x$, if $x = 1$ then $x^2 = 1$ (True)
• For real $x$, $x^2 = 1$ is a necessary condition for $x = 1$
  $\equiv \forall x$, if $x^2 \ne 1$ then $x \ne 1$ (True)
• For real $x$, $x = 1$ only if $x^2 = 1$
  $\equiv \forall x$, if $x^2 \ne 1$ then $x \ne 1$ (True)

Statements with multiple quantifiers

Solution: Ambiguous interpretations:

1. There is one single person who supervises all the details of the production process.
   $\exists$ person $p$ such that $\forall$ detail $d$, $p$ supervises $d$
2. For any particular production detail, there is a person who supervises that detail, but there might be different supervisors for different details.
   $\forall$ detail $d$, $\exists$ person $p$ such that $p$ supervises $d$

Interpretations

1. Statement form:
   $\forall x \in D, \exists y \in E$ such that $P(x, y)$
   Interpretation: Allow someone else to pick whatever element $x$ in $D$ they wish. Then, you must find an element $y$ in $E$ that "works" for that particular $x$.
2. Statement form:
   $\exists x \in D$ such that $\forall y \in E, P(x, y)$
   Interpretation: Your job is to find one particular $x$ in $D$ that will "work" no matter what $y$ in $E$ anyone might choose to challenge you with.

Example: Tarski world

Write the truth value and provide reasons:

• For all triangles $x$, there is a square $y$ such that $x$ and $y$ have the same color. (True. How?)
• There is a triangle $x$ such that for all circles $y$, $x$ is to the right of $y$. (True. How?)

Example: College cafeteria

Write the informal statements and truth values of the statements and provide reasons.

• $\exists$ an item $I$ such that $\forall$ students $S$, $S$ chose $I$.
  • There is an item that was chosen by every student.
  • True.
• $\exists$ a student $S$ such that $\forall$ items $I$, $S$ chose $I$.
  • There is a student who chose every available item.
  • False.
• $\exists$ a student $S$ such that $\forall$ stations $Z$, $\exists$ an item $I$ in $Z$ such that $S$ chose $I$.
  • There is a student who chose at least one item from every station.
  • True.
• $\forall$ students $S$ and $\forall$ stations $Z$, $\exists$ an item $I$ in $Z$ such that $S$ chose $I$.
  • Every student chose at least one item from every station.
  • False.

Translating from informal to formal language

Solutions:

1. $\forall$ nonzero real numbers $u$, $\exists$ a real number $v$ such that $uv = 1$.
2. $\exists$ a real number $c$ such that $\forall$ real numbers $d$, $cd \ne 1$.
3. $\exists$ a positive integer $m$ such that $\forall$ positive integers $n$, $m \le n$.
4. $\forall$ positive real numbers $x$, $\exists$ a positive real number $y$ such that $y < x$.

Negations of multiply-quantified statements

Example: Tarski world

Problems: Write negations, the truth value of negations and provide reasons.

• For all squares $x$, there is a circle $y$ such that $x$ and $y$ have the same color.
  • $\exists$ a square $x$ such that $\forall$ circles $y$, $x$ and $y$ do not have the same color.
  • True
• There is a triangle $x$ such that for all squares $y$, $x$ is to the right of $y$.
  • $\forall$ triangles $x$, $\exists$ a square $y$ such that $x$ is not to the right of $y$.
  • True

Order of quantifiers

The order of quantifiers are important when multiple quantifiers are involved

Example 1

• $\forall$ people $x$, $\exists$ a person $y$ such that $x$ loves $y$.
  Quite possible.
• $\exists$ a person $y$ such that $\forall$ people $x$, $x$ loves $y$.
  Quite impossible.

Example 2

In Tarski world:

• For every square $x$ there is a triangle $y$ such that $x$ and $y$ have different colors (True)
• There exists a triangle $y$ such that for every square $x$, $x$ and $y$ have different colors. (False)

Example 3

• Suppose $\mathbb{R}^*$ is a set of nonzero real numbers.

• $\forall x \in \mathbb{Z}, \exists y \in \mathbb{R}^* (xy < 1)$ (True)
  Two cases:
  1. For $x \le 0$, let $y = 1$, then $xy < 1$
  2. For $x > 0$, let $y = 1/(x + 1)$, then $xy < 1$
• $\exists y \in \mathbb{R}^*, \forall x \in \mathbb{Z}~ (xy < 1)$ (False)
  Two cases:
  1. For $y > 0$, if integer $x \ge 1/y$, then $xy \nless 1$
  2. For $y < 0$, if integer $x \le 1/y$, then $xy \nless 1$
  In both the cases, an adversary can choose an integer that makes the predicate false. Hence, the quantified statement is false.

Formal logical notation

Predicates

• Triangle$(x)$: $x$ is a triangle
• Circle$(x)$: $x$ is a circle
• Square$(x)$: $x$ is a square
• Blue$(x)$: $x$ is blue
• Gray$(x)$: $x$ is gray
• Black$(x)$: $x$ is black
• RightOf$(x, y)$: $x$ is to the right of $y$
• Above$(x, y)$: $x$ is above $y$
• SameColor$(x, y)$: $x$ has the same color as $y$

Examples

Write the formal statement and derive the formal negation.

• For all circles $x$, $x$ is above $f$.
  • Formal statement
    $\forall x( \text{Circle}(x) \rightarrow \text{Above}(x, f) )$
  • Formal negation
    $\sim (\forall x( \text{Circle}(x) \rightarrow \text{Above}(x, f) ) )$
    $\equiv \exists x \sim ( \text{Circle}(x) \rightarrow \text{Above}(x, f) )$
    $\equiv \exists x ( \text{Circle}(x) \land \sim \text{Above}(x, f) )$
• There is a square $x$ such that $x$ is black.
  • Formal statement
    $\exists x( \text{Square}(x) \land \text{Black}(x) )$
  • Formal negation
    $\sim ( \exists x( \text{Square}(x) \land \text{Black}(x) ) )$
    $\equiv \forall x \sim ( \text{Square}(x) \land \text{Black}(x) )$
    $\equiv \forall x ( \sim \text{Square}(x) \lor \sim \text{Black}(x) )$
• For all circles $x$, there is a square $y$ such that $x$ and $y$ have the same color.
  • Formal statement
    $\forall x( \text{Circle}(x) \rightarrow \exists y (\text{Square}(y) \land \text{SameColor}(x, y) ) )$
  • Formal negation
    $\sim ( \forall x( \text{Circle}(x) \rightarrow \exists y (\text{Square}(y) \land \text{SameColor}(x, y) ) ) )$
    $\equiv \exists x \sim ( \text{Circle}(x) \rightarrow \exists y (\text{Square}(y) \land \text{SameColor}(x, y) ) )$
    $\equiv \exists x ( \text{Circle}(x) \land \sim ( \exists y (\text{Square}(y) \land \text{SameColor}(x, y) ) ) )$
    $\equiv \exists x ( \text{Circle}(x) \land \forall y ( \sim ( \text{Square}(y) \land \text{SameColor}(x, y) ) ) )$
    $\equiv \exists x ( \text{Circle}(x) \land \forall y ( \sim \text{Square}(y) \lor \sim \text{SameColor}(x, y) ) )$
• There is a square $x$ such that for all triangles $y$, $x$ is to right of $y$.
  • Formal statement
    $\exists x( \text{Square}(x) \land \forall y (\text{Triangle}(y) \rightarrow \text{RightOf}(x, y) ) )$
  • Formal negation
    $\sim ( \exists x( \text{Square}(x) \land \forall y (\text{Triangle}(y) \rightarrow \text{RightOf}(x, y) ) ) )$
    $\equiv \forall x \sim ( \text{Square}(x) \land \forall y (\text{Triangle}(y) \rightarrow \text{RightOf}(x, y) ) )$
    $\equiv \forall x ( \sim \text{Square}(x) \lor \sim ( \forall y (\text{Triangle}(y) \rightarrow \text{RightOf}(x, y) ) ) )$
    $\equiv \forall x ( \sim \text{Square}(x) \lor \exists y ( \sim ( \text{Triangle}(y) \rightarrow \text{RightOf}(x, y) ) ) )$
    $\equiv \forall x ( \sim \text{Square}(x) \lor \exists y ( \text{Triangle}(y) \land \sim \text{RightOf}(x, y) ) )$

Arguments with Quantified Statements

Universal instantiation

If some property is true of everything in a set, then it is true of any particular thing in the set.

Example:

• All men are mortal.
  Socrates is a man.
  $\therefore$ Socrates is mortal.

Rule of inference: Universal modus ponens

Example:

• Informal argument
  If an integer is even, then its square is even.
  $k$ is a particular integer that is even.
  $\therefore$ $k^2$ is even
• Formal argument
  $\forall x$, if $E(x)$ then $S(x)$
  $E(k)$ for a particular $k$
  $\therefore$ $S(k)$

Rule of inference: Universal modus tollens

Example:

• Informal argument
  All human beings are mortal.
  Zeus is not mortal.
  $\therefore$ Zeus is not human.
• Formal argument
  $\forall x$, if $H(x)$ then $M(x)$$\triangleright H(x)$? $M(x)$? $Z$? $\sim M(Z)$
  $\therefore$ $\sim H(Z)$

Fallacy: Converse and inverse errors

Examples of converse error

• Law
  All the town criminals frequent the Hot Life bar.
  John frequents the Hot Life bar.
  $\therefore$ John is one of the town criminals.
  Suspect John but don't convict him.
• Medicine
  For all $x$, if $x$ has pneumonia, then $x$ has a fever and chills, coughs deeply, and feels exceptionally tired and miserable.
  John has a fever and chills, coughs deeply, and feels exceptionally tired and miserable.
  $\therefore$ John has pneumonia.
  Diagnosis of pneumonia is a strong possibility, though not a certainty.

Using diagrams to test validity

Example 1

All human beings are mortal.
Zeus is not mortal.
$\therefore$ Zeus is not human.$\triangleright$ Valid (Modus tollens)

Example 2

All human beings are mortal.
Felix is mortal.
$\therefore$ Felix is a human being.$\triangleright$ Invalid (Converse error)

Example 3

No polynomial functions have horizontal asymptotes.
This function has a horizontal asymptote.
$\therefore$ This function is not a polynomial function.$\triangleright$ Valid

Form:
$P(x):$ $x$ is a polynomial function
$Q(x):$ $x$ does not have a horizontal asymptote
$\forall x$, if $P(x)$ then $Q(x)$
$\sim Q(a)$ for a particular $a$
$\therefore$ $\sim P(a)$$\triangleright$ Modus tollens