Test 1 provided tables

 

 

 

Test 1 - Sample - Solutions

 

Page 19, #37 a, b

1) Find the bitwise OR and bitwise AND of each the following pairs of bit strings: 

a)      101 1110, 010 0001

b)      1111 0000, 1010 1010

 

Page 19, #29a

2) Construct a truth table for the following compound proposition: (p Ú q) ® (p Å q) 

 

Page 18, #23

3) State the contrapositive of  “I come to class whenever there is going to be a quiz.” 

 

Page 17, #9 c, d, f

4) Let p and q be the propositions: 

p: You drive over 65 miles/hour

q: You get a speeding ticket

 

Write these propositions using p and q and logical connectives:

a)      You will get a speeding ticket if you drive over 65 miles per hour.

b)      If you do not drive over 65 miles per hour, then you will not get a speeding ticket.

c)      You get a speeding ticket, but you do not drive over 65 miles per hour.

 

Page 28, #9b

5) Show that the following implication is a tautology by using a truth table: p ® (p Ú q) 

 

Page 47, #7 a, c, d

6) Translate these statements into English, where C(x) is “x is a comedian” and F(x) is “x is funny” and the universe of discourse is all people.

a)      "x (C(x) ® F(x))

b)      $x (C(x) ® F(x))

c)      $x (C(x) Ù F(x))  

 

Page 47, #17 a, c, e

7) Suppose the universe of discourse of the propositional function P(x) consists of the integers 0, 1, 2, 3, and 4.  Write out each of these propositions using disjunctions, conjunctions and negations.

a)      $x P(x)

b)      $x ØP(x)

c)     Ø$x P(x)  

 

8) Use a direct proof to show that the sum of two odd integers is even.  First state what needs to be proved using the predicates Even(x) and Odd(x), then do the proof. 

Propositions

  1. Odd(n) is "n is an odd integer" or n = 2i + 1
     
  2. Odd(m) is "m is odd" or m = 2j + 1

Prove

"If n and m are odd integers, n + m is even"

"n"m (Odd(n) ^ Odd(M) ® Even(n+m))

Hypothesis

"n and m are odd integers"

n + m = 2i + 1 + 2j + 1 = Assume hypothesis, n and m are odd
2i + 2j + 2 = Add
2(i + j + 1) = Let k = i+j+1
2k Definition of even integer
\ n + m is even  

 

Page 85, #17a

9) Use an indirect proof to prove that if n is an integer and n3 + 5 is odd, then n is even.  First state what needs to be proved using the predicates Even(x) and Odd(x), then do the proof. 

Propositions

  1. Odd(n3 + 5) is "n3 + 5 is an odd integer" or n3 + 5 = 2k + 1
     
  2. Even(n) is "n is even integer" or n = 2k

Direct proof, p ® q

"If n3 + 5 is odd then n is even"

"n (Odd(n3 + 5) ® Even(n))

Indirect, use Contraposition, Øq ® Øp

"If  n is odd then n3 + 5 is even"

"n (Odd(n) ® Even(n3 + 5))

Hypothesis

"n is odd integer"

n = 2k + 1 Assume hypothesis, n is odd
n3 + 5 = (2k+1)3 + 5 Substitute
          = 8k3 + 12k2 + 6k + 6 Multiply
          = 2(4k3 + 6k2 + 3k + 3) Definition of even integer
\ n3 + 5 is even Øq ® Øp
"If  n is odd then n3 + 5 is even"
\ n is even p ® q
"If n3 + 5 is odd then n is even"

 

 

10) Let C(x), P(x) and W(x) be the following predicates:

C(x): x is in this class

P(x): x owns a PC

W(x): x can use a word-processing program

Assume the following premises:

C(Sally)

"x (C(x) ® P(x))

"x (P(x) ® W(x))

Annotate each line of the following argument by explaining the rules of inference that were used:

1.      "x (C(x) ® P(x))            Premise

2.      C(Sally) ® P(Sally)          Universal instantiation

3.      "x (P(x) ® W(x))            Premise

4.      P(Sally) ® W(Sally)         Universal instantiation

