Note for PHIL 110 at UMass
Popular in Course
Popular in Department
This 88 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Note for PHIL 110 at UMass
Report this Material
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: 02/06/15
DERIVATIONS IN 39 39 PREDICATE LOGIC NQF WPP N Intro duction 3 8 2 The Rules of Sentential Logic 382 The Rules of Predicate Logic An Overview 385 Universal Out 387 Potential Errors in Applying UniversalOut 389 Examples of Derivations using UniversalOut 390 Existential In 393 Universal Derivation 397 Existential Out 404 How ExistentialOut Differs from the other Rules 412 Negation Quanti er Elimination Rules 414 Direct versus Indirect Derivation of Existentials 420 Appendix 1 The Syntax of Predicate Logic 429 Appendix 2 Summary of Rules for System PL Predicate Logic 438 Exercises for Chapter 8 440 Answers to Exercises for Chapter 8 444 382 Hardegree Symbolic Logic 1 INTRODUCTION Having discussed the grammar of predicate logic and its relation to English we now turn to the problem of argument validity in predicate logic Recall that in Chapter 5 we developed the technique of formal derivation in the context of sentential logic specifically System SL This is a technique to de duce conclusions from premises in sentential logic In particular if an argument is valid in sentential logic then we can in principle construct a derivation of its con clusion from its premises in System SL and if it is invalid then we cannot construct such a derivation In the present chapter we examine the corresponding deductive system for predicate logic what will be called System PL short for predicate logic As you might eXpect since the syntaX grammar of predicate logic is considerably more compleX than the syntaX of sentential logic the method of derivation in System PL is correspondingly more compleX than System SL On the other hand anyone who has already mastered sentential logic deriva tions can also master predicate logic derivations The transition primarily involves 1 getting used to the new symbols and 2 practicing doing the new derivations just like in sentential logic The practical converse unfortunately is also true Anyone who hasn39t already mastered sentential logic derivations will have tremen dous difficulty with predicate logic derivations Of course it39s still not too late to figure out sentential derivations 2 THE RULES OF SENTENTIAL LOGIC We begin by stating the first principle of predicate logic derivations To wit Every rule of System SL sentential logic is also a rule of System PL predicate logic The converse is not true as we shall see in later sections there are several rules peculiar to predicate logic ie rules that do not arise in sentential logic Since predicate logic adopts all the derivation rules of sentential logic it is a good idea to review the salient features of sentential logic derivations First of all the derivation rules divide into two categories on the one hand there are inference rules which are upwardoriented on the other hand there are Show rules which are downwardoriented There are numerous inference rules but they divide into four basic categories Chapter 8 Derivations in Predicate Logic 383 11 Introduction Rules InRules ampI vI lt gtI XI 12 Simple Elimination Rules OutRules amp0 VO gtO lt gtO XO I3 Negation Elimination Rules TildeOutRules ampO vO gtO lt gtO I4 Double Negation Repetition In addition there are four showrules S 1 Direct Derivation S2 Conditional Derivation S3 Indirect Derivation First Form S4 Indirect Derivation Second Form As noted at the beginning of the current section every rule of sentential logic is still operative in predicate logic However when applied to predicate logic the rules of sentential logic look somewhat different but only because the syntax of predicate logic is different In particular instead of formulas that involve only sentential letters and connectives we are now faced with formulas that involve predicates and quantifiers Accordingly when we apply the sentential logic rules to the new formulas they look somewhat different For example the following are all instances of the arrowout rule applied to predicate logic formulas 1 Fa gt Ga Fa Ga 2 Vxe gt VxGx Vxe 3 Fa gt Ga 4 VxFx gt Gx gt 3xe Exe VxFx gt Gx Thus in moving from sentential logic to predicate logic one must first become accustomed to applying the old inference rules to new formulas as in examples l4 384 Hardegree Symbolic Logic The same thing applies to the show rules of sentential logic and their associ ated derivation strategies which remain operative in predicate logic Just as before to show a conditional formula one uses conditional derivation similarly to show a negation or disjunction or atomic formula one uses indirect derivation The only difference is that one must learn to apply these strategies to predicate logic formulas For example consider the following show lines 1 SHOW Fa gt Ga 2 SHOW VXFX gt VXGX 3 SHOW Fa 4 SHOW EXFX amp GX 5 SHOW Rab 6 SHOW VXFX V VXGX Every one of these is a formula for which we already have a readymade derivation strategy In each case either the formula is atomic or its main connective is a sen tential logic connective The formulas in l and 2 are conditionals so we use conditional derivation as follows 1 SHOW Fa gt Ga CD Fa As SHOW Ga 7 2 SHOW VXFXgt VXGX CD VXFX As SHOW VXGX 7 The formulas in 3 and 4 are negations so we use indirect derivation of the first form as follows 3 SHOW Fa ID Fa As SHOW X 7 4 SHOW EXFXamp GX ID EXFX amp GX As SHOW X 7 The formula in 5 is atomic so we use indirect derivation supposing that a direct derivation doesn39t look promising Chapter 8 Derivations in Predicate Logic 385 5 SHOW Rab ID Rab As SHOW X 7 Finally the formula in 6 is a disjunction so we use indirect derivation along with tildewedgeout as follows 6 SHOW Vxev VxGx ID Vxe V VxGx As SHOW X NVxe NVO NVxGx NVO In conclusion since predicate logic subsumes sentential logic all the derivation techniques we have developed for the latter can be transferred to predicate logic On the other hand given the additional logical apparatus of predicate logic in the form of quantifrers we need additional derivation techniques to deal successfully with predicate logic arguments 3 THE RULES OF PREDICATE LOGIC AN OVERVIEW If we confined ourselves to the rules of sentential logic we would be unable to derive any interesting conclusions from our premises All we could derive would be conclusions that follow purely in virtue of sentential logic On the other hand as noted at the beginning of Chapter 6 there are valid arguments that can39t be shown to be valid using only the resources of sentential logic Consider the following valid arguments VxFx gt Hx every Freshman is Happy Fc Chris is a Freshman Hc Chris is Happy VxSx gt Px every Snake is Poisonous VxSx amp Px gt Dx every Poisonous Snake is Dangerous Sm Max is a Snake Dm Max is Dangerous In either example if we try to derive the conclusion from the premises we are stuck very quickly for we have no means of dealing with those premises that are universal formulas They are not conditionals so we can39t use arrowout they are not conjunctions so we can39t use ampersandout etc etc Sentential logic does not provide a rule for dealing with such formulas so we need special rules for the added logical structure of predicate logic 386 Hardegree Symbolic Logic In choosing a set of rules for predicate logic one goal is to follow the general pattern established in sentential logic In particular according to this pattern for each connective we have a rule for introducing that connective and a rule for eliminating that connective Also for each twoplace connective we have a rule for eliminating negations of formulas with that connective In sentential logic with the exception of the conditional for which there is no introduction rule every connective has both an inrule and an outrule and every connective has a tildeout rule There is no arrowin inference rule rather there is an arrow showrule namely conditional derivation In regard to derivations moving from sentential logic to predicate logic basi cally involves adding two sets of oneplace connectives on the one hand there are the universal quantifiers Vx Vy Vz on the other hand there are the existential quantifiers Elx Ely Elz So following the general pattern for rules just as we have three rules for each sentential connective we correspondingly have three rules for universals and three rules for existentials which are summarized as follows Universal Rules 1 Universal Derivation U D 2 UniversalOut VO 3 TildeUniversaIOut VO Existential Rules 1 ExistentialIn 3 2 ExistentialOutGO 3 TildeExistentiaIOut30 Thus predicate logic employs six rules in addition to all of the rules of sen tential logic Notice carefully that five of the rules are inference rules upward oriented rules but one of them universal derivation is a showrule downward oriented rule much like conditional derivation Indeed universal derivation plays a role in predicate logic very similar to the role of conditional derivation in sentential logic Notez Technically speaking ExistentialOut EIO is an assumption rule rather than a true inference rule See Section 10 for an explanation In the next section we examine in detail the easiest of the six rules of predicate logic universalout Chapter 8 Derivations in Predicate Logic 387 4 UNIVERSAL OUT The first and easiest rule we examine is universalelimination universalout for short As its name suggests it is a rule designed to decompose any formula whose main connective is a universal quanti er ie Vx Vy or Vz The official statement of the rule goes as follows UniversalOut VO If one has an available line that is a universal formula which is to say that it has the form VvFv where v is any variable and FM is any formula in which v occurs free then one is entitled to infer any substitution in stance of Fv In symbols this may be pictorially summarized as follows VO VvFv In Here 1 v is any variable x y z 2 n is any name aw 3 Fv is any formula and Fn is the formula that results when n is substi tuted for every occurrence of v that is free in Fv In order to understand this rule it is best to look at a few examples Example 1 Vxe This is by far the easiest example In this v is x and Fv is Fx To obtain a substi tution instance of Fx one simply replaces x by a name any name Thus all of the following follow by VO Fa Fb Fc Fd etc Example 2 VyRyk This is almost as easy In this v is y and Fv is Ryk To obtain a substitution in stance of Ryk one simply replaces y by a name any name Thus all of the following follow by VO Rak Rbk Rck de etc In both of these examples the intuition behind the rule is quite straightforward In Example 1 the premise says that everything is an F but if 388 Hardegree Symbolic Logic everything is an F then any particular thing we care to mention is an F so a is an F b is an F c is an F etc Similarly in Example 2 the premise says that everything bears relation R to k for example everyone respects Kay but if everything bears R to k then any particular thing we care to mention bears R to k so a bears R to k b bears R to k etc In examples 1 and 2 the formula Fv is atomic In the remaining examples Fv is molecular Example 3 VxFx gt Gx In this v is x and Fv is Fx gtGx To obtain a substitution instance we replace both occurrences of x by a name the same name for both occurrences Thus all of the following follow by VO Fa gt Ga Fb gt Gb Fc gt Gc etc In this example the intuition underlying the rule may be less clear than in the first two examples The premise may be read in many ways in English some more colloquial than others r1 every F is G r2 everything is G if it39s F r3 everything is such that if it is F then it is G The last reading r3 says that everything has a certain property namely that if it is F then it is G But if everything has this property then any particular thing we care to mention has the property So a has the property b has the property etc But to say that a has the property is simply to say that if a is F then a is G to say that b has the property is to say that if b is F then b is G Both of these are applications of universalout Example 4 VxEInyy Here v is x and Fv is EInyy To obtain a substitution instance of EInyy one replaces the one and only occurrence of x by a name any name Thus the following all follow by VO EIyRay EIbey EIyRcy EIdey etc The premise says that everything bears relation R to something or other For exam ple it translates the English sentence everyone respects someone or other But if everyone respects someone or other then anyone you care to mention respects someone so a respects someone b respects someone etc Example 5 VxFx gt VxGx Here v is x and Fv is Fx gtVxGx To obtain a substitution instance one replaces every free occurrence of x in Fx gtVxGx by a name In this example the first occurrence is free but the remaining two are not so we only replace the first occurrence Thus the following all follow by VO Fa gt VxGx Fb gt VxGx Fc gt VxGx etc Chapter 8 Derivations in Predicate Logic 389 This example is complicated by the presence of a second quantifier governing the same variable so we have to be especially careful in applying VO Nevertheless one39s intuitions are not violated The premise says that if anyone is an F then every one is a G recall the distinction between if any and if every From this it fol lows that if a is an F then everyone is a G and if b is an F then everyone is a G etc But that is precisely what we get when we apply V0 to the premise 5 POTENTIAL ERRORS IN APPLYING UNIVERSALOUT There are basically two ways in which one can misapply the rule universal out 1 improper substitution 2 improper application In the case of improper substitution the rule is applied to an appropriate for mula namely a universal but an error is made in performing the substitution Refer to the Appendix concerning correct and incorrect substitution instances The following are a few examples of improper substitution 1 VxRxx to infer Rax Rab Rba WRONG 2 VxFx gt Gx to infer Fa gt Gb Fb gt Go WRONG 3 VxFx gt VxGx to infer Fa gt VaGa Fa gt VxGa WRONG In the case of improper application one attempts to apply the rule to a line that does not have the appropriate form Universalout as its name is intended to sug gest applies to universal formulas not to atomic formulas or existentials or nega tions or conditionals or biconditional or conjunctions or disjunctions Recall in this connection a very important principle INFERENCE RULES APPLY EXCLUSIVELY TO WHOLE LINES NOT TO PIECES OF LINES The following are examples of improper application of universalout 4 Vxe gt VxGx to infer Fa gt VxGx WRONG to infer Vxe gt Ga WRONG to infer Fa gt Gb WRONG In each case the error is the same specifically applying universalout to a formula that does not have the appropriate form Now the formula in question is not a universal but is rather a conditional so the appropriate elimination rule is not universalout but rather arrowout which of course requires an additional prem ise 390 Hardegree Symbolic Logic 5 NVxe to infer Fa or Fb or Fc WRONG Once again the error involves applying universalout to a formula that is not a uni versal In this case the formula is a negation Later we will have a rule tilde universalout designed specifically for formulas of this form The moral is that you must be able to recognize the major connective of a for mula is it an atomic formula a conjunction a disjunction a conditional a bicondi tional a negation a universal or an existential Otherwise you can39t apply the rules successfully and hence you can39t construct proper derivations Of course sometimes misapplying a rule produces a valid conclusion Take the following example 6 Vxe gt VxGx to infer Vxe gt Ga to infer Vxe gt Gb etc All of these inferences correspond to valid arguments But many arguments are valid The question at the moment is whether the inference is an instance of uni versal out These inferences are not In order to show that Vxe gtGa follows from Vxe gtVxGx one must construct a derivation of the conclusion from the premise In the next section we examine this particular derivation as well as a number of others that employ our new tool universalout 6 EXAMPLES OF DERIVATIONS USING UNIVERSALOUT Having figured out the universalout rule we next look at examples of deriva tions in which this rule is used We start with the arguments at the beginning of Section 3 Example 1 l VxFx gt Hx Pr 2 F0 Pr 3 SHOW Hc DD 4 Fc gt Hc lVO 5 Ho 24 gto Chapter 8 Derivations in Predicate Logic 391 Example 2 1 VxSx gt PX Pr 2 VxSx amp PX gt Dx Pr 3 Sm Pr 4 SHGW Dm DD 5 Sm gt Pm 1VO 6 Sm amp Pm gt Dm 2VO 7 Pm 35 gtO 8 Sm amp Pm 37ampI 9 Dm 68 gtO The above two examples are quite simple but they illustrate an important strategic principle for doing derivations in predicate logic REDUCE THE PROBLEM TO A POINT WHERE YOU CAN APPLY RULES OF SENTENTIAL LOGIC In each of the above examples we reduce the problem to the point where we can finish it by applying arrowout Notice in the two derivations above that the tool namely universalout is specialized to the job at hand According to universalout if we have a line of the form VvFv we are entitled to write down any instance of the formula Fv So for example in line 4 of the first example we are entitled to write down Fa gtHa Fb gtHb as well as a host of other formulas But of all the formulas we are entitled to write down only one of them is of any use namely Fc gtHc Similarly in the second example we are entitled by universalout to instantiate lines I and 2 respectively to any name we choose But of all the permitted instantiations only those that involve the name m are of any use To say that one is permitted to do something is quite different from saying that one must do it or even that one should do it At any given point in a game say chess one is permitted to make any number of moves but most of them are stupid supposing one39s goal is to win A good chess player chooses good moves from among the legal moves Similarly a good derivation builder chooses good moves from among the legal moves In the first example it is certainly true that Fa gtGa is a permitted step at line 4 but it is pointless because it makes no contribution what soever to completing the derivation By analogy standing on your head until you have a splitting headache and are sick to your stomach is not against the law it39s just stupid In the examples above the choice of one particular letter over any other letter as the letter of instantiation is natural and obvious Other times as you will later see there are several names oating around in a derivation and it may not be obvious which one to use at any given place Under these circumstances one must primarily use trialanderror 392 Hardegree Symbolic Logic Let us look at some more examples In the previous section we looked at an argument that was obtained by a misapplication of universalout As noted there the argument is valid although it is not an instance of universalout Let us now show that it is indeed valid by deriving the conclusion from the premises Example 3 l Vxe gt VxGx Pr 2 SHGW Vxe gt Ga CD 3 Vxe As 4 SHGW Ga DD 5 VxGx l3 gtO 6 Ga 5VO Notice in particular that the formula in 2 is a conditional and is accordingly shown by conditional derivation You are of course already very familiar with conditional derivations to show a conditional you assume the antecedent and show the consequent The following is another example in which a sentential derivation strategy is employed Example 4 l VxFx gt Hx Pr 2 Hb Pr 3 SHGW NVxe ID 4 Vxe As 5 SHGW X DD 6 Fb gt Hb lVO 7 Fb 4VO 8 Hb 67 gtO 9 X 28XI In line 3 we have to show Vxe this is a negation so we use a triedandtrue strategy for showing negations namely indirect derivation To show the negation of a formula one assumes the formula negated and one shows the generic contradiction X We conclude this section by looking at a considerably more complex example but still an example that requires only one special predicate logic rule universal out Chapter 8 Derivations in Predicate Logic 393 Example 5 1 VXFX gt Vnyy Pr 2 VXVyny gt VZGZ Pr 3 Gb Pr 4 SHGW Fa ID 5 Fa As 6 SHGW X DD 7 Fa gt VyRay 1VO 8 VyRay 57 gtO 9 Rab 8VO 10 VyRay gt VZGZ 2VO 11 Rab gt VZGZ 10VO 12 VZGZ 911 gtO 13 Gb 12VO 14 X 313XI If you can figure out this derivation better yet if you can reproduce it yourself then you have truly mastered the universalout rule 7 EXISTENTIAL IN Of the siX rules of predicate logic that we are eventually going to have we have now examined only one universalout In the present section we add one more to the list The new rule eXistential introduction eXistentialin Ell is officially stated as follows ExistentialIn Hi If formula Fn is an available line where Fn is a substitution instance of formula Fv then one is entitled to infer the existential formula 3vFv In symbols this may be pictorially summarized as follows 3 Fn 3vFv Here 1 v is any variable X y z 394 Hardegree Symbolic Logic 2 n is any name aw 3 Fv is any formula and Fn is the formula that results when n is substi tuted for every occurrence of V that is free in Fv ExistentialIn is very much like an upsidedown version of UniversalOut However turning VO upside down to produce EII brings a small complication In VO one begins with the formula Fv with variable v and one substitutes a name 11 for the variable v The only possible complication pertains to free and bound occur rences of v By contrast in EII one works backwards one begins with the substitu tion instance Fn with name 11 and one quotdesubstitutesquot a variable v for 11 Unfortunately in many cases desubstitution is radically different from substitution See examples below As with all rules of derivation the best way to understand EII is to look at a few examples Example 1 have Fb b is F infer EIxe EIyFy 3ze at least one thing is F Here n is b and Fn is Fb which is a substitution instance of three different for mulas Fx Fy and Fz So the inferred formulas which are alphabetic variants of one another see Appendix can all be inferred in accordance with EII In Example 1 the intuition underlying the rule39s application is quite straight forward The premise says that b is F But if b is F then at least one thing is F which is what all three conclusions assert One might understand this rule as saying that if aparlicular thing has a property then at least one thing has that property Example 2 have Rjk j R39s k infer EIxka EIyRyk Elszk something R39s k infer EIijx EIijy Elszz j R39s something Here we have two choices for n j and k Treating j as n Rjk is a substitution instance of three different formulas ka Ryk and Rzk which are alphabetic variants of one another Treating k as n Rjk is a substitution instance of three different formulas ij Rjy and Rj z which are alphabetic variants of one another Thus two different sets of formulas can be inferred in accordance with EII In Example 2 letting R be respects and j be Jay and k be Kay the premise says that Jay respects Kay The conclusions are basically two discounting alphabetic variants someone respects Kay and Jay respects some one Example 3 have Fb amp Hb Here n is b and Fn is FbampHb which is a substitution instance of nine different formulas Chapter 8 Derivations in Predicate Logic 395 fl FxampHxFyamp Hy FZampHZ f2 Fb amp Hx Fb amp Hy Fb amp Hz f3 Fx amp Hb Fy amp Hb FZ amp Hb So the following are all inferences that are in accord with EII infer ExFx amp Hx EyFy amp Hy EZFZ amp HZ infer ExFb amp Hx EyFb amp Hy EZFb amp HZ infer ExFx amp Hb EyFy amp Hb EZFZ amp Hb In Example 3 three groups of formulas can be inferred by EII In the case of the first group the underlying intuition is fairly clear The premise says that b is F and b is H ie b is both F and H and the conclusions variously say that at least one thing is both F and H In the case of the remaining two groups the intuition is less clear These are permitted inferences but they are seldom if ever used in actual derivations so we will not dwell on them here In Example 3 there are two groups of conclusions that are somehow extrane ous although they are certainly permitted The following example is quite similar insofar as it involves two occurrences of the same name However the difference is that the two extra groups of valid conclusions are not only legitimate but also useful Example 4 have Rkk k R39s itself infer EIxRxx EIyRyy Elszz something R39s itself infer EIxka EIyRyk EIszk something R39s k infer EIkax EIyRky Elszz k R39s something Here n is k and Fn is Rkk which is a substitution instance of nine different formulas Rxx ka ka as well as the alphabetic variants involving y and z So the above inferences are all in accord with EII In Example 4 although the various inferences at first look a bit complicated they are actually not too hard to understand Letting R be respects and k be Kay then the premise says that Kay respects Kay or more colloquially Kay re spects herself But if Kay respects herself then we can validly draw all of the fol lowing conclusions cl someone respects herhimself EIxRxx c2 someone respects Kay EIxka c3 Kay respects someone EIkax All of these follow from the premise Kay respects herself and moreover they are all in accord with Ell In all the previous examples no premise involves a quantifier The following is the first such example which introduces a further complication as well 396 Hardegree Symbolic Logic Example 5 have EIkax k R39s something infer EIyEInyx EIzEIszx something R39s something Here n is k and Fn is EIkax which is a substitution instance of two different formulas EInyx and EIszx which are alphabetic variants of one another However in this example there is no alphabetic variant involving the variable x39 in other words EIkax is not a substitution instance of EIxRxx because the latter for mula doesn39t have any substitution instances since it has no free variables In Example 5 letting R be respects and letting k be Kay the prem ise says that someone we are not told who in particular respects Kay The conclu sion says that someone respects someone If at least one person respects Kay then it follows that at least one person respects at least one person Let us now look at a few examples of derivations that employ Ell as well as our earlier rule VO Example 1 1 VxFx gt Hx Pr 2 Fa Pr 3 SHGW EIxHx DD 4 Fa gt Ha WC 5 Ha 24 gtO 6 EIxHx 5331 Example 2 1 VxGx gt Hx Pr 2 Gb Pr 3 SHGW ExGx amp Hx DD 4 Gb gt Hb 1VO 5 Hb 25 gtO 6 Gb amp Hb 25ampI 7 ExGx amp Hx 631 Example 3 1 ExRxa gt ExRax Pr 2 Raa Pr 3 SHGW NRab ID 4 Rab As 5 W x DD 6 ExRxa 231 7 ExRax l6 gtO 8 EIxRax 431 9 x 78XI Chapter 8 Derivations in Predicate Logic 397 Example 4 1 VXEnyy gt Vnyy Pr 2 Raa Pr 3 SHGW Rab DD 4 EIyRay gt VyRay 1VO 5 EIyRay 231 6 VyRay 45 gtO 7 Rab 6VO 8 UNIVERSAL DERIVATION We have now studied two rules universalout and existentialin As stated earlier every connective other than tilde has associated with it three rules an introduction rule an elimination rule and a negationelimination rule In the present section we examine the introduction rule for the universal quantifier The first important point to observe is that whereas the introduction rule for the existential quantifier is an inference rule the introduction rule for the universal quantifier is a Show rule called universal derivation UD compare this with condi tional derivation In other words the rule is for dealing with lines of the form SHOW Vv Suppose one is faced with a derivation problem like the following 1 VXFX gt GX Pr 2 VXFX Pr 3 SHOW VXGX 7 How do to go about completing the derivation At the present given its fonn the only derivation strategies available are direct derivation and indirect derivation second form However in either approach one quickly gets stuck This is be cause as it stands our derivation system is inadequate we cannot derive VXFX with the machinery currently at our disposal So we need a new rule Now what does the conclusion say Well for any X GX says that everything is G This amounts to asserting every item in the following very long list c1 Ga c2 Gb c3 Gc c4 Gd etc This is a very long list one in which every particular thing in the universe is eventually mentioned Of course we run out of ordinary names long before we run out of things to mention so in this situation we have to suppose that we have a truly huge collection of names available 398 Hardegree Symbolic Logic Still another way to think about VXGX is that it is equivalent to a correspond ing in nite conjunction c GaampGbampGcampGdampGeamp where every particular thing in the universe is eventually mentioned Nothing really hinges on the difference between the infinitely long list and the infinite conjunction After all in order to show the conjunction we would have to show every conjunct which is to say that we would have to show every item in the infinite list So our task is to show Ga Gb Gc etc This is a daunting task to say the least Well let39s get started anyway and see what develops l VXFX gt GX Pr 2 VXFX Pr a 3 SHGW Ga DD 4 Fa gt Ga lVO 5 Fa 2VO 6 Ga 45 gtO b 3 SHGW Gb DD 4 Fb gt Gb 1VO 5 Fb 2VO 6 Gb 45 gtO c 3 SHGW Gc DD 4 Fc gt Gc lVO 5 Fc 2VO 6 Gc 45 gtO d 3 SHGW Gd DD 4 Fd gt Gd 1VO 5 Fd 2VO 6 Gd 45 gtO We are making steady progress but we have a very long way to go Fortunately however having done a few we can see a distinctive pattern emerging except for particular names used the above derivations all look the same This is a pattern we can use to construct as many derivations of this sort as we care to for any particular thing we care to mention we can show that it is G So we can eventually show that every particular thing is G Ga Gb Gc Gd etc and hence that everything is G VXGX We have the pattern for all the derivations but we certainly don39t want to indeed we can39t construct all of them How many do we have to do in order to be finished 5 25 100 Well the answer is that once we have donejusl one deri Chapter 8 Derivations in Predicate Logic 399 vation we already have the pattern model mould for every other derivation so we can stop after doing just one The rest look the same and are redundant in effect This leads to the first but not final formulation of the principle of universal derivation Universal Derivation First Approximation In order to show a universal formula which is to say a formula of the form VvFv it is sufficient to show a substitution instance Fn of Fv This is not the whole story as we will see shortly However before facing the complication let39s see what universal derivation so stated allows us to do First we offer two equivalent solutions to the original problem using universal derivation Example 1 a l VXFx gt GX Pr 2 VXFX Pr 3 SHGW VXGX UD 4 SHGW Ga DD 5 Fa gt Ga lVO 6 Fa 2VO 7 Ga 56 gtO b l VXFx gt GX Pr 2 VXFX Pr 3 SHGW VXGX UD 4 W Gb DD 5 Fb gt Gb lVO 6 Fb 2VO 7 Gb 56 gtO Each example above uses universal derivation to show VXGX In each case the overall technique is the same one shows a universal formula VvFv by showing a substitution instance Fn of Fv In order to solidify this idea let39s look at two more examples Example 2 l VXFX gt GX Pr 2 SHGW VXFX gt VXGX CD 3 VXFX As 4 SHGW VXGX UD 5 SHGW Ga DD 6 Fa gt Ga lVO 7 Fa 3VO 8 Ga 67 gtO 400 Hardegree Symbolic Logic In this example line 2 asks us to show Vxe gtVxGx One might be tempted to use universal derivation to show this but this would be completely wrong Why Because Vxe gtVxGx is not a universal formula but rather a conditional Well we already have a derivation technique for showing conditionals conditional derivation That gives us the next two lines we assume the antecedent and we show the consequent So that gets us to line 4 which is to show VxGx39 Now this formula is indeed a universal so we use universal derivation this means we immediately write down a further showline SHOW Ga we could also write SHOW Gb or SHOW Gc etc This is shown by direct derivation Example 3 l VxFx gt Gx Pr 2 VxGx gt Hx Pr 3 SHGW VxFx gt Hx UD 4 SHGW Fa gt Ha CD 5 Fa As 6 SHGW Ha DD 7 Fa gt Ga 1VO 8 Ga gt Ha 2VO 9 Ga 57 gtO 10 Ha 89 gtO In this example we are asked to show VxFx gtGx which is a universal formula so we show it using universal derivation This means that we immediately write down a new show line in this case SHOW Fa gtHa notice that Fa gtHa is a substitution instance of Fx gtHx Remember to show VvFv one shows Fn where Fn is a substitution instance of Fv Now the problem is to show Fa gtHa this is a conditional so we use conditional derivation Having seen three successful uses of universal derivation let us now examine an illegitimate use Consider the following quotproof39 of a clearly invalid argument Example 4 Invalid Argument 1 Fa amp Ga Pr 2 SHOW VxGx UD 3 SHOW Ga DD WRONG 4 Ga 1ampo First of all the fact that a is F and a is G does not logically imply that every thing or everyone is G From the fact that Adams is a Freshman who is Gloomy it does not follow that everyone is Gloomy Then what went wrong with our tech nique We showed VxGx by showing an instance of Gx namely Ga An important clue is forthcoming as soon as we try to generalize the above erroneous derivation to any other name In the Examples 13 the fact that we use a is completely inconsequential we could just as easily use any name and the derivation goes through with equal success But with the last example we can in deed show Ga but that is all we cannot show Gb or Gc or Gd But in order to dem Chapter 8 Derivations in Predicate Logic 401 onstrate that everything is G we have to show in effect that a is G b is G c is G etc In the last example we have actually only shown that a is G In Examples 13 doing the derivation with a was enough because this one derivation serves as a model for every other derivation Not so in Example 4 But what is the difference When is a derivation a model derivation and when is it not a model derivation Well there is at least one conspicuous difference between the good derivations and the bad derivation above In every good derivation above no name appears in the derivation before the universal derivation whereas in the bad derivation above the name a appears in the premises This can39t be the whole story however For consider the following perfectly good derivation Example 5 1 Fa amp Ga Pr 2 VxFx gt VyGy Pr 3 VxGx gt Fx Pr 4 SHGW Vxe UD 5 SHGW Fb DD 6 Fa lampO 7 Fa gt VyGy 2VO 8 VyGy 67 gtO 9 Gb 8VO 10 Gb gt Fb 3VO l l Fb 910 gtO In this derivation which can be generalized to every name a name occurs earlier but we refrain from using it as our instance at line 5 We elect to show not just any instance but an instance with a letter that is not previously being used in the derivation We are trying to show that everything is F we already know that a is F so it would be no good merely to show that we show instead that b is F This is better because we don39t know anything about b so whatever we show about b will hold for everything We have seen that universal derivation is not as simple as it might have looked at first glance The first approximation which seemed to work for the first three examples is that to show VvFv one merely shows Fn where Fn is any substi tution instance But this is not right If the name we choose is already in the derivation then it can lead to problems so we must restrict universal derivation accordingly As it turns out this adjustment allows Examples l235 but blocks Example 4 Having seen the adjustment required to make universal derivation work we now formally present the correct and final version of the universalelimination rule The crucial modification is marked with an V 402 Hardegree Symbolic Logic Universal Derivation Intuitive Formulation In order to show a universal formula which is to say a formula of the form VvFv it is sufficient to show a substitution instance Fn of FM V where n is any new name which is to say that n does not appear anywhere earlier in the derivation As usual the official formulation of the rule is more complex Universal Derivation Official Formulation If one has a showline of the form SHOW VvFv then if one has SHeW Fn as a later available line where Fn is a substitution instance of FM and n is a new name and there are no intervening uncancelled show line then one may box and cancel SHOW VvFv The annotation is UD In pictorial terms similar to the presentations of the other derivation rules DD CD ID universal derivation UD may be presented as follows SHeW VvFv UD SHeW Fn n must be new ie it cannot occur in any previous line including the line SHOW VvFv We conclude this section by examining an argument that involves relational quantification This example is quite complex but it illustrates a number of impor tant points Chapter 8 Derivations in Predicate Logic 403 Example 6 1 Raa Pr 2 VXVyny gt VXVnyy Pr 3 SHGW VXVyRyX UD 4 SHGW VyRyb UD 5 SHGW Rcb DD 6 VyRay gt VXVnyy 2VO 7 Raa gt VXVnyy 6VO 8 VXVnyy 17 gtO 9 VyRcy 8VO 10 Rob 9VO Analysis 3 SHOW VXVyRyX 4 5 6 7 8 9 this is a universal VXVyRyX so we show it by UD which is to say that we show an instance of VyRyX where the name must be new Only a is used so far so we use the next letter b yielding SHOW VyRyb this is also a universal VyRyb so we show it by UD which is to say that we show an instance of Ryb where the name must be new Now both a and b are already in the derivation so we can39t use either of them So we use the next letter c yielding SHOW Rcb This is atomic We use either DD or ID DD happens to work Line 1 is VXVyny gt VXVnyy which is a universal VXVyny gt VXVnyy so we apply V0 The choice of letter is completely free so we choose a replacing every free occurrence of X by a yielding VyRay gt VXVnyy This is a universal VyRay gt VXVnyy so we apply V0 The choice of letter is completely free so we choose a replacing every free occurrence of X by a yielding Raa gt VXVnyy This is a conditional so we apply gtO in conjunction with line 1 which yields VXVnyy This is a universal VXVnyy so we apply VO instantiating X to c yielding VyRcy This is a universal VyRcy so we apply VO instantiating y to b yielding 404 Hardegree Symbolic Logic 10 Rcb This is what we wanted to show By way of concluding this section let us review the following points Having VvFv as an available line is very different from having SHOW VvFv as a line In one case you have VvFv in the other case you don39t have VvFv rather you are trying to show it VO applies when you have a universal you can use any name whatsoever UD applies when you want a universal you must use a new name 9 EXISTENTIAL OUT We now have three rules we have both an elimination out and an introduc tion in rule for V and we have an introduction rule for El At the moment how ever we do not have an elimination rule for El That is the topic of the current sec tion Consider the following derivation problem 1 VXFX gt HX Pr 2 EIXFX Pr 3 SHOW EIXHX 7 One possible English translation of this argument form goes as follows 1 every Freshman is happy 2 at least one person is a Freshman 3 therefore at least one person is happy This is indeed a valid argument But how do we complete the corresponding derivation The problem is the second premise which is an eXistential formula At present we do not have a rule specifically designed to decompose eXistential formulas How should such a rule look Well the second premise is EIXFX which says that some thing at least one thing is F however it is not very specific it doesn39t say which particular thing is F We know that at least one item in the following in finite list is true but we don39t know which one it is Chapter 8 Derivations in Predicate Logic 405 1 Fa 2 Fb 3 Fc 4 Fd etc Equivalently we know that the following in nite disjunction is true d Favachdev v Once again we pretend that we have sufficiently many names to cover every single thing in the universe The second premise EIXFX says that at least one thing is F some thing is F but it provides no further information as to which thing in particular is F Is it a Is it b We don39t know given only the information conveyed by EIXFX So what hap pens if we simply assume that a is F Adding this assumption yields the following substitute problem 1 VXFX gt HX Pr 2 EIXFX Pr 3 SHOW EIXHX DD 4 Fa I write because the status of this line is not obvious at the moment Let us proceed anyway Well now the problem is much easier The following is the completed derivation a l VXFX gt HX Pr 2 EIXFX Pr 3 SHGW EIXHX DD 4 Fa 5 Fa gt Ha lVO 6 Ha 45 gtO 7 EIXHX 631 In other words if we assume that the something that is F is in fact a then we can complete the derivation The problem is that we don39t actually know that a is F but only that something is F Well then maybe the something that is F is in fact b So let us instead assume that b is F Then we have the following derivation b l VXFX gt HX Pr 2 EIXFX Pr 3 SHGW EIXHX DD 4 Fb 5 Fb gt Hb 1VO 6 Hb 45 gtO 7 EIXHX 631 406 Hardegree Symbolic Logic Or perhaps the something that is F is actually c so let us assume that c is F in which case we have the following derivation c l VXFX gt HX Pr 2 EIXFX Pr 3 SHGW EIXHX DD 4 Fc 5 Fc gt Hc lVO 6 Hc 45 gtO 7 EIXHX 631 A definite pattern of reasoning begins to appear We can keep going on and on It seems that whatever it is that is actually an F and we know that something is we can show that something is H For any particular name we can construct a derivation using that name All the resulting derivations would look virtually the same the only difference being the particular letter introduced at line 4 The generality of the above derivation is reminiscent of universal derivation Recall that a universal derivation substitutes a single model derivation for infinitely many derivations all of which look virtually the same The above pattern looks very similar the first derivation serves as a model of all the rest Indeed we can recast the above derivations in the form of UD by inserting an extra showline as follows Remember that one is entitled to write down any show line at any point in a derivation u l VXFX gt HX Pr 2 EIXFX Pr 3 SHGW EIXHX DD 4 SHGW VXFX gt EIXHX UD 5 SHGW Fa gt EIXHX CD 6 Fa As 7 SHGW EIXHX DD 8 Fa gt Ha lVO 9 Ha 68 gtO 10 EIXHX 931 11 EIXHX 24 The above derivation is clear until the very last line since we don39t have a rule that deals with lines 2 and 4 In English the reasoning goes as follows 2 at least one thing is F 4 if anything is F then at least one thing is H 10 therefore at least one thing is H Without further ado let us look at the eXistentialelimination rule Chapter 8 Derivations in Predicate Logic 407 ExistentialOut 30 If a line of the form 3vFv is available then one can assume any substitution instance Fn of FM so long as n is a name that is newto the derivation The annotation cites the line number plus 30 The following is the cartoon version HO 3vFv n must be new ie it cannot occur in Fn any previous line including the line 3vFv Note on annotation When applying EIO the annotation appeals to the line number of the existential formula EIVFV and the rule EIO In other words even though EIO is an assumption rule and not a true inference rule we annotate derivations as if it were a true inference rule see below Before worrying about the proviso so long as n is let us go back now and do our earlier example now using the rule EIO The crucial line is marked by V Example 1 l VxFx gt Hx Pr 2 3xe Pr 3 SHGW EIxHx DD V 4 Fa 230 5 Fa gt Ha LVO 6 Ha 45 gtO 7 EIxHx 631 In line 4 we apply EIO to line 2 instantiating x to a note that a is a new name The following are two more examples of EIO 408 Hardegree Symbolic Logic Example 2 1 VXFX gt GX 2 EIXFX amp HX 3 SHGW EIXGX amp HX 4 Fa amp Ha 5 Fa 6 Ha 7 Fa gt Ga 8 Ga 9 Ga amp Ha 10 EIXGX amp HX Example 3 1 VXFX gt GX 2 VXGX gt NHX 3 SHGW ExFX amp HX 4 EIXFX amp HX 5 SHQW X 6 Fa amp Ha 7 Fa 8 Ha 9 Fa gt Ga 10 Ga 11 Ga gt Ha 12 Ha 13 X Pr Pr DD 2EO 4ampO 4ampO 1VO 57 gtO 68ampI 931 DD 430 6ampO 6ampO 1VO 79 gtO 2VO 1011 gto 812XI Examples 2 and 3 illustrate an important strategic principle in constructing derivations in predicate logic In Example 3 when we get to line 6 we have many rules we can apply including V0 and EIO Which should we apply first The fol lowing are two rules of thumb for dealing with this problem Remember a rule of thumb is just that it does not work 100 of the time Rule of Thumb 1 Don39t apply VO unless until you have a name in the derivation to which to apply it Rule of Thumb 2 If you have a choice between applying V0 and applying HO apply 30 first Chapter 8 Derivations in Predicate Logic 409 The second rule is in some sense an application of the first rule If one has no name to apply V0 to then one way to produce a name is to apply EIO Thus one first applies EIO thus producing a name and then applies VO What happens if you violate the above rules of thumb Well nothing very bad you just end up with extraneous lines in the derivation Consider the following derivation which contains a violation of Rules 1 and 2 Example 2 revisited l VxFx gt Gx Pr 2 ExFx amp Hx Pr 3 SHGW ExGx amp Hx DD V Fa gt Ga lVO 4 Fb amp Hb 230 b is new a isn39t 5 Fb 4ampO 6 Hb 4ampO 7 Fb gt Gb lVO 8 Gb 57 gtO 9 Gb amp Hb 68ampI 10 ExGx amp Hx 931 The line marked V is completely useless it just gets in the way as can be seen immediately in line 4 This derivation is not incorrect it would receive full credit on an exam supposing it was assigned rather it is somewhat disfigured In Examples 13 there are no names in the derivation except those introduced by EIO At the point we apply EIO there aren39t any names in the derivation so any name will do Thus the requirement that the name be new is easy to satisfy However in other problems additional names are involved and the requirement is not trivially satisfied Nonetheless the requirement that the name be new is important because it blocks erroneous derivations and in particular erroneous derivations of invalid ar guments Consider the following Invalid argument A 3xe EIxGx ExFx amp Gx at least one thing is F at least one thing is G at least one thing is both F and G There are many counterexamples to this argument consider two of them Counterexamples at least one number is even at least one number is odd at least one number is both even and odd 410 Hardegree Symbolic Logic at least one person is female at least one person is male at least one person is both male and female Argument A is clearly invalid However consider the following erroneous derivation Example 4 erroneous derivation 1 2 3 4 5 6 7 3xe Pr 3xGx Pr SHOW 3XFX amp GX DD Fa 130 Ga 230 Fa amp Ga 45ampl 3XFX amp GX 631 WRONG The reason line 5 is wrong concerns the use of the name a which is defi nitely not new since it appears in line 4 To be a proper application of 30 the name must be new so we would have to instantiate GX to Gb or Gc anything but Ga When we correct line 5 the derivation looks like the following 1 2 3 4 5 6 3xe Pr 3xGx Pr SHOW 3XFX amp GX DD Fa 130 Gb 230 RIGHT but we can39t finish Now the derivation cannot be completed but that is good because the argument in question is after all invalid The previous examples do not involve multiply quantified formulas so it is probably a good idea to consider some of those Example 5 l VXFX gt 3yHy Pr 2 SHGW 3XFX gt 3yHy CD 3 3XFX As 4 SHGW 3yHy DD 5 Fa 330 6 Fa gt 3yHy lV0 7 3yHy 56 gt0 As noted in the previous chapter the premise may be read if anything is F then something is H whereas the conclusion may be read if something is F then something is H Chapter 8 Derivations in Predicate Logic 411 Under very special circumstances if any is equivalent to if some this is one of the circumstances These two are equivalent We have shown that the latter follows from the former To balance things we now show the converse as well Example 6 l 3xe gt 3yHy Pr 2 SHGW VXFX gt 3yHy UD 3 SHGW Fa gt 3yHy CD 4 Fa As 5 SHGW 3yHy DD 6 3xe 431 7 3yHy l6 gt0 Before turning to examples involving relational more example involving multiple quantification Example 7 l 3xe gt VXNGX Pr 2 SHGW VXFX gt 3yGy UD 3 SHGW Fa gt 3yGy CD 4 Fa As 5 SHGW 3yGy ID 6 3yGy As 7 SHGW X DD 8 Gb 630 9 3xe 431 10 VXNGX l9 gt0 l l Gb 10 V0 12 X 81 lX1 quantification we do one As in many previous sections we conclude this section with some examples that involve relational quantification Example 8 l VxVyny gt ny Pr 2 3x3nyy Pr 3 SHGW 3x3nyy DD 4 3yKay 230 5 Kab 430 6 VyKay gt Ray lV0 7 Kab gt Rab 6V0 8 Rab 57 gt0 9 3yRay 831 10 3x3nyy 931 412 Hardegree Symbolic Logic Example 9 1 VXEInyy Pr 2 VXVyny gt RXX Pr 3 VXRXX gt VyRyX Pr 4 SHOW VXVnyy UD 5 SHGW VyRay UD 6 SHGW Rab DD 7 EIbey 1VO 8 Rbc 7EO 9 VyRby gt Rbb 2VO 10 Rbc gt Rbb 9VO 1 1 Rbb 89 gtO 12 Rbb gt VyRyb 3VO 13 VyRyb 1112 gtO 14 Rab 13VO 10 HOW EXISTENTIALOUT DIFFERS FROM THE OTHER RULES As stated in the previous section although we annotate eXistentialout just like other elimination rules like gtO V0 V0 etc it is not a true inference rule but is rather an assumption rule In the present section we show exactly how EIO is dif ferent from the other rules in predicate and sentential logic First consider a simple application of the rule VO VXFX Fa This is a valid argument of predicate logic and the corresponding derivation is triv ial 1 VXFX Pr 2 SHGW Fa DD 3 IFa 2vo Next consider a simple application of the rule Ell Fa EXFX Again the argument is valid and the derivation is trivial Chapter 8 Derivations in Predicate Logic 413 1 Fa Pr 2 SHGW EIXFX DD 3 EIXFX l EII The same can be said for every inference rule of predicate logic and sentential logic Speci cally every inference rule corresponds to a valid argument In each case we derive the conclusion simply by appealing to the rule in question But what about EIO Does it correspond to a valid argument Earlier I men tioned that although the notation makes it look like VO it is not really an inference rule but is rather an assumption rule much like the assumption rules associated with CD and ID Why is it not a true inference rule The answer is that it does not correspond to a valid argument in predicate logic The argument form is the following EXFX Fa In English this reads as follows something is F therefore a is F That this argument form is invalid is seen by observing the following counterexam ple l someone is a pacifist 2 therefore Adolf Hitler is a pacifist If one has EIXFX one is entitled to assume Fa so long as a is new So we can assume for the sake of argument that Hitler is a pacifist but we surely cannot de duce the false conclusion that Hitler iswas a pacifist from the true premise that at least one person is a pacifist The argument is invalid but one might still wonder whether we can nonethe less construct a derivation quotprovingquot it is in fact valid If we could do that then our derivation system would be inconsistent and useless so let39s hope we cannot Well can we derive Fa from EIXFX If we follow the pattern used above first we write down the problem then we solve it simply by applying the appropriate rule of inference Following this pattern the derivation goes as follows 1 EIXFX Pr 2 SHOW Fa DD 3 IFa 130 WRONG This derivation is erroneous because in line 3 a is not a permitted substitution according to the EIO rule because the letter used is not new since a already appears in line 2 We are permitted to write down Fb Fc Fd or a host of other formulas but none of these makes one bit of progress toward showing Fa That is good because Fa does not follow from the premise 414 Hardegree Symbolic Logic Thus in spite of the notation EIO is quite different from the other rules When we apply EIO to an existential formula say EIXFX to obtain a formula say Fc we are not inferring or deducing Fc from EIXFX After all this is not a valid inference Rather we are writing down an assumption Some assumptions are permitted and some are not this is an example of a permitted assumption provided of course the name is new just like assuming the antecedent in conditional derivation 11 NEGATION QUANTIFIER ELIMINATION RULES Earlier in the chapter I promised siX rules and now we have four of them The remaining two are tildeeXistentialout and tildeuniversalout As their names are intended to suggest the former is a rule for eliminating any formula that is a negation of an eXistential formula and the latter is a rule for eliminating any formula that is a negation of a universal formulas These rules are officially given as follows TildeExistentialOut 30 If a line of the form 3vFv is available then one can inferthe formula VvFv TildeUniversalOut VO If a line of the form VvFv is available then one can inferthe formula 3VFv Schematically these rules may be presented as follows Before continuing we observe is that both of these rules are derived rules which is to say that they can be derived from the previous rules In other words Chapter 8 Derivations in Predicate Logic 415 these rules are completely dispensable any conclusion that can be derived using either rule can be derived without using it They are added for the sake of conven ience First let us consider 30 and let us consider its simplest instance where Fv is FX Then EO amounts to the following argument Argument 1 NEIXFX it is not true that there is at least one thing such that it is F therefore VXNFX everything is such that it is not F Recall from the previous chapters that the colloquial translation of the premise is nothing is F and the colloquial translation of the conclusion is everything is unF The following derivation demonstrates that Argument 1 is valid by deducing the conclusion from the premise l NEIXFX Pr 2 SHGW VXNFX UD 3 SHGW Fa ID 4 Fa As 5 SHGW X DD 6 EIXFX 431 7 X 16XI Next let us consider NVO and let us consider the simplest instance Argument 2 NVXFX it is not true that everything is such that it is F therefore EIXNFX there is at least one thing such that it is not F Recall from the previous chapter that the colloquial translation of the premise is not everything is F and the colloquial translation of the conclusion is something is not F The following derivation demonstrates that Argument 2 is valid It employs lines 1 5 11 a seldomused sentential logic strategy 416 Hardegree Symbolic Logic 1 2 3 4 5 6 7 8 9 10 V 11 NVXFX Pr SHGW EIXNFX ID NEIXNFX As SHGW X DD SHGW VXFX UD SHGW Fa ID Fa As SHGW X DD EIXNFX 7EI X 39XI X 15XI In each derivation we have only shown the simplest instance of the rule where Fv is FX However the complicated instances are shown in precisely the same manner We can in principle show for any formula Fv and variable v that VvFv follows from EvFv and that EvFv follows from VvFv Note that the converse arguments are also valid as demonstrated by the following derivations 1 2 3 4 5 6 7 1 2 3 4 5 6 7 VXNFX Pr SHGW NEIXFX ID EIXFX As SHGW X DD Fa 3EO Fa lVO X 56XI EIXNFX Pr SHGW NVXFX ID VXFX As SHGW X DD Fa lEO Fa 3VO X 56XI Note carefully however that neither of the converse arguments corresponds to any rule in our system In particular THERE IS NO RULE TILDEEXISTENTIALIN THERE IS NO RULE TILDEUNIVERSALIN The corresponding arguments are valid and accordingly can be demonstrated in our system However they are not inference rules As usual not every valid argument form corresponds to an inference rule This is simply a choice we make we only Chapter 8 Derivations in Predicate Logic 417 have negationconnective elimination rules and no negationconnective introduction rules Before proceeding let us look at several applications of EO and NVO to specific formulas in order to get an idea of What the syntactic possibilities are l Exe VxFx 2 ExFx amp Gx VxFx amp Gx 3 ExFx amp VyGy gt ny VxFx amp VyGy gt ny 4 NVxe ExFx 5 VxFx gt Gx ExFx gt Gx 6 VxFx gt EyGy amp ny ExFx gt EyGy amp ny Having seen several examples of proper applications of EO or NVO it is probably a good idea to see examples of improper applications 7 EIxe V EIyGy WRONG VXNFX v EIyGy 8 Exe gt VxGx WRONG VxFx gt VxGx In each example the error is that the premise does not have the correct form In 7 the premise is a negation of a disjunction not a negation of an existential The ap propriate rule is NVO not 30 In 8 the premise is a conditional so the appro priate rule is gtO Of course sometimes an improper application of a rule produces a valid con clusion and sometimes it does not 8 is a valid argument but so are a lot of argu ments The question here is not Whether the argument is valid but Whether it is an application of a rule Some valid arguments correspond to rules and hence do not have to be explicitly shown other valid arguments do not correspond to particular rules and hence must be shown to be valid by constructing a derivation Recall as usual 418 Hardegree Symbolic Logic INFERENCE RULES APPLY EXCLUSIVELY TO WHOLE LINES NOT TO PIECES OF LINES 8 is valid so we can derive its conclusion from its premise The following is one such derivation It also illustrates a further point about our new rules Example 1 l NEIXFX gt VXGX 2 SHGW VXNFX gt VXGX 3 VXNFX V 4 W VXGX 5 N VXGX 6 SHGW X 7 N N EIxe 8 EIxe 9 Fa 10 NFa l l X This derivation is curious in the following way derivation rather than universal derivation suitable for any kind of formula Pr CD As ID As DD 15 gtO 7DN 830 3VO 910XI line 4 is shown by indirect But this is permissible since ID is Indeed once we have the rule NVO we can show any universal formula by ID By way of illustration consider Example 2 from Section 7 first done using UD then done using ID Example 2 done using UD 1 2 3 V 4 5 6 7 8 VXFX gt Gx SHGW VXFX gt VXGX VXFX SHGW VXGX SHGW Ga Fa gt Ga Fa Ga CD As UD DD 1VO 3VO 67 gtO Chapter 8 Derivations in Predicate Logic 419 Example 2 done using ID 1 VxFx gt Gx Pr 2 SHGW Vxe gt VxGx CD 3 Vxe As gt 4 W VXGX ID 5 NVxGx As 6 SHGW X DD 7 3xGx 5V0 8 NGa 730 9 Fa gt Ga 1V0 10 Fa 3V0 11 Ga 910 gt0 12 X 811XI Now that we have NVO it is always possible to show a universal by indirect derivation However the resulting derivation is usually longer than the derivation using universal derivation On rare occasions the indirect derivation is easier for example go back and try to do Example 1 using universal derivation We conclude this section with a derivation that uses V0 in a straightforward way it also involves relational quantification Example 3 1 VxVnyy gt NVyRyx Pr 2 3xVnyy Pr 3 SHGW 3x3yny DD 4 VyRay 230 5 VyRay gt NVyRya 1V0 6 NVyRya 45 gt0 V 7 3yRya 6V0 8 Rba 730 9 3yRby 831 10 3x3yny 931 420 Hardegree Symbolic Logic 12 DIRECT VERSUS INDIRECT DERIVATION OF EXISTENTIALS Adding NVO to our list of rules enables us to show universals using indirect derivation This particular use of NVO is really no big deal since we already have a derivation technique ie universal derivation that is perfect for universals Whereas we have a derivation scheme showrule specially designed for uni versal formulas we do not have such a rule for existential formulas You may have noticed that in every previous example involving SHOW EIvFv we have used direct derivation This corresponds to a derivation strategy which is schematically presented as follows Direct Derivation Strategy for Existentials SHeW 3vFv DD Fin 3vFv 3 But now we have an additional rule 30 so we can show any existential formula using indirect derivation This gives rise to a new strategy which is schematically presented as follows Indirect Derivation Strategy for Existentials SHeW 3vFv ID 3vFv As SHGW X DD VvFv 30 x Many derivation problems can be solved using either strategy For example recall Example 1 from Section 8 Chapter 8 Derivations in Predicate Logic 421 Example 1d DD strategy 1 VXFX gt HX Pr 2 EIXFX Pr 3 SHGW EIXHX DD 4 Fa 230 5 Fa gt Ha 1VO 6 Ha 45 gtO 7 EIXHX 631 Example 1i ID strategy 1 VXFX gt HX Pr 2 EIXFX Pr 3 SHGW EIXHX ID 4 NEIXHX As 5 SHGW X DD 6 VXNHX 4EO 7 Fa 230 8 Fa gt Ha 1VO 9 Ha 78 gtO 10 Ha 6VO 11 X 910XI Comparing these two derivations illustrates an important point Even though we can use the ID strategy it may end up producing a longer derivation than if we use the DD strategy instead On the other hand there are derivation problems in which the DD strategy will not work in a straightforward way recall that every indirect derivation can be con verted into a quottrickquot derivation that does not use ID in these problems it is best to use the ID strategy Consider the following example besides illustrating the ID strategy for existentials it also recalls an important sentential derivation strategy 422 Hardegree Symbolic Logic Example 2 V 1 EIXFX v EIXGX Pr V 2 SHGW EXFX GX ID 3 EXFX V GX As 4 SHGW X DD 5 VXFX V GX 3EO V 6 W 3xe ID 7 EIXFX As 8 SHGW X DD 9 Fa 730 10 Fa v Ga 5VO 11 Fa 10vO 12 X 911XI gt 13 EIXGX 16VO 14 Gb 13EO 15 Fb v Gb 5VO 16 Gb 15vO 17 X 1416XI Recall the wedgeout strategy from sentential logic WedgeOut Strategy If you have a disjunction for example it is a premise then you try to nd or show the negation of one of the disjuncts We are following the wedgeout strategy in line 6 While we are on the topic of sentential derivation strategies let us recall two other strategies the first being the wedgederivation strategy which is schematically presented as follows WedgeDerivation Strategy SHGW it v 3 ID t v B As W x DD Nil NVO NB NVO x XI Chapter 8 Derivations in Predicate Logic 423 This strategy is employed in the following example which is the converse of 2 Example 2c 1 ExFx v Gx Pr 2 SHGW 3xe v EIxGx ID 3 EIxe V EIxGx As 4 SHGW X DD 5 Exe 3O 6 3xGx 3O 7 VxFx 5EO 8 VxGx 6EO 9 Fa v Ga lEO 10 Fa 7VO l l Ga 8VO 12 Ga 910O 13 X lll2Xl Another sentential strategy is the arrowout strategy which is given as follows ArrowOut Strategy If you have a conditional for example it is a premise then you try to nd or show either the antecedent or the negation of the consequent The following example illustrates the arrowout strategy it also reiterates a point made in Chapter 6 namely that an existentialconditional formula eg ExFx gt Gx does not say much and certainly does not say that some F is G 424 Hardegree Symbolic Logic Example 3 gt 1 VXFX gt EIXGX Pr gtgt 2 SHGW ExFx gt GX ID 3 ExFx gt GX As 4 SHGW X DD 5 VxFx gt Gx 3EO V 6 W VXFX UD 7 SHGW Fa DD 8 Fa gt Ga 5VO 9 Fa amp Ga 8 gtO 10 Fa 9ampO gt 11 EIXGX 16 gtO 12 Gb 11EO 13 Fb gt Gb 5VO 14 Fb amp Gb 13 gtO 15 Gb 14ampO 16 X 1215XI In line 6 above we apply the arrowout strategy electing in particular to show the antecedent The converse of the above argument can also be shown as follows which demonstrates that EIxFx gtGx is equivalent to Vxe gtExGx which says that something is G if everything is F Example 3c 1 EIXFX gt GX Pr 2 SHGW VXFX gt EIXGX CD 3 VXFX As 4 SHGW EIXGX ID 5 NEIXGX As 6 SHGW X DD 7 VXNGX 5EO 8 Fa gt Ga 1EO 9 Fa 3VO 10 Ga 7VO 11 Ga 89ampI 12 X 1011XI Note carefully that the ID strategy is used at line 4 but only for the sake of illus trating this strategy If one uses the DD strategy then the resulting derivation is much shorter This is left as an exercise for the student The last several examples of the section involve relational quantification Many of the problems are done both with and without ID Example 4 1 there is a Freshman who respects every Senior 2 therefore for every Senior there is a Freshman who respects himher Chapter 8 Derivations in Predicate Logic 425 Example 4d DD strategy 1 EIXFX amp VySy gt ny 2 SHGW VXSX gt EyFy amp RyX 3 SHGW Sa gt 3yFy amp Rya 4 Sa V 5 W ElyFy amp Rya 6 Fb amp VySy gt Rby 7 Fb 8 VySy gt Rby 8 Sa gt Rba 9 Rba 10 Fb amp Rba 11 3yFy amp Rya Example 4i ID strategy 1 EIXFX amp VySy gt ny 2 SHGW VXSX gt EyFy amp RyX 3 SHGW Sa gt 3yFy amp Rya 4 Sa V 5 W ElyFy amp Rya 6 3yFy amp Rya 7 W x 8 VyFy amp Rya 9 Fb amp VySy gt Rby 10 Fb 11 VySy gt Rby 12 Fb amp Rba 13 Sa gt Rba 14 Rba 15 Fb gt Rba 16 Rba 17 x UD CD As DD 13O 6ampO 6ampO 8VO 48 gtO 79ampI 103I Pr UD CD As ID As DD 63O 13O 9ampO 9ampO 8VO 11VO 413 gto 12ampo 1015 gto 1416XI Note that this derivation can be shortened by two lines at the end exercise for the student The previous problem was solved using both ID and DD The next problem is done both ways as well 426 Hardegree Symbolic Logic Example 5 1 there is someone who doesn39t respect any Freshman 2 therefore for every Freshman there is someone who doesn39t respect himher Example 5d DD strategy 1 ExEyFy amp Ryx Pr 2 SHGW VXFX gt EIyNny UD 3 SHGW Fa gt EIyNRay CD 4 Fa As gt 5 31461717 EIyNRay DD 6 EyFy amp Ryb 1EO 7 VyFy amp Ryb 6EO 8 Fa amp Rab 7VO 9 Fa gt NRab 8ampO 10 NRab 49 gtO 11 EIyNRay 10EI Example 5i ID strategy 1 ExEyFy amp Ryx Pr 2 SHGW VXFX gt EIyNny UD 3 SHGW Fa gt EIyNRay CD 4 Fa As gt 5 31461717 EIyNRay ID 6 NEIyNRay As 7 SHGW X DD 8 Vy NRay 6EO 9 EyFy amp Ryb 1EO 10 VyFy amp Ryb 9EO 11 Fa amp Rab 10VO 12 Fa gt NRab 11ampO 12 N NRab 8VO 14 Fa 1213 gtO 15 X 414XI The final example of this section is considerably more complex than the previ ous ones It is done only once using ID Using the ID strategy is hard enough using the DD strategy is also hard try it and see Chapter 8 Derivations in Predicate Logic 427 Example 6 1 every Freshman respects Adams 2 there is a Senior who doesn39t respect any one who respects Adams 3 therefore there is a Senior who doesn39t respect any Freshman 1 VXFX gt Rxa Pr 2 EXSX amp EyRya amp ny Pr gt 3 SHGW EXSX amp EyFy amp ny ID 4 EXSX amp EyFy amp ny As 5 SHGW X DD 6 VXSX amp EyFy amp ny 4EO 7 Sb amp EyRya amp Rby 2EO 8 Sb 7ampO 9 EyRya amp Rby 7ampO 10 VyRya amp Rby 9EO 11 Sb amp EyFy amp Rby 6VO 12 Sb gt EyFyamp Rby 11ampO 13 N EyFy amp Rby 812 gtO 14 EyFy amp Rby 13DN 15 Fc amp Rbc 1430 16 Fc 15ampO 17 Rbc 15ampO 18 Fc gt Rca 1VO 19 Rca 1618 gtO 20 Rca amp Rbc 10VO 21 Rca gt Rbc 20ampO 22 Rbc 1921 gtO 23 X 1722XI What strategy should one employ in showing existential formulas The fol lowing principles might be useful in deciding between the two strategies 428 Hardegree Symbolic Logic 1 If any strategy will work the ID strategy will The worst that can happen is that the derivation is longer than it needs to be 2 Ifthere are no names available and if there are no existential formulas to instantiate in order to obtain names then the ID strategy is advisable although a quottrickquot derivation is still possible 3 When it works in a straightforward way and it usually does the DD strategy produces a prettier derivation The worst that can happen is that one has to start over and use ID 4 If names are obtainable by applying 30 then the DD strategy will probably work however it might be harder than the ID strategy I conclude with the following principle based on 14 lfyou want a riskfree technique use the ID strategy If you want more of a challenge use the DD strategy Chapter 8 Derivations in Predicate Logic 429 13 APPENDIX 1 THE SYNTAX OF PREDICATE LOGIC In this appendix we review the syntactic features of predicate logic that are crucial to understanding derivations in predicate logic These include the following notions l principal major connective 2 free occurrence of a variable 3 substitution instance 4 alphabetic variant 1 OFFICIAL PRESENTATION OF THE SYNTAX OF PREDICATE LOGIC A Singular Terms 1 Variables X y z 2 Constants a b c w X Nothing else is an singular term B Predicate Letters 0 0place predicate letters A B Z l lplace predicate letters the same 2 2place predicate letters the same 3 3place predicate letters the same and so forth X Nothing else is a predicate letter C Quanti ers 1 Universal Quantifiers VX Vy Vz 2 Existential Quantifiers EIX Ely Elz X Nothing else is a quantifier D Atomic Formulas 1 If P is an nplace predicate letter and t1tn are singular terms then Ptlt2 is an atomic formula X Nothing else is an atomic formula E Formulas 1 Every atomic formula is a formula 2 If l is a formula then so is Nil 3 If A and B are formulas then so are a fl amp B b fl v B c A gt B d A lt gt B 430 Hardegree Symbolic Logic 4 If A is a formula then so are Vx l Vy l Vz l Elx l Ely l EIZJL X Nothing else is a formula Given the above characterization of the syntax of predicate logic we see that every formula is exactly one of the following 1 An atomic formula there are no connectives Fa Fx Rab Rax Rxb etc A negation the major connective is negation Fa Nny Fx amp Gx NVxe 3xVnyy VxFx gt Gx etc A universal the major connective is a universal quantifier Vxe VyRay VxFx gt Gx VxEInyy VxFx gt EInyy etc An existential the major connective is an existential quantifier EIZFZ EIxRax ExFx amp Gx EInyny ExFx amp VyRyx etc A conjunction the major connective is ampersand Fx amp Gy Vxe amp EIyGy VxFx gt Gx amp VxGx gt Fx etc Fx V Gy Vxe V EIyGy VxFx gt Gx V VxGx gt Fx etc A conditional the major connective is arrow Fx gt Gx Vxe gt VxGx VxFx gt Gx gt VxFx gt Hx etc A biconditional the major connective is doublearrow Fx lt gt Gy Vxe gt EIyGy VxFx gt Gx lt gt NVxGx etc Now just as in sentential logic whether a rule of predicate logic applies to a given formula is primarily determined by what the formula39s major connective is In the case of negations the immediately subordinate formula must also be considered So it is important to be able to recognize the major connective of a formula of predicate logic 2 FREEDOM AND BONDAGE A Variables versus Occurrences of Variables How many words are there in this paragraph Well it depends on what you mean This question is actually ambiguous between the following two different questions 1 How many different unique words are used in this paragraph 2 How long is this paragraph in words or how many word occurrences are there in Chapter 8 Derivations in Predicate Logic 431 this paragraph The answer to the first question is 46 On the other hand the answer to the second question is 93 For example the word the appears 10 times which is to say that there are 10 occurrences of the word the in this paragraph Just as a given word of English eg the can occur many times in a given sentence or paragraph of English a given logic symbol can occur many times in a given formula And in particular a given variable can occur many times in a for mula Consider the following examples of occurrences of variables 1 Fx x occurs once or there is one occurrence of x 2 RXy x occurs once y occurs once 3 Fx gt Hx x occurs twice 4 VxFx gt Hx x occurs three times 5 VyFx gt Hy x occurs once y occurs twice 6 VxFx gt VxHx x occurs four times 7 VxVyny gt Ryx x occurs three times y occurs three times We also speak the same way about occurrences of other symbols and combi nations of symbols So for example we can speak of occurrences of N or occur rences of Vx B Quanti er Scope Definition The scope of an occurrence of a quantifier is by definition the smallest formula containing that occur rence The scope of a quantifier is exactly analogous to the scope of a negation sign in a formula of sentential logic Consider the analogous definition 432 Hardegree Symbolic Logic Definition The scope of an occurrence of N is by definition the smallest formula containing that occurrence Examples 1 NP gt Q the scope of N is NP 2 NP gt Qthe scope of N is NP gt Q 3 P gt NR gt8 the scope of N is NR gt S By analogy consider the following involving universal quantifiers 1 VXFX gt Fa the scope of VX is VXFX 2 VXFX gt GX the scope of VX is VXFX gt GX 3 Fa gt VXGx gtHX the scope of VX is VXGX gt HX As a somewhat more complicated example consider the following 4 VXVnyy gt VZRZX the scope of VX is VXVnyy gt VZRZX the scope of Vy is Vnyy the scope of Vz is VZRZX As a still more complicated example consider the following 5 VXVXFX gt VyVyGy gt VZnyZ the scope of the first VX is the whole formula the scope of the second VX is VXFx the scope of the first Vy is VyVyGy gt Vszyz the scope of the second Vy is VyGy the scope of the only Vz is Vszyz C Government and Binding Definition Vx and 3x govern the variable x Vy and y govern the variable y V2 and 32 govern the variable 2 etc Chapter 8 Derivations in Predicate Logic 433 Definition An occurrence of a quantifier binds an occurrence of a variable iff 1 the quantifier governs the variable and 2 the occurrence of the variable is contained within the scope of the occurrence of the quantifier Definition An occurrence of a quantifier truly binds an occurrence of a variable iff 1 the occurrence of the quantifier binds the occurrence of the variable and 2 the occurrence of the quantifier is inside the scope of every occurrence of that quantifier that binds the occurrence of the variable Example VXFX gt VXGX In this formula the first VX binds every occurrence of X but it only truly binds the rst two occurrences on the other hand the second VX truly binds the last two occurrences of X D Free versus Bound Occurrences of Variables Every given occurrence of a given variable is either free or bound Definition An occurrence of a variable in a formula F is bound in F if and only if that occurrence is bound by some quantifier occurrence in F Definition An occurrence of a variable in a formula F is free in F if and only if that occurrence is not bound in F 434 Hardegree Symbolic Logic Examples 1 Fx the one and only occurrence of X is free in this formula 2 VXFX gt GX a all three occurrences of X are bound by VX 3 FX gt VXGX the first occurrence of X is free the remaining two occurrences are bound 4 VXFX gt VXGX the first two occurrences of X are bound by the first VX the second two are bound by the second VX 5 VXVnyy gt VZRZX every occurrence of every variable is bound Notice in example 4 that the variable X occurs within the scope of two different occurrences of VX It is only the innermost occurrence of VX that truly binds the variable however The other occurrence of VX binds the first occurrence of X but none of the remaining ones 3 SUBSTITUTION INSTANCES Having described the difference between free and bound occurrences of vari ables we turn to the topic of substitution instance which is officially defined as follows Definition Let v be any variable let Fv be any formula containing v and let n be any name Then a substitution instance of the formula FM is any formula Fn obtained from Fv by substituting occurrences of the name n for each and every occurrence of the variable v that is free in Fv Let us look at a few examples in each example I give examples of correct substitu tion instances and then I give examples of incorrect substitution instances 1 Fx Correct Fa Fb Fc etc Incorrect FxFyFz Chapter 8 Derivations in Predicate Logic 435 2 FX gt Gx Correct Fa gt Ga Fb gt Gb Fc gt Gc etc Incorrect Fa gt Gb Fb gt Ga Fy gt Gy 3 RXX Correct Raa Rbb Rcc etc Incorrect Rab Rba RXX 4 FX gt VXGX Correct Fa gt VXGX Fb gt VXGX Fc gt VXGX etc Incorrect Fy gt VXGX Fa gt VaGa Fb gt Vbi 5 VyRXyI Correct VyRay Vbey VyRcy etc Incorrect Vszy VaRaa 6 Vnyy gt VZRZXI Correct VyRay gt Vsza Vbey gt Vszb VyRcy gt Vszc Incorrect Vszy gt Vsza VyRay gt Vszb In each case you should convince yourself why the given formula is or is not a correct substitution instance 4 ALPHABETIC VARIANTS As you will recall one can symbolize everything is F in one of three ways 1 VXFX 2 VyFy 3 VZFZ Although these formulas are distinct they are clearly equivalent Yet they are equivalent in a more intimate way than say the following formulas 4 VXFX gt VyHy 5 EIXFX gt VyHy 6 VXVyFX gt Hy 46 are mutually equivalent in a weaker sense than l3 If we translate 4 6 into English they might read respectively as follows r4 if anything is F then everything is H r5 if at least one thing is F then everything is H r6 for any two things if the first is F then the second is H These definitely don39t sound the same yet we can prove that they are logically equivalent By contrast if we translate l3 into English they all read exactly the same 436 Hardegree Symbolic Logic r1 3 everything is F We describe the relation between the various l3 by saying that they are alpha betic variants of one another They are slightly different symbolic ways of saying exactly the same thing The formal definition of alphabetic variants is difficult to give in the general case of unlimited variables But if we restrict ourselves to just three variables then the definition is merely complicated Definition A formula F is closed iff no variable occurs free in F Chapter 8 Derivations in Predicate Logic 437 Definition Let F1 and F2 be closed formulas Then F1 is an al phabetic variant of F2 iff F1 is obtained from F2 by permuting the variables x y 2 which is to say applying one of the following procedures 1 replacing every occurrence of x by y and every occurrence of y by x 2 replacing every occurrence of x by z and every occurrence of 2 by x 3 replacing every occurrence of y by z and every occurrence of 2 by y 4 replacing every occurrence of x by y and every occurrence of y by z and every occurrence of 2 by x 5 replacing every occurrence of x by z and every occurrence of 2 by y and every occurrence of Cy X7 Examples 1 VXFX VyFy VZFZ everyone is F 2 VXFX gt GX VyFy gt Gy VZFZ gt GZ every F is G 3 VXEInyy VXEIZRXZ VyEIZRyZ VyEIXRyX everyone respects someone or other 4 VXFX gt EyGy amp VZRXZ gt Ryz VXFX gt EZGZ amp Vyny gt VyFy gt EZGZ amp VXRyX gt VyFy gt EXGX amp VZRyz gt RXZ VZFZ gt EXGX amp VyRyZ gt VZFZ gt EyGy amp VXRZX gt RyX for every F there is a G who respects everyone the F respects 438 Hardegree Symbolic Logic 14 APPENDIX 2 SUMMARY OF RULES FOR SYSTEM PL PREDICATE LOGIC A Sentential Logic Rules Every rule of SL sentential logic is also a rule of PL predicate logic B Rules that don39t require a new name In the following v is any variable a and n are names FM is a formula Furthermore Fa is the formula that results when a is substituted for V at all its free occurrences and similarly Fn is the formula that results when n is so substituted UniversalOut V0 VvFv Fa a can be any name ExistentialIn 3 Fa a can be any name 3vFv Chapter 8 Derivations in Predicate Logic 439 C Rules that do require a new name In the following two rules n must be a new name that is a name that has not occurred in any previous line of the derivation ExistentialOut 30 3vFv Fn n must be a new name Universal Derivation UD SHeW VVFV SHeW Fn n must be a new name D Negation Quanti er Elimination Rules TildeUniversalOut VO 440 Hardegree Symbolic Logic 15 EXERCISES FOR CHAPTER 8 General Directions For each of the following construct a formal derivation of the conclusion indicated by from the premises EXERCISE SET A UniversalOut 1 2 3 4 5 6 7 8 9 10 VXFX gt GX NGb NFb VXFX gt GX NGb NVXFX VXFX gt GX Fc amp Gc NFC VXFX V GX gt HX VXHX gt JX amp KX Fa gt Ka VXFX amp GX gt HX Fa amp Ha Ga VXFX gt GX V HX VXHX gt GX Fa V Ga VXFX gt NGX Fa VXFX gt GX VXFX gt RXX VXNRaX Fa VXFX gt Vnyy Fa Raa VXRXX gt FX VXVyny gt RXX Fa NRab EXERCISE SET B ExistentialIn 11 12 13 14 15 16 17 18 19 20 VXFX gt GX Fa EIXGX VXFX gt GX VXGX gt HX Fa EXGX amp HX EXFX amp GX Fa NGa EIXFX gt VXGX Fa Gb VXFX V GX gt HX Ga V Ha EIXNFX VXRxa gt NRXb Raa EIXNRXb EIXRaX gt VXRxa Rba Raa VXFX gt RXX Fa EIXRxa EIXRaX gt VXRxa Raa Rab VXEnyy gt VyRyX Raa Rba XH 75 Xan lt XD 75 Xan XH lt XD lt XampXA XDXE lt XdXE X9 lt XampXA XDXE XJNXA f XDXE XJXE XI 75 XIXE X9 A XampXA f XH 75 XIXE f XH lt XDXA XH 75 XampXE XH lt XDXA 5 X9 lt XampXA X9 lt XampXA XD 75 XampXE X9 75 XdXE XD lt XampXA XaXE XHXE f XH lt XDXA f X9 lt XampXA XH 75 XampXE XD lt XHXA f X9 75 XampXE XH 75 XDXE XH 75 XampXE X9 lt XampXA 017 6 8 8 8 LE 99 99 179 9 ZS I s moIvnualslxa ms EISIDHEIXEI XH lt XampXA lt XD lt XampXA XH lt XD 75 XampXA XDXA lt XaXA X9 lt XampXA XH lt XampXA XH 75 XDXE f X9 lt XampXA XD lt XampXA X9 75 XampXE X9 lt XampXA XaXE X9 A XampXA XDXA A XHXA X9 75 XampXA XDXA 75 HM Xgt1 lt XampXA Xgt1 lt XH A XDDXA f X9 lt XampXA XH lt XampXA XH lt XD 75 XdXA f X9 lt XampXA XH lt XampXA XH lt XDXA f X9 lt XampXA 09 6Z sz LZ 9z sz vz sz zz IZ Honmuea IBSIQAIUH 3 ms EISIDHEIXEI WV og60 eleOHDQJd u suoneAueQ 9J91deuo 442 Hardegree Symbolic Logic EXERCISE SET E Negation Quanti er Elimination 41 VXFX gt GX EXFX amp NGX 42 NVXFX EXFX gt GX 43 VXGX gt HX VXFX gt GX NVXHX gt EIXNFX 44 EXFX V GX EIXFX V EIXGX 45 EXFX gt GX EIXNFX V EIXGX 46 EIXFX gt VXFX VXFX V VXNFX 47 VXFX gt GX EXGX amp HX EXFX amp HX 48 EIXFX V EIXGX EXFX V GX 49 EIXNFX V EIXGX EXFX gt GX 50 VXFX gt GX VXFX amp GX gt NHX EIXHX EXHX amp NFX EXERCISE SET F Multiple Quanti cation 51 VXFX gt GX VXFX gt EIyGy 52 VXFX gt VyGy EIXFX gt VXGX 53 EIXFX gt VXGX VXFX gt VyGy 54 EIXFX gt VXGX VXVyFX gt Gy 55 VXVyFX gt Gy NVXGX gt NEIXFX 56 EIXFX gt EIXNGX VXFX gt NVyGy 57 EIXFX gt VXNGX VXFX gt NEIyGy 58 VXFX gt NEIyGy EIXFX gt VXNGX 59 VXEyFy gt GX VXVyFX gt Gy 60 EIXFX gt VXFX VXVyFX lt gt Fy Chapter 8 Derivations in Predicate Logic 443 EXERCISE SET G Relational Quanti cation 61 62 63 64 65 66 67 68 69 70 VXVnyy VXVyRyX EIXRXX EIXEInyy EIXEInyy EIXEIyRyX EIXVnyy VXEIyRyX EIXNEInyy VXEIyNRyX EXEyFy amp ny VXFX gt EIyNRyX VXFX gt EIyNny EXGX amp Vnyy EXGX amp NFX EXFX amp EyGy amp ny VXGX gt EyFy amp RyX EXFX amp VyGy gt ny VXGX gt EyFy amp RyX EXKxa amp LXb VXKxa gt NFX gt LXb Kba gt Fb EXERCISE SET H More Relational Quanti cation 71 72 73 74 75 76 77 78 79 80 VXEInyy VXEnyy gt RXX VXRXX gt VyRyX VXVnyy VXEInyy VXVyny gt EIZRZX VXVyRyX gt VZRXZ VXVnyy VXEInyy VXVy ny gt RyX VXEyRyX gt VyRyX VXVnyy EIXEInyy VXVyny gt VZRXZ VXVZRXZ gt VyRyX VXVnyy EIXEInyy VXEnyy gt VyRyX VXVnyy VXKxa gt VyKyb gt ny VXFX gt KXb EXKxa amp EyFy amp Nny EIXGX EIXFX VXFX gt EyFy amp RyX VXVyny gt RyX EIXEyny amp RyX EXFX amp Kxa EXFX amp VyKya gt Nny EXFX amp EyFy amp RyX EXFX amp VyGy gt ny EXFX amp EyHy amp ny EXGX amp HX VXFX gt Kxa EXGX amp EyKya amp ny EXGX amp EyFy amp ny 444 Hardegree Symbolic Logic 16 ANSWERS TO EXERCISES FOR CHAPTER 8 1 1 VXFX gt GX Pr 2 NGb Pr 3 SHGW Fb DD 4 Fb gt Gb WC 5 Fb 24 gtO 2 1 VXFX gt GX Pr 2 Gb Pr 3 SHGW NVXFX ID 4 VXFX As 5 SHGW X DD 6 Fb 4VO 7 Fb gt Gb INC 8 Gb 67 gtO 9 X 28XI 3 1 VXFX gt GX Pr 2 Fc amp Gc Pr 3 SHGW Fc ID 4 Fc As 5 SHGW X DD 6 Fc gt Go 1VO 7 Fc gt Gc 2ampO 8 Go 46 gtO 9 Gc 47 gtO 10 X 89XI 4 1 VXFX V GX gt HX Pr 2 VXHX gt JX amp KX Pr 3 SHGW Fa gt Ka CD 4 Fa As 5 SHGW Ka DD 6 Fa v Ga gt Ha LVO 7 Ha gt Ja amp Ka 2VO 8 Fa v Ga 4vI 9 Ha 68 gtO 10 Ja amp Ka 79 gtO 1 1 Ka 10ampO Chapter 8 Derivations in Predicate Logic 445 5 1 VXFX amp GX gt HX Pr 2 Fa amp Ha Pr 3 SHGW Ga 1D 4 Ga As 5 SHGW X DD 6 Fa amp Ga gt Ha LVO 7 Fa 2ampO 8 Fa amp Ga 47ampI 9 Ha 68 gtO 10 Ha 2ampO 11 X 910XI 6 1 VXFX gt GX V HX Pr 2 VXHX gt GX Pr 3 SHGW Fa v Ga ID 4 Fa v Ga As 5 SHGW X DD 6 Fa 4O 7 Fa gt Ga v Ha 1VO 8 Ga v Ha 67 gtO 9 Ga 4vO 10 Ha 89VO 11 Ha gt Ga 2VO 12 Ga 1011 gtO 13 X 912XI 7 1 VXFX gt NGX Pr 2 Fa Pr 3 SHGW VXFX gt GX ID 4 VXFX gt GX As 5 SHGW X DD 6 Fa gt Ga 1VO 7 Fa gt Ga 4VO 8 Ga 26 gtO 9 Ga 27 gtO 10 X 89XI 8 1 VXFX gt RXX Pr 2 VXNRaX Pr 3 SHGW Fa DD 4 Fa gt Raa 1VO 5 Raa 2VO 6 Fa 45 gtO 446 Hardegree Symbolic Logic 9 1 VXFX gt Vnyy Pr 2 Fa Pr 3 SHGW Raa DD 4 Fa gt VyRay 1VO 5 VyRay 24 gtO 6 Raa 5VO 10 1 VXRXX gt FX Pr 2 VXVyny gt RXX Pr 3 Fa Pr 4 SHGW Rab DD 5 Raa gt Fa 1VO 6 Raa 35 gtO 7 VyRay gt Raa 2VO 8 Rab gt Raa 7VO 9 Rab 68 gtO 1 1 1 VXFX gt GX Pr 2 Fa Pr 3 SHGW EIXGX DD 4 Fa gt Ga 1VO 5 Ga 24 gtO 6 EIXGX 531 12 1 VXFX gt GX Pr 2 VXGX gt HX Pr 3 Fa Pr 4 SHGW EXGX amp HX DD 5 Fa gt Ga 1VO 6 Ga gt Ha 2VO 7 Ga 35 gtO 8 Ha 67 gtO 9 Ga amp Ha 78ampI 10 EXGX amp HX 931 13 1 EXFX amp GX Pr 2 Fa Pr 3 SHGW Ga DD 4 VXFX amp GX 1EO 5 Fa amp Ga 4VO 6 Fa gt Ga 5ampO 7 Ga 26 gtO Chapter 8 Derivations in Predicate Logic 447 14 1 3XFX gt VXGX Pr 2 Fa Pr 3 SHGW Gb DD 4 3XFX 231 5 VXGX 14 gtO 6 Gb 5VO 15 1 VXFX V GX gt HX Pr 2 Ga v Ha Pr 3 SHGW 3XFX DD 4 Ha 2O 5 Fa v Ga gt Ha 1VO 6 Fa v Ga 45 gtO 7 Fa 6vO 8 3XFX 731 16 1 VXRxa gt NRXb Pr 2 Raa Pr 3 SHGW 3XRXb DD 4 Raa gt Rab 1VO 5 Rab 24 gtO 6 3XRXb 531 17 1 3XRaX gt VXRxa Pr 2 NRba Pr 3 SHGW Raa 1D 4 Raa As 5 SHGW X DD 6 3XRaX 431 7 VXRxa 16 gtO 8 Rba 7VO 9 X 28X1 18 1 VXFX gt RXX Pr 2 Fa Pr 3 SHGW 3XRxa DD 4 Fa gt Raa 1VO 5 Raa 24 gtO 6 3XRxa 531 448 Hardegree Symbolic Logic 19 1 EIXRaX gt VXRxa Pr 2 Raa Pr 3 SHGW Rab ID 4 Rab As 5 SHGW X DD 6 EIXRaX 431 7 VXRxa 16 gtO 8 Raa 7VO 9 X 28XI 20 1 VXEnyy gt VyRyX Pr 2 Raa Pr 3 SHGW Rba DD 4 EIyRay gt VyRya 1VO 5 EIyRay 231 6 VyRya 45 gtO 7 Rba 6VO 21 1 VXFX gt GX Pr 2 VXGX gt HX Pr 3 SHGW VXFX gt HX UD 4 SHGW Fa gt Ha CD 5 Fa As 6 SHGW Ha DD 7 Fa gt Ga 1VO 8 Ga gt Ha 2VO 9 Ga 57 gtO 10 Ha 89 gtO 22 1 VXFX gt GX Pr 2 VXFX amp GX gt HX Pr 3 SHGW VXFX gt HX UD 4 SHGW Fa gt Ha CD 5 Fa AS 6 SHGW Ha DD 7 Fa gt Ga 1VO 8 Ga 57 gtO 9 Fa amp Ga 58ampI 10 Fa amp Ga gt Ha 2VO 1 1 Ha 910 gtO Chapter 8 Derivations in Predicate Logic 449 23 1 VXFX gt GX Pr 2 VXGX V HX gt KX Pr 3 SHGW VXFX gt KX UD 4 SHGW Fa gt Ka CD 5 Fa As 6 SHGW Ka DD 7 Fa gt Ga 1VO 8 Ga 57 gtO 9 Ga v Ha 891 10 Ga v Ha gt Ka 2VO 11 Ka 910 gtO 24 1 VXFX amp VXGX Pr 2 SHGW VXFX amp GX UD 3 SHGW Fa amp Ga DD 4 VXFX 1ampO 5 VXGX 1ampO 6 Fa 4VO 7 Ga 5vo 8 Fa amp Ga 67amp1 25 1 VXFX v VXGX Pr 2 SHGW VXFX V GX UD 3 SHGW Fa v Ga ID 4 Fa v Ga As 5 SHGW X DD 6 Fa 4O 7 Ga 4vO 8 SHGW NVXFX ID 9 VXFX As 10 SHGW X DD 11 Fa 9VO 12 X 611XI 13 VXGX 18VO 14 Ga 13VO 15 X 714XI 450 Hardegree Symbolic Logic 26 1 NEIXFX Pr 2 SHGW VXFX gt GX UD 3 SHGW Fa gt Ga CD 4 Fa As 5 SHGW Ga ID 6 Ga As 7 SHGW X DD 8 VXNFX 1EO 9 Fa 8VO 10 X 49XI 27 1 EXFX amp GX Pr 2 SHGW VXFX gt NGX UD 3 SHGW Fa gt Ga CD 4 Fa As 5 SHGW Ga ID 6 Ga As 7 SHGW X DD 8 VXFX amp GX 1EO 9 Fa amp Ga 8VO 10 Fa amp Ga 46ampI 11 X 910XI 28 1 VXFX gt GX Pr 2 EXGX amp HX Pr 3 SHGW VXFX gt NHX UD 4 SHGW Fa gt Ha CD 5 Fa As 6 SHGW Ha ID 7 Ha As 8 SHGW X DD 9 Fa gt Ga 1VO 10 Ga 59 gtO 11 Gaamp Ha 710ampI 12 EXGX amp HX 11EII 13 X 212XI 29 1 VXFX gt GX Pr 2 SHGW VXFX gt VXGX CD 3 VXFX As 4 SHGW VXGX UD 5 SHGW Ga DD 6 Fa gt Ga 1VO 7 Fa 3VO 8 Ga 67 gtO Chapter 8 Derivations in Predicate Logic 451 30 1 VXFX amp GX gt HX Pr 2 SHGW VXFX gtGX gtVXFXgtHX CD 3 VXFX gt GX As 4 SHGW VXFX gt HX UD 5 SHGW Fa gt Ha CD 6 Fa As 7 SHGW Ha DD 8 Fa gt Ga 3VO 9 Ga 68 gtO 10 Fa amp Ga 69ampI 11 Faamp Ga gtHa 1VO 12 Ha 1011 gtO 31 1 VXFX gt GX Pr 2 3XFX amp HX Pr 3 SHGW 3XGX amp HX DD 4 Fa amp Ha 230 5 Fa 4ampO 6 Fa gt Ga 1VO 7 Ga 56 gtO 8 Ha 4ampO 9 Ga amp Ha 78ampI 10 3XGX amp HX 931 32 1 3XFX amp GX Pr 2 VXHX gt NGX Pr 3 SHGW 3XFX amp NHX DD 4 Fa amp Ga 130 5 Ha gt Ga 2VO 6 Ga 4ampO 7 N Ga 6DN 8 Ha 57 gtO 9 Fa 4ampO 10 Fa amp Ha 89ampI 11 3XFX amp NHX 1031 33 1 VXFX gt GX Pr 2 VXGX gt HX Pr 3 3XHX Pr 4 SHGW 3XFX DD 5 Ha 330 6 Ga gt Ha 2VO 7 Ga 56 gtO 8 Fa gt Ga 1VO 9 Fa 78 gtO 10 3XFX 931 452 Hardegree Symbolic Logic 34 1 VXFX gt NGX Pr 2 SHGW EXFX amp GX ID 3 EXFX amp GX As 4 SHGW X DD 5 Fa amp Ga 3EIO 6 Fa 5ampO 7 Fa gt Ga LVO 8 Ga 67 gtO 9 Ga 5ampO 10 X 89XI 35 1 EXFX amp NGX Pr 2 SHGW VXFX gt GX ID 3 VXFX gt GX As 4 SHGW X DD 5 Fa amp Ga 1EO 6 Fa 5ampO 7 Fa gt Ga 3VO 8 Ga 67 gtO 9 Ga 5ampO 10 X 89XI 36 1 VXFX gt GX Pr 2 VXGX gt NHX Pr 3 SHGW EXFX amp HX ID 4 EXFX amp HX As 5 SHGW X DD 6 Fa amp Ha 4EIO 7 Fa 6ampO 8 Fa gt Ga LVO 9 Ga 78 gtO 10 Ga gt Ha 2VO 11 Ha 910 gtO 12 Ha 6ampO 13 X 1112XI Chapter 8 Derivations in Predicate Logic 453 37 1 VXGX gt HX Pr 2 3XIX amp NHX Pr 3 VXFX v GX Pr 4 SHGW 3XIX amp NFX DD 5 la amp Ha 230 6 Ha 5amp0 7 Ga gt Ha 1V0 8 Ga 67 gt0 9 Fa v Ga 3V0 10 Fa 89v0 11 Ia 5amp0 12 Iaamp Fa 1011ampI 13 3XIX amp NFX 1231 38 1 3XFX v 3XGX Pr 2 VXNFX Pr 3 SHGW 3XGX ID 4 3XGX As 5 SHGW X DD 6 3XFX 140 7 Fa 630 8 Fa 2V0 9 X 78XI 39 1 VXFX gt GX Pr 2 SHGW 3XFX gt 3XGX CD 3 3XFX As 4 SHGW 3XGX DD 5 Fa 330 6 Fa gt Ga 1V0 7 Ga 56 gt0 8 3XGX 731 40 1 VXFX gt GX gt HX Pr 2 SHGW 3XFXampGX gt3XFXampHX CD 3 3XFX amp GX As 4 SHGW 3XFX amp HX DD 5 Fa amp Ga 330 6 Fa 5amp0 7 Fa gt Ga gt Ha 1V0 8 Ga gt Ha 67 gtO 9 Ga 5amp0 10 Ha 89 gt0 11 FaampHa 610ampI 12 3XFX amp HX 1131 454 Hardegree Symbolic Logic 41 1 VXFX gt GX Pr 2 SHGW 3XFX amp NGX ID 3 3XFX amp NGX As 4 SHGW X DD 5 3XFX gt GX 1V0 6 Fa gt Ga 530 7 Fa amp Ga 6 gt0 8 VXFX amp NGX 330 9 Fa amp NGa 8V0 10 X 79XI 42 1 NVXFX Pr 2 SHGW 3XFX gt GX ID 3 3XFX gt GX As 4 SHGW X DD 5 3XFX 1V0 6 Fa 530 7 VXFX gt GX 330 8 Fa gt Ga 7V0 9 Fa amp Ga 8 gt0 10 Fa 9amp0 11 X 610XI 43 1 VXGX gt HX Pr 2 VXFX gt GX Pr 3 SHGW NVXHX gt 3XFX CD 4 NVXHX As 5 SHGW 3XFX DD 6 3XHX 4V0 7 Ha 630 8 Ga gt Ha 1V0 9 Ga 78 gt0 10 Fa gt Ga 2V0 11 Fa 910 gt0 12 3XFX 1131 Chapter 8 Derivations in Predicate Logic 455 44 1 EXFX v GX Pr 2 SHGW EIXFX v EIXGX ID 3 EIXFX V EIXGX As 4 SHGW X DD 5 NEIXFX 3O 6 NEIXGX 3O 7 Fa v Ga 1EO 8 VXNFX 5EO 9 Fa 8VO 10 Ga 79VO 11 VXNGX 6EO 12 Ga 11VO 13 X 1012XI 45 1 EXFX gt GX Pr 2 SHGW EIXNFX v EIXGX ID 3 NEIXNFX V EIXGX As 4 SHGW X DD 5 NEIXNFX 3O 6 NEIXGX 3O 7 Fa gt Ga 1EO 8 VX NFX 5EO 9 N Fa 8VO 10 Fa 9DN 11 Ga 710 gtO 12 VXNGX 6EO 13 Ga 12VO 14 X 1113XI 46 1 EIXFX gt VXFX Pr 2 SHGW VXFX v VXNFX ID 3 VXFX v VXNFX As 4 SHGW X DD 5 NVXFX 3O 6 NVXNFX 3O 7 NEIXFX 15 gtO 8 VXNFX 7EO 9 X 68XI 456 Hardegree Symbolic Logic 47 1 VXFX gt GX Pr 2 EXGX amp HX Pr 3 SHGW EXFX amp HX ID 4 EXFX amp HX As 5 SHGW X DD 6 Fa amp Ha 4EIO 7 Fa 6ampO 8 Fa gt Ga 1VO 9 Ga 78 gtO 10 VXGX amp HX 2EO 11 Ga amp Ha 10VO 12 Ga gt Ha 11ampO 13 Ha 912 gtO 14 Ha 6ampO 15 X 1314XI 48 1 EIXFX v EIXGX Pr 2 SHGW EXFX v GX ID 3 EXFX V GX As 4 SHGW X DD 5 VXFX V GX 3EO 6 SHGW NEIXFX ID 7 EIXFX As 8 SHGW X DD 9 Fa 7EO 10 Fa v Ga 5VO 11 Fa 10vO 12 X 911XI 13 EIXGX 16VO 14 Gb 1330 15 Fb v Gb 5VO 16 Gb 15O 17 X 1416XI Chapter 8 Derivations in Predicate Logic 457 49 1 EIXNFX v EIXGX Pr 2 SHGW EXFX gt GX ID 3 EXFX gt GX As 4 SHGW X DD 5 VXFX gt GX 3EO 6 SHGW NEIXNFX ID 7 EIXNFX As 8 SHGW X DD 9 Fa 730 10 Fa gt Ga 5VO 11 Faamp Ga 10 gtO 12 Fa 11ampO 13 X 912XI 14 EIXGX 16VO 15 Gb 1430 16 Fb gt Gb 5VO 17 Fb amp NGb 16 gtO 18 Gb 17ampO 19 X 1518XI 50 1 VXFX gt GX Pr 2 VXFX amp GX gt NHX Pr 3 EIXHX Pr 4 SHGW EXHX amp NFX ID 5 EXHX amp NFX As 6 SHGW X DD 7 Ha 330 8 VXHX amp NFX 5EO 9 Ha amp Fa 8VO 10 Ha gt Fa 9ampO 11 Fa 710 gtO 12 Fa 11DN 13 Fa gt Ga 1VO 14 Ga 1213 gtO 15 Fa amp Ga 1214ampI 16 Fa amp Ga gt Ha 2VO 17 Ha 1516 gtO 18 X 717XI 51 1 VXFX gt GX Pr 2 SHGW VXFX gt EIyGy UD 3 SHGW Fa gt EIyGy CD 4 Fa As 5 SHGW EIyGy DD 6 Fa gt Ga 1VO 7 Ga 46 gtO 8 EIyGy 7EII 458 Hardegree Symbolic Logic 52 1 VXFX gt VyGy Pr 2 SHGW 3XFX gt VXGX CD 3 3XFX As 4 SHGW VXGX UD 5 SHGW Ga DD 6 Fb 330 7 Fb gt VyGy 1VO 8 VyGy 67 gtO 9 Ga 8VO 53 1 3XFX gt VXGX Pr 2 SHGW VXFX gt VyGy UD 3 SHGW Fa gt VyGy CD 4 Fa As 5 SHGW VyGy UD 6 SHGW Gb DD 7 3XFX 431 8 VXGX 17 gtO 9 Gb 8VO 54 1 3XFX gt VXGX Pr 2 SHGW VXVyFX gt Gy UD 3 SHGW VyFa gt Gy UD 4 SHGW Fa gt Gb CD 5 Fa As 6 SHGW Gb DD 7 3XFX 531 8 VXGX 17 gtO 9 Gb 8VO 55 1 VXVyFX gt Gy Pr 2 SHGW NVXGX gt 3XFX CD 3 NVXGX As 4 SHGW 3XFX 1D 5 3XFX As 6 SHGW X DD 7 3XGX 3VO 8 NGa 730 9 Fb 530 10 VyFb gt Gy 1VO 11 Fb gt Ga 10VO 12 Fb 811 gtO 13 X 912XI Chapter 8 Derivations in Predicate Logic 459 56 1 3XFX gt 3XGX Pr 2 SHGW VXFX gt NVyGy UD 3 SHGW Fa gt NVyGy CD 4 Fa As 5 SHGW NVyGy ID 6 VyGy As 7 SHGW X DD 8 3XFX 431 9 3XGX 18 gt0 10 Gb 930 11 Gb 6V0 12 X 1011XI 57 1 3XFX gt VXNGX Pr 2 SHGW VXFX gt 3yGy UD 3 SHGW Fa gt 3yGy CD 4 Fa As 5 SHGW 3yGy ID 6 3yGy As 7 SHGW X DD 8 3XFX 431 9 VXNGX 18 gt0 10 Gb 630 11 Gb 9V0 12 X 1011XI 58 1 VXFX gt 3yGy Pr 2 SHGW 3XFX gt VXNGX CD 3 3XFX As 4 SHGW VXNGX UD 5 SHGW Ga ID 6 Ga As 7 SHGW X DD 8 Fb 330 9 Fb gt 3yGy 1V0 10 3yGy 89 gt0 11 VyNGy 1030 12 Ga 11V0 13 X 612XI 460 Hardegree Symbolic Logic 59 1 VX3yFy gt GX Pr 2 SHGW VXVyFX gt Gy UD 3 SHGW VyFa gt Gy UD 4 SHGW Fa gt Gb CD 5 Fa As 6 SHGW Gb DD 7 3yFy gt Gb 1VO 8 3yFy 531 9 Gb 78 gtO 60 1 3XFX gt VXFX Pr 2 SHGW VXVyFX lt gt Fy UD 3 SHGW VyFa lt gt Fy UD 4 SHGW Fa lt gt Fb DD 5 SHGW Fa gt Fb CD 6 Fa As 7 SHGW Fb DD 8 3XFX 631 9 VXFX 18 gtO 10 Fb 9VO 11 SHGW Fb gt Fa CD 12 Fb As 13 SHGW Fa DD 14 3XFX 1231 15 VXFX 114 gtO 16 Fa 15VO 17 Falt gtFb 511lt gt1 61 1 VXVnyy Pr 2 SHGW VXVyRyX UD 3 SHGW VyRya UD 4 SHGW Rba DD 5 Vbey 1vo 6 Rba 5VO 62 1 3XRXX Pr 2 SHGW 3X3nyy DD 3 Raa 130 4 3yRay 331 5 3X3nyy 431 Chapter 8 Derivations in Predicate Logic 461 63 1 3X3nyy Pr 2 SHGW 3X3yRyX DD 3 3yRay 130 4 Rab 330 5 3yRyb 431 6 3X3yRyX 531 64 1 3XVnyy Pr 2 SHGW VX3yRyX UD 3 SHGW 3yRya DD 4 Vbey 130 5 Rba 4VO 6 3yRya 531 65 1 3X3nyy Pr 2 SHGW VX3yRyX UD 3 SHGW 3yRya DD 4 3bey 130 5 VyNRby 43O 6 Rba 5VO 7 3yRya 631 66 1 3X3yFy amp ny Pr 2 SHGW VXFX gt 3yRyX UD 3 SHGW Fa gt 3yRya CD 4 Fa As 5 SHGW 3yRya DD 6 3yFy amp Rby 130 7 VyFy amp Rby 63O 8 Fa amp Rba 7VO 9 Fa gt Rba 8ampO 10 Rba 49 gtO 11 3yRya 1031 462 Hardegree Symbolic Logic 67 1 VXFX gt 3yny Pr 2 3XGX amp Vnyy Pr 3 SHGW 3XGX amp NFX ID 4 3XGX amp NFX As 5 SHGW X DD 6 VXGX amp NFX 43O 7 Ga amp VyKay 230 8 Ga 7ampO 9 Ga amp NFa 6VO 10 Ga gt Fa 9ampO 11 Fa 810 gtO 12 Fa 11DN 13 Fa gt 3yKay 1VO 14 3yKay 1213 gtO 15 NKab 1430 16 VyKay 7ampO 17 Kab 16VO 18 X 1517XI 68 1 3XFX amp 3yGy amp ny Pr 2 SHGW VXGX gt 3yFy amp RyX UD 3 SHGW Ga gt 3yFy amp NRya CD 4 Ga As 5 SHGW 3yFy amp NRya DD 6 Fb amp 3yGy amp Rby 130 7 Fb 6ampO 8 3yGy amp Rby 6ampO 9 VyGy amp Rby 83O 10 Ga amp Rba 9VO 11 Ga gt NRba 10ampO 12 NRba 411 gtO 13 Fb amp NRba 712ampI 14 3yFy amp NRya 1331 69 1 3XFX amp VyGy gt ny Pr 2 SHGW VXGX gt 3yFy amp RyX UD 3 SHGW Ga gt 3yFy amp Rya CD 4 Ga As 5 SHGW 3yFy amp Rya DD 6 Fb amp VyGy gt Rby 130 7 VyGy gt Rby 6ampO 8 Ga gt Rba 7VO 9 Rba 48 gtO 10 Fb 6ampO 11 Fb amp Rba 910ampI 12 3yFy amp Rya 1131 Chapter 8 Derivations in Predicate Logic 463 70 1 EXKxa amp LXb Pr 2 VXKxa gt NFX gt LXb Pr 3 SHGW Kba gt Fb CD 4 Kba As 5 SHGW Fb DD 6 Kba gt Fb gt Lbb 2VO 7 Fb gt Lbb 46 gtO 8 VXKX3 amp LXb 1EO 9 Kba amp Lbb 8VO 10 Kba gt Lbb 9ampO 11 Lbb 410 gtO 12 Fb 711 gtO 13 Fb 12DN 71 1 VXEInyy Pr 2 VXEnyy gt RXX Pr 3 VXRXX gt VyRyX Pr 4 SHGW VXVnyy UD 5 SHGW VyRay UD 6 SHGW Rab DD 7 EIbey 1VO 8 EIbey gt Rbb 2VO 9 Rbb 78 gtO 10 Rbb gt VyRyb 3VO 11 VyRyb 910 gtO 12 Rab 1 1VO 72 1 VXEInyy Pr 2 VXVyny gt EIZRZX Pr 3 VXVyRyX gt VZRXZ Pr 4 SHGW VXVnyy UD 5 SHGW VyRay UD 6 SHGW Rab DD 7 EIyRay 1VO 8 Rac 7EO 9 VyRay gt Elsza 2VO 10 Rac gt EIsza 9VO 11 EIZRza 810 gtO 12 Rda 1 1EO 13 VyRya gt VzRaz 3VO 14 Rda gt VzRaz 13VO 15 VzRaz 1214 gtO 16 Rab 15VO 464 Hardegree Symbolic Logic 73 1 VXEInyy Pr 2 VXVyny gt RyX Pr 3 VXEyRyX gt VyRyX Pr 4 SHGW VXVnyy UD 5 SHGW VyRay UD 6 SHGW Rab DD 7 EIbey 1VO 8 Rbc 7EO 9 VyRby gt Ryb 2VO 10 Rbc gt Rcb 9VO 11 Rob 810 gtO 12 EIyRyb gt VyRyb 3VO 13 EIyRyb 11EI 14 VyRyb 1214 gtO 15 Rab 14VO 74 1 EIXEInyy Pr 2 VXVyny gt VZRXZ Pr 3 VXVZRXZ gt VyRyX Pr 4 SHGW VXVnyy UD 5 SHGW VyRay UD 6 SHGW Rab DD 7 EIyRcy 130 8 Rod 7EO 9 VyRcy gt Vchz 2VO 10 Rod gt VZRCZ 9VO 11 VZRCZ 810 gtO 12 Vchz gt VyRyc 3VO 13 VyRyc 1112 gtO 14 Rac 13VO 15 VyRay gt VzRaz 2VO 16 R30 gt VZRaZ 15VO 17 VzRaz 1416 gtO 18 Rab 17VO Chapter 8 Derivations in Predicate Logic 465 75 1 EIXEInyy 2 VXEnyy gt VyRyX 3 SHGW VXVnyy 4 5 6 7 8 9 10 11 12 13 SHGW VyRay SHGW Rab EIyRcy EIyRcy gt VyRyc VyRyc Rbc EIbey EIbey gt VyRyb VyRyb Rab 466 Hardegree Symbolic Logic 76 1 VXKxa gt VyKyb gt ny Pr 2 VXFX gt KXb Pr 3 3XKxa amp 3yFy amp Nny Pr 4 SHGW 3XGX ID 5 3XGX As 6 SHGW X DD 7 Kca amp 3yFy amp NRcy 330 8 3yFy amp NRcy 7ampO 9 Fd amp NRcd 830 10 Fd 9ampO 11 Kca gt VyKyb gt Rcy 1VO 12 Kca 7ampO 13 VyKyb gt Rcy 1112 gtO 14 de gt Red 13VO 15 Fd gt de 2VO 16 de 1015 gtO 17 Rod 1416 gtO 18 NRcd 9ampO 19 X 1718XI 77 1 3XFX Pr 2 VXFX gt 3yFy amp RyX Pr 3 VXVyny gt RyX Pr 4 SHGW 3X3yny amp RyX DD 5 Fa 130 6 Fa gt 3yFy amp Rya 2VO 7 3yFy amp Rya 56 gtO 8 Fb amp Rba 730 9 Rba 8ampO 10 VyRby gt Ryb 3VO 11 Rba gt Rab 10VO 12 Rab 911 gtO 13 Rab amp Rba 912ampI 14 3yRay amp Rya 1331 15 3X3yny amp RyX 1431 Chapter 8 Derivations in Predicate Logic 467 78 1 3XFX amp Kxa Pr 2 3XFX amp VyKya gt Nny Pr 3 SHGW 3XFX amp 3yFy amp RyX DD 4 Fb amp Kba 130 5 Fc amp VyKya gt NRcy 230 6 VyKya gt Rcy 5ampO 7 Kba gt NRcb 6VO 8 Kba 4ampO 9 Rcb 78 gtO 10 Fe 5ampO 11 Fe amp NRcb 910ampI 12 3yFy amp NRyb 1131 13 Fb 4ampO 14 Fb amp 3yFy amp NRyb 1213ampI 15 3XFX amp 3yFy amp RyX 1431 79 1 3XFX amp VyGy gt ny Pr 2 3XFX amp 3yHy amp ny Pr 3 SHGW 3XGX amp HX ID 4 3XGX amp HX As 5 SHGW X DD 6 Fa amp VyGy gt Ray 130 7 VX FX amp 3yHy amp ny 23O 8 N Fa amp 3yHy amp Ray 7VO 9 Fa gt 3yHy amp Ray 8ampO 10 Fa 6ampO 11 3yHy amp Ray 910 gtO 12 VyHyampRay 113O 13 Gb amp Hb 430 14 Hb amp Rab 12VO 15 Hb gt Rab 14ampO 16 Hb 13ampO 17 Rab 1516 gtO 18 VyGy gt Ray 6ampO 19 Gb gt Rab 18VO 20 Gb 13ampO 21 Rab 1920 gtO 22 X 1721XI 468 Hardegree Symbolic Logic 80 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 VXFX gt Kxa EXGX amp EyKya amp ny SHGW EXGX amp EyFy amp ny EXGX amp EyFy amp ny SHGW X Gb amp EyKya amp Rby Gb VX GX amp EyFy amp ny N Gb amp EyFy amp Rby Gb gt N EyFy amp Rby N 3yFy amp Rby 3yFy amp Rby Fc amp Rbc Fe Fe gt Kca Kca EyKya amp Rby VyKya amp Rby Kca amp Rbc Kca gt Rbc Rbc Rbc X DD 230 6ampO 430 8vo 9ampo 710 gto 11DN 1230 13ampo 1vo 1415 gto 6ampO 1130 18vo 19ampo 1620 gto 13ampo 2122x1
Are you sure you want to buy this material for
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'