Part 1: Logical Reasoning & Using Variables

An Example

Take a look at the following statement:

If it's not raining tomorrow then I'll go for a walk and I'll get ice cream.

This statement has a couple of what we will call propositions, which are things that can either be true or false:

It also has a few connectives that relate these propositions to each other:

Math works the exact same way! For these propositions we can use variables, and for connectives we can use mathematical symbols known as operators.

Propositions and Connectives

Let's replace the propositions with variables, and the connectives with operators:

Now we could write down the statement as follows, where the parentheses help to read the formula:

\( (\lnot r) \Rightarrow (w \land i) \)

Truth Tables

A propositional variable such as \( w \) can be either true (written as 1, meaning I am actually going for a walk) or false (written as 0, meaning I am not going for a walk). These are known as boolean values.

A boolean operator combines these boolean values into new boolean values, which is written in a truth table. For all possible combinations, it tells you if the formula is true or false.

Let's look at the first and also hardest operator \( \Rightarrow \). The formula \( a \Rightarrow b \), pronounced "\( a \) implies \( b \)", can be seen as a promise: if \( a \) is true, then we have to fulfill \( b \). For example, the statement "if it's sunny, I will buy you ice cream" can be viewed on a case-by-case basis:

\( a \) \( b \) \( a \Rightarrow b \)
🌧 not sunny no ice cream ✅ (it wasn't sunny so you didn't break your promise)
🌧 not sunny 🍦 ice cream ✅ (you did not say anything about this case, but I'm glad you still got me ice cream)
🌞 sunny no ice cream 🚫 (you said in this case we would get ice cream, but we didn't...)
🌞 sunny 🍦 ice cream ✅ (promise fulfilled)

Unfortunately, mathematicians don't work using emojis, so instead we write 0 for false/no and 1 for true/yes. If you know the values for \( a \) and \( b \), then this table tells you the value for \( a \Rightarrow b \):

\( a \)\( b \)\( a \Rightarrow b \)
001
011
100
111

For \( a \land b \) (pronounced "\( a \) and \( b \)"), the truth table is:

\( a \)\( b \)\( a \land b \)
000
010
100
111

For \( a \lor b \) (pronounced "\( a \) or \( b \)") the truth table is:

\( a \)\( b \)\( a \lor b \)
000
011
101
111

Now an interesting question arises: if I say "we can go to the mall or we can order from home", does that mean we can also do both? In other words, does the "\( \lor \)" operator include the possibility that both are true? In logic, the answer to this question is yes, and the \( \lor \) operator is therefore called "inclusive or". If you don't want this, you can use the so-called "exclusive or" operator (often shortened to "XOR" or "\( \oplus \)"), which has the following slightly different truth table (compare them!):

\( a \)\( b \)\( a \oplus b \)
000
011
101
110

It will turn out we don't really use the \( \oplus \) operator a lot in logic though. However, it is used a lot in computer programming and electronics.

The "not" operator, written as \( \lnot \), takes only one boolean input and has a very simple truth table:

\( a \)\( \lnot a \)
01
10

Finally we have the \( \Leftrightarrow \) operator named bi-implication. This is essentially an implication, but in both directions. \( a \Leftrightarrow b \) is often pronounced as "\( a \) if and only if \( b \)", often shortened to "\( a \) iff \( b \)" (not a typo!), and it has the following truth table (compare with the truth table for \( \Rightarrow \)):

\( a \)\( b \)\( a \Leftrightarrow b \)
001
010
100
111

Don't worry if you think you might forget all these operator and truth tables. You will see these so often that you'll remember them soon enough, and I have a cheatsheet here.

Art by Alice

Reasoning with Truth Tables

You can also put more complicated formulas in a truth table. For instance, we can write out the truth table for the example above, with extra columns in between to show the intermediate steps (for subformulas \( \lnot r \) and \( w \land i\)):

\( r \) \( w \) \( c \) \( \lnot r \) \( w \land i \) \( (\lnot r) \Rightarrow (w \land i) \)
000100
001100
010100
011111
100001
101001
110001
111011

If we have a formula for which each row in the truth table results in a 1, this means that the formula is true no matter what input we give it. In this case, the formula is called a tautology. In the same way, if each row has a 0 as the result, that means the formula is always false and we call this a contradiction.

Exercises

  1. Write out the truth tables for the following formulas. Add columns for the subformulas.
    1. \( a \Rightarrow (b \Rightarrow a) \)
    2. \( (a \Rightarrow b) \Rightarrow a \)
    3. \( (a \land b) \Leftrightarrow (\lnot c) \)
    4. \( \lnot (a \lor b) \Rightarrow \lnot a \)
  2. Which of the formulas in exercise 1 are tautologies? Which are contradictions? This should be easy to see from the truth tables you made.
  3. If you have a truth table with \( n \) different variables, how many rows will it get?

Next Lesson

As you can see, the number of rows of the truth table grows really fast. For example, if we have 20 variables, we already get 1 048 576 rows, which is clearly not practical. For this reason, we need better techniques than simply listing all possibilities. This is something for in the next chapter!

NEXT LESSON

Addendum

Some final notes and disclaimers: