Consider truth assignments involving only the propositional variables x0, x1, x2, x3 and y0, y1, y2, y3. Every such truth assignment gives a value of 1 (representing true) or 0 (representing false) to each variable. We can, therefore, think of a truth assignment as determining a four-bit integer x depending on the values given to x0, x1, x2 and x3, and a four-bit integer y depending on the values given to y0, y1, y2 and y3. More precisely, with (xi) being the truth value assigned to xi , we can define the integers x = 23 (x3) + 22 (x2) + 21 (x1) + (x0) and y = 23 (y3) + 22 (y2) + 21 (y1) + (y0). Write a formula that is satisfied by exactly those truth assignments for which x > y . Your formula may use any of the Boolean connectives introduced so far. Explain how you obtained your formula, and justify its correctness.

Note: This can be done by writing down a truth table for eight propositional variables i.e., a truth table with 28 = 256 rows. It can be done more easily (and interestingly) by identifying the precise condition under which the four-bit number x3x2x1x0 is greater than the four-bit number y3y2y1y0. (Hint: If the high-order bits, x3 and y3, are not equal, which of the two numbers is greater? If the two high-order bits are equal, how do we proceed to determine which of the two numbers is greater?)