View source for Truth table

{{Short description|Mathematical table used in logic}}
{{Logical connectives sidebar}}
A '''truth table''' is a [[mathematical table]] used in [[logic]]—specifically in connection with [[Boolean algebra (logic)|Boolean algebra]], [[Boolean function]]s, and [[propositional calculus]]—which sets out the functional values of logical [[expression (mathematics)|expressions]] on each of their functional arguments, that is, for each [[valuation (logic)|combination of values taken by their logical variables]].<ref>{{harvnb|Enderton|2001}}</ref> In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, [[Validity (logic)|logically valid]].

A truth table has one column for each input variable (for example, A and B), and one final column showing all of the possible results of the logical operation that the table represents (for example, [[#Exclusive disjunction|A]] [[XOR]] [[#Exclusive disjunction|B]]). Each row of the truth table contains one possible configuration of the input variables (for instance, A=true, B=false), and the result of the operation for those values.

A proposition's truth table is a graphical representation of its [[truth function]].  The truth function can be more useful for mathematical purposes, although the same information is encoded in both.

[[Ludwig Wittgenstein]] is generally credited with inventing and popularizing the truth table in his ''[[Tractatus Logico-Philosophicus]]'', which was completed in 1918 and published in 1921.<ref>{{cite journal | author-link = Georg Henrik von Wright |first=Georg Henrik |last=von Wright  | title = Ludwig Wittgenstein, A Biographical Sketch | journal = The Philosophical Review | volume = 64 | issue = 4 | year = 1955 | pages = 527–545 (p. 532, note 9) | jstor = 2182631 | doi=10.2307/2182631}}</ref> Such a system was also independently proposed in 1921 by [[Emil Leon Post]].<ref>{{cite journal | author-link=Emil Post |first=Emil |last=Post |title=Introduction to a general theory of elementary propositions|journal=American Journal of Mathematics|date=July 1921|volume=43|issue=3|pages=163–185|jstor= 2370324|doi=10.2307/2370324|hdl=2027/uiuo.ark:/13960/t9j450f7q|hdl-access=free}}</ref>

==History==
[[Irving Anellis]]'s research shows that [[C.S. Peirce]] appears to be the earliest logician (in 1883) to devise a truth table matrix.<ref name="Peirce">{{cite journal|last1=Anellis|first1=Irving H.|authorlink=Irving Anellis|title=Peirce's Truth-functional Analysis and the Origin of the Truth Table|journal=History and Philosophy of Logic|date=2012|volume=33|pages=87–97|doi=10.1080/01445340.2011.621702|s2cid=170654885 }}</ref>

From the summary of Anellis's paper:<ref name="Peirce"/>
<blockquote> In 1997, John Shosky discovered, on the [[verso]] of a page of the typed transcript of [[Bertrand Russell]]'s 1912 lecture on "The Philosophy of Logical Atomism" truth table matrices. The matrix for negation is Russell's, alongside of which is the matrix for material implication in the hand of Ludwig Wittgenstein. It is shown that an unpublished manuscript identified as composed by Peirce in 1893 includes a truth table matrix that is equivalent to the matrix for material implication discovered by John Shosky. An unpublished manuscript by Peirce identified as having been composed in 1883–84 in connection with the composition of Peirce's "On the Algebra of Logic: A Contribution to the Philosophy of Notation" that appeared in the ''[[American Journal of Mathematics]]'' in 1885 includes an example of an indirect truth table for the conditional. </blockquote>

==Applications==
Truth tables can be used to prove many other [[logical equivalence]]s.  For example, consider the following truth table:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|+ <math>(p\rightarrow q)\equiv(\neg p\vee q)</math>
|- style="background:paleturquoise"
! style="width:12%" | <math>p</math>
! style="width:12%" | <math>q</math>
! style="width:12%" | <math>\neg p</math>
! style="width:12%" | <math>\neg p\vee q</math>
! style="width:12%" | <math>p\rightarrow q</math>
|-
| {{success|T}} || {{success|T}} || {{failure|F}} || {{success|T}} || {{success|T}}
|-
| {{success|T}} || {{failure|F}} || {{failure|F}} || {{failure|F}} || {{failure|F}}
|-
| {{failure|F}} || {{success|T}} || {{success|T}} || {{success|T}} || {{success|T}}
|-
| {{failure|F}} || {{failure|F}} || {{success|T}} || {{success|T}} || {{success|T}}
|}

This demonstrates the fact that <math>p\rightarrow q</math> is [[logically equivalent]] to <math>\neg p\vee q</math>.

===Truth table for logic gates===
Here is a truth table that gives definitions of each of the 6 possible 2-input [[logic gate]] functions of two Boolean variables P and Q:

{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"
|-
! <math>P</math> || <math>Q</math> || <math>P\and Q</math> || <math>P\vee Q</math> || <math>P\uparrow Q</math> || <math>P\downarrow Q</math> || <math>P\nleftrightarrow Q</math> || <math>P\leftrightarrow Q</math>
|-
| {{success|T}} || {{success|T}} || {{success|T}} || {{success|T}} || {{failure|F}} || {{failure|F}} || {{failure|F}} || {{success|T}}
|-
| {{success|T}} || {{failure|F}} || {{failure|F}} || {{success|T}} || {{success|T}} || {{failure|F}} || {{success|T}} || {{failure|F}}
|-
| {{failure|F}} || {{success|T}} || {{failure|F}} || {{success|T}} || {{success|T}} || {{failure|F}} || {{success|T}} || {{failure|F}}
|-
| {{failure|F}} || {{failure|F}} || {{failure|F}} || {{failure|F}} || {{success|T}} || {{success|T}} || {{failure|F}} || {{success|T}}
|-
| colspan="2" |Name<br />(function)
| [[logical conjunction|AND]]<br />(conjunction)
| [[logical disjunction|OR]]<br />(disjunction)
| [[Sheffer stroke|NAND]]<br />(non-conjunction)
| [[Logical NOR|NOR]]<br />(non-disjunction)
| [[Exclusive or|XOR]]<br />(non-equivalence)
| [[Logical biconditional|XNOR]]<br />(equivalence)
|-
| colspan="8" |
''where'' {{color box|9EFF9E|T}} ''means'' '''true''' ''and'' {{color box|FFC7C7|F}} ''means'' '''false'''
|}

