MATH 213: Logical Equivalences, Rules of Inference and ...

1 MATH 213: Logical Equivalences, Rules of Inference andExamplesTables of Logical EquivalencesNote: In this handout the symbol is used the tables instead of to help clarify where one statementends and the other begins, particularly in those that have a biconditional as part of the statement. Theabbreviations are not T pIdentity / Idempotent(Conjunction)IdCp F pIdentity / Idempotent(Disjunction)IdDp F FDomination (Conjunction)DomCp T TDomination (Disjunction)DomD ( p) pDouble NegationDNp q q pCommutative (Conjunction)CCp q q pCommutative (Disjunction)CD(p q) r p (q r)Associative (Conjunction)AC(p q) r p (q r)Associative (Disjunction)ADp (q r) (p q) (p r)Distributive (Conjunction)DCp (q r) (p q) (p r)Distributive (Disjunction)DD (p q) p qDeMorgan s Law(Conjunction)DMC (p q) p qDeMorgan s Law(Disjunction)DMDp (p q) pAbsorption (Conjunction)AbCp (p q) pAbsorption (Disjunction)AbDp p FNegation (Conjunction)NegCp p TNegation (Disjunction)NegDTable 1.

2 Logical Equivalences1 EquivalenceNameAbbr (p= q) p qNegation of ImplicationNIp= q p qImplication to DisjunctionIDp= q q= pContrapositiveCp q p= qp q (p= q)(p= q) (p= r) p= (q r)(p= r) (q= r) (p q) = r(p= q) (p= r) p= (q r)(p= r) (q= r) (p q) = rTable 2: Logical Equivalences Involving ImplicationsEquivalenceNameAbbr. (p q) p qNegation of BiconditionalNB (p q) p qNegation of Biconditional(alternative)NBp q (p= q) (q= p)BiconditionalBp q p qContrapositive of Biconditionalp q (p q) ( p q)Table 3: Logical Equivalences Involving BiconditionalsTautology (so these will be true for pExcluded MiddleEM(p q) = pSimplificationSp= (p q)AdditionA(p (p= q)) = qModus PonensMP((p= q) (q= r)) = (p= r)Hypothetical SyllogismHS((p q) q) = pDisjunctive SyllogismDS( q (p= q)) = pModus TollensMT((p r) ((p= q) (r= s)))= (q s)Constructive DilemmaCDL(( q s) ((p= q) (r= s)))= ( p r)Destructive DilemmaDDL(p p) = pIdempotentIMTable 4.)

3 Additional Tautologies(Remember,tautologymeans these will always be true for any values ofp,q,r, ands.)2 Standard Rules of InferenceEach of the following is based on a tautology. Modus Ponenspp= q q Modus Tollens qp= q p Conjunctive Simplificationpq p Disjunctive Syllogismp q p q Hypothetical Syllogismp= qq= r p= r..Others not give in the book: Additionp p q Conjunctive Simplification (alternate version)p q p Resolutionp q p r q rExample the Rules of Inference used in each of the following arguments.(a) Alice is a math major. Therefore, Alice is either a math major or a major.(b) If it snows today, the college will close. The college is not closed today. Therefore it did not snowtoday.(c) If I go swimming, then I will stay in the sun too long.

4 If I stay in the sun too long, then I will , if I go swimming, then I will get rule of Inference to show that the premises Henry works hard , If Henry works hardthen he is a dull boy , and If Henry is a dull boy then he will not get the job imply the conclusion Henry will not get the job. Standard Rules of InferenceEach of the following is based on a Universal Instantiation x P(x) P(c) for any fixedc Universal GeneralizationP(c) for an arbitraryc x P(x) Existential Instantiation x P(x) P(c) for somec Existential GeneralizationP(c) for somec x P(x) Universal Modus Ponens x(P(x) = Q(x))P(c) Q(c) Universal Modus Tollens x(P(x) = Q(x)) Q(c) P(c)Example can you conclude about Henry, Jack, and Jill, given the following premises?

