CMSC250, Spring 2004 Homework 3Due 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.(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.(c) Write a logical expression that is equivalent to your expression from part (a), butwithout using any OR gates.(d) Draw the circuit diagram corresponding to your expression in part (c).2. 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.(a) 10110110 =10(b) BC49A16=8(c) 14716=10(d) 10001011 + 00011111 =2(e) 00111001 − 00011101 =23. 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.1The 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?(b) How would you modify the conversion procedures ab ove to convert integers inbinary to and from the base-4 system?(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.4. 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.(b) “All cows eat grass.” Domain: U = universal set. Predicates: G(x) = x eatsgrass; W (x) = x is a cow.(c) “Some teachers are also students.” Domain: T = {teachers}. Predicates:S(x) = x is a student.(d) “Some teachers are also students.” Domain: U = universal set. Predicates:S(x) = x is a student; R(x) = x is a teacher.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?(b) Are “∃x ∈ D (P (x) ∧ Q(x))” and “(∃x ∈ D P (x)) ∧ (∃x ∈ D Q(x))” equivalentstatements?6. 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.(b) There is someone who doesn’t enjoy any sports.(c) Every sport is enjoyed by someone (possibly a different someone f or each sport).(d) There is a sport that nobody enjoys.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
View Full Document
Unlocking...