CS 135 Spring 2018: Problem Set 2. Problem 1-(10 points) Let Fool(x.y.d) be a predicate that represents the statement "x makes a fool of y on day d." Thus, for example, x vd Fool(x, Lem,d) means that there is someone who fools Lem every day. Express each of the following statements as a quantified predicate. a. Every day Lem fools someone. b. There is a person who, on each day, fools someone other than himself c. Everyone fools someone someday. d. On any day a person who is fooled does not fool anyone that day e. Lem never fools himself Now, let Wise() Futured d) respectively denote the predicates "x is wise" and"on day d1, day d lies in the future" (e, day d comes after dayd1. Use these in addition to Fool(x.y.d) to express the following statements. f. A wise person never fools himself. B If Lem fools a wise person someday then he never fools that person on any future day. h. If someone fools Lem someday then Lem fooled himself someday in the past i. Anyone who is faoled by the same person on more than one day is not wise. j. Lem was fooled two different people other than himself, each on a different day, Problem 2- (10 points) In this problem we explore the use of logic in computer arithmetic. As you know, computers represent numbers using the bits (binary digits) 0 and 1. These bits represent (obviouslyl) the numbers zero and one respectively. The number two is represented as 10, three is 11, and four is 100. The four bit sequence bb2b,b represents the number 29b0 + 21b1 + 22ht 28bz-As examples, the sequence 1001 represents (23 x 1) + (2,1) 8 + 1 = 9, while the number thirteen is represented as 1101. Suppose we have to design an addition circuit to add three one-bit numbers ap,bCo. The possible values for the sum are 0, 1, 2, and 3, So the sum w be represented by a 2-bit number SiSo For example, 0+1+1-10, while 1+0+0-01. To see the connection to logic, let us correspond the bit value 1 with the logical value T (True) and 0 with F (False). So we can consider ab. Co S1,5 to be logical variables a. Construct the truth tables for st and se in terms of the inputs ag, boCp. For example, when do - T.b-T.co-F, the truth values of s-T and so - F Express So as a proposition using the variables ap.be.Co and the logical connectives b. RAV. Write a similar expression for s Express so and s1 using only the NAND connective discussed in lecture, Next, let's see how to add two 2-bit numbers 100, b1b0 to produce the 3-bit result SsSg- Recall how we usualy add numbers-we first add the lowest order bits (ap and ba) to get the value S as well as a "carry bit" which when added with a and b produces s, and a carry bit (which is sz for 2-bit numbers). Express each of ky,S1-4 in terms of a,a,, bo using the NAND connective c. d