===Condensed truth tables for binary operators===
For binary operators, a condensed form of truth table is also used, where the row headings and the column headings specify the operands and the table cells specify the result. For example, [[Boolean logic]] uses this condensed truth table notation:

{|
|-
| style="width:80px;"|
|
{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"
|-
! {{N/A|}}∧
! T
! F
|-
! T
| {{success|T}}
| {{failure|F}}
|-
! F
| {{failure|F}}
| {{failure|F}}
|}
| style="width:80px;"|
|
{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"
|-
! {{N/A|}}∨
! T
! F
|-
! T
| {{success|T}}
| {{success|T}}
|-
! F
| {{success|T}}
| {{failure|F}}
|}
|}

This notation is useful especially if the operations are commutative, although one can additionally specify that the rows are the first operand and the columns are the second operand. This condensed notation is particularly useful in discussing multi-valued extensions of logic, as it significantly cuts down on combinatoric explosion of the number of rows otherwise needed. It also provides for quickly recognizable characteristic "shape" of the distribution of the values in the table which can assist the reader in grasping the rules more quickly.

===Truth tables in digital logic===
Truth tables are also used to specify the function of [[Lookup table#Hardware LUTs|hardware look-up tables (LUTs)]] in [[Digital circuit|digital logic circuitry]]. For an n-input LUT, the truth table will have {{tmath|2^n}} values (or rows in the above tabular format), completely specifying a Boolean function for the LUT. By representing each Boolean value as a [[bit]] in a [[Binary numeral system|binary number]], truth table values can be efficiently encoded as [[integer]] values in [[Electronic design automation|electronic design automation (EDA)]] [[software]]. For example, a 32-bit integer can encode the truth table for a LUT with up to 5 inputs.

When using an integer representation of a truth table, the output value of the LUT can be obtained by calculating a bit index ''k'' based on the input values of the LUT, in which case the LUT's output value is the ''k''th bit of the integer. For example, to evaluate the output value of a LUT given an [[Array data structure|array]] of ''n'' Boolean input values, the bit index of the truth table's output value can be computed as follows: if the ''i''th input is true, let <math>V_i = 1</math>, else let <math>V_i = 0</math>. Then the ''k''th bit of the binary representation of the truth table is the LUT's output value, where 
<math display="block">k = V_0 \times 2^0 + V_1 \times 2^1 + V_2 \times 2^2 + \dots + V_{n-1} \times 2^{n-1}.</math>

Truth tables are a simple and straightforward way to encode Boolean functions, however given the [[exponential growth]] in size as the number of inputs increase, they are not suitable for functions with a large number of inputs. Other representations which are more memory efficient are text equations and [[binary decision diagram]]s.

===Applications of truth tables in digital electronics===
In digital electronics and computer science (fields of applied logic engineering and mathematics), truth tables can be used to reduce basic Boolean operations to simple correlations of inputs to outputs, without the use of [[logic gate]]s or code. For example, a binary addition can be represented with the truth table:

{| class="wikitable" 
|+ Binary addition
|-
! style="width:80px" | {{mvar|A}}
! style="width:80px" | {{mvar|B}}
! style="width:80px" | {{mvar|C}}
! style="width:80px" | {{mvar|R}}
|-
| {{success|T}}
| {{success|T}}
| {{success|T}}
| {{failure|F}}
|-
| {{success|T}}
| {{failure|F}}
| {{failure|F}}
| {{success|T}}
|-
| {{failure|F}}
| {{success|T}}
| {{failure|F}}
| {{success|T}}
|-
| {{failure|F}}
| {{failure|F}}
| {{failure|F}}
| {{failure|F}}
|}

where A is the first operand, B is the second operand, C is the carry digit, and R is the result.

This truth table is read left to right:
* Value pair (A, B) equals value pair (C, R).
* Or for this example, A plus B equal result R, with the Carry C.

This table does not describe the logic operations necessary to implement this operation, rather it simply specifies the function of inputs to output values.

With respect to the result, this example may be arithmetically viewed as modulo 2 binary addition, and as logically equivalent to the exclusive-or (exclusive disjunction) binary logic operation.

In this case it can be used for only very simple inputs and outputs, such as 1s and 0s. However, if the number of types of values one can have on the inputs increases, the size of the truth table will  increase.

For instance, in an addition operation, one needs two operands, A and B. Each can have one of two values, zero or one. The number of combinations of these two values is 2{{times}}2, or four. So the result is four possible outputs of C and R.  If one were to use base 3, the size would increase to 3{{times}}3, or nine possible outputs.

The first "addition" example above is called a half-adder. A full-adder is when the carry from the previous operation is provided as input to the next adder. Thus, a truth table of eight rows would be needed to describe a [[full adder]]'s logic:

<pre>
A B C* | C R
0 0 0  | 0 0
0 1 0  | 0 1
1 0 0  | 0 1
1 1 0  | 1 0
0 0 1  | 0 1
0 1 1  | 1 0
1 0 1  | 1 0
1 1 1  | 1 1

Same as previous, but..
C* = Carry from previous adder
</pre>

== Methods of writing truth tables ==
Regarding the ''guide columns<ref name=":0" />'' to the left of a table, which represent [[propositional variable]]s, different authors have different recommendations about how to fill them in, although this is of no logical significance.<ref name=":13">{{Cite book |last=Howson |first=Colin |title=Logic with trees: an introduction to symbolic logic |date=1997 |publisher=Routledge |isbn=978-0-415-13342-5 |location=London; New York |pages=10}}</ref>

=== Alternating method ===
Lee Archie, a professor at [[Lander University]], recommends this procedure, which is commonly followed in published truth-tables:

# Write out the number of variables (corresponding to the number of statements) in alphabetical order.
# The number of lines needed is 2<sup>''n''</sup> where n is the number of variables. (E. g., with three variables, 2<sup>3</sup> = 8).
# Start in the right-hand column and alternate {{strong|T}}'s and {{strong|F}}'s until you run out of lines.
# Then move left to the next column and alternate pairs of {{strong|T}}'s and {{strong|F}}'s until you run out of lines.
# Then continue to the next left-hand column and double the numbers of {{strong|T}}'s and {{strong|F}}'s until completed.<ref name=":0">{{Cite web |title=How to Construct a Truth Table |url=https://philosophy.lander.edu/logic/table.html |access-date=2024-04-05 |website=philosophy.lander.edu}}</ref>

This method results in truth-tables such as the following table for {{math|''P'' → (''Q'' ∨ ''R'' → (''R'' → ¬''P''))}}, produced by [[Stephen Cole Kleene]]:<ref>{{cite book|title=Mathematical Logic|series=Dover Books on Mathematics|first=Stephen Cole |last=Kleene|author-link=Stephen Cole Kleene|publisher=Courier Corporation|year=2013|isbn=9780486317076|page=11|url=https://books.google.com/books?id=4GzCAgAAQBAJ&pg=PA11}}</ref>
{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! <math>P</math>
! <math>Q</math>
! <math>R</math>
! <math>P\rightarrow (Q\vee R\rightarrow(R\rightarrow \neg P))</math>
|-
| {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Failure|F}}
|-
| {{Success|T}} || {{Success|T}} || {{Failure|F}} || {{Success|T}}
|-
| {{Success|T}} || {{Failure|F}} || {{Success|T}} || {{Failure|F}}
|-
| {{Success|T}} || {{Failure|F}} || {{Failure|F}} || {{Success|T}}
|-
| {{Failure|F}} || {{Success|T}} || {{Success|T}} || {{Success|T}}
|-
| {{Failure|F}} || {{Success|T}} || {{Failure|F}} || {{Success|T}}
|-
| {{Failure|F}} || {{Failure|F}} || {{Success|T}} || {{Success|T}}
|-
| {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Success|T}}
|}

=== Combinatorial method ===
[[Colin Howson]], on the other hand, believes that "it is a good practical rule" to do the following:<blockquote>to start with all Ts, then all the ways (three) two Ts can be combined with one F, then all the ways (three) one T can be combined with two Fs, and then finish with all Fs. If a compound is built up from n distinct sentence letters, its truth table will have 2<sup>n</sup> rows, since there are two ways of assigning T or F to the first letter, and for each of these there will be two ways of assigning T or F to the second, and for each of these there will be two ways of assigning T or F to the third, and so on, giving 2.2.2. …, n times, which is equal to 2<sup>n</sup>.<ref name=":13" /></blockquote>

This results in truth tables like this table "showing that {{math|(''A''→''C'')∧(''B''→''C'')}} and {{math|(''A''∨''B'')→''C''}} are [[Truth function|truth-functionally]] [[Logical biconditional|equivalent]]", modeled after a table produced by [[Colin Howson|Howson]]:<ref name=":13" />
{| class="wikitable" style="margin:1em auto; text-align:center;"
! <math>A</math>
! <math>B</math>
! <math>C</math>
! <math>(A\rightarrow C)\and(B\rightarrow C)</math>
! <math>(A\vee B)\rightarrow C</math>
|-
| {{Success|T}} || {{Success|T}} || {{Success|T}} 
|{{Success|T}}|| {{Success|T}}
|-
| {{Success|T}} || {{Success|T}} || {{Failure|F}} 
|{{Failure|F}}|| {{Failure|F}}
|-
| {{Success|T}} || {{Failure|F}} || {{Success|T}} 
|{{Success|T}}|| {{Success|T}}
|-
| {{Failure|F}} || {{Success|T}} || {{Success|T}} 
|{{Success|T}}|| {{Success|T}}
|-
| {{Failure|F}} || {{Failure|F}} || {{Success|T}} 
|{{Success|T}}|| {{Success|T}}
|-
| {{Failure|F}} || {{Success|T}} || {{Failure|F}} 
|{{Failure|F}}|| {{Failure|F}}
|-
| {{Success|T}} || {{Failure|F}} || {{Failure|F}} 
|{{Failure|F}}|| {{Failure|F}}
|-
| {{Failure|F}} || {{Failure|F}} || {{Failure|F}} 
|{{Success|T}}|| {{Success|T}}
|}

== Size of truth tables ==
If there are ''n'' input variables then there are 2<sup>''n''</sup> possible combinations of their truth values. A given function may produce true or false for each combination so the number of different functions of ''n'' variables is the [[double exponential function|double exponential]] 2<sup>2<sup>''n''</sup></sup>.

{| class="wikitable" style="text-align:right;"
|-
! ''n'' !! 2<sup>''n''</sup> !! colspan="2" | 2<sup>2<sup>''n''</sup></sup>
|-
| 0 || 1 || style="border-right:0px solid transparent;" |  2 || style="border-left:0px solid transparent;" |
|-
| 1 || 2 || style="border-right:0px solid transparent;" |  4 || style="border-left:0px solid transparent;" |
|-
| 2 || 4 || style="border-right:0px solid transparent;" |  16 || style="border-left:0px solid transparent;" |
|-
| 3 || 8 || style="border-right:0px solid transparent;" |  256 || style="border-left:0px solid transparent;" |
|-
| 4 || 16 || style="border-right:0px solid transparent;" |  65,536 || style="border-left:0px solid transparent;text-align:left;" |
|-
| 5 || 32 || style="border-right:0px solid transparent;" |  4,294,967,296 || style="border-left:0px solid transparent;text-align:left;" | ≈ 4.3{{e|9}}
|-
| 6 || 64 || style="border-right:0px solid transparent;" |  18,446,744,073,709,551,616 || style="border-left:0px solid transparent;text-align:left;" | ≈ 1.8{{e|19}}
|-
| 7 || 128 || style="border-right:0px solid transparent;" |  {{val|340282366920938463463374607431768211456|fmt=commas}} || style="border-left:0px solid transparent;text-align:left;" | ≈ 3.4{{e|38}}
|-
| 8 || 256 || style="border-right:0px solid transparent;" |  {{val|115792089237316195423570985008687907853269984665640564039457584007913129639936|fmt=commas}} || style="border-left:0px solid transparent;text-align:left;" | ≈ 1.2{{e|77}}
|}

Truth tables for functions of three or more variables are rarely given.

==Function Tables==
It can be useful to have the output of a truth table expressed as a function of some variable values, instead of just a literal truth or false value. These may be called "function tables" to differentiate them from the more general "truth tables".<ref>{{cite book |last1=Mano |first1=M. Morris |last2=Ciletti |first2=Michael |title=Digital Design, Global Edition |date=2018-07-13 |publisher=Pearson Education, Limited |isbn=9781292231167 |edition=6th}}</ref> For example, one value, {{mvar|G}}, may be used with an XOR gate to conditionally invert another value, {{mvar|X}}. In other words, when {{mvar|G}} is false, the output is {{mvar|X}}, and when {{mvar|G}} is true, the output is <math display="inline">\neg X</math>. The function table for this would look like:
{| class="wikitable" style="margin:1em auto; text-align:center;"
! <math>G</math> !! <math>G\nleftrightarrow X</math>
|-
| F || <math>X</math>
|-
| T || <math>\neg X</math>
|}

Similarly, a 4-to-1 [[multiplexer]] with select imputs <math>S_0</math> and <math>S_1</math>, data inputs {{mvar|A}}, {{mvar|B}}, {{mvar|C}} and {{mvar|D}}, and output {{mvar|Z}} (as displayed in the image) would have this function table:
[[File:Multiplexer 4-to-1.svg|thumb|4-to-1 multiplexer]]
{| class="wikitable" style="margin:1em auto; text-align:center;"
! <math>S_1</math> !! <math>S_0</math> !! {{nobold|{{mvar|Z}}}}
|-
| F || F || {{mvar|A}}
|-
| F || T || {{mvar|B}}
|-
| T || F || {{mvar|C}}
|-
| T || T || {{mvar|D}}
|}

==Sentential operator truth tables==
===Overview table===
Here is an extended truth table giving definitions of all sixteen possible truth functions of two Boolean variables '''''p''''' and '''''q''''':<ref group=note>Information about notation may be found in {{harv|Bocheński|1959}}, {{harv|Enderton|2001}}, and {{harv|Quine|1982}}.</ref>

{| class="wikitable" style="margin:left margin:1em auto 1em auto; text-align:center;"
|-
! <math>p</math> || <math>q</math>
! style="background:black" |
![[Contradiction|<math>\bot</math>]]||[[Logical NOR|<math>p\downarrow q</math>]]||[[Converse nonimplication|<math>p\nleftarrow q</math>]]||[[Negation|<math>\neg p</math>]]||[[Material nonimplication|<math>p\nrightarrow q</math>]]||[[Negation|<math>\neg q</math>]]||[[Exclusive or|<math>p\nleftrightarrow q</math>]]||[[Sheffer stroke|<math>p\uparrow q</math>]]||[[Logical conjunction|<math>p\and q</math>]]||[[Logical biconditional|<math>p\leftrightarrow q</math>]]||[[Projection (set theory)|<math>q</math>]]||[[Material conditional|<math>p\rightarrow q</math>]]||[[Projection (set theory)|<math>p</math>]]||[[Converse (logic)|<math>p\leftarrow q</math>]]||[[Logical disjunction|<math>p\vee q</math>]]||[[Tautology (logic)|<math>\top</math>]]
|-
| {{Success|T}} || {{Success|T}}
| style="background:black" | || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Success|T}}
|-
| {{Success|T}} || {{Failure|F}}
| style="background:black" | || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Failure|F}} || {{Success|T}} || {{Success|T}} || {{Success|T}} || {{Success|T}}
|-
| {{Failure|F}} || {{Success|T}}
| style="background:black" | || {{Failure|F}} || {{Failure|F}} || {{Success|T}} || {{Success|T}} || {{Failure|F}} || {{Failure|F}} || {{Success|T}} || {{Success|T}} || {{Failure|F}} || {{Failure|F}} || {{Success|T}} || {{Success|T}} || {{Failure|F}} || {{Failure|F}} || {{Success|T}} || {{Success|T}}
|-
| {{Failure|F}} || {{Failure|F}}
| style="background:black" | || {{Failure|F}} || {{Success|T}} || {{Failure|F}} || {{Success|T}} || {{Failure|F}} || {{Success|T}} || {{Failure|F}} || {{Success|T}} || {{Failure|F}} || {{Success|T}} || {{Failure|F}} || {{Success|T}} || {{Failure|F}} || {{Success|T}} || {{Failure|F}} || {{Success|T}}
|-
| colspan="19" style="background:black" |
|-
| colspan="2" style="background: #;" |{{abbr|Com|Commutative}}
| style="background:black" | || {{yan}} || {{yan}} || || || || || {{yan}} || {{yan}} || {{yan}} || {{yan}} || || || || || {{yan}} || {{yan}}
|-
| colspan="2" style="background: #;" |{{abbr|Assoc|Associative}}
| style="background:black" | || {{yan}} || || || || || || {{yan}} || || {{yan}} || {{yan}} || {{yan}} || || {{yan}} || || {{yan}} || {{yan}}
|-
| colspan="2" style="background: #;" |{{abbr|Adj|Adjoint operator}}
| style="background:black" | || <math>\bot</math> || <math>p\downarrow q</math> || <math>p\nrightarrow q</math> || <math>\neg q</math> || <math>p\nleftarrow q</math> || <math>\neg p</math> || <math>p\nleftrightarrow q</math> || <math>p\uparrow q</math> || <math>p\and q</math> || <math>p\leftrightarrow q</math> || <math>p</math> || <math>p\leftarrow q</math> || <math>q</math> || <math>p\rightarrow q</math> || <math>p\vee q</math> || <math>\top</math>
|-
| colspan="2" style="background: #;" | {{abbr|Neg|Negation}}
| style="background:black" | || <math>\top</math> || <math>p\vee q</math> || <math>p\leftarrow q</math> || <math>p</math> || <math>p\rightarrow q</math> || <math>q</math> || <math>p\leftrightarrow q</math> || <math>p\and q</math> || <math>p\uparrow q</math> || <math>p\nleftrightarrow q</math> || <math>\neg q</math> || <math>p\nrightarrow q</math> || <math>\neg p</math> || <math>p\nleftarrow q</math> || <math>p\downarrow q</math> || <math>\bot</math>
|-
| colspan="2" style="background: #;" | {{abbr|Dual|Dual operator}}
| style="background:black" | || <math>\top</math> || <math>p\uparrow q</math> || <math>p\rightarrow q</math>  || <math>\neg p</math> || <math>p\leftarrow q</math> || <math>\neg q</math> || <math>p\leftrightarrow q</math> || <math>p\downarrow q</math> || <math>p\vee q</math> || <math>p\nleftrightarrow q</math> || <math>q</math> || <math>p\nleftarrow q</math> || <math>p</math> || <math>p\nrightarrow q</math> || <math>p\and q</math> || <math>\bot</math>
|-
| colspan="2" style="background: #;" |{{abbr|L id|Left identities}}
| style="background:black" | || || || F || || || || F || || T || T || T,&nbsp;F || T || || || F ||
|-
| colspan="2" style="background: #;" |{{abbr|R id|Right identities}}
| style="background:black" | || || || || || F || || F || || T || T || || || T,&nbsp;F || T || F ||
|}

