The Propositional Calculus
In the propositional calculus, the basic unit of
inference is a proposition, which is just a
statement about the world that is either true or false.
Symbols
The symbols of the propositional calculus are defined
in the following table:
| TYPE | SYMBOLS |
|---|
| Propositional | P, Q, R, S, T, ... |
| Truth Values | true, false |
| Connectives | ^, v, ~, →, ≡ |
Syntax: Well-formed formulas (wffs)
Sentences or propositions can be formed by means
of the following rules.
- Every propositional symbol and truth value is a sentence P, Q
- The negation of a sentence is a sentence: ~P, ~false
- The conjunction (AND) of two sentences is a sentence: P ^ ~Q
- The disjunction (OR) of two sentences is a sentence: P v ~Q
- The implication of two sentences is a sentence: P → ~Q
- The equivalence of two sentences is a sentence: P v Q ≡ R
Semantics: The meanings of the symbols
The semantics of the propositional calculus defines the
meanings of its sentences. A propositional symbol, such as P or
Q, represents a sentence about the world, such as "It is raining".
A proposition can be either true or false, depending on the state
of the world.
Possible World Semantics: The assignment of a truth value
to a proposition is called
an interpretation, which is an assertion about its truth in
some possible world. The symbols T and F are used
to symbolize true and false.
Here's a list of rules defining the semantics of the predicate calculus:
- An interpretation assigns either T or F to each
propositional symbol.
- The symbol true is always assigned T and the symbol
false is always assigned F.
- The truth assignments for sentence involving connectives is defined by
the following table:
| P | Q | | ~P | P v Q | P ^ Q | P → Q | P ≡ Q |
|---|
| T | T | | F | T | T | T | T |
| T | F | | F | T | F | F | F |
| F | T | | T | T | F | T | F |
| F | F | | T | F | F | T | T |
Proof by Truth Table
Two statements in the propositional calculus are equivalent
if they have the same truth values under all possible assignments of
truth values---i.e., in all possible worlds. A truth table can be used
to prove that two propositions are either equivalent or not
equivalent.
Example: Show that the expressions P → Q and ~P v Q are equivalent.
Solution: Draw a truth table. Since the columns under both expressions
have the same truth values, they are equivalent.
| P | Q | ~P | ~P v Q | P → Q | (~P v Q) ≡ (P → Q) |
|---|
| T | T | F | T | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
Additional Well-known Equivalences
- Double Negation: ~~P ≡ P
- No name: (P v Q) ≡ (~P → Q)
- Contraposition: (P → Q) ≡ (~Q → ~P)
- DeMorgan's Law 1: ~(P v Q) ≡ (~P ^ ~Q)
- DeMorgan's Law 2: ~(P ^ Q) ≡ (~P v ~Q)
- Commutation 1: (P v Q) ≡ (Q v P)
- Commutation 2: (P ^ Q) ≡ (Q ^ P)
- Association 1: ((P ^ Q) ^ R) ≡ (P ^ (Q ^ R))
- Association 2: ((P v Q) v R) ≡ (P v (Q v R))
- Distribution 1: P v (Q ^ R) ≡ (P v Q) ^ (P v R)
- Distribution 2: P ^ (Q v R) ≡ (P ^ Q) v (P ^ R)
Example: Prove the equivalence of Distribution 1.
Solution: For this proof we need an 8 row truth table
because there are 3 variables, P, Q, and R. In general, for an
expression with n variables, you need a truth table with
2n rows.
| P | Q | R | P v (Q ^ R) | (P v Q) ^ (P v R) | P v (Q ^ R) ≡ (P v Q) ^ (P v R) |
|---|
| T | T | T | T | T | T |
| T | T | F | T | T | T |
| T | F | T | T | T | T |
| T | F | F | T | T | T |
| F | T | T | T | T | T |
| F | T | F | F | F | T |
| F | F | T | F | F | T |
| F | F | F | F | F | T |
Exercise: Prove the equivalence of Demorgan's 1.
Exercise: Prove the equivalence of Distribution 2.
Proof By Substitution of Equivalents
Another form of proof in the propositional calculus is to derive
one expression from another by replacing expressions with
equivalent expressions. For example, here's how we might
prove the Contraposition Law using this approach:
Proof:
| Line | Premise | Justification |
|---|
| 1 | P → Q | Given |
| 2 | ~~P → Q | From step 1 double negation |
| 3 | ~P v Q | From step 2 by equivalence rule #2, above |
| 4 | Q v ~P | From step 3 by Commutation |
| 5 | ~Q → ~P | From step 4 by rule 2 above |