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.
   1. Write a logical expression that corresponds to this circuit.
      • Answer: $(P \wedge R) \vee (\sim P \wedge Q)$
   2. 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:
        
   3. Write a logical expression that is equivalent to your expression from part (a), but without using any OR gates.
      • Answer: $\sim ( \sim (P \wedge R) \wedge \sim (\sim P \wedge Q))$
   4. Draw the circuit diagram corresponding to your expression in part (c).
      • Answer:
        

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. $10110110 = -74_{10}$
   2. $BC49A_{16} = 2742232_8$
   3. $147_{16} = 327_{10}$
   4. $10001011 + 00011111 = 10101010_2$
   5. $00111001 - 00011101 = 00011100_2$

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.

   1. The decimal system uses the digits 0-9. What are the digits in the base-4 system?
      • Answer: 0, 1, 2, 3.
   2. 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:

        
        
        

   3. 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 $2^n$ 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 $2^n$. In other words, if you have a base-32 number system, group the bits in fives, since $32 = 2^5$.

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.
   1. ``All cows eat grass.''     Domain: $C =${cows}.     Predicates: $G(x) = x$ eats grass.
      • Answer: $\forall x \in C \ G(x)$
   2. ``All cows eat grass.''     Domain: $U =$ universal set.     Predicates: $G(x) = x$ eats grass; $W(x) = x$ is a cow.
      • Answer: $\forall x \in U \ W(x) \to G(x)$
   3. ``Some teachers are also students.''     Domain: $T =$ {teachers}.     Predicates: $S(x) = x$ is a student.
      • Answer: $\exists x \in T \ S(x)$
   4. ``Some teachers are also students.''     Domain: $U =$ universal set.     Predicates: $S(x) = x$ is a student; $R(x) = x$ is a teacher.
      • Answer: $\exists x \in U \ R(x) \wedge 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.
   1. Are `` $\forall x \in D \ (P(x) \wedge Q(x))$'' and `` $(\forall x \in D \ P(x)) \wedge (\forall x \in 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 $\{x_1, x_2, x_3, \ldots\}$, then
        $$\forall x \in D \ P(x) \wedge Q(x)$$
        is logically equivalent to
        $$P(x_1) \wedge Q(x_1) \wedge P(x_2) \wedge Q(x_2) \wedge P(x_3) \wedge Q(x_3) \wedge \cdots,$$
        which, by commutativity, is logically equivalent to
        $$(\forall x \in D \ P(x)) \wedge (\forall x \in D \ Q(x)).$$

   2. Are `` $\exists x \in D \ (P(x) \wedge Q(x))$'' and `` $(\exists x \in D \ P(x)) \wedge (\exists x \in D \ Q(x))$'' equivalent statements?
      • Answer: No. The above argument does not apply to or statements. For example, let $D = {\bf {Z}}$, and let $P(x)$ mean ``$x$ is even'' and $Q(x)$ mean ``$x$ is odd.'' Then it is true that
        $$(\exists x \in D \ P(x)) \wedge (\exists x \in 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
        $$\exists x \in D \ (P(x) \wedge Q(x))$$
        because no integer is both even and odd.

        Note: A more thorough explanation is on page 92 of the textbook.

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.

   1. Everyone has some sport that they enjoy.
      • Answer: $\forall x \in P \ \exists y \in S \ E(x, y)$
   2. There is someone who doesn't enjoy any sports.
      • Answer: $\exists x \in P \ \forall y \in S \ \sim E(x, y)$
   3. Every sport is enjoyed by someone (possibly a different someone for each sport).
      • Answer: $\forall y \in S \ \exists x \in P \ E(x, y)$
   4. There is a sport that nobody enjoys.
      • Answer: $\exists y \in S \ \forall x \in P \ \sim E(x, y)$

7. Define a predicate $K(r, s)$ to satisfy these conditions: `` $\forall m \in {\bf {Z}}\ \exists n \in {\bf {Z}}\ K(m, n)$'' is true, but `` $\exists n \in {\bf {Z}}\ \forall m \in {\bf {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).

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -nonavigation -antialias_text -antialias hw3ans

The translation was initiated by Phillip Kirlin on 2004-02-18

Web Accessibility