where

:T = true.
:F = false.
:The '''Com''' row indicates whether an operator, '''op''', is [[Commutative property|commutative]] – {{math|1=''P'' op ''Q'' = ''Q'' op ''P''}}.
:The '''Assoc''' row indicates whether an operator, '''op''', is [[Associative property|associative]] – {{math|1=(''P'' op ''Q'') op ''R'' = ''P'' op (''Q'' op ''R'')}}.
:The '''Adj''' row shows the operator '''op2''' such that {{math|1=''P'' op ''Q'' = ''Q'' op2 ''P''}}.
:The '''Neg''' row shows the operator '''op2''' such that {{math|1=''P'' op ''Q'' = ¬(''P'' op2 ''Q'')}}.
:The '''Dual''' row shows the [[Duality principle (Boolean algebra)|dual operation]] obtained by interchanging T with F, and AND with OR.
:The '''L id''' row shows the operator's [[left identity|left identities]] if it has any values {{mvar|I}} such that {{math|1=''I'' op ''Q'' = ''Q''}}.
:The '''R id''' row shows the operator's [[right identity|right identities]] if it has any values {{mvar|I}} such that {{math|1=''P'' op ''I'' = ''P''}}.<ref group=note>The operators here with equal left and right identities (XOR, AND, XNOR, and OR) are also [[monoid#Commutative monoid|commutative monoids]] because they are also [[Associative property|associative]]. While this distinction may be irrelevant in a simple discussion of logic, it can be quite important in more advanced mathematics. For example, in [[category theory]] an [[enriched category]] is described as a base [[category (mathematics)|category]] enriched over a monoid, and any of these operators can be used for enrichment.</ref>

