math vic

Math 11: Exam 1 (morning) solution

1.1 Construct a truth-table for the proposition  p q r  (5 points)

1.3 Give a syntactic proof that  p p q  is a tautology.

(I.e. use logical equivalences to show that  p p q T   ) Justify each step in your proof. Do not use more than one logical equivalence per step. (5 points)

1.  p p q  1. Given

2.  p p q   2. Definition of conditional

3.  p p q   3. Associative Law

4.  p p q  4. Commutative Law

5. T q 5. Negation Law

6. q T 6. Commutative Law

7. T 7. Domination Law

p q r  p q r 

T T T T

T T F T

T F T F

T F F T

F T T T

F T F T

F F T T

F F F T

12.2-12.4 Consider the Boolean function given by the table below. (10 points)

x y z F(x,y,z)

1 1 1 1

1 1 0 1

1 0 1 1

1 0 0 0

0 1 1 0

0 1 0 0

0 0 1 0

0 0 0 0

a) Find the sum-of-products expansion for F.

xyz xyz xyz 

b) Simplify your answer to a) using a Karnaugh map.

xy xz

c) Simplify your answer to a) using the Quine-McCluskey Method

1. xyz 111 11_ (1,2)

2. xyz 110 1_1 (1,3)

3. xyz 101

11_ and 1_1 cover all of the minterms: xy xz

d) Design a circuit that represents this Boolean function.

13.2 Construct a finite state machine to model a newspaper vending machine. A newspaper costs $0.15. The

machine accepts nickels and dimes and does not make change. If the user has put in less than $0.15, the machine

will display the balance. When the user has put in enough money, the machine will display “Here’s your paper” and

resets itself. (10 points)

E.g.

Customer puts nickel into machine. Display is “0.05”

Customer puts another nickel into machine. Display is “0.10”

Customer puts dime into machine. Display is “Here’s your paper”

13.3 For this problem, all strings are in the set   *

0,1

a) Construct a regular expression for the set of strings that start with 00 and end with 11. (500,000 points)

  *

00 0 1 11

b) Construct a deterministic finite state automata that at accepts all and only those strings that start with 0 and end

with 1. (500,000 points)

1.4/1.5 Translate the following statements into predicate logic. The domain is Z (integers).

Use ( )P n for “n is prime” (10 points)

a) There is a prime number greater than 1.   1x P x x  

b) All prime numbers are greater than 1.   1x P x x  

c) There are at least two prime numbers.     x y P x P y x y    

d) There is a smallest prime number.      x P x y P y y x   

1.6 Prove the validity of the following argument using Logical Equivalences and the Propositional Rules of

Inference . (5 points)

p q

p r

q r

 

 

 

1. p q  1. Given

2. p r  2. Given

3. p q   3. Defn of Conditional, 1

4. q p   4. Commutative, 3

5. q p  5. Defn of Conditional, 4

6. q r 6. Hypothetical Syllogism, 5, 2

1.7 a) Give a direct proof or a proof by contraposition of the following statement:

“If 3 2n  is odd, then n is odd” (5 points)

Proof by contraposition:

Assume n is not odd. Then n is even, so 2n k for some k.

   3 2 3 2 2 2 3 1 2n k k k      where 3 1k k   . So, 3n+2 is even, which implies that it is not odd.

QED

b) Give a direct proof or a proof by contraposition of the following statement:

“If n is even, then 1n  is odd” (5 points)

Proof by contraposition:

Assume 1n  is not odd. Then 1n  is even, so 1 2 2 1n k n k n      is odd n is even.

Direct proof:

Assume n is even. Then 2n k for some k,

and  1 2 1 2 2 1 2 1 1 2 1n k k k k           where 1k k   , i.e. 1n  is odd.