The Central Idea
Two propositions \(A\) and \(B\) are logically equivalent when they always have the same truth value.
We write
\[ \boxed{A\equiv B}. \]This means that every truth assignment making \(A\) true also makes \(B\) true, and every truth assignment making \(A\) false also makes \(B\) false.
Equivalence Is About All Possible Cases
Two formulas are not logically equivalent merely because they agree under one assignment.
They must agree under every possible assignment.
For formulas involving \(n\) variables, that means checking all
\[ 2^n \]truth-value combinations.
Truth Tables Can Prove Equivalence
Consider
\[ \neg\neg p \]and
\[ p. \]| \(p\) | \(\neg p\) | \(\neg\neg p\) |
|---|---|---|
| T | F | T |
| F | T | F |
The \(p\) and \(\neg\neg p\) columns match.
Therefore,
\[ \boxed{\neg\neg p\equiv p}. \]Equivalence and the Biconditional
If
\[ A\equiv B, \]then
\[ A\leftrightarrow B \]is a tautology.
The biconditional is true in every row because \(A\) and \(B\) always have matching truth values.
Logical Equivalence Is Not Equality of Symbols
The expressions
\[ p\to q \]and
\[ \neg p\lor q \]look different.
Yet they have identical truth behavior.
Thus,
\[ \boxed{p\to q\equiv\neg p\lor q}. \]Logical equivalence compares meaning through truth behavior, not visual appearance.
The Identity Laws
Combining a proposition with a neutral truth value leaves it unchanged:
\[ \boxed{p\land T\equiv p} \]and
\[ \boxed{p\lor F\equiv p}. \]These are called identity laws.
The Domination Laws
Some Boolean constants determine the result regardless of \(p\):
\[ \boxed{p\lor T\equiv T} \]and
\[ \boxed{p\land F\equiv F}. \]These are often called domination laws.
The Idempotent Laws
Repeating the same proposition does not change its truth behavior:
\[ \boxed{p\lor p\equiv p} \]and
\[ \boxed{p\land p\equiv p}. \]These are the idempotent laws.
The Double-Negation Law
Negating a proposition twice restores the original truth value:
\[ \boxed{\neg\neg p\equiv p}. \]This is the logical analogue of undoing a reversal by reversing again.
The Complement Laws
A proposition and its negation cannot both be true:
\[ \boxed{p\land\neg p\equiv F}. \]At least one of them must be true:
\[ \boxed{p\lor\neg p\equiv T}. \]These are complement relationships.
The Commutative Laws
For AND and OR, the order of the propositions does not matter:
\[ \boxed{p\land q\equiv q\land p} \]and
\[ \boxed{p\lor q\equiv q\lor p}. \]This mirrors the commutative structure of addition and multiplication.
The Associative Laws
When the same operation is repeated, grouping can be changed:
\[ \boxed{(p\land q)\land r\equiv p\land(q\land r)} \]and
\[ \boxed{(p\lor q)\lor r\equiv p\lor(q\lor r)}. \]Therefore, repeated AND or repeated OR can often be written without internal parentheses.
The Distributive Laws
AND distributes over OR:
\[ \boxed{p\land(q\lor r)\equiv(p\land q)\lor(p\land r)}. \]OR also distributes over AND:
\[ \boxed{p\lor(q\land r)\equiv(p\lor q)\land(p\lor r)}. \]The second relationship has no ordinary arithmetic analogue, but it is a standard feature of Boolean structure.
The Absorption Laws
Consider
\[ p\lor(p\land q). \]If \(p\) is true, the entire expression is already true.
If \(p\) is false, then \(p\land q\) is false.
Therefore,
\[ \boxed{p\lor(p\land q)\equiv p}. \]Similarly,
\[ \boxed{p\land(p\lor q)\equiv p}. \]De Morgan’s First Law
The negation of a conjunction is equivalent to the disjunction of the negations:
\[ \boxed{\neg(p\land q)\equiv\neg p\lor\neg q}. \]In words:
It is not true that both \(p\) and \(q\)
is equivalent to
\(p\) is false or \(q\) is false.
Truth Table for De Morgan’s First Law
| \(p\) | \(q\) | \(p\land q\) | \(\neg(p\land q)\) | \(\neg p\) | \(\neg q\) | \(\neg p\lor\neg q\) |
|---|---|---|---|---|---|---|
| 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 |
The two final expressions have identical columns.
De Morgan’s Second Law
The negation of a disjunction is equivalent to the conjunction of the negations:
\[ \boxed{\neg(p\lor q)\equiv\neg p\land\neg q}. \]In words:
Neither \(p\) nor \(q\) is true
means that both \(p\) and \(q\) are false.
Negation Pushes Inward and Changes the Operation
De Morgan’s laws can be remembered structurally:
- push the negation inward;
- negate each component;
- switch AND to OR or OR to AND.
Thus,
\[ \neg(p\land q) \]becomes
\[ \neg p\lor\neg q. \]Implication Law
The conditional
\[ p\to q \]is false only when \(p\) is true and \(q\) is false.
The expression
\[ \neg p\lor q \]has exactly the same truth behavior.
Therefore,
\[ \boxed{p\to q\equiv\neg p\lor q}. \]Negating an Implication
Start with
\[ \neg(p\to q). \]Replace the implication:
\[ \neg(\neg p\lor q). \]Apply De Morgan’s law:
\[ \neg\neg p\land\neg q. \]Apply double negation:
\[ \boxed{\neg(p\to q)\equiv p\land\neg q}. \]This matches the single row in which an implication is false.
The Contrapositive Law
A conditional is logically equivalent to its contrapositive:
\[ \boxed{p\to q\equiv\neg q\to\neg p}. \]This relationship is fundamental in mathematical proof.
Deriving the Contrapositive Algebraically
Begin with
\[ p\to q. \]Replace implication:
\[ \neg p\lor q. \]Now rewrite the contrapositive:
\[ \neg q\to\neg p. \]Using the implication law,
\[ \neg(\neg q)\lor\neg p. \]Simplify:
\[ q\lor\neg p. \]By commutativity,
\[ \neg p\lor q. \]Both statements therefore reduce to the same expression.
The Converse Is Not Equivalent in General
The converse of
\[ p\to q \]is
\[ q\to p. \]These are not generally equivalent.
For example, when
\[ p=T,\qquad q=F, \]we have
\[ p\to q=F \]but
\[ q\to p=T. \]Biconditional Law
A biconditional asserts two implications:
\[ \boxed{p\leftrightarrow q\equiv(p\to q)\land(q\to p)}. \]Both directions must hold simultaneously.
Biconditional as Agreement
A biconditional is true when \(p\) and \(q\) agree.
Agreement occurs when both are true or both are false:
\[ \boxed{p\leftrightarrow q \equiv (p\land q)\lor(\neg p\land\neg q)}. \]XOR as Disagreement
XOR is true when \(p\) and \(q\) differ:
\[ p\oplus q. \]One equivalent form is
\[ \boxed{p\oplus q \equiv (p\land\neg q)\lor(\neg p\land q)}. \]Another is
\[ \boxed{p\oplus q \equiv (p\lor q)\land\neg(p\land q)}. \]Biconditional and XOR
Since the biconditional detects agreement and XOR detects disagreement,
\[ \boxed{p\leftrightarrow q\equiv\neg(p\oplus q)}. \]They have opposite truth values in every row.
Replacing Equivalent Subexpressions
If two formulas are logically equivalent, one may replace the other inside a larger expression.
For example, because
\[ p\to q\equiv\neg p\lor q, \]the expression
\[ (p\to q)\land r \]can be rewritten as
\[ (\neg p\lor q)\land r. \]The overall truth behavior is preserved.
Equivalence Transformations
A sequence of valid equivalence laws can transform a logical expression without changing its truth behavior.
For example,
\[ \neg(p\to q) \]can be transformed as
\[ \neg(\neg p\lor q) \] \[ \equiv\neg\neg p\land\neg q \] \[ \equiv p\land\neg q. \]Every step is justified by a known equivalence.
Transformation Is Different from Evaluation
Evaluation assigns a particular truth value after values for the variables are given.
Equivalence transformation rewrites a formula into another formula with the same behavior for all assignments.
These are related but distinct tasks.
Example: Simplifying with Identity and Domination
Simplify
\[ (p\land T)\lor F. \]Apply the identity law:
\[ p\land T\equiv p. \]Therefore,
\[ (p\land T)\lor F \equiv p\lor F. \]Apply the identity law again:
\[ \boxed{(p\land T)\lor F\equiv p}. \]Example: Simplifying with Complement
Simplify
\[ (p\land\neg p)\lor q. \]The complement law gives
\[ p\land\neg p\equiv F. \]Therefore,
\[ F\lor q. \]Apply the identity law:
\[ \boxed{(p\land\neg p)\lor q\equiv q}. \]Example: Simplifying with Absorption
Consider
\[ p\lor(p\land q). \]By absorption,
\[ \boxed{p\lor(p\land q)\equiv p}. \]The extra conjunction cannot create a true case not already covered by \(p\).
Example: De Morgan with Three Variables
Consider
\[ \neg(p\land q\land r). \]Repeated application of De Morgan’s law gives
\[ \boxed{ \neg(p\land q\land r) \equiv \neg p\lor\neg q\lor\neg r }. \]The negation moves inward while AND becomes OR.
Negating a Three-Way Disjunction
Similarly,
\[ \neg(p\lor q\lor r) \]becomes
\[ \boxed{ \neg p\land\neg q\land\neg r }. \]For the entire OR statement to be false, every component must be false.
Equivalence and Tautologies
To show
\[ A\equiv B, \]another valid method is to show that
\[ A\leftrightarrow B \]is a tautology.
A tautological biconditional means the formulas agree in every possible case.
Equivalence and Contradictions
Two formulas are equivalent exactly when they never disagree.
Therefore,
\[ A\equiv B \]also means
\[ A\oplus B \]is a contradiction.
Why Equivalence Matters in Proof
Logical equivalence lets a statement be replaced by a more useful form.
For example,
\[ p\to q \]may be replaced by its contrapositive
\[ \neg q\to\neg p. \]In many proofs, the contrapositive is easier to establish directly.
Why Equivalence Matters in Computing
Equivalent Boolean expressions produce the same output for every input.
This means a system designer may replace one expression with another that is easier to:
- implement;
- evaluate;
- verify;
- simplify;
- translate into hardware.
Why Equivalence Matters in Digital Circuits
If two Boolean expressions are logically equivalent, circuits implementing those expressions have the same input-output behavior.
One circuit may use fewer gates or a more convenient gate family.
Later lessons will connect logical transformations directly to circuit design.
Common Error: Checking Only One Assignment
Suppose two expressions both evaluate to true when
\[ p=T,\qquad q=T. \]That single agreement does not establish equivalence.
All assignments must agree.
Common Error: Reversing an Implication
The equivalence
\[ p\to q\equiv\neg p\lor q \]does not imply
\[ p\to q\equiv q\to p. \]A conditional and its converse are generally different.
Common Error: Applying De Morgan Without Switching the Operation
The incorrect transformation
\[ \neg(p\land q)\equiv\neg p\land\neg q \]fails because AND must switch to OR.
The correct form is
\[ \boxed{\neg(p\land q)\equiv\neg p\lor\neg q}. \]Common Error: Negating Only One Component
From
\[ \neg(p\lor q), \]both components must be negated:
\[ \boxed{\neg p\land\neg q}. \]Negating only \(p\) changes the meaning.
Common Error: Confusing Equivalence with Implication
The notation
\[ A\equiv B \]means \(A\) and \(B\) have identical truth behavior.
The notation
\[ A\to B \]is itself a proposition with a truth value.
These symbols serve different roles.
Common Error: Changing More Than One Thing Without Justification
In a symbolic transformation, each step should follow from a known equivalence law.
Large unexplained jumps make errors difficult to detect.
Prefer short, justified transformations.
A Reliable Procedure for Testing Equivalence with a Truth Table
- Identify every variable appearing in either expression.
- Construct all \(2^n\) truth assignments.
- Build any needed intermediate columns.
- Compute the final column for the first expression.
- Compute the final column for the second expression.
- Compare the final columns row by row.
- If every row matches, the expressions are logically equivalent.
- If even one row differs, they are not equivalent.
A Reliable Procedure for Transforming Expressions
- Identify the main connective and important subexpressions.
- Look for a standard equivalence law that applies.
- Replace only the matching subexpression.
- Preserve parentheses and scope carefully.
- Simplify one step at a time.
- Continue until the desired form is reached.
- Use a truth table as a check when needed.
Example: Full Transformation Workflow
Simplify
\[ \neg(p\to q)\lor q. \]First use
\[ \neg(p\to q)\equiv p\land\neg q. \]Then
\[ \neg(p\to q)\lor q \equiv (p\land\neg q)\lor q. \]Use commutativity:
\[ q\lor(p\land\neg q). \]Distribute OR over AND:
\[ (q\lor p)\land(q\lor\neg q). \]Apply the complement law:
\[ (q\lor p)\land T. \]Apply the identity law:
\[ q\lor p. \]By commutativity,
\[ \boxed{\neg(p\to q)\lor q\equiv p\lor q}. \]Practice 1: Double Negation
Simplify
\[ \neg\neg p. \]Practice 2: Identity
Simplify
\[ p\land T. \]Practice 3: Domination
Simplify
\[ p\lor T. \]Practice 4: Complement
Simplify
\[ p\land\neg p. \]Practice 5: De Morgan
Rewrite
\[ \neg(p\lor q) \]without a negation outside parentheses.
Practice 6: Implication
Rewrite
\[ p\to q \]using only NOT and OR.
Practice 7: Negated Implication
Simplify
\[ \neg(p\to q). \]Practice 8: Absorption
Simplify
\[ p\lor(p\land q). \]Practice 9: Contrapositive
Write a formula logically equivalent to
\[ p\to q \]using the contrapositive.
Practice 10: Test a Proposed Equivalence
Is
\[ p\to q \]logically equivalent to
\[ q\to p? \]Explain briefly.
Practice Answers
Practice 1
\[ \boxed{\neg\neg p\equiv p}. \]Practice 2
\[ \boxed{p\land T\equiv p}. \]Practice 3
\[ \boxed{p\lor T\equiv T}. \]Practice 4
\[ \boxed{p\land\neg p\equiv F}. \]Practice 5
\[ \boxed{\neg(p\lor q)\equiv\neg p\land\neg q}. \]Practice 6
\[ \boxed{p\to q\equiv\neg p\lor q}. \]Practice 7
\[ \boxed{\neg(p\to q)\equiv p\land\neg q}. \]Practice 8
\[ \boxed{p\lor(p\land q)\equiv p}. \]Practice 9
\[ \boxed{p\to q\equiv\neg q\to\neg p}. \]Practice 10
No.
For example, if
\[ p=T,\qquad q=F, \]then
\[ p\to q=F \]while
\[ q\to p=T. \]Since at least one row differs,
\[ \boxed{p\to q\not\equiv q\to p}. \]What to Remember
- Logically equivalent formulas have the same truth value under every assignment.
- Truth tables can verify logical equivalence directly.
- \(\neg\neg p\equiv p\).
- \(\neg(p\land q)\equiv\neg p\lor\neg q\).
- \(\neg(p\lor q)\equiv\neg p\land\neg q\).
- \(p\to q\equiv\neg p\lor q\).
- \(\neg(p\to q)\equiv p\land\neg q\).
- A conditional is equivalent to its contrapositive, not generally to its converse.
- Equivalent subexpressions may be substituted inside larger formulas.
- Each transformation step should be justified by a valid equivalence law.
The central habit is to preserve truth behavior while changing form.
Where We Go Next
Logical equivalence provides a toolkit for replacing formulas with truth-preserving alternatives. The next step is to organize formulas into standardized structures that make their components and satisfying assignments easier to analyze.
The next lesson, Normal Forms, introduces systematic ways to write logical expressions using structured combinations of conjunctions, disjunctions, and literals.