1)
Find the bitwise OR and bitwise AND of each the following pairs of bit
strings: Page 18, #33 a, b
a) 101 1110, 010 0001
b) 1111 0000, 1010 1010
2)
Construct a truth table for the following compound proposition: (p <=
span
style=3D'font-size:11.0pt;mso-bidi-font-size:12.0pt;font-family:Symbol;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Ro=
man";
mso-char-type:symbol;mso-symbol-font-family:Symbol'>Ú q) ® (p Å q)
3)
State the contrapositive of
“I come to class whenever there is going to be a quiz.”<=
span
style=3D'mso-spacerun:yes'>
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 ov=
er 65
miles per hour, then you will not get a speeding ticket. c) You get a speeding tic=
ket,
but you do not drive over 65 miles per hour. 5)
Show that the following implication is a tautology by using a truth table: =
p ® (p Ú q) 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 40, #7 a, c, d 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 propositio=
ns
using disjunctions, conjunctions and negations. a) $x P(x) b) $x ~P(x) c) ~$x P(x) Page 41, #17 a, c, e 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. 9)
Use an indirect proof to prove that if n is an integer and n<=
sup>3
+ 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. 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 th=
at
were used: 1. "x (C(x) ® P(x)) 2. C(Sally) ® P(Sally) 3. "x (P(x) ® W(x)) 4. P(Sally) ® W(Sally) 5. C(Sally) 6. P(Sally) 7. W(Sally) Page 74, #9c 11)
Let A =3D {a, b, c, d} and B =3D {y, z}.&n=
bsp;
Find the following: a) A ´ B b) B ´ B 12)
What is the Power Set of {C251, C343, B438}? 13)
Find these values: a) é3/4ù b) ë7/8û c) é3ù d) ë1/2 * ë5/2û û 14) Let f: A =
® B where A =3D {a, b, =
c, d}
and B =3D {1, 2, 3, 4} with
f(a) =3D 4, f(b) =3D 2, f(c) =3D 1 and f(d) =3D=
4 a) What is the domain of =
f ? b) What is the codomain o=
f f
? c) What is the range of <=
i>f
? d) Is f one-to-one=
? e) Is f onto? 15) Describe an algorithm t=
hat
takes as input a list of n integers in non-decreasing order and produces the
list of all values that occur more than once. Answer q=
uestions
2, 3 and 4 based on the following operation procedure Find_Last_Even (a location :=3D 0 i :=3D 1 while i if (ai mod 2)=
=3D 0
then location :=3D i i :=3D i + 1 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) =3D 2n + 5 18) What is the Big-O perfo=
rmance
of Find_Last_Even 19) Execute the greedy
‘change’ algorithm on page 175 with the following input: 20) Determine if f(x=
) is
O(x) for each of the functions: 21) Show that f(x) =3D=
x2
+ 2x + 2 is O(x2)
Change (0.25, 0.5, 0.01, .83)
Tell how many of each coin will be returned in change.
f(x) =3D 24 f=
(x)
=3D 5x + 7 f(x) =3D 3x2 - 2
I201/C2= 51 &= nbsp; &nbs= p; &= nbsp; &nbs= p; &= nbsp; &nbs= p; Name: ____________________________