5 1. Every major has an Henry does not have an Jill has an Jack is a Affirming the Conclusionp= qq p Universal x S, P(x) = Q(x)For a particulars S,Q(s). P(s). Denying the Hypothesisp= q p q Universal x S, P(x) = Q(x)For a particulars S,6P(s). Q(s).Example 4(Valid or Fallacy?).Do the following represent valid arguments, or fallacies?(a) All students in this class understand logic. Pascal is a student in this class. Therefore, Pascal under-stands logic. (LetP(x) = xis in this class andQ(x) = xunderstands logic .)(b) Every major takes discrete mathematics. Esther is taking discrete mathematics. Therefore, Estheris a major. (LetP(x) = xis a major andQ(x) = xtakes discrete.)

6 (c) All parrots like fruit. My pet bird is not a parrot. Therefore, my pet bird does not like fruit. (LetP(x) = xis a parrot andQ(x) = xlike fruit .)(d) Everyone who eats granola every day is healthy. John is not healthy. Therefore John does not eatgranola every day. (LetP(x) = xeats granola every day andQ(x) = xis healthy .)Example 5.(If we can find the link.) Let F(x) = x s cable freezes I(x) = xis irritable S(x) = x s work suffers W(x) = xis wrongly convicted T(x, y) = xhas time to think abouty(a lot) E(x) = x s house explodes D(x) = xhas DirecTV Additional Puzzles1. Use all of the following premises to reach a conclusion: The only books in this library, that I do not recommend for reading, are unhealthy in tone.

7 The bound books are all well written. All the romances are healthy in tone. I do not recommend you to read any of the unbound all of the following premises to reach a conclusion: All my sons are slim. No child of mine is healthy who takes no exercise. All gluttons, who are children of mine, are 1 and 2 are attributed to Lewis Carroll5 No daughter of mine takes any Lady or the certain king likes to entertain himself by making his prisoners playa game to decide their fate. The prisoners are presented with two doors. In a room behind eachdoor is either a lady whom the prisoner may marry, or a tiger whom may eat the prisoner. A clueis written on each door and the prisoner decides which door to open based on these clues.

8 The cluesprovided to three prisoners brought before the king are below. Try to figure out which door eachprisoner should 1 is told that exactly one of the following clues is true and exactly one is 1:There is a lady behind this door and a tiger behind the 2:There is a lady behind one of the doors and a tiger behind the 2 is told that either both clues are true or both are 1:Either there is a tiger behind this door or a lady behind the second 2:There is a lady behind this 3 receives directions which are a bit tricker since the first two escaped. This prisoner is toldthat if a lady is behind door 1 then the clue on door 1 is true, but if a tiger is behind door 1 thenthe clue on that door is false.

9 Door 2 follows the opposite rule: if a lady is behind door 2 the clueon door 2 is false, but if a tiger is behind door 2 the clue on that door is 1:A lady is waiting behind at least one of the 2:A lady is waiting behind the other Let us assume that there are five houses of different colors next to each other on the same road. Ineach house lives a man of a different nationality. Every man has his favorite drink, his favorite brandof cigarettes, and keeps pets of a particular kind. The Englishman lives in the red house. The Swede keeps dogs. The Dane drinks tea. The green house is just to the left of the white one. The owner of the green house drinks coffee. The Pall Mall smoker keeps birds. The owner of the yellow house smokes Dunhills.

10 The man in the center house drinks milk. The Norwegian lives in the first house. The Blend smoker has a neighbor who keeps cats. The man who smokes Blue Masters drinks bier. The man who keeps horses lives next to the Dunhill smoker. The German smokes Prince. The Norwegian lives next to the blue house. The Blend smoker has a neighbor who drinks keeps fish as his pet?32 Commonly attributed to Raymond attributed to Albert Proofs using Rules of InferenceExample an argument (based on Rules of Inference ) to show that the hypotheses/premises( p q) = (r s), p= (r= w),(s= t) p, p qlead to the conclusionw StepReason(1)(2)(3)(4)(5)Example an argument (based on Rules of Inference ) to show that the hypotheses/premisesp= q, q r, r= (t s), s plead to the StepReason(1)(2)(3)(4)(5)7 Example an argument (based on Rules of Inference ) to show that the hypotheses/premisesp q, p= ( q r), r= slead to the StepReason(1)(2)(3)(4)(5)8