Algebra of Propositions and Logical Equivalences

In propositional logic, compound propositions are formed by combining simpler propositions using logical operators such as AND, OR, NOT, implication, and biconditional.

Just as ordinary algebra has laws for simplifying numerical expressions, propositional logic has a collection of logical equivalence laws that allow us to simplify and transform logical expressions without changing their truth values.

These laws are collectively called the algebra of propositions.

---

1. Logical Equivalence

Two propositions are said to be logically equivalent if they have the same truth value for every possible combination of truth values of their variables.

If propositions $P$ and $Q$ are logically equivalent, we write:

$$P \equiv Q$$

For example,

$$p \to q \equiv \neg p \lor q$$

This means that $p \to q$ and $\neg p \lor q$ always produce exactly the same truth value.

Logical equivalences are extremely useful because they allow complicated logical expressions to be rewritten in simpler forms.

---

2. Basic Laws of Propositional Algebra

Let $p$, $q$, and $r$ be propositions.

Let:

• $T$ represent True
• $F$ represent False
• $\neg$ represent NOT
• $\land$ represent AND
• $\lor$ represent OR

The following laws are fundamental.

---

Identity Laws

$$p \land T \equiv p$$ $$p \lor F \equiv p$$

These are called identity laws because combining a proposition with the appropriate identity value does not change it.

Intuition

For AND:

• $p$ AND True depends entirely on $p$.

Therefore,

$$p \land T = p$$

For OR:

• $p$ OR False also depends entirely on $p$.

Therefore,

$$p \lor F = p$$

---

Domination Laws

$$p \lor T \equiv T$$ $$p \land F \equiv F$$

Here, one truth value completely determines the result.

If one operand of OR is True, the entire expression must be True:

$$p \lor T \equiv T$$

Similarly, if one operand of AND is False, the entire expression must be False:

$$p \land F \equiv F$$

---

Idempotent Laws

$$p \lor p \equiv p$$ $$p \land p \equiv p$$

Repeating the same proposition does not change its truth value.

For example, saying

"It is raining OR it is raining"

has exactly the same logical meaning as simply saying

"It is raining."

---

Double Negation Law

$$\neg(\neg p) \equiv p$$

Negating a proposition twice gives the original proposition.

If $p$ means:

It is raining.

then $\neg p$ means:

It is not raining.

and $\neg(\neg p)$ again means:

It is raining.

Therefore,

$$\neg\neg p \equiv p$$

---

3. Commutative Laws

$$p \lor q \equiv q \lor p$$ $$p \land q \equiv q \land p$$

The order of propositions does not matter when using AND or OR.

For example,

$$p \land q$$

has the same truth value as

$$q \land p$$

This is similar to ordinary arithmetic:

$$a+b=b+a$$

---

4. Associative Laws

$$(p \lor q)\lor r \equiv p\lor(q\lor r)$$ $$(p\land q)\land r \equiv p\land(q\land r)$$

When the same logical operator is used repeatedly, changing the grouping does not change the result.

Therefore, we can often simply write

$$p\lor q\lor r$$

or

$$p\land q\land r$$

without worrying about the grouping.

---

5. Distributive Laws

Logical operators can distribute over one another.

OR distributed over AND

$$p\lor(q\land r) \equiv (p\lor q)\land(p\lor r)$$

AND distributed over OR

$$p\land(q\lor r) \equiv (p\land q)\lor(p\land r)$$

Notice something interesting here.

In ordinary algebra, multiplication distributes over addition. In propositional logic, however, both AND and OR have distributive forms.

---

6. De Morgan's Laws

De Morgan's laws describe what happens when a negation is applied to an AND or OR expression.

$$\neg(p\land q) \equiv \neg p\lor\neg q$$

and

$$\neg(p\lor q) \equiv \neg p\land\neg q$$

A useful way to remember De Morgan's laws is:

Negate each proposition and switch the operator.

Thus,

$$\land \quad \longleftrightarrow \quad \lor$$

