Logical Equivalence Revisited

Background

We can build new propositions from the given ones using logical operations like conjunction, disjunction, and negation. The combination of these operations can provide us with new propositions. When using different operations, other than precedence, we must keep the following properties in mind to get the desired effect and be logically correct.

• Conjunction and disjunction operations are both commutative and associative.
• Distributive law does not hold for negation over conjunction or disjunction, instead, we use DeMorgan’s laws.
• Implication operation is neither commutative nor associative.
• Bi-implication operation is both commutative and associative.

Implication and equivalence

Take $p$ and $q$ as two arbitrary propositions and make $q_1$ as:

$$q_1 = p \Rightarrow q.$$

We can derive more implications as follows:

• $q_2 =\text{Converse}\left(q_1\right) := q \Rightarrow p.$

• $q_3 = \text{Inverse}\left(q_1\right) := \neg p \Rightarrow \neg q.$

• $q_4 = \text{Contrapositive}\left(q_1\right) := \neg q \Rightarrow \neg p.$

Note: The $:=$ symbol used above means “defined as” or “is by definition equal to.”

Let’s look at the truth table of $q_1, q_2, q_3,$ and $q_4$ to see if any of them are equivalent.

$p$	$q$	$p \Rightarrow q$	$q \Rightarrow p$	$\neg p \Rightarrow \neg q$	$\neg q \Rightarrow \neg p$
T	T	T	T	T	T
T	F	F	T	T	F
F	T	T	F	F	T
F	F	T	T	T	T

From the truth table above, we can observe that,

• $p \Rightarrow q \equiv \neg q \Rightarrow \neg p.$

• $q \Rightarrow p \equiv \neg p \Rightarrow \neg q.$

We can also look at it as follows:

• $q_1 \equiv \text{Contrapositive}\left(q_1\right)$.

• $\text{Converse}\left(q_1\right)\equiv\text{Inverse}\left(q_1\right)$.

• $\text{Inverse}\left(q_1\right)\equiv\text{Contrapositive}\left(\text{Converse}\left(q_1\right)\right)$.

• $\text{Inverse}\left(q_1\right)\equiv\text{Converse}\left(\text{Contrapositive}\left(q_1\right)\right)$.

Replacement of implication operation

We can express the logical equivalence of a proposition containing implication operation with a proposition that does not have implication operation.

$$q_1 = p\Rightarrow q \equiv \neg p \lor q.$$

If we look closely, when $p$ is false, $q_1$ is true, making it equivalent to $\neg p$. When $p$ is true ($\neg p$ is false), the truth value of $q_1$ is equivalent to the truth value of $q$. We can also verify this equivalence using the following truth table.

$p$	$q$	$p \Rightarrow q$	$\neg p \lor q$
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

We have,

$$q_1 = p \Rightarrow q.$$

$$q_1 \equiv \neg q \Rightarrow \neg p$$

and

$$q_1 \equiv \neg p \lor q.$$

As $q_1$ is equivalent to two different propositions, they must be equivalent to each other.

$$\neg q \Rightarrow \neg p \equiv \neg p \lor q.$$

We can also look at it as follows:

$$\neg q \Rightarrow \neg p \equiv \neg\left(\neg q\right) \lor \neg p \equiv \neg p \lor q.$$

Bi-implication and equivalence

If bi-implication is true, we can conclude that both operands are logically equivalent.

This way, the bi-implication allows us to establish that two propositions are equivalent. If we want to prove that,

$$q_1 \equiv q_2,$$

we can achieve it by showing that,

• $q_1 \Rightarrow q_2$ is true,

and

• $q_2 \Rightarrow q_1$ is also true,

therefore establishing that,

• $q_1 \Leftrightarrow q_2$ is true.

So, we can say that if $q_1$ and $q_2$ are logically equivalent, then $q_1 \Leftrightarrow q_2$ is true. If $q_1 \nLeftrightarrow q_2$, then $q_1$ and $q_2$ are not logically equivalent. Further, if $q_1 \nLeftrightarrow q_2$, then either $q_1 \nRightarrow q_2$ or $q_2 \nRightarrow q_1.$

Replacement of bi-implication operation

We can replace implication operation using the following equivalence.

$$p\Rightarrow q \equiv \neg p \lor q.$$

We have the following equivalence for bi-implication.

$$p \Leftrightarrow q \equiv (p\Rightarrow q) \land \left(q \Rightarrow p\right).$$

Using both of these equivalences, we can develop the following replacement of bi-implication without using implication operation.

$$p \Leftrightarrow q \equiv \left(\neg p \lor q\right) \land \left(\neg q \lor p\right).$$

Further, we can verify this equivalence by the following truth table:

$\left(p, q\right)$	$p \Leftrightarrow q$	$\neg p \lor q$	$\neg q \lor p$	$\left(\neg p \lor q\right) \land \left(\neg q \lor p\right)$
(T, T)	T	T	T	T
(T, F)	F	F	T	F
(F, T)	F	T	F	F
(F, F)	T	T	T	T

