Your continued donations keep Wikipedia running!    

Laws of logic

From Wikipedia, the free encyclopedia

Jump to: navigation, search

These laws of classical logic are valid in propositional logic and any boolean algebra. Some are axioms and others derived with truth tables. The logical operators ¬ 'not', ∧ 'and', ∨ 'or', the values T 'logically true', F 'logically false', and the relation ≡ 'logically equivalent to' are applied to propositions p, q, r.

Basic Principles of Classical, Propositional and Boolean Logic
* Bivalency   ¬ T  ≡  F
¬ F  ≡  T
* Involution   ¬ ¬ p  ≡  p
* Idempotency   p ∧ p  ≡  p
p ∨ p  ≡  p
Identity   p ∧ T  ≡  p
p ∨ F  ≡  p
(Non-)Contradiction   p ∧ ¬ p  ≡  F
¬ ( p ∧ ¬ p )  ≡  T
Excluded Middle   p ∨ ¬ p  ≡  T
¬ ( p ∨ ¬ p )  ≡  F
* Contraction   p ∧ ( p ∨ q )  ≡  p
p ∨ ( p ∧ q )  ≡  p
Commutativity   p ∧ q  ≡  q ∧ p
p ∨ q  ≡  q ∨ p
* DeMorgan's   ¬ ( p ∧ q )  ≡  ¬ p ∨ ¬ q
¬ ( p ∨ q )  ≡  ¬ p ∧ ¬ q
Associativity   p ∧ ( q ∧ r )  ≡  ( p ∧ q ) ∧ r
p ∨ ( q ∨ r )  ≡  ( p ∨ q ) ∨ r
Distributivity   p ∧ ( q ∨ r )  ≡  ( p ∧ q ) ∨ ( p ∧ r )
p ∨ ( q ∧ r )  ≡  ( p ∨ q ) ∧ ( p ∨ r )
  • In these logics, the principles of bivalency, involution, idempotency, contraction, DeMorgan, and others like p ∧ T ≡ p and p ∨ F ≡ p are traditionally derived from the remainder above, which are considered axioms. One could reverse these derivations and make some of the derived principles axiomatic and derive some of the former axioms (like the laws of non-contradiction and the excluded middle) from them.
Retrieved from "http://en.wikipedia.org/wiki/Laws_of_logic"
Personal tools