Universal and Existential Quantifiers

Given a predicate, $P(x)$ may be true for all $x$ from a set, or it may be rue for some choice of $x$ from the set.

Universal Quantifier

The symbol known as $\forall$ (knwon as for all) is used to indicate that a statement applies to all choices of the object.

\[ \forall x \, P(x) \textrm{ - for all } x \textrm{, } P(x) \textrm{ is true.} \]

For example, if we are talking about something like the set of all people, “Everybody likes Arch Linux” could be:
$\forall x , \textrm{likes}(x, \textrm{Arch})$

“All integers divisible by 4 are even”:
$\forall x , (\textrm{divisible}(n,4) \Leftrightarrow \textrm{even}(n))$

Existential Quantifier

The symbol $\exists$ called “there exists”, is used to indicate there exists at least one element in the domain where the proposition is true.

\[ \exists x \, P(x) \textrm{ - there exists an } x \textrm{ such that } P(x) \textrm{ is true.} \]

Proving by Existence & Counter Example

  • $\forall x P(x)$ can be proven true through the use of induction and contradiction to prove that $P(x)$ is true for all $x$ in the domain of discourse.
  • $\forall x P(x)$ can be proven false through the use of counterexample, a single value of $x$ in the domain of discourse where $P(x)$ is false is enough for this.
  • To prove that $\exists x P(x)$ is true, only a single value of $x$ in the domain of discussion where $P(x)$ is true is needed.
  • To prove that $\exists x P(x)$ is false, it has to be proven for the entire domain of discussion via induction and/or contradiction.

Muliple Parameters

Predicaes can involve more than one object, for example for, $y = x^2$ we can write $P(x, y)$.

The following are all versions of the proposition “for all $x$ there exists some $y$ such that $y = x^2$” (all squares of integers are integers)

  • $\forall x \exists y P(x, y)$
  • $\forall x \exists y (y = x^2)$
  • $\forall x \exists y (\textrm{integer}(x) \Rightarrow (\textrm{integer}(y) \wedge (y = x^2)))$

n-ary predicates

  • 1 argument predicaes are called unary predicates/properties, $P(x)$, ie: even(n) or odd(n)
  • 2 argument predicates are called binary predicates/properties, $P(x, y)$, ie likes(x, y) or divisible(n, m)
  • 3 arguments are ternary, etcetc

Well Formed Formulae

Using the symbols from propositional calculus, predicate based logical expressions can be constructed.

  • $\forall x (P(x) \Rightarrow \exists y Q(x, y))$
  • $\exists x (P(x) \wedge Q(x, c))$

Logical Equivalences

WFF manipulation is part of predicate calculus, the study of equality of logical expressions.

The following logical equivalences exist:

Re-naming

\[ \forall x A(x) \Leftrightarrow \forall y A(y)\\ \\ \exists x A(x) \Leftrightarrow \exists y A(y) \]

Negation

\[ ¬ \forall x A(x) \Leftrightarrow \exists x (¬A(x)) ¬ \exists x A(x) \Leftrightarrow \forall x (¬A(x)) \]

Disributive laws

\[ \forall x(A(x) \wedge B(x)) \Leftrightarrow \forall x A(x) \wedge \forall x B(x)\\ \\ \exists x (A(x) \vee B(x)) \Leftrightarrow \exists x A(x) \vee \exists x B(x) \]

Interpretations

A formula in propositional logic has a truth value associated with each possible truth value of each of its propositional values.
The mapping from each of the variables to T or F is called an interpretation and gives a meaning to the formula.

The process of giving an interpretation to a predicate logic formula is more complicated than in propositional logic.

Interpretations in Predicate Logic

Given the formula $\forall x \forall y (P(x,y))$
Where the domain for both x and y is {1, 2, 3, 4}
And where P is the relation divides and we have:

\[ divides = \{\\ (1, 1),\\ (1, 2),\\ (1, 3),\\ (1, 4),\\ (2, 2),\\ (2, 4),\\ (3, 3),\\ (4, 4),\\ \} \]

We can say that the formula is false under this interpretation, because we can find a counter-example: x = 4 and y = 1

Semantic Entailment

An interpretation that makes a formula true is known as a model for that formula.

A formula that has at least one model is said to be consistent or satisfiable.
A formula that has no models is said to be inconsistent or unsatisfiable.

