Algebraic Laws for Logical Expressions

As with arithmetic expressions, there are algebraic laws for logical expressions that establish the equivalence of two expressions. Each of these laws can be proven by showing the equivalence is a tautology.


DeMorgan's Laws

DeMorgan's Laws are algebraic laws (or equivalences) that allow us to rewrite any logical expression so that NOT is only applied to propositional variables (and not to other logical expressions).

DeMorgan's Laws:

  1. NOT (p AND q) == (NOT p) OR (NOT q)

  2. NOT (p OR q) == (NOT p) AND (NOT q)

These laws state that the negation of the conjunction (or disjunction) of two propositions is logically equivalent to the disjunction (or conjunction) of their negations.

By repeated application of DeMorgan's laws, we can push the NOT operators inward in an expression until they apply to variables only.

Example:

      NOT ((p AND q) OR (NOT p AND r))
      == NOT (p AND q) AND NOT (NOT p AND r)
      == (NOT p OR NOT q) AND (p OR NOT r)
  

Example:

      NOT (NOT p OR (q AND ( NOT(r OR NOT s) ) )
      == NOT NOT p AND NOT (q AND (NOT(r OR NOT s))
      == p AND (NOT q OR NOT (NOT(r OR NOT s))
      == p AND (NOT q OR NOT (NOT r AND NOT NOT s)
      == p AND (NOT q OR (r OR NOT s) )
  

Laws of Implication