#Logic: the truth is out there

#Riddle me this

You are standing before two doors. One door leads to your desire. The other leads to your doom. Before the doors are two guards. They both know which door leads where. One guard always lies. The other always tells the truth.

You may ask one question.

Obviously, you need to ask a question that reveals which door to use. But the obvious question doesn't work.

Which door should I choose?

If you ask the truthful guard, she'll point to your desire. If you ask the lying guard, she'll point to your doom. Since you don't know which guard you're asking, the answer is useless. Let's put both possibilities in a table:

That doesn't help. The answer depends on which guard you asked, and you don't know that. So the famous solution is to ask a different, less direct question:

If I asked the other guard which door leads to my desire, what would she answer?

Now whatever answer you get, you choose the other door.

If the guard you ask tells the truth, she must give you the wrong answer, because that is what the liar would say. If the guard you ask lies, she must also give you the wrong answer, because she lies about the truthful guard's answer.

No matter which guard you ask, you get the wrong answer. So you choose the other door.

Your brain is good at guessing. Logic is what we use when guessing isn’t good enough.

#Boolean logic

George Boole Boolean logic https://en.wikipedia.org/wiki/Truth_table Today we call this Boolean logic, after George Boole. The tables above are called truth tables. https://en.wikipedia.org/wiki/George_Boole https://en.wikipedia.org/wiki/Truth_table

Logic itself is much older, going back through the 17th century wizard Leibniz, to an ancient Greek wizard called Aristotle. Boolean logic is the smaller, stricter version that computers use today.

Boolean logic has only two values:

Boolean logic is at the core of modern programming. It is at the core of computers. Everything your computer does for you is built, eventually, on Boolean logic: true and false, 1 and 0.

Most Boolean operations combine two terms. Let's call them p and q. Just like our guards, we don't know whether they are true or false. But using truth tables, we can reason about them anyway.

The operations are: and, or and not.

And of course:

Combining these, we can also create nor and nand.

Wait a minute... what is this nand thing? Why not just write not and?

https://en.wikipedia.org/wiki/NAND_logic https://en.wikipedia.org/wiki/NAND_gate Well... it so happens that your computer can implement just about everything with only nand logic. All other operations can be written as combinations of one or more NANDs. Hardware wizards found ways to create tiny NAND gates, and from those gates built the tiny parts of modern CPUs. https://en.wikipedia.org/wiki/NAND_logic https://en.wikipedia.org/wiki/NAND_gate

#This much is true

What does all this logic trickery do for you? Well, you can reason with it, of course. But doing so can become difficult pretty quickly. For example, when is this logic equation true?

(not p and not q and r) 
or (not p and q and r) 
or (p and q and r) 
or (p and not q and r)

https://en.wikipedia.org/wiki/Karnaugh_map Unless you are a computer, you probably struggle coming up with the answer. A truth table won't help you here, there are three variables, not two. It becomes difficult to see the pattern. But there is a slightly different truth table that may help: A Karnaugh map: https://en.wikipedia.org/wiki/Karnaugh_map

Instead of true and false, we're using 1 and 0, but they mean the same thing.

The column headings now show a combination of both q and r, in an unusual order. The trick is that this order makes sure that only one of those values changes when you move to the left or the right. So each column shows answers that only differ in one detail, one input, compared to the columns next to them.

What you probably noticed immediately is that the true outputs, the 1s, are clustered in a block in the middle. If you look carefully, in that block both p and q vary, while r stays the same. So the output always matches the value of r.

You can simplify the whole equation to just r and get the same result.

The map did not change the equation, it only changed how it was written down. It contains the same answers as a truth table would. The only thing that changes is that we chose a notation that allows you to see the patterns.

A useful notation changes what you can easily express and see.

Tables don't lie, but people do. And we like it. So much that we've invented something entirely new. Something clever and diabolical, called language.