### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Formal Reasoning PHL 330

MSU

GPA 3.72

### View Full Document

## 73

## 0

## Popular in Course

## Popular in PHIL-Philosophy

This 11 page Class Notes was uploaded by Joanne Schamberger on Saturday September 19, 2015. The Class Notes belongs to PHL 330 at Michigan State University taught by Daniel Steel in Fall. Since its upload, it has received 73 views. For similar materials see /class/207674/phl-330-michigan-state-university in PHIL-Philosophy at Michigan State University.

## Similar to PHL 330 at MSU

## Popular in PHIL-Philosophy

## Reviews for Formal Reasoning

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/19/15

Chapter 6 Formal Proofs and Boolean Logic The Fitch program like the system f uses introduction and elimination rules The ones we ve seen so far deal with the logical symbol The next group of rules deals with the Boolean connectives A V and u 61 Conjunction rules Conjunction Elimination Elim P1 A A P A A P gt P This rule tells you that if you have a conjunction in a proof you may enter on a new line any of its conjuncts P1 here represents any of the conjuncts including the first or the last Notice this important point the conjunction to which you apply A Elim must appear by itself on a line in the proof You cannot apply this rule to a conjunction that is em bedded as part of a larger sentence For example this is not a valid use of Elim 1 u Cubea A Largea gt 2 uCubea X A Elim1 The reason this is not valid use of the rule is that Elim can only be applied to conjunctions and the line that this proof purports to apply it to is a negation And it s a good thing that this move is not allowed for the inference above is not validifrom the premise that a is not a large cube it does not follow that a is not a cube 1 might well be a small cube and hence not a large cube but still a cube This same restrictionithe rule applies to the sentence on the entire line and not to an embedded sentenceiholds for all of the rules of f by the way And so Fitch will not let you apply Elim or any of the rules of inference to sentences that are embedded within larger sentences Conjunction Introduction A Intro P1 U Pr gt P1 A A P This rule tells you that if you have a number of sentences in a proof you may enter on a new line their conjunction Each conjunct must appear individually on its own line although they may occur in any order Thus if you have A on line 1 and B on line 3 you may enter B A on a subsequent line Note that the lines need not be consecutive You may of course also enter A B Copyright 2004 S Marc Cohen 6 Revised 6104 Default and generous uses of rules Unlike system f Fitch has both default and generous uses of its rules A default use of a rule is what will happen if you cite a rule and a previous line or lines as justi cation but do not enter any new sentence If you askFitch to check out the step it will enter a sentence for you A generous use of a rule is one that is not is not strictly in accordance with the rule as stated in j ie j would not allow you to derive it in a single step but is still a valid inference Fitch will often let you do this in one step Default and generous uses of the A rules 0 Default use if you cite a conjunction and the rule A Elim and ask Fitch to check out the step Fitch will enter the leftmost conjunct on the new line Generous use if you cite a conjunction and the rule A Elim you may manually enter any of its con juncts or you may enter any conjunction whose conjuncts are among those in the cited line Fitch will check out the step as a valid use of the rule Note just how generous Fitch is about A Elimifrom the premise A A B A C A D Fitch will allow you to obtain any of the following among others by a generous use of the rule DAAAC BAAACAD 62 Disjunction rules Disjunction Introduction V Intro P Igt P1 V V P V V Pquot This rule tells you that if you have a sentence on a line in a proof you may enter on a new line any disjunction of which it is a disjunct P1 here represents any of the disjuncts including the rst or the last Copyright 2004 S Marc Cohen 62 Revised 6104 Disjunction Elimination V Elim This is the formal rule that corresponds to the method of proof by cases It incorporates the formal device of a subproof A subproof involves the temporary use of an additional assumption which functions in a subproof the way the premises do in the main proof under which it is subsumed We place a subproof within a main proof by introducing a new vertical line inside the vertical line for the main proof We begin the subproof with an assumption any sentence of our choice and place a new Fitch bar under the assumption Premise Assumption for subproof The subproof may be ended at any time When the subproof ends the vertical line stops and the next line either jumps out to the original vertical proof line or a new subproof may be begun As we ll see V Elim involves the use of two or more subproofs typically although not necessarily entered one immediately after the other The rule P1 V V P P1 8 U Pn 8 gt8 What the rule says is this if have a disjunction in a proof and you have shown through a sequence of subproofs that each of the disjuncts together with any other premises in the main proof leads to the same conclusion then you may derive that conclusion from the disjunction together with any main premises cited within the subproofs This is clearly a formal version of the method of proof by cases Each ofthe P1 represents one of the cases Each subproof represents a demonstration that in each case we may conclude 8 Our conclusion is that S is a consequence of the disjunction together with any of the main premises cited within the subproofs When you do the You try it on p 151 notice as you proceed through the proof that after step 4 you must end the subproof rst before you begin the next subproof To do these things you can click on the options in the Proof menu But it is easier and quicker to use the keyboard shortcuts to end a subproof press Control E to begin a new subproof press Cont rol P Another handy shortcut is Control A for adding a new line after the current line as part of the same proof or subproof Any time you add a new line Fitch will wait for you to write in a sentence and cite a justi cation for it Copyright 2004 S Marc Cohen 63 Revised 6104 Note also that the use of Reit is strictly optional For example in the proof on p 151 step 5 is not required The proof might look like the one in Page 151 Qrf on Supplementary Exercises page and it will check out Default and generous uses of the Vrules 0 Default uses 0 V Elim if you cite a disjunction and some subproofs with each subproof beginning with a different disjunct of the disjunction and all subproofs ending in the same sentence 8 cite the rule V Elim and ask Fitch to check it out Fitch will enter 8 0 V Intro if you cite a sentence and the rule V Intro and ask Fitch to check it out Fitch will enter the cited sentence followed by a V and wait for you to enter whatever disjunct you wish Generous use if your cited disjunction contains more than two disjuncts you don t need a separate subproof for each disjunct A subproof may begin with a disjunction of just some of the disjuncts of the cited disjunction When you ask Fitch to check the step Fitch will check it out as a valid use of the rule so long as every disjunct of the cited disjunction is either a subproof assumption or a disjunct of such an assumption 63 Negation rules Negation Elimination u Elim This simple rule allows us to eliminate double negations u u P gt P Negation Introduction u Intro This is our formal version of the method of indirect proof or proof by contradiction It requires the use of a subproof The idea is this if an assumption made in a subproof leads to J you may close the subproof and derive as a conclusion the negation of the sentence that was the assumption P h gt u P To use this rule we will need a way of getting the contradiction symbol J into a proof We will have a special rule for that one which allows us to enter a J if we have on separate lines in our proof or subproof both a sentence and its negation J Introduction J Intro P u P gt J Copyright 2004 S Marc Cohen 64 Revised 6104 Note that the cited lines must be explicit contradictories ie sentences of the form P and u P This means that the two sentences must be symbolforsymbol identical except for the negation sign at the beginning of one of them It is not enough that the two sentences be TT inconsistent with one another such as A V B and uA u B Although these two are contradictories semantically speaking since they must always have opposite truthvalues they are not explicit contradictories syntactically speaking since they are not written in the form P and u P To try out these two rules do the You try it on p 156 Other kinds of contradictions The rule of J Intro lets us derive J whenever we have a pair of sentences that are explicit contradictories But there are other kinds of contradictory pairs nonexplicit TT contradictories FOcontradictories that are TTconsistent logical contradictories that are FO consistent and TWcontradictories that are logically consistent Here are some examples of these other types of contradictory pairs 1 Teta VTetb and uTeta A uTetb 2 Cubeb A a b and uCubea 3 Cubeb and Tetb 4 uTeta A uCubea and uDodeca In example 1 we have TTcontradictory sentences but not an explicit contradiction as de ned above In 2 we have a pair of sentences that are FOinconsistent they cannot both be true in any possible circumstance but not TTinconsistent a truthtable would not detect their inconsistency In 3 we have a pair that are logically inconsistent but not FOinconsistent or TTinconsistent Finally in 4 we have a pair that are TW contradictories there is no Tarski world in which both of these sentences are simultaneously true although they are logically consistentiit is possible for an object to be neither a tetrahedron nor a cube nor a dodecahedron it may be a sphere The rule of J Intro does not apply directly in any of these examples In each case it takes a bit of maneuvering first before we come up with an explicitly contradictory pair of sentences as required by the rule Example 1 1 Teta V Tetb 2 uTeta A uTetb 3 Teta A Elim 2 4 Tetb A Elim 2 5 Teta 6 J J Intro 3 5 7 Tetb 8 J J Intro 4 7 9 J v Elim 1 56 78 Copyright 2004 S Marc Cohen 65 Revised 6104 Here we used A Elim twice to get the two conjuncts of 2 separately and then constructed a proof by cases to show that whichever disjunct of line 1 we choose we get to an explicit contradiction Example 2 1 Cubeb a b 2 uCubea 3 Cubeb A Elim l 4 a b Elim l 5 Cubeb Elim 2 4 6 J J Intro 3 5 Here we used Elim to get Cubeb and a b to stand alone and then Elim substituting b for a in line 2 to get the explicit contradictory of Cubeb Example 3 1 Cubeb 2 Tetb 3 uTetb Ana Con l 4 J J Intro 2 3 Here we had to use Ana Con Of course as long as we were going to use Ana Con at all we could have used it instead of J Intro to get our contradiction as follows 1 Cubeb 2 Tetb 3 J Ana Con l 2 Example 4 1 uTeta uCubea 2 uDodeca 3 J Ana Con l2 To see these different forms of contradictions in action do the You try it on p 159 It s an excellent illustration of these differences You ll nd that you often need to use the Con mechanisms to introduce a J into a proof since J Intro requires that there be an explicit contradiction in the form of a pair of sentences P and u P Copyright 2004 S Marc Cohen 66 Revised 6104 J Elimination J Elim J gt P The rule of J elimination is added to our system strictly as a convenienceiwe do not really need it It allows us once we have a J in a proof to enter any sentence we like We ve already seen that every sentence follows from a contradiction As p 161 shows we can easily do without this rule with a four step workaround Default and generous uses of the u rules Note the default and generous uses of these rules in Fitch p 161 With Elim you don t need two steps to get from u u u u P to P passing through the intermediate step u u P You can do it in one step In fact this is also the default use of the rule if you cite the rule and ask Fitch to fill in the derived line In the case of u Intro where the subproof assumption is a negation u P and the subproof ends with a J 0 Default use if you end the subproof cite the subproof and rule u Intro and ask Fitch to check the step Fitch will enter the line u u P Generous use if you end the subproof enter the line P manually cite the subproof and rule a Intro and ask Fitch to check the step Fitch will check it out as a valid use of the rule 64 The proper use of subproofs Once a subproof has ended none of the lines in that subproof may be cited in any subsequent part of the proof Look at the proof on p 163 to see what can happen if this restriction is violated How Fitch keeps you out of trouble When you are working in system f you can enter erroneous lines like line 8 on p 163 and never be aware of it But Fitch won t let you do this To see what happens look at Page1639rf Notice that when we try to justify line 8 by means of A Intro Fitch will not let us cite the line that occurs inside the subproof that has already been closed When a subproof ends we say that its assumption has been discharged After an assumption is discharged one may not cite any line that depended on that assumption Note that it is permissible while within a subproof to cite lines that occur outside that subproof So for example one may while within a subproof refer back to the original premises or conclusions derived from them One must just take care not to cite lines that occur in subproofs whose assumptions have been discharged Subproofs may be nestedione subproof may begin before another is ended In such cases the last subproof begun must be ended first The example on p 165 illustrates such a nested subproof 65 Strategy and tactics Keep in mind what the sentences in your proof mean Don t just look at the sentences in your proof as meaningless collections of symbols Remember what the sentences mean as you try to discover whether the argument is valid Copyright 2004 S Marc Cohen 67 Revised 6104 Ifyou re not told whether the argument is valid you can use Fitch s Taut Con mechanism to check it out Ifyou discover that the argument is not valid you should not waste time trying to nd a proof Try to sketch out an informal proof This will often give you a good formal proof strategy An informal indirect proof can be turned into a use of u Intro in f An informal proof by cases can be turned into a use of V Elim in f Try working backwards This is a very basic strategy It involves guring out what intermediate conclusion you might reach that would enable you to obtain your ultimate conclusion and then taking that intermediate conclusion as your new goal You can then work backwards to achieve this new goal gure out what other intermediate conclusion you might reach that would enable you to obtain your rst intermediate conclusion and so on Working backward in this way you may discover that it is obvious to you how to obtain one of those intermediate conclusions You then have all the pieces you need to assemble the proof Fitch is very helpful to you in using this strategy for you can work from the bottom up as well as from the top down To see this do the You try it on p 168 open the le Strategy 1 You will note that you can cite a line or a subproof as part of a justi cation even before you have justi ed the line itself This shows up with the two innermost subproofs 35 and 6 8 which can be used in the justi cation of line 9 even before lines 5 and 8 themselves have been justi ed This gives you a good method for checking out your strategy An example AA uBVCV D C B u u D Open Ch6Ex2a 7 you ll nd this problem on the Supplementary Exercises page of the web site We can start by working backwards We can get u u D from D by assuming u D and using u Intro So our goal will be to get D Our rst premise is a disjunction so that suggests a proof by cases We will have a separate subproof for each case deriving D at the end of each subproof Open Ch6EX2b Notice that our strategy checks out when we apply V Elim and that our strategy for obtaining u u D also checks out Case 1 A B The second conjunct u B contradicts the second conjunct of premise 2 So we can derive J by J Intro and then derive D by J Elim Case 2 C The first conjunct C contradicts the first conjunct of premise 2 So we can derive J by J Intro and then derive D by J Elim Copyright 2004 S Marc Cohen 68 Revised 6104 Case 3 D We already have D so we can use Reit to enter it as a conclusion in the subproof In fact we can even skip the Reit step as we ll see We ll now go after case 1 Open Ch6EX2C and follow the strategy above Notice that the steps check out Finally we ll complete cases 2 and 3 Open Ch6EX2d and follow the strategy for cases 2 and 3 Notice that in case 3 we did not need to use Reit In this case our subproof contains only the assumption line In such a case we count the assumption line itself as the last line in the subproof and hence we take that line to have been established given the assumption This is obviously acceptable since every sentence is a consequence of itself 66 Proofs without premises Both system j and the program Fitch are set up so that a proof may begin with some line other than a premise For example it might begin with a use of Intro Or it may begin with a subproof assumption This means that we may have a proof that has no premises at all What does such a proof establish Since a proof establishes that a conclusion is a logical consequence of its premises ie that it must be true if they are a proof without premises establishes that its conclusion is a logical consequence of the empty set of premises That is it establishes that its conclusion must be true period In other words such a proof establishes that its conclusion is a logical truth See pages 1734 for examples of such proofs The conclusion of a proof without premises is often called a theorem although Barwise and Etchernendy do not use that terminology For a try at proving a logical truth in Fitch try exercise 633 Can you think of a simpler proof of the same logical truth You can nd one at Proof 633 simpler A Dif cult example 641 We ll try to prove this starred tautology A B V uA V u B And we will do so the hard way without using Taut Con to justify an instance of Excluded Middle Our tautology says that either A and B are both true or at least one of them is false To prove a tautology it is often easiest to use indirect proof assume the negation of what we re trying to prove and show that it leads to a contradiction That is the method we will use To see the general strategy for our proof open Proof 641 a We assume the negation of our desired conclusion and aim to derive I We can then apply rule u Intro generous version to get our theorem Note that this last step checks out Now what we have assumed is the negation of a disjunction So if what we ve assumed is true each of the disjuncts is false In particular both uA and u B are false So given our assumption we should be able to prove both A and B That is what we will do next We will do so by indirect proof open Proof 641 b Note that our indirect method for proving both A and B checks out Copyright 2004 S Marc Cohen 69 Revised 6104 W awn mummm mm mm m m w Cam My wwwulhthnlzyululhrimwzlwmxhg39z Wmquot mum mug mm masmammm munnu muwmgmmw Nam mm axma 1mm mmmmmmwwmumgummmm m m mn n no 13 vi same WWW Mm mmuhmm mm mm mm mum mm A hl MWWWMW mm mgmmgmmw m Myzhusmlyynmhmsusymlkmmuhwmbu mm axma mmu umwzm mnmmm xwmmrmm Vilma 3mm mas mmmb mam m an mum hindMK A m WWWMMWW m Magmwmw Chmzm wmm y mew mm mmmw wh mumrm mum m V n wwwmmm AD mammgmmw Any me ymy mmmw buml Wmmm mme WWW mm mm mmmwm sm Wmmmmaummymmmm mum farm Em mismank mm mmymumm m nah mm m m m mm mm gmmmmmumkm ism an uh mum nuhmf m Mesvfsumesyunzmyrvw Any Types of sentences you must cite Cite only a negation of a negation Instructions for use If there is a sentence with at least two negations on it you can take the negations off two at a time with this rule Cite only one sentence Rule Name Negation Introduction 39 Intro Types of sentences you can prove An Types of sentences you must cite Cite only a single subproof that begins with the opposite of what you hope to prove and ends with L Instructions for use Begin a subproof with the opposite of what you want to prove outside of the subproof End the subproof with J Cite only the subproof Rule Name Contradiction Introduction J Intro Types of sentences you can prove nl Types of sentences you must cite l A sentence and 2 Exactly that sentence negated Cite only two sentences Instructions for use Find a sentence and it39s negation Cite both and write J on a line Rule Name Contradiction Elimination J Elim Types of sentences you can prove Any i on a line you may cite that line and write any sentence you please Types of sentences you must cite You must cite only a single line containing Instructions for use If you prove J on a subsequent line Rule Name Conditional Introduction gt Intro Types of sentences you can prove Only a Conditional Types of sentences you must cite You must cite only a single subproof Instructions for use To prove a conditional statement make a subproof that begins with the antecedent and ends with the consequent Rule Name Conditional Elimination gt Elim Types of sentences you can prove An Types of sentences you must cite You must cite exactly two sentences I a conditional and 2 a sentence that is the antecedent of the conditional in 1 Instructions for use You can only prove the consequent of the conditional cited in 1 above Rule Name Biconditional Introduction ltgt Intro Types of sentences you can prove Only a Biconditional Types of sentences you must cite You must cite exactly two subproofs Instructions for use To prove a biconditional statement make a subproof that begins with the left and ends with the right and make another subproof that begins with the right and ends with the left Rule Name Biconditional Elimination ltgt Elim Types of sentences you can prove Any Types of sentences you must cite You must cite exactly two sentences 1 a Biconditional and 2 a sentence that is either the left or right side of the biconditional in 1 Instructions for use You prove one side of the biconditional cited in 1 above

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.