Equivalent Boolean Expressions

Two Boolean expressions can be written differently and still give the same value every time. In a home security system, armed says whether the alarm is set and doorOpen says whether the front door is open.

The system raises an alert when armed && doorOpen is true. Someone proposes !armed && !doorOpen as the condition for no alert. Two boolean variables have four combinations of values, and the table lists them all.

armed   doorOpen   !(armed && doorOpen)   !armed && !doorOpen
  T        T              F                      F
  T        F              T                      F
  F        T              T                      F
  F        F              T                      T

Here T stands for true and F for false.

The last two columns disagree in the second and third rows. In the second row the alarm is armed with the door shut: there's no alert, but the proposed condition is false. One row that disagrees is enough to show the two expressions aren't equivalent. A check of rows one and four alone would have missed it, since the columns agree there.

The expression !(armed && doorOpen) says the two aren't both true. That happens when at least one of them is false, which is !armed || !doorOpen. A column for that expression in the table above would read F, T, T, T from the top, the same as the third column.

The same reasoning applies to ||. The expression !(armed || doorOpen) says neither is true, which is !armed && !doorOpen. The proposal in the table was this second form, so it matched the wrong expression.

A negated comparison can be rewritten without the !. The system also logs a warning when the door has been open for more than 30 seconds, and !(seconds > 30) is equivalent to seconds <= 30. The direction of the comparison reverses, and the equal case changes sides. At exactly 30, seconds > 30 is false, so its negation must be true there, and seconds < 30 would be wrong.

The pairs are == and !=, < and >=, and > and <=.

De Morgan's law and these pairs work together. Applied to !(armed && seconds > 30), De Morgan gives !armed || !(seconds > 30), and the second operand becomes seconds <= 30.

A ! applied twice returns the original value, so !!armed is armed. A rewrite can produce two negations in a row. Take !(armed || !doorOpen). De Morgan's law gives !armed && !!doorOpen, and the double negation cancels, leaving !armed && doorOpen: the alarm is off and the door is open.