CPS102- Homework 1Due on September 15, 2005Questions may continue on the back. Please write clearly. What I cannot read, I will not grade. Typedhomework is preferable. A good compromise is to type the words and write the math by hand.The Duke Community Standard requires every undergraduate student to sign the statement below uponcompletion of each academic assignment. I am not allowed to accept your assignment unless you sign on theline below, if you intend to return this sheet, or you copy and sign the same statement on your own paper.I have adhered to the Duke Community Standard in completing this assignment.Signature:In all answers, show your work in detail. The first two questions are warm-up problems from the book (supplementaryexercises 2 and 6 on pages 114-115).1. Find the truth table of the following compound proposition:(p ∨ q) → (p ∧ ¬r)2. Show that these statements are inconsistent: “If Sergei takes the job offer then he will get a signing bonus.” “If Sergeitakes the job offer, then he will receive a high salary.” “If Sergei gets a signing bonus, then he will not receive a high salary.”“ Sergei takes the job offer.”You may use truth tables or inference rules. Either way, start by transforming the propositions above into appropriatesymbolic form.3. In class and in the book you saw several truth tables that take two propositions as their input. The operators asso ciatedto these tables are called binary, because they take two propositions as operands. For instance,p qT T TT F FF T FF F Fis the truth table for the conjunction (“and”) of the two propositions p and q, that is, the truth table of p ∧ q, so conjunctionis a binary operator. How many distinct binary truth tables could one conceivably make up? The answer is sixteen: Truthtables for binary operators all have four rows, and the tables differ from one another by the content of the four elements inthe last column. There are sixteen possible ways to fill the last column, and here they are:p q a b c d e f g h i j k l m n o rT T T T T T T T T T F F F F F F F FT F T T T T F F F F T T T T F F F FF T T T F F T T F F T T F F T T F FF F T F T F T F T F T F T F T F T FSome of these are familiar: a is a tautology, r is a contradiction, b is p ∨ q, c is q → p, e is p → q, and so forth. Someothers we have never seen before.Table i is called the nand of p and q. Let us use a special symbol for it, p | q (called Sheffer’s stroke). Let us repeat itstruth table here:p q p | qT T FT F TF T TF F T.From this table, we can see immediately the following logical equivalence:p | q ≡ ¬(p ∧ q) ,CPS102 — Duke — September 8, 2005so we can obtain the table for “and” (column h) from that of “nand” by inverting the equivalence:p ∧ q ≡ ¬(p | q) .Write sixteen lines in the following format:x : expressionwhere x represents one of the sixteen letters in the column headings of the table above, and expression is an implementationof the corresponding truth table using nothing other than the symbols p, q, “nand” operators and parentheses. For example,i : p | q .There may be different answers for each column. Just give any one. Show your reasoning, and also give the final table neatlywritten with the columns in alphabetical order. [Hint: Column m is the truth table for ¬p, which can b e implemented asfollows:m : p | p(check with a two-row truth table that this is the case). It is best to build your answer from the easiest cases, and deriveharder answers from easier ones.]4. Express the following sentence in predicate logic:Nobody is right all the time but everybody is right some of the time.In doing so, use the predicate R(x, t) meaning “person x is right at time t.”5. If we combine supplementary problems 14 and 16 on page 115 of the textbook, we are asked to show that the implication∃ x ∀ y P (x, y) → ∀ y ∃ x P (x, y) (1)is a tautology, while the converse implication∀ y ∃ x P (x, y) → ∃ x ∀ y P (x, y) (2)is not. Rather than doing this in general, it may be instructive to show this result in the special case in which the domain (oruniverse of discourse) for x and y is finite. This allows transforming each existential quantifier to the “or” of a finite numberof propositions, and each universal quantifier to the “and” of a finite number of propositions, as shown in the text.Let us do this. For the following questions, assume that the universe of discourse for x is the set {x1, x2}, and that theuniverse of discourse for y is the set {y1, y2}.(a) Rewrite the two propositions∃ x ∀ y P (x, y) (3)∀ y ∃ x P (x, y) (4)using only “and” and “or” operators, and parentheses as needed. State which is which.(b) Transform one of the two resulting expressions so that each of them is the disjunction of several conjunctions (the “or’of several “and”s).(c) Use a simple argument to show that (1) is a tautology and (2) is not.CPS102 — Duke — September 8,
View Full Document
Unlocking...