Homework # 10

1. Chapter 11 – page 749 #2

• the sleepy hare runs quickly
• the hare passes the tortoise
• the happy hare runs slowly
• the happy tortoise passes the hare
• the hare passes the happy hare

2. Chapter 11 – page 749 #4a

• {abbb}

3. Chapter 11 – page 749 #6

• If we apply the rule S -> 0S1 n times, followed by the rule S -> lambda, then the string 0ⁿ1ⁿ results. On the other hand, no other derivations are possible, since once the rule S -> lambda is used, the derivation stops. this proves the given statement.

4. Chapter 10 – page 736 #18

• (x’Å y) Å x alternatively 1 Å y which equals y’

5. Find the simplest expression for the function in the Karnaugh map below.

• wxz’ + wx’y’ + w’x’z’+ w’xy’

	yz	yz'	y'z'	y'z
wx		1	1
wx'			1	1
w'x'		1	1
w'x			1	1

6. Chapter 10 – page 708 #4c

x	y	z	y’	xy’z	xyz	(xyz)’	xy’z+(xyz)’
1	1	1	0	0	1	0	0
1	1	0	0	0	0	1	1
1	0	1	1	1	0	1	1
1	0	0	1	0	0	1	1
0	1	1	0	0	0	1	1
0	1	0	0	0	0	1	1
0	0	1	1	0	0	1	1
0	0	0	1	0	0	1	1

7. Chapter 3 – page 253 #4

• to be done in class - not to be graded

8. Chapter 3 – page 253 #12

• Gone over in class

• To prove that 3ⁿ < n! whenever n is a positive integer greater than 6.

9. Find the binary, octal and hexadecimal representations for the decimal number 37982

• 1001010001011110

• 1 001 010 001 011 110

1 1 2 1 3 6

• 1001 0100 0101 1110

9 4 5 E

10. Carry out the following operation in binary – you must show all work to get credit.

problem omitted

1. Chapter 1 – page 41 #16c

• true (the left hand side is always at least 2)

2. Chapter 1 – page 41 #22a

• let C(x) be “x is in your class “ Let P(x) be “x has a cellular phone”.
• Then we have "x P(x), the first way or
• "x (C(x) -> P(x)) the second way

3. Chapter 1 – page 27 #30c

• (p ÙT) ∨ (q Ù F)

4. Chapter 1 – page 27 #40

• We write down the truth table corresponding to the definition
• p q p|q

T T F

T F T

F T T

F F T

5. Chapter 1 – page 73 #2

• a) simplification
• b) disjunctive syllogism
• c) modus ponens
• d) addition
• e) hypothetical syllogism