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, 3x 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(x), Future(d d2) respectively denote the predicates "x is wise" and on day di, day dz lies in the future" (.e., day d2 comes after day di). Use these in addition to Fool(x, y,d) to express the following statements f. A wise person never fools himself. g. 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 fooled 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 (obviously!) the numbers zero and one respectively. The number two is represented as 10, three is 11, and four is 100. The four bit sequence b b2b,bo represents the number 2%, + 2%, (23 x 1) + (2 x 1) = 8 + 1 = 9, while the number thirteen is represented as 1101. +22b2 +2'by. As examples, the sequence 1001 represents Suppose we have to design an addition circuit to add three one-bit numbers a, b,Co. The possible values for the sum are 0, 1, 2, and 3. So the sum will be represented by a 2-bit number S1Sg. 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 a, bo,Co.S,So to be logical variables. a. Construct the truth tables for s and so in terms of the inputs ao, bo,co. For example, when ao T,bo-T,co F, the truth values of s Tand s F b. Express So as a proposition using the variables a, b, Co and the logical connectives AV. Write a similar expression for s1 c. Express so and s using only the NAND connective discussed in lecture. d. Next, let's see how to add two 2-bit numbers a, a b, bo to produce the 3-bit result S2S1S0. Recall how we usually add numbers- we first add the lowest order bits (ao and bo) to get the value so as well as a "carry bit" which when added with az and b produces s, and a carry bit (which is s2 for 2-bit numbers). Express each of s2,S, So in terms of a, ao, bl. bo using the NAND connective 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, 3x 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(x), Future(d d2) respectively denote the predicates "x is wise" and on day di, day dz lies in the future" (.e., day d2 comes after day di). Use these in addition to Fool(x, y,d) to express the following statements f. A wise person never fools himself. g. 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 fooled 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 (obviously!) the numbers zero and one respectively. The number two is represented as 10, three is 11, and four is 100. The four bit sequence b b2b,bo represents the number 2%, + 2%, (23 x 1) + (2 x 1) = 8 + 1 = 9, while the number thirteen is represented as 1101. +22b2 +2'by. As examples, the sequence 1001 represents Suppose we have to design an addition circuit to add three one-bit numbers a, b,Co. The possible values for the sum are 0, 1, 2, and 3. So the sum will be represented by a 2-bit number S1Sg. 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 a, bo,Co.S,So to be logical variables. a. Construct the truth tables for s and so in terms of the inputs ao, bo,co. For example, when ao T,bo-T,co F, the truth values of s Tand s F b. Express So as a proposition using the variables a, b, Co and the logical connectives AV. Write a similar expression for s1 c. Express so and s using only the NAND connective discussed in lecture. d. Next, let's see how to add two 2-bit numbers a, a b, bo to produce the 3-bit result S2S1S0. Recall how we usually add numbers- we first add the lowest order bits (ao and bo) to get the value so as well as a "carry bit" which when added with az and b produces s, and a carry bit (which is s2 for 2-bit numbers). Express each of s2,S, So in terms of a, ao, bl. bo using the NAND connective