Name (printed):Student ID #:Section # (or TA’s:name and time)CMSC 250 Exam #1 Thursday, Oct. 16, 2003Read this page and all directions carefully.Write 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 exam is 150, and you will have exactly 1.75 hoursto complete this exam. You may not use calculators, textbooks or any other aids during this exam. If youneed more space for any answe r, ask for an extra paper - these extra papers must be turned in, and youmust mark so we can find the answer corresponding to a question. The “cheatsheet” (which is the lastpage of the exam) can be ripped off and used during the exam; the back of the cheat sheet can be usedfor scratch paper. You do not need to turn in the cheat sheet paper at the end of the exam period. Eve nif you do, anything written on the cheatsheet (or its back) will not be graded.Please, copy the university honor pledge written below and sign your name on the line labeled ”Signa-ture”.I pledge on my honor that I have not given nor received unauthorized assistance on this examination.Signature:**** This area is for grading purposes (points lost per page)- Do not write below this line ****2 3 4 5 6 7 8 9 10 11 12 Total11. [15 pnts.] Use a complete truth table to determine if the following two statements are logicallyequivalent. Use 1 for “true” and 0 for “false” to create the complete truth table.• (p ∧ q) ∨ [∼ (r ∧ p) ∧ (q∧ ∼ r)]• q ∧ (p ∨ r)(Yes or No) These statements are logically equivalent.Why did you answer this way?? Indicate row and/or column which implied the answer above.22. [6 pnts.] Convert the following to 8-bit two’s complement representation.a. 2410=__ __ __ __ __ __ __ __b. −610=__ __ __ __ __ __ __ __c. −1410=__ __ __ __ __ __ __ __3. [6 pnts.] Convert the following from/to the bases indicated.a. 2510=2b. 1A216=2c. BA16=1034. [20 pnts.] For each of the following English sentences, translate the meaning into formal notationusing the logic symbols (∃, ∀, ∧, ∨, ∼, and →). In addition to these, you may also use mathematical,grouping and set notations symbols as needed. On the next line write the negation of the originalstatement using formal notation. Note: On the negation, no quantifier nor quantitified expression(parentheses) may be negated in the final answer.There are no more than two tall people in my class.Domains: P = {all people}Predicates: T(x) = “x is tall”, C(x) = “x is in my class”statement:negation:No person can survive in space without being dressed in a space suit.Domains: P = {all people}Predicates: D(x)= “is dressed in a space suit”, S(x) = “x can survive in space”statement:negation:At least 1 young person must go to the meeting.Domains: U = {universe of all things}Predicates: P(x) = “x is a person”,M(x)= “x goes to the meeting”, Y(x) = “ x is young”statement:negation:Exactly two people like me.Domains: P= {all people}Predicates: L(x) = “x likes m e”statement:negation:45. [10 pnts.] Use an Euler diagram to determine if each of the following represents a valid argumentform. Make sure to label the parts of the diagram. If it is invalid, you must draw a diagram thatis not supportive of the conclusion. If it is a valid argument, draw a diagram that does support theconclusion (since you can’t draw one that doesn’t).All pieces of luggage have handles.All of my suitcases have handles.———therefore: All of my s uitcases are pieces of luggage.Circle One: Valid InvalidAll dogs are cute.My pet is cute.———therefore: My pet is a dog.Circle One: Valid Invalid56. [20 pnts.] Use only the rules provided on the “cheatsheet” to prove the following. It is a ValidArgument - you only need to prove that it is. You may also assume the Domain is not empty (it hasat least three members - that member is named a,b,d).P1 ∀x ∈ D, (P (x) ∨ Q(x)) → (R(x) ∨ S(x))P2 P (a) ∨ R(a)P3 ∃y ∈ D, Q(y) → (S(y) ∨ M(y))P4 ∀z ∈ D, ∼ M(z)∨ ∼ R (z)− − − − − − − − − − − − −−therefore ∃w ∈ D, ∼ (Q(w)∧ ∼ S(w))line Statement Reason Line #s123456789101112131415161718192067. [43 pnts.] For each of the following, either give a counter example with justification to prove thatthe statement is false or give a complete proof to show that it is true.a. For any two perfect squares their product is also a perfect square. In other words: that the setof “perfect squares” is closed under multiplication.Hint: Remember the definition of perfect square is :∀a ∈ Z , a ∈ Zperfect square↔ ∃m ∈ Z, m2= a7b. For all positive integers n, 3 does not divide n2− 28c. For all rational numbers x and y,xyis rational.9d. The cube root of 5 is irrational.If you prove this to be true, you may use any of the following lemmas in the proof withoutneeding to prove them if you would like.Lemma #1: ∀a, b ∈ Z+, ∃m, n ∈ Z+ such that m and n have no common factors andab=mnLemma #2: ∀a ∈ Z, ∀p ∈ Zprime, p|a2→ p|aLemma #3: ∀a ∈ Z, ∀p ∈ Zprime, p|a3→ p|a108. [15 pnts.] Given the following logical statement, convert it so that it can be built using only OR andNOT gates. (No AND or other gates may be used.) The OR gates can only have two inputs and theNOT gates can only have one input.[(∼ P ∧ ∼ Q)∧ ∼ (R∨ ∼ P )] ∨ (∼ P ∧ Q)a. Give the logical statement as it would be expressed using only OR and NOT operators (givingthe proof that they are equivalent in the table below):b. Show the proof of this translation here to prove that your statement is equivalent to the original.line Statement Reason Line #s123456789101112c. Draw the Circuit as it is expressed in the statement you just gave:119. [15 pnts.] Use only those rules given on the “cheatsheet” to prove that the following is a validargument. It is a Valid Argument - you only need to prove that it is.P1 (∼ P ∨ ∼ Q) ∨ (R → S)P2 P → (Q → R)P3 ∼ (P ∧ S) ∧ (Q → P )P4 M ∨ NTherefore Q → Mline Statement Reason Line
View Full Document
Unlocking...