math vic

Exam #1: Solution 1. a) Using a truth-table, show that    p q r p q r    

p q r  p q r   p q r 

T T T T T

T T F F F

T F T T T

T F F T T

F T T T T

F T F T T

F F T T T

F T F T T

b) Using logical equivalences, show that    p q r p q r    

2. For the Boolean function given by the table below.

x y z F(x,y,z)

1 1 1 0

1 1 0 1

1 0 1 1

1 0 0 1

0 1 1 1

0 1 0 1

0 0 1 0

0 0 0 0

a) Find the sum-of-products expansion for F. xyz xyz xy z xyz xyz   

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

xz y z x y  (Other answers possible)

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

2.  p q r    2. Defn of Conditional

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

4.  p q r   4. DeMorgan’s Law

5.  p q r  5. Defn of Conditional

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

1. xyz 110 1_0 {1,3}

2. xyz 101 _10 {1,5}

3. xy z 100 10_ {2,3}

4. xyz 011 01_{4,5}

5. xyz 010

Take 10_, 01_ and either 1_0 or _10

xy yz xz  or xy yz yz 

d) Design a circuit that represents this Boolean function.

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

0,1

a) Design a Finite State Automata that accepts the strings matched by the regular expression     * *

00 11

b) Find a regular expression for the finite state automata below.

  *

00 11

4. Let ( , )W x y be the statement “author x wrote the book y” and  S y be the statement “the book y is short” Translate the following statements into first-order logic. Note that the domain of x is all authors, and the

domain of y is all books.

a) Every book has an author.  ,y xW x y 

b) There is an author who has not written any books.    ,x y W x y 

c) Every author has written a short book.   , ( )x y W x y S y  

d) Every book has exactly one author.   ( , ) ( , )y x W x y z W x z z y    

5. One of the following arguments is valid and one is invalid. For the one that is invalid, give a truth assignment that

shows this. For the valid argument, prove it is valid using the propositional equivalences and the propositional rules

of inference.

  ___________________

q r

p q r



    

____________

p q

p q r

q r



 

 

The second one is invalid. Let , ,p F q T r F  

1. q r 1. Given

2. q r  2. Definition of Conditional

3.  q r p   3. Addition

4.  p q r    4. Commutative Property

5.  p q r   5. Associative Property

6.  p q r   6. DeMorgan’s Law

7.  p q r  7. Definition of Conditional

6. Give a direct proof for one of the statements below and give a proof by contraposition for the other one.

If m is even and n is odd, then, then m n is odd.

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

   2 2 1 2 2 1 2 2 2 1 2 1 1 2 1m n k k k k k k k k k                    

where 1k k k    , so m n is odd. QED

If 2

n is odd, then n is odd.

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

Then  2 2 24 2 2 2n k k k   ( 2k k  ), so 2n is even. This means 2n is not odd. QED