CMSC250 Spring 2004 Homework 3 Answers Due Wednesday February 18 at the beginning of your discussion section You must write the solutions to the problems single sided on your own lined paper with all sheets stapled together and with all answers written in sequential order 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 P selects 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 lines coming into it It does not mean that you may only use two of these gates in your circuit you may use any number of each type of gate Note 2 Please label each gate in your circuit diagram to assist us in grading your work Answer P Q R c Write a logical expression that is equivalent to your expression from part a but without using any OR gates Answer P R P Q d Draw the circuit diagram corresponding to your expression in part c Answer P Q R 2 Perform the following conversions and calculations Binary numbers are represented in 8 bit 2 s complement Showing your work will assist us in awarding partial credit 1 a 10110110 7410 b BC49A16 27422328 c 14716 32710 d 10001011 00011111 101010102 e 00111001 00011101 000111002 3 You ve learned techniques for converting numbers between the binary octal and hexadecimal number systems A quick review from textbook pages 72 73 To convert an integer from hexadecimal to binary write each hexadecimal digit of the integer in fixed 4 bit binary notation Combine the resulting bits end to end To convert an integer from binary to hexadecimal group the bits into sets of four starting from the right and adding leading zeros as needed Convert the binary numbers in each set of four into hexadecimal digits and string all the digits together The procedures for octal are identical but instead of making groups of four bits make groups of three bits In the future astronauts land on the planet Quatrella in a far away galaxy The inhabitants 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 above to convert integers in binary 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 10324 1 0 3 2 010011102 7810 c To prepare for future encounters in outer space the astronauts would like to know how to convert binary integers to and from any base that is a power of two that is any base in the form 2n for some integer n 2 Describe procedures to accomplish 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 number system group the bits in fives since 32 25 2 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 defined in that part a All cows eat grass Domain C cows Answer x C G x Predicates G x x eats grass b All cows eat grass Domain U universal set grass W x x is a cow Answer x U W x G x Predicates G x x eats Domain T teachers Predicates d Some teachers are also students Domain U universal set S x x is a student R x x is a teacher Answer x U R x S x Predicates c Some teachers are also students S x x is a student Answer x T S x 5 Let P x and Q x be predicates and D be the domain of x Justify each of your answers in English a Are x D P x Q x and x D P x x D Q x equivalent statements Answer Yes A universal statement can be thought of a generalization of an and statement If the domain D is x1 x2 x3 then x D P x Q x is logically equivalent to P 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 equivalent statements Answer No The above argument does not apply to or statements For example 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 infinite number 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 3 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 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 for 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 is true 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 that is greater the first condition but it is not true that there is some integer n that is greater than all integers m the second condition 4
View Full Document
Unlocking...