Propositional Logic

A proposition is, at its heart, just a statement which can be true (⊤) or false (⊥). And it can only be true or false. Not “maybe”. Not “both” or “neither”. It’s always ⊤ or ⊥.1

“It is rainy and wet” is a proposition. “7 is a prime number” is a proposition. “A dark sky implies the sun is not visible” is a proposition. All are either ⊤ or ⊥.

Note the “…or ⊥” bit above. A proposition does not need to be ⊤ to be a proposition. “12 is a prime number” is very much a proposition — it just happens to be ⊥.

Compound and Atomic Propositions

We might note that there’s another difference between our propositions above beyond whether they’re ⊤ or ⊥.

Some, like “7 is a prime number”, feel irreducible and seem to stand on their own. Others, like “it is rainy and wet” would appear to contain multiple, smaller propositions within themselves (both “it is rainy” and “it is wet” are each, individually, statements that can be either ⊤ or ⊥).

An atomic proposition is a proposition that is irreducible — that is, it is in its entirety just a single proposition. “7 is a prime number” is an atomic proposition.

A compound proposition, on the other hand, is some combination of atomic propositions connected together with… words. Words like “and”, “or”, “not”, and so on. “It is rainy and wet” is a compound proposition — and also where things start to get a little less straight forward.

Because as clear as the meaning behind “it is rainy and wet” is, there are hundreds of ways we could phrase it:

It’s rainy as well as wet.

In addition to it being rainy, it is also wet.

It’s rainy; what’s more, it’s wet.

All carry the same meaning despite the different words and constructions used. Which means a single concept can be expressed by many different representations. That can get pretty confusing.

But what’s worse, many phrasings appear to mean the same thing but actually mean something subtly (or mistakenly) different. Take:

Its raininess was only matched by its wetness.

At first glance this looks to mean the same thing as our examples above; it’s rainy and wet. But couldn’t it also mean it’s neither rainy nor wet?

A Formal Language

There’s nothing wrong with writing propositions out in english as we have above. It doesn’t make them any less propositional. But as we’ve seen, spoken language often trades preciseness for expressiveness and thus carries with it inherent ambiguity. Once we start combining atomic propositions into compound ones — threading them together with spoken language — ambiguity seems to flood in through the cracks between.

We need a formal language — that is, a terse language whose vocabulary and grammar have been boiled down to their most essential essence — in order to squeeze the ambiguity out of our propositions.

To us programmers, this is a familiar concept. If we try to evaluate the text “four score and seven years”, our interpreter won’t know where to start. But if we rewrite it into the formal language of, say, javascript…

const score = 20;
let years = (4 * score) + 7;

the meaning is now unambiguous to our interpreter allowing it to perform computation.

The same is true of propositions. Reducing them to a formal representation removes all ambiguity and thus allows us (or our computer) to manipulate them in a mathematical context.

Two Disciplines

These, then, are the two major undertakings that surround propositional logic (and, indeed, all formal logics):

To the programmer, these steps roughly correlate to “learn to code in a particular language” and “learn to parse/compile/interpret that language”. While the former is obviously prerequisite for any practitioner, the latter is the domain of a particular type of engineer. The rest of us just let the computer handle it.

So it is with logic. Many texts spend a lot of time on truth trees, open and closed branches, and detailed rules of inference with awesome latin names like modus ponens.

Understanding this symbolic manipulation of logical statements gives us a deeper understanding of the nature (and beauty!) of logic in the same way diving into SICP opens up a whole other window through which we can appreciate our code.

But that is a project for some other year. For now, I aim to focus on the “language” of logic, allowing us to fluently “code” in it. I’ll leave its interpretation to “compilers” like Alloy.

Next week we’ll take another step down the “language of logic” path when we dig into the syntax of propositional logic.

  1. See the symbol page for more information about the symbols used in this post. ↩︎