Predicate Logic

Introduction

Terminology

Predicate logic generalizes propositional logic with the following new things:

• Definition. A domain is a non-empty set of objects.
• Definition. A constant is a concrete object in the domain.
• Definition. A variable is a place holder for a concrete object; it lets us refer to an object without specifying which particular object it is.
• Definition. A function symbol is denoted by $f^{(n)}$, where $f$ is the function name and $n$ denotes its arity.

Term

Definition. A term is defined inductively as:

• Atom: each constant symbol and variable term is a term.
• Function application: if $t_1, \ldots, t_n$ are terms and $f$ is a function symbol of arity $n$, then $f(t_1, \ldots, t_n)$ is a term.
• Nothing else is a term.

Predicate

Definition. A predicate represents a property of an object or a relation among multiple objects.

Remark. We can think of a predicate as a function mapping from $\mathcal{D}^n$ into $\{T, F\}$.

Quantifier

• Universal quantifier $\forall$
• Existential quantifier $\exists$

WFF (of First-Order Logic)

WFF

Definition. The set of well-formed formulas of first-order logic is inductively defined as follows:

• Atom: A predicate (atomic formula) is a formula.
• Unary Connectives:If $\alpha$ is a formula, $(\lnot \alpha)$ is a formula.
• Binary Connectives: If $\alpha, \beta$ are formulas and $\ast$ is a binary connective, $(\alpha \ast \beta)$ is a formula.
• Quantifiers: If $\alpha$ is a formula and $x$ is a variable, then each of $(\forall x \; \alpha)$ and $(\exists s \; \alpha)$ is a formula.
• Nothing else is a formula.

Notation: Seven Kinds of Symbols

• Constant symbols: $a,b,c$
• Variables: $x,y,z$
• Function symbols: $f,g,h$
• Predicate symbols: $P, Q, R$
• Connectives: $\land, \lor, \lnot$
• Quantifiers: $\forall, \exists$
• Punctuations: parentheses and comma

Remarks. Function symbols and predicate symbols have assigned arities.

Application: Parse Tree

• Quantifiers $\forall x$ and $\exists y$ have one subtree, behaves like the unary connective $\lnot$.
• A predicate symbol $P(t_1, t_2, \ldots, t_n)$ has a parent node labeled $P$ with a subtree for each of the term $t_1, t_2, \ldots, t_n$.
• A function symbol $f(t_1, t_2, \ldots, t_n)$ has a parent node labeled $f$ with a subtree for each of the term $t_1, t_2, \ldots, t_n$.

Free and Bound Variables

Definition. There are two types of variables in a formula:

• A variable may be free. To evaluate the formula, we need to replace a free variable by an object in the domain.
• A variable may be bound by a quantifier. The quantifier tells us how to evaluate the formula.

Definition.

• In a formula $(\forall x \; \alpha)$ or $(\exists x \; \alpha)$, the scope of a quantifer is the formula $\alpha$; the quantifier binds its variable within its scope.

• An occurrence of a variable in a formula is bound if it lies in the scope of some quantifier of the same variable. Otherwise the occurrence of this variable is free.

  • If a variable occurs multiple times, we need to consider each occurrence of the variable separately.
  • The variable symbol immediately after $\exists$ or $\forall$ is neither free nor bound.

• A formula with no free variables is called a closed formula or sentence.

Application: Determining Free or Bound using Parse Tree

To determine whether a variable is free or bound, we can use a parse tree:

• Draw the parse tree for the formula
• Choose the leaf node for an occurrence of a variable
• Walk up the tree. Stop as soon as we encounter a quantifier for this variable or we reach the root of the tree.
• If we reach the root of the tree which is not a quantifier for the variable, this occurrence of the variable is free.

Substitution

Motivation

Definition. For a variable $x$, a term $t$, and a formula $\alpha$, $\alpha[t/x]$ denotes the resulting formula by replacing each free occurrence of variable $x$ in formula $\alpha$ with term $t$.

Remark. Subsitution does NOT affect bound occurrences of a variable.

Example.

