You might already be familiar with procedures for driving negations into the scopes of other truth functors until you arrive at an equivalent formula in which the remaining negations range only over atomic sentences. (For instance, think of formulas in disjunctive normal form.) One starts with negations with the widest scope, and then successively applies the DeMorgans rules on negations of conjunctions and on negations of disjunctions. For negations of conditionals we appeal to the equivalence: (P Q) i.e.t. (P & Q). Each time we drive in a negation, we dispose of pesky double negations when they arise. Consider then the following claim, which can be established through logical induction:

Every well-formed formula of LSL is equivalent to one in which all negations (if any) range over just single sentence letters (that is, one in which all the negations have been driven inside of any parentheses).

[In short: Every wff of LSL has an equivalent with all negations driven in.]

1. To prove this claim by induction, we need to begin by identifying an appropriate means of ordering all the well-formed formulas of LSL. What ordering should we use?

2. From that ordering, we begin our inductive proof with a base case. What is this base case? And why is the proof of the overall claim for the base case trivial?

3. We then proceed to the inductive step. So now lets consider an arbitrary, compound formula . We then need to have an inductive hypothesis. In this example, what would the inductive hypothesis be?

4. In the inductive step, the demonstration that our arbitrary, compound formula must obey our initial claim proceeds by cases corresponding to s major operator. Suppose that is a conjunction ( & ). How does the inductive hypothesis apply?

[Observe that here is a conjunction not a negation of a conjunction! We dont need to get ahead of ourselves and apply the DeMorgans rules just yet.]

5. Again, assuming that is a conjunction, say why our hypothesis must then apply to as well. Specifically, what is the formula equivalent to that would have all its negations driven in?

6. In this particular example, it turns out that most of the legwork is done in the case that is a negation. One then proceeds to show that our hypothesis must hold of , depending upon the kind of formula that it negates; this can be an atomic, a negation, a conjunction, a disjunction, or a conditional. For instance, if is the negation of an atomic, the hypothesis clearly holds, because then just is equivalent to the negation of a sentence in which no negations can be further driven in.

Briefly state why the hypothesis must hold of when the formula that negates is itself a negation.

7. Finally, briefly state why our initial conjecture must hold of when the formula that negates is itself a conjunction. That is, is of the form ( & ). Be very specific about how the inductive hypothesis applies.