Programmer’s Anti-intuition

So far we’ve covered the first three logical connectives: negation, conjunction, and disjunction. That only leaves two for us to tackle this week: implication and the biconditional.

Seems easy enough! But unfortunately, unlike negation and the ’junctions, our programmer’s intuition actually works against us for these final connectives. Let’s break down what they are and why they may seem weird to us.

Implication

“Implication”, or →, is sometimes called a “conditional”. In fact, in some logic circles it’s pronounced “if”. As in, for the propositions 𝑆 = “the switch is on” and 𝐿 = “the light is on”, 𝑆 → 𝐿 might be read “If the switch is on, then the light is on.”

I would strongly recommend against this reading, though. We programmers have a lot of baggage when it comes to conditionals — ifs in particular — and have strong intuitions about how they should play out:

That is, if the switch is on, then the light is on. If the switch is off, then the light is off. All other combinations are nonsense and thus false.

But logically™ this is completely wrong. The actual truth table for implication looks like this:

That is, if the switch is on, the light must be on. But all other configurations are also valid.

This can be a bit of a 🤯, but if we slow it down and think it through, it makes perfect sense. We said, “If the switch is on, then the light is on.” Considering it carefully, we see the only state we’re making any claim about is when the switch is on. We’re completely silent about what we expect when the switch is off. And so, when the switch is off, anything goes.

To put it another way, “If the switch is on, then the light is on” is like a floating conditional statement without an else clause:

const switchIsOn = false;
var lightIsOn;
if(switchIsOn) {
  lightIsOn = true;
}

Ah, now we can see: the state of lightIsOn is undefined when switchIsOn is false.

This is a Bad Thing in programming, so we are hard-wired to avoid this sort of undefined ambiguous behavior in our code. So hard-wired, in fact, that when many of us hear “if… then…” we mentally insert the unspoken else.

This is why I shy away from pronouncing → as “if”. Years of habituation prevent me from taking it at face value. So instead, I read it as “implies”; as in “The switch being on implies the light is on.” “Implies”, to my ear, hints at the undefined ambiguity surrounding the light when the switch is off.

The Biconditional

There is a connective that does the full if-then-else thing, though, just like we wanted. It’s the biconditional, usually represented with a ↔. And in some circles, “𝑆 ↔ 𝐿” is indeed read as “If the switch is on, then the light is on, otherwise the light is off.”

So we should just use ↔ instead of →, right? Well, no. It turns out once again that our instincts for the imperative, procedural world of code may be blinding us in subtle-but-important ways.

Let’s look at a particularly imperative way to express “if the switch is on, then the light is on, otherwise the light is off” in code:

if(switchIsOn) {
  turnLightOn();
} else { 
  turnLightOff();
}

We’re used to reading this in a kind of temporal, branching way. If the switchIsOn then the code branches such that turnLightOn() gets evaluated. Otherwise some completely different branch is executed, calling turnLightOff().

And these branches are mutually exclusive. Only one or the other is taken, depending on the value of switchIsOn. This is the very definition of a conditional: depending on a value, different paths are travelled.

Look what happens, though, when we convert this to the declarative, value-based world of logic by replacing our procedures with values:

var switchIsOn = true;
var lightIsOn;
if(switchIsOn) {
  lightIsOn = true;
} else { 
  lightIsOn = false;
}

Hmm. “If true then true, if false then false.” This is pretty redundant. We could keep the code functionally identical, but DRY things up with a direct assignment:

var switchIsOn = true;
var lightIsOn = switchIsOn;

Or, even further:

var switchIsOn = lightIsOn = true;

Ahh. And now we see. Because boolean types have only two values (true and false), setting one variable based on the if and the else of another completely defines all its possibilities. There is no condition, only assignment. Saying “if the switch is on, then the light is on, otherwise the light is off” is the same as saying “The switch and light are equivalent.”

And that’s usually a stronger claim than we’re prepared to make. Consider a proposition in which the switch is one way to power the light (𝑆 ↔ 𝐿), but there’s also a solar panel wired up such that, when it’s bright out, the light is on as well (𝐵 ↔ 𝐿).

Now, because when it’s bright out the light is on, and because the light and switch are equivalent, whenever it is bright, the switch suddenly flips on. Or, more perversely, whenever we flip the switch to turn on the light, we also makes the sun come out!

⊤ Flow

All this highlights the true utility of implication’s “undefined” ⊥ case. If we say instead that an on switch implies a lit light (𝑆 → 𝐿) and that a bright day implies a lit light (𝐵 → 𝐿), then it’s completely possible for 𝑆 to be ⊤ while 𝐵 is ⊥. Though 𝑆 → 𝐿 requires 𝐿 be ⊤ when 𝑆 is, 𝐵 → 𝐿 means 𝐿 can be whatever it wants so long as 𝐵 is ⊥. Taken in reverse, 𝐵 can be ⊥ regardless of what 𝑆 requires 𝐿 to be.

If that doesn’t makes sense (and believe me, been there), get out some paper and write it down. It’s hard enough to build up an intuition for these things from scratch. It’s doubly hard when having to set aside an existing-and-partially-conflicting intuitions from another craft. Pull out some paper and prove it to yourself. Trust me, it helps.

Another thing that can aid as a sort of mnemonic is thinking of the arrows as showing the flow of ⊤ values through the proposition.

Take 𝑃 → 𝑄. When 𝑃 is ⊤, 𝑄 must be as well. The ⊤ “flows” from 𝑃 to 𝑄 in the direction of the arrow. But if 𝑄 is ⊤, 𝑃 is free to be whatever it wants. The ⊤ doesn’t flow against the arrow.

The weird corollary to this is that ⊥ values flow backwards. In 𝑃 → 𝑄, a 𝑃 with ⊥ doesn’t require anything of the 𝑄. The ⊥ does not flow in the direction of the arrow. But when 𝑄 is ⊥, 𝑃 must be as well. The ⊥ flows “backwards” across the arrow.

With the double-ended arrow of 𝑃 ↔ 𝑄, of course, both ⊤ and ⊥ flow in both directions. The leads to 𝑃 and 𝑄 always taking whatever value the other has. Which, as we’ve discussed, means they are always equivalent.