Propositional Logic

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.

AND and OR are commutative

      p AND q == q AND p
      p OR q == q OR p

AND and OR are associative

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

AND is distributive over OR; OR is distributive over AND

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

TRUE is the identity for AND; FALSE is the identity for OR
```
      p AND TRUE == p
      p OR FALSE == p
  
```

FALSE annihilates AND; TRUE annihilates for OR

      p AND FALSE == FALSE
      p OR TRUE == TRUE

AND and OR are idempotent
```
      p AND p == p
      p OR p == p
  
```

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:

NOT (p AND q) == (NOT p) OR (NOT q)
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

(p -> q) AND (q -> p) == (p == q)
Two expressions are equivalent if they imply each other.
(p == q) -> (p -> q)
If two expressions are equivalent, they imply each other.
((p -> q) AND (q -> r)) -> (p -> r)
Implies is transitive.
(p -> q) == (NOT p OR q)
We can express "implies" in terms of NOT and OR.
(p1 AND p2 AND ... pn -> q)
== (NOT p1 OR NOT p2 OR ... NOT pn OR q)
We can express a series of implicants using NOT and OR.
(p -> q) == (NOT q -> NOT p)
This equivalence is known as the contrapositive law.
((p -> q) AND (NOT p -> q)) == q
This equivalence follows from expressing implies in terms of NOT and OR: (Not p OR q) AND (p OR q) == q.