CMSC250, Spring 2004 Homework 2 Answers

Due Wednesday, February 11 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. For each of the following statements, give its converse, inverse, and contrapositive in English sentences; be sure to label the three parts of each answer. You may change verb tenses to make your answers sound better.
   1. ``If one thinks, one must reach conclusions.''¹
      • Answer:
        • Converse: If one must reach conclusions, then one thinks.
        • Inverse: If one does not think, then one must not reach conclusions.
        • Contrapositive: If one must not reach conclusions, then one does not think.
   2. ``If you look good and dress well, you don't need a purpose in life.''²
      • Answer:
        • Converse: If you don't need a purpose in life, then you look good and dress well.
        • Inverse: If you do not look good or do not dress well, then you need a purpose in life.
        • Contrapositive: If you need a purpose in life, then you do not look good or do not dress well.
   3. ``California is a fine place to live if you happen to be an orange.''³
      • Answer:
        • Converse: If California is a fine place to live, then you happen to be an orange.
        • Inverse: If you don't happen to be an orange, then California is not a fine place to live.
        • Contrapositive: If California is not a fine place to live, then you don't happen to be an orange.
   4. ``You can be free only if I am free.''⁴
      • Answer:
        • Converse: If I am free, then you can be free.
        • Inverse: If you cannot be free, then I am not free.
        • Contrapositive: If I am not free, then you cannot be free.

2. Construct a complete truth table to help you determine if the following argument is valid or not. State whether it is valid or not, indicate the entries in the truth table that led you to your answer, and explain why those entries support your answer.

   	$p \to (q \vee r)$
   	$q \to \sim p$
   $\therefore$	$p \to r$

   • Answer:

     
     
     

     					Premise	Premise	Conclusion
     $p$	$q$	$r$	$\sim p$	$q \vee r$	$p \to (q \vee r)$	$q \to \sim p$	$p \to r$
     1	1	1	0	1	1	0	1
     1	1	0	0	1	1	0	0
     1	0	1	0	1	1	1	1	$\gets$ Critical row
     1	0	0	0	0	0	1	0
     0	1	1	1	1	1	1	1	$\gets$ Critical row
     0	1	0	1	1	1	1	1	$\gets$ Critical row
     0	0	1	1	1	1	1	1	$\gets$ Critical row
     0	0	0	1	0	1	1	1	$\gets$ Critical row

     
     
     The critical rows are the rows where all the premises are true. Since in all five critical rows the conclusion is also true, this argument is valid.

3. Use the rules of inference you were given to complete the two proofs below. Use the same format as was shown in class for these proofs -- each line of your proof must be justfied with the rule and line numbers you used to obtain that line.

   1. P1	$\sim x \vee w$
      P2	$(x \to y) \to (s \to z)$
      P3	$\sim z$
      $\therefore$	$s \to w$

      • Answer:

        
        
        

        Line	Statement	Rule	Lines Used
        1	$\sim (x \to y) \vee (s \to z)$	Definition of $\to$	P2
        2	$(x \wedge \sim y) \vee (\sim s \vee z)$	Definition of $\to$	1
        3	$(x \wedge \sim y) \vee \sim s \vee z$	Associativity	2
        4	$(x \wedge \sim y) \vee \sim s$	Disjunctive syllogism	3, P3
        5	$\ \vline \ s$	Assume	--
        6	$\ \vline \ x \wedge \sim y$	Disjunctive syllogism	4,5
        7	$\ \vline \ x$	Conjunctive simplification	6
        8	$\ \vline \ w$	Disjunctive syllogism	P1, 7
        9	$s \to w$	Closing conditional world	5-8

        
        Here's another way.

        
        
        

        Line	Statement	Rule	Lines Used
        1	$\sim (x \to y) \vee (s \to z)$	Definition of $\to$	P2
        2	$\ \vline \ s \wedge \sim w$	Assume	--
        3	$\ \vline \ \sim w$	Conjunctive simplification	2
        4	$\ \vline \ \sim x$	Disjunctive syllogism	P1, 3
        5	$\ \vline \ \sim x \vee y$	Disjunctive addition	4
        6	$\ \vline \ x \to y$	Definition of $\to$	5
        7	$\ \vline \ \sim \sim (x \to y)$	Double negation	6
        8	$\ \vline \ s \to z$	Disjunctive syllogism	1, 7
        9	$\ \vline \ s$	Conjunctive simplification	2
        10	$\ \vline \ z$	Modus ponens	8, 9
        11	$\ \vline \ z \wedge \sim z$	Conjunctive addition	10, P3
        12	$\sim (s \wedge \sim w)$	Closing cond world w/ contra	2-11
        13	$\sim s \vee \sim \sim w$	DeMorgan's law	12
        14	$\sim s \vee w$	Double negative	13
        15	$s \to w$	Definition of $\to$	14

        
        And yet another way.

        
        
        

        Line	Statement	Rule	Lines Used
        1	$\ \vline \ s$	Assume	--
        2	$\ \vline \quad \vline \ x \to y$	Assume	--
        3	$\ \vline \quad \vline \ s \to z$	Modus ponens	2, P2
        4	$\ \vline \quad \vline \ z$	Modus ponens	3, 1
        5	$\ \vline \quad \vline \ z \wedge \sim z$	Conjunctive addition	P3, 4
        6	$\ \vline \ \sim (x \to y)$	Closing cond world w/ contra	2-5
        7	$\ \vline \ x \wedge \sim y$	Definition of $\to$	6
        8	$\ \vline \ x$	Conjunctive simplification	7
        9	$\ \vline \ \sim \sim x$	Double negation	8
        10	$\ \vline \ w$	Disjunctive syllogism	P1, 9
        11	$s \to w$	Closing conditional world	1-10

   2. P1	$(a \wedge \sim b) \vee (c \wedge a)$
      P2	$(a \vee d) \to \sim f$
      P3	$c \to (f \vee \sim a)$
      $\therefore$	$\sim b$

      • Answer:

        
        
        

        Line	Statement	Rule	Lines Used
        1	$(a \wedge \sim b) \vee (a \wedge c)$	Commutativity	P1
        2	$a \wedge (\sim b \vee c)$	Distributive law	1
        3	$a$	Conjunctive simplification	2
        4	$\sim b \vee c$	Conjunctive simplification	2
        5	$a \vee d$	Disjunctive addition	3
        6	$\sim f$	Modus ponens	5, P2
        7	$\sim f \wedge a$	Conjunctive addition	6, 3
        8	$\sim (f \vee \sim a)$	Double negative, DeMorgan's law	7
        9	$\sim c$	Modus tollens	P3, 8
        10	$\sim b$	Disjunctive syllogism	9, 4

        
        Here's another way using proof by contradiction.

        
        
        

        Line	Statement	Rule	Lines Used
        1	$\ \vline \ b$	Assume	--
        2	$\ \vline \ \sim a \wedge b$	Disjunctive addition	1
        3	$\ \vline \ \sim (a \vee \sim b)$	DeMorgan's and Double neg	2
        4	$\ \vline \ c \wedge a$	Disjunctive syllogism	3, P1
        5	$\ \vline \ a$	Conjunctive simplification	4
        6	$\ \vline \ a \vee d$	Disjunctive addition	5
        7	$\ \vline \ \sim f$	Modus ponens	P2, 6
        8	$\ \vline \ c$	Conjunctive simplification	4
        9	$\ \vline \ f \vee \sim a$	Modus ponens	P3, 8
        10	$\ \vline \ \sim \sim a$	Double negation	4
        11	$\ \vline \ f$	Disjunctive syllogism	9, 10
        12	$\ \vline \ f \wedge \sim f$	Conjunctive addition	7, 11
        13	$\sim b$	Closing cond world w/ contra	1-12

