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