## Wednesday, May 11, 2011

### 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!