0
$\begingroup$

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 $y_\tau$ depending on the values given to $y_0, y_1, y_2$ and $y_3$.

More precisely, with $\tau (x_i)$ being the truth value assigned to $x_i$, we can define the integers $x_\tau = 2^3 \tau (x_3) + 2^2 \tau (x_2) + 2^1 \tau (x_1) + \tau (x_0)$ and $y_\tau = 2^3\tau (y_3) + 2^2 \tau (y_2) + 2^1 \tau (y_1) + \tau (y_0)$.

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?

$\endgroup$
17
  • $\begingroup$ Do you mean $x\tau=2^3\tau(x_3)+2^2\tau(x_2)+2\tau(x_1)+\tau(x_0)$? $\endgroup$ – Demosthene Jan 21 '15 at 23:55
  • $\begingroup$ Also, what are the Boolean connectives you've been introduced to so far? And from the formulation of the question, you only need to come up with one formula. $\endgroup$ – Demosthene Jan 21 '15 at 23:57
  • $\begingroup$ Yes! Let me me change the format. We have done basics of predicate logic with two variables. $\endgroup$ – java_script Jan 21 '15 at 23:57
  • $\begingroup$ Quite trivially, you could set $\tau(x_i)=1$ and $\tau(y_i)=0$, i.e. all $x$'s are true and all $y$'s are false. $\endgroup$ – Demosthene Jan 21 '15 at 23:58
  • $\begingroup$ Could I? It sets both y and x as true in the question. $\endgroup$ – java_script Jan 22 '15 at 0:00
0
$\begingroup$

I'm just re-writing my answer from the comments section.

$\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: \begin{cases} x_\tau=2^3\tau(x_3)+2^2\tau(x_2)+2^1\tau(x_1)+2^0\tau(x_0)\\ y_\tau=2^3\tau(y_3)+2^2\tau(y_2)+2^1\tau(y_1)+2^0\tau(y_0) \end{cases} Therefore, the most trivial formula that satisfies $x_\tau>y_\tau$ will assign: \begin{cases} x_\tau=2^3\times 1+2^2\times 1+2^1\times 1+2^0\times 1=8+4+2+1=15=_{bin} 1111\\ y_\tau=2^3\times 0+2^2\times 0+2^1\times 0+2^0\times 0=0+0+0+0=0=_{bin} 0000\\ \end{cases} 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\land x_1\land x_2\land x_3\land (\neg y_0)\land (\neg y_1)\land (\neg y_2)\land (\neg y_3)$$ where we have used the two Boolean connectives $\land$ (AND) and $\neg$ (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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.