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