Logical Equivalences & Laws

Math for CS · Axiom Academy

De Morgan's laws, distribution, absorption, and proving equivalences Equivalences let us simplify complex expressions — just like algebraic identities simplify equations. In circuit design, equivalent expressions that use fewer gates mean cheaper, faster hardware. The most important equivalences in all of logic and CS: In words: "NOT of AND becomes OR of NOTs" and "NOT of OR becomes AND of NOTs." Negation flips the connective and distributes to each operand. Verify De Morgan's first law: (p q) p q . Columns 4 and 7 match in every row, confirming the equivalence. Chain known laws together. Show p (p q) p (absorption): Each step cites a law from the table. This approach scales better than truth tables for complex expressions. De Morgan's laws are the single most useful equivalences — memorize them. Two proof methods: truth table (brute force) or algebraic derivation (chain of laws). These laws are identical to Boolean algebra rules used in circuit simplification. Absorption and distribution often simplify complex expressions dramatically.

This is the written version of the interactive lesson above. See the full Math for CS course.