Truth table

A way to organize the results of combining logical Boolean variables for a single Boolean operation.

Since there are 2²=4 possible combinations of two Boolean variables, there are 2⁴ = 16 possible Boolean operations on two variables (If we had three variables, there would be 2³=8 possible outcomes and thus 2⁸=256 possible operations). If we combine all of the possible truth tables into a single table, we can order the truth tables by the number that results from interpreting the four results as a binary representation:

P = 0 1 0 1
Q = 0 0 1 1  Dec Hex    Interpretation
    -------  --- ---    ----------------
    0 0 0 0    0   0    Zero
    0 0 0 1    1   1    P AND Q
    0 0 1 0    2   2    Q AND (NOT P)
    0 0 1 1    3   3    Q
    0 1 0 0    4   4    P AND (NOT Q)
    0 1 0 1    5   5    P
    0 1 1 0    6   6    (P != Q) aka (P XOR Q)
    0 1 1 1    7   7    P OR Q
    1 0 0 0    8   8    NOT (P OR Q)
    1 0 0 1    9   9    (P = Q) aka (P iff Q)
    1 0 1 0   10   A    NOT P
    1 0 1 1   11   B    P -> Q aka (P implies Q)
    1 1 0 0   12   C    NOT Q
    1 1 0 1   13   D    P <- Q aka (P if Q)
    1 1 1 0   14   E    NOT (P AND Q)
    1 1 1 1   15   F    One

Each four-digit binary representation can also be interpreted as a hexadecimal digit; This will be familiar to old-time GUI (Windows and X) programmers as the list of raster operators when performing something like a bitblt.

The following is a truth table for two boolean arguments. Any larger truth tables would be quite difficult to node

A  B |1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
_____|_____________________________________________________
T  T |T  T  T  T  T  T  T  T  F  F  F  F  F  F  F  F
T  F |T  T  T  T  F  F  F  F  T  T  T  T  F  F  F  F
F  T |T  T  F  F  T  T  F  F  T  T  F  F  T  T  F  F
F  F |T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F

legend:
1.  true
2.  or  ( V )
3.  consequence ( <= )
5.  implication ( => )
7.  equality ( = )
8.  and ( ^ )
9.  nand ¬(A ^ B)
10. not equal ( != ; or a = with a slash through it)
15. nor ¬(A V B)
16. false

¬ - not. Prefixed to nand and nor. I.E. True nand False is written as ¬(True ^ False)

If you have a boolean equation of True OR False, you can use the table find that the equation equals True. For larger equations, such as (True ^ ¬(False OR False)), resolve what's in the innermost parentheses first (in this case, False nor False is True), then work outwards. This example resolves to (True ^ True) or True.

Actually, larger (more-than-two-variable) truth tables are pretty easy to make, but as the math guru who taught this to me said, it will make your arms hurt a bit. Here's how to make larger truth tables:

A truth table will always have 2^n lines (ie, 2^n different combinations), where n is the number of variables. Thus 2-variable truth table will have 4 lines, 3-variable table will have 8 lines, 4-variable table will have 16 lines and so on. I've made a 6-variable table (64 lines) once, on paper - that was pretty boring. =)

How to fill the columns? First column will have half of the table True and other half False; Second will have one-fourth (half of previous) True, False, True, False, Third will have one-eighth, and so on. Final column will thus look like "T,F,T,F,T,F..." then.

Example:

 A B C   Op...
 ---------------
 T T T
 T T F
 T F T
 T F F
 F T T
 F T F
 F F T
 F F F

For three variables, table will have 8 lines; Half of it is 4, so for A there's 4 Trues and four Falses, For B there's 8/4=2 T's, then 2 F's, and so on.

An explanation at a more basic level:

In Boolean logic, we are interested in how to make compound statements out of primitive statements and a few logical operators.

To do this consistently, we need rules about what these operators do.

In Boolean logic, each statement evaluates to either T or F, representing True or False. Because each operator has one or two operands, which may only have the values T or F, we can define our logical operators by means of truth tables.

Consider two statements:

• (A) it is dark

and

• (B) we're wearing sunglasses

Now consider the compound statements:

