2.4: Rules of Inference

Having established our set \(\Lambda\) of logical axioms, we must now fix our rules of inference. There will be two types of rules, one dealing with propositional consequence and one dealing with quantifiers.

Propositional Consequence

In all likelihood you are familiar with tautologies of propositional logic. They are simply formulas like \(\left( A \rightarrow B \right) \leftrightarrow \left( \neg B \rightarrow \neg A \right)\). If you are comfortable with tautologies, feel free to skip over the next couple of paragraphs. If not, what follows is a very brief review of a portion of propositional logic.

We work with a restricted language \(\mathcal{P}\), consisting only of a set of propositional variables \(A, B, C, \ldots\) and the connectives \(\lor\) and \(\neg\). Notice there are no quantifiers, no relation symbols, no function symbols, and no constants. Formulas of propositional logic are defined as being the collection of all \(\phi\) such that either \(\phi\) is a propositional variable, or \(\phi\) is \(\left( \neg \alpha \right)\), or \(\phi\) is \(\left( \alpha \lor \beta \right)\), with \(\alpha\) and \(\beta\) being formulas of propositional logic.

Each propositional variable can be assigned one of two truth values, \(T\) or \(F\), corresponding to truth or falsity. Given such an assignment (which is really a function \(v \: : \: \text{propositional variables} \rightarrow \{T, F\}\)), we can extend \(v\) to a function \(\bar{v}\) assigning a truth value to any propositional formula as follows:

\[\bar{v} \left( \phi \right) \begin{cases} \begin{array}{ll} v \left( \phi \right) & \text{if} \: \phi \: \text{is a propositional variable} \\ F & \text{if} \: \phi : \equiv \left( \neg \alpha \right) \: \text{and} \bar{v} \left( \alpha \right) = T \\ F & \text{if} \: \phi : \equiv \left( \alpha \lor \beta \right) \: \text{and} \: \bar{v} \left( \alpha \right) = \bar{v} \left( \beta \right) = F \\ T & \text{otherwise} \end{array} \end{cases}\]

Now we say that a propositional formula \(\phi\) is a tautology if and only if \(\bar{v} \left( \phi \right) = T\) for any truth assignment \(v\).

One way that you can check whether a given \(\phi\) is a tautology is by constructing a truth table with one row for each possible combination of truth values for the propositional variables that occur in \(\phi\). Then you fill in the truth table and see whether the truth value associated with the main connective is always true. For example, consider the propositional formula \(A \rightarrow \left( B \rightarrow A \right)\), which is translated to \(\neg A \lor \left( \neg B \lor A \right)\). The truth table verifying that this formula is a tautology is

\[\begin{array}{cc|c||c||ccc} A & B & \neg A & \lor & (\neg B & \lor & A) \\ \hline T & T & F & T & F & T & T \\ T & F & F & T & T & T & T \\ F & T & T & T & F & F & F \\ F & F & T & T & T & T & F \end{array}\]

To discuss propositional consequence in first-order logic, we will transfer our formulas to the realm of propositional logic and use the idea of tautology in that area. To be specific, given \(\beta\), an \(\mathcal{L}\)-formula of first-order logic, here is a procedure that will convert \(\beta\) to a formula \(\beta_P\) of propositional logic corresponding to \(\beta\):

1. Find all subformulas of \(\beta\) of the form \(\forall x \alpha\) that are not in the scope of another quantifier. Replace them with propositional variables in a systematic fashion. This means that if \(\forall y Q \left( y, c \right)\) appears twice in \(\beta\), it is replaced by the same letter both times, and distinct subformulas are replaced with distinct letters.
2. Find all atomic formulas that remain, and replace them systematically with new propositional variables.
3. At this point, \(\beta\) will have been replaced with a propositional formula \(\beta_P\).

For example, suppose that we look at the \(\mathcal{L}\)-formula

\[\left( \forall x P \left( x \right) \land Q \left( c, z \right) \right) \rightarrow \left( Q \left( c, z \right) \lor \forall x P \left( x \right) \right).\]

