# Consider truth assignments involving only the propositional variables x_0,x_1,x_2,x_3 and y_0,y_1,y_2,y_3. 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 x_0,x_1,x_2 and x_3, and a four-bit integer y_τ depending on the values given to y_0,y_1,y_2 and y_3.

Consider truth assignments involving only the propositional variables ${x}_{0},{x}_{1},{x}_{2},{x}_{3}$ and ${y}_{0},{y}_{1},{y}_{2},{y}_{3}$.
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 $\tau$ as determining a four-bit integer ${x}_{\tau }$ depending on the values given to ${x}_{0},{x}_{1},{x}_{2}$ and ${x}_{3}$, and a four-bit integer ${x}_{\tau }$ depending on the values given to ${y}_{0},{y}_{1},{y}_{2}$ and ${y}_{3}$.
More precisely, with $\tau \left({x}_{i}\right)$ being the truth value assigned to ${x}_{i}$, we can define the integers ${x}_{\tau }={2}^{3}\tau \left({x}_{3}\right)+{2}^{2}\tau \left({x}_{2}\right)+{2}^{1}\tau \left({x}_{1}\right)+\tau \left({x}_{0}\right)$ and ${y}_{\tau }={2}^{3}\tau \left({y}_{3}\right)+{2}^{2}\tau \left({y}_{2}\right)+{2}^{1}\tau \left({y}_{1}\right)+\tau \left({y}_{0}\right)$
Write a formula that is satisfied by exactly those truth assignments $\tau$ for which ${x}_{\tau }>{y}_{\tau }$. Your formula may use any of the Boolean connectives introduced so far. Explain how you obtained your formula, and justify its correctness
Am I right in assuming that I would need to construct a formula for every single possibility where x is the greater bit?
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Brienueentismvh
Step 1
$\tau$ is a function that assigns the binary value 0 or 1 to a propositional variable, depending on whether that variable has the truth assignment FALSE or TRUE (respectively).
We then compute the 4-bit integers ${x}_{\tau }$ and ${y}_{\tau }$ as follows:
$\left\{\begin{array}{l}{x}_{\tau }={2}^{3}\tau \left({x}_{3}\right)+{2}^{2}\tau \left({x}_{2}\right)+{2}^{1}\tau \left({x}_{1}\right)+{2}^{0}\tau \left({x}_{0}\right)\\ {y}_{\tau }={2}^{3}\tau \left({y}_{3}\right)+{2}^{2}\tau \left({y}_{2}\right)+{2}^{1}\tau \left({y}_{1}\right)+{2}^{0}\tau \left({y}_{0}\right)\end{array}$
Therefore, the most trivial formula that satisfies ${x}_{\tau }>{y}_{\tau }$ will assign:
$\left\{\begin{array}{l}{x}_{\tau }={2}^{3}×1+{2}^{2}×1+{2}^{1}×1+{2}^{0}×1=8+4+2+1=15{=}_{bin}1111\\ {y}_{\tau }={2}^{3}×0+{2}^{2}×0+{2}^{1}×0+{2}^{0}×0=0+0+0+0=0{=}_{bin}0000\end{array}$
In other words, we're looking for a logical formula that is true whenever the ${x}_{i}$ are true and the ${y}_{i}$ are false. Such a formula is given by:
${x}_{0}\wedge {x}_{1}\wedge {x}_{2}\wedge {x}_{3}\wedge \left(\mathrm{¬}{y}_{0}\right)\wedge \left(\mathrm{¬}{y}_{1}\right)\wedge \left(\mathrm{¬}{y}_{2}\right)\wedge \left(\mathrm{¬}{y}_{3}\right)$
where we have used the two Boolean connectives ∧ (AND) and ¬ (NOT). The AND connective yields TRUE if and only if both its arguments are TRUE. The NOT connective flips the truth-value of its argument, i.e. NOT TRUE=FALSE and NOT FALSE=TRUE.
Therefore, it can easily be seen that the formula above, where each element is connected by AND connectives, is true only when each element is TRUE. And in particular, the elements formed by NOT ${y}_{i}$ are true only when the ${y}_{i}$ are FALSE.