1 CPSC 121: Models of Computation Assignment #1 Due: Monday September 25, 4:00 pm Total: 42 Marks Submission Instructions-- read carefully All assignments should be done in groups of 2. It is very important to work with another student and exchange ideas. Each group should submit ONE assignment. Type or write your assignment on clean sheets of paper with question numbers prominently labelled. Answers that are difficult to read or locate may lose marks. We recommend working problems on a draft copy then writing a separate final copy to submit. Your submission must be STAPLED and include the CPSC 121 assignment cover page – located at the Assignments section of the course web page. Assignments that are not stapled will receive a penalty of 2 marks. Additionally, include your names at the top of each page. We are not responsible for lost pages from unstapled submissions. Submit your assignment to the appropriately marked box (box 31) in room ICCS X235 by the due date and time listed above. Late submissions are not accepted. Note: the number of marks allocated to a question appears in square brackets after the question number. A Note on the Marking Scheme Most items (i.e., question or, for questions divided into parts, part of a question) will be worth 3 marks with the following general marking scheme: • 3 marks: correct, complete, legible solution. • 2 marks: legible solution contains some errors or is not quite complete but shows a clear grasp of how the concepts and techniques required apply to this problem. • 1 mark: legible solution contains errors or is not complete but shows a clear grasp of the concepts and techniques required, although not their application to this problem or the solution is somewhat difficult to read but otherwise correct. • 0 marks: the solution contains substantial errors, is far from complete, does not show a clear grasp of the concepts and techniques required, or is illegible. This marking scheme reflects our intent for you to learn the key concepts and techniques underlying computation, determine where they apply, and apply them correctly to interesting problems. It also reflects a practical fact: we have insufficient time to decipher illegible answers. At the instructor’s discretion, some items may be marked on a different scale. 2 Question 1 [ 12] One way to better understand a computational system is to look at the minimum set of primitives (simple operations) that are sufficient to express all the tasks performed by the system. In this question, you will prove that every truth table can be implemented by a circuit that uses only 2-input NOR gates. To do that you need to show the following steps: [3] a. Show that ~ can be simulated using NOR gates. That is, design a circuit of NOR gates, that takes as input a signal x, and whose output is ~x. [3] b. Show that V can be simulated using NOR gates. That is, design a circuit whose only gates are NOR gates, that takes as inputs two signals x and y, and whose output is x V y. (Hint: take advantage of what you learned in the previous part!) [3] c. Show that Λ can be simulated using NOR gates. That is, design a circuit whose only gates are NOR gates, that takes as inputs two signals x and y, and whose output is x Λ y. (Hint: take advantage of what you learned in the previous parts!) [3] d. Now argue that any logic function that is represented by a truth table over k atomic propositions can be implemented with a circuit that uses only 2-input NOR gates. Question 2 [ 6 ] The truth table below defines the truth value of f for each combination of truth values of a, b and c. a b c f F F F T F F T F F T F F F T T F T F F T T F T T T T F F T T T T a. [3] Find a logic formula for f that uses each variable name at most twice. Then verify the correctness of your formula by drawing a truth table corresponding to this formula, including the truth values of all the subformulas. Note that by "subformulas" we mean the formulas representing the two inputs to the main logical operation. Hint: try to divide the rows of the truth table which contribute to the formula into two groups based on the values of two of the variables, find a logical formula for each group, and then combine them appropriately. b. [3] Draw a circuit with inputs a, b and c which directly implements the formula from 2(a). 3 Question 3 [ 9 ] Consider the following logical expressions and circuits: a) (c Ù a) ® (c Ù b) b) (a Ù (b Ú c)) ® (a Ù c) c) ~a Ú (c ® b) d) a Ú ~b e) f) Each proposition or circuit is logically equivalent to exactly one other proposition or circuit. For each of them, write down which one it is equivalent to and provide a proof for that equivalency. Each proof of the three logical equivalences must use a sequence of the logical equivalences that are listed in the “Logical Equvalence Laws”and “Implication” sections of the 121 “official” formula list shown on the first page of Dave’s excellent Formula sheet in the Other Handouts section of the course web site. You must not use truth tables for these proofs. (See also Epp-4 theorem 2.1.1, Epp-3 theorem 1.1.1, Rosen-6 table 6 in section 1.2, Rosen-7 table 6 in section 1.3; you can also assume that x ® y º ~x Ú y). You may also use the abbreviations for the rule names which are shown on this handout. 4 Question 4 [ 6 ] Design a circuit that takes three inputs a, b, and c and returns the value that the majority of inputs have (this is called a majority vote). For example, if a and b are true, and c is false, the circuit must output true, because 2/3 inputs (the majority of inputs) are true. a. [3] Show the formula for this problem and explain how did you find it. Any formula that satisfies the problem specification is acceptable here b. [3] Show the circuit. Question 5 [ 9 ] An Island of Riddles There is an island on which everyone is a dragon or a troll. Dragons, being noble, always tell the truth. Trolls, being tricky, always lie. Alice, Bob, and Carol, all inhabitants of the island, make the following statements: Alice: “Bob is a dragon " Bob: “Alice is a dragon" Carol: “Alice is a troll" a. [3] Is it possible that Alice is a dragon? Is it possible that Alice is a troll? Justify each answer in no more than three sentences. Hint: a full and complete justification will include more than just a truth table, and will almost certainly include the word, “because" (with reference to what Alice, Bob, and Carol said). b. [3] Is it possible that Carol is a dragon? Is it possible that Carol is a troll? Justify each answer in no more than three sentences. c. [3] There are eight possible assignments of dragon or troll to Alice, Bob, and Carol. An assignment is a label of dragon or troll to each of Alice, Bob, and Carol, regardless of whether it is correct or incorrect. For example, “Alice is a dragon, Bob is a dragon, and Carol is a troll" is one of the eight possible assignments, regardless of whether that assignment is correct or not. Are all of the eight possible assignments potentially correct, based on what Alice, Bob, and Carol said? Justify your answer. Your answer will be judged on the brevity and preciseness of justifying why either “yes" or “no" is correct.

Attachments:

• 1507810724-assign1.pdf