For the first step of the procedure above, we replace the quantified subformulas with the propositional letter \(B\):

\[\left( B \land Q \left( c, z \right) \right) \rightarrow \left( Q \left( c, z \right) \lor B \right).\]

To finish the transformation to a propositional formula, replace the atomic formula with a propositional letter:

\[\left( B \land A \right) \rightarrow \left( A \lor B \right).\]

Notice that if \(\beta_P\) is a tautology, the \(\beta\) is valid, but the converse of this statement fails. For example, if \(\beta\) is

\[\left[ \left( \forall x \right) \left( \theta \right) \land \left( \forall x \right) \left( \theta \rightarrow \rho \right) \right] \rightarrow \left( \forall x \right) \left( \rho \right),\]

then \(\beta\) is valid, but \(\beta_P\) would be \(\left[ A \land B \right] \rightarrow C\), which is certainly not a tautology.

We are now almost at a point where we can state our propositional rule of inference. Recall that a rule of inference is an ordered pair \(\left( \Gamma, \phi \right)\), where \(\Gamma\) is a set of \(\mathcal{L}\)-formulas and \(\phi\) is an \(\mathcal{L}\)-formula.

Definition 2.4.1. Suppose that \(\Gamma_P\) is a set of propositional formulas and \(\phi_P\) is a propositional formula. We will say that \(\phi_P\) is a propositional consequence of \(\Gamma_P\) if every truth assignment that makes each propositional formula in \(\Gamma_P\) true also makes \(\phi_P\) true. Notice that \(\phi_P\) is a tautology if and only if \(\phi_P\) is a propositional consequence of \(\emptyset\).

Lemma 2.4.2. If \(\Gamma_P = \{ \gamma_{1 \: P}, \gamma_{2 \: P}, \ldots, \gamma_{n \: P} \}\) is a nonempty finite set of propositional formulas and \(\phi_P\) is a propositional formula, then \(\phi_P\) is a propositional consequence of \(\Gamma_P\) if and only if

\[\left[ \gamma_{1 \: P} \land \gamma_{2 \: P} \land \cdots \land \gamma_{n \: P} \right] \rightarrow \phi_P\]

is a tautology.

Proof. Exercise 3.

Now we extend our definition of propositional consequence to include formulas of first-order logic:

Definition 2.4.3. Suppose that \(\Gamma\) is a finite set of \(\mathcal{L}\)-formulas and \(\phi\) is an \(\mathcal{L}\)-formula. We will say that \(\phi\) is a propositional consequence of \(\Gamma\) if \(\phi_P\) is a propositional consequence of \(\Gamma_P\), where \(\phi_P\) and \(\Gamma_P\) are the results of applying the procedure above uniformly to \(\phi\) and all of the formulas in \(\Gamma\).

Example 2.4.4. Suppose that \(\mathcal{L}\) contains two unary relation symbols, \(P\) and \(Q\). Let \(\Gamma\) be the set

\[\{ \forall x P \left( x \right) \rightarrow \exists y Q \left( y \right), \exists y Q \left( y \right) \rightarrow P \left( x \right), \neg P \left( x \right) \leftrightarrow \left( y = z \right) \}.\]

If we let \(\phi\) be the formula \(\forall x P \left( x \right) \rightarrow \neg \left( y = z \right)\), then by applying our procedure uniformly to the elements of \(\Gamma\) and \(\phi\), we see that.

\[\Gamma_P \: \text{is} \: \{ A \rightarrow B, B \rightarrow C, \neg C \leftrightarrow D \}\]

and \(\phi_P\) is \(A \rightarrow \neg D\), where the fact that we have substituted the same propositional variables for the same formulas in \(\phi\) and the elements of \(\Gamma\) is ensured by our applying the procedure uniformly to all of the formulas in question. At this point it is easy to verify that \(\phi\) is a propositional consequence of \(\Gamma\).

Finally, our rule of inference:

Definition 2.4.5. If \(\Gamma\) is a finite set of \(\mathcal{L}\)-formulas, \(\phi\) is an \(\mathcal{L}\)-formula, and \(\phi\) is a propositional consequence of \(\Gamma\), then \(\left( \Gamma, \phi \right)\) is a rule of inference of type (PC).