For example,

$$\neg(p\land q)$$

becomes

$$\neg p\lor\neg q$$

while

$$\neg(p\lor q)$$

becomes

$$\neg p\land\neg q$$

---

7. Absorption Laws

$$p\lor(p\land q)\equiv p$$ $$p\land(p\lor q)\equiv p$$

These are called absorption laws because the larger expression containing $q$ is effectively absorbed by $p$.

For example,

$$p\lor(p\land q)$$

can only be true when $p$ is true, so the expression behaves exactly like $p$.

---

8. Negation Laws

$$p\lor\neg p\equiv T$$ $$p\land\neg p\equiv F$$

A proposition must either be true or false. Therefore,

$$p\lor\neg p$$

is always true.

This is known as the Law of Excluded Middle.

On the other hand,

$$p\land\neg p$$

can never be true because a proposition and its negation cannot simultaneously be true.

This is the Law of Contradiction.

---

9. Summary of the Basic Equivalence Laws

---

10. Principle of Duality

An important feature of propositional algebra is that most laws occur in dual pairs.

The dual of a logical expression is obtained by simultaneously replacing:

$$T \leftrightarrow F$$

and

$$\land \leftrightarrow \lor$$

Variables and negations remain unchanged.

For example, consider the identity law:

$$p\land T\equiv p$$

Replace $\land$ with $\lor$ and $T$ with $F$:

$$p\lor F\equiv p$$

Therefore, these two identity laws form a dual pair.

Similarly,

$$p\lor T\equiv T$$

has the dual

$$p\land F\equiv F$$

The double-negation law,

$$\neg(\neg p)\equiv p$$

does not contain $\land$, $\lor$, $T$, or $F$, so it is self-dual under these replacements.

---

11. Logical Equivalences Involving Implication

Recall that

$$p\to q$$

means:

If $p$ is true, then $q$ is true.

Implication can be rewritten using NOT and OR.

Fundamental Implication Law

$$p\to q\equiv\neg p\lor q$$

This is one of the most important equivalences in propositional logic.

It allows us to completely eliminate the implication operator.

---

Contrapositive

$$p\to q\equiv\neg q\to\neg p$$

The proposition

$$\neg q\to\neg p$$

is called the contrapositive of $p\to q$.

A conditional statement and its contrapositive are logically equivalent.

---

OR Using Implication

$$p\lor q\equiv\neg p\to q$$

Using the implication law,

$$\neg p\to q$$

becomes

$$\neg(\neg p)\lor q$$

and by double negation,

$$p\lor q$$

Hence,

$$p\lor q\equiv\neg p\to q$$

---

AND Using Implication

$$p\land q\equiv\neg(p\to\neg q)$$

Because

$$p\to\neg q \equiv \neg p\lor\neg q$$

negating both sides gives

$$\neg(\neg p\lor\neg q)$$

Applying De Morgan's law,

$$p\land q$$

Therefore,

$$p\land q\equiv\neg(p\to\neg q)$$

---

Negation of an Implication

A particularly important equivalence is

$$\neg(p\to q) \equiv p\land\neg q$$

Why?

Because $p\to q$ is false in exactly one situation:

$$p=T,\qquad q=F$$

Therefore, saying

"$p\to q$ is false"

means exactly

"$p$ is true AND $q$ is false."

Hence,

$$\boxed{\neg(p\to q)\equiv p\land\neg q}$$

---

12. Additional Implication Equivalences

The following equivalences are also useful:

$$(p\to q)\land(p\to r) \equiv p\to(q\land r)$$ $$(p\to r)\land(q\to r) \equiv (p\lor q)\to r$$ $$(p\to q)\lor(p\to r) \equiv p\to(q\lor r)$$ $$(p\to r)\lor(q\to r) \equiv (p\land q)\to r$$

These identities are especially useful when simplifying compound logical expressions.

---

Summary of Logical Equivalences Involving Conditional Statements

