New version page

# UMD CMSC 250 - Quiz #4 Answers

Pages: 2
Documents in this Course

2 pages

2 pages

2 pages

2 pages

57 pages

12 pages

2 pages

3 pages

8 pages

4 pages

2 pages

28 pages

2 pages

6 pages

2 pages

2 pages

2 pages

4 pages

2 pages

2 pages

57 pages

2 pages

16 pages

10 pages

2 pages

32 pages

5 pages

28 pages

4 pages

2 pages

8 pages

2 pages

8 pages

2 pages

12 pages

16 pages

2 pages

12 pages

13 pages

2 pages

12 pages

2 pages

2 pages

2 pages

2 pages

2 pages

8 pages

3 pages

44 pages

4 pages

2 pages

4 pages

4 pages

2 pages

2 pages

5 pages

2 pages

40 pages

14 pages

## This preview shows page 1 out of 2 pages.

View Full Document

End of preview. Want to read all 2 pages?

View Full Document
Unformatted text preview:

Name (printed):Student ID #:Section # (or TA’s:name and time)CMSC 250 Quiz #4 ANSWERS Wednesday, Feb. 18, 2004Write all answers legibly in the space provided. The number of points possible for each question is indicatedin square brackets – the total number of points on the quiz is 30, and you will have exactly 15 minutes tocomplete 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 notationusing the symbols (∃, ∀, ∧, ∨, ∼, and →). You may also use the following relational operators: =and 6= as well as the algebraic operators: +, −, ∗ (multiplication) and / (division). On the nextline write the negation of the original statement using formal notation. A negation symbol may onlyappear 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 ystatement:∃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 evenstatement:∀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 wingsstatement:∀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 herestatement:∃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 q r output1 1 1 11 1 0 01 0 1 01 0 0 00 1 1 10 1 0 10 0 1 00 0 0 0a. 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 oflogical operators. (This reduction is in the standard form of a proof.)Equivalent Statement Rule1 (q ∧ (p ∧ r)) ∨ (q ∧ (∼ p ∧ r)) ∨ (q ∧ (∼ p∧ ∼ r)) Assoc andComm2 q ∧ ((p ∧ r) ∨ ((∼ p ∧ r) ∨ (∼ p∧ ∼ r))) Distrib and As-soc3 q ∧ ((p ∧ r) ∨ (∼ p ∧ (r∨ ∼ r))) Distrib4 q ∧ ((p ∧ r) ∨ (∼ p ∧ t)) Negation5 q ∧ ((p ∧ r)∨ ∼ p identity6 q ∧ ((p∨ ∼ p) ∧ (r∨ ∼ p)) distribution7 q ∧ (t ∧ (r∨ ∼ p)) Negation8 q ∧ (r∨ ∼ p) identityc. 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∨ ∼

View Full Document
Unlocking...