5.      C(Sally)                            Premise

6.      P(Sally)                            Modus ponens

7.      W(Sally)                           Modus ponens

11) Let A = {a, b, c, d} and B = {y, z}.  Find the following:

a)      A ´ B  = {(a, y), (a, z), (b, y), (b, z), (c, y), (c, z), (d, y), (d, z)}

b)      B ´ B = {(y, y), (y, z), (z, y), (z, z)}

 

12) What is the Power Set of set C = {C251, C343, B438}?  
P(C) = { {}, {C251}, {C343}, {B438}, {C251, C343}, {C251, B438}, {C343, B438}, {C251, C343, B438}}

 

13) Find these values:  Page 109, #9

a)      é3/4ù                    1

b)      ë7/8û                    0

c)      é3ù                       3

d)      ë1/2 * ë5/2û û        1

 

 

14) Let f: A ® B where A = {a, b, c, d} and B = {1, 2, 3, 4}

with f(a) = 4, f(b) = 2, f(c) = 1 and f(d) = 4

 

a)      What is the domain of f ?               A is the domain

b)      What is the codomain of f ?           B is the codomain

c)      What is the range of f ?                  {1, 2, 4} is the range

d)      Is f one-to-one?                              Not one-to-one because f(a) and f(d) map to the same value

e)      Is f onto?                                        Not onto because nothing maps to 3

 

15)  Page 177, #5

Figure 1

procedure Find_Last_Even (a1, a2, …, an: positive integers)

location := 0                          1

i := 1                                 1

while i £ n begin                      n+1

   if (ai mod 2) = 0 then               n

location := i                    n

   i := i + 1                           n

end

return location

16) Diagram Find_Last_Even.  Use diamond shapes for the test in an ‘if’ or ‘while, rectangles for regular statements, and an oval for a ‘return’ statement.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


17) Analyze Find_Last_Even for the number of operations it executes in terms of ‘n’.  Hint: you answer should be linear a function that is dependent on n, i.e., something like f(n) = 2n + 5
Answer: f(n) = 4n1 + 3n0

 

18) What is the Big-O performance of Find_Last_Even

Answer: By observation, f(n) = 4n1 + 3n0 is O(n)

19) Execute the greedy ‘change’ algorithm on page 175 with the following input:

Change (0.25, 0.5, 0.01, .83)
Tell how many of each coin will be returned in change.

Answer: 3 quarters, 1 nickel, 3 pennies

20) Determine if f(x) is O(x) for each of the functions:

f(x) = 10 Answer: Yes

f(x) = 3x + 7   Answer: Yes

f(x) = 3x2 - 2  Answer: No

21) Show that f(x) = x2 + 2x + 2 is O(x2)

 

Solution:

Must show:    x2 + 2x + 1 £ C x2

f(x) = x2 + 2x + 1

g(x) = x2

Need to determine

C the constant

k the value for x > k

Use algebra to solve the following inequality for constant C

f(x) £ C * g(x)

f(x) £ C * g(x) From definition
x2 + 2x + 1 £ C x2 substitute for f(x) and g(x)
1 + 2/x + 1/x2 £  C divide both sides by x2 
C ³ 1 + 2/x + 1/x2  

Know x > 0

1 + 2/x + 1/x2

C = 4

C ³ 1 + 2/x + 1/x2  
C = 4 ³ 1 + 2/k + 1/k2 substitute C=4 and k
1 + 2/1 + 1/12 £  C Maximum when k = 1

The constants C=4 and k=1

22)    Section 4.1, #3, p279

"n, n ≥ 1 P(n) = 12 + 22 ...+ n2  = n(n+1)(2n+1)/6

a) P(1) = 12 = 1(1+1)(2*1+1)/6 = 1(2)(3)/6 = 1

b) See a)

c) "k, k ≥ 1 P(k) = 12 + 22 ...+ k2  = k(k+1)(2k+1)/6

d)  P(k+1) = (k+1)(k+2)(2k+3)/6

e)