===Wittgenstein table===

In proposition 5.101 of the ''[[Tractatus Logico-Philosophicus]]'',<ref name=tlp5.101>{{cite book|first=Ludwig |last=Wittgenstein|author-link=Ludwig Wittgenstein |date=1922 |title=Tractatus Logico-Philosophicus|url=https://www.gutenberg.org/files/5740/5740-pdf.pdf |at=Proposition 5.101}}</ref> [[Ludwig Wittgenstein|Wittgenstein]] listed the table above as follows:
:{| class="wikitable" style="margin:left margin:1em auto 1em auto; text-align:left;"
|-
! scope=col |
! scope=col | Truthvalues
! scope=col |
! scope=col colspan="2" | Operator
! scope=col | Operation name
! scope=col | Tractatus<ref name="different_mapping" group="note" />
|-
| 0 ||(F F F F)(p, q)|| ⊥ || [[falsum|false]] || '''Opq''' || [[Contradiction]] || p and not p; and q and not q
|-
| 1 ||(F F F T)(p, q)|| NOR || '''p''' ↓ '''q''' || '''Xpq''' || [[Logical NOR]] || neither ''p'' nor ''q''
|-
| 2 ||(F F T F)(p, q)|| ↚ || '''p''' ↚ '''q''' || '''Mpq''' || [[Converse nonimplication]] ||''q'' and not ''p''
|-
| 3 ||(F F T T)(p, q)|| '''¬p''', '''~p''' || '''¬p''' || '''Np''', '''Fpq''' || [[Negation]] || not ''p''
|-
| 4 ||(F T F F)(p, q)|| ↛ || '''p''' ↛ '''q''' 
|| '''Lpq''' || [[Material nonimplication]] ||''p'' and not ''q''
|-
| 5 ||(F T F T)(p, q)|| '''¬q''', '''~q''' || '''¬q''' || '''Nq''', '''Gpq''' || Negation || not ''q''
|-
| 6 ||(F T T F)(p, q)|| XOR ||'''p''' ⊕ '''q''' || '''Jpq''' || [[Exclusive disjunction]] || ''p'' or ''q'', but not both
|-
| 7 || (F T T T)(p, q)|| NAND || '''p''' ↑ '''q''' || '''Dpq''' || [[Logical NAND]] || not both ''p'' and ''q''
|-
| 8 || (T F F F)(p, q)|| AND || '''p''' ∧ '''q''' || '''Kpq''' || [[Logical conjunction]] || ''p'' and ''q''
|-
| 9 || (T F F T)(p, q)|| XNOR || '''p'''  [[if and only if|iff]] '''q''' || '''Epq'''  || [[Logical biconditional]] || if ''p'' then ''q''; and if ''q'' then ''p''
|-
| 10 || (T F T F)(p, q)|| '''q''' || '''q''' || '''Hpq''' || [[Projection function]] || ''q''
|-
| 11 || (T F T T)(p, q)|| '''p''' → '''q'''  || if '''p''' then '''q''' || '''Cpq''' || [[Material conditional|Material implication]] || if ''p'' then ''q''
|-
| 12 || (T T F F)(p, q)|| '''p''' || '''p''' || '''Ipq''' || Projection function || ''p''
|-
| 13 || (T T F T)(p, q)|| '''p''' &larr; '''q''' || if '''q''' then '''p''' || '''Bpq''' || [[Converse implication]] || if ''q'' then ''p''
|-
| 14 || (T T T F)(p, q)|| OR || '''p''' ∨ '''q''' || '''Apq''' || [[Logical disjunction]] || ''p'' or ''q''
|-
| 15 || (T T T T)(p, q)|| ⊤ || [[Tee (symbol)|true]] ||  '''Vpq''' || [[Tautology (logic)|Tautology]] || if p then p; and if q then q
|}

The truth table represented by each row is obtained by appending the sequence given in '''Truthvalues'''<sub>row</sub> to the table<ref name="different_mapping" group="note">Wittgenstein used a different mapping. In proposition 5.101 of the Tractatus one has to append '''Truthvalues'''<sub>row</sub> to the table
:{| class="wikitable" style="margin:left margin:1em auto 1em auto; text-align:left;"
!scope=row | ''p''
| {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Failure|}}F
|-
!scope=row | ''q''
| {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|}
This explains why '''Tractatus'''<sub>row</sub> in the table given here does not point to the same '''Truthvalues'''<sub>row</sub> as in the Tractatus.</ref>
:{| class="wikitable" style="margin:left margin:1em auto 1em auto; text-align:left;"
!scope=row | ''p''
| {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
!scope=row | ''q''
| {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Failure|}}F
|}

For example, the table
:{| class="wikitable" style="margin:left margin:1em auto 1em auto; text-align:left;"
!scope=row | ''p''
| {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
!scope=row | ''q''
| {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Failure|}}F
|-
!scope=row | ''11''
| {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Success|}}T
|}
represents the truth table for [[Material conditional|Material implication]]. Logical operators can also be visualized using [[Venn diagram#Overview|Venn diagram]]s.

=== Nullary operations ===

There are 2 nullary operations:
*Always true
*Never true, unary ''[[falsum]]''

====Logical true====
The output value is always true, because this operator has zero operands and therefore no input values
{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:80px" | ''p''
! style="width:80px" | {{math|''T''}}
|-
| {{Success|}}T
| {{Success|}}T
|-
| {{Failure|}}F
| {{Success|}}T
|}

====Logical false====
The output value is never true: that is, always false, because this operator has zero operands and therefore no input values
{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:80px" | ''p''
! style="width:80px" | {{math|''F''}}
|-
| {{Success|}}T
| {{Failure|}}F
|-
| {{Failure|}}F
| {{Failure|}}F
|}

=== Unary operations ===
There are 2 unary operations:
*Unary ''identity'' 
*Unary ''negation''

====Logical identity====
[[Identity function|Logical identity]] is an [[logical operation|operation]] on one [[logical value]] p, for which the output value remains p.

The truth table for the logical identity operator is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:80px" | ''p''
! style="width:80px" | {{math|''p''}}
|-
| {{Success|}}T
| {{Success|}}T
|-
| {{Failure|}}F
| {{Failure|}}F
|}

====Logical negation====
[[Logical negation]] is an [[logical operation|operation]] on one [[logical value]], typically the value of a [[proposition]], that produces a value of ''true'' if its operand is false and a value of ''false'' if its operand is true.

The truth table for '''NOT p''' (also written as '''¬p''', '''Np''', '''Fpq''', or '''~p''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:80px" | ''p''
! style="width:80px" | {{math|''¬p''}}
|-
| {{Success|}}T
| {{Failure|}}F
|-
| {{Failure|}}F
| {{Success|}}T
|}

===Binary operations===
There are 16 possible [[truth function]]s of two [[binary variable]]s, each operator has its own name.

====Logical conjunction (AND)====
[[Logical conjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if both of its operands are true.

The truth table for '''p AND q''' (also written as '''p ∧ q''', '''Kpq''', '''p & q''', or '''p''' <math>\cdot</math> '''q''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ∧ ''q''
|-
| {{Success|}}T || {{Success|}}T || {{Success|}}T
|-
| {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
| {{Failure|}}F || {{Success|}}T || {{Failure|}}F
|-
| {{Failure|}}F || {{Failure|}}F || {{Failure|}}F
|}

In ordinary language terms, if both ''p'' and ''q'' are true, then the conjunction ''p'' ∧ ''q'' is true.  For all other assignments of logical values to ''p'' and to ''q'' the conjunction ''p''&nbsp;∧&nbsp;''q'' is false.

It can also be said that if ''p'', then ''p'' ∧ ''q'' is ''q'', otherwise ''p'' ∧ ''q'' is ''p''.

====Logical disjunction (OR)====
[[Logical disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if at least one of its operands is true.

The truth table for '''p OR q''' (also written as '''p ∨ q''', '''Apq''', '''p || q''', or '''p + q''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ∨ ''q''
|-
| {{Success|}}T || {{Success|}}T || {{Success|}}T
|-
| {{Success|}}T || {{Failure|}}F || {{Success|}}T
|-
| {{Failure|}}F || {{Success|}}T || {{Success|}}T
|-
| {{Failure|}}F || {{Failure|}}F || {{Failure|}}F
|}

Stated in English, if ''p'', then ''p'' ∨ ''q'' is ''p'', otherwise ''p'' ∨ ''q'' is ''q''.

====Logical implication====
Logical implication and the [[material conditional]] are both associated with an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, which produces a value of ''false'' if the first operand is true and the second operand is false, and  a value of ''true'' otherwise.

The truth table associated with the logical implication '''p implies q''' (symbolized as '''p&nbsp;⇒&nbsp;q''', or more rarely '''Cpq''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ⇒ ''q''
|-
| {{Success|}}T || {{Success|}}T || {{Success|}}T
|-
| {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
| {{Failure|}}F || {{Success|}}T || {{Success|}}T
|-
| {{Failure|}}F || {{Failure|}}F || {{Success|}}T
|}

The truth table associated with the material conditional '''if p then q''' (symbolized as '''p&nbsp;→&nbsp;q''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' → ''q''
|-
| {{Success|}}T || {{Success|}}T || {{Success|}}T
|-
| {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
| {{Failure|}}F || {{Success|}}T || {{Success|}}T
|-
| {{Failure|}}F || {{Failure|}}F || {{Success|}}T
|}

'''p&nbsp;⇒&nbsp;q''' and '''p&nbsp;→&nbsp;q''' are equivalent to '''¬p&nbsp;∨&nbsp;q'''.

====Logical equality====
[[Logical equality]] (also known as [[biconditional]] or [[exclusive nor]]) is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if both operands are false or both operands are true.

The truth table for '''p XNOR q''' (also written as '''p ↔ q''', '''Epq''', '''p = q''', or '''p ≡ q''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ↔ ''q''
|-
| {{Success|}}T || {{Success|}}T || {{Success|}}T
|-
| {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
| {{Failure|}}F || {{Success|}}T || {{Failure|}}F
|-
| {{Failure|}}F || {{Failure|}}F || {{Success|}}T
|}

So p EQ q is true if p and q have the same [[truth value]] (both true or both false), and false if they have different truth values.

====Exclusive disjunction====
[[Exclusive disjunction]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if one but not both of its operands is true.

The truth table for '''p XOR q''' (also written as '''Jpq''', or '''p ⊕ q''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | '''p''' ⊕ '''q'''
|-
| {{Success|}}T || {{Success|}}T || {{Failure|}}F
|-
| {{Success|}}T || {{Failure|}}F || {{Success|}}T
|-
| {{Failure|}}F || {{Success|}}T || {{Success|}}T
|-
| {{Failure|}}F || {{Failure|}}F || {{Failure|}}F
|}

For two propositions, '''XOR''' can also be written as (p ∧ ¬q) ∨ (¬p ∧ q).

====Logical NAND====
The [[logical NAND]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''false'' if both of its operands are true.  In other words, it produces a value of ''true'' if at least one of its operands is false.

The truth table for '''p NAND q''' (also written as '''p ↑ q''', '''Dpq''', or '''p | q''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ↑ ''q''
|-
| {{Success|}}T || {{Success|}}T || {{Failure|}}F
|-
| {{Success|}}T || {{Failure|}}F || {{Success|}}T
|-
| {{Failure|}}F || {{Success|}}T || {{Success|}}T
|-
| {{Failure|}}F || {{Failure|}}F || {{Success|}}T
|}

It is frequently useful to express a logical operation as a [[compound operation (computing)|compound operation]], that is, as an operation that is built up or composed from other operations.  Many such compositions are possible, depending on the operations that are taken as basic or "primitive" and the operations that are taken as composite or "derivative".

In the case of logical NAND, it is clearly expressible as a compound of NOT and AND.

The negation of a conjunction: ¬(''p''&nbsp;∧&nbsp;''q''), and the disjunction of negations: (¬''p'')&nbsp;∨&nbsp;(¬''q'') can be tabulated as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p''&nbsp;∧&nbsp;''q''
! style="width:15%" | ¬(''p''&nbsp;∧&nbsp;''q'')
! style="width:15%" | ¬''p''
! style="width:15%" | ¬''q''
! style="width:15%" | (¬''p'')&nbsp;∨&nbsp;(¬''q'')
|-
| {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Failure|}}F || {{Failure|}}F || {{Failure|}}F
|-
| {{Success|}}T || {{Failure|}}F || {{Failure|}}F || {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Success|}}T
|-
| {{Failure|}}F || {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Success|}}T
|-
| {{Failure|}}F || {{Failure|}}F || {{Failure|}}F || {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Success|}}T
|}

====Logical NOR====
The [[logical NOR]] is an [[logical operation|operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, that produces a value of ''true'' if both of its operands are false. In other words, it produces a value of ''false'' if at least one of its operands is true. ↓ is also known as the [[Peirce arrow]] after its inventor, [[Charles Sanders Peirce]], and is a [[Sole sufficient operator]].

The truth table for '''p NOR q''' (also written as '''p ↓ q''', or '''Xpq''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ↓ ''q''
|-
| {{Success|}}T || {{Success|}}T || {{Failure|}}F
|-
| {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
| {{Failure|}}F || {{Success|}}T || {{Failure|}}F
|-
| {{Failure|}}F || {{Failure|}}F || {{Success|}}T
|}

The negation of a disjunction ¬(''p''&nbsp;∨&nbsp;''q''), and the conjunction of negations (¬''p'')&nbsp;∧&nbsp;(¬''q'') can be tabulated as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|-
! style="width:10%" | ''p''
! style="width:10%" | ''q''
! style="width:10%" | ''p''&nbsp;∨&nbsp;''q''
! style="width:10%" | ¬(''p''&nbsp;∨&nbsp;''q'')
! style="width:10%" | ¬''p''
! style="width:10%" | ¬''q''
! style="width:10%" | (¬''p'')&nbsp;∧&nbsp;(¬''q'')
|-
| {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Failure|}}F || {{Failure|}}F || {{Failure|}}F
|-
| {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Failure|}}F || {{Failure|}}F || {{Success|}}T || {{Failure|}}F
|-
| {{Failure|}}F || {{Success|}}T || {{Success|}}T || {{Failure|}}F || {{Success|}}T || {{Failure|}}F || {{Failure|}}F
|-
| {{Failure|}}F || {{Failure|}}F || {{Failure|}}F || {{Success|}}T || {{Success|}}T || {{Success|}}T || {{Success|}}T
|}

Inspection of the tabular derivations for NAND and NOR, under each assignment of logical values to the functional arguments ''p'' and ''q'', produces the identical patterns of functional values for ¬(''p''&nbsp;∧&nbsp;''q'') as for (¬''p'')&nbsp;∨&nbsp;(¬''q''), and for ¬(''p''&nbsp;∨&nbsp;''q'') as for (¬''p'')&nbsp;∧&nbsp;(¬''q'').  Thus the first and second expressions in each pair are logically equivalent, and may be substituted for each other in all contexts that pertain solely to their logical values.

This equivalence is one of [[De Morgan's laws]].

==See also==
{{Portal|Philosophy|Psychology}}
{{div col|colwidth=20em}}
* [[Boolean domain]]
* [[Boolean-valued function]]
* [[Publicad|Espresso heuristic logic minimizer]]
* [[Excitation table]]
* [[State-transition table]]
* [[First-order logic]]
* [[Functional completeness]]
* [[Karnaugh maps]]
* [[Logic gate]]
* [[Logical connective]]
* [[Logical graph]]
* [[Mathematical table]]
* [[Method of analytic tableaux]]
* [[Propositional calculus]]
* [[Truth function]]
* [[Decision table]]
{{div col end}}

==Notes==
{{reflist|group=note}}

==References==
{{Reflist}}

===Works cited===
*{{cite book |author-link=Józef Maria Bocheński |first=Józef Maria |last=Bocheński |translator-first=Otto |translator-last=Bird |title=A Précis of Mathematical Logic |publisher=D. Reidel |date=1959 |isbn=978-94-017-0592-9 |url={{GBurl|YX8iCQAAQBAJ|pg=PP5}}
 |doi=10.1007/978-94-017-0592-9}}
*{{cite book |author-link=Herbert Enderton |first=H. |last=Enderton |title=A Mathematical Introduction to Logic |publisher=Harcourt Academic Press |edition=2nd |date=2001 |isbn=0-12-238452-0 |url={{GBurl|dVncCl_EtUkC|pg=PR7}}}}
*{{cite book |author-link=W.V. Quine |edition=4th |first=W.V. |last=Quine |title=Methods of Logic |publisher=Harvard University Press |date=1982 |isbn=978-0-674-57175-4 }}

==External links==
{{Commons category|Truth tables}}
* {{springer|title=Truth table|id=p/t094370}}
*[http://sites.millersville.edu/bikenaga/math-proof/truth-tables/truth-tables.html Truth Tables, Tautologies, and Logical Equivalence]
*[http://www.allaboutcircuits.com/vol_4/chpt_7/9.html Converting truth tables into Boolean expressions]
{{Classical logic}}
{{Mathematical logic}}

{{Authority control}}

{{Diagrams in logic}}

{{DEFAULTSORT:Truth Table}}
[[Category:Boolean algebra]]
[[Category:Mathematical tables]]
[[Category:Semantics]]
[[Category:Propositional calculus]]
[[Category:Conceptual models]]