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's raining tomorrow
- I'll go for a walk
- I'll get ice cream
It also has a few connectives that relate these propositions to each other:
- if ... then ...
- not ...
- ... and ...
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:
- \( r \) to denote that it is raining tomorrow
- \( w \) to denote that I'll go for a walk
- \( i \) to denote that I'll get ice cream
- \( \lnot \) for "not ..."
- \( \Rightarrow \) for "if ... then ..."
- \( \land \) for "... and ..."
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 \) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
For \( a \land b \) (pronounced "\( a \) and \( b \)"), the truth table is:
| \( a \) | \( b \) | \( a \land b \) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
For \( a \lor b \) (pronounced "\( a \) or \( b \)") the truth table is:
| \( a \) | \( b \) | \( a \lor b \) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
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 \) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
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 \) |
|---|---|
| 0 | 1 |
| 1 | 0 |
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 \) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
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 bbpoltergayst on Tumblr (opens new tab)
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) \) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
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
-
Write out the truth tables for the following formulas. Add columns for the subformulas.
- \( a \Rightarrow (b \Rightarrow a) \)
- \( (a \Rightarrow b) \Rightarrow a \)
- \( (a \land b) \Leftrightarrow (\lnot c) \)
- \( \lnot (a \lor b) \Rightarrow \lnot a \)
- Which of the formulas in exercise 1 are tautologies? Which are contradictions? This should be easy to see from the truth tables you made.
- 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!
Addendum
Some final notes and disclaimers:
- Notation used by people is often different. Some people use \( \Rightarrow \) and \( \Leftrightarrow \), others use the thinner arrows \( \rightarrow \) and \( \leftrightarrow \). Some people write \( \mathit{true} \) for 1 and \( \mathit{false} \) for 0.
-
Parentheses are often unnecessary, so \( (\lnot r) \Rightarrow (w \land c) \) could also be written as
\( \lnot r \Rightarrow w \land c \). Just like how in algebra, \( a + b \cdot c \) is \( a + (b \cdot c) \) and
not \( (a + b) \cdot c \), there is an order to read operators in:
- \( \Leftrightarrow \)
- \( \Rightarrow \)
- \( \land \), \( \lor \), \( \oplus \)
- Other mathematical operators such as \( = \), \( \neq \), \( + \), \( \cdot \) etc. in their own order
- \( \lnot \)