Proposition Theorems

Propositions can be simplified to make them simpler to understand.

  • Idempotence: p\vee p \equiv p and p\wedge p \equiv p.
  • Excluded middle: p\vee p \equiv T and p\wedge p \equiv F
  • Identity: p\vee F \equiv p and p\wedge T \equiv p.
  • Strictness: p\vee T \equiv T and p\vee F \equiv F.
  • Double negation \lnot \lnot p \equiv p

This is easily provable: construct truth tables with rows for p=F and p=T.

Associativity
(p\vee q) \vee r \equiv p \vee (q \vee r)
(p\wedge q) \wedge r \equiv p \wedge (q \wedge r)

Communtativity
p \vee q \equiv q \vee p
p \wedge q \equiv q \wedge p

Distributivity
p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)
p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)

de Morgan
\lnot (p \vee q) \equiv (\lnot p) \wedge (\lnot q)
\lnot (p \wedge q) \equiv (\lnot p) \vee (\lnot q)

There is a convention of priority among connectives, together with the associativity of \vee and \wedge, reduces the need for brackets. The list below is order from the highest priority to lowest:

  1. \lnot not
  2. \wedge and
  3. \vee or

Leave Comment

Your email address will not be published.

Please type the characters of this captcha image in the input box

Please type the characters of this captcha image in the input box