THE TRUTH, THE WHOLE TRUTH AND NOTHING BUT THE TRUTH Part 2 of 3
2: Binary and Truth Tables (there are 3 subsections A B and C)
In our previous article, we discussed the basics of propositional logic and the representation of propositions and connectives as variables and symbols respectively. That was the first step on our journey to understanding machines better.
This article will take the next step, which is to translate that knowledge of logic to a machine’s interpretation. We will first look at the way machine parts communicate, then look at truth tables, which are a way to show the truth and falsehood of general propositions in many circumstances.
Ready? Then we shall begin…
Section A: Binary
How do computer parts communicate? In what form is the message sent?
For a machine, everything has 2 states: On or Off, Working or Malfunctioning, Yes or No are some examples of this.
Their language reflects this idea of 2 states in that it only has 2 values- 0 and 1.
This is called binary.
You can actually convert our base 10 number system to a binary one by representing the number as a sum of powers of two. I highly recommend working with it if you’d like the challenge.
For the purposes of logic, we have that 1 represents True and 0 represents False.
This is very important as an illustration of what a proposition is: A statement that can be either True or False, but never both. True and False are opposing states and as such are shown by different numbers.
So we’ve got our answer- Machines understand logic in terms of the binary states or values 0 (False) and 1 (True).
We shall use this in our look at Truth Tables.
Section B: Fundamental Truth Tables
There are few more powerful tools than the truth table. As mentioned in the introduction, they are a way to show the truth and falsehood of a general compound proposition in all possible circumstances. We can know what the overall truth state of the compound proposition is. They are useful for proving laws and equivalencies, as we shall show in the next article
We will look at the fundamental ones first, as they illustrate the effect of the connectives we met in the previous article: NOT, AND OR and IMPLICATION.
First though, how many rows does our table have?
We know that each proposition/ variable can only take the states 1/True and 0/False. If there are n propositions/ variables in a compound proposition, we know that there are 2^n ways to combine the states and so 2^n situations to explore.
There are then 2^n rows to a truth table for n variables.
You may wish to have proof of this notion for small values of n.
- Looking at n=1, 1 variable has the 2 states 0 and 1, which is backed up by the fact that 2¹=2.
- Looking at n=2, we’ve seen that 2 variables have the possibilities 11 (both true), 10 01 (one true, the other false) and 00 (both false). There are 4 combinations, which is backed up by the fact that 2²=4
- For n=3, we have the states 111 (all three true) 110 101 011 (one false, two true) 100 010 001 (one true, two false) 000 (all three false). There are 8 combinations, which is backed up by the fact that 2³=8.
I hope this is enough to show you that a compound proposition with n variables has 2^n combinations of states and so the truth table needs 2^n rows.
How many columns will the table have?
Well, we need one for each variable (which are on the left), then another for the effect of each connective in turn (which are on the right). This will be more relevant when we look (later in this article) at constructing truth tables in general. We are learning the fundamental ones first to get a feel for how it works and to formalise some concepts we have already covered.
In our look at the fundamental tables, we shall mainly look at the cases n=2 and n=3, but the behaviour is generalisable to any value of n.
Negation/NOT
You should recall that the NOT connective changes the original truth state so that a 0 becomes a 1 (and vice versa). The negation of a negation is the original statement. This is shown in the truth table below
P ~P ~~P
1 0 1
0 1 0
Conjunction/AND
You should recall that the only time when the output proposition is true is when all the inputs are true.
The truth table shows this well in the 2 variable case….
P Q P ∧ Q
1 1 1
1 0 0
0 1 0
0 0 0
….and the 3 variable case….
P Q R P ∧ Q ∧ R
1 1 1 1
0 1 1 0
1 0 1 0
0 0 1 0
1 1 0 0
0 1 0 0
1 0 0 0
0 0 0 0
….which is of course generalisable to any number of variables.
Disjunction/OR
You should recall that the only time when the output proposition is false is when all the inputs are false.
The truth table shows this well in the 2 variable case….
P Q P ∨ Q
1 1 1
1 0 1
0 1 1
0 0 0
….and the 3 variable case….
P Q R P ∨ Q ∨ R
1 1 1 1
0 1 1 1
1 0 1 1
0 0 1 1
1 1 0 1
0 1 0 1
1 0 0 1
0 0 0 0
….which is again generalisable to any number of variables.
Implication
ONE-WAY IMPLICATION
The truth of an implication is best shown by a truth table.
P Q P → Q
1 1 1
1 0 0
0 1 1
0 0 1
Essentially, the statement ‘If P, then Q’ (P implies Q) is true when either Q is true or both are false. Essentially, the implication is only false where P is true but Q is false. This situation severs the connection between the propositions. The most interesting part about this is that Q can be true when P is false. You’d think this violated the connection too, but not in Boolean logic!
BOTH-WAYS IMPLICATION
We’ve already explored how a both-ways implication represents two simultaneous one-way implications. We shall use this idea to build up a table for this type of implication.
The table below shows the truth of the one-way implications ‘If P, then Q’ and ‘If Q, then P’ in the same table.
Note that ‘If P, then Q’ is false where P is true but Q is false, which leads to the result that ‘If Q, then P’ is false where Q is true but P is false.
P Q P implies Q Q implies P
1 1 1 1
1 0 0 1
0 1 1 0
0 0 1 1
We can say the both-ways implication is true when these two implications are both true. From the table, this is where both P and Q are true or both P and Q are false.
This is shown in the following table.
P Q P ↔ Q
1 1 1
1 0 0
0 1 0
0 0 1
Extra results- TAUTOLOGY and CONTRADICTION
A tautology is something that is always true. It is represented by the variable 1 or TRUE for the reason that it’s truth value is always 1.
A contradiction is something that is always false. It is represented by the variable 0 or FALSE for the reason that it’s truth value is always 0.
We shall see 6 general results involving tautologies and contradictions.
1)P and 1 = P
This shows that P and a tautology are only both true when P is true.
2)P or 1 = 1
This shows that, as one of P or the tautology is always true, the output is always true and so it’s another tautology.
3)P and 0 = 0
This shows that, as P and the contradiction are never both true, the output is always false and so it’s another contradiction.
4)P or 0 = P
This shows that the only time that P or 0 is true is when P is true.
5)P and ~P = 0
P and it’s negation can never both be true. P and ~P is always false and so it’s a contradiction.
6)P or ~P = 1
Where P is false, it’s negation will be true. One of P or it’s negation will therefore always be true. P or ~P is always true and so it’s a tautology.
These 6 results are shown in the following tables.
P AND TRUE= P
P TRUE P ∧ TRUE
1 1 1
0 1 0
P OR TRUE= TRUE (tautology)
P TRUE P ∨ TRUE
1 1 1
0 1 1
P AND FALSE= FALSE (contradiction)
P FALSE P ∧ FALSE
1 0 0
0 0 0
P OR FALSE= P
P FALSE P ∨ FALSE
1 0 1
0 0 0
P OR Not P = TRUE (tautology)
P ~P P ∧ ~ P
1 0 0
0 1 0
P AND Not P = FALSE (contradiction)
P ~P P ∨ ~ P
1 0 1
0 1 1
Section C: Working with Truth Tables
In the last section, we looked at the fundamental truth tables for operators like NOT, AND, OR and IMPLICATION. You may see any number of operators combined into an expression. We will look at a few examples. The basics of each operator are just the same as before.
Soon after learning how all the basic operations worked, we were taught the order of operations (known by the acronyms BIDMAS or PEMDAS). This helped us to handle multi-step calculations in the right way.
Similarly, we are now going to need to know the order of priority of the different logical connectives. This is the order in which they are evaluated, and we build up the layers of our truth table in that order.
First priority- brackets. Anything within brackets should be evaluated first. If there are many layers of brackets then work outwards from the innermost set of brackets.
Within brackets, after brackets, or if there are no brackets, the following is the order of priority in most cases:
1)NOT
2)AND
3)OR
4)One-Way Implication
5)Both-Ways Implication
Examples of tables with many stages of evaluation
- A v ~B
You do the NOT first then the OR
There are 2 propositions in the composite so there are 2 initial columns and 4 rows.
The composite is only false when A is false and B is true (row 3)
A B notB A v ~B
1 1 0 1
1 0 1 1
0 1 0 0
0 0 1 1
2. P -> ~Q v R
You do the NOT, then the OR, then the one way implication
There are 3 propositions in the composite, so you need 3 initial columns and 8 rows
The composite is only false when R is the only false proposition (row 2)
P Q R notQ notQ or R P -> ~Q v R
1 1 1 0 1 1
1 1 0 0 0 0
1 0 1 1 1 1
1 0 0 1 1 1
0 1 1 0 1 1
0 1 0 0 0 1
0 0 1 1 1 1
0 0 0 1 1 1
3. ~A v B -> ~C
On the left, you do the NOT of A followed by the OR with B. On the right you can then do the NOT of C. The final step is the one-way implication.
There are 3 propositions in the composite so we need 3 initial columns and 8 rows.
The composite is false if all 3 are true (row 1) just B and C are true (row 5) or just C is true (row 7)
A B C notA notA or B notC ~A v B -> ~C
1 1 1 0 1 0 0
1 1 0 0 1 1 1
1 0 1 0 0 0 1
1 0 0 0 0 1 1
0 1 1 1 1 0 0
0 1 0 1 1 1 1
0 0 1 1 1 0 0
0 0 0 1 1 1 1
4. (A ^ ~B) -> (C v D)
We first do the NOT of B, then we can do the AND with A in the bracket on the left, followed by the OR of C with D on the right. The final step is the one-way implication.
There are 4 propositions within the composite so we need 4 initial columns and 16 rows.
The composite is only false when A is the only true proposition (row 8)
A B C D notB A and notB C or D (A ^ ~B) -> (C v D)
1 1 1 1 0 0 1 1
1 1 1 0 0 0 1 1
1 1 0 1 0 0 1 1
1 1 0 0 0 0 0 1
1 0 1 1 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 1 1 1 1 1
1 0 0 0 1 1 0 0
0 1 1 1 0 0 1 1
0 1 1 0 0 0 1 1
0 1 0 1 0 0 1 1
0 1 0 0 0 0 0 1
0 0 1 1 1 0 1 1
0 0 1 0 1 0 1 1
0 0 0 1 1 0 1 1
0 0 0 0 1 0 0 1
5. P∨Q∧~R⇒S should be done as (P∨(Q∧(~R)))⇒S according to the conventions.
You evaluate each bracket layer in order, using one logical operator at a time. We do the NOT, then AND, then OR, then the one-way implication.
We have 4 propositions in our composite, so we need 4 initial columns and 16 rows. When P is true, the truth of the composite depends on the truth of S (first 8 rows). When P is false, the composite is only false when Q is the only true proposition (row 11)
P Q R S notR Q∧notR P∨(Q∧(notR)) (P∨(Q∧(~R)))⇒S
1 1 1 1 0 0 1 1
1 1 1 0 0 0 1 0
1 1 0 1 1 1 1 1
1 1 0 0 1 1 1 0
1 0 1 1 0 0 1 1
1 0 1 0 0 0 1 0
1 0 0 1 1 0 1 1
1 0 0 0 1 0 1 0
0 1 1 1 0 0 0 1
0 1 1 0 0 0 0 1
0 1 0 1 1 1 1 1
0 1 0 0 1 1 1 0
0 0 1 1 0 0 0 1
0 0 1 0 0 0 0 1
0 0 0 1 1 0 0 1
0 0 0 0 1 0 0 1
6. ~(Q∧R)VP⇔Q⇒R is evaluated as ((~(Q∧R))VP)⇔(Q⇒R) according to the conventions, and you work from the inner brackets outwards as usual.
We do the AND in brackets, then the NOT, then the OR, then the one-way implication, then the both-ways implication.
There are 3 propositions within this composite so we need 3 initial columns and 8 rows. When P is true, the truth of the composite depends on that of R (first 4 rows).When P is false, the composite is only false where P is the only false proposition (row 5).
P Q R Q∧R not(Q∧R) (not(Q∧R))VP Q⇒R ((~(Q∧R))VP)⇔(Q⇒R)
1 1 1 1 0 1 1 1
1 1 0 0 1 1 0 0
1 0 1 0 1 1 1 1
1 0 0 0 1 1 0 0
0 1 1 1 0 0 1 0
0 1 0 0 1 1 1 1
0 0 1 0 1 1 1 1
0 0 0 0 1 1 1 1
7. ~(P∧~Q∧R)⇔PV(Q⇒R) V~R should be evaluated as ~(P∧(~Q)∧R)⇔(PV(Q⇒R) V(~R)) according to the conventions. You should go from the inner brackets outwards and work with one operator at a time.
You start with the NOT of Q and the NOT of R then do the one-way implication for Q and R. On the left, you proceed with the AND with 3 variables in the bracket, then another NOT. On the right, you proceed with the 3-variable OR. Once you’ve done these, the final step is the both-ways implication.
There are 3 propositions within the composite so we need 3 initial columns and 8 rows.
The only situation where the composite is false is where Q is the only false proposition (row 3).
First 8columns: P Q R notQ notR Q⇒R P∧(notQ)∧R not(P∧(notQ)∧R) Columns 9 and 10: PV(Q⇒R)V(notR) ~(P∧(~Q)∧R)⇔(PV(Q⇒R)V(~R))
1 1 1 0 0 1 0 1 1 1
1 1 0 0 1 0 0 1 1 1
1 0 1 1 0 1 1 0 1 0
1 0 0 1 1 1 0 1 1 1
0 1 1 0 0 1 0 1 1 1
0 1 0 0 1 0 0 1 1 1
0 0 1 1 0 1 0 1 1 1
0 0 0 1 1 1 0 1 1 1
For all truth tables see https://docs.google.com/spreadsheets/d/1aIB3p3G88xTgNdqcZ4QRerAMW32me57753lwUzuoUTs/edit?usp=drivesdk