CMSC 250 Homework 3 Spring 2006

Due Wed Feb 15 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. Use only the rules of inference that appear on the ``cheat sheet'' you were given to prove the following:

   1. P1	$(a\vee b)\wedge (c\vee d)$
      P2	$\sim (\sim b\rightarrow c)$
      Therefore	$a\leftrightarrow d$

   2. P1	$p \rightarrow q$
      P2	$p$
      P3	$q \rightarrow r$
      Therefore	$r$

   3. P1	$\sim (((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r)) \vee x$
      Therefore	$x$

2. Draw a circuit with inputs P, Q, and R, such that the output is 1 when at exactly two of the inputs are 1, and 0 otherwise. You can only use 2-input AND gates, 2-input OR gates, and NOT gates.

3. Redo the previous problem using only 2-input OR gates and NOT gates (you may not use any AND gates in this version).

4. Translate the following numbers from one base to another. Assume any 8-bit binary number is representing the value using 2's complement notation, but all other representations are only representing positive integers.:
   1. $11001001_{2}=\underline{\hskip 30pt}_{10}$

   2. $01011011_{2}=\underline{\hskip 30pt}_{10}$

   3. $A9B_{16} = \underline{\hskip 30pt}_{10}$

   4. $A9B_{16} = \underline{\hskip 30pt}_{2}$

   5. $29_{10} = \underline{\hskip 30pt}_2$

   6. $-14_{10} = \underline{\hskip 30pt}_2$

5. Translate the following English sentences into formal language. Then write the negation of the original sentence in informal language, and translate the negation into formal language. You may use symbols such $\forall, \exists, \in$ and mathematical and logical symbols. You may use the domains and predicates you believe are most appropriate to the sentence. Make sure you define what those domains and predicates are so that we can understand your translation.
   1. All cars are driven by a person.

   2. Some people don't drive cars.

   3. No cars have more than 24 tires.

6. Give the invesrse, the converse, and the contrapositive of each of the following statements:
   1. $\forall x\in{\bf {Z}}$ if $x$ is an even number, then $x+3$ is an odd number.

   2. $\forall s\in{\hbox{Students}} \exists a\in{\hbox{Fun Activities}}$ if s is frustrated with CMSC250, s will go do a.

   3. $\forall x\in{\bf {R}}\forall y\in{\bf {R}}\exists z\in{\bf {R}} (x<y)\rightarrow (x<z<y)$

7. Let the predicate $L(p,j) =$``person p laughs at joke j'', let $P=\{\hbox{People}\}$, and let $J=\{\hbox{Jokes}\}$ For each of the following statements, write the meaning of the statement using informal language, then negate the statement using formal notation, and write the meaning of the negation using informal language.
   1. $\forall{p\in P} \exists{j\in J} L(p,j)$

   2. $\forall{j\in J} \exists{p\in P} L(p,j)$

   3. $\exists{p\in P} \forall{j\in J} L(p,j)$

   4. $\exists{j\in J} \forall{p\in P} L(p,j)$

   5. $\forall{p\in P} \forall{j\in J} L(p,j)$

   6. $\exists{j\in J} \exists{p\in P} L(p,j)$

Web Accessibility