Propositional Equivalences
Quick Reference
| Field | Value |
|---|---|
| Textbook | Rosen, Discrete Mathematics and Its Applications, 8th edition |
| Chapter | 1 (The Foundations: Logic and Proofs) |
| Section | 1.3 Propositional Equivalences |
| Subsection | 1.3.1 Introduction (tautology, contradiction, contingency); 1.3.2 Logical Equivalences; 1.3.3 Using De Morgan’s Laws; 1.3.5 Propositional Satisfiability |
| Pages | 26-39 |
| Course | MATH301 (Discrete Mathematics), Week 1 |
A professor pulling this up before lecture has the exact section, subsection, and page range; a student studying for a quiz has the same anchor. Every definition below is quoted from Section 1.3 with its page.
Try This First
Before any rules or tables, take two sentences and check whether they say the same thing.
Sentence A: “It is not the case that the bridge is open and the train is running.”
Sentence B: “The bridge is not open, or the train is not running.”
Imagine the four ways the world could be (bridge open or not, train running or not). For each one, decide whether A is true and whether B is true. Then check yourself.
Check your four cases
Let $p$ stand for “the bridge is open” and $q$ for “the train is running.”
| $p$ | $q$ | A: $\neg(p \wedge q)$ | B: $\neg p \vee \neg q$ |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | T | T |
| F | F | T | T |
The two columns agree in every row. The sentences are true in exactly the same situations and false in exactly the same situations. They are different strings of words, yet they carry identical truth content. That is what it means for two compound propositions to be logically equivalent, and the pair you just checked is one of De Morgan’s Laws.
You have already done the central work of this section: build a truth table for two compound propositions and compare them column for column. The rest of this page makes that idea precise, names the standard equivalences, and shows how to chain them without a table.
What Equivalence Means, in Plain Words
Two compound propositions are logically equivalent when they always have the same truth value, no matter what the underlying propositional variables are set to. The two propositions may look nothing alike as strings of symbols. What matters is the function each one computes from inputs (the truth values of its variables) to an output (true or false). If two compound propositions compute the same truth-value output for every input, they are equivalent.
A short way to remember the test: line up the two final truth-table columns. If the columns match in every row, the propositions are equivalent. If even one row differs, they are not.
Prerequisite Hub
Propositional equivalences come immediately after the connectives and translation are in place.
Builds on
| Skill | Why this node needs it |
|---|---|
dm-propositional-logic |
Equivalence is defined through the biconditional $p \leftrightarrow q$ and the truth tables of the connectives $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$. |
dm-applications-of-propositional-logic |
Translating English into compound propositions is what makes an equivalence such as De Morgan’s Law useful in practice. |
Unlocks
| Skill | Why it needs this node |
|---|---|
dm-predicates-and-quantifiers |
The quantifier negation rules (“not all” becomes “some not”) are the De Morgan pattern carried over from propositions to predicates. |
dm-rules-of-inference |
Valid arguments are built by replacing a premise with a logically equivalent one and by applying equivalences such as contrapositive. |
Cross-course prerequisites
None. This node has no dependency on another course.
Official Definitions
The definitions below are quoted from the textbook. Read the property each one fixes, not just the words.
Tautology, contradiction, contingency. A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.
Cite: Rosen 8e, Section 1.3, Definition 1, p.27 (verbatim).
Logical equivalence. The compound propositions $p$ and $q$ are called logically equivalent if $p \leftrightarrow q$ is a tautology. The notation $p \equiv q$ denotes that $p$ and $q$ are logically equivalent.
Cite: Rosen 8e, Section 1.3, Definition 2, p.28 (verbatim).
The symbol $\equiv$ is not one of the connectives $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$. It is a claim about two propositions: that the biconditional joining them is true under every assignment. A clean restatement: $p \equiv q$ exactly when $p$ and $q$ have the same truth value in every row of their shared truth table.
Satisfiable, unsatisfiable. A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignment exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable.
Cite: Rosen 8e, Section 1.3, subsection 1.3.5 Propositional Satisfiability, p.35.
These three ideas line up. A tautology is satisfiable in every row. A contradiction is unsatisfiable, false in every row. A contingency is satisfiable but not a tautology, true in some rows and false in others.
Key Theorem
De Morgan’s Laws (for propositions). $\neg(p \wedge q)$ is logically equivalent to $(\neg p) \vee (\neg q)$, and $\neg(p \vee q)$ is logically equivalent to $(\neg p) \wedge (\neg q)$. In symbols, $$\neg(p \wedge q) \equiv \neg p \vee \neg q, \qquad \neg(p \vee q) \equiv \neg p \wedge \neg q.$$
Cite: Rosen 8e, Section 1.3, Table 6 (Logical Equivalences) and De Morgan’s Laws discussion, p.27-28.
In words, negation turns “and” into “or” and turns “or” into “and,” while flipping each part. This is the rule you verified by hand in the opener.
A Working List of Equivalences
Section 1.3 collects the standard equivalences in Table 6. The ones below are the most heavily used. Each can be confirmed by a truth table; later examples chain them without one.
| Name | Equivalence |
|---|---|
| Identity | $p \wedge \mathbf{T} \equiv p$, and $p \vee \mathbf{F} \equiv p$ |
| Domination | $p \vee \mathbf{T} \equiv \mathbf{T}$, and $p \wedge \mathbf{F} \equiv \mathbf{F}$ |
| Double negation | $\neg(\neg p) \equiv p$ |
| De Morgan | $\neg(p \wedge q) \equiv \neg p \vee \neg q$, and $\neg(p \vee q) \equiv \neg p \wedge \neg q$ |
| Distributive | $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ |
| Conditional rewrite | $p \rightarrow q \equiv \neg p \vee q$ |
| Contrapositive | $p \rightarrow q \equiv \neg q \rightarrow \neg p$ |
Two representations sit side by side here. The conditional rewrite $p \rightarrow q \equiv \neg p \vee q$ is the bridge between the arrow connective and the and-or-not connectives; it lets you carry every “if-then” into a form that De Morgan’s Laws can act on. Translate $p \rightarrow q$ into $\neg p \vee q$ and back a few times until the move feels automatic.
Worked Examples
Each example states a goal, predicts the shape of the answer, carries out the work, then compares the result to the prediction.
Example 1: Confirm an equivalence by truth table
Goal. Show that $p \rightarrow q \equiv \neg p \vee q$.
Predict. Both expressions are built from the same two variables, so each has four rows. A conditional is false only when its hypothesis is true and its conclusion is false. The prediction is that the two final columns match in all four rows.
Work. Build the columns side by side.
| $p$ | $q$ | $\neg p$ | $p \rightarrow q$ | $\neg p \vee q$ |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Compare. The column for $p \rightarrow q$ and the column for $\neg p \vee q$ agree in every row. By Definition 2 the biconditional joining them is a tautology, so $p \rightarrow q \equiv \neg p \vee q$. The prediction held: the only false row is $p$ true, $q$ false.
Example 2: Classify a proposition
Goal. Decide whether $(p \rightarrow q) \vee (q \rightarrow p)$ is a tautology, a contradiction, or a contingency.
Predict. A disjunction is false only when both parts are false. For both conditionals to fail at once would need $p$ true with $q$ false (so the first fails) and $q$ true with $p$ false (so the second fails) in the same row, which cannot happen. The prediction is a tautology.
Work. Tabulate the two conditionals and their disjunction.
| $p$ | $q$ | $p \rightarrow q$ | $q \rightarrow p$ | $(p \rightarrow q) \vee (q \rightarrow p)$ |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | T |
| F | T | T | F | T |
| F | F | T | T | T |
Compare. The final column is true in every row, so the proposition is a tautology. The prediction held: in no row do both conditionals fail together.
Example 3: Simplify with the equivalence laws (no table)
Goal. Show that $\neg(p \rightarrow q) \equiv p \wedge \neg q$ using the laws, not a truth table.
Predict. A conditional fails exactly when the hypothesis holds and the conclusion fails. The negation of “if $p$ then $q$” should therefore mean “$p$ and not $q$.” The prediction is that the chain lands on $p \wedge \neg q$.
Work. Apply one law per step.
$$ \begin{aligned} \neg(p \rightarrow q) &\equiv \neg(\neg p \vee q) && \text{conditional rewrite } p \rightarrow q \equiv \neg p \vee q \\ &\equiv \neg(\neg p) \wedge \neg q && \text{De Morgan} \\ &\equiv p \wedge \neg q && \text{double negation } \neg(\neg p) \equiv p \end{aligned} $$
Compare. The chain produces $p \wedge \neg q$, exactly the prediction. Each step replaced a subexpression with a logically equivalent one, so the whole chain is a sequence of equivalences and the endpoints are equivalent.
Example 4: Test for satisfiability
Goal. Decide whether $(p \vee q) \wedge (\neg p) \wedge (\neg q)$ is satisfiable.
Predict. The proposition demands $p$ false and $q$ false (from the last two parts), yet also $p \vee q$ true (from the first part). With both variables false, $p \vee q$ is false. The prediction is that no assignment works, so the proposition is unsatisfiable.
Work. A row makes the whole conjunction true only if every part is true. The part $\neg p$ forces $p$ false; the part $\neg q$ forces $q$ false. Substitute into the remaining part: $p \vee q$ becomes $\mathbf{F} \vee \mathbf{F} = \mathbf{F}$. So the first part is false in the only row that satisfies the other two, and the conjunction is false there. Every other row already fails $\neg p$ or $\neg q$.
Compare. No assignment of truth values makes the proposition true, so it is unsatisfiable, which is the same as saying it is a contradiction. The prediction held.
Common Misconceptions
logical equivalence means the two propositions are written with the same symbols. Equivalence is about truth values across every row, not about matching strings. The propositions $p \rightarrow q$ and $\neg p \vee q$ share no connective in common, yet Example 1 shows their truth-table columns agree in all four rows, so they are equivalent. The reverse trap also appears: two propositions can use the very same variables and connectives in a different arrangement and fail to be equivalent. The only reliable test is to compare the final columns, never to compare appearances.
a conditional is equivalent to its converse. The converse of $p \rightarrow q$ is $q \rightarrow p$, and these are not equivalent. Check the row $p$ true, $q$ false: here $p \rightarrow q$ is false while $q \rightarrow p$ is true, so a single row breaks the claim. What is equivalent to $p \rightarrow q$ is its contrapositive $\neg q \rightarrow \neg p$, which agrees with the original in all four rows. Keeping converse and contrapositive apart is one of the most useful habits to build.
Practice Problems
Decide whether each compound proposition is a tautology, a contradiction, or a contingency: (a) $p \vee \neg p$, (b) $p \wedge \neg p$, (c) $p \rightarrow q$.
Write a proposition logically equivalent to $\neg(p \vee \neg q)$ that has no negation applied to a parenthesized group.
Use a truth table to decide whether $p \rightarrow (q \vee r)$ is logically equivalent to $(p \rightarrow q) \vee (p \rightarrow r)$.
A classmate says: “Since $p \rightarrow q$ and $q \rightarrow p$ are both conditionals built from $p$ and $q$, they must be logically equivalent.” Decide whether the claim is correct. If it is wrong, give a single row that breaks it, and state which proposition actually is equivalent to $p \rightarrow q$.
(a) Using the equivalence laws (no truth table), simplify $\neg(\neg p \wedge q) \wedge p$ to a single variable.
(b) Decide whether $(p \rightarrow q) \wedge p \wedge \neg q$ is satisfiable, and justify the answer.
Mastery Checklist
Novice (Level 1-2):
Competent (Level 3-4):
Proficient (Level 5):
Mental Model
Picture each compound proposition as a small machine. The inputs are the truth values of its variables; the output is a single light that is on (true) or off (false). Two machines are logically equivalent when they have the same wiring behavior: feed them the same inputs and their lights always agree, row by row, even if the machines are built from different parts inside. A truth table is the full record of one machine’s behavior across every input. The equivalence laws are shortcuts that let you rebuild a machine into a simpler one whose light never disagrees with the original.
Connections
Looking back:
- Propositional logic supplies the connectives and the biconditional that the definition of equivalence rests on.
- Applications of propositional logic turns English sentences into the compound propositions that these equivalences simplify.
Looking ahead:
- Predicates and quantifiers extends De Morgan’s pattern to quantifiers: the negation of “for all” is “there exists not.”
- Rules of inference builds valid arguments by replacing premises with logically equivalent forms.
Real-world connections:
- A search filter that asks for “not (in stock and on sale)” returns the same results as “out of stock or not on sale,” which is De Morgan’s Law applied to a query.
- A circuit that computes $\neg(p \wedge q)$ can be rebuilt as $\neg p \vee \neg q$ with the same output for every input, a fact hardware designers use to swap gate types.
Resources
- Textbook (primary): Rosen, Discrete Mathematics and Its Applications, 8th edition, Section 1.3 Propositional Equivalences, pages 26-39, including Table 6 (Logical Equivalences). This is the source of every definition and the De Morgan statement on this page.
- Open companion: Levin, Discrete Mathematics: An Open Introduction, the Logic chapter on propositional equivalences and De Morgan’s Laws, free online: https://discrete.openmathbooks.org/dmoi3/sec_propositional.html
- Next node in the tree: Predicates and Quantifiers (
dm-predicates-and-quantifiers), the Section 1.4 node this section unlocks.
| Previous | Up | Next |
|---|---|---|
| Applications of Propositional Logic | Skills Index | Predicates and Quantifiers |
Last updated: 2026-06-16