4. Logical Equivalence and Consequence

Logical Equivalence

Two formulas $\phi$ and $\psi$ in $L^p(\sigma)$ are (logically) equivalent when every truth assignment causes $\phi$ and $\psi$ to evaluate to the same value. We write

\[\phi \equiv \psi\]

when $\phi$ and $\psi$ are equivalent formulas.

We can demonstrate logical equivalence using a truth table that has columns giving the truth values of both formulas under each truth assignment. For example, the equivalence $(p \to q) \equiv (\neg p \vee q)$ is verified by the table

\[\begin{array}{cc|c|c} p & q & (p \to q) & (\neg p \vee q)\phantom{\neg} \\ \hline T & T & T & T \\ T & F & F & F \\ F & T & T & T \\ F & F & T & T \end{array}\]

Examples of equivalences:

$\neg \neg p \equiv p$

$\neg(p \vee q) \equiv (\neg p \wedge \neg q)$

$\neg(p \wedge q) \equiv (\neg p \vee \neg q)$

$((p \wedge q) \wedge r) \equiv (p \wedge (q \wedge r))$

$(p \vee q) \equiv (q \vee p)$

$(p \leftrightarrow q) \equiv ((p \to q) \wedge (q \to p))$

Logical Consequence

The formula $\phi$ is a logical consequence of the set $\Gamma$ of formulas when every truth assignment that satisfies every formula in $\Gamma$ also satisfies $\phi$. We write

\[\Gamma \vDash \phi\]

to denote logical consequence.

Some logical consequences are simple:

Examples: Fix any formulas $\phi$, $\psi$, and $\theta$. Some logical consequences are simple:

$\{(\phi \wedge \psi)\} \vDash \phi$.

$\{\phi, \psi\} \vDash (\phi \wedge \psi)$.

$\{\phi\} \vDash (\phi \vee \psi)$.

$\{(\phi \to \psi), \phi\} \vDash \psi$.

$\{\neg(\phi \vee \psi)\} \vDash (\neg \phi \wedge \neg \psi)$.

Others can be more complex:

$\{\phi, \neg \theta\} \vDash (\psi \vee (\theta \to \neg \phi))$.

$\{((\phi \wedge \psi) \to \theta), (\phi \to (\psi \vee \theta))\} \vDash (\phi \to \theta)$.

$\{\neg((\phi \wedge \psi) \wedge \neg\theta), ((\neg \phi \vee \psi) \vee \neg \theta)\} \vDash \neg((\phi \wedge \psi) \leftrightarrow (\phi \to \neg \theta))$.

Note that the set $\Gamma$ does not have to be finite in the definition. One example of a logical consequence with an infinite set $\Gamma$ is this consequence which holds for any $k \in \mathbb{N}$:

\[\{p_1\} \cup \{ (p_n \to p_{n+1}) \}_{n \ge 1} \vDash p_k.\]

(Does this logical consequence look familiar?)

There is also one special class of logical consequences that may look puzzling at first. Fix any formula $\phi \in L^p(\sigma)$. Then

\[\{ (p \wedge \neg p) \} \vDash \phi\]

is a valid logical consequence. More generally, every formula $\phi$ is a logical consequence of any set $\Gamma$ that includes a contradiction: since a contradiction has no satisfying truth assignment, the condition for logical consequence is trivially satisfied.

Tautologies

When $\phi$ is a tautology, then $\phi$ is a logical consequence of the empty set $\emptyset$. We can write this as $\emptyset \vDash \phi$ following the convention above. But in this case we usually write

\[\vDash \phi\]

instead, with no argument to the left of the $\vDash$ symbol.

There is a close connection between logical consequence and tautologies. One way to express this connection is via the following basic observation.

Proposition. For any finite set $\{\phi_1,\ldots,\phi_n\}$ of formulas and any formula $\psi$,
\[\{ \phi_1, \phi_2, \phi_3, \ldots, \phi_n\} \vDash \psi\]
if and only if
\[\vDash (((\cdots((\phi_1 \wedge \phi_2) \wedge \phi_3) \cdots) \wedge \phi_n) \to \psi).\]

Proof. Let us write $\theta = ((\cdots((\phi_1 \wedge \phi_2) \wedge \phi_3) \cdots ) \wedge \phi_n)$. The key observation is that the set of truth assignments that satisfy all of $\phi_1,\ldots,\phi_n$ is exactly the set of truth assignments that satisfy $\theta$. We use it to prove both directions of the “if and only if” statement.

$(\Rightarrow)$ When $\{\phi_1,\ldots,\phi_n\} \vDash \psi$, then by definition every truth assignment that satisfies each of $\phi_1,\ldots,\phi_n$ also satisfies $\psi$. But by the key observation above, this means that every assignment that satisfies $\theta$ also satisfies $\psi$. Therefore, $(\theta \to \psi)$ is a tautology.

$(\Leftarrow)$ In the other direction, when $(\theta \to \psi)$ is a tautology, then every truth assignment that satisfies $\theta$ also satisfies $\psi$. Using the key observation once again, this means that every assignment that satisfies all of $\phi_1,\ldots,\phi_n$ also satisfy $\psi$. Therefore, $\{\phi_1,\ldots,\phi_n\} \vDash \psi$.

Logical Argument Validity

Recall that a logical argument is a set of propositions that we call premisses and a single proposition called the conclusion. A logical argument is valid if whenever all the premisses are true, then so is the conclusion.

The tools we have developed so far give us a way to check the validity of any logical argument:

Identify all the atomic propositions and assign each of them to a propositional variable.
Translate all the premisses and the conclusion as formulas over those propositional variables.
Using truth tables, verify that all the truth assignments that satisfy all of the premisses also satisfy the conclusion.

This method works for all logical arguments. But it is not completely satisfactory in a number of ways.

First, it is not efficient. Even when the set of premisses is finite the truth table for a formula over $n$ propositional variables has $2^n$ rows so the method we have described corresponds to (at best) an exponential-time algorithm and quickly becomes infeasible.

Second, this method does not help explain why logical arguments might be valid. Ideally, we would like the verification method to not only verify the validity of arguments but also show in more detail how the conclusion follows from the premisses. This is analogous to the situation in mathematics, where a good proof of a mathematical theorem does not just demonstrate its truth but also gives meaningful insights into why the theorem is true.

And finally, we will see in the next part of the course when we introduce First-Order Logic that this truth table method does not extend to that richer logic model. We would like to develop an alternative verification method that will be applicable in that setting as well.

All three of these weaknesses of the truth table method will be addressed by introducing a different approach to proving the validity of logical arguments: formal proofs, the topic to be introduced in the next lecture.