(Last modified Wed May 07 22:43 2008)
Propositional logic (PL) concerns statements that can be true or false, possibly combined into more complex statements using negation (¬α), disjunction (α∨β), and conjunction (α∧β), where α and β are meta-variables that represent formulae in PL.
| Common notations | Ours | ASCII | Others |
|---|---|---|---|
| True | T | T | 1, tt, T |
| False | F | F | 0, ff, ⊥ |
| Negation | ¬α | !α | α, ~α, -α |
| Disjunction | α∨β | α|β, α||β | α+β |
| Conjunction | α∧β | α&β, α&&β | α·β, αβ |
The only variable-like elements in PL are propositional variables (also called sentence letters), such as A, B, or C. A propositional variable represents either "true" or "false", although we may not know which.
An interpretation is a mapping from propositional variables to truth values. A propositional logic formula involving propositional variables can always be evaluated as true or false in a specific interpretation that defines its propositional variables.
You will notice that the PL operations ¬ ∧ ∨ have the same properties as the set operations ∩ ∪: PL and sets are both examples of lattices. As with ∩ and ∪, ∧ and ∨ exhibit duality.
The symbol ≡ represents logical equivalence. α≡β means that for every assignment of T or F to each of the variables in α and β (in other words, for every interpretation), either
| Property | Definition for ∧ and ∨ | Definition for ∨ and ∧ |
|---|---|---|
| idempotent | X∧X ≡ X | X∨X ≡ X |
| commutative | X∧Y ≡ Y∧X | X∨Y ≡ Y∨X |
| associative | (X∧Y)∧Z ≡ X∧(Y∧Z) | (X∨Y)∨Z ≡ X∨(Y∨Z) |
| distributive | X∧(Y∨Z) ≡ (X∧Y)∨(X∧Z) | X∨(Y∧Z) ≡ (X∨Y)∧(X∨Z) |
| De Morgan's laws | ¬(X∧Y) ≡ ¬X ∨ ¬Y | ¬(X∨Y) ≡ ¬X ∧ ¬Y |
| absorptive | X∧(X∨Y) ≡ X ≡ X∨(X∧Y) | |
One sometimes sees material implication α→β, usually pronounced as "if α then β". It seems to imply that its left operand causes its right operand. However, this is misleading and incorrect. Logic abstracts everything but truth value and logical structure — cause and effect are simply not there. The material conditional is simply another truth-function. A material implication α→β may always be rewritten as ¬α∨β, and almost always should be (except perhaps when dealing with logical proofs, in which material implication corresponds to syntactic implication, and cause and effect are not relevant). This form ¬α∨β is clearer and doesn't imply anything more than it says.
One also sometimes sees material bi-implication α↔β, usually pronounced "α if and only if β" and also best avoided in most circumstances.
Material implication is involved in the paradoxes of classical logic:
For the purpose of minimizing parentheses, ¬ binds tightest, followed by ∧ and ∨, followed by →, and finally ↔ (and any other operators). Logicians have not adopted a single custom for ∧ and ∨, so it is safest to parenthesize sentences that contain both. However, in computer science it has long been customary for ∧ to bind more tightly than ∨, and we will follow that approach. Thus for us α∨¬β∧γ→δ is the same as (α∨((¬β)∧γ))→δ
It is handy to know how to show the various forms of propositions are not true:
