Fun With Boolean Statements

A single Boolean expression can often be specified in multiple ways. For example, the expression A AND B is equivalent to the expression NOT (NOT A OR NOT B). One way to test the equivalence of two Boolean expressions is to create a table of every possible combination of the input variables along with the resulting value of the expression. In the example above:

A | B | A AND B

-----------------

F | F | F

T | F | F

F | T | F

T | T | T

And

A | B | NOT ((NOT A) OR (NOT B))

----------------------------------

F | F | F

T | F | F

F | T | F

T | T | T

Of course, a Boolean expression with N different input variables has 2^N different input combinations. Thus these tables can grow quickly, and it is often preferable to simplify the expressions mathematically.

The children of Bool enjoyed playing a particularly creative (and admittedly annoying) game. They would ask travelers simple questions that were phrased as complex Boolean expressions. They would then watch the traveler struggle to figure out how to answer the question. Usually, some amount of laughter would follow. It was like Bool's own form of logic-based prank calling.

The rules of the game were quite simple:

1) Start with a Boolean expression that asked a reasonable question.*

2) Make that expression as long as possible without changing the meaning.

Of the two rules, the second one was the easiest to follow. Newcomers to the game would dutifully draw out the logic tables for both expressions in order to demonstrate their equivalence. Experience players would produce simple, yet beautiful, proofs using simplification rules.

The first graders in Bool tended to stick with questions using double, triple, and quadruple negatives:

"Are you NOT NOT NOT NOT staying at the inn?" = "Are you staying at the inn?"

Unfortunately, the first graders still almost always managed to confuse themselves. They often had to resort to standing in the middle of the street, counting the number of negatives on their fingers, before deciding whether or not they could laugh at the traveler's answer.

By the time the kids reached second grade, they were using more complex rules, such as:

A AND TRUE = A

B AND FALSE = FALSE

C OR TRUE = TRUE

D OR FALSE = D

This would lead to all sorts of new fun, such as: "(Are you NOT stupid) OR (is the sun hot)?" which was TRUE regardless of the intelligence of the person. However, after being asked that question by a second grader, most travelers tended to feel stupid.

Of all the kids in Bool, Chuck was the best at this game. In fact, he was something of a legend at his elementary school. He had once caused a merchant to sputter in confusion by asking: "Is it really false that you: do not carry chocolate or do not carry gum?" By the time that the merchant figured out that Chuck was asking if he carried both chocolate and gum, Chuck and his friends were already laughing hysterically in the road.

Chuck's personal favorite was De Morgan's law, which stated:

NOT (A AND B) = (NOT A) OR (NOT B)

NOT (A OR B) = (NOT A) AND (NOT B)

In fact, DeMorgan's law led to Chuck's first classic: "Are you NOT (smart OR funny)?" which meant "(Are you NOT smart?) AND (Are you NOT funny?)" Even when someone answered the question correctly, Chuck found their expression hilarious.

Chuck's ultimate masterpiece was a thirty-eight clause phrase that asked about the traveler's path to Bool. It included no less than three different applications of De Morgan's law.

Thus it was much to Chuck's dismay when Ann passed through the town of Bool. Chuck sprung the question on her as she was finally leaving the town. He held is breath as he finished, waiting for the confused look that would ultimately prove him the master of complexifying Boolean expressions. Instead, Ann looked back at him and answered simply: "Yes. That is TRUE."

She waited for a moment to see why he had asked her an odd question. Then, after realizing that there was no followup question, Ann turned and continued her journey.

Chuck was devastated. He immediately went home and started work on a new, 50-clause, expression.

* "Reasonable" was much debated term and often led to hour long arguments. This matter was usually decided by a vote of the kids standing nearby or, in the case of ties, by a game of rocks-paper-scissors.

--------------------

For more Boolean fun, read about Ann's visit to the town of Bool.