## 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.