• Let $\alpha = E(f(x))$, then

  • $\alpha[(y+y)/x] = E(f((y+y))$
  • $\alpha[f(x)/x] = E(f(f(x)))$
  • $E(f((x+y)))[y/x] = E(f((y+y)))$.

• If $\beta = (\forall x (E(f(x)) \land S(x,y)))$, then $\beta[g(x,y)/x] = \beta$, because $\beta$ has no free occurrence of $x$ so the substitution does nothing.

Formal Definition

Definition. Let $x$ be a variable and $t$ a term.

For a term $u$, the term $u[t/x]$ is $u$ with each occurrence of $x$ replaced by $t$.

For a formula $\alpha$,

1. If $\alpha$ is a predicate, recursively substitute each $x$ with $t$.

2. If $\alpha$ can be splitted into other formulas, recursively apply rule 1.

3. If $x$ is bounded in $\alpha$, then substituting $t$ into $x$ does nothing.

4. If $t$ contains no bounded variable, leave the quantifier alone and do substituion.

5. If $t$ contains a bounded variable, we need to find a new variable with no name clash and do the substitution.

Exercise.

$\alpha = (\forall x \;(\exists y \;((x + y) = z)))$, then $\alpha[(y-1)/z]$ is?

• Note that the term $t = y-1$ contains a bounded variable. To resolve the name clash, we first replace every occurrence of $y$ in $\alpha$ by $w$, i.e. $\alpha[w/y] = (\forall x \; (\exists w \; ((x + w) = z)))$, and then substitute $z$ by $y-1$, so that $\alpha[w/y][(y-1)/z] = (\forall x \; (\exists w \; ((x + w) = (y - 1))))$.

• To write this formally, we need the following steps:

  1. Let $\beta = ((x + y) = z)$, so that $\alpha = (\forall x \; (\exists y \; \beta))$.
  2. Let $\gamma = (\exists y \;\beta)$ and $t = (y-1)$. Since $y$ occurs in $t$, select a new variable, say $w$.
  3. Then $(\exists y\;\beta[w/y]) = (\exists w\;((x+w) = z)) \implies (\exists y\;\beta[w/y][(y-1)/z]) = (\exists w\;((x+w) = (y-1)))$.
  4. Thus $\alpha [(y-1)/z] = (\forall x \; (\exists w \; ((x+w) = (y-1))))$.

Interpretations

Definition. Fix a set $\mathcal{L}$ of constant symbols, function symbols, variable symbols and predicate symbols. An interpretation $\mathcal{I}$ for the set $\mathcal{L}$ consists of

• A non-empty set $\mathcal{D}^\mathcal{I}$ or simply $\mathcal{D}$, called the domain of $\mathcal{I}$.
• For each constant symbol $c \in \mathcal{L}$, a member $c^\mathcal{I} \in \mathcal{D}^\mathcal{I}$.
• For each function symbol $f^{(i)} \in \mathcal{L}$, an $i$-ary function $f^\mathcal{I}$.
• For each predicate symbol $P^{(i)} \in \mathcal{L}$, an $i$-ary predicate $P^{\mc I}$.

Values of Variable-Free Terms

Definition. Fix an interpretation $\mc{I}$. For each term $t$ containing no variables (only constants), the value of $t$ under interpretation $\mc{I}$, denoted $t^\mc{I}$, is as follows:

• If $t$ is a constant $c$, the value $t^\mc{I}$ is $c^{\mc I}$.
• If $t$ is $f(t_1, \ldots, t_n)$, the value $t^\mc{I}$ is $f^\mc{I}(t_1^\mc{I}, \ldots, t_n^\mc{I})$.

Remark. The value of a term is always a member of the domain of $\mc{I}$.

Total Functions

Motivation. Recall that your function's interpretation must be defined on the entire domain. That is, for a function $f$ with arity $k$, we need to define an interpretation such that the function $f^\mc{I}$ satisfies

Definition. Functions capable of doing this (that is, the result is in domain) are called total functions.

Example. Let $\mc{D} = \mathbb{N}$. The addition function is a total function since the sum of any two natural numbers gives another natural number. However, the subtraction function is not, as $2-6 = -4 \not \in \mathbb{N} = \mathcal{D}$.

Values of Formulas Containing Only Variable-Free Terms

Definition. Fix an interpretation $\mc I$. For each formula $\alpha$ containing no variables, the value of $\alpha$ under interpretation $\mc I$, denoted $\alpha^\mc I$, is as follows:

• If $\alpha$ is $P(t_1, \ldots, t_n)$, then

  $$\alpha^\mc I = \begin{cases} T &\text{if }\left<t_1^\mc I, \ldots, t_n^\mc I\right> \in P^\mc I\\ F &\text{otherwise} \end{cases}$$

• If $\alpha$ is $(\lnot \beta)$ or $(\beta \ast \gamma)$, then $\alpha^\mc I$ is determined by $\beta^\mc I$ and $\gamma^\mc I$ in the same way as for propositional logic.

Remark. $\left<t_1^\mc I, \ldots, t_n^\mc I\right> \in P^\mc I$ simply means $P(t_1, \ldots, t_n)$ evaluates to True under the interpretation $\mc I$.

Environments

Definition. An environment is a function that assigns a value in the domain to every variable symbol in the language.

• Warning. An environment needs to be defined on all variables.
• Although environments will only be used to interpret free variables, they still need to be defined on all variables including bound variables.
• Bound variables will get their meaning primarily through the corresponding quantifier.

Meaning of Terms

Principle. The combination of an interpretation and an environment supplies a meaning (value) for every term.

Definition. Fix an interpretation $\mc I$ and an environment $E$. For each term $t$, the value of $t$ under $\mc I$ and $E$, dentoed $t^{(\mc I, E)}$, is as follows:

• Interpretations give constants meanings: if $t$ is a constant $c$, then $t^{(\mc I, E)} = c^\mc I$.
• Environments give variables meanings: if $t$ is a variable $x$, then $t^{(\mc I, E)} = x^E$.
• Recursively extend to functions: if $t$ is a function application $f(t_1, \ldots, t_n)$, then $t^{(\mc I, E)} = f^\mc I\Big(t_1^{(\mc I, E)}, \ldots, t_n^{(\mc I, E)}\Big)$.

Example. Let $\alpha_1$ be $P(c)$ where $c$ is a constant and let $\alpha_2$ be $P(x)$ where $x$ is a variable. Let $\mc I$ be the interpretation with domain $\mathbb N$, $c^\mc I = 2$ and $P^\mc I = \text{"is even"}$. Then $\alpha_1^\mc I = T$ but $\alpha_2^\mc I$ is undefined. To give $\alpha_2$ a value, we must also specify an environment $E$. For example, if $E(x) = 2$ (inside this environment $x$ has value $2$), then $\alpha_2^{(\mc I, E)} = T$.

Quantified Formulas

Definition. For any environment $E$ and domain element $d$, the environment "$E$ with $x$ maps to $d$", denoted $E[x\mapsto d]$, is given by

In other words, $E[x \mapsto d](x) = d$ and for any other variable $y$, $E[x \to d](y) = E(y)$.

Remark. $E[x\mapsto d]$ is a new environment!

Example. Let $\mc D = \{1, 2, 3\}$ for some $\mc I$ and $E$ such that $E(x) = 3 \quad E(y) = 3 \quad E(z) = 1$. Then $E[x\mapsto 2](x)=2 \quad E[x\mapsto 2](y) = 3\quad E[x\mapsto2](z) = 1$.

Values of Quantified Formulas

Definition. The values of $(\forall x \; \alpha)$ and $(\exists x \; \alpha)$ are given by

• $(\forall x\;\alpha)^{(\mc I, E)} = \begin {cases} T &\text{if $\alpha^{(\mc I, E[x\mapsto d])} = T$ for every $d \in \mc D^\mc I$}\\ F &\text{otherwise}\end{cases}$
• $(\exists x\;\alpha)^{(\mc I, E)} = \begin {cases} T &\text{if $\alpha^{(\mc I, E[x\mapsto d])} = T$ for some $d \in \mc D^\mc I$}\\ F &\text{otherwise}\end{cases}$

Remark. The values of $(\forall x\;\alpha)^{(\mc I, E)}$ and $(\exists x\;\alpha)^{(\mc I, E)}$ do not depend on the values of $E(x)$; $E(x)$ only matters for free occurrences of $x$ but nontheless environments must be specified for all variables.

Validity and Satisfiability

Definition. A formula $\alpha$ is

• valid if every interpretation and environment satisfy $\alpha$, that is, $\mc I \models_{E} \alpha$ for every $\mc I$ and $E$.
• satisfiable if some interpretation and environment satisfy $\alpha$, that is, $\mc I \models_{E}$ for some $\mc I$ and $E$.
• unsatisfiable if no interpretation and environment satisfy $\alpha$, that is, $\mc I \not \models_{E} \alpha$for every $\mc I$ and $E$.

Remark. The term "tautology" is not used in predicate logic.

Remark. If there is no need to specify an environment, then simply defining an interpretation $\mc I$ and writing $\mc I \models \alpha$ will suffice.

Remark. To show a formula is valid or unsatisfiable, start with "let $I$ be an arbitrary interpretation and $E$ be an arbitrary environment", then show that $\alpha^{(I, E)} = T$ (for valid) and $\alpha^{(I, E)} = F$ (for unsatisfiable); to show a formula is satisfiable, give examples of $\alpha$ being true under some $(I_1, E_1)$ and false under some $(I_2, E_2)$.

Exercise: Give an Interpretation $I$ and an environment $E$ such that ...

Template:

1. Define the domain.
2. Map each constant to a domain element.
3. Give each function a meaning.
4. Give each predicate a meaning.
5. Map each variable to a domain element.

Now use reduction to show the statement holds.

Example I. (with variables but no quantifier): Consider this language of predicate logic:

• Constant symbols: $a, b, c$
• Variable symbols: $x, y, z$
• Function symbols: $f^{(1)}, g^{(2)}$
• Predicate symbols: $P^{(1)}, Q^{(2)}$

Give an interpretation $I$ and environment $E$ such that $Q(f(x), a)^{(I, E)} = T$.

Solution I:

• The interpretation $I$ and the environment $E$ are given below:

  • $dom(I) = \{1, 2, 3\}$
  • $a^I =2, b^I=1, c^I=1$
  • $(\forall x \in dom (I): f^{I}(x) = x); (\forall x \in dom(I):g^I(x) = 1)$
  • $Q^I = \{\left<1, 2\right>\}, P^I = \varnothing$
  • $E(x) = 1, E(y) = 1, E(z) = 1$

• Given $I$ and $E$, we can show that $Q(f(x), a)^{(I, E)} = T$ because

Example II: Use the same language as above, give an interpretation $I$ and environment $E$ such that $(\exists x \;Q(x, y))^{(I, E)} = T$.

Remark II: $y$ is free so its value is given by the environment; even though $x$ and $z$ do not appear in the formula, we need to define their mapping as part of $E$. To make the statement true, there must be at least one tuple in the set of $Q^I$ with second element being $E(y)$.

Solution II:

• The interpretation $I$ and the environment $E$ are given below:

  • $dom(I) = \{1, 2, 3\}$
  • $a^I =2, b^I=1, c^I=1$
  • $(\forall x \in dom (I): f^{I}(x) = x); (\forall x \in dom(I):g^I(x) = 1)$
  • $Q^I = \{\left<1, 2\right>\}, P^I = \varnothing$
  • $E(x) = 1, E(y) = 2, E(z) = 1$

• Given $I$ and $E$, we can show that $Q(x,y)^{(I, E[x\mapsto 1])} = T$ because

• Hence, by the satisfaction rules for $\exists$, $(\exists x \;Q(x, y))^{(I, E)} = T$.

Overall Remarks

1. The constants get their meaning through $I$ and the variables through $E$.

2. Map every constant to a domain element in $I$ and every variable to a domain element in $E$, even if some of them do not appear in the formula.

3. The function and predicate must be able to every possible domain elements (or combinations of domain element, in the case its arity is greater than one).

4. To show $P(\alpha)^{(I,E)} = T$, show that $\alpha^{(I,E)} \in P^I$; LHS gets its value from $I$ only if there is no free variable.

5. Use the satisfaction rules precisely

   • $(\forall x\;\alpha)^{(\mc I, E)} = \begin {cases} T &\text{if $\alpha^{(\mc I, E[x\mapsto d])} = T$ for every $d \in \mc D^\mc I$}\\ F &\text{otherwise}\end{cases}$
   • $(\exists x\;\alpha)^{(\mc I, E)} = \begin {cases} T &\text{if $\alpha^{(\mc I, E[x\mapsto d])} = T$ for some $d \in \mc D^\mc I$}\\ F &\text{otherwise}\end{cases}$

Semantic Entailment

Relevance Lemma

Lemma. Let $\alpha$ be a well-formed predicate formula, $\mc I$ be an interpretation, and $E_1, E_2$ be two environments such that $E_1(x) = E_2(x)$ for every $x$ that occurs free in $\alpha$. Then $\mc I \models_{E_1} \alpha$ if and only if $\mc I \models_{E_2} \alpha$.

Semantic Entailment

Let $\Sigma$ be a set of well-formed predicate logic formulas and $\alpha$ is a well-formed predicate logic formula. For an interpretation $\mc I$ and an environment $E$, we write $\mc I \models_E \Sigma$ if and only if for every $\varphi \in \Sigma$, we have that $\mc I \models_E \varphi$.

Definition. We say that $\Sigma$ semantically entails $\alpha$, written as $\Sigma \models \alpha$, if and only if for any interpretation $\mc I$ and environment $E$, we have $\mc I \models_E \Sigma$ implies $\mc I \models_E \alpha$. This can also be written as $\alpha^{(\mc I, E)} = T$.

Remark. $\varnothing \models \alpha$ means that $\alpha$ is valid (recall how we interpret this in propositional logic).

Notes. Suppose $\Sigma = \{\alpha_1, \ldots, \alpha_n\}$. Then $\Sigma \models \beta$ means

• ... that every pair of interpretation and environment that makes $\Sigma$ true must also make $\beta$ true.
• ... that $\varnothing \models ((\alpha_1 \land (\alpha_2 \land (... \land \alpha_n ))) \to \beta)$.
• ... that $((\alpha_1 \land (\alpha_2 \land (... \land \alpha_n))) \to \beta)$ is valid.

Thus, to prove these, take an arbitrary interpretation and environment and show that if this satisified $\Sigma$ then it must also satisfy $\beta$. You may also assume towards a contradiction that $\mc I \not \models_E \beta$ and proceed from there. To prove $\Sigma\not\models\beta$ find an interpretation $\Sigma$ and environment $E$ that satisfies $\Sigma$ but doesn't satisfy $\beta$, that is, show that $\mc \not \models_E \beta$.

Exercise: Semantic Entailment

Example I. Show that $\{(\forall x \; (\alpha \to \beta))\} \models ((\forall x \; \alpha) \to (\forall x \; \beta))$, where $x$ is a variable symbol and $\alpha$ and $\beta$ are well-formed predicate formulas.

Remark I. The solution to this kind of problems will be a stack of logic properties and satisfaction rules.

Solution I. Consider an interpretation $I$ and environment $E$ such that $(\forall x \; (\alpha \to \beta))^{(I,E)} = T$. We will prove that $((\forall x \; \alpha) \to (\forall x \; \beta))^{(I,E)} = T$. First, if $(\forall x\; \alpha)^{(I,E)} = F$, the implication is vacuously true, thus we assume the hypothesis is true.

• By the satisfaction rule for $\forall$, we have $\alpha^{(I,E[x\mapsto d])} = T$ for every $d \in dom(I)$.
• From premise (and by the satisfaction rule for $\forall$), we have $(\alpha \to \beta)^{(I,E[x\mapsto d])} = T$ for every $d \in dom(I)$.
• By the satisfaction rule for an implication, we have that $\beta^{(I,E[x\mapsto d])} = T$.
• By the satisfaction rule for $\forall$, we have that $(\forall x\; \beta)^{(I,E)} = T$.

Thus, the entailment holds. $\square$

Example II. Show that $\{((\forall x \; \alpha) \to (\forall x \; \beta))\} \not\models (\forall x \; (\alpha\to\beta))$.

Remark II. We need to come up with a concrete example. The first step is to choose concrete formulas for $\alpha$ and $\beta$, because without doing so, we cannot make claims about whether $\alpha$ and $\beta$ are true under a particular interpretation. Next, we need to cnostruction an interpretation to satisfy the premise but not the conclusion.

Solution II. Let $\alpha$ be $P(x)$ and $\beta$ be $Q(x)$ where $P,Q$ are unary predicates. Consider the following interpretation:

• $dom(I) = \{1, 2\}$.
• $P^I=\{2\}, Q^I =\{1\}$.

Let $E$ be an arbitrary environment (no free variable, but still need to mention it). First, we will show that $((\forall x \; P(x)) \to (\forall x \; Q(x)))^{(I,E)} = T$.

• $P(x)^{(I,E[x\mapsto 1])} = F$ because $E[x\mapsto 1](x) = 1 \notin P^I$. By the satisfaction rule for $\forall$, $(\forall x \; P(x))^{(I,E)} = F$.
• By the satisfaction rule for an implication, $((\forall x \; P(x)) \to (\forall x \; Q(x)))^{(I,E)} = T$ because the hypothesis is aflse.

Next, we shall show $(\forall x \;(P(x) \to Q(x)))^{(I,E)} = F$.

• $(P(x) \to Q(x))^{(I,E[x\mapsto 2])}= F$ because $E[x\mapsto 2](x)=2\in P^I$ but $E[x\mapsto 2](x) = 2 \not\in Q^I$.
• By the satisfaction rule for $\forall$, $(\forall x \;(P(x) \to Q(x)))^{(I,E)} = F$

Hence, the entailment does not hold. $\square$

Example III. Show that $\{(\exists y \; (\forall x \; Q(x,y)))\} \models (\forall x \; (\exists y \; Q(x,y)))$.

Solution III. Let $E$ be an arbitrary environment. Consider an interpretation $I$ such that $(\exists y \; (\forall x \; Q(x,y))^{(I,E)} = T$. We will show that $(\forall x \; (\exists y \; Q(x,y)))^{(I,E)} = T$.

• By the satisfaction rules for $\exists$, $\exists d_y \in dom(I) : (\forall x \; Q(x,y))^{(I,E[y\mapsto d_y])} = T$
• By the satisfaction rules for $\forall$, $\exists d_y \in dom(I) : \forall d\in dom(I) : Q(x,y)^{(I,E[y\mapsto d_y][x\mapsto d])} = T$
• The substitutions are independent, thus we can rewrite to $\exists d_y \in dom(I) : \forall d\in dom(I) : Q(x,y)^{(I,E[x\mapsto d][y\mapsto d_y])} = T$.
• By the satisfaction rules for $\exists$, $\forall d \in dom(I) : \exists y\in dom(I) : Q(x,y)^{(I,E[x\mapsto])} = T$.
• By the satisfaction rules for $\forall$, $(\forall x \; (\exists y \; Q(x,y)))^{(I, E)} = T$. $\square$

Natural Deduction

We present four new rules; two of them are pretty much trivial; the other two are a little bit more challenging.

Trivial: Forall-elimination

• Analogous to $\land e$.
• Given $(\forall x \; P(x))$, you can substiute $x$ with any domain element $d$ and $P(d)$ holds true.

Trivial: Exists-introduction

• Analogous to $\lor i$.
• Given $P(d)$ where $d$ is any domain element, you can claim $(\exists x : P(x))$.

Challenging: Forall-introduction

• Analogous to $\land i$.
• Given $P(u)$, the only thing we know is $u$ is some domain element (if $u$ is special, the generalized $(\forall x \; P(x))$ might not be valid)..
• We introduce a fresh variable (inside a subproof) and end the subproof with $\alpha[u/x]$. The intuition is, if plugging in an arbitrary variable $u$ into $x$ and $\alpha$ still holds, then $(\forall x \; \alpha)$ should be valid.
• When you choose the fresh variable $u$, make sure it does not appear anywhere outside this subproof.

Challenging: Exists-elimination

• Analogous to $\lor e$.
• Given $(\exists x \; \alpha)$, to conclude $\beta$, we want to introduce a fresh variable on the first line of a subproof using "$\alpha[u/x], u$ fresh", then reach the conclusion $\beta$ at the last line of the subproof.
• The intuition is, you are told that there exists some domain element which makes $\alpha$ work, then you substitution an arbitrary element and reach a conclusion. Since this element is arbitrary, you essentially did a proof by cases, where every case is covered in this subproof with an arbitrary element.