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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- symbolic logic derivation solver
- symbolic logic proof solver
- symbolic logic solver
- symbolic logic translator
- 421 ways to say said
- symbolic logic proof practice
- symbolic logic calculator
- symbolic logic proof calculator
- famous alpha phi alpha poems
- poems of alpha phi alpha
- alpha phi alpha poems
- alpha phi alpha hymn words