CMSC 250 Fall 2004 -- Homework 3

Due Wed., Sept. 22 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 of the circuit must be the same as the value of $Q\wedge R$ whenever the value of $P$ is 1, and the output of the circuit must be the same as the value of $Q \vee R$ whenever the value of $P$ is 0.
   1. Write a logical expression that corresponds to this circuit.

   2. Draw the diagram for this circuit, using only a 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.

2. Perform the following conversions and calculations. Binary numbers shown here are represented in 8-bit 2's complement, and any binary numbers you give as answers should also be represented in 8-bit 2's complement. Showing your work will assist us in awarding partial credit.
   1. $10100111 = \underline{\hspace{3cm}}_{10}$
   2. $FACE_{16} = \underline{\hspace{3cm}}_{10}$
   3. $CC99_{16} = \underline{\hspace{3cm}}_{8}$
   4. $11001011 + 01101101 = \underline{\hspace{3cm}}_{2}$
   5. $01100011 - 00110111 = \underline{\hspace{3cm}}_{2}$
3. Translate each of the following English sentences into formal language -- that is, using the symbols $\forall, \exists, \in$, etc. Then write the negation of each statement in English, then translate the negation into formal language. In your formal language statements, you may only use the domains $P = \{$all people$\}$ and ${\bf {Z}}= \{$all integers$\}$. Be sure to define all of the predicates you invent. For example, you must write the line F(x) = ``x does fine'' if you want to use this predicate named F or C(y) = ``y is Chinese'' so that you can use this predicate named C.
   1. Every good boy does fine.
   2. Some Chinese speak Mandarin or Cantonese.
   3. All integers which are singly even are divisible by two but not by four.
   TURN OVER

4. Let $E(s, j)$ mean ``student $s$ majors in subject $j$,'' and let $S = \{$students $\}$ and $J = \{$subjects$\}$. For each of the following statements, re-write each one formally using symbolic logic.
   1. Every students has some subject that they major in.
   2. There is some student who does not major in any subjects.
   3. Every subject is majored by some students.
   4. There is a major that no student majors.

Web Accessibility