My propositional logic notes.

March 23, 2025

Summary

Recently I took a freshman Computer Science course in logic, set theory, and relations at the Open University in the Netherlands. The course proved to be more difficult than expected, but I managed to pass the course on my first attempt. However, I felt I could have done better with a bit of extra work, and that is the reason why I am writing this blog post.

This post contains not only my notes on propositional logic, but also the ‘ah-ha’ moments that I have experienced while studying the course. These ‘ah-ha’ moments vary from simple algebraic tricks that I (re) learned, to the realization that a large part of what you learn in propositional logic can also be applied in other fields such as predicate logic, boolean algebra, and set theory.

The most important thing that I have realized is that logic is the basis for mathematical proofs, and for that reason alone I believe it is wortwhile to deepen your knowledge on (propositional) logic.

For this post I have used three sources.

• The study material of the Computer Science course “Logica, verzamelingen en relaties” from the Open University. Note that the course material is in Dutch.
• The “Proofs, a long-form mathematics textbook” book from Jay Cummings.
• The propositional calculus Wikipedia page.

What is propositional logic?

Propositional logic deals with statements (which are called propositions) that are either true or false, and the relations between these propositions. Let’s look at a few examples.

• I stay at home.
• Utrecht is a town in the Netherlands.
• An even number is divisible by two.

Each statement is either true or false, making them valid propositions. Although these concrete examples might be helpful in the short run, it’s better to let the propositions be abstract. Since (propositional) logic is a branch of mathematics, the focus is on general characteristics of propositions, and how they behave when combined. Therefore, from now on, I will use symbols like $p, q, r$ that each represent a proposition.

Logical connectives

The three proposition examples from the introduction are ‘single’ statements, also called atomic statements. With logical connectives you can combine atomic statements into a compound statements. The following list covers the most common connectives.

With these logical connectives I am now able to express the compound statement “I stay at home and Utrecht is a town in the Netherlands” as:

Similar to the order of operations of the math you already know (parentheses, exponents, …), propositional logic also has a few rules that you need to follow to correctly combine propositions:

1. The negation connective is evaluated first.
2. If necessary, use parentheses.

Valid propositional statements are called formulas, which is the topic of the next section.

Formulas, partial formulas and reach

Before presenting the exact definition of a formula, let’s look at a few examples.

Each of these compound statements consists of smaller building blocks, the atomic formulas ($p, q, r$) in this case. Together with the logical connectives these atomic formulas are combined into compound statements, and parentheses are applied when necessary. This brings us to the following inductive definition of a formula. To aid the generalization of the definition, it is common to use Greek letters like $\phi$ (‘phi’) and $\psi$ (‘psi’) that refer to random formulas.

1. Every propositional letter is a formula.
2. If $\phi$ is a formula, then $\neg\phi$ is also a formula.
3. If $\phi$ and $\psi$ are formulas, then ($\phi \land \psi$), ($\phi \lor \psi$), ($\phi \to \psi$), ($\phi \leftrightarrow \psi$) are also formulas.
4. There are no other formulas.

If we look closely at this definition, we notice that formulas are build from other (smaller) formulas. Since these smaller formulas are part of the final formula, they are called partial formulas. Let’s examine this idea with the following formula.

• The smallest (atomic) formulas are the propositional letters, so $p$, $q$ and $r$ in this case.
• Since $p$ and $q$ are formulas, $(p \land q)$ is also a formula.
• And since $(p \land q)$ and $r$ are formulas, $(p \land q) \to r$ is also a formula.

Directly related to these partial formulas is the range of a logical connective, which tells us which part or parts of the formula are affected by the connective. For example, the range ($\underline{underlined}$) of the $\land$ connective in $(p \land q) \to r$ is $(\underline{p} \land \underline{q}) \to r$, while the range of the $\to$ connective is $\underline{(p \land q)} \to \underline{r}$.

Although these details might seem tedious and not that interesting, I will show you later in this post that it is important to understand the partial formulas and the range of the connectives. Furthermore, the idea of connectives and their range applies to other mathematical topics as well, such as predicate logic and set theory.

Truth tables

Truth tables are tables that help to find the truth value of a formula. To get the truth value of a composite formula, we first need to find the truth value of each partial formula, and the effect of the connectives on these truth values. Let’s look at an example.

There is a lot going on in this table so let’s break it down step-by-step. To aid in a better understanding of the evaluation of each column I have included the order of steps ( $^{1234}$).

1. The left two columns $p$ and $q$ represent each combination of the two propistion letters.
2. Break the formula into partial formulas and use a column for every proposition letter and connective.
3. Fill in the values for the propositional letters as written down in the left two columns¹.
4. Since the negation connective takes precedence over other connectives this column is filled next².
5. Since we work from the inside to the outside of the formula, the next comparison is the conjunction $(p \land \neg)$³.
6. The final comparison is the disjunction $(\land \lor q)$⁴.

Truth tables are a powerful and convenient way to to evaluate the truth values of a (composite) formula. However, as you can imagine these tables are difficult to use for complex formulas since the number of unique combinations of the proposition letters is equal to $2^n$. Later in this post we will discuss the laws of propositional logic which help to identify certain patterns in composite statements. Since these pattern have fixed truth values they allow to drastically simplify complex formulas.

From natural language to propositional formula

Before we go to the next level and examine the laws of propositonal logic, let’s look at a few examples where we translate real world sentences into valid propsitional formulas. Say we have the following two propositions.

• Ernst takes the train ($p$).
• Ernst goes to work ($q$).
• It is weekend ($r$).

a. If Ernst goes to work, he takes the train.

b. If Ernst does not go to work, he does not take the train.

c. If it is weekend and Ernst takes the train, he does not go to work.

Although natural language is much more powerful than propositional logic, the advantage of propositional logic is that you can be specific. Consider the following sentence and ask yourself who is going to the party?

• Ernst and Henk or Kees go to the party.

Is it Ernst and Henk? Is it just Kees? Is it Ernst and either Henk or Kees? Or all the three of them? It is unclear. However, with propositional logic we can be exact.

• Ernst goes to the party ($p$).
• Henk goes to the party ($q$).
• Kees goes to the party ($r$).

This formula is already an improvement since it becomes clear that Ernst and Henk are going to the party, or Henk. However, the $\lor$ connective is also true when both statements are true. So it’s still possible that Ernst, Henk and Kees are all going to the party. We can fix this ambiguity with another connective called XOR, which is shorthand for exclusive-or.

From this truth table you can immediately see when xor applies by looking at the rows where $xor=1$ and then inspecting the first three columns for the truth-values of $p, q, r$.

Now that you know about the basics of propositional logic, let take a look a the laws of propositional logic.

The laws of propositional logic

Coming soon.