Introduction to Logic

Lessons

Senior 4 · Mathematics

Introduction to Logic

5 lessons

Lesson 3 of 5

Logical equivalence and the laws of logic

25 min

Two notices, one rule

One gate says "No entry without a ticket". Another says "If you enter, you must have a ticket". Different words, the same rule. Logic can prove that two sentences always mean the same thing, and it gives a set of laws for rewriting a complicated condition as a simpler one. Programmers use the same laws to simplify the conditions in their code, and engineers to simplify circuits (Lesson 5).

Definition

Logically equivalent statements: compound statements $P$ and $Q$ are logically equivalent, written $P \equiv Q$ , if they have the same truth value in every row of their truth tables. Equivalently, $P \Leftrightarrow Q$ is a tautology.

Example: $p \Rightarrow q \equiv \neg p \vee q$ (Lesson 2, Worked example 4). We write $\mathbf{T}$ for any tautology and $\mathbf{F}$ for any contradiction.

The laws of logic

Each law below can be checked with a truth table. Notice that every law comes in a pair: swap $\wedge$ with $\vee$ and $\mathbf{T}$ with $\mathbf{F}$ and you get its partner.

Law	Form with $\wedge$	Form with $\vee$
Identity	$p \wedge \mathbf{T} \equiv p$	$p \vee \mathbf{F} \equiv p$
Domination	$p \wedge \mathbf{F} \equiv \mathbf{F}$	$p \vee \mathbf{T} \equiv \mathbf{T}$
Idempotent	$p \wedge p \equiv p$	$p \vee p \equiv p$
Negation (complement)	$p \wedge \neg p \equiv \mathbf{F}$	$p \vee \neg p \equiv \mathbf{T}$
Double negation	$\neg(\neg p) \equiv p$
Commutative	$p \wedge q \equiv q \wedge p$	$p \vee q \equiv q \vee p$
Associative	$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$	$(p \vee q) \vee r \equiv p \vee (q \vee r)$
Distributive	$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$	$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
De Morgan	$\neg(p \wedge q) \equiv \neg p \vee \neg q$	$\neg(p \vee q) \equiv \neg p \wedge \neg q$
Absorption	$p \wedge (p \vee q) \equiv p$	$p \vee (p \wedge q) \equiv p$
Conditional	$p \Rightarrow q \equiv \neg p \vee q \equiv \neg q \Rightarrow \neg p$
Biconditional	$p \Leftrightarrow q \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)$

Worked example 1: proving De Morgan's law with a truth table

Show that $\neg(p \wedge q) \equiv \neg p \vee \neg q$ .

$p$	$q$	$p \wedge q$	$\neg(p \wedge q)$	$\neg p$	$\neg q$	$\neg p \vee \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 fourth and seventh columns are identical, so the statements are equivalent. The diagram shows the same fact: the cases where " $p$ and $q$ " fails are exactly those outside $P$ or outside $Q$ .

Augustus De Morgan (1806–1871), best known for the laws relating conjunction, disjunction and negation that carry his name; his logic is now used in set theory, probability and computer science. Portrait from the 1882 memoir by Sophia Elizabeth De Morgan, public domain, via Wikimedia Commons.

Worked example 2: negating in words

Write the negation of each statement without starting "It is not true that". (a) The shop is open and the price is fair. (b) $x \gt 2$ or $x \lt -2$ . (c) If it is Saturday, the office is closed.

Solution

De Morgan: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ . "The shop is closed or the price is not fair."
$\neg(p \vee q) \equiv \neg p \wedge \neg q$ : " $x \le 2$ and $x \ge -2$ ", that is, $-2 \le x \le 2$ .
$\neg(p \Rightarrow q) \equiv \neg(\neg p \vee q) \equiv p \wedge \neg q$ : "It is Saturday and the office is open." The negation of a conditional is not another conditional.

Worked example 3: simplifying with the laws

Simplify $\neg(p \vee \neg q) \vee (\neg p \wedge \neg q)$ .

Solution Name one law at each step.

\begin{aligned} \neg(p \vee \neg q) \vee (\neg p \wedge \neg q) &\equiv (\neg p \wedge \neg\neg q) \vee (\neg p \wedge \neg q) && \text{De Morgan} \\ &\equiv (\neg p \wedge q) \vee (\neg p \wedge \neg q) && \text{double negation} \\ &\equiv \neg p \wedge (q \vee \neg q) && \text{distributive} \\ &\equiv \neg p \wedge \mathbf{T} && \text{negation} \\ &\equiv \neg p && \text{identity} \end{aligned}

Worked example 4: proving an equivalence without a truth table

Show that $(p \Rightarrow q) \wedge (p \Rightarrow r) \equiv p \Rightarrow (q \wedge r)$ .

Solution

\begin{aligned} (p \Rightarrow q) \wedge (p \Rightarrow r) &\equiv (\neg p \vee q) \wedge (\neg p \vee r) && \text{conditional law} \\ &\equiv \neg p \vee (q \wedge r) && \text{distributive} \\ &\equiv p \Rightarrow (q \wedge r) && \text{conditional law} \end{aligned}

In words: "if $p$ then $q$ , and if $p$ then $r$ " says the same as "if $p$ then both $q$ and $r$ ". With three statements a truth table would need 8 rows; the laws need three lines.

Warning

The conditional is not associative. $(p \Rightarrow q) \Rightarrow r$ and $p \Rightarrow (q \Rightarrow r)$ are different: with $p$ false, $q$ true and $r$ false, the first is $\mathrm{T} \Rightarrow \mathrm{F}$ , which is F, while the second is $\mathrm{F} \Rightarrow (\ldots)$ , which is T. Always keep the brackets around a conditional.

Tip

To simplify, first remove every $\Rightarrow$ and $\Leftrightarrow$ with the conditional and biconditional laws, then push each $\neg$ inside with De Morgan until it sits on a single letter, and only then look for distributive, negation and absorption steps.

Dr. Trefor Bazett: 3 Ways to Show a Logical Equivalence, with De Morgan's laws as the example. Watch for the truth-table method and the method of applying known laws step by step.

✦

Practice

Name the law you use at each step.

Prove with a truth table that $\neg(p \vee q) \equiv \neg p \wedge \neg q$ .
Write the negation in words: (a) The road is wet and the sky is clear. (b) The number is even or it is negative.
Write the negation of "If a triangle has a right angle, then it is isosceles" (for a particular triangle).
Use the laws to show that $p \Rightarrow q \equiv \neg q \Rightarrow \neg p$ .
Simplify $\neg(\neg p \wedge q) \wedge (p \vee q)$ .
Simplify $p \vee (p \wedge q)$ and $p \wedge (\neg p \vee q)$ .
Show that $p \Leftrightarrow q \equiv (p \wedge q) \vee (\neg p \wedge \neg q)$ .
Is $\neg(p \Leftrightarrow q)$ equivalent to $p \veebar q$ ? Justify.

Show answersHide answers

Both columns are F, F, F, T.
(a) The road is dry or the sky is not clear. (b) The number is odd and it is not negative.
The triangle has a right angle and it is not isosceles.
$p \Rightarrow q \equiv \neg p \vee q \equiv q \vee \neg p$ (commutative) $\equiv \neg(\neg q) \vee \neg p$ (double negation) $\equiv \neg q \Rightarrow \neg p$ (conditional law).
De Morgan and double negation give $(p \vee \neg q) \wedge (p \vee q)$ ; distributive: $p \vee (\neg q \wedge q)$ ; negation: $p \vee \mathbf{F}$ ; identity: $p$ .
$p$ (absorption). $(p \wedge \neg p) \vee (p \wedge q) \equiv \mathbf{F} \vee (p \wedge q) \equiv p \wedge q$ .
Both have truth table T, F, F, T.
Yes: $p \Leftrightarrow q$ is T, F, F, T, so its negation is F, T, T, F, which is the table of $p \veebar q$ .

Quick check

Which statement is logically equivalent to ¬(p ∧ q)?

Key points

$P \equiv Q$ when they agree in every row, i.e. $P \Leftrightarrow Q$ is a tautology.
De Morgan: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$ .
$p \Rightarrow q \equiv \neg p \vee q$ , so $\neg(p \Rightarrow q) \equiv p \wedge \neg q$ .
Simplify step by step, naming one law per step.

Sources and credits

Written by Ganzaa: the explanations, the diagram, the tables, the worked examples, the practice items and the questions.
De Morgan's dates and work: Augustus De Morgan, Wikipedia contributors, Wikipedia, CC BY-SA 4.0, adapted by Ganzaa.
Portrait: De Morgan Augustus, from Sophia Elizabeth De Morgan's memoir (1882), Wikimedia Commons, public domain.
Video: 3 Ways to Show a Logical Equivalence: Ex: DeMorgan's Laws, Dr. Trefor Bazett, embedded from YouTube.
This lesson adapts CC BY-SA material and is shared under CC BY-SA 4.0.

1Two notices, one rule

2The laws of logic

Two notices, one rule

The laws of logic