Goldilocks and the Two Boolean Bears

Boolean logic is based on two values: TRUE and FALSE. Boolean values are used within programs to perform logic such as: determining if an IF statement executes or controlling when a loop terminates.

Once upon a time, a girl named Goldilocks came across a small cottage. She had been wandering around the woods all day and was eager to rest. She furtively peeped into the windows and listened at the door. There was no sign of life. Convinced that the cottage was empty, Goldilocks climbed in through an open window.

The smell of fresh porridge wafted through house. Goldilocks followed her nose as if in a trance. Presently, she came to the kitchen and saw two large bowls of porridge sitting on a low wooden table.

"Nobody will mind if I have just a little," thought Goldilocks. Her stomach grumbled in agreement. The smell of freshly ground cinnamon pushed away the last of her doubts.

Goldilocks skipped over to the table and tried the first bowl of porridge. It was ice cold. "This porridge is completely cold," she thought to herself. "It is not hot at all."

She tried the next bowl of porridge.

"Argh!" she screamed. The molten porridge seared the inside of her mouth. She spit the porridge across the room, eager to distance herself from the fiery pain. She then dove for the bowl of cold porridge, filled her mouth with the icy sludge, and waited for the pain to subside.

"Who makes porridge that hot?" she moaned to no one in particular.

Traumatized, she looked for someplace to rest. In the living room, she found a single small chair.

"Only one chair?" Goldilocks wondered aloud. Then, noticing the well worn patch of carpet adjacent to the chair, she concluded: "I guess one person sits and the other does not sit. That seems awkward."

Goldilocks climbed into the chair, which promptly collapsed onto the floor. After quick examination of the wreckage, Goldilocks mumbled to herself in confusion "Who makes a chair out of balsa wood? No wonder the other person did not sit down. You would have to be tiny for that chair to support you."

Continuing her search for a place to rest, Goldilocks ventured upstairs. The large bedroom held two beds. The first bed looked incredibly soft. Cotton balls filled the four foot thick mattress. In stark contrast, the second bed consisted of a flat plank of iron supported by four cinder blocks.

"What is going on?" asked Goldilocks. "One bed is clearly comfortable. The other is not. Who makes a bed out of an iron plank?"

Golidlocks debated crawling into comfortable bed when the truth dawned on her. Everything in this house was Boolean. The porridge was hot or NOT hot. One person sat in a chair and the other did NOT sit. One bed was comfortable and the other was NOT comfortable. Whoever lived in this house did not believe in a middle ground. That did not bode well for visitors.

Goldilocks dove out an open window. She sprinted down the path and away from the house before the owners returned. She had no interest in learning whether they were welcoming or not.

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

For more about Boolean logic, see Ann's visit to the city of Bool.

For another take on familiar tale, see Binary Searching for Cinderella.

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.

The Valley of NAND and NOR: Part 3 of Ann's encounter with the Booleans

NAND and NOR are Boolean logic operations. They are negations of AND and OR respectively. NAND (Not AND) evaluates to true if and only if at least one of the inputs is false. NOR (Not OR) evaluates to true if and only if both inputs are false.

After leaving the wizard's resort and completing her trek through the Lagrange mountains, Ann came to the Valley of NAND and NOR. She had heard rumors that it was a most disagreeable place, filled with negative people. The valley itself certainly seemed to uphold this reputation. It could only generously be described as a desert oasis. A more accurate description would be two small villages on either side of a large muddy puddle.

Ann considered passing by the villages without stopping. Her experience at the wizard's resort had left her feeling bitter. But, her horse needed water and Ann herself was tired. She decided to try the village of NAND first.

"Hi." Ann began cheerfully as she walked up to the counter at the village's only inn. "I would like a room for the night and some dinner, please." Ann smiled broadly, hoping to set a cheerful tone.

"No." responded the inn keeper. "One or the other." She pointed behind her to a sign on the wall that read: 'NAND INN - Providing a room, or dinner, or neither.'

"But, that does not make any sense." objected Ann.

The inn keeper shrugged. "That is how we do things in NAND. If you do not like it, you can always try NOR. They are really nice over there." She laughed as she spoke.

