Name (printed):Student ID #:Section # (or TA’s:name and time)CMSC 250 Exam #1 Thursday, Mar. 11, 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 exam is 100, and you will have exactly 1 hour and10 minutes to complete this exam. You may not use calculators, textbooks or any other aids during thisexam. If you need more space for any answer, ask for an extra paper - these extra papers must be turnedin and you must mark so we can find the answer corresponding to a question. The “cheatsheet” (which isthe last page of the exam) can be ripped off and used during the exam, and the back of the cheat sheetcan be used for scratch paper.1. [15 pnts.] Use a COMPLETE truth table to determine if the following argument is valid or not.Use 1 for “true” and 0 for “false” to create the complete truth table. If it is not valid, indicate allrows/columns indicate that it is not valid; if it is valid, mark all rows/columns which prove that it isvalid.P1 (A → W )∨ ∼ RP2 ∼ A∨ ∼ WP3 R → ATherefore ∼ (W ∨ R)(Yes or No) These statements do represent a valid argument.Explain why you selected this answer for validity/invalidity - indicate how specific rows/columnsindicated this answer to you.**** This area is for grading purposes (points lost per page)- Do not write below this line ****1 2 3 4 5 6 7 8 9 10 Total12. [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 ∀x ∈ D, (∼ P (x) ∧ Q(x)) → R(x)P2 ∃x ∈ D, ∼ P (x) → M(x)P3 ∀x ∈ D, ∼ R(x) ∨ Z(x)P4 ∀x ∈ D, ∼ Z(x) →∼ P (x)Therefore ∃x ∈ D, Z(x) ∨ (∼ Q(x) ∧ M (x))line Statement Reason Line #s12345678910111213141516171823. [36 pnts.]For each of the following either give a complete proof to demonstrate that the statement istrue or a counter-example with validation to show that it is false. For these problems you may useany of the formal definitions given in class or the textbook, and you may use the fact that “everyinteger is either even or odd but not both”.a. For all integers (a,b,m,n) greater than 1, if m|n and a ≡mb, then a ≡nb.3b.∀n ∈ Z, [n ∈ Zodd∧ (n ≡32)] → [12|(n2+ 3) ∨ 12|(n2− 1)]4c.∀a ∈ Zprime, ∀b ∈ Z>1, a|b3→ a|b54. [14 pnts.] Each item in the alphabetized list below completely describes a situation (if the situationsays “Jan grooms Butch. Lori gro oms Butch.” for example - this means that Jan only grooms Butchand neither of the other two dogs and Lori grooms Butch and neither of the other two dogs). Eachitem in the number list below gives a formal logic statement. You must determine which of the formallogic statements would be true in each of the (lettered) real world situations. For each situation theremay be one, more than one or none of the listed logic statements that are true in that situation. Ifthere are none - you must write the word NONE, if there is more than one, you must write all of thelogic statements that are true in that described situation.Defined are the following sets (you can assume everything in that set is listed and that these are allof the sets you have to work with):D = “dogs” = {Alphie, Butch, Carlos}P = “people” = {J an, Lori}The predicate is G(x,y) meaning person x grooms dog y. (Note it is possible for more than one personto work on the same dog, it is possible for a dog not to be groomed at all, it is possible a person canwork on more than one dog, etc. If the situation does not say that a certain person grooms a certaindog, you must assume that that person DOES NOT groom that dog.Logic Statements:(1) ∀x ∈ P, ∃y ∈ D , G(x, y)(2) ∃x ∈ P, ∀y ∈ D , G(x, y)(3) ∀y ∈ D , ∃x ∈ P, G(x, y)(4) ∃y ∈ D , ∀x ∈ P, G(x, y)Next to each of the situations (descriptions of that world’s real life configuration), write all numberswhich correspond to logic s tateme nts that are true in that situation:a. Jan grooms Alphie and Butch. Lori grooms Butch and Carlos.b. Jan does not groom any dog. Lori grooms Alphie, Butch and Carlos.c. Jan grooms Alphie. Lori grooms Butch.d. Jan grooms Alphie, Butch and Carlos. Lori grooms Alphie, Butch and Carlos.e. Jan grooms Alphie and Carlos. Lori grooms Butch.f. Jan grooms Alphie, Butch and Carlos. Lori grooms Butch.g. Jan does not groom any dog. Lori does not groom any dog.65. [10 pnts.] Given the following truth-table, do each of the following tasks. The operators and thegates they represent must only be those we have discussed in class: the “AND” gate that has exactly2 inputs and 1 output, the “OR” gate that has exactly 2 inputs and 1 output, and the “NOT” gatethat has exactly 1 input and 1 output.p q r output1 1 1 01 1 0 01 0 1 01 0 0 10 1 1 00 1 0 00 0 1 10 0 0 1a. 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).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 Rule12345678911c. Draw the circuit represented by this truth table using as few gates as possible.76. [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 hunters are animals that like meat.Some animals that like me at like to sleep.———therefore: Some hunters like to sleep.Circle One: Valid InvalidNo spiders are animals with 6 legs.All spiders spin webs.———therefore: No 6 legged animals spin webs.Circle One: Valid
View Full Document
Unlocking...