3

During software testing I needed to find at least one solution for this:

(a or (b and c)) != ((a or b) and c)

Where all variables are boolean.

I can (and did) solve it with brute-force (if you can call so few combinations brute-force):

for a in (True, False):
    for b in (True, False):
        for c in (True, False):
            if (a or (b and c)) != ((a or b) and c):
                print a, b, c

Which yields two solutions:

True True False
True False False

I'm curious if theres a way to solve this algebraically? And if so can somebody please show the process.

Elliot Chance
  • 131

3 Answers3

1

Surely this can be solved algebraically. We have $$a \lor bc \ne (a\lor b)c$$ $$a \lor bc \ne ac \lor bc$$

If $bc=true$ they will be equal. So we get:

\begin{cases} bc=false \\ a\ne ac \\ \end{cases}

From second follows that $a \ne false$ and $c = false$. Since $c = false$, $b$ may have any value. So we get those solutions.

Ashot
  • 4,753
  • 3
  • 34
  • 61
0

I think that ashot's solution is the most economical deductive solution, and is the one I recommend. However, it is not really algebraic in any way. So, I took up the challenge of replacing some of the deductions with the actual boolean ring operations, to make as much use of the algebraic structure as possible.

To do this, first we exchange the boolean algebra operations for their boolean ring counterparts:

$ab=a\otimes b$

$a\vee b=a\oplus b\oplus ab$

THus we may treat $a,b,c$ as elements of a ring with operations $\oplus, \otimes$.

First let's solve $a\vee bc=(a\vee b)c$ noting that the solutions we seek are the complement of that set of solutions.

To save space, I won't bother to write $a\otimes b$, I'll just leave it as $ab$. Translated as above, this reads

$a\oplus bc\oplus abc=ac\oplus bc\oplus abc$

Recall that in the boolean ring, every element is its own additive inverse, so adding $abc$ to both sides:

$a\oplus bc=ac\oplus bc$

and adding $bc$ to both sides

$a=ac$

So the original equality is equivalent to this one.

To solve our problem, we must decide when $a\neq ac$.

Now we have no choice but to fall back on deductive cases, since the multiplication operation does not have inverses.

If $a$ is false, $a=ac$, so going forward we expect $a$ is true.

It follows then that $ac$ is false, and this is true exactly when $c$ is false.

Note that $b$ does not appear, so any value for it is suitable.

That's how we arrive at the two solutions: $TTF$ and $TFF$

rschwieb
  • 153,510
  • Another note: I attempted to use purely the lattice operations to do the solution, and arrived at the same equation $a=ac$, but I couldn't find an suitably simple version to post. – rschwieb Dec 02 '18 at 21:48
0

In a Boolean algebra, $X \neq Y$ if and only if $(X \wedge \neg Y) \vee (\neg X \wedge Y)$ is true. In our case,

$$ [(a \vee (b \wedge c)) \wedge ((\neg a \wedge \neg b) \vee \neg c)] \vee [\neg a \wedge (\neg b \vee \neg c) \wedge ((a \vee b) \wedge c)] $$

should be true. By applying distributivity, this expression is easily simplified to $a \wedge \neg c$.

Another approach, related to the one of @Ashot, is to apply the expansion theorem to get

$$ X(a,b,c) \neq Y(a,b,c) ~~\text{ if and only if }~~ X(\top,b,c) \neq Y(\top,b,c) ~~\text{ or }~~ X(\bot,b,c) \neq Y(\bot,b,c) \enspace. $$

In our case, $X(\bot,b,c) = Y(\bot,b,c) = b \wedge c$. Hence we assert $a$ and obtain $\top \neq c$. All in all, $a \wedge \neg c$.

Fabio Somenzi
  • 7,676