Logical Equivalences and Validity

Unit 5: Introduction to Logic in AI — Section 5.3

You now know how to build propositional formulas. The next question is: how do we know when two different formulas mean the same thing, or when one formula’s truth guarantees another’s? These questions are at the heart of automated reasoning — an AI system that can identify equivalences and entailments can simplify its knowledge base and draw new conclusions automatically.

See how truth tables reveal the structure of logical formulas.

Truth Tables Explained

Learn how logical inference lets AI systems derive new knowledge from existing facts.

Logical Inference and Reasoning

Three Ways a Formula Can Behave

Every propositional formula falls into one of three categories based on its truth table.

Tautology

A tautology is a formula that is true under every possible truth assignment — no matter what values you give the variables, the formula comes out true.

Tautology: A propositional formula that is true in every possible truth assignment (every row of its truth table). Tautologies represent logical truths — statements that are necessarily true by the structure of logic alone, not because of any particular facts about the world. Example: P ∨ ¬P (the law of excluded middle).

P	¬P	P ∨ ¬P
T	F	T
F	T	T

¬P

P ∨ ¬P

P ∨ ¬P says "either P is true or P is not true." This is true regardless of the weather, the exam results, or any other fact. It is a logical law, not an empirical claim.

Contradiction

A contradiction is the opposite of a tautology — a formula that is false under every possible truth assignment.

Contradiction: A propositional formula that is false in every possible truth assignment. Contradictions are logically impossible — no state of the world can make them true. Example: P ∧ ¬P (a proposition cannot be both true and false simultaneously).

P	¬P	P ∧ ¬P
T	F	F
F	T	F

¬P

P ∧ ¬P

P ∧ ¬P says "P is both true and false." This is never possible. Finding a contradiction in a knowledge base is serious — it means the knowledge base contains inconsistent information, and from a contradiction, any conclusion can be "proved" (the principle of explosion).

Contingent Formula

A contingent formula is true under some truth assignments and false under others. Most real-world propositions are contingent — their truth depends on facts about the world.

Satisfiability: A formula is satisfiable if there exists at least one truth assignment that makes it true. Tautologies and contingent formulas are satisfiable; contradictions are not. Determining satisfiability (the SAT problem) is one of the most studied problems in computer science. AI planning and constraint satisfaction frequently reduce to SAT.

Logical Equivalence

Two formulas are logically equivalent if they have exactly the same truth value under every possible truth assignment — that is, if their truth tables are identical column-for-column.

Logical Equivalence (≡): Two formulas α and β are logically equivalent (written α ≡ β) when they have the same truth value in every possible truth assignment. Equivalent formulas can always substitute for each other without changing the meaning of a larger formula. Equivalences are the algebraic identities of logic.

The Core Equivalence Laws

The following equivalences hold for any propositions P, Q, and R. They are the toolkit for simplifying and transforming logical formulas.

Law	Formula	In Words
Double Negation	¬¬P ≡ P	Two negations cancel out
De Morgan’s (AND)	¬(P ∧ Q) ≡ ¬P ∨ ¬Q	Negate a conjunction: flip to disjunction, negate each part
De Morgan’s (OR)	¬(P ∨ Q) ≡ ¬P ∧ ¬Q	Negate a disjunction: flip to conjunction, negate each part
Commutativity (∧)	P ∧ Q ≡ Q ∧ P	Order does not matter for AND
Commutativity (∨)	P ∨ Q ≡ Q ∨ P	Order does not matter for OR
Associativity (∧)	(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)	Parentheses do not matter for AND
Associativity (∨)	(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)	Parentheses do not matter for OR
Distribution (∧ over ∨)	P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)	AND distributes over OR
Distribution (∨ over ∧)	P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)	OR distributes over AND
Implication Elimination	P → Q ≡ ¬P ∨ Q	A conditional rewrites as a disjunction
Contrapositive	P → Q ≡ ¬Q → ¬P	An implication is equivalent to its contrapositive

Law

Formula

In Words

Double Negation

¬¬P ≡ P

Two negations cancel out

De Morgan’s (AND)

¬(P ∧ Q) ≡ ¬P ∨ ¬Q

Negate a conjunction: flip to disjunction, negate each part

De Morgan’s (OR)

¬(P ∨ Q) ≡ ¬P ∧ ¬Q

Negate a disjunction: flip to conjunction, negate each part

Commutativity (∧)

P ∧ Q ≡ Q ∧ P

Order does not matter for AND

Commutativity (∨)

P ∨ Q ≡ Q ∨ P

Order does not matter for OR

Associativity (∧)

(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)

Parentheses do not matter for AND

Associativity (∨)

(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)

Parentheses do not matter for OR

Distribution (∧ over ∨)

P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

AND distributes over OR

Distribution (∨ over ∧)

P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

OR distributes over AND

Implication Elimination

P → Q ≡ ¬P ∨ Q

A conditional rewrites as a disjunction

Contrapositive

P → Q ≡ ¬Q → ¬P

An implication is equivalent to its contrapositive

Applying De Morgan’s Laws:

Suppose a security system stores the rule: "It is NOT the case that both the alarm is off and the door is open."

Formula: ¬(AlarmOff ∧ DoorOpen)

Applying De Morgan’s Law for AND:

¬AlarmOff ∨ ¬DoorOpen

This is equivalent: "Either the alarm is ON, or the door is CLOSED (or both)."

The two formulas mean exactly the same thing but the second may be easier to evaluate against two separate sensor readings.

Verifying Equivalence with Truth Tables

The most reliable way to check whether two formulas are equivalent is to build a truth table for both and compare the output columns.