"So, I can NOT have a dinner AND a room?" Ann confirmed.

"No!" The inn keeper was most rude.

Frustrated, Ann left the inn and started her journey to NOR on the other side of the mud puddle. She had heard that the villagers in this valley were descendants of the Booleans, but she had hoped that they did not adhere quite as strictly to the Boolean's beliefs. If anything though, the people of NAND seemed worse!

It took an hour before Ann arrive at NOR's inn.

"I would like a room for the night and some dinner, please." Ann asked the inn keeper. This time Ann was too tired to pretend to be overly cheerful.

"No." he responded. Without any additional explanation, he pointed to a sign on the wall that read: NOR INN - Providing no rooms or food.

"Wait." Ann objected. "You are telling me that this inn does NOT provide rooms OR dinner? What sort of an inn is that? What do you provide?"

The inn keeper shrugged. "If you don't like it, you can always try the village of NAND."

Ann stormed out with responding, and left town. NAND and NOR were just as negative as everyone had warned. As she looked back at the two villages disappearing into the distance, she hoped that the next place she went would not be filled with Booleans.

The Gates of XOR: Part 2 of Ann's encounter with the Booleans

XOR is a binary operation that evaluates to true if exactly one of its inputs is true. Formally, A XOR B = (A AND NOT B) OR (NOT A AND B). XOR is used as an operation in a variety of computer programming languages as well as low-level machine operations.

As she left the town of Bool, Ann realized that she would have to face the gates of Xor. The gates of Xor stood in front of a small pass through the Lagrange mountains. While it was possible to simply walk around the Lagrange mountains, it would add another 500 miles to Ann's journey. The mountain pass was the obvious choice, but the gates were known to be highly dangerous. Either you were allowed to pass through the gates, or you were dropped into a pit of spikes. As with everything in the town of Bool, there were only two completely opposite outcomes.

The gates of Xor were a classic example of the complete adherence to binary logic that the Booleans had long embraced. Boolean wizards had built the gates such that they would only allow the people whom they judged worthy to pass. Specifically, the gates were rumored to evaluate two characteristics: Intelligence and strength. Both characteristics were evaluated in a completely binary way; you were either weak or strong. However, no one understood how the gates actually used these criteria to judge the travelers. The wizards that had built the gates had never explained their reasoning, and they had disappeared shortly after construction was completed.

Ann walked up to the gates and tentatively placed her hand on the evaluation panel. She was nervous. She understood the danger all too well. But, her quest came first; and she needed to take this short cut.

With a loud click the gates unlocked and opened. Breathing a sigh of relief, Ann walked through and into the mountain pass.

Ann had walked about a mile when she came upon a completely unexpected sight. There, nestled in the mountains, was a lavish resort filled with wizards. Wizards lounged by the pools, played beach volleyball, and were generally having a good time. Ann stood in shock, until an old wizard approached her and introduced himself.

"What is this place?" asked Ann.

"A wizard's resort." answered the wizard.

"But, it is completely hidden." stated Ann. "I have never heard of this place."

"Of course not." laughed the wizard. "We built the gates of Xor to ensure that. No-one that passes through the gates is a threat to us."

"Excuse me?" asked Ann, offended by the wizard's statement.

The wizard smiled broadly. "I mean no offense. It is just a matter of binary logic. We constructed the gate using two attributes, strength and intelligence, and an xor function. A person can only pass through if they have exactly one of the attributes. Basically, they need to be (strong AND NOT intelligent) OR (NOT strong AND intelligent). That is how we created the gate."

"But how does that protect you?" asked Ann.

"Let's look at the 4 cases:

1) If you are smart and strong: then you are a real threat. So, we do not let you pass.

2) If you are strong and dumb: then you only think you pose a threat. We can use your overconfidence to cast a spell of confusion. So, you are really no threat; and we let you pass.

3) If you are weak and smart: then you pose no threat, because you are smart enough to know that you cannot win in a fight with us. So, we let you pass.

4) If you are weak and dumb: then you will probably go tell your big friends where to find us. So, we do not let you pass.

It is all very simple."

"But that means…" started Ann.

