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

*View Full Document*

End of preview. Want to read all 2 pages?

Upload your study docs or become a GradeBuddy member to access this document.

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