CMSC 250 (0201&0202) Homework 3 ANSWERS Fall 2005

Due Wed Sept 21 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. Construct a logical expression that is equivalent to the following circuit.
   1. ANSWER: $(\sim P \wedge Q) \vee (\sim R \vee Q)$
   2. ANSWER: $\sim ((\sim P \vee Q) \wedge \sim R)$
2. For each of the following input signals: (a) P=1, Q=0, R=1, and (b) P=0, Q=0, R=1, find the output $X$ for each of the circuits given in the figures below.

   ANSWERS:

   p=1, q = 0, and r = 1 --> x = 0

   p=0, q = 0, and r = 1 --> x = 1

   p = 1, q = 0, and r = 1 --> x = 0

   p = 0, q = 0, and r = 1 --> x = 1

3. Convert the following numbers from one base to another:
   1. $45_{10} = \underline {\hskip 40pt}_{2} = ANSWER: 2D_{16}$
   2. $DEAB_{16} = ANSWER: 1101 1110 1010 1011_{2}$
   3. $1101101_{2} = ANSWER: 109_{10}$
   4. $514_{10} = ANSWER: 1000000010_{2}$
4. Find the following:

   $0011111$ $+ 110110$ $\overline{\hskip 50pt}$ $010011001100$ $+ 11011011101$ $\overline{\hskip 80pt}$

   ANSWERS:

   1010101

   101110101001

5. For each of the following, let $W(x,y)$ mean that x has visited y, where the universe of discourse for x is the set of all students in your school (P for people) and the universe of discourse for y is the set of all Web sites (S for sites). For ease of writing assume all first names are unique among the members of this domain. Express each of the following statements in a simple English sentence.
   1. $W(Sarah, www.att.com)$ ANSWER: Sarah has visited att.com.
   2. $\exists x \in P, W(x, www.imdb.org)$ ANSWER: Someone in my school has visited imdb.org.
   3. $\exists y \in S, W(Jose, y)$ ANSWER: Jose has visited at least one site.
   4. $\exists y \in S, (W(Joe, y) \wedge W(Tom, y))$ ANSWER: There's at least one site that both Joe and Tom have visited.
   5. $\exists y \in P, \forall z \in S, (y \neq David \wedge (W(David, z) \rightarrow W(y,z)))$ ANSWER: There is a student other than David that has at least visited all of the sites that David has visited.
   6. $\exists x \in P, \exists y \in P, \forall z \in S,((x \neq y) \wedge (W(x,z) \leftrightarrow W(y,z)))$ ANSWER: There are at least two different students that have visited exactly the same sites.
6. Let $F(x,y)$ be the statement ``x can fool y'' where the universe of discourse for both is the set of all people in the world (P for people). Use quantifiers to express each of the following statements:
   1. Everybody can fool Fred. ANSWER: $\forall x \in P, F(x, Fred)$
   2. Evelyn can fool everybody. ANSWER: $\forall x \in P, F(Evelyn,x)$
   3. Everybody can fool somebody. ANSWER: $\forall x \in P, \exists y \in P, F(x,y)$
   4. There is no one who can fool everybody. ANSWER: $\sim (\exists x \in P, \forall y \in P, F(y,x))$
   5. Everyone can be fooled by somebody. ANSWER: $\forall x \in P, \exists y \in P, F(y,x)$
   6. No one can fool both Fred and Jerry. ANSWER: $\forall x \in P, \sim (F(x,Fred) \wedge F(x,Jerry))$
   7. Nancy can fool exactly two people. ANSWER: $(\exists x,y \in P,((x \neq y) \wedge F(Nancy,x) \wedge F(Nancy,y))) \wedge \forall z \in P ( x \neq z \wedge y \neq z \rightarrow \sim F(Nancy,z))$
   8. There is exactly one person whom everybody can fool. ANSWER: $(\exists x \in P, \forall y \in P, F(y,x))\wedge (forall z \in P, x \neq z \rightarrow \exists w \in P, \sim F(w,z))$
   9. No one can fool him/herself. ANSWER: $\forall p \in P, F(p,p)$
   10. There is someone who can fool exactly one person besides himself or herself. ANSWER: $\exists x \in P, \exists y \in P, (x \neq y \wedge F(x,y)) \wedge \sim (\exists... ...in P, ((x \neq y \wedge x \neq z \wedge y \neq z) \wedge F(x,y) \wedge F(x,z)))$
7. Explain why $(\forall x \in U, P(x)) \wedge (\forall x \in U, Q(x))$ is not equivalent to $\forall x \in U, (P(x) \wedge Q(x))$. ANSWER: As the class email said as well as the web page - there was a typo on this question - both conjunctions should have been disjunctions.

Web Accessibility