Using truth tables, it becomes possible to prove that a logical expression is always true by enumerating all possibilities and showing that each possibility is always true.

What does it mean for something to be true?

What does it mean to say that something is "true"?

People are at the human/opinion level and, to some extent, use logic truth and/or reality truth.

Many people have difficulty distinguishing between opinion based in reality and/or logic and opinion not based on reality and/or logic.

Logic tends not to work with people who do not think logically. These areas can overlap but the distinction is, nonetheless, useful. All humans work at the level of opinion, but more or less connect that opinion with reality truth and/or logical truth.

Logical truth: symbol manipulation involving integer values, which is exact but may involve paradoxes. This includes coded information, programming languages, digital computers, etc.

Mathematics is concerned with logical without any connection to reality. (Mathematicians such as Hilbert made this decision in the early 1900's).

In the 1920's, Hilbert (1928) proposed finding a consistent mathematical system that will allow all possible truths
to be decided. This would allow the automatic, or mechanical, proving of all possible truths.

Hilbert invented/discovered the Hilbert curve, a monster curve that was not fully understood until the introduction of fractals a half-century later. Logical truth involves mathematical and computer/information logic using two discrete logic values (e.g., true and false, 1 and 0) and symbol manipulation using rules to determine which claims are "true" or "false".

Computer logic and programming involves logical truth.

Hilbert and his problems and the separation of math with reality and philosophy.

Note that generalizations of logical truth can involve paradoxes, incompleteness, undecidability, etc.

Reality truth: approximations using all math values, probability and statistics, etc., which may use logical truth. Traditional science involves reality truth.

Reality truth involves what exactly is real, or reality. Reality truth involves probability, statistics, approximations, unknowns, etc. The traditional scientific method involves reality truth. So does, to some extent, the traditional legal process.

Opinion truth: all other types of truth, which may or may not use logical and reality truth, but need not do so.

Human truth can be whatever one or more humans decide it is. Thus, there are no precise rules for defining human truth other than it is not necessarily logical truth or statistical truth.

In a programming languages course, one is primarily concerned with logical truth. There may or may not be any connection of logical truth with reality truth and/or human truth.

Thus, a Boolean condition that is either true or false may or may have no connection to "reality".

An extended truth table for a logical expression enumerates all of the possible results and intermediate results of the evaluation of a logical expression in a convenient format.

The method is credited to Quine Quine, W. (1950). Methods of logic, 4th ed. Cambridge, MA: Harvard University Press.. by Church Church, A. (1956). Introduction to mathematical logic, revised and enlarged ed. Princeton, NJ: Princeton University Press., p. 95., but does not seem to be in widespread use, or even to have a formal name.

For lack of a formal name, they will be called extended truth tables. The method is now presented by way of an example.

Consider the following (fully parenthesized) logical expression that is given.

This expression contains the following logical variables.

The logical variables here are X and Y.

Using the logical variables X and Y, start the above truth table structure with the variable list on the left, the expression containing the variables on the right, and the possible values for the logical variables in the left-bottom part of the table. These values should be in binary order.

Now add the parentheses below each of the parentheses in the original expression.

Now, take the logical variable values in the bottom left and put them on the bottom right below each respective logical variable.

Now work up the levels of parentheses from the innermost to the outermost.

The last column filled in is the value of the expression when the logical variables have the values in that row.

This table might be better seen as the above logical expression tree. Computer scientists usually draw tree structures with the root at the top.

Data flowing from top to bottom are called inherited attributes.

The parentheses disappear in the tree, since parentheses are used to specify precedence of evaluation order and that is specified by the tree structure. Technically, this is the difference between abstract syntax (i.e., without parentheses) and concrete syntax (i.e., with parentheses)

To evaluate a logical expression, one must work up the tree from the leaves and evaluate each subtree as all of its arguments become known.

Whenever you work from innermost to outermost parentheses, you are going up the tree from the leaves to the root. The root contains the final result.

Data flowing from bottom to top are called synthesized attributes.

If the overall result column were all true (i.e., 1), then the logical expression would be called a tautology and the truth table would represent a proof that, for all possible logical values of X and Y, the logical expression is true.

In this above case, however, the logical expression is true if X and Y have the same logical value.

A new logical operation, the logical equivalence of logical variables X and Y, can be defined as follows.

The result column, under the "=", is the same as the result column for the more complicated logical expression above (under the "|").

Abstracting in this way means that a more concise notation can be used while fundamental properties of logic need only be shown for the fundamental operations (e.g., via a structural induction).

Truth tables have many practical applications, even though truth tables using exhaustive enumeration by hand are impractical for more than just a few variables. For example, if there are 12 logical variables, there will be 4096 lines to the truth table. In general, if there are n logical variables, there will be 2ⁿ lines to the truth table.

A few practical applications of truth tables will now be covered.

The main use of truth tables, however, is that useful results can be proven for smaller truth tables and then the results can be used. Consider the following logical expression that uses the abstracted "=" operation developed above.

What is the value 1? Remember that the beginning assumption is that true is always true and false is always false, and true and false are different, the following truth table can be developed.

This logical expression has the same result as the following truth table.

Instead of just observing that the two expressions are equal, let us do the full proof.

The final column has a 1 for all possible values of the logical variables. Thus, it is a tautology.

Thus, the logical expression

can be simplified to the logical expression

In most programming languages, this means that, say, the Java logical expression in a conditional if statement as

can be simplified to the following.

In general, removing unnecessary code from a program is a win-win situation both for the human programmer and for machine efficiency. Some related logical expressions are the following.

Try simplifying the following logical expressions in Java.

Here is a logical truth table related to Bayes rule. The rule can be seen visually with a Venn diagram (omitted).