Propositional Logic
A (True ∨ False) Story
In my previous post, I discussed the importance of foundational elements of software development such as propositional logic. The words “propositional logic” may strike fear into the hearts of many, but one need not fret. At its core, propositional logic is nothing more than the practice of asserting that particular statements are true or false and combining them in different ways to create new statements which are themselves true or false.
Many a dense textbook begins exploring propositional logic with a pair of rather intangible entities P and Q. Digestible educational material starts with the concrete and slowly becomes more abstract, so let’s try that instead.
Suppose we begin with two premises:
- When Charles misses the bus, he’s late for school.
- Charles has missed the bus.
From these premises we can conclude that Charles is late for school. We are able to conclude this because we’ve started with two pieces of information we assume are valid and combine them to produce a logical conclusion.
We could alter the wording of our first premise as follows:
If Charles has missed the bus it implies that he’ll be late for school.
This new sentence structure parallels the language in our second premise and makes the conclusion we reached even more apparent. Let’s break this structure into its constituents:
If Charles has missed the bus it implies that he’ll be late for school.
The phrases in italics are propositions. They are the building blocks of propositional logic. You can recognize these pieces because they will never have an air of conditionality associated with them. If you examine the propositions above, you’ll notice they read like matter-of-fact statements.
The piece in bold above is a logical connective. This simply means that it’s used to connect two propositions or groups of connected propositions. We’ll talk more about these soon.
Let’s look at our sentence once more, this time replacing our propositions with placeholders and removing unnecessary words:
P implies Q.
Hey look, it’s our friends P and Q! A special symbol was created as shorthand for this relationship, called implication — “P → Q”
Things will get a bit more complicated from this point on, so buckle your seatbelt.
I haven’t forgotten that I promised to return to logical connectives. As a reminder, these connectives are just operators that connect propositions or connected groups of propositions. The simplest operator — which isn’t a connective — is negation. Negation denotes using the meaning opposite the negated phrase:
¬P → Q
In the context of our more concrete example, this would correlate to:
If Charles hasn’t missed the bus, it implies that he’ll be late for school.
This new sentence doesn’t make a lot of sense unless Charles’ bus driver is dreadfully inept, but it demonstrates that negation flips the meaning of a proposition entirely. Note that we only negated the first proposition; if we want to say that he won’t be late for school we need to negate the second proposition too!
The two most basic logical connectives are conjunction and disjunction.
Conjunction is an assertion that two propositions must both be true. If either is false, their conjunction is false. This is denoted as “P and Q.”
Disjunction is an assertion that either one or both propositions are true. The only time the disjunction is false is if both propositions are false. This is denoted as “P or Q.” Note that the “or both” part is implied here.
Other logical connectives exist, and they simply change how propositions come together. We’ll explore these in depth in another installation.
That wasn’t so bad, was it? We learned what propositions are, how they map to real language, and how to connect them together to make new propositions. Propositional logic combines these ideas with laws and proofs to reach conclusions. These tools are useful in a number of fields, and in particular I’d like to steer the discussion of their use toward writing software. We’ll talk more about this as time goes on! If you’ve made it this far there may be hope for you yet.