4. Indiana Jones, the famous archeologist, is off on another adventure. Indy knows that in all his adventures he always has three tasks to accomplish: he must get the treasure, save the girl, and defeat the bad guy. However, being a college professor, Dr. Jones is also a very logical person. In fact, he has developed a set of rules to determine which of his three tasks he should complete first. The rules are:

   P1

   If Indy is in Europe or South America, he gets the treasure first.

   P2

   If Indy is in Asia or Africa, he saves the girl or defeats the bad guy first.

   P3

   Indy was almost squashed by a rolling boulder if and only if he is in South America or Africa.

   P4

   Indy is in neither Europe nor South America if he falls into a pit of snakes.

   P5

   Indy never defeats the bad guy first if he is in Africa.

   Indy can't remember which continent he is currently on, but he does remember that earlier in this adventure he fell into a pit of snakes and was almost squashed by a rolling boulder. Help him figure out which task he should do first.

   You may use the following propositions:

   $$e = t =$$ ``Indy is in Europe.'' ``Indy gets the treasure first.''

   $$f = g =$$ ``Indy is in Africa.'' ``Indy saves the girl first.''

   $$s = b =$$ ``Indy is in South America.'' ``Indy defeats the bad guy first.''

   $$a = p =$$ ``Indy is in Asia.'' ``Indy falls into a pit of snakes.''

   $$r =$$ ``Indy is almost squashed ``by a rolling boulder.

   
   
   1. Convert each of the rules P1-P5 to symbolic form using only the nine propositions defined above, and the operators $\wedge , \vee , \sim , \to$, and $\leftrightarrow$.
      • Answer:

        P1

        $(e \vee s) \to t$

        P2

        $(a \vee f) \to (g \vee b)$

        P3

        $r \leftrightarrow (s \vee f)$

        P4

        $p \to (\sim e \wedge \sim s)$

        P5

        $f \to \sim b$

   2. Convert the statements from the paragraph above into symbolic expressions, using the same nine propositions and the same operators as in part (a). Continue to list these as premises for your proof -- P6, etc.
      • Answer:

        P6

        $p$

        P7

        $r$

   3. Use the rules of inference you learned in class to determine which of the three tasks Indy should complete first. Be sure to use the same layout format as was shown in class for logic proofs -- same as in Question 3.
      • Answer:

        
        
        

        Line	Statement	Rule	Lines Used
        1	$[r \to (s \vee f)] \wedge [(s \vee f) \to r]$	Definition of $\leftrightarrow$	P3
        2	$r \to (s \vee f)$	Conjunctive simplification	1
        3	$s \vee f$	Modus ponens	2, P7
        4	$\sim e \wedge \sim s$	Modus ponens	P6, P4
        5	$\sim s$	Conjunctive simplification	4
        6	$f$	Disjunctive syllogism	3, 5
        7	$\sim b$	Modus ponens	P5, 6
        8	$a \vee f$	Disjunctive addition	6
        9	$g \vee b$	Modus ponens	P2, 8
        10	$g$	Disjunctive syllogism	9, 7

   4. Which task will Indy do first?
      • Answer: He will save the girl first.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -nonavigation -antialias_text -antialias hw2ans

The translation was initiated by Phillip Kirlin on 2004-02-11

Footnotes

... conclusions.''¹

Helen Keller (1880-1968)

... life.''²

Robert Pante

... orange.''³

Fred Allen (1894-1956)

... free.''⁴

Clarence Darrow (1857-1938)