math vic

Math 11: Exam 1 Solution (afternoon)

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

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

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

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

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

3.  p q p   3. DeMorgan’s Law

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

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

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

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

8. T q  8. Negation Law

9. q T  9. Commutative Law

10. T 10. Domination Law

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 0

1 1 0 0

1 0 1 0

1 0 0 0

0 1 1 1

0 1 0 1

0 0 1 1

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.

p q r  p q r  

T T T T

T T F F

T F T T

T F F T

F T T T

F T F T

F F T T

F F F T

xz xy

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

1. xyz 011 01_ (1,2)

2. xyz 010 0_1 (1,3)

3. xyz 001

01_ and 0_1 cover all minterms: xz xy

d) Design a circuit that represents this Boolean function.

13.2 Construct a finite state machine to model an error detector. The machine accepts indefinitely long strings from

the alphabet  0,1 . An error occurs if the last two inputs were both 0, or the last two inputs were both1. If an error occurs, output “Err”, otherwise output “OK”.

E.g.

Input 0 1 0 0 0 1 1 1 1 0 …

Output OK OK OK Err Err OK Err Err Err OK …

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 01 and end with 10 (500,000 points)

  *

01 0 1 10 0110 

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. Let  ,T x y be the predicate x is taking the

class y¸ where the domain of x is all students and the domain of y is all classes. Let ( )C y be the predicate “y is

a computer science class” and ( )M y be the predicate “y is a math class”. (1,000,000 points)

a) Some student is taking both a math class and a computer science class.

  ( ) ( , ) ( , )x y z M y C z T x y T x z     

b) Every student who is taking a computer science class is also taking a math class.

    ( ) ( , ) ( ) ( , )x y M y T x y y C y T x y    

c) Some student has taken all of the math classes.

 ( ) ( , )x y M y T x y  

d) Some student has not taken any computer science classes.

 ( ) ( , )x y C y T x y  

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

Inference . (5 points)

 p q r

p r

 

 

1.  p q r  1. Given

2.  p q r   2. Definition of Conditional, 1

3.    p q p r     3. Distributive Law, 2

4. p q  4. Simplification, 3

5. p q 5. Definition of Conditional, 4

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

“If m n is even and m is even, then n is even.” (5 points)

Assume m n is even and m is even. Then 2m n k  for some k and 2m k for some k .

Then    2 2 2 2n m n m k k k k k          where k k k   , i.e., n is even.

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

“If m is even, then mn is even for any n.” (500,000 points)

Assume m is even. Then 2m k for some k. Then 2 2mn kn k  where 2k n  , i.e. mn is even.