Name printed Student ID Section or TA s name and time CMSC 250 Quiz 4 ANSWERS Wednesday Feb 18 2004 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 16 pnts For each of the following English Sentences translate the meaning into formal notation using the symbols and You may also use the following relational operators and 6 as well as the algebraic operators multiplication and division On the next line write the negation of the original statement using formal notation A negation symbol may only appear immediately before an individual predicate There is a tree taller than any building Domains B all buildings and D all trees Predicate T x y x is taller than y statement t D b B T t b negation t D b B T t b The square of any even integer is an even integer Domain Z all integers Predicates E x x is even statement x Z E x E x x negation x Z E x E x x No pigs have wings Domain P all pigs Predicate W x x has wings statement x P W x negation x P W x There are at least two people here Domain P all people Predicate H x x is here statement a b P H a H b a 6 b negation a b P H a H b a b TURN OVER 2 14 pnts Given the following truth table do each of the following tasks p 1 1 1 1 0 0 0 0 q 1 1 0 0 1 1 0 0 r 1 0 1 0 1 0 1 0 output 1 0 0 0 1 1 0 0 a Give the three situations values for p q and r that will give a 1 as the output in a single long logic statement of the form situation1 situation2 situation3 ANSWER p q r p q r p q r b Show the reduction of that line to an equivalent statement that has the minimum number of logical operators This reduction is in the standard form of a proof Equivalent Statement Rule 1 q p r q p r q p r Assoc and Comm 2 q p r p r p r Distrib and Assoc 3 q p r p r r Distrib 4 q p r p t Negation 5 q p r p identity 6 q p p r p distribution 7 q t r p Negation 8 q r p identity c Draw the circuit represented by this truth table using as few gates as possible d Give the equivalent logic statement without using any and gates ANSWER q r p
View Full Document
Unlocking...