Name (PRINTED):
Student ID #:
Section # (or TA's:
name and time)

CMSC 250

Quiz #4 ANSWERS

Wed., Feb. 15, 2006

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.

1. [9 pnts.] Give the long form of the logic expression represented by the truth table below (the long form means that each of the lines containing a 1 should be represented as a different term in the disjunction). Then use only the rules presented on the ``cheat sheet'' to reduce the equation to an expression that would require the smallest number of gates. The draw the circuit that represents the reduced expression.

   p	q	r	Output
   1	1	1	1
   1	1	0	1
   1	0	1	0
   1	0	0	0
   0	1	1	1
   0	1	0	0
   0	0	1	0
   0	0	0	0

   Long form of the expression: $(p \wedge q \wedge r)\vee (p \wedge q \wedge \sim r)\vee (\sim p \wedge q \wedge r)$ Reduce the expression:
   

   #	Statement	Rule Used
   1	$((p \wedge q) \wedge (r \vee \sim r)) \vee (\sim p \wedge q \wedge r)$	Assoc. & Distrib
   2	$((p \wedge q) \wedge t) \vee (\sim p \wedge q \wedge r)$	Negation
   3	$(p \wedge q) \vee (\sim p \wedge q \wedge r)$	Identity
   4	$q \wedge (p \vee (\sim p \wedge r))$	Comm & Distrib
   5	$q \wedge ((p \vee \sim p) \wedge (p \vee r))$	Distrib
   6	$q \wedge (t \wedge (p \vee r))$	Negation
   7	$q \wedge (p \vee r)$	Identity

   Draw the Circuit:
   
   
   
   
   
   
   
   
   $\downarrow$ TURN OVER $\downarrow$
2. [6 pnts.] Translate the following to/from the bases indicated: Assume they should all be done assuming 8-bit 2's complement is the storage representation.
   • $1B_{16}$ = 27 $_{10}$
   • $11001010_{2}$ =-54 $_{10}$
   • $-35_{10}$ =11100111$_{2}$
3. [15 pnts.] Prove the following using only the rules on the ``cheat sheet.''

   P1	$q \vee r$
   P2	$\sim m \rightarrow (n \wedge \sim p)$
   P3	$m \rightarrow x$
   P4	$p \vee (q \rightarrow r)$
   P5	$r \rightarrow p$
   	therefore $p \wedge m$

   #	Statement	Rule	Lines Used
   1	$\sim r \vee p$	Def of Impl	P5
   2	$(p \vee \sim r)\wedge (p \vee (q \rightarrow r)$	Comm & Conj Add	1,P4
   3	$p \vee (\sim r \wedge (q \rightarrow r)))$	Distrib	2
   4	$p \vee (\sim r \wedge (\sim q \vee r))$	Def of Impl	3
   5	$p \vee ((\sim r \wedge \sim q)) \vee (\sim r \wedge r))$	Distrib	4
   6	$p \vee ((\sim r \wedge \sim q) \vee C)$	Negation	5
   7	$p \vee (\sim r \wedge \sim q)$	Identity	6
   8	$p \vee (\sim q \wedge \sim r)$	comm	7
   9	$p \vee \sim (q \vee r)$	DeMorgan's	8
   10	$p$	Disj Syll	9, P1
   11	$\vert\sim m$	Assume
   12	$\vert n \wedge \sim p$	Modus Ponens	11, P2
   13	$\vert\sim p$	Conj Simpl	12
   14	$\vert p \wedge \sim p$	Conj Add	10, 13
   15	$m$	CCW with contradiction & DN	11-14
   16	$p \wedge m$	Conj Add	10,15

Web Accessibility