CMSC 250 Fall 2004 -- Homework 3 Answer

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 cicuit 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.
      Answer: $(P \wedge Q \wedge R) \vee (\sim P \wedge Q \vee R)$

   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.
      Answer:

      

2. Perform the following conversions and calculations. Binary numbers shown here are represented in 8-bit 2's complement, and your binary answers must 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}$
      Answer: -89
   2. $FACE_{16} = \underline{\hspace{3cm}}_{10}$
      Answer: 175316
   3. $CC99_{16} = \underline{\hspace{3cm}}_{8}$
      Answer: 146231
   4. $11001011 + 01101101 = \underline{\hspace{3cm}}_{2}$
      Answer: 00111000
   5. $01100011 - 00110111 = \underline{\hspace{3cm}}_{2}$
      Answer: 00101100
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.
   1. Every good boy does fine.
      Answer:

      $G(x) = x \mbox{ is a good boy}$, $F(x) = x \mbox{ does fine}$.
      $\forall x \in P \quad G(x) \rightarrow F(x)$
      Negation: Some good boys does not do fine.
      $\exists x \in P \quad G(x) \wedge \sim F(x)$

   2. Some Chinese speak Mandarin or Cantonese.
      Answer:

      $C(x) = x \mbox{ is a Chinese}$, $M(x) = x \mbox{ speaks Mandarin}$, $K(x) = x \mbox{ speaks Cantonese}$.
      $\exists x \in P \quad C(x) \rightarrow M(x) \vee K(x)$
      Negation: All Chineses do not speak Mandarin and Cantonese.
      $\forall x \in P \quad C(x) \wedge \sim M(x) \wedge \sim K(x)$

   3. All integers which are singly even are divisible by two but not by four.
      Answer:

      $S(x) = x \mbox{ is singly even}$, $T(x) = x \mbox{ is divisible by two}$, $F(x) = x \mbox{ is divisible by four}$.
      $\forall x \in Z \quad S(x) \rightarrow T(x) \wedge \sim F(x)$
      Negation: There is an integer which is singly even but is either not divisible by two or it is divisible by four.
      $\exists x \in P \quad C(x) \wedge \sim T(x) \vee F(x)$

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.
      Answer: $\forall x \in S \ \exists y \in J \ E(x,y)$
   2. There is some student who does not major in any subjects.
      Answer: $\exists x \in S \ \forall y \in J \ \sim E(x,y)$
   3. Every subject is majored by some students.
      Answer: $\forall y \in S \ \exists x \in S \ E(x, y)$
   4. There is a major that no student majors.
      Answer: $\exists y \in S \ \forall x \in S \ \sim E(x, y)$

Web Accessibility