---

13. Logical Equivalences Involving Biconditional

The biconditional

$$p\leftrightarrow q$$

means:

$p$ if and only if $q$.

It is true whenever $p$ and $q$ have the same truth value.

---

Biconditional as Two Implications

$$p\leftrightarrow q \equiv (p\to q)\land(q\to p)$$

For $p$ and $q$ to be equivalent, both directions must hold.

---

Negating Both Sides

$$p\leftrightarrow q \equiv \neg p\leftrightarrow\neg q$$

Negating both propositions does not change whether their truth values are equal.

---

Biconditional Using AND and OR

$$p\leftrightarrow q \equiv (p\land q)\lor(\neg p\land\neg q)$$

This representation makes the meaning of the biconditional very clear.

It is true when either:

$$p=T,\quad q=T$$

or

$$p=F,\quad q=F$$

In other words, $p$ and $q$ must agree.

---

Negation of a Biconditional

$$\neg(p\leftrightarrow q) \equiv p\leftrightarrow\neg q$$

It can also be written as

$$\neg(p\leftrightarrow q) \equiv (p\land\neg q)\lor(\neg p\land q)$$

The negation is therefore true exactly when $p$ and $q$ have different truth values.

---

Summary of Logical Equivalences Involving Biconditional Statements

---

14. Verifying Logical Expressions Using Truth Tables

Logical equivalences can be verified using truth tables.

If two expressions have identical truth values in every possible row, they are logically equivalent.

Let's look at a few examples.

---

Example 1: Construct the Truth Table for $(p\lor\neg q)\to p$

We evaluate the expression step by step.

First calculate:

$$\neg q$$

then

$$p\lor\neg q$$

and finally

$$(p\lor\neg q)\to p$$

Therefore, the compound proposition has truth values

$$T,\;T,\;T,\;F$$

Notice the final row.

There,

$$p\lor\neg q=T$$

while

$$p=F$$

so the implication becomes

$$T\to F$$

which is False.

---

Example 2: Construct the Truth Table for $(\neg(p\land q)\lor r)\to\neg p$

Because there are three variables $p$, $q$, and $r$, the truth table contains

$$2^3=8$$

possible combinations.

We evaluate:

$$p\land q$$

then

$$\neg(p\land q)$$

then

$$\neg(p\land q)\lor r$$

and finally

$$(\neg(p\land q)\lor r)\to\neg p$$

The final column gives the truth value of the complete compound proposition.

---

Example 3: Prove That $p\to q\equiv\neg p\lor q$

One of the most important implication identities is

$$p\to q\equiv\neg p\lor q$$

We can prove this using a truth table.

Compare the final two columns:

They are identical for every possible combination of $p$ and $q$.

Therefore,

$$\boxed{p\to q\equiv\neg p\lor q}$$

The logical equivalence is proved.

---

15. Truth Tables vs. Equivalence Laws

There are two common ways to prove that logical expressions are equivalent.

Method 1: Truth Table

Construct the truth table for both expressions and compare their final columns.

If the columns are identical, the expressions are logically equivalent.

Method 2: Algebraic Simplification

Use established logical laws to transform one expression into another.

For example,

$$\neg(p\to q)$$

Using the implication law,

$$\equiv\neg(\neg p\lor q)$$

Using De Morgan's law,

$$\equiv\neg(\neg p)\land\neg q$$

Using double negation,

$$\equiv p\land\neg q$$

Therefore,

$$\boxed{\neg(p\to q)\equiv p\land\neg q}$$

For large expressions, algebraic simplification is often much faster than constructing a complete truth table.

---

The algebra of propositions provides a systematic way to simplify and transform logical expressions without changing their meaning. By understanding the fundamental equivalence laws, implication and biconditional identities, De Morgan's laws, duality, and truth-table verification, we can solve complex logical expressions more efficiently. These concepts form an important foundation for discrete mathematics, Boolean algebra, digital logic, programming, and theoretical computer science.