Verifying the contrapositive: P → Q ≡ ¬Q → ¬P

P	Q	¬P	¬Q	P → Q	¬Q → ¬P
T	T	F	F	T	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

¬P

¬Q

P → Q

¬Q → ¬P

Columns 5 and 6 are identical — the formulas are logically equivalent.

This equivalence is practically important: if you know "If it rains, the ground is wet," you also know "If the ground is NOT wet, then it did NOT rain." The two statements carry exactly the same information.

Entailment

Logical equivalence asks whether two formulas always have the same truth value. Entailment asks a slightly different question: does the truth of one formula guarantee the truth of another?

Entailment (⊨): A set of formulas α entails a formula β (written α ⊨ β) when β is true in every truth assignment that makes α true. Equivalently, there is no possible world where α is true but β is false. Entailment formalizes the idea of "logical consequence" — β follows necessarily from α.

Valid entailments:

(P ∧ Q) ⊨ P — If P and Q are both true, then P must be true.
(P ∧ Q) ⊨ Q — Similarly for Q.
P ⊨ (P ∨ Q) — If P is true, then "P or Q" is certainly true.
(P → Q) ∧ P ⊨ Q — This is modus ponens (see below).
(P → Q) ∧ ¬Q ⊨ ¬P — This is modus tollens (see below).

Not entailments:

P ⊭ (P ∧ Q) — P alone does not guarantee Q.
(P ∨ Q) ⊭ P — Either-or does not guarantee the first disjunct.
(P → Q) ∧ Q ⊭ P — This is the fallacy of affirming the consequent.

Inference Rules

An inference rule is a pattern that lets us derive a new formula from existing formulas, guaranteed to preserve truth. Inference rules are the machinery that lets AI systems reason.

Modus Ponens

Modus ponens (Latin: "mode of affirming") is the most fundamental inference rule.

     P → Q      (if P then Q)
     P           (P is true)
     ──────
  ∴  Q           (therefore Q is true)

Modus Ponens: An inference rule that derives Q from the premises P → Q and P. If an implication holds and its antecedent is true, the consequent must be true. Modus ponens is the engine of forward-chaining expert systems: when all conditions of a rule are satisfied, the rule fires and its conclusion is added to the knowledge base.

Modus ponens in a medical system:

Rule stored in KB: Fever ∧ ElevatedWBC → BacterialInfection

Patient facts: Fever (temperature 39.2°C), ElevatedWBC (white blood cell count 15,000/µL)

Conjunction of facts: Fever ∧ ElevatedWBC

Applying modus ponens: conclude BacterialInfection — flag for antibiotic review.

The system derives a new fact it was never explicitly told.

Modus Tollens

Modus tollens (Latin: "mode of denying") reasons backwards from a false conclusion.

     P → Q      (if P then Q)
     ¬Q          (Q is false)
     ──────
  ∴  ¬P          (therefore P is false)

Modus Tollens: An inference rule that derives ¬P from the premises P → Q and ¬Q. If an implication holds and its consequent is false, the antecedent must also be false. Diagnostic systems use modus tollens to rule out causes: if the expected symptom is absent, the hypothesized condition is eliminated.

Resolution

Resolution is the inference rule used by automated theorem provers. It is more general than modus ponens and can be applied to disjunctions.

     P ∨ Q
     ¬P ∨ R
     ──────
  ∴  Q ∨ R

The shared variable P "resolves" out, leaving the combined conclusion Q ∨ R.

Resolution: An inference rule that combines two clauses sharing a complementary literal (P and ¬P) to produce a new clause containing the remaining literals. Resolution is complete for propositional logic — any valid conclusion can be derived using only resolution. It is the foundation of PROLOG and automated theorem provers like the Logic Theorist.

Common Logical Fallacies

Two common invalid argument patterns look similar to modus ponens and modus tollens but are not valid.

Affirming the Consequent (INVALID):

     P → Q      (If it rains, the ground is wet)
     Q           (The ground IS wet)
     ──────
  ✗  P           (INVALID: It rained?)

Wrong because Q could be true for other reasons (a sprinkler ran). Wet ground does not prove rain.

Denying the Antecedent (INVALID):

     P → Q      (If it rains, the ground is wet)
     ¬P          (It is NOT raining)
     ──────
  ✗  ¬Q          (INVALID: The ground is NOT wet?)

Wrong because the ground could still be wet from a sprinkler. The implication only tells us what happens when it rains — it says nothing about what happens when it does not.

Putting It Together: A Multi-Step Proof

Proving "I need my textbook" from three facts:

Given: . M → C: "If it is Monday, I have class." . M: "It is Monday." . C → T: "If I have class, I need my textbook."

Step 1 — Apply modus ponens to (1) and (2): * Premises: M → C, M * Conclusion: C ("I have class")

Step 2 — Apply modus ponens to (3) and the new fact C: * Premises: C → T, C * Conclusion: T ("I need my textbook")

We derived T from only M, even though no rule directly connected M to T. Chained inference is how AI systems navigate large knowledge bases.

Logical equivalences let AI systems rewrite formulas into simpler or more useful forms. Entailment defines what can be proven from a knowledge base. Inference rules — especially modus ponens and resolution — are the mechanical procedures that do the proving. Together, they are the foundation of all automated reasoning.

Test your understanding of tautologies, equivalences, and inference rules.

Next: 5.4 A Brief History of Logic in AI →

Adapted from forall x: Calgary by P.D. Magnus et al., licensed under CC BY 4.0.

This work is licensed under CC BY-SA 4.0.