math vic
Exam #1: Solution
1. a) Using a truth-table, show that p q r q p r
p q r p q r q p 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 F F T T
b) Syntactically show that p q r p q r (Use the logical equivalences)
1. p q r 1. Given
2. p q r 2. Definition of Conditional
3. p q r 3. Associative Property
4. p q r 4. Double Negation
5. p q r 5. DeMorgan’s Law
6. p q r 6. Definition of Conditional
2. For the Boolean function given by the table below.
x y z F(x,y,z)
1 1 1 1
1 1 0 1
1 0 1 0
1 0 0 0
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 1
a) Find the sum-of-products expansion for F. xyz xyz x y z x y z
b) Simplify your answer to a) using a Karnaugh map.
xy x y
c) Simplify your answer to a) using the Quine-McCluskey Method
1. xyz 111 11_ {1,2}
2. xyz 110 00_ {3,4}
3. x y z 001
4. x y z 000
xy x y
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 * *
01 10
b) Find a regular expression for the finite state automata below.
*
00 11
4. Translate the following statements into first-order logic. The domain is all people. Let ( , )H x y be the
statement “x has heard of y” and let ( , )L x y be the statement “x likes y”
a) Somebody likes everybody. ,x yL x y
b) Somebody likes everybody they have heard of. , ,x y H x y L x y
c) Everybody likes themselves. ,xL x x
d) Everybody likes somebody they have never heard of. , ,x y H x y L x 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.
____________
p q
p r
q r
r
__________________________
p r
q s
p q r s
The second one is invalid. Let , , ,p F q T r F s T
1. p q 1. Given
2. p r 2. Given
3. q r 3. Given
4. p r 4. Defn of Conditional, 1
5. q r 5. Defn of Conditional, 2
6. q r 6. Resolution 1,4
7. r r 7. Resolution 6,5
8. r 8. Idempotent Law
6. Give a direct proof for one of the statements below and give a proof by contraposition for the other one.
If n is odd, then n is odd. Proof: (Direct)
Assume n is odd. Then 2 1n k for some k.
So, 2 1 2 2 1 2 1 1 2 1n k k k k where 1k k , i.e. n is odd. QED
If 3n is odd, then n is odd. Proof: (Contraposition)
Assume n is not odd. Then 2n k for some k.
So, 3 6 2 3 2n k k k where 3k k , i.e., 3n is even.
Since no number is both even and odd, 3n is not odd. QED