Truth table

Lore & Background

A truth table is a mathematical table used in logic, particularly in Boolean algebra, Boolean functions, and propositional calculus. It displays the functional values of logical expressions for every combination of values taken by their logical variables. The table includes one column for each input variable and a final column showing the result of the logical operation. Each row represents a possible configuration of the input variables and the corresponding operation result. A proposition's truth table is a graphical representation of its truth function, which encodes the same information in a form often more useful for mathematical purposes.

The invention and popularization of the truth table is generally credited to Ludwig Wittgenstein, who presented it in his *Tractatus Logico-Philosophicus*, completed in 1918 and published in 1921. Emil Leon Post independently proposed a similar system in 1921. However, research by Irving Anellis indicates that C.S. Peirce appears to be the earliest logician to devise a truth table matrix, in 1883. In 1997, John Shosky discovered truth table matrices on the verso of a page from Bertrand Russell's 1912 lecture transcript, including a matrix for negation by Russell and one for material implication in Wittgenstein's hand. An unpublished Peirce manuscript from 1893 contains a truth table matrix equivalent to that material implication matrix, and an earlier Peirce manuscript from 1883–84 includes an example of an indirect truth table for the conditional.

Truth tables can prove logical equivalences. In digital logic, they specify the function of hardware look-up tables (LUTs); for an n-input LUT, the truth table has 2^n values. These values can be encoded as integer bits in electronic design automation software, with the output obtained by calculating a bit index from the input values. While straightforward, truth tables grow exponentially with the number of inputs, making them unsuitable for functions with many inputs; more memory-efficient representations include text equations and binary decision diagrams. A condensed form of truth table for binary operators uses row and column headings for operands and table cells for results, which is useful for commutative operations and multi-valued logic, and provides a recognizable shape for the distribution of values.

Reader's Guide

Truth tables are a simple and straightforward way to encode Boolean functions, with one column for each input variable and a final column for the result. Each row represents a possible configuration of inputs. They can be used to prove logical equivalences, such as that p → q is equivalent to ¬p ∨ q. In digital logic, truth tables specify the function of hardware look-up tables (LUTs); for an n-input LUT, the table has 2^n rows. Truth table values can be encoded as integer bits in electronic design automation software. However, due to exponential growth in size as inputs increase, truth tables are not suitable for functions with many inputs; other representations like text equations and binary decision diagrams are more memory efficient. In digital electronics, truth tables can reduce basic Boolean operations to simple input-output correlations, as in half-adders and full-adders.