• (C) A and B (= 'it is dark and we're wearing sunglasses')

• (D) A or B (= 'it is dark or we're wearing sunglasses')

Let's draw a little table:

A  B      C (= A and B)
-------+-------------
F  F   |     F          
F  T   |     F          
T  F   |     F          
T  T   |     T

This tells us that C ( 'it is dark and we're wearing sunglasses') is only true when both A ('it is dark') and B ('we're wearing sunglasses') are true. If one of them is false, then C is false.

The table is all we need to define 'and' for use in our algebra.

In the case of D:

A  B      D (= A or B)
-------+-------------
F  F   |     F          
F  T   |     T          
T  F   |     T          
T  T   |     T

D ('it is dark or we are wearing sunglasses') is only false when both A and B are false. We only need one out of A and B to be true in order for D to be true. Thus, we can precisely define how we want 'or'to behave in our algebra.

the table for the not operator is very simple, because it only has one operand:

A    not A
---+------
F  |  T
T  |  F

This just says that if A is true, then 'not A' is false, and the converse.

These tables are normally called truth tables. (Or sometimes, apparently, logic tables.)

I seem to remember reading somewhere that they were invented by Ludwig Wittgenstein.

Ah, I see Gritchka has something to impart on this. Thanks Gritchka!

Wittgenstein introduced them in the Tractatus Logico-Philosophicus (1921); in proposition 4.31 to be exact.

4.26    If all true elementary propositions are given, the result is a complete description of the world. The world is completely described by giving all elementary propositions, and adding which of them are true and which false.

4.27    For n states of affairs, there are K_n = Σ(from ν = 0 to n) (n above ν) possibilities of existence and non-existence.

Of these states of affairs any combination can exist and the remainder not exist.

4.28    There correspond to these combinations the same number of possibilities of truth -- and falsity -- for n elementary propositions.

4.3    Truth-possibilities of elementary propositions mean possibilities of existence and non-existence of states of affairs.

4.31    We can represent truth-possibilities by schemata of the following kind ('T' means 'true', 'F' means 'false'; the rows of 'T's' and 'F's' under the row of elementary propositions symbolize their truth-possibilities in a way that can easily be understood):

    p  q  r
    -  -  -
    T  T  T       p  q
    F  T  T       -  -       p
    T  F  T       T  T       -
    T  T  F ,     F  T ,     T
    F  F  T       T  F       F
    F  T  F       F  F
    T  F  F
    F  F  F

And thereafter with a number of remarks in a similar vein. Clearly he is working this out as a new idea. In his later work (foremost in Philosophical Investigations) he repudiated this atomistic picture of the world being composed of all the things that were true about it, but his legacy of the truth table remains useful.

Truth tables, also known as logic tables are an important part of symbolic logic, also known as propositional logic or sentential logic. Propositional logic is mainly concerned with finding the "truth value" of statements, in order to assess the vailidity of arguments.

In propositional logic there are a few operational symbols:
~ NOT (negation)
& AND (conjunction)
v OR (disjunction)
V exclusive OR
→ IF....THEN (implication)
↔ IF AND ONLY IF (biconditional)
that are used to show the relationships of sentences. Variables (A,B,C,P,Q,R...) are used to represent the sentence.

Example:
A - Max is a dog.
B - Max is hungry.
so the sentence Max is a dog and hungry. would be represented as A & B.

On to truth tables. On the left side of the truth table is all the possible true-false combinations for the variables we are using. For one variable there are two possible truth combinations : T (true) or F (false). For two variables there are 4 combinations, for 3 variables there are 8 combinations and so on. On the right side of the table there is the truth value for the statement.

~ - Negation

A | ~A
--------
T | F
F | T

The negation serves simply to reverse the truth values. True becomes false, false becomes true.

& - Conjuction:

A B | A&B
------------
T T |  T
T F |  F
F T |  F
F F |  F 

This truth table tells us that the conjunction of A and B is only true when both A and B are true.

v - Disjunction

A B | A v B
------------
T T |   T
T F |   T
F T |   T
F F |   F

This truth table says that as long as one of the variables is true, the disjunction is true (either A or B is true). It was argued by some logiticians that the conversational implication of saying either-or is that we do not know which one is true, just that one of them is. If we knew A and B were both true, we would say A&B not A v B. Because of this, the special exclusive disjunction (represented by the symbol V (capital v) should be used. The truth table for V is below:

V - Exclusive Disjunction

A B | A V B
------------
T T |   F
T F |   T
F T |   T
F F |   F

This truth table says that the statement is true only when A or B have different truth values. When A and B are both true or both false, the sentence is false.

→ - Implication, If-Then

A B|  A→B
------------
T T |   T
T F |   F
F T |   T  
F F |   T 

This is often the hardest truth table to grasp. For most of the other operational symbols, their truth tables very closely resemble or match what their engligh translations mean. The If-Then table is not so clear. It says that if A is true and A→B is true, then B is true. Or, if we look at just the first two lines, a true statement cannot imply a false statment. If it does, the whole thing is false. The last two lines on the table say that if we start with a false statment or premise, it doesn't matter what the second part is, the whole thing is true (ie: If I gave birth to puppies than you would be their father. is true, because I am never going to give birth to puppies. The statement I gave birth to puppies. is always going to be false.)

↔ - Biconditional

A B |  A↔B
------------
T T |   T 
T F |   F 
F T |   F
F F |   T 

The biconditional states that when both sentences have the same truth value, the statment is true. So, when both A and B are true, or when they are both false, the biconditional true. (this truth table is the same as for ~(A V B), the negation of the exclusive or).

An example of how to work a more complex truth table:

Either Sam and Mark go running or Pat goes running.
S - Sam goes running
M - Mark goes running
P - Pat goes running

This gives us the formula (S&M) v P. Within this, there is a sub-formula S&M. The operational symbol & applies only to S and M, not to the whole formula.

S M P | (S&M) v P
----------------------
T T T |
T T F |
T F T |
T F F |
F T T |
F T F |
F F T |
F F F |

Here is our truth table for this sentence. To start, we will have to assess the truth value of the sub-formula S&M. To do this, we just look at the truth values for S and M, we are ignoring P for now. We will record the truth value for each line under the & symbol. By placing it there, we know that that column in our table applies to S&M. Here is the table with that column completed:

S M P | (S&M) v P
----------------------
T T T |   T
T T F |   T
T F T |   F
T F F |   F
F T T |   F
F T F |   F
F F T |   F
F F F |   F

Now that we have the truth value of our sub-formula we can find the truth value for the whole sentence. If there were more sub-formulas you would continue finding thier truth values and in essence work "outward" until you had the truth value for the whole sentence. For the next step we are going to treat S&M as a single variable. We are going to nickname S&M - Q for simplicity. Now we can asess the truth value of Q v P. The table for Q v P would look like:

Q P | Q v P
------------------
T T |   T
T F |   T
F T |   T
F F |   F
F T |   T
F F |   F
F T |   T
F F |   F

The column for Q (on the left) is the same as the column for S&M on the above truth table. The column for P in this table is also the same as the column for P above.

It is not nessisary to make an entirely new truth table for this step. I only did so for clarity. It is preferable to write this final column on the original table, placing it under the disjunction (v) operator like so:

S M P | (S&M) v P
----------------------
T T T |   T   T
T T F |   T   T
T F T |   F   T
T F F |   F   F
F T T |   F   T
F T F |   F   F
F F T |   F   T
F F F |   F   F

The far right column under v is the truth value for the entire statement given the contions of truth or falsehood given on the left side of the table. We can see that this table is accurate just by thinking about what it represents. For example, on line 4, Sam runs, but Mark doesn't and neither does Pat. So the statement Either Sam and Mark go running or Pat goes running. is false in this case, and that is what the truth table tells us. We can think about all 8 lines this way, keeping in mind that we are not using the exclusive or (V) - even if everyone goes running the statment is still true.

It should be noted that there are many other variations on how to write out a truth/logic table. I prefer this method because involves the least amount of writing, and I think it is fairly straight forward. The left-right division of variables and formulas is not nessisary, but it makes it easier for other people who are looking at your work to read.