View source for Truth table

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 combination of values taken by their logical variables ([[Herbert Enderton|Enderton]], 2001). 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, P and Q), and one final column showing all of the possible results of the logical operation that the table represents (for example, P [[XOR]] Q). Each row of the truth table contains one possible configuration of the input variables (for instance, P=true Q=false), and the result of the operation for those values. See the examples below for further clarification. [[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 = [[Georg Henrik 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=[[Emil 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}}</ref> An even earlier iteration of the truth table has also been found in unpublished manuscripts by [[Charles Sanders Peirce]] from 1893, antedating both publications by nearly 30 years.<ref name="Peirce"/>

==Unary operations==

There are 4 unary operations:
*Always true
*Never true, unary ''[[falsum]]''
*Unary ''Identity'' 
*Unary ''negation''

===Logical true===
The output value is always true, regardless of the input value of p
{| class="wikitable" style="margin:1em auto; text-align:center;"
|+ '''Logical True'''
|-
! style="width:80px" | ''p''
! style="width:80px" | <span class="texhtml">''T''</span>
|-
| T ||  T
|-
| style="background:papayawhip" | F || T
|}

===Logical false===
The output value is never true: that is, always false,  regardless of the input value of p
{| class="wikitable" style="margin:1em auto; text-align:center;"
|+ '''Logical False'''
|-
! style="width:80px" | ''p''
! style="width:80px" | <span class="texhtml">''F''</span>
|-
| T || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F ||  style="background:papayawhip" | F
|}

===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;"
|+ '''Logical Identity'''
|-
! style="width:80px" | ''p''
! style="width:80px" | <span class="texhtml">''p''</span>
|-
| T || T
|-
| style="background:papayawhip" | F ||  style="background:papayawhip" | 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;"
|+ '''Logical Negation'''
|-
! style="width:80px" | ''p''
! style="width:80px" | <span class="texhtml">''¬p''</span>
|-
| T || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || T
|}

==Binary operations==

There are 16  possible [[truth function]]s of two [[binary variable]]s:

===Truth table for all binary logical operators===
Here is an extended truth table giving definitions of all possible truth functions of two Boolean variables P and Q:<ref group=note>Information about notation may be found in [[Józef Maria Bocheński|Bocheński]] (1959), [[Herbert Enderton|Enderton]] (2001), and [[W. V. Quine|Quine]] (1982).</ref>

{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"
|-
! ''p'' || ''q''
|
! &nbsp;[[Contradiction|F]]<sup>0</sup>&nbsp; || &nbsp;[[Logical NOR|NOR]]<sup>1</sup>&nbsp; || &nbsp;[[Converse nonimplication|↚]]<sup>2</sup>&nbsp; || &nbsp;[[Negation|'''¬p''']]<sup>3</sup>&nbsp; || &nbsp;[[Material nonimplication|↛]]<sup>4</sup>&nbsp; || &nbsp;[[Negation|'''¬q''']]<sup>5</sup>&nbsp;  || &nbsp;[[Exclusive disjunction|XOR]]<sup>6</sup>&nbsp; || &nbsp;[[Logical NAND|NAND]]<sup>7</sup>&nbsp;
|
!| &nbsp;[[Logical conjunction|AND]]<sup>8</sup>&nbsp; || &nbsp;[[Logical biconditional|XNOR]]<sup>9</sup>&nbsp; || [[Projection function|q]]<sup>10</sup> || [[Material conditional|→]]<sup>11</sup> || [[Projection function|p]]<sup>12</sup> || [[Converse implication|←]]<sup>13</sup> || [[Logical disjunction|OR]]<sup>14</sup> || [[Tautology (logic)|T]]<sup>15</sup>
|-
! T || T
| || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || || T || T || T || T || T || T || T || T
|-
! T || style="background:papayawhip" | F
| || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || T || T || T || T || || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || T || T || T || T
|-
! style="background:papayawhip" | F || T
| || style="background:papayawhip" | F || style="background:papayawhip" | F || T || T || style="background:papayawhip" | F || style="background:papayawhip" | F || T || T || || style="background:papayawhip" | F || style="background:papayawhip" | F || T || T || style="background:papayawhip" | F || style="background:papayawhip" | F || T || T
|-
! style="background:papayawhip" | F || style="background:papayawhip" | F
| || style="background:papayawhip" | F || T || style="background:papayawhip" | F || T || style="background:papayawhip" | F || T || style="background:papayawhip" | F || T || || style="background:papayawhip" | F || T || style="background:papayawhip" | F || T || style="background:papayawhip" | F || T || style="background:papayawhip" | F || T
|-
! colspan="2" style="background: #ffdead;" |Com  
| || ✓ || ✓ || || || || || ✓ || ✓ || || ✓ || ✓ || || || || || ✓ || ✓
|-
! colspan="2" style="background: #ffdead;" |L id  
| || || || F || || || || F || || || T || T || T,F || T || || || F ||
|-
! colspan="2" style="background: #ffdead;" |R id  
| || || || || || F || || F || || || T || T || || || T,F || T || F ||
|}

where

:T = true.
:F = false.
:The '''Com''' row indicates whether an operator, '''op''', is [[Commutative property|commutative]] - '''P op Q = Q op P'''.
:The '''L id''' row shows the operator's [[left identity|left identities]] if it has any - values '''I''' such that '''I op Q = Q'''.
:The '''R id''' row shows the operator's [[right identity|right identities]] if it has any - values '''I''' such that '''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>

The four combinations of input values for p, q, are read by row from the table above.
The output function for each  p, q combination, can be read, by row, from the table.

'''Key:'''

The following table is oriented by column, rather than by row. There are four columns rather than four rows, to display the four combinations of p, q, as input.

'''p''': T T F F<br />
'''q''': T F T F

There are 16 rows in this key, one row for each binary function of the two binary variables, p, q. For example, in row 2 of this Key, the value of [[Converse nonimplication]] ('<math>\nleftarrow</math>') is solely T, for the column denoted by the unique combination p=F, q=T; while  in row 2, the value of that '<math>\nleftarrow</math>' operation is F for the three remaining columns of p, q. The output row for <math>\nleftarrow</math> is thus

2: F F T F

and the 16-row<ref name=tlp5.101/> key is
{| class="wikitable" style="margin:1em auto 1em auto; text-align:left;"
|-
! ||<ref name=tlp5.101>[[Ludwig Wittgenstein]] (1922) ''[[Tractatus Logico-Philosophicus]]'' [http://www.gutenberg.org/files/5740/5740-pdf.pdf Proposition 5.101]</ref>|| || operator || Operation name
|-
| 0 ||(F F F F)(p, q)|| ⊥ || [[falsum|false]], '''Opq''' || [[Contradiction]]
|-
| 1 ||(F F F T)(p, q)|| NOR || '''p''' ↓ '''q''', '''Xpq''' || [[Logical NOR]]
|-
| 2 ||(F F T F)(p, q)|| ↚ || '''p''' ↚ '''q''', '''Mpq''' || [[Converse nonimplication]]
|-
| 3 ||(F F T T)(p, q)|| '''¬p''', '''~p''' || '''¬p''', '''Np''', '''Fpq''' || [[Negation]]
|-
| 4 ||(F T F F)(p, q)|| ↛ || '''p''' ↛ '''q''', '''Lpq''' || [[Material nonimplication]]
|-
| 5 ||(F T F T)(p, q)|| '''¬q''', '''~q''' || '''¬q''', '''Nq''', '''Gpq''' || Negation
|-
| 6 ||(F T T F)(p, q)|| XOR ||'''p''' ⊕ '''q''', '''Jpq''' || [[Exclusive disjunction]]
|-
| 7 || (F T T T)(p, q)|| NAND || '''p''' ↑ '''q''', '''Dpq''' || [[Logical NAND]]
|-
| 8 || (T F F F)(p, q)|| AND || '''p''' ∧ '''q''', '''Kpq''' || [[Logical conjunction]]
|-
| 9 || (T F F T)(p, q)|| XNOR || '''p'''  [[If and only if]] '''q''', '''Epq'''  || [[Logical biconditional]]
|-
| 10 || (T F T F)(p, q)|| '''q''' || '''q''', '''Hpq''' || [[Projection function]]
|-
| 11 || (T F T T)(p, q)|| '''p''' &rarr; '''q'''  || if '''p''' then '''q''', '''Cpq''' || [[Material conditional|Material implication]]
|-
| 12 || (T T F F)(p, q)|| '''p''' || '''p''', '''Ipq''' || Projection function
|-
| 13 || (T T F T)(p, q)|| '''p''' &larr; '''q''' || '''p''' if '''q''', '''Bpq''' || [[Converse implication]]
|-
| 14 || (T T T F)(p, q)|| OR || '''p''' ∨ '''q''', '''Apq''' || [[Logical disjunction]]
|-
| 15 || (T T T T)(p, q)|| ⊤ || [[Tee (symbol)|true]], '''Vpq''' || [[Tautology (logic)|Tautology]]
|}
Logical operators can also be visualized using [[Venn diagram#Overview|Venn diagram]]s.

===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;"
|+ '''Logical conjunction'''
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ∧ ''q''
|-
| T || T || T
|-
| T || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || T || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | 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;"
|+ '''Logical disjunction'''
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ∨ ''q''
|-
| T || T || T
|-
| T || style="background:papayawhip" | F || T
|-
| style="background:papayawhip" | F || T || T
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | 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;"
|+ '''Logical implication'''
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ⇒ ''q''
|-
| T || T || T
|-
| T || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || T || T
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || 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;"
|+ '''Material conditional '''
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' → ''q''
|-
| T || T || T
|-
| T || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || T || T
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || T
|}

It may also be useful to note that '''p&nbsp;⇒&nbsp;q''' and '''p&nbsp;→&nbsp;q''' are equivalent to '''¬p&nbsp;∨&nbsp;q'''.

===Logical equality===
[[Logical equality]] (also known as biconditional) 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;"
|+ '''Logical equality'''
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ↔ ''q''
|-
| T || T || T
|-
| T || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || T || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || 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 '''p ⊕ q''') is as follows:

{| class="wikitable" style="margin:1em auto; text-align:center;"
|+ '''Exclusive disjunction'''
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''¬p''v''¬q''
|-
| T || T || style="background:papayawhip" | F
|-
| T || style="background:papayawhip" | F || T
|-
| style="background:papayawhip" | F || T || T
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | 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;"
|+ '''Logical NAND'''
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ↑ ''q''
|-
| T || T || style="background:papayawhip" | F
|-
| T || style="background:papayawhip" | F || T
|-
| style="background:papayawhip" | F || T || T
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || T
|}

It is frequently useful to express a logical operation as a 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'')
|-
| T || T || T || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| T || style="background:papayawhip" | F || style="background:papayawhip" | F || T || style="background:papayawhip" | F || T || T
|-
| style="background:papayawhip" | F || T || style="background:papayawhip" | F || T || T || style="background:papayawhip" | F || T
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || T || T || T || 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;"
|+ '''Logical NOR'''
|-
! style="width:15%" | ''p''
! style="width:15%" | ''q''
! style="width:15%" | ''p'' ↓ ''q''
|-
| T || T || style="background:papayawhip" | F
|-
| T || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || T || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || 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'')
|-
| T || T || T || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| T || style="background:papayawhip" | F || T || style="background:papayawhip" | F || style="background:papayawhip" | F || T || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || T || T || style="background:papayawhip" | F || T || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || T || T || T || 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]].

