Homework 2

CS 280 - Spring 2002

Due: Friday, February 8

Part A

1. 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. Every dog has his day
   2. For every action there is an equal and opposite reaction
   3. Every golfer will eventually be defeated by a better golfer.
   4. For some x, if x>1 then x²>x.
       
2. Problem 66, page 185 in the text. (which conclusions are valid?)

Part B

3. Problem 18, page 35 in the text. (Express using quantifiers and determine truth value) 
    
4. 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 ® [p Ù (q Ú ¬ p)]
   2. [(p Ù r) ® (p Ú q)] ® (r ® q)

Part C

5. For each of the following, give an argument using the rules of inference (pages 169 and 174 in the text) to show that the conclusion follows from the hypotheses.
   1. Hypotheses: If there is gas in the car then I will go to KMart. If I go to KMart then I will buy some Martha Stewart designer shower curtains.  I do not buy shower curtains.  Conclusion: There is not gas in the car or the car is broken.
   2. Hypotheses: Everyone in the Discrete Structures class loves proofs.  Someone in the Discrete Structures class has never taken History.  Conclusion: Someone who loves proofs has never taken History.
       
6. Define a₁ = 3 and a₂ = 5.  We recursively define a_n+1 = 3a_n-2a_n-1.  Find a nonrecursive formula for a_n and use induction to prove your formula is correct.