Reducing a boolean expression with nested ternary expression

90 Views Asked by At

Consider the following boolean expression with a nested ternary expression:

$$(\text{if $a < 0$ then $-a$ else $a$}) < 3$$

I can "see" that it can be reduced to:

$$a > -3 \land a < 3$$

However, I can't figure out the algebraic rules I need to apply in order to arrive at the reduced expression.

I got as far as:

$$(\text{if $a < 0$ then $-a$ else $a$}) < 3$$ $$\text{if $a < 0$ then $-a < 3$ else $a < 3$}$$ $$\text{if $a < 0$ then $a > -3$ else $a < 3$}$$ $$(a < 0 \land a > -3) \lor (\lnot(a < 0) \land a < 3)$$ $$(a < 0 \land a > -3) \lor (a \ge 0 \land a < 3)$$

But that's where I'm stuck. I think somewhere in between I should arrive at:

$$(a < 0 \lor a \ge 0) \lor (a > -3 \land a < 3)$$

Or maybe:

$$(a < 0 \lor a \ge 0) \land (a > -3 \land a < 3)$$

Because then the term $(a < 0 \lor a \ge 0)$ would cancel out. So I tried my way backwards from there, but I still no luck.

I feel like I'm missing something quite simple.

2

There are 2 best solutions below

2
On BEST ANSWER

You are almost there:

From:

$$(a < 0 \land a > -3) \lor (a \ge 0 \land a < 3)$$

Distribute (FOIL, basically):

$$(a < 0 \lor a \ge 0) \land (a < 0 \lor a < 3) \land (a > -3 \lor a < 3) \land (a > -3 \lor a \ge 0)$$

Now, as you say, $(a < 0 \lor a \ge 0)$ is a mathetical truth, and so can be ignored:

$$ (a < 0 \lor a < 3) \land (a > -3 \lor a < 3) \land (a > -3 \lor a \ge 0)$$

Also, since $a < 0$ implies $a<3$, the term $(a < 0 \lor a < 3)$ reduces to the weakest claim, i.e. to $a < 3$. Likewise, $(a > -3 \lor a \ge 0)$ reduces to $a > -3$:

$$ a < 3 \land (a > -3 \lor a < 3) \land a > -3 $$

Finally, if $a < 3$ and $a > -3$, then certainly $(a > -3 \lor a < 3)$, so that middle term can be completely removed, leaving you with:

$$ a < 3 \land a > -3 $$

Now, note that this transformation was not a purely logical transformation, but that is because the equivalence between your original statement and the statement $ a < 3 \land a > -3 $ is indeed 'merely' a mathematical equivalence, and not a logical one. For, example, $(a < 0 \lor a \ge 0)$ is a mathematical truth, and not a logical one.

2
On

\begin{equation} (a < 0 \land a > -3) \lor (a \ge 0 \land a < 3) \\ (a < 0 \lor a \ge 0) \land (a < 0 \lor a < 3) \land (a > -3 \lor a \ge 0) \land (a > -3 \lor a < 3) \\ 1 \land (a < 3) \land (a > -3) \land 1 \\ (a < 3) \land (a > -3) \end{equation}