==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;"
|+ '''Logical equivalence : <math>(p \Rightarrow q) \equiv (\lnot p \lor q)</math>'''
|- style="background:paleturquoise"
! style="width:12%" | <math>p</math>
! style="width:12%" | <math>q</math>
! style="width:12%" | <math>\lnot p</math>
! style="width:12%" | <math>\lnot p \lor q</math>
! style="width:12%" | <math>p \Rightarrow q</math>
|-
| T || T || style="background:papayawhip" | F || T || T
|-
| T || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F || style="background:papayawhip" | F
|-
| style="background:papayawhip" | F || T || T || T || T
|-
| style="background:papayawhip" | F || style="background:papayawhip" | F || T || T || T
|}

This demonstrates the fact that <math>p \Rightarrow q</math> is [[logically equivalent]] to <math>\lnot p \lor q</math>.

===Truth table for most commonly used logical operators===
Here is a truth table that gives definitions of the 6 most commonly used out of [[Tractatus Logico-Philosophicus#Propositions 4.*-5.*|the 16 possible truth functions of two Boolean variables P and Q]]:

{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"
|-
! {{nobold|{{mvar|P}}}} || {{nobold|{{mvar|Q}}}} || <math>P \land Q</math> || <math>P \lor Q</math> || <math>P\ \underline{\lor}\ Q</math> || <math>P\ \underline{\land}\ Q</math> || <math>P \Rightarrow Q</math> || <math>P \Leftarrow Q</math>  ||  <math>P \Leftrightarrow Q</math>
|-
| T || T ||  T  ||  T  ||  style="background:papayawhip" | F   ||  T  ||  T  ||  T  ||  T
|-
| T || style="background:papayawhip" | F  ||  style="background:papayawhip" | F   ||  T  ||  T  ||  style="background:papayawhip" | F   ||  style="background:papayawhip" | F   ||  T  ||  style="background:papayawhip" | F 
|-
| style="background:papayawhip" | F  || T ||  style="background:papayawhip" | F   ||  T  ||  T  ||  style="background:papayawhip" | F   ||  T  ||  style="background:papayawhip" | F   ||  style="background:papayawhip" | F 
|-
| style="background:papayawhip" | F  || style="background:papayawhip" | F  ||  style="background:papayawhip" | F   ||  style="background:papayawhip" | F   ||  style="background:papayawhip" | F   ||  T  ||  T  ||  T  ||  T
|}

where

:; T : true
:; F : false
:; <math>\land</math> : [[logical conjunction|AND]] (logical conjunction)
:; <math>\lor</math> : [[logical disjunction|OR]] (logical disjunction)
:; <math>\underline{\lor}</math> : [[Exclusive or|XOR]] (exclusive or) <!-- this could be "+" instead according to other articles -->
:; <math>\underline{\land}</math> : [[Exclusive nor|XNOR]] (exclusive nor)
:; <math>\Rightarrow</math> : [[logical conditional|conditional "if-then"]]
:; <math>\Leftarrow</math> : conditional "then-if"
:; <math>\Leftrightarrow</math> : [[if and only if|biconditional "if-and-only-if"]].

===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;"
|-
! ∧ || F || T
|-
! F
| F || F
|-
! T
| F || T
|}
| style="width:80px;"|
|
{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"
|-
! ∨ || F || T
|-
! F
| F || T
|-
! T
| T || T
|}
|}

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 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>k = V_0 \times 2^0 + V_1 \times 2^1 + V_2 \times 2^2 + \dots + V_n \times 2^n</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:

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