P(k+1)   = 12 + 22 ...+ k2 + (k+1)2 Definition
  = P(k)                  + (k+1)2 Substitute P(k)
   = k(k+1)(2k+1)/6 + (k+1)2 Induction Hypothesis
  = (2k3 +3k2 + k)/6 + (k2 + 2k + 1) Multiply
  = [(2k3 +3k2 + k) + 6(k2 + 2k + 1)]/6 Multiply
  = (2k3 +9k2 + 13k + 6)/6 Add
  = [(k2 +3k + 2)(2k+3)]/6 Factor (2k+3)
  = (k+1)(k+2)(2k+3)/6  

23) Give the resulting sets.

  1. {1, 2, 3} ∩ { 1, 2 }                         {1, 2}
     
  2. {1, 2, 3} ∩ { R, G, B }                    {}
     
  3. {1, 2, 3} ∩ ∅                                   {}
     
  4. {1, 2, 3} ∪ { 1, 4 }                         {1, 2, 3, 4}
     
  5. {1, 2, 3} ∪ {R, G, B }                    {1, 2, 3, R, G, B}
     
  6. {1, 2, 3} ∪ ∅                                  {1, 2, 3}

24) Give the resulting values.

  1. | {1, 2, 3} ∪ { 2, 3, 4 } |                 4
     
  2. {1, 2, 3} - { 1, 2 }                           {3}
     
  3. {1, 2, 3} - { 1, 2, 3 }                       ∅
     
  4. {1, 2, 3} - ∅                                    {1, 2, 3}

25) Prove De Morgan's 1st law: A U B ≡ A ∩ B

In a membership table, think of:

∩ is as ^ conjunction

∪ is as v disjunction

A U B ≡ A ∩ B

A B A ∪ B A U B A B A ∩ B
1 1 1 0 0 0 0
1 0 1 0 0 1 0
0 1 1 0 1 0 0
0 0 0 1 1 1 1

26) Find f  ○  g where

g: {R, G, B}  →  {red, green, blue}

g( R ) = red

g( G ) = green

g( B ) = blue

          f: {red, green, blue} → {Ford, Chevy}

f( red ) = Ford

f( green ) = Chevy

f( blue ) = Ford

a.    (f ○ g) (R) = f( g (R) ) = f(red) = Ford

b.    (f ○ g) (G) = Chevy

c.    (f ○ g) (B) = Ford

27) What are the following values?

  1.                      1+1+1+1+1+1 = 6
     
  2.             -20 + -21 + -22 + -23  = 1 -2 +4 -8 = -5
     

  3. 0+2+4 = 6

     

28) For:    sequence {tn}

tn = 7 - 3n

  1.  t5 = 7 - 3*5 = -8
     
  2.  t42 = 7 - 3*42

29)    Prove p ^ q is true, using logical rules of inference and equivalences, given:

            p

            p ® q

        ____________

            p
            p ® q
            ______
            q              Modus ponens

            p
            q
           __
           p ^ q         Conjunction

 

30) Two algorithms are analyzed to determine the number of instructions executed.

        Algorithm A execution cost is defined by:

                f( N ) = 2N2 + 4N

        Algorithm B execution cost is defined by:

                f( N ) = 4N2

        a)    Which function, A or B, dominates the other?                        B

      b)    Which algorithm, A or B, has the lowest cost for large N?     A

      c)    At what value of N, approximately, does the one function dominate the other?        N=15

31)  Big-O T/F

  1. 5 is O(n)                   T
  2. n2 is O(n)                  F
  3. n is O(n2)                  T
  4. 4n2+3n is O(n2)        T

32) Give the inverse of:

  1. ∃x ( x = 2)

    ¬∃x ( x = 2)  Ξ   ∀x ¬( x = 2)   Ξ   ∀x ( x ≠ 2 )

     

  2. ∀x (x2 > x)

    ¬∀x (x2 > x)  Ξ  ∃x ¬( x2 > x )   Ξ   ∃x ( x2 ≤ x )

     

  3. ∃x ( x2 = 2)

    ¬∃x (x2 = 2)   Ξ   ∀x ¬( x2 = 2 )   Ξ   ∀x ( x2 ≠ 2 )