1.      If  8 is odd, then 6 is even.
    1. What is the true value of the italicized statement above?   (2 points)

   true

    1. Explain why your answer to part a. is correct.                   (3 points)

because false implies true is true   OR

because a false premise implies anything  OR

8 is odd is FALSE, therefore it doesn’t matter what 6 is

 

  1.    Cucumbers are green and seedy
    1.  Which one(s) of the following are correct negation(s) of the italicized statement above?          Circle your answer(s)                           (2 points)

                                                              i.      Cucumbers are not green and not seedy.

                                                           ii.      Cucumbers are not green or not seedy. 

                                                         iii.      Cucumbers are green and not seedy.

ii    OR  cucumbers are not green or not seedy

    1. What equivalence rule helped you answer this question?      (3 points)

DeMorgan’s Law

 

  1.   Provide the definition of an algorithm                                       (5 points)

an unambiguous step by step solution for  solving a problem  in a

finite amount of time using a finite amount of space

 

  1. Use propositional logic to prove the following                              (10 points)

 

(A’  Ú  B)  Ù (B → C) → (A → C)   Example 17 p. 27

 

 

 

 

 

 

 

(I implies H) and (F or H’) and I implies F                Example 18 p. 28

 

25 points on this page – NEED TO CHOOSE  1 ALTERNATIVE FOR 4

 

1.  (A’  Ú  B)      hyp

2.  (B → C)        hyp

3.  A                 hyp  (deductive method)

4.  B                 1,3  D.S. OR Disjunctive Syllogism

5. C                  2,5  M.P.  or Modus Ponens

 

 

  1. How many binary strings of length 8  begin and end with 0? (each character is either the digit 0 or the digit 1)                                            (5 points)

1 * 2 * 2 * 2 * 2 * 2  * 2 * 1  OR  26 OR  64

  1. Using propositional logic, prove that the following argument is valid.  Use the statement letters shown                                                           (10 points)

If the ad is successful, then the sales volume will go up.  Either the ad is successful or the store will close.  The sales volume will not go up.  Therefore the store will close.    (A,S,C)

 

1.  A → S               hyp

2.  A Ú  C              hyp

3.   S’                    hyp

4.  A’ Ú S               1, implication

5.   A’                    4,3  D.S. Disjunctive Syllogism

6.   C                     2,5   D.S. Disjunctive Syllogism

 

  1. All people are tall and thin

Which of the following is the correct form of negation for the italicized statement statement above?  Circle your answer.                (5 points)

                                                              i.      Someone is short and fat

                                                           ii.       No one is tall and thin

                                                         iii.      Someone is short or fat

 

  1. (∃x)P(x) Ù(∀x)(P(x) → Q(x)) → (∃x) Q(x)

Justify each step in the following proof sequence of the above argument

                                                                                                (10 points)

1.  (∃x)P(x)                               hyp

2.  (∀x)(P(x) → Q(x))               hyp   

3.  P(a)                                      1 e.i.

4.  P(a) → Q(a)                          2 u.i.

5.  Q(a)                                    3,4  MP  OR Modus Ponens

6.  (∃x) Q(x)                            5  e.g.

 

  1. Translate the following argument into predicate logic.  Use the statement letters shown.   Do NOT determine its validity                            (5 points)

Every ambassador speaks only to diplomats, and some ambassador speaks to somone.  Therefore, there is a diplomat.     A(x), S(x,y), D(x)

 

(∀x) (∀y) ((A(x) Ù S(x,y)) →D(y)) Ù (∃x) (∃y) A(x) Ù S(x,y)) →(∃x)  D(x)

 

35 points this page

  1. Which of the following are true for all sets A,B, and C?               (5 points)
    1.  If  A ∩ B =Æ, then A Ì B         __F____
    2. B ∩ B = B                                 __T____
    3. (A’)’ = A                                    __T____
    4. (A – B ) ∩ (B – A) = Æ            __T____
    5. (A – B) ∪ (B – C) = A – C           __F____

 

  1.   What are Polya’s four steps to follow in problem solving?           (5 points)

1. Understand the problem     2.   Devise a plan

                            3.  Carry out the plan              4.   Look back

 

  1. An apartment building purchases a new lock system for its 175 units.  A lock is opened by punching in a two-digit code.  Why is the purchase that the apartment management made unwise?                                                (5 points)

because the number of 2 digit codes is only 100 so some apartments will have the same code

 

  1. A,B,C, and D are nodes on a computer network.  There are two (2) paths between A and C, two (2) between B and D,  three (3) between A and B,  and four (4) between C and D.  Along how many routes can a message from A to D be sent?                                                                                    (5 points)

  3*2 (A to B to D) + 4*2 (A to C to D) = 14

  1. A multiple-choice exam has 6 questions each with four possible answers, and 7 additional questions, each with 3 possible answers.  How many different answer sheets are possible?                                                    (5 points)

4 * 4  * 4 * 4 * 4 * 4 * 3 * 3 * 3 * 3 * 3 * 3 * 3   OR  46 * 37 

 

  1. How many of the three-digits integers between 100 and 999 inclusive (i.e.including 100 and 999) are divisible by 4 or 5?                        (5 points)

A is the set of numbers divisible by 4   B is the set of numbers divisible by 5

     A ∩ B  is the set of numbers divisible by 4 and 5 (i.e. divisible by 20)

|A| + |B| - | A ∩ B|30 points this page

 

900/4 = 225    900/5 = 180    225 + 180 = 405   900/20 = 45  405-45=  360

 

  1. A customer is ordering a computer.   The coices are 17”, 19” 21” or 23” monitor;  1.0 GHz, 1.3 GHz, 1.5 GHz, 1.7 GHz, or 2.0 GHz processor;  10X, 12X or 14X CD drive; 64 MG, 128 MB, or 256 MB RAM; optional fax card; optional sound card.   How many different machine configurations are possible?                                                                                    (5 points)

4 * 5 * 3 * 3 * 2 * 2 OR 720 

 

  1.  In a group of 24 people who like rock, country, and classical music, 14 like rock, 17 like classical, 11 like both rock and country, 9 like rock and classical, 13 like country and classical , and 8 like rock, country , and classical.  How many like country?                                                                      (5 points)

A is like rock    B is like classical  C is like Country  answer = 18

|A| = 14,  |B| = 17,   |A∩ B ∩ C | = 8,    | A∩ C| = 11  | A ∩ B| = 9   |B  ∩ C| = 13

  1.  In a group of 25 people, there must be at least 3 who were born in the same month?     
    1.  Is the above italicized statement true or false?                (2 points)

true

    1.  Justify (i.e. explain) your answer to part a.                      (3 points)

by the pigeon hole principle, since there are only 12 months in a year, 24 people would mean 2 per month, the 25th person has to go in a month with 2 people in it already

  1. In how many different ways can you seat 11 men and 8 women in a row?

(5 points)

19!    There are 19 different people so it’s a permutation question.

  1. A set of four coins is slected from a box containing five dimes and seven quarters.  Find the number of sets in which two are dimes and two are quarters.                                                                                     (5 points)

                                                         2                    3

     C(5,2) * C(7,2) =   5!    *  7!     5*4*3*2*1  *  7*6*5*4*3*2*1   OR  10*21 = 210

                              2!3!      2! 5!             2*1*3*2*1       2*1*5*4*3*2*1

 

 

28 points this page

  1. BONUS QUESTION
    Using propositional logic, prove that the following is valid.

(C → D) Ù(D’ or S) Ù (K’ → ‘S) Ù (K → (D Ù H)) Ù (H’ → C’)