UNIVERSITY OF WESTERN ONTARIO
Computer Science 2209b, Winter 2016-2017
Applied Logic for Computer Science
ASSIGNMENT 3
Given: Wednesday, March 1, Due: Wednesday March 8, 6:00pm
1) In a small prison, there are four individual rooms for prisoners. One of the
four prisoners is the dangerous and witty Zorro. The jailers want to be sure that
the prisoners, and especially Zorro, do not conspire to escape. At each room
door there is a switch. Design a combinatorial circuit, that causes the alarm to
ring in the main prison o�ce i↵ either Zorro’s room door and at least one other
room door is open, or if at least three room doors are open.
Follow these steps:
(i) Determine the Boolean function that needs to be implemented.
(ii) Find the sum-of-products expansion of the Boolean function in (i).
(iii) Simplify the expression obtained in (ii) by using a Karnaugh map.
(iv) Design a combinatorial circuit using AND gates, OR gates and inverters
that implements the simplified expression obtained in (iii).
2) Design a combinatorial circuit that receives as input a three-digit binary
number, n = p2p1p0, and has four outputs O1, O2, O3 and O4, where O1 is
the formula that says n is even; O2 is the formula that says that n, in decimal
notation, is 4 or 5; O3 is the formula that says that n, in decimal notation, is
2, 3, 4, or 6; O4 is the formula that says that n, in decimal notation, is prime.
Use the methodology described in Question 1). Justify your answers.
Continued on the next page
1
3) Simplify each of the following formulas using Karnaugh maps. Clearly circle
the blocks that you use for simplification in the Karnaugh maps. Use the fol-
lowing standard forms for Karnaugh maps in 3 respectively 4 variables.
yz yz y z yz
——————————————–
x
x
yz yz y z yz
——————————————–
wx
wx
w x
wx
(a) xyz + xyz + xy z + xyz + x y z
(b) wxyz + wxyz + wxy z + wxyz + wx yz
(c) wxyz + wxyz + wxyz + wxyz + w xyz + w x yz
(d) wxyz + wxyz + wxyz + wx yz + wx y z + wxyz + w xyz + w x yz
(e) wxyz+wxyz+wxyz+wxyz+wxyz+wxyz+w xyz+w xyz+w x yz
4) Translate in two ways each of the following statements into the language of
predicate calculus, using predicates, quantifiers and logical connectives. First,
let the domain consist of all the students in your class and second, let it consist
of all people.
(a) Everyone in your class has a cellular phone.
(b) Somebody in your class has seen a foreign movie.
(c) There is a person in your class who cannot swim.
(d) All students in your class can solve quadratic equations.
(e) Some student in your class does not want to be rich.
2