CMSC250, Spring 2004 Homework 3 AnswersDue Wednesday, February 18 at the beginning of your discussion section.You must write the solutions to the problems single-sided on your own linedpaper, with all sheets stapled together, and with all answers written in sequentialorder or you will lose points.1. Consider a digital logic circuit that works as follows. There are three inputs, P , Q,and R. The output is Q’s value if P is 0, and R’s value if P is 1. In other words, Pselects which input, Q or R , to output.(a) Write a logical expression that corresponds to this circuit.Answer: (P ∧ R) ∨ (∼ P ∧ Q)(b) Draw the diagram for this circuit, using any combination of 2-input AND gates,2-input OR gates, and 1-input NOT gates.Note 1: A “2-input AND gate” simply means that the AND gates has two linescoming into it. It does not mean that you may only use two of these gates in yourcircuit; you may use any number of each type of gate.Note 2: Please label each gate in your circuit diagram to assist us in gradingyour work.Answer:PQR(c) Write a logical expression that is equivalent to your expression from part (a), butwithout using any OR gates.Answer: ∼ (∼ (P ∧ R)∧ ∼ (∼ P ∧ Q))(d) Draw the circuit diagram corresponding to your expression in part (c).Answer:PQR2. Perform the following conversions and calculations. Binary numbers are representedin 8-bit 2’s complement. Showing your work will assis t us in awarding partial credit.1(a) 10110110 = −7410(b) BC49A16= 27422328(c) 14716= 32710(d) 10001011 + 00011111 = 101010102(e) 00111001 − 00011101 = 0001110023. You’ve learned techniques for converting numbers between the binary, octal, and hex-adecimal number systems. A quick review (from textbook pages 72–73):• To convert an integer from hexadecimal to binary, write each hexadecimal digitof the integer in fixed 4-bit binary notation. Combine the resulting bits, end toend.• To convert an integer from binary to hexadecimal, group the bits into sets offour, starting from the right and adding leading zeros as needed. Convert thebinary numbers in each set of four into hexadecimal digits, and string all thedigits together.The procedures for octal are identical, but instead of making groups of four bits, makegroups of three bits.In the future, astronauts land on the planet Quatrella in a far away galaxy. Theinhabitants of Quatrella use a base-4 number system.(a) The decimal system uses the digits 0–9. What are the digits in the base-4 system?Answer: 0, 1, 2, 3.(b) How would you modify the conversion procedures ab ove to convert integers inbinary to and from the base-4 system?Answer: Instead of grouping by four bits (hexadecimal) or three bits (octal),group in two bits.For example:= 781010324010011101 0 3 22(c) To prepare for future encounters in outer space, the astronauts would like toknow how to convert binary integers to and from any base that is a power of two;that is, any base in the form 2nfor some integer n > 2. Describe procedures toaccomplish this.Answer: Follow the regular procedures above, but group bits into sizes of n,for a number system in base 2n. In other words, if you have a base-32 numbersystem, group the bits in fives, since 32 = 25.24. In each part below, you are given a statement, a domain, and one or more predicates.Translate the statement into symbolic logic using only those predicates and sets definedin that part.(a) “All cows eat grass.” Domain: C ={cows}. Predicates: G(x) = x eats grass.Answer: ∀x ∈ C G(x)(b) “All cows eat grass.” Domain: U = universal set. Predicates: G(x) = x eatsgrass; W (x) = x is a cow.Answer: ∀x ∈ U W (x) → G(x)(c) “Some teachers are also students.” Domain: T = {teachers}. Predicates:S(x) = x is a student.Answer: ∃x ∈ T S(x)(d) “Some teachers are also students.” Domain: U = universal set. Predicates:S(x) = x is a student; R(x) = x is a teacher.Answer: ∃x ∈ U R(x) ∧ S(x)5. Let P (x) and Q(x) be predicates and D be the domain of x. Justify each of youranswers in English.(a) Are “∀x ∈ D (P (x) ∧ Q(x))” and “(∀x ∈ D P (x)) ∧ (∀x ∈ D Q(x))” equivalentstatements?Answer: Yes. A universal statement can be thought of a generalization of anand statement. If the domain D is {x1, x2, x3, . . .}, then∀x ∈ D P (x) ∧ Q(x)is logically equivalent toP (x1) ∧ Q(x1) ∧ P (x2) ∧ Q(x2) ∧ P (x3) ∧ Q(x3) ∧ · · · ,which, by commutativity, is logically equivalent to(∀x ∈ D P (x)) ∧ (∀x ∈ D Q(x)).(b) Are “∃x ∈ D (P (x) ∧ Q(x))” and “(∃x ∈ D P (x)) ∧ (∃x ∈ D Q(x))” equivalentstatements?Answer: No. The ab ove argument does not apply to or statements. Forexample, let D = Z, and let P (x) mean “x is even” and Q(x) mean “x is odd.”Then it is true that(∃x ∈ D P (x)) ∧ (∃x ∈ D Q(x)),since there is an integer that is even and an integer is odd—there are an infinitenumber of both, in fact. However, it is not true that∃x ∈ D (P (x) ∧ Q(x))because no integer is both even and odd.Note: A more thorough explanation is on page 92 of the textbook.36. Let E(i, j) mean “person i enjoys sport j,” and let P = {people} and S = {sports}.For each of the following statements, re-write each one formally using symbolic logic.(a) Everyone has some sport that they enjoy.Answer: ∀x ∈ P ∃y ∈ S E(x, y)(b) There is someone who doesn’t enjoy any sports.Answer: ∃x ∈ P ∀y ∈ S ∼ E(x, y)(c) Every sport is enjoyed by someone (possibly a different someone f or each sport).Answer: ∀y ∈ S ∃x ∈ P E(x, y)(d) There is a sport that nobody enjoys.Answer: ∃y ∈ S ∀x ∈ P ∼ E(x, y)7. Define a predicate K(r, s) to satisfy these conditions: “∀m ∈ Z ∃n ∈ Z K(m, n)” istrue, but “∃n ∈ Z ∀m ∈ Z K(m, n)” is false.You do not need to justify your answer.Answer: There are many predicates that work. For example, let K(r, s) mean“r < s.” This works because for any integer m, there is always another integer n thatis greater (the first condition), but it is not true that there is some integer n that isgreater than all integers m (the second
View Full Document
Unlocking...