"That you are either weak or dumb." finished the wizard. "Either way, you are not a threat to us. Now, off you go." As he finished, the wizard started to push Ann down the path out of the village.

"But… but…" objected Ann. She was definitely offended now. But, given the fact that a frail-looking wizard in his late eighties was pushing her down the road with seemingly super-human strength, she was smart enough to know that she would not win this fight.

"Off you go," repeated the wizard.

Suddenly, a thought came to Ann. "You could help me in my quest." she suggested.

"We don't do that." answered the wizard. "That is why we built a secret resort in the middle of the mountains, so that we do not have to help with quests... or perform at birthday parties. Now go on."

As Ann walked away from the wizard's resort, she wondered whether the short cut through the Lagrange mountains was worth the insults.

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

Read Part 3 of Ann's encounter with the Booleans in The Valley of NAND and NOR!

The Town of Bool: Part 1 of Ann's encounter with the Booleans

Boolean logic is based on two values: TRUE and FALSE (or alternately ON and OFF for physical transistors). Complex logical expressions can be formed by using a few simple operations, such as: AND, OR, and NOT. These expressions allow computers to perform logic such as: adding binary digits, determining if an IF statement executes, or controlling when a loop terminates.

Ann found her short stay in the town of Bool most annoying. She had always heard that the Booleans were strict believers in binary logic -- everything was either true or false. She had naturally assumed that this simply meant that they were opinionated. For example, she would not expect anyone in Bool to state “Jazz is okay”. Opinions would be definite. However, she had not expected this philosophy to apply to absolutely every single aspect of life.

The first surprise had come at a local restaurant.

“May I get some more water, please?” Ann asked a waiter.

“No.” he replied. “I only refill a glass if it is: empty AND you are still eating.”

“I am still eating.” Ann assured him.

“Yes. But your glass is NOT empty.” he responded as he moved off to the next table.

Ann looked down at her glass. There was at most three drops of water left at the bottom. Ann sighed and finished those drops in preparation for the waiter's return. She decided that in this case she was going to embrace their binary philosophy and NOT give him a tip.

Luckily, Ann was well equipped for her stay. She had studied Boolean logic as an elective in kindergarten. It all came down to a few simple rules:

• There were only two options TRUE and FALSE,
• A AND B evaluated to TRUE if and only if both A and B were TRUE,
• A OR B evaluated to TRUE if either A or B were TRUE,
• NOT A evaluated to TRUE if and only if A was FALSE.

Conceptually, it was very simple and matched how most people used the terms in everyday life. Unfortunately though, the laws of Boolean logic were not really designed for living everyday life.

Over the course of her 16 hour stay, Ann continued to experience the frustration of dealing with the Booleans' world. She found that when the park proclaimed that it was “closed at dark”, the patrons would stay until the sun had technically set and then run out of the park. Similarly, getting directions turned out to be extremely aggravating.

“Is the hotel in that direction?” she asked, pointing approximately south east.

“It is NOT in that direction,” proclaimed a Boolean on the street. “It is in that direction.” The Boolean was pointing in almost, but not exactly, the same direction. Ann sighed and walked in approximately the correct direction.

“You are NOT going in the correct direction.” the Boolean shouted after her. Ann ignored him.

Even the signage in Bool was overly logical. The crosswalk light actually said “Cross when the WALK light is on AND there are no cars speeding toward you.” Did they really need to clarify that? Ann wondered what would happen if someone misprinted the sign to use an OR? Would it be chaos?

It was not until she reached the hotel that Ann really understood the true adherence to this logical formulation. There, on the back of her hotel door, was a fire escape plan like you would find at any hotel. Except in this case, all of the conditions were specified as long Boolean logic statements. “Use the South Stairs if: (they are NOT on fire AND the north stairs are on fire) OR (there is an obstruction in the hall toward the north stairs) OR …”

After reading the sign four times, Ann decided that in the event of a fire she would be too confused to escape. She promptly resolved to leave Bool as soon as she could.

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

Read Part 2 of Ann's encounter with the Booleans in Part 2: The Gates of XOR. Or see how the Booleans like to trick people in Fun with Boolean Statements.