INTRODUCTION TO LOGIC
INTRODUCTION TO LOGIC PHIL 240
Popular in Course
Popular in PHIL-Philosophy
This 80 page Class Notes was uploaded by Dr. Kathryn Mayer on Wednesday October 21, 2015. The Class Notes belongs to PHIL 240 at Texas A&M University taught by Staff in Fall. Since its upload, it has received 48 views. For similar materials see /class/226146/phil-240-texas-a-m-university in PHIL-Philosophy at Texas A&M University.
Reviews for INTRODUCTION TO LOGIC
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/21/15
86 Proving Theorems Definition A theorem is a statement that can be proved from no premises Comment It can be shown that our system of proof is complete in the following sense every statement that is logically true that is true in every row of its truth table is a theorem of our system The converse can also be shown every theorem of our system of proof is true a logical truth that is true in every row of its truth table Comment Because every theorem is a logical truth any argument with a theorem as a conclusion is valid For to be invalid it has to be possible to make an argument s premises true and its conclusion false and a logical truth can t be false To prove a theorem you must use either GP or RAA Example A proof for A A B o A 3 Examgle A proof for A B lt gt 3 gt A B lt gt 3 In some cases a combination of RAA and CP works best Examgle A proof for F gt G gt F gt F In other cases it is best to use CP multiple times and hence one might have to embed multiple assumptions one within the other to prove a theorem Example A proof for A gt B gt 3 gt A gt B gt A gt 3 Corresponding conditionas There is an important connection between valid arguments and theorems Definition Letp1 pn1 pn q be an argument Ifn gt 1 then the conditional p1 o o pn1 o p gt q formed by conjoining the premises and forming a conditional with that conjunction as the antecedent and the premise q as conse quent is called the corresponding conditional for the argu ment If there is only one premise in the argument ie if the argument is of the form 19 q then the corresponding conditional is justp gt q Comment One can show an argument to be valid by proving its corre sponding conditional Examgle One Premise Argument AV NB B Corresponding conditional AV NB gt B Examgle Multigle Premises Argument G gtHoKHlt gtLol 1VKG Conjunction of premises G gt H o K o H lt gt L o 1 o NI K Corresponding conditional G gt H o K o H lt gt L o 1 o NI K gt G 73 Using Truth Tables to Evaluate Arguments Consider first the following valid argument 1 Either Israel will abandon the West Bank settlements or the sui cide bombings will continue But Israel will never abandon the West Bank settlements Therefore the suicide bombings will continue A Israel will abandon the West Bank settlements B The suicide bombings will continue We can symbolize this argument as follows 2 AVB A B We want to use truth tables to verify that this argument is valid To do so we first construct the truth table Then we use it to test for validity Constructing the Truth Table 1 Begin by listing the statement letters that occur in the symbolization of the argument in the order in which they first appear followed by the argument thus A B AVB NA B 2 Now add all the possible truth value assignments there are for A and B In any truth table for a sentence or argument there will always be 2 where n is the number of statement letters in the sentence or argument So there will be 4 rows in this truth table To construct the truth value assignments begin in the column to the left of the vertical bar and alternate Ts and Fs 3 Then move to the next column to the left and alternate pairs of Ts and Fs Continue in this fashion until you have truth values beneath every sentence letter as we do already in this example 4 Fill in the truth table ABlAvB NA B TT T F T TF T F F FT T T T FF F T F Discussion How do we know under which elements of an argument to put truth values In actual practice it is up to you so long as there is enough information for you to determine the validity of the argument But it tends to look best if you fill in truth values according to the following two principles these principles must be followed when you are using the Web Tutor 0 Put truth values beneath every occurrence of a logical operator 0 Put truth values beneath an occurrence of a statement letter ifand only if that occurrence is either a premise or the conclusion of the argument Evaluating the argument Definition Let p be a WFF occurring as a premise or the conclusion in an argument and let R be a row of a truth table for that argument Then p is said to be true in R iff either i p is atomic and T occurs beneath p in R or ii p is compound and T occurs beneath its main logical operator in R Otherwise p is false in R There are two simple steps for determining whether or not an argument is valid 1 Look for a row of the truth table in which the premises are ALL true and the conclusion is false 2 If there is no such a row the argument is valid if there is it is invalid Looking at the truth table above we see that it is indeed valid as expected Discussion By definition a valid argument is one that cannot have true premises and a false conclusion That is more picturesquely there is no possible worldquot in which the premises are true and the conclusion false Now each row of a truth table represents a possible world or rather a class of possible worlds namely all of those worlds in which the statement letters have the truth values assigned them in that row Since the statements in an argument are all truth functional each row shows what the truth values of the premises and the conclusion would have been if the statement letters had had the truth values assigned to them in that row Since we have listed all possible truth value assignments the truth table in effect shows what all the truth values that the premises and conclusion could possibly have had Hence if the argument is valid ie if there is no possible in which the premises are true and the conclusion false there should be no row of the truth table in which the premises are assigned T and the conclusion F Another Example Consider the following argument 1 Abortion is permissible only if fetuses are not innocent human be ings or it is not always wrong to kill innocent human beings But it is always wrong to killl innocent human beings So abortion is not permissible A Abortion is permissible B Fetuses are innocent human beings W It is always wrong to kill innocent human beings We can symbolize this argument as follows 2 A gt NB VNW w NA A gt NB v NW w A n n n n I I I Igt I39I I39I l l I39I I39I l lUJ I39I l I39I l I39I l I39I lE The completed truth table looks like this E A NB v NW F 2 gt n n n n I I I Igt I39I I39I l l I39I I39I l IUJ I39I l I39I l I39I l I39I l l l l l l l l 39li l l 39 39 l l l39l l39l l l l 39I l l l l 39 l 39 l I39I l l39l I39I l I39I l I39I l I39I IE l l l l I39I I39I I39I I39I And we can see from row 3 that it is invalid the premises are true but the conclusion is false when A is true B is false and W is true 82 Five Equivalence Rules Comment Recall that two statements are logically equivalentjust in case they are true on exactly the same truth value assigments Logically equiv alent statements thus express the same information Hence given a state ment p one can always validly infer a logically equivalent statement q This warrants the formation of rules of inference known as equivalence rules based upon logical equivalence They provide us with explicit patterns of logical equivalence that we can use to infer new statements from given statements in a proof Because logically equivalent statements express the same information one can always replace any statementpart p of any statement q with a statement 19 that is logically equivalent to p and the resulting statement q will be logically equivalent to q it will express the same information Con sequently equivalence rules apply not only to the entire statement in a line of a proof but to statementparts of a statement in a line of a proof This is the main difference between implicational rules and equivalence rules All of our equivalence rules are of the form p q where the fourdot symbol indicates that p is logically equivalent to q Such a rule tells is that in the context of a proof we may replace any occurrence ofp in a line of a proof even if p is only part of a statement on a line with q or any occurrence of q with p and validly infer the result We illustrate with the first of our equivalence rules Rule 9 Double negation DN p p Rule 9 thus tells us that ifp is a statement in a proof or a part of a state ment in a proof we can replace it with p and add the resulting state ment to the proof as a further step justified by DN We can also go from right to left that is if p is a part of a statement in a proof we can replace it with p and add the resulting statement to the proof as a further step justified by DN Examgle A proof for F gt w R R F 1 NF gtNR 2 R F Rule 10 Commutation Com p q q p 1901 qp Examgle A proof for P gt w B o 0 O o B N P 1 P gtBOO 2 013 P Rule 11 Association As p q 7 p v 1 v 7 pqT D 196007 Examgle A proof for C R DH w R D C 1 CVRD 2 RVD 39C Rule 12 DeMorgan s laws DeM N p q Np Nq 39V QUpVNQ Examgle A proof for E o D E o w D w E N D 1KE0DMME0DN 2E gD Rule 13 Contraposition Cont p gt q q gtp Example A proof for W gt D gt w G N D gt NW N C 1 W gtD gtNC 2 ND gtNW NC More Rules of Thumb Rule of Thumb 4 It is often useful to consider logically equiv alent forms of the conclusion Eg if the conclusion is A gt w B consider whether you might be able to prove B gt A Again if eg A o B is the conclusion consider whether you might be able to prove A w B Rule of Thumb 5 Both conjunction and disjunction can lead to useful applications of De Morgan s laws That is when you see a conjunction or disjunction or a negated conjunc tion or a negated disjunction scan your premises and derived lines to see if a transformation using DeM might be useful Examgle Exercise 82D 2 N J o L 1 2 JVL gtM 3 EVMS SE The example completed 1 JOL 2 JVL gtM 3 EvMvS 39SoE 4 NJVNL 1DeM 5 NM 24MP 6 ESM 3Com 7 EVSM 6A5 8 NEVNS 57DS 9 SVE 8Com 10 SoE 9DeM 95 The Logic of Relations So far we ve only considered WFFs containing monadic predicates like Ax and ElyPy gt Qy where monadic predicates stand for verb phrases like is happy or is a woman However predicate logic also contains binary predicates ie 2 place predicates for forming WFFs like Fyz and N x Ax gt ElyByo ny ternary predicates for forming WFFs like NRabc and in general n place predicates for all n Binary predicates stand for expressions like father of and shorter than that express relations between individuals In this section we will consider arguments and symbolizations involving nplace predicates Proofs work no differently with nplace predicates than with monadic predicates The major trick is translation Example from text Al is taller than Bob Bob is taller than Chris If one thing is taller than a second and the second is taller than a third then the fist is taller than the third 80 Al is taller than Chris Txy x is taller than y a Al 13 Bob c Chris Translation Tab The x y zTxy o Tyz gt sz Tao 1 Tab 2 Tbc 3 XyzTxy o Tyz gt sz Tac 4 yzTay o Tyz gt Taz 3 UI 5 zTab o sz gt Taz 4 UI 6 Tab 0 Tbc gt Tac 5 UI 7 Tab 0 Tbc 12 Conj 8 Tac 67 MP Translation with 2place predicates Consider the following scheme of abbreviation drawn from the headlines from a few years ago PX X should be impeached BX X is beautiful HXy X harassed y SXy X should sue y b Bill p Paula c me Now let us translate the following sentences according to this scheme Bill harassed Paula pr Bill harassed Paula but I didn t pr o N Hcp Bill and Paula harassed each other pr o Hpb Bill harassed Paula but he shouldn t be impeached pr o Pb Bill shouldn t be impeached even though he harassed someone Pb o 30be No one harassed Paula 3pr or X N pr Paula should sue anyone who harassed her Xpr gt 8px Someone harassed Paula and she should sue him Elx Exp 0 8px If someone harassed Paula she should sue him Xpr gt pr Paula is beautiful So anyone who harasses Paula harasses someone beautiful 1313 Xpr gt ElyBy 0 ny More on 2place Relations The following material is not in the text Its purpose is to illustrate the importance of the order of the universal and existential quanti rs when they occur together and also to illustrate the importance of the order of the arguments in an atomic sentence We will do so by building a series of small l nodels in which certain sentences are true Many sentences are true in each model of course We will just identify the ones that are particularly salient In these mod els dots represent persons and an arrow between two dots ie o gt 0 indicates that the person represented by the fist dot loves the person represented by the second The answers are left out of the notes so that we can construct them as exercises in class o o L The Caring World EngHsh Logic A o o o o The Caredfor World EngHsh Logic Unrequited Love EngHsh Logic 0 c U U o c U U The Narcissistic World EngHsh Logic o c U U The603 EngHsh Logm The Bleak World EngHsh Logm Universal Object of Adoration EngHsh Logic 0 o o o 0 Universal Adorer EngHsh Logic Important Properties of Relations R is symmetrical if x bears R to y then y bears R to x ie XyRXy gt RyX Examgle being a sibling of R is asymmetrical if x bears R to y then y does not bear R to X ie X y ny gt N Ryx Examgle mother of R is nonsymmetrical R is neither symmetrical nor asymmetrical Examgle loves R is re xive x bears R to x for all x ie xRxx Examgle identical to R is irreflxive x does not bear R to x for any x ie x N Rxx Examgle grandmother of sister of R is transitive if x bears R to y and y bears R to 2 then x bears R to Z ie X y Zny o Ryz gt RXZ Examgle ancestor of taller than not sister of R is intransitive if x bears R to y and y bears R to 2 then x does not bear R to z ie XyZny o Ryz gt sz Examgle father of R is nontransitive R is neither transitive nor intransitive Examgle sister of 72 Truth Tables Truth tables provide a simple method for testing whether or not a given argument is valid They can also be used to test for certain logical properties of statements Definition sorta A compound statement is truth functional if its truth value ie its truth or falsity is completely determined by the truth values of its component statements Nega ons Semantic rule for negations The truth value of a negation is the opposite of the truth value of its immediate component la the statement that is negated This rule can be captured conveniently in the following truth table schema Truth table schema for negations Np I39l I B F T This is a truth table schema because it is really a pattern that characterizes infinitely many truth tables at once one for every possible wff Conjunctions Semantic rule for conjunctions A conjunction is true if and only if both its conjuncts are true otherwise it is false Truth table schema for conjunctions Disjunctions Semantic rule for disjunctions A disjunction is false if and only if both its conjuncts are false otherwise it is true Truth table schema for disjunctions Comment As the truth table makes explicit we understand V to express inclusive rather than exclusive disjunction That is we allow a disjunction to be true if at least one of the disjuncts is true Exclusive disjunction requires that exactly one of the disjuncts be true in order for the disjunction to be true lfthis were the meaning we desired for how would we alter the truth table above Comment The choice of the inclusive meaning is reasonable as i it is clear that many instances of disjunction in English are inclusive and ii the exclusive meaning can be expressed very naturally in terms of the inclusive and negation On the first point consider a sentence like the following which might appear in a job advertisement Applicants must have a BS in computer science or at least 3 years of programming experience Clearly a company would not discard an application from someone with both the degree and the experience On the second point note that an exclusive disjunction can be expressed simply by expressing an inclusive disjunction and then explicitly ruling out the possibility of both disjuncts being true Letting lt29 express exclusive disjunction p qdefqu pVq def here means means by definition Material Conditionals Semantic rule for conditionals A conditional is false if and only if its antecedent is true and its consequent is false othenvise it is true Truth table schema for conditionals Comment Natural language conditionals statements of the form if then are in fact very complicated The truth values of some in particular are not completely determined by the truth values of their component statements One semantic fact however ties all conditionals together namely that they are false if their antecedent is true and their consequent is false The material conditional is distinguished by the fact that it is false only under those conditions and true under all others The material conditional is not entirely a logicians invention there do appear to be instances of it in natural language For example suppose I were to tell you lfyou get an A on the final exam you will get an A for the course The only case in which you would be able to accuse me of lying to you hence of having said something false would be the case where in fact you get an A on the final but I do not give you an A for the course ie the case where the antecedent is true and the consequent is false In all other cases what I said was true Hence the conditional in this case is plausibly taken to be a material conditional Material Biconditionals Semantic rule for biconditionals A biconditional is true if and only if the component statements on either side of the main double arrow have the same truth value otherwise it is false Truth table schema for biconditionals Comment Note that a material biconditional is logically equivalent to ie roughly means the same as a conjunction of two material conditionals specifi cally p lt gt q means the same as p gt q o q gt p An Example B gt A H A B v B A n n I Igt B T F T F The completed truth table looks like this F A BB gt A H A B v B A 96 The Logic of Relations Proofs The inference rules for predicate logic do not change when we extend our lan guage to include relations Nonetheless some of the restrictions on the rules become particularly pertinent in the new proof contexts that can arise when re lations are allowed Hence a number of reminders are in order 1 If you have a premise with more than one quantifer apply U or E to remove the quantifiers one at a time from left to right Example done in class 1 0060ny gt N121 2 EIXHbX o XyZnyZ Jabc gt Ia 2 Remember that the generalization and instantiation rules EG U6 El U are implicational rules not equivlalence rules In the case of UI and El be sure that the quantifiers you apply these rules to have scope over the entire statement in a line of a proof not just part of it Example done in class 1 EIXEyny gt Gb 2 Xyny Gb In the case of EG and UG be sure be sure the rules are applied to the entire statement in a line of a proof 1 XAX gt Bac XAX gt EIyByC 2 XAX gt EIyByC 1EG WRONG Done correctly in class 1 XAX gt Bac XAX gt EIyByC Consider now UG 1 XyLXy gt Ma XyLXy gt Ma 2 yLXy gt Ma 1 UI 3 xyny gtMa 2 UG WRONG Done correctly in class 1 XyLXy gt Ma XyLXy gt Ma 3 When applying UI take care than any variables that you instantiate to remain free after the instantiation 1 xEyny 2 Elyny 1U WRONG When the variable y is instantiated for x in this incorrect application of Ul it gets captured by the existential quantifier it falls within the scope of the quantifier The restriction on Ul prohibits this Compare 1 EIyEXSyx gtRC 2 XEySxy 39RC 4 As with U in applying El take care than any variables that you instanti ate to remain free after the instantiation 1 EIyEXByX 2 EIXBXX 1E WRONG 5 When applying UI remember that variables and constants must be sub stituted UNIFORMLK XlMX 0 LX V WKXYH onrswme Compare 3ylNy xNx a mu NZ 0 XNX gt LZX NZ XNX gt LZX NZ gt LZZ LZZ 3yLZy EXXEWLZy Fquot39quot N Mb 0 Lb yKby 1 MZ o LZ yKZy 1 Mb 0 Lb yny 1 MK 0 LC yny 1 El El El El correct correct WRO N G WRO N G EIXEyny 1 El 2 Simp 2 Simp 4 UI 53 MP 6 El 7 EG Note that in moving from Line 1 to Line 2 all free yvariables in Ny o xNx gt Lyx are replaced with Zvariables in NZ 0 xNx gt sz in accordance with El the latter is an instance of ElyNy o xNx gt Lyx On the other hand note that in moving from Line 6 to Line 7 we only replaced one occurrence of 2 with an occurrence of y This is perfectly permissiny by El as LZZ is also an instance of EIyLZy 6 Remember that we may never use El to instantiate to a variable that occurs free previously in the proof 1 xEyny 2 Elyny 1 U 3 GXX 2 El WRONG 4 EIXGXX 3 EG 7 Be aware of problems that can arise with the variables involved in appli cations of U6 1 Elx yDyX 2 yDyX 1 El 3 Dyx 2 U 4 XDXX 3 UG WRONG This violates UG because Dyx is not an instance of x Dxx Again 1 EIXGXS 2 Gys 1 El 4 Xst 2 UG WRONG This violates UG because the variable y is free on a line derived by El 81 Implicational Rules of Inference Comment The focus of the rest of the course will be on systems of natural deduction in which one uses a set of inference rules to demonstrate step by step that the conclusion of an argument follows from the premises Advantages of Natural Deduction 0 Generally less cumbersome than truth tables 0 Reflects more closely the way we actually reason Definition sorta A proof is a series of steps that leads by way of valid inference rules from the premises of a symbolic argument to its conclusion An inference rule is valid if and only if any statement that follows from a set of statements by means of the rule must be true if all of the statements in the set are true Implication Rules Rule 1 Modus ponens MP 19 gt q p q 1 If it s either raining or snowing the ground is wet R S gt W 2 It s either raining or snowing R S 80 3 The ground is wet W Rule 2 Modus tollens MT 19 gt q NC Np 1 If it s either raining or snowing the ground is wet R S gt W 2 The ground is not wet N W 80 3 It is neither raining nor snowing N R S Rule 3 Hypothetical syllogism HS p gt q q gtr pgtr 1 If it s raining the ground is wet 2 Ifthe ground is wet you should wear your boots So 3 If it s raining you should wear your boots Rule 4 Disjunctive syllogism DS p v q p v q Np N C 39 q p 1 Either the Aggies will win or UT will win 2 UT will not win 80 3 The Aggies will win So So A thA N A Rule 5 Constructive dilemma CD p q p 7 q 8 39 7 s Either the Aggies will win or UT will win Ifthe Aggies win College Station will go wild If UT wins Austin will go wild Either College Station or Austin will go wild Rule 6 Simplification Simp p o q p o q p q The Aggies will win and UT will not The Aggies will win Rule 7 Conjunction Conj p q 19 C The Aggies will win 2 UT will not win So 3 The Aggies will win and UT won t Rule 8 Addition Add p 19 V q 1 The Aggies will win 80 2 Either the Aggies will win or UT will win Comment The Greek metavariables p q 1quot can be replaced by any WFF as long as the replacement is uniform throughout the argument 0 The following are both instances of MT AaB lP gtQ Rl gtSlt gtT NB NNSlt gtT NA NlP gtQO NEH The first one is obviously an instance of MT A has been substituted for p and B for q The second is a little harder to see Here P gt Q o N R has been substituted for p and S lt gt T for q Hence for the q part ofthe MT schema we have S lt gt T Note that the following is not an instance of MT A gtB B NA The second line in a genuine instance of MT must be the negation of the consequent of the conditional in the first line Hence to get a legitimate instance of MT B in the second line would have to be replaced by B Note that the pattern exhibited by the argument above is valid It is just not the pattern of modus tollens Examgle A proof for A G gt K K gt B gt F A o B F 1 A V G gt K 2 K gt B gt 3 A o B F The completed proof nicely formatted 1 A G gt K 2 K gt B gt 3 A o B F 4 A 3 Simp 5 A G 4 Add 6 K 15 MP 7 B gt F 26 MP 8 B 3 Simp 9 F 78 MP The implication rules above are contrasted with the equivalence rules introduced in the next section The chief difference between the two is that implication rules cannot be applied to parts of a line in a proof equivalence rules can be so applied Example The following is not an instance of modus ponens A gtB gtC B C Some Rules of Thumb Rule of Thumb 1 Work backwards Begin by looking at the conclusion Try to find it or its components in the premises Apply rules to extract the conclusion or its components In the lat ter case you will need to to apply rules to construct the conclusion from those components Rule of Thumb 2 Apply the inference rules to break the premises down We apply these two rules of thumb to a particular argument Examgle thA The example nicely formatted NP7WPP N ZoAY ZoA gtU WVNU NW Y ZoAY ZoA gtU WVNU NW Y NU 34DS ZOA 25MT NY 16DS Rweof mmbBHmecommmmncm ansaswwnmnuamrmat does not appear in the premises use the rule of addition Examgle L 2 3 NoM gtT NOONN Theexampmmcdy nnw e P TJS VFquot NNOM gtT NO gtM NOONN NO M NN NNOM T TVS ZTVS LTVS 38mp 2AMP 38mp 56Com 1JMP ampAw Summary of the Implicational Rules of Inference Rule 1 Rule 2 Rule 3 Rule 4 Rule 5 Modus ponens MP Modus tollens MT Hypothetical syllogism HS Disjunctive syllogism DS Constructive dilemma CD P gtq P gtq Nq Np P gtq q gt7quot pgtr PVC PVC NP Nq PVC P gt7quot q gt3 39 TVS Rule 6 Simplification Simp Rule 7 Conjunction Conj Rule 8 Addition Add P39q P39q p q 93 Constructing Proofs In this section we extend the method of proof introduced in Chapter 8 to predicate logic by adding four new rules two for each quantifier NOTE All of the rules of statement logic will continue to apply in predicate logic Notably equivalence rules will still be applicable inside quantified WFFs Example 1 xAX gt Bx X BX gt AX 2 XAx sNNBx 1 DN 3 X BX gt AX 2 Cont Some Preliminary Definitions only implicit in the text Definition The scope of a quantifier in a formula 79 is the shortest WFF occurring immediately to the right of the quantifier Examples In the WFF XFX amp Pa the scope of the quantifier x is Fx In the WFF mayny amp aszyz H Hzxn the scope of the quantifier x is EIyny amp EIzGyz lt gt Hzx that of Ely is ny and that Of EIZ is Gyz lt gt HZX Definition An occurrence of a variable x that is in the scope of a quantifier for that variable Le a quantifier of the form 13 or 313 is said to be bound An occurrence of a variable that is not bound is said to be free Example The first occurrence of the variable x not counting its occurrence in the quanti fier is bound in the WFF xPx gt Qx the second occurrence is free Definition A variable 13 is free for a free variable y in 79 if no occurrence of y occurs in the scope of a quantifier of the form 13 or x in 79 The idea here is that one variable is free for another in a formula 73 if the first vari able wouldn t get captured by a quantifier if it were substituted for the second variable in 73 Example The variable y is free for x in EIzPx 0 Q2 the variable 2 is not Definition An instance of a quantified WFF x or 33 is any WFF obtained by the following two steps 1 Remove the initial quantifier x or 33 as the case may be 2 In the WFF resulting from Step 1 where t is either a name or a variable that is free for x in 79 uniformly replace all free occurrences of the variable x in 79 by occurrences of t We signify the resulting instance by 7 where t is the lnstantla name or lnstantla variable as the case may be Example The WFFs VXFX gt Gx and EIXFX gt GX have instances Fa gt Ga Fb gt Gb FZ gt GZ Universal lnstantiation Ul Ul allows us to infer from an assertion about everything in a given universe a corresponding statement about a given individual Example All politicians are egomaniacs Jesse is a politician Therefore Jesse is an egomaniac 1 XPx gt EX 2 Pj Ej One might be tempted to use MP here but Premise 1 does not have the proper form Premise 1 is a universally quantified statement what we need is a condi tional statement in which Pj is the antecedent To derive this we need Ul Universal lnstantiation Ul x 39 7 where 7 is any instance of 110 Given the notion of instance defined above we can distinguish two forms of Ul one for individual constants and one for variables Universal Instantiation Ul x x PC 79y where c is any individual where y is any variable and constant and PC is an in 73y is an instance of as stance of 110 Now we can complete the above proof correctly 1 XPX gt EX 2 Pj 3 Pj gt 1 U1 4 23 MP Errors to Avoid Be very sure that you only apply UI to statements that universally quantified not to universally quantified parts of statements eg 1 N XAX 2 N AC 1 UI MISTAKE 1 XAX gt Ba 2 Ax gt Ba 1 UI MISTAKE Contrast the second of these with a correct application of Ul 1 XAX gt Ba 2 Ax gt Ba 1 UI OK The scope of the quantifier makes all the difference Existential Instantiation El El allows us to infer from a general statement that something has a certain prop erty to a statement to the effect that some particular thing has that property so long as nothing has been assumed about that thing For this latter reason a certain restriction is placed on the rule Existential Instantiation El Elm 39 79y where 73y is an instance of 39073 and y is any variable not occur ring free previously in the proof y is known as the instantia variable in the application of El Examples 1 EIXAX 2 Ay 1E 1 EIXAX 0 Ba 2 AX 0 Ba 1 El Errors to Avoid There are two common errors in the application of El instantiating a name in stead of a variable and violating the restriction on the variable y These errors are illustrated in the following examples lnstantiating to a Name 1 EIXAX 2 AC 1 El MISTAKE Violating the condition on variables in instances 1 EIXAX 2 EIyBy Ay o By 3 Ay 1 El OK 4 By 2 El MISTAKE 5 Ay o By 34 Conj Universal Generalization UG UG lets us infer a universal quantification from a statement derived about an arbitrary individual about which no assumptions have been made Universal Generalization UG 73y x where 73y is an instance of 07 and y is not free in any line derived by an application of El Example XAX y Ay gt NBy X N BX 1 XAX 2 yAy gt N By X N BX 3 AX 1 UI 4 AX gt N BX 2 UI 5 NBX 34 MP 6 X N BX 5 UG Errors to Avoid There are two common errors in the application of UG instantiating on a name instead of a variable and violating the restriction on the instantial variable y These errors are illustrated in the following examples Generalizing on a Name 1 AC 2 XAx 1UG MISTAKE Violating the condition on variables in instances 1 EIXAX 2 AX 1 El 3 XAX 2 UG MISTAKE Existential Generalization EG EG lets us infer that something in general has a given property from the fact that some particular object does Existential Generalization EG 7 Elm where 7 is any instance of 110 As with UI given the notion of instance we can distinguish two forms of EG one for constants and one for variables Existential Generalizaztion EG 79C 79y Elm Elm where c is any individual where c is any individual constant and PC is an in constant and 73y is an in stance of Elm stance of Elm Example yAy gt N By X3yAX gtN By 1 yAy gt N By X3yAX gt N By 2 AX gt N BX 1 UI 3 EIyAX gt NBy 2 EG 4 XEyAx gt By 3 UG EG enables us to give proofs with particular conclusions Example XN PX gt QX EIXRXO NQX EIXRX o PX 1 XN PX gt QX 2 EIXRX o N QX EIyRy o Py 3 The complete proof nicely formatted L ltxgtlt Px a ox 2 EIXRX o N QX EIyRy o Py 3 Ry o N Qy 2 El 4 NPy gt Qy 1 UI 5 NPy gtNN Qy 4 DN 6 N Qy gt Py 5 Cont 7 NQy 3 Simp 8 Py 67 MP 9 Ry 3 Simp 10 Ry o Py 89 Conj 11 EIyRy o Py 1O EG Example X EIyQy gt N PX EIXRX o PX EIXEZRX o Qz L X 330C231 gt N PX 2 EIXRX o PX EIXEZRX o Qz 3 RX 0 PX 2 El 4 EIyQy gtPX 1U 5 PX gt EIyQy 4 Cont 6 Px 3 Simp 7 ElyQy 56 MP 8 Qy 7 El 9 Rx 3 Simp 10 RX 0 Qy 89 Conj 11 EIZRX o QZ 1O EG 12 EIXEZRX o QZ 11 EG Note that we had to apply El to line 2 before applying UI to line 1 to be able to make the proof work If we had applied UI to line 1 first to obtain the WFF in line 4 we would not have been able to use El to obtain the WFF in line 3 as it would have violated the restriction on variables in El This leads to our first Rule 039 Thumb Rule of Thumb 1 Apply El before U A related rule 0 thumb illustrated in especially lines 4 and 5 Rule of Thumb 2 Universaly instantiate to free variables or individual constants and apply the rules of statement logic Generally speaking that is one wants to instantiate as many quantifiers as nec essary until one gets to a point where one can apply the rules of statement logic to usually atomic WFFs 91 Predicates and Quantifiers Expressive Limitations of Statement Logic Many intuitively valid arguments in ordinary language cannot be represented as valid in statement logic For example 0 This house is red Therefore something is red All logicians are exceptional Saul is a logician Therefore Saul is excep onaL No politicians are honest Some politicians are administrators Therefore some administrators are not honest Every horse is an animal Therefore every head of a horse is a head of an animal Represented in statement logic under appropriate schemes of abbreviation these arguments look like this Obviously all three of these symbolized arguments are invalid in statement logic You should know how to prove that The problem The validity of the above arguments rests in large measure on subsentential components of the constituent statements eg the name Saul the plural common noun logicans the verb phrase is exceptional and the quantifier All Because the basic unit of statement logic is the atomic statement statement logic is incapable of representing these features of the arguments that are crucial to their validity In this chapter we will extend statement logic with the apparatus and methods necessary for representing the above arguments adequately and proving their validity Predicates and Quantifiers Recall the four Standard Forms of categorical statements Categorical Statement Form Universal affirmative All 8 are P Universal negative No S are P Particular affirmative Some 8 are P Particular negative Some 8 are not P To represent these statements we need to supplement the language of state ment logic with new elements corresponding to those noted above The first kinds of elements we need are those corresponding to names and verb phrases Individual constants a u Predicate letters A Z Individual constants will represent names of individual things like the logician Saul Kripke the city of Austin and the number 17 Predicate letters standing alone are just statement letters However when combined with individual con stants and names they stand for verb phrases like is a man and is mortal and relational predicates like is the head of which we will not study in this section Individual constants and predicate letters will enable to represent the subsen tential structure simple atomic sentences and boolean combinations of such Example s represent Saul and Let L represent is a logician and let a represent Arthur 0 Saul is a logician Ls o Saul and Arthur are logicians Ls 0 La To represent more complex sentences like categorical statements we need to introduce the apparatus of quantifiers and variables Individual variables v w x y z An individual variable can be thought of as a placeholder for a name in a sen tence Example 0 is a logician Lx or Lw or Ly etc o is the head of ny or va or Hvy or ny etc NB Expressions like Lx and ny are not statements but statement func tions because replacing a variable with a constant yields a statement Here s a rigorous definition Definition A statement function is the result of replacing one or more occurrences of an individual constant K in a statement or statement function containing n with occurrences of an individual variable Example Lx is a statement function because it is the result of replacing the occurrence of s in Ls with an occurrence of x ny is a statement function because it results from replacing the occurrence of a in the statement function Hxa with an occurrence of y Variables are used together with quantifiers to symbolize categorical statements and other sentences containing all every no some at least one etc Quantifiers x Elx y Ely and so on for the other variables x y etc are called universal quantifiers and are used to translate uni versal categorical statements and more generally statements containing all every each and usually any Elx Ely etc are called existential quantifiers and are used to translate particular categorical statements and more generally statements containing some at least one as in At least one student scored a 100 a as in A woman won the race there is as in There is a planet beyond Pluto and there are as in There are cats that have no fur As we will see No as in No politicians are honest can translated equally well by either quantifier Translating Categorical Statements Universal Affirmatives Let L stand for is a logician again and let E stand for is exceptional Ordinary English All logicians are exceptional Can be paraphrased as Everything is such that if it is logician then it is exceptional o In logical English Logicese For all individuals x ifx is a logician then x is exceptional 0 Fully translated xLx gt Ex In general All S are P is translated into predicate logic as xSr gt Pm where on is any variable Note that the arrow usually goes with the universal quantifier Universal Negatives Let P stand for is a politician and let H stand for is honest 0 Ordinary English No politicians are honest 0 Can be paraphrased as 0 Everything is such that if it is politician then it is not honest o It is false that something is both a politician and honest o In logical English 0 For all individuals x ifx is a politician then x is not honest o It is not the case that there is an individual x such that x is a politician and x is a honest 0 Fully translated O XPx gt N HX O EIXPX o HX In general No S are P is translated into predicate logic as either xSac gt w Pm or w EIacSr 0 P36 where on is any variable Particular Affirmatives Let P stand for is a politician again and let A stand for is an administrator 0 Ordinary English Some politicians are administrators 0 Can be paraphrased as Something is such that it is both a politician and an administrator o In logical English For some individual x x is a politician and x is an admin istrator Fully translated ElxPx o Ax In general Some S are P is translated into predicate logic as EIacSr 0 P36 where on is any variable Note that the dot usually goes With the existential quanti er Particular Negatives 0 Ordinary English Some administrators are not honest 0 Can be paraphrased as Something is such that it is both an administrator and not honest o In logical English For some individual x x is an administrator and x is not honest 0 Fully translated ElxAx o w Hx In general Some S are not P is translated into predicate logic as EIacSr o w Pm where on is any variable Stylistic Variants for Categorical Statements Recall that each type of categorical statement has both a standard form and multiple stylistic variants that essentially mean the same thing Universal affirmative xSr gt Pm Universal negative xSac gt w Pm N EIacXSac 0 Par All men are animals Every man is an animal Each man is an animal Men are animals Any man is an animal Anything that is a man is an animal Only animals are men No politicians are logicians No politician is a logician All politicians are nonlogicians No one is a politician if a logician There are no politicians who are logicians All politicians fail to be logicians Only nonlogicians are politicians Particular affirmative EIacSr 0 Pac Particular negative EIacSr o N Pm Some women are actors Some cyclists are not triathletes Some woman is an actor Some cyclist is not a triathlete At least one woman is an actor At least one cyclist isn t a triathlete There is a woman who acts There is a nontriathlete cyclist Something is both a woman and an actor Not every cyclist is a triathlete Note that Not every S is a P is more faithfully translated as N xSac gt Pm As we will prove this is equivalent to ElacSr o N Pm Although they are the most common forms containing quantifiers not every quantified statement is a categorical statement or a stylistic variant of one No tably we often make unqualified quantified statements that is statements where we are talking about everything or something in general There are dogs Elx Dx A god exists Elx Gx Some things are best left unsaid Elx Bx Everything is beautiful x Bx All things are known by God x Kxg And of course it is possible to form boolean combinations of quantified state ments There are dogs and cats No gods exist EIXDX o EIyCy N Elx Gx or x N Gx If no gods exists then the universe has no purpose N Elx Gx gt N U A Grammar for Predicate Logic Definition If P is a predicate letter and t1 tn are individual constants or variables then Punt is an atomic formula Note that the case where n 0 tells us that our statement letters from statement logic are also atomic formulas Let 79 and Q stand for any expression ie any string of symbols in the language of predicate logic then we define the notion of a wellformed formula WFF of predicate logic as follows 1 Every atomic formula is a WFF of predicate logic 2 If is a WFF so is 79 3 If 79 and Q are WFFs so are 79 c Q 79 V Q 73 gt Q and 79 lt gt Q 4 If 79 is a WFF and 13 any variable then x and 3x are WFFs Nothing else is a WFF of predicate logic 83 Five More Equivalence Rules In this section the remaining five equivalence rules are intro duced Rule 14 Distribution Dist poq7 poqVp07 pvmo pV Vr Examgle A proof for F G o L F L gt D D 1 FVGOL 2 FVL gtD D Rule 15 Exportation Exp Wom rwnaw Examgle Aprooffor Wo D gtJ W D gtJ 2 NW 39D gtNJ Rule 16 Redundancy Re 19 3 3 p 0 p p 3 3 19 V p Examgle A proof for R I R gt B I gt B B 1 RVI 2 R gtB 3I gtB B Rule 17 Material Equivalence ME plt gtq p gtQ q gtp plt gtq pqVp q Examgle Aproof forW lt gt L F B B gtL NF NW Wlt gtLVF B B gtL FPNT NF NW Rule 18 Material Implication MI 19 lt gt q r 19 V q Example A proof for N E gt N S NN gt w S 1 NVE gtS N gtS More Rules of Thumb Rule of Thumb 6 Material implication can lead to useful ap plications of distribution See above proof Rule of Thumb 7 Distribution can lead to useful applications of simplication See above proof Rule of Thumb 8 Addition can lead to useful applications of material implication Examples 12 Forms and Counterexamples Consider the following arguments 1 All oaks are trees 2 All trees are plants 80 all oaks are plants 1 All monauli are flageolets 2 All flageolets are fippIeflutes So all monauli are fippIeflutes These arguments have the same form namely Form 1 1 All A are B 2 A B are C 80 all A are C A B and C here stand for terms Definition A term is a word or phrase that stands for a Class Le a collection or set of things General diagram of the logic of this argument form C Plants B Trees Another valid form 1 All emeralds are gems 2 Some rocks are not gems So some rocks are not emeralds 1 All collies are dogs 2 Some animals are not dogs 80 some animals are not collies These arguments also have the same form namely Form 2 1 All A are B 2 Some C are not B So some C are not A The logic here can be diagrammed in any of four possible ways depending on how the second premise is realized the Cs might not overlap the Bs at all hence also the As the Cs might overlap the Bs but not the As the Cs might overlap the As hence also the Bs and the Cs might completely include the As but only overlap the Bs as their must be some Cs that are not B In every case however we see that when the premises are true the conclusion is as well and hence the argument must be valid Definition sorta An argument form is a pattern of reasoning Definition An argument that results from uniformly re placing letters in an argument form with terms or state ments when appropriate is called a substitution in stance of that form Comment The two arguments preceding the form in each case above are substitution instances of the respective forms Definition A counterexample to an argument form is a substitution instance whose premises are wellknown truths and whose conclusion is a wellknown falsehood Form 3 1 All A are B 2 All C are B So all A are C A Counterexample to Form 3 1 All birds are animals 2 All dogs are animals So all birds are dogs Here is a diagram for the counterexample Showing invalidity by counterexample 1 Identify the form of the argument 2 If the validity of the argument is suspect attempt to produce a substitution instance of the argument form in which the premises are obviously true and the conclusion obviously false 3 Conclude that the argument is invalid Example 1 All determinists are fatalists 2 Some fatalists are not Calvinists So some Calvinists are not determinists Form of the argument 1 All A are B 2 Some B are not C 80 some C are not A Counterexample 1 All dogs are animals 2 Some animals are not oollies So some oollies are not dogs Example 1 No capitalists are philanthropists 2 All philanthropists are altruists So no capitalists are altruists Form of the argument 1 No A are B 2 All B are C 80 no A are C Counterexample 2 steps Begin with an obviously false conclu sion and work backwards use simple well understood concepts eg biological kinds 1 No dogs are B 2 All B are animals 80 no dogs are animals Notice we start with our obviously false conclusion and fill in for the terms A and C Now all we need to do is find an appropriate term for B to complete our counterexample 1 No dogs are cats 2 All cats are animals 80 no dogs are animals Limitations of the method of Counterexamples 1 The method cannot show that a valid form is valid o Finding a substitution instance with true premises and a true conclusion does not show validity 2 Inability to find a counterexample of itself does not establish validity o Perhaps we are just not being clever enough A final complication Arguments can and typically do have more than one form Example 1 All determinists are fatalists 2 All fatalists are unhappy So all determinists are unhappy In addition to a valid form this has the invalid form A B so C But note an argument is valid if any of its forms is valid