Homework 1 Solution

CS 280 - Fall 2002

Part A

1. Can a compound proposition be both
   1. a tautology and satisfiable?  If yes then give an example.
      Yes: p �  � p [or in English: p or (not p)]
   2. not a tautology and satisfiable?  If yes then give an example.
      Yes: p
   3. a contradiction and satisfiable?  If yes then give an example.
      No.
   4. not a contradiction and satisfiable?  If yes then give an example.
      Yes: p
       
2. For each of the following Boolean expressions find a logically equivalent Boolean expression in which each variable appears at most once.  Use a truth table to demonstrate this logical equivalence.
   1. (� p) � (q � (� p � � q))
      p � � q [or in English: p or (not q)]
      Alternate answer: q � p [or in English: q implies p]
      

      p q	q � p	(� p) � (q � (� p � � q))
      T T	T	T         T          T
      T F	T	T         T          T
      F T	F	F          F          F
      F F	T	T          T          T

   2. [(p � r) � (q � � r)] � (r � (� p))
      � r � � p [or in English: (not r) or (not p)]
      

      p  r	� r � � p	[(p � r) � (q � � r)] � (r � (� p))
      T T	F	T     T     F          F      F
      T F	T	F     ?      ?          T      T
      F T	T	F     F      F         T      T
      F F	T	F     ?      ?          T      T

   Fonts for logical symbols are not consistent among browsers; the problems are restated below in a form that should be readable on any browser.

   1. (not p) implies (q implies (not p implies not q))
   2. [(p and r) or (q and not r)] implies (r implies (not p))

Part B

3. Problem 8, page 11 in the text.
   1. r and (not q)
   2. p and q and r
   3. r implies p
   4. p and (not q) and r
   5. (p and q) implies r
   6. r iff (p or q)
       
4. For each of the following English sentences, write an English sentence that is equivalent to its logical negation. It is likely that converting the sentence into qualifiers and logical connectives will help, but you are not required to do this. Your final answer should consist of just an English sentence.
   • English sentences can be ambiguous.  If you think a sentence is ambiguous then explain the possible meanings and indicate the meaning that you are using.
   • You do not have to decide whether you think the sentence is true or false.
   • You are not allowed to use the phrase, "It is not the case that..." or some equivalent and then just repeat the original sentence.
   • Example: Suppose the sentence is, "Every natural number is a multiple of 2 or a multiple of 3."  You can convert this to pseudo-mathematical notation as [for all]x (multiple(x,2) or multiple(x,3)).  Negating this, you get [there exists]x (not multiple(x,2) and not multiple(x,3)). This converts to English as, "There exists a natural number that is not a multiple of 2 and not a multiple of 3."  Only the final sentence needs to be turned in.
   1. Everybody loves somebody sometime.
      L(x,y,t) denotes x loves y at time t.
      The sentence is (for all x) (there exists y) (there exists t) L(x,y,t).
      Negating: (there exists x) (for all y) (for all t) (not L(x,y,t)).
      As a sentence: There is somebody who, over all time, never loves anyone.
   2. Every homework problem is nasty and unpleasant.
      N(x) denotes x is nasty; U(x) denotes x is unpleasant.  Universe is all homework problems.
      The sentence is (for all x)(N(x) and U(x)).
      Negating: (there exists x) ((not N(x)) or (not U(x))).
      As a sentence: There is a homework problem that is either not nasty or not unpleasant.
   3. Every week there is either homework or an exam (but not both).
      H(w) denotes there is homework on week w; E(w) denotes there is an exam on week w.
      The sentence is (for all w) (H(w) xor E(w)).
      Negating: (there exists w) (H(w) iff E(w)).
      As a sentence: There is a week when there is homework if and only if there is an exam.
      Alternate sentence: There is a week when there is both homework and an exam or there is week when there is neither homework nor exam.
   4. All 8-year-olds like to eat both ice cream and chocolate.
      I(x) denotes x likes to eat ice cream; C(x) denotes x likes to eat chocolate.  Universe is all 8-year-olds.
      The sentence is (for all x) (I(x) and C(x)).  This is basically the same as (b).
      Negating: (there exists x) ((not I(x) or (not C(x))).
      As a sentence: There is an eight-year-old who does not like to eat ice cream or does not like to eat chocolate.
    

Part C

5. Problem 14, page 34 in the text. 
   [I(x) is "has an Internet connection"; C(x,y) is "x and y have chatted over the Internet.]
   1. not I(Jerry)
   2. not C(Rachel, Chelsea)
   3. not C(Jan, Sharon)
   4. (for all x) (not C(x, Bob))  [Alternately: not (there exists x) C(x, Bob)]
   5. (for all x) (not (x=Joseph) implies C(Sanjay, x))
   6. (there exists x) (not I(x))
   7. (not (for all x) I(x)) [This is equivalent to the previous proposition.]
   8. (there exists x) (I(x) and (for all y) (not (y=x) implies not I(y)))
   9. (there exists x) (not I(x) and (for all y) (not (y=x) implies I(y)))
   10. (for all x) (I(x) implies (there exists y) C(x, y))
   11. (there exists x) (I(x) and (for all y) (not C(x,y)))
   12. (there exists x) (there exists y) (not C(x, y) and not (x=y))
   13. (there exists x) (for all y) C(x, y)
   14. (there exists x) (there exists y) (there exists z) (not (x=y) and not C(x, z) and not C(y, z))
   15. (there exists x) (there exists y) ( not (x=y) and (for all z) (C(x, z) or C(y, z)) )
       
        
6. Problem 32, page 36 in the text.
   [P(x) is "x is a clear explanation"; Q(x) is "x is satisfactory"; R(x) is "x is an excuse".]
   1. (for all x) (P(x) implies Q(x))
   2. (there exists x) (R(x) and not Q(x))
   3. (there exists x) (R(x) and not P(x))
   4. Yes.  From (b), we conclude that there is an excuse (call it e) that is not satisfactory.  Part (a) can be rewritten as (for all x) (not Q(x) implies not P(x)) [this is the contrapositive and can be shown to be equivalent via truth tables].  Thus from (a), we conclude that since e is not satisfactory it follows that e is not a clear explanation.  We have now found a specific example (e) that is an excuse that is not a clear explanation.  By definition of 'there exists' (c) follows.  Chapter 3 outlines a more formal process for proving this result.