We can compare the third and last columns to observe the desired equivalence.

Negation of implication and bi-implication

When we negate the implication, we get a new equivalence. For arbitrary propositions $p$ and $q$, we have,

$$p\Rightarrow q \equiv \neg p \lor q.$$

apply negation on both sides,

$$\neg\left(p\Rightarrow q\right) \equiv \neg\left(\neg p \lor q\right).$$

Use DeMorgan’s law on the right-hand side to get the following equivalence:

$$\neg\left(p\Rightarrow q\right) \equiv p \land \neg q.$$

Similarly, we can apply negation on bi-implication. For arbitrary propositions $p$ and $q$, we have,

$$p \Leftrightarrow q \equiv \left(\neg p \lor q\right) \land \left(\neg q \lor p\right).$$

By applying negation on both sides, we get,

$$\neg\left(p \Leftrightarrow q\right) \equiv \neg\left(\left(\neg p \lor q\right) \land \left(\neg q \lor p\right)\right).$$

Use DeMorgan’s law to distribute negation operation on the right-hand side.

$$\neg\left(p \Leftrightarrow q\right) \equiv \neg\left(\neg p \lor q\right) \lor \neg\left(\neg q \lor p\right).$$

We can use DeMorgan’s law again to simplify the right-hand side further.

$$\neg\left(p \Leftrightarrow q\right) \equiv \left(p \land \neg q\right) \lor \left(q \land \neg p\right).$$

We know, the exclusive disjunction ($\oplus$) is only true when both operands have different truth values. Look at the following truth table for an exciting equivalence relation.

$p$	$q$	$p \Leftrightarrow q$	$\neg\left(p \Leftrightarrow q\right)$	$p \oplus q$
T	T	T	F	F
T	F	F	T	T
F	T	F	T	T
F	F	T	F	F

By observing the last two columns, we have,

$$\neg\left(p \Leftrightarrow q\right) \equiv p \oplus q.$$

Therefore, we also have,

$$p \oplus q \equiv \left(p \land \neg q\right) \lor \left(q \land \neg p\right).$$

Examples

Let’s look at a few examples to explore the logical equivalence.

---

Consider:

• $P_E$: Peter is eighteen years old.
• $P_D$: Peter has permission to drive a car.

---

Now,

• $I_P = P_E \Rightarrow P_D.$
• $I_P$: If Peter is eighteen years old, then he has permission to drive a car.

And,

• $F_P = \neg P_E \lor P_D.$
• $F_P$: Peter is not eighteen years old, or he has permission to drive a car.

As,

• $I_P \equiv F_P.$

Because,

• $P_E \Rightarrow P_D \equiv \neg P_E \lor P_D.$

Hence, it is logically equivalent to say either, “If Peter is eighteen years old, then he has permission to drive a car,” or to say, “Peter is not eighteen years old, or he has permission to drive a car.”

For the second example, Murphy is shown in the figure.

We have,

• $I_{mh}=m_{h}\Rightarrow m_{l}$: If Murphy is a pet horse, then Murphy has four legs.
• $I_{md}= m_{d}\Rightarrow m_{l}$: If Murphy is a pet dog, then Murphy has four legs.

Now,

• $C_{mh}=\text{Converse}\left(I_{mh}\right)$ $=m_{l}\Rightarrow m_{h}.$

• $C_{mh}$: If Murphy has four legs, then Murphy is a pet horse.

• $C_{md}$: If Murphy has four legs, then Murphy is a pet dog.

• $B_{mh}=m_{h}\Leftrightarrow m_{l}$: Murphy is a pet horse, if and only if Murphy has four legs.

• $B_{md}=m_{d}\Leftrightarrow m_{l}$: Murphy is a pet dog, if and only if Murphy has four legs.

Proposition	Statement	Equivalent Statement	Truth value
$I_{mh}$	If Murphy is a pet horse, then Murphy has four legs.	Murphy is not a pet horse, or it has four legs.	T
$C_{mh}$	If Murphy has four legs, then it is a pet horse.	Murphy does not have four legs, or Murphy is a pet horse.	F
$B_{mh}$	Murphy is a pet horse, if and only if Murphy has four legs.	Murphy is a pet horse, and it has four legs, OR, Murphy is not a pet horse, and it does not have four legs.	F
$I_{md}$	If Murphy is a pet dog, then Murphy has four legs.	Murphy is not a pet dog, or it has four legs.	T
$C_{md}$	If Murphy has four legs, then Murphy is a pet dog.	Murphy does not have four legs, or it is a pet dog.	T
$B_{md}$	Murphy is a pet dog, if and only if Murphy has four legs.	Murphy is a pet dog, and it has four legs, OR, Murphy is not a pet dog, and it does not have four legs.	T