CMSC 250 (0201&0202) Homework 3 Fall 2005Due 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 oryou will lose points.1. Construct a logical expression that is equivalent to the following circuit.NOTNOTANDORORPQRX(a)NOTNOTORANDNOTPQRX(b)2. For each of the following input signals: (a) P=1, Q=0, R=1, and (b) P=0, Q=0, R=1, findthe output X for each of the circuits given in the figures below.ANDORANDNOTNOTNOTNOTANDORPQRPQR13. Convert the following numbers from one base to another:(a) 4510=2=16(b) DE AB16=2(c) 11011012=10(d) 51410=24. Find the following:0011111+110110010011001100+110110111015. For each of the following, let W (x, y) mean that x has visited y, where the universe of discoursefor x is the set of all students in your school (P for people) a nd the universe of discourse fory is the set of all Web sites (S for sites). For ease of writing assume all first names are uniqueamong the members of this domain. Express each of the following statements in a simpleEnglish sentence.(a) W (S arah, www.att.com)(b) ∃x ∈ P, W(x, www.imdb.org)(c) ∃y ∈ S, W (Jose, y)(d) ∃y ∈ S, (W (Joe, y) ∧ W (Tom,y))(e) ∃y ∈ S, ∀z ∈ P, (y = David ∧ (W (David, z) → W (y, z)))(f) ∃x ∈ P, ∃y ∈ P, ∀z ∈ S, ((x = y) ∧ (W (x, z) ↔ W (y, z)))6. Let F (x, y) be the statement “x can fool y” where the universe of discourse for both is theset of all people in the world (P for people). Use quantifiers to express each of the followingstatements:(a) Everybody can fool Fred.(b) Evelyn can fool everybody.(c) Everybody can fool somebody.(d) There is no one who can fool everybody.(e) Everyone can be fooled by somebody.(f) No o ne can fool both Fred and Jerry.(g) Nancy can fool exactly two people.(h) There is exactly one person whom everybody can fool.(i) No one can fool him/herself.(j) There is someone who can fool exactly one person besides himself or herself.7. Explain why (∀x ∈ U, P (x)) ∧ (for allx ∈ U, Q(x)) is not equivalent to ∀x ∈ U, (P (x) ∧
View Full Document
Unlocking...