where

A = First Operand
B = Second Operand
C = Carry
R = Result
</pre>

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.

Note that 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×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×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>

==History==
Irving Anellis’s research shows that [[C.S. Peirce]] appears to be the earliest logician (in 1893) to devise a truth table matrix.<ref name="Peirce">{{cite journal|last1=Anellis|first1=Irving H.|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}}</ref><ref>Peirce's publication included the work of [[Christine Ladd-Franklin#Mathematics and logic|Christine Ladd (1881)]]: Peirce's Ph.D. student Christine Ladd-Franklin found the truth table in ''Tractatus Logico-Philosophicus'' Proposition 5.101, 40 years earlier than Wittgenstein. [https://books.google.com/books?id=A48XAAAAIAAJ&pg=PA62 Christine Ladd (1881), "On the Algebra of Logic", p.62], ''Studies in Logic'', C. S. Peirce ed., 1883</ref> From the summary of his paper:
<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>

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

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

==References==
{{Reflist}}

==Further reading==
* [[Bocheński, Józef Maria]] (1959), ''A Précis of Mathematical Logic'', translated from the French and German editions by Otto Bird, Dordrecht, South Holland:  D. Reidel.
* [[Herbert Enderton|Enderton, H.]] (2001). ''A Mathematical Introduction to Logic'', second edition, New York:  Harcourt Academic Press. {{isbn|0-12-238452-0}}
* [[W.V. Quine|Quine, W.V.]] (1982), ''Methods of Logic'', 4th edition, Cambridge, MA:  Harvard University Press.

==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]
*[https://arxiv.org/ftp/arxiv/papers/1108/1108.2429.pdf PEIRCE'S TRUTH-FUNCTIONAL ANALYSIS AND THE ORIGIN OF TRUTH TABLES] by Irving H. Anellis
*[http://www.allaboutcircuits.com/vol_4/chpt_7/9.html Converting truth tables into Boolean expressions]
{{Classical logic}}
{{Mathematical logic}}

{{Authority control}}

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