Formulas, Truth Tables, and Logical Equivalence
Learning Objectives
- Define well-formed formulas recursively
- Apply operator precedence to parse formulas correctly
- Construct truth tables for compound formulas involving several connectives
- Classify formulas as tautologies, contradictions, or contingencies
- Define logical equivalence and verify it via truth tables
- Apply De Morgan’s Laws and other fundamental equivalences
From Connectives to Formulas
In the previous two lessons we defined the five classical propositional connectives: \(\neg, \land, \lor, \to, \leftrightarrow\). With these operations we can build compound propositions of arbitrary complexity from atomic ones. For example, from the atomic propositions \(P, Q, R\) we may form:
\[(P \land \neg Q) \to (R \lor \neg P)\]
But what, precisely, is a compound proposition? When does a string of symbols constitute a legitimate formula, and when is it mere notation? And given two distinct formulas, when do they express the same logical content?
These questions are the subject of this lesson. We begin by defining formulas rigorously, then study how to evaluate them systematically, and finally introduce the notion of logical equivalence — the relation that underlies all propositional reasoning.
Well-Formed Formula
The set of well-formed formulas (or simply formulas) of propositional logic is defined recursively by the following clauses:
Every propositional variable \(P, Q, R, \ldots\) is a well-formed formula. Such formulas are called atomic.
If \(\varphi\) is a well-formed formula, then \(\neg\varphi\) is a well-formed formula.
If \(\varphi\) and \(\psi\) are well-formed formulas, then \((\varphi \land \psi)\), \((\varphi \lor \psi)\), \((\varphi \to \psi)\), and \((\varphi \leftrightarrow \psi)\) are well-formed formulas.
Nothing else is a well-formed formula.
The symbols \(\varphi\) and \(\psi\) (Greek phi and psi) are metavariables: they range over arbitrary formulas within the definition itself. They are not propositional variables of the object language.
Operator Precedence
According to the strict definition, every application of a binary connective introduces a pair of parentheses. The formula
\[((P \land Q) \lor (\neg R))\]
is well-formed; but the more concise
\[P \land Q \lor \neg R\]
is ambiguous without further convention, since it might stand for either \((P \land Q) \lor \neg R\) or \(P \land (Q \lor \neg R)\).
To reduce notational clutter while preserving unambiguity, we adopt the following precedence hierarchy, from tightest to loosest binding:
\[\begin{array}{|c|l|} \hline \text{Rank} & \text{Connective} \\ \hline 1 & \neg \\ 2 & \land \\ 3 & \lor \\ 4 & \to \\ 5 & \leftrightarrow \\ \hline \end{array}\]
A connective of lower rank binds tighter than one of higher rank. Thus \(P \land Q \lor \neg R\) parses unambiguously as \((P \land Q) \lor (\neg R)\).
The implication \(\to\) is conventionally right-associative: \(P \to Q \to R\) abbreviates \(P \to (Q \to R)\). When a formula becomes difficult to read, however, parentheses remain the safest guide — precedence conventions exist to clarify, never to obscure.
Parsing — Examples
Each of the following formulas is shown with its implicit parentheses restored:
\(\neg P \land Q\) means \((\neg P) \land Q\), not \(\neg(P \land Q)\).
\(P \land Q \to R\) means \((P \land Q) \to R\).
\(P \to Q \leftrightarrow \neg R\) means \((P \to Q) \leftrightarrow (\neg R)\).
\(\neg P \lor Q \land R\) means \((\neg P) \lor (Q \land R)\).
\(P \to Q \to R\) means \(P \to (Q \to R)\) — not \((P \to Q) \to R\).
Truth Tables for Compound Formulas
A truth table for a formula displays the truth value of the formula under every possible assignment of truth values to its propositional variables. A formula containing \(n\) distinct variables admits \(2^n\) possible assignments, yielding a truth table with \(2^n\) rows.
To evaluate a compound formula, proceed compositionally: evaluate the innermost sub-expressions first, then work outward, filling in a column for each sub-expression until the full formula is reached. Each column depends only on columns already computed.
A Full Truth Table
Consider the formula:
\[(P \lor Q) \land \neg(P \land Q)\]
It contains two variables (\(P, Q\)) and four sub-expressions: \(P \lor Q\), \(P \land Q\), \(\neg(P \land Q)\), and the full formula. Its truth table requires \(2^2 = 4\) rows:
\[\begin{array}{|c|c|c|c|c|c|} \hline P & Q & P \lor Q & P \land Q & \neg(P \land Q) & (P \lor Q) \land \neg(P \land Q) \\ \hline T & T & T & T & F & F \\ T & F & T & F & T & T \\ F & T & T & F & T & T \\ F & F & F & F & T & F \\ \hline \end{array}\]
Observation: the formula is true precisely when \(P\) and \(Q\) have different truth values. This pattern is known as the exclusive disjunction — sometimes denoted \(P \oplus Q\). It demonstrates that further connectives can be defined in terms of the five we already possess.
Tautology, Contradiction, Contingency
Formulas may be classified by the pattern of truth values they produce across all assignments.
A tautology is a formula that is true under every assignment of truth values to its variables.
A contradiction is a formula that is false under every assignment.
A contingency is a formula that is neither a tautology nor a contradiction — that is, it is true under some assignments and false under others.
Tautologies are the formulas guaranteed to hold by logic alone, independently of any subject matter. Contradictions are the formulas that can never hold. Contingencies are the formulas whose truth depends on what the world happens to be like.
Tautology, Contradiction, Contingency — Examples
\(P \lor \neg P\) is a tautology — it is the Law of Excluded Middle.
\(P \land \neg P\) is a contradiction — it is the negation of the Law of Non-Contradiction.
\(P \to Q\) is a contingency — it is false only when \(P\) is true and \(Q\) is false, and true otherwise.
\(\neg\neg P \leftrightarrow P\) is a tautology — negating twice returns the original value.
\((P \to Q) \land P \land \neg Q\) is a contradiction — it requires \(P \to Q\), \(P\), and \(\neg Q\) to all hold, which is impossible.
Logical Equivalence
Two formulas \(\varphi\) and \(\psi\) are logically equivalent, written
\[\varphi \equiv \psi\]
if they have the same truth value under every assignment of truth values to their propositional variables.
Equivalently, \(\varphi \equiv \psi\) if and only if the biconditional \(\varphi \leftrightarrow \psi\) is a tautology.
A Note on Notation
The symbol \(\equiv\) is not a connective of the object language. It is a metalinguistic symbol used to make statements about formulas. Contrast:
\(P \leftrightarrow Q\) is a formula — a string of symbols with a truth value depending on \(P\) and \(Q\).
\(P \leftrightarrow Q \equiv Q \leftrightarrow P\) is a claim — it asserts, in our metalanguage, that the two formulas have identical truth-value behaviour.
This object-language/metalanguage distinction is central to formal logic and will reappear throughout our courses.
Verifying Equivalence via Truth Tables
To verify that two formulas \(\varphi\) and \(\psi\) are logically equivalent, construct a truth table with a column for each formula and check that the two columns agree in every row. Since truth tables exhaust all possible assignments, agreement in every row establishes logical equivalence.
This method is decidable: for any two propositional formulas, the question “are they equivalent?” can be settled mechanically in finitely many steps. This is a distinguishing feature of propositional logic and does not extend to richer logical systems.
Verifying the Material Implication Equivalence
In Lesson 2 we claimed that \(P \to Q\) and \(\neg P \lor Q\) have the same truth values. We now prove it by truth table.
\[\begin{array}{|c|c|c|c|c|} \hline P & Q & P \to Q & \neg P & \neg P \lor Q \\ \hline T & T & T & F & T \\ T & F & F & F & F \\ F & T & T & T & T \\ F & F & T & T & T \\ \hline \end{array}\]
The columns for \(P \to Q\) and \(\neg P \lor Q\) agree in all four rows. Therefore:
\[P \to Q \;\equiv\; \neg P \lor Q\]
This is known as the material implication equivalence. It reduces implication to a combination of negation and disjunction, and it is one of the most frequently applied equivalences in all of logic.
De Morgan’s Laws
For all formulas \(P\) and \(Q\):
\[\neg(P \land Q) \;\equiv\; \neg P \lor \neg Q\]
\[\neg(P \lor Q) \;\equiv\; \neg P \land \neg Q\]
In words:
The negation of a conjunction is the disjunction of the negations.
The negation of a disjunction is the conjunction of the negations.
These laws, named after the 19th-century logician Augustus De Morgan, describe how negation distributes over conjunction and disjunction. They will reappear throughout our courses — in reasoning about sets, predicates, and quantifiers — always with the same fundamental shape.
Verifying De Morgan’s First Law
We verify \(\neg(P \land Q) \equiv \neg P \lor \neg Q\) by truth table.
\[\begin{array}{|c|c|c|c|c|c|c|} \hline P & Q & P \land Q & \neg(P \land Q) & \neg P & \neg Q & \neg P \lor \neg Q \\ \hline T & T & T & F & F & F & F \\ T & F & F & T & F & T & T \\ F & T & F & T & T & F & T \\ F & F & F & T & T & T & T \\ \hline \end{array}\]
The columns for \(\neg(P \land Q)\) and \(\neg P \lor \neg Q\) agree in every row. The second De Morgan law can be verified analogously.
A Catalogue of Fundamental Equivalences
The following equivalences hold for all formulas \(P, Q, R\). Each can be verified by constructing a truth table.
Name | Equivalence |
|---|---|
Double negation | \(\neg\neg P \equiv P\) |
Commutativity of \(\land\) | \(P \land Q \equiv Q \land P\) |
Commutativity of \(\lor\) | \(P \lor Q \equiv Q \lor P\) |
Associativity of \(\land\) | \((P \land Q) \land R \equiv P \land (Q \land R)\) |
Associativity of \(\lor\) | \((P \lor Q) \lor R \equiv P \lor (Q \lor R)\) |
Distributivity of \(\land\) over \(\lor\) | \(P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)\) |
Distributivity of \(\lor\) over \(\land\) | \(P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)\) |
Idempotence of \(\land\) | \(P \land P \equiv P\) |
Idempotence of \(\lor\) | \(P \lor P \equiv P\) |
De Morgan (\(\land\)) | \(\neg(P \land Q) \equiv \neg P \lor \neg Q\) |
De Morgan (\(\lor\)) | \(\neg(P \lor Q) \equiv \neg P \land \neg Q\) |
Material implication | \(P \to Q \equiv \neg P \lor Q\) |
Contrapositive | \(P \to Q \equiv \neg Q \to \neg P\) |
Biconditional as mutual implication | \(P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)\) |
Every formula built from the five classical connectives can be transformed into an equivalent formula using combinations of these equivalences. The catalogue is therefore an essential toolkit: it allows us to rewrite formulas into standard forms, to simplify them, and to demonstrate equivalences without always resorting to truth tables.
Exercise 1
For each formula, classify it as tautology, contradiction, or contingency.
Exercise 2
For each pair, determine whether the two formulas are logically equivalent.
Exercise 3
For each formula, find the logically equivalent one using De Morgan’s Laws and other equivalences.
Critical Examination
A student is asked to negate the statement “If it rains, then the ground is wet.” They write:
“If it does not rain, then the ground is not wet.”
Writing \(P\) for “it rains” and \(Q\) for “the ground is wet,” this reads: \(\neg(P \to Q) \equiv \neg P \to \neg Q\). Is the student correct?
Analysis
They are not. The formula \(\neg P \to \neg Q\) is the inverse of \(P \to Q\), not its negation. As we noted in Lesson 2, an implication and its inverse are in general not logically equivalent.
To compute the actual negation, we apply the equivalences established in this lesson:
\[\neg(P \to Q) \;\equiv\; \neg(\neg P \lor Q) \qquad \text{[material implication]}\]
\[\phantom{\neg(P \to Q)} \;\equiv\; \neg\neg P \land \neg Q \qquad \text{[De Morgan]}\]
\[\phantom{\neg(P \to Q)} \;\equiv\; P \land \neg Q \qquad \text{[double negation]}\]
The correct negation is therefore:
\[\neg(P \to Q) \;\equiv\; P \land \neg Q\]
In words, the negation of “If \(P\), then \(Q\)” is “\(P\) holds, and yet \(Q\) does not.” Applied to the original example: the negation of “If it rains, then the ground is wet” is not “If it does not rain, then the ground is not wet.” It is: “It rains, but the ground is not wet.”
This distinction carries practical weight in proof. To refute an implication, one must exhibit a case in which the hypothesis holds but the conclusion fails — a single such case suffices. Exhibiting a case in which the hypothesis fails proves nothing about the implication at all, since an implication with a false hypothesis is vacuously true.
Summary
A well-formed formula is defined recursively from propositional variables and the five connectives.
Operator precedence (\(\neg, \land, \lor, \to, \leftrightarrow\) from tightest to loosest) reduces the need for parentheses.
A truth table for a formula with \(n\) variables has \(2^n\) rows. Compound formulas are evaluated compositionally, one sub-expression at a time.
A formula is a tautology if it is true in every row, a contradiction if false in every row, a contingency otherwise.
Two formulas are logically equivalent, written \(\varphi \equiv \psi\), if they have the same truth value under every assignment. The symbol \(\equiv\) is metalinguistic; it is not a connective.
De Morgan’s Laws: \(\neg(P \land Q) \equiv \neg P \lor \neg Q\) and \(\neg(P \lor Q) \equiv \neg P \land \neg Q\).
Other key equivalences: double negation, commutativity, associativity, distributivity, material implication, contrapositive, biconditional as mutual implication.
The negation of an implication \(P \to Q\) is \(P \land \neg Q\), not \(\neg P \to \neg Q\).