Propositional Formula - Parsing Formulas

Parsing Formulas

The following "laws" of the propositional calculus are used to "reduce" complex formulas. The "laws" can be easily verified with truth tables. For each law, the principal (outermost) connective is associated with logical equivalence ≡ or identity =. A complete analysis of all 2n combinations of truth-values for its n distinct variables will result in a column of 1's (T's) underneath this connective. This finding makes each law, by definition, a tautology. And, for a given law, because its formula on the left and right are equivalent (or identical) they can be substituted for one another.

Example: The following truth table is De Morgan's law for the behavior of NOT over OR: ~(a V b) ≡ (~a & ~b). To the left of the principal connective ≡ (yellow column labelled "taut") the formula ~(b V a) evaluates to (1, 0, 0, 0) under the label "P". On the right of "taut" the formula (~(b) V ~(a)) also evaluates to (1, 0, 0, 0) under the label "Q". As the two columns have equivalent evaluations, the logical equivalence ≡ under "taut" evaluates to (1, 1, 1, 1), i.e. P ≡ Q. Thus either formula can be substituted for the other if it appears in an larger formula.

Enterprising readers might challenge themselves to invent an "axiomatic system" that uses the symbols { V, &, ~, (, ), variables a, b, c }, the formation rules specified above, as few as possible of the laws listed below, and then derive as theorems the others as well as the truth-table valuations for V, &, and ~. One set attributed to Huntington (1904) (Suppes:204) uses 8 of the laws defined below.

Note that that if used in an axiomatic system, the symbols 1 and 0 (or T and F) are considered to be wffs and thus obey all the same rules as the variables. Thus the laws listed below are actually axiom schemas, that is, they stand in place of an infinite number of instances. Thus ( x V y ) ≡ ( y V x ) might be used in one instance, ( p V 0 ) ≡ ( 0 V p ) and in another instance ( 1 V q ) ≡ ( q V 1 ), etc.