A formula that is true for all interpretations is said to be valid.
A formula which is neither inconsistent nor valid is said to be contingent.

A formula semantically entails another formula iff every model for one of them is a model for the other.
That is to say, if any interpretation makes formula A true, then it also makes B true:

\[ A \models B \]
It can also be said that A logically implies B, or that B is a logical consequence of A.

Inference and Proof

As a formula can be the logical consequence of another ($A \models B$), it can also be said that A logically implies B, or that B is a logical consequence of A.

This can also apply to set formulae: $S \models A$, meaning that any interpretation that makes all the formulae in set $S$ true, also makes $A$ true.

  • $A$ is semantically entailed by the set $S$
  • A is a logical consequence of $S$

Demonstrating Logical Consequences

This can be done using a truth table.
This is left as an exercise to the reader

Note that logical inference can be used instead.

Modus Ponens

If a property $P$ implies a property $Q$, and $P$ is true, we can deduce that $Q$ is true.

\[ \begin{prooftree} \AxiomC{$P, P\Rightarrow Q$} \UnaryInfC{$Q$} \end{prooftree} \]

Example

If we have the following hypothesis:

\[ \{ P \Rightarrow Q, Q \Rightarrow R, P \} \]

Modus ponens can be used to show that:

\[ \{ P \Rightarrow Q, Q \Rightarrow R, P \} ⊢ R \]

As so:

\[ \begin{prooftree} \AxiomC{$P, P\Rightarrow Q$} \UnaryInfC{$Q$} \AxiomC{$Q \Rightarrow R$} \BinaryInfC{$R$} \end{prooftree} \]

Example

Given the rule:

\[ \{ A \wedge B \} ⊢ B \]

Show:

\[ \{ R \Rightarrow ((\forall x P(x)) \wedge Q), R \} ⊢ \forall x P(x) \]

\[ \begin{prooftree} \AxiomC{$R \Rightarrow ((\forall x P(x)) \wedge Q), R$} \UnaryInfC{$(\forall x P(x)) \wedge Q$} \UnaryInfC{$\forall x P(x)$} \end{prooftree} \]

Inference Rules

\[ \begin{prooftree} \AxiomC{$A$} \UnaryInfC{$A \vee B$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$¬(A \wedge B)$} \UnaryInfC{$(¬A) \vee (¬B)$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$A \wedge B$} \UnaryInfC{$A$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$¬(A \vee B)$} \UnaryInfC{$(¬A) \wedge (¬B)$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$A, B$} \UnaryInfC{$A \wedge B$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$¬(A \vee (B \wedge C))$} \UnaryInfC{$A \vee B$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$A, A \Rightarrow B$} \UnaryInfC{$B$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$A \wedge (B \vee C)$} \UnaryInfC{$(A \wedge B) \vee (A \wedge C)$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$¬B, A \Rightarrow B$} \UnaryInfC{$¬A$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$A \Rightarrow B$} \UnaryInfC{$(¬A) \vee B$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$A \Rightarrow B, B \Rightarrow C$} \UnaryInfC{$A \Rightarrow C$} \end{prooftree} \]

\[ \begin{prooftree} \AxiomC{$A \vee B, ¬A$} \UnaryInfC{$B$} \end{prooftree} \]

Proof by contradiction

If you want to show that $S \models A$ then you only need to prove that:

\[ S \cup \{¬A\} \models \bot \]

(Note that $\bot$ represents FALSE)

To prove something by contradiction, simply prove:

\[ \begin{prooftree} \AxiomC{$A, ¬A$} \UnaryInfC{$\bot$} \end{prooftree} \]

Example

Prove via contradiction that:

\[ \{P, P \Rightarrow Q, Q \Rightarrow R \} \models R \wedge Q \]

\[ \begin{prooftree} \AxiomC{$P, P \Rightarrow Q$} \UnaryInfC{$Q$} \AxiomC{$¬(R \wedge Q)$} \UnaryInfC{$¬R \vee ¬Q$} \BinaryInfC{$¬R$} \AxiomC{$P, P \Rightarrow Q$} \UnaryInfC{$Q$} \AxiomC{$Q \Rightarrow R$} \BinaryInfC{$R$} \BinaryInfC{$\bot$} \end{prooftree} \]