Boolean Algebra

Since we now understand what it means for two propositions to be logically equivalent, we can pre-emptively determine cases where the truth values of propositions match, thus finding substitutions for propositions.

Double negation

The negation of the negation of a proposition is logically equivalent to the proposition itself: $$ \begin{equation}\begin{aligned} \neg (\neg p)\equiv p\\ \end{aligned}\end{equation} $$

De Morgan’s Laws

The negation of a disjunction is logically equivalent to the conjunction of the negations of the individual propositions: $$ \begin{equation}\begin{aligned} \neg (p\lor q)\equiv \neg p \land \neg q\\ \end{aligned}\end{equation} $$

The negation of a conjunction is logically equivalent to the disjunction of the negations of the individual propositions: $$ \begin{equation}\begin{aligned} \neg (p\land q)\equiv\neg p \lor \neg q\\ \end{aligned}\end{equation} $$

Challenge

Using truth tables, prove the following logical equivalences:

• $p\lor 0\equiv p$ (Identity Law)
• $p\land 1\equiv p$ (Identity Law)
• $p\lor 1\equiv 1$ (Annulment Law)
• $p\land 0\equiv 0$ (Annulment Law)
• $p\lor p\equiv p$ (Idempotent Law)
• $p\land p\equiv p$ (Idempotent Law)
• $p\lor \neg p\equiv 1$ (Complement Law)
• $p\land \neg p\equiv 0$ (Complement Law)
• $p\lor q \equiv q\lor p$ (Commutative Law)
• $p\land q\equiv q\land p$ (Commutative Law)
• $p\lor (q\lor r) \equiv (p\lor q)\lor r$ (Associative Law)
• $p\land (q\land r) \equiv (p\land q)\land r$ (Associative Law)
• $p\lor (p\land q) \equiv p$ (Absorption Law)
• $p\land (p\lor q) \equiv p$ (Absorption Law)
• $p\lor (q\land r) \equiv (p\lor q)\land (p\lor r)$ (Distributive Law)
• $p\land (q\lor r) \equiv (p\land q)\lor (p\land r)$ (Distributive Law)