Discrete Mathematics for Computer Science

Introduction to Propositional Logic 93

The formal definition of a formula is an inductive definition of a set of strings. The

base cases correspond to the base step of an inductive proof. The closure rules correspond

to the inductive step.

Definition 2. A formula is any string of symbols that is formed using the following rules:

1. Base cases: Every proposition letter is a formula. T and F are formulas.


2. Closure rules: Let 4 be a formula. Then, (--4)) is a formula. For formulas 4 and V,
   (0 A f), (0 V ), (0 - s), and (0 + *t) are formulas.

According to the base case alone, p, q, and T are formulas. From the base case and

just one application of the closure rules, one can show that (p A q), (p v p), (p --+ T),

and -q are formulas. From the base case and two applications of the closure rules, one can

show that (-(p A q)) and (q <-* (p -+ T)) are formulas.

It often seems that in elementary logic, most theorems are proved by induction on

some integer related to formulas, such as the number of symbols, the number of parenthe-

ses, the number of propositional connectives, or the number of times the closure rules of

Definition 2 were applied to generate the formula. (Let this be a hint for the Exercises.)

Theorem 1. (Principle of Induction on Formulas) Let T be a set of formulas such

that:

Base cases Each proposition letter is in F, and T and F are in T.

Closure rules If 4, Vtare formulas in F7, so are

(-0), (4 A *t), (0 V Vt), (4 -- Vt), and (4 - Vt)

Then, F is the set of all formulas.

Proof. Let T = {n E N : all formulas formed using n elements of {-, V, A, -+, +-+} are
in F71. If we prove T = N, then all formulas are in F. We will use the strong form of
mathematical induction to complete this proof.
(Base step) Let n = 0. All formulas using 0 instances of elements of {-, V, A, --, --}
are just the proposition letters and the two logical constants T and F. Because these are
just the elements in the base cases used to define T, all these elements are in F, and 0 E T.

(Inductive step) Let n > 0 and assume that 0, 1 .... n - 1 c T. To prove n E T will be

a proof by cases (see Template 1.8, Proof by Cases). We use a proof by cases because a for-

mula formed using n instances of elements of {-, v, A, -+, ++-J is of one of the following

forms:

(a) -0, where 4 is formed using n - 1 elements of {-, V, A, -*, +}

(b) 4 V *, where 4 and Vt are each formed using fewer than n elements of

I-•, V, A,--+, ++}

(c) 4 A *,, where 4 and * are each formed using fewer than n elements of

{-, V, A, -+, +-}

(d) 4-+ V*, where 4 and V are each formed using fewer than n elements of

t', V, A, --, +-}

(e) 4) *,- , where 4 and Vt are each formed using fewer than n elements of

{-, V, A, -+, ++1

The details of the proof in each of these cases are left as an exercise. U