Chaff: All of this formalism just might be hiding what is really going on here. What rule (PC) says is that if you have proved \(\gamma_1\) and \(\gamma_2\) and \(\left[ \left( \gamma_1 \land \gamma_2 \right) \rightarrow \phi \right]_P\) is a tautology, then you may conclude \(\phi\). Nothing fancier than that.

Also notice that if \(\phi\) is a formula such that \(\phi_P\) is a tautology, rule (PC) allows us to assert \(\phi\) in any deduction, using \(\Gamma = \emptyset\).

Quantifier Rules

The motivation behind our quantifier rules is very simple. Suppose, without making any particular assumptions about \(x\), that you were able to prove "\(x\) is an ambitious aardvark". Then it seems reasonable to claim that you have proved "\(\left( \forall x \right) x\) is an ambitious aardvark". Dually, if you were able to prove the Riemann Hypothesis from the assumption that "\(x\) is a bossy bullfrog", then from the assumption "\(\left( \exists x \right) x\) is a bossy bullfrog", you should still be able to prove the Riemann Hypothesis.

Definition 2.4.6. Suppose that the variable \(x\) is not free in the formula \(\psi\). Then both of the following are rules of inference of type (QR):

\[\left( \{ \psi \rightarrow \phi \}, \psi \rightarrow \left( \forall x \phi \right) \right)\]

\[\left( \{ \phi \rightarrow \psi \}, \left( \exists x \phi \right) \rightarrow \psi \right).\]

The "not making any particular assumptions about \(x\)" comment is made formal by the requirement that \(x\) not be free in \(\psi\).

Chaff: Just to make sure that you are not lost in the brackets of the definition, what we are saying here is that if \(x\) is not free in \(\psi\):

1. From the formula \(\psi \rightarrow \phi\), you may deduce \(\psi \rightarrow \left( \forall x \phi \right)\).
2. From the formula \(\phi \rightarrow \psi\), you may deduce \(\left( \exists x \phi \right) \rightarrow \psi\).

Exercises

1. We claim that the collection \(\Lambda\) of logical axioms is decidable. Outline an algorithm which, given an \(\mathcal{L}\)-formula \(\theta\), outputs "yes" if \(\theta\) is an element of \(\Lambda\) and outputs "no" if \(\theta\) is not an element of \(\Lambda\). You do not have to be too fussy. Notice that you have to be able to decide if a term \(t\) is substitutable for a variable \(x\) in a formula \(\phi\). See Exercise 7 in Section 1.8.
2. Show that the set of rules of inference is decidable. So outline an algorithm that will decide, given a finite set of formulas \(\Gamma\) and a formula \(\theta\), whether or not \(\left( \Gamma, \theta \right)\) is a rule of inference.
3. Prove Lemma 2.4.2.
4. Write a deduction of the second quantifier axiom (Q2) without using (Q2) as an axiom.
5. For each of the following, decide if \(\phi\) is a propositional consequence of \(\Gamma\) and justify your assertion.
   (a) \(\Gamma\) is \(\{ \left( \forall P \left( x \right) \right) \rightarrow Q \left( y \right), \left( \forall x P \left( x \right) \right) \lor \left( \forall x R \left( x \right) \right), \exists x \neg R \left( x \right) \}\); \(\phi\) is \(Q \left( y \right)\).
   (b) \(\Gamma\) is \(\{ x = y \land Q \left( y \right), Q \left( y \right) \lor x + y < z \}\); \(\phi\) is \(x + y < z\).
   (c) \(\Gamma\) is \(\{ P \left( x, y, x \right), x < y \lor M \left( w, p \right), \left( \neg P \left( x, y, x \right) \right) \land \left( \neg x < y \right) \}\); \(\phi\) is \(\neg M \left( w, p \right)\).
6. Prove that if \(\theta\) is not valid, then \(\theta_P\) is not a tautology. Deduce that if \(\theta_P\) is a tautology, then \(\theta\) is valid.