New version page

UMD CMSC 250 - Quiz #4 Answers

This preview shows page 1 out of 2 pages.

View Full Document
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
Loading Unlocking...
Login

Join to view Quiz #4 Answers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Quiz #4 Answers and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?