PHI 421 – Symbolic Logic



|PHIL 422 – Advanced Logic |

|Proof by Induction Exercise |

|I. You might already be familiar with procedures for “driving” negations into the scopes of other functors through successive |

|applications of DeMorgan’s rule. Consider then the following claim, which can be established through logical induction: |

|  |

|Any formula is equivalent to one in which all negations (if any) range over just single proposition letters (that is, one in which |

|all the negations have been “driven” inside of any parentheses). |

|  |

| |

|1.  To prove this claim by induction, we need to begin by identifying an appropriate means of ordering all of the well-formed |

|formulas. 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 let’s consider an arbitrary formula χ. We then need to have an inductive |

|hypothesis.  In this example, what would the inductive hypothesis be? |

| |

|  |

|  |

|  |

|  |

|  |

|  |

|  |

|4.  In the (inductive) case, the demonstration that our arbitrary formula χ must obey our initial claim proceeds by cases |

|corresponding to χ’s major operator. Supposing χ is a conjunction -- (φ & ψ) -- how does the inductive hypothesis apply? |

|  |

|  |

|  |

|  |

|  |

|  |

| |

|5.  Again, assuming that χ is a conjunction, say why our initial conjecture must then apply to χ as well. |

| |

| |

| |

| |

| |

| |

|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 initial conjecture must hold of χ, depending upon the kind of formula that it negates. Briefly state why our |

|initial conjecture 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. |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|  |

|II.  Hopefully, you are now in position to construct an inductive proof entirely on your own. |

|Consider a formal language with a one-place operator * and a three-place operator # with the following syntax (or rules of sentence|

|or formula formation). |

| |

|(1) Any Atomic Proposition Letter is a well-formed formula (wff). |

|(2) If φ is a wff, then so too is *φ. |

|(3) If φ, χ, and ψ are all wffs, then so too is #φχψ. |

|(4) Nothing else is a wff. |

| |

|Using what we just did above in part I as a model, carefully construct an inductive argument for the claim that any formula |

|constructed according to this syntax must have an odd number of proposition letters.  This is not as complex as what we just went |

|through. However, be very explicit about how you are ordering formulas, what the base case is, what the inductive hypothesis is, |

|and how it is used in the proof. |

 

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download