Boolean conditions

Boolean conditions #

A complex boolean sub-expression in the scope of a negation can be difficult to read and/or debug.

Example. The two following expressions are equivalent (but the latter is arguably easier to read):

$$ \neg(\neg(a \lor b) \land \neg (\neg c \lor d)) $$

$$ a \lor b \lor \neg c \lor d $$

Simplification #

In a Boolean expression, negations can always be “pushed” inside parentheses, as follows:

  • base case:

    • $\neg (x = y)$ becomes $x \neq y$
    • $\neg (x \le y)$ becomes $x > y$
    • $\neg (x > y)$ becomes $x \le y$
    • etc.
  • inductive case:

    • $\neg (\phi \land \psi)$ becomes $\neg \phi \lor \neg \psi$
    • $\neg (\phi \lor \psi)$ becomes $\neg \phi \land \neg \psi$

Simplify the following Java condition:

!(x != y && ( !x.hasNext() || !y.hasNext() || x.next() != y.next()))

The expression is of the form

!(x != y && <expression 1>)

So we can transform it into

x == y || ! <expression 1>

Next observe that

! <expression 1>

is

!( !x.hasNext() || !y.hasNext() || x.next() != y.next())

which can be transformed into

x.hasNext() && y.hasNext() && x.next() == y.next()

So the whole expression becomes

x == y || ( x.hasNext() && y.hasNext() && x.next() == y.next() )