Richard Chen

Propositional Logic 1: The Basics

Last Edited January 3, 2016
Created April 9, 2016

Hey folks, so as a U of T Computer Science student, one concept that I've studied here and strangely enjoyed is the idea of propositional logic. Those of you taking courses like CSC165 and CSC236 will be introduced to this sort of notation, which is critical in writing proofs and reasoning in the field of software design. Thus, today I'm going to begin a series of articles for any students in these courses on propositional logic in case something isn't clear for any of you.

Bread and Butter: Booleans and Logical Connectives

Booleans: Booleans refer to variables that can either have a true or false value, not unlike booleans in most programming languages. As such, they can represent the truthhood or falsehood of ideas, like these:

There are three pieces of pizza left in the refrigerator.
It rained every day for the past month.
The population of Toronto is 2.503 million.

Clearly, the above statements can be contextually true or false. Depending on what house you live in, there may be three pieces of pizza left in the fridge or none at all; the truthhood of the second statement can vary between if you live in the Amazon or in Antarctica; and perhaps one day, Toronto's population will spiral out of control to 5 billion, but currently (according to Google Search) the statement is true.

Other statements, however, can be true under any circumstance, or false under any circumstance. Statements of the former kind are called tautologies

We represent booleans in propositional logic with single lowercase (or sometimes uppercase) letters, like this: $p, q, r$, or this: $P, Q, R$.

In some areas of study, booleans are called atoms because they are statements that can't be broken down any further (i.e. statements that don't consist of logical connectives, like AND, OR, or NOT).

Logical Connectives: Of course, booleans by themselves are not very interesting as we often want to relate one of more of them with certain connectives. Consider these statements represented in a natural language:

  1. Dmitri went to the party last night.
  2. Dmitri and Jonathan went to the party last night.
  3. Andy Dick went to the party last night, so Dmitri and Jonathan didn't go to the party last night.
  4. Either Andy Dick, Dmitri or Jonathan went to the party last night.

We can consider a representation of each of the above statements with some boolean values. So, we let:

  • $D$ represent that Dmitri went to the party last night;
  • $J$ represent that Jonathan went to the party last night;
  • $A$ represent that Andy Dick went to the party last night. (Like he's ever gonna be invited to one.)

To represent the first statement, we can simply use the following: $$D$$ This is rather simple. The next few ones are a little more interesting, such as that for number two: $$D \wedge J$$ Now that little $\wedge$ that you see is called the AND symbol, which, as in natural language, denotes that both its operands must be true in order for the resulting statement to be true.

The third one is even better: $$A \Rightarrow (\neg D \wedge \neg J)$$ Here we see the use of three symbols: the AND symbol from before, the NOT symbol ($\neg$), and the implication symbol ($\Rightarrow$). The NOT symbol negates the value of a boolean, or any statement in general, and the implication symbol dictates that, for the whole statement to be true, whatever on the left side of the implication arrow must be false, or if it is true, then whatever is on the right side must also be true. (This is going to be a little confusing at first but bear with me.)

Finally, we have number four: $$D \vee J \vee A$$ ...and as you can guess, the $\vee$ is the OR symbol: for the statement to be true, only one of its operands has to be true. Since $\vee$ is a binary operator, however, we need to evaluate $D \vee J$ first and then take the logical or of the result with $A$, or evalute $J \vee A$ and then take the logical OR of that with D, depending on what kind of associativity (left or right) you use. However, the OR operator is associative anyways, so regardless of what order you evaluate them in, you get the same result in the end.

Oh, there's one final symbol I've neglected to mention, the bi-implication symbol ($\Leftrightarrow$). Let's say $S$ represents that Sarah Palin went to the party last night. Then the following: $$A \Leftrightarrow S$$ ...means this: $$A \Rightarrow S \wedge S \Rightarrow A$$

Essentially what we are saying is that either Sarah Palin and Andy Dick are at the party at the same time, or they both aren't at the same time. If $A$ is true, then $S$ has to be true, and vice-versa, and if $S$ is true, then $A$ is true and vice-versa. It isn't possible for one of these booleans to be true and the other false; they both have to have the same value at the same time. (Don't ask me what Sarah Palin and Andy Dick are doing together.)

Truth Tables

So some of you are probably wondering what the diagram at the beginning of this article refers to. This is called a truth table. A truth table's main function is to determine what the value of one or more non-atomic statements are, given all possible combinations of values asssigned to each of the individual booleans. Any one of these combinations is what we call a truth assignment to a set of variables.

It's easier explained than said, so here are some truth tables representing each of the five important connectives I have mentioned above:

AND