A
truth table is a
mathematical tableBefore calculators were cheap and plentiful, people would use mathematical tables —lists of numbers showing the results of calculation with varying arguments— to simplify and drastically speed up computation...
used in
logicLogic, from the Greek λογική is the art and science of reasoning. More specifically, it is defined by the Penguin Encyclopedia to be "The formal systematic study of the principles of valid inference and correct reasoning". As a discipline, logic dates back to Aristotle, who established its...
—specifically in connection with Boolean algebra,
boolean functionIn mathematics, a Boolean function is a function of the form f : Bk → B, where B = {0, 1} is a Boolean domain and k is a nonnegative integer called the arity of the function...
s, and
propositional calculusIn logic and mathematics, a propositional calculus or logic is a formal system in which formulae representing propositions can be formed by combining atomic propositions using logical connectives, and a system of formal proof rules allows certain formulae to be established as theorems.-...
—to compute the functional values of logical
expressionIn mathematics, the word expression is a term for any well-formed combination of mathematical symbols. An algebraic expression is only a phrase, not a whole sentence, so it cannot contain an equality sign . For example,is an expression, while...
s on each of their functional arguments, that is, on each combination of values taken by their logical variables (Enderton 2001). In particular, truth tables can be used to tell whether a propositional expression is true for all legitimate input values, that is,
logically validThe term Validity in logic applies to arguments or statements.-Validity of arguments:An argument is valid if and only if the truth of its premises entails the truth of its conclusion. It would be self-contradictory to affirm the premises and deny the conclusion...
.
Practically, a truth table is composed of one column for each input variable (for example, A and B), and one final column for all of the possible results of the logical operation that the table is meant to represent (for example, A XOR B). Each row of the truth table therefore contains one possible configuration of the input variables (for instance, A=true B=false), and the result of the operation for those values. See the examples below for further clarification.
Logical negation
Logical negation is an operation on one
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
, typically the value of a
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
, 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 or
¬p) is as follows:
Logical Negation
| |
¬p |
| 1 |
0 |
| 0 |
1 |
Logical conjunction
Logical conjunctionIn logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
is an operation on two
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
s, typically the values of two
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
s, that produces a value of
true if and only if both of its operands are true.
The truth table for
p AND q (also written as
p ∧ q,
p & q, or
pq) is as follows:
Logical Conjunction
| |
|
. |
| 1 |
1 |
1 |
| 1 |
0 |
0 |
| 0 |
1 |
0 |
| 0 |
0 |
0 |
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 ∧
q is false.
It can also be said that if
p, then
p ∧
q is
q, otherwise
p ∧
q is
p.
Logical disjunction
Logical disjunctionIn logic and mathematics, or, also known as logical disjunction or inclusive disjunction, is a logical operator that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are true. In grammar, or is a...
is an operation on two
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
s, typically the values of two
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
s, that produces a value of
false if and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements. In that it is biconditional, the connective can be likened to the standard material conditional combined with its reverse ; hence the name...
both of its operands are false.
The truth table for
p OR q (also written as
p ∨ q,
p || q, or
p + q) is as follows:
Logical Disjunction
| |
|
|
| 1 |
1 |
1 |
| 1 |
0 |
1 |
| 0 |
1 |
1 |
| 0 |
0 |
0 |
Stated in English, if
p, then
p ∨
q is
p, otherwise
p ∨
q is
q.
Logical implication
Logical implicationIn logic and mathematics, logical implication is a logical relation that holds between a set T of formulae and a formula B when every model of T is also a model of B. In symbols,# ,# #...
and the material conditional are both associated with an operation on two
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
s, typically the values of two
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
s, that produces a value of
false just in the singular case the first operand is true and the second operand is false.
The truth table associated with the material conditional
not p or q (symbolized as
p → q) and the logical implication
p implies q (symbolized as
p ⇒ q) is as follows:
Logical Implication
| |
|
→ |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
Logical equality
Logical equalityLogical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus...
(also known as biconditional) is an operation on two
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
s, typically the values of two
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
s, that produces a value of
true if and only if both operands are false or both operands are true.
The truth table for
p EQ q (also written as
p = q,
p ↔ q, or
p ≡ q) is as follows:
Logical Equality
| |
|
≡ |
| T |
T |
T |
| T |
F |
F |
| F |
T |
F |
| F |
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 disjunctionThe logical operation exclusive disjunction, also called exclusive or , is a type of logical disjunction on two operands that results in a value of true if exactly one of the operands has a value of true...
is an operation on two
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
s, typically the values of two
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
s, that produces a value of
true if and only if one but not both of its operands is true.
The truth table for
p XOR q (also written as
p + q,
p ⊕ q, or
p ≠ q) is as follows:
Exclusive Disjunction
| |
|
⊕ |
| T |
T |
F |
| T |
F |
T |
| F |
T |
T |
| F |
F |
F |
For two propositions,
XOR can also be written as (p = 1 ∧ q = 0)∨ (p = 0 ∧ q = 1).
Logical NAND
The logical NAND is an operation on two
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
s, typically the values of two
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
s, that produces a value of
false if and only if both of its operands are true. In other words, it produces a value of
true if and only if at least one of its operands is false.
The truth table for
p NAND q (also written as
p | q or
p ↑ q) is as follows:
Logical NAND
| |
|
↑ |
| T |
T |
F |
| T |
F |
T |
| F |
T |
T |
| F |
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 conjunction , and the disjunction of negations are depicted as follows:
| |
|
|
|
|
|
|
| T |
T |
T |
F |
F |
F |
F |
| T |
F |
F |
T |
F |
T |
T |
| F |
T |
F |
T |
T |
F |
T |
| F |
F |
F |
T |
T |
T |
T |
Logical NOR
The
logical NORIn boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
is an operation on two
logical valueIn logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
s, typically the values of two
propositionA proposition is a sentence expressing something true or false. In philosophy, particularly in logic, a proposition is identified ontologically as an idea, concept, or abstraction whose token instances are patterns of symbols, marks, sounds, or strings of words...
s, that produces a value of
true if and only if both of its operands are false. In other words, it produces a value of
false if and only 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
p ↓ q) is as follows:
Logical NOR
| |
|
↓ |
| T |
T |
F |
| T |
F |
F |
| F |
T |
F |
| F |
F |
T |
The negation of disjunction and the conjunction of negations are tabulated as follows:
| |
|
|
|
|
|
|
| T |
T |
T |
F |
F |
F |
F |
| T |
F |
T |
F |
F |
T |
F |
| F |
T |
T |
F |
T |
F |
F |
| F |
F |
F |
T |
T |
T |
T |
Inspection of the tabular derivations for NAND and NOR, under each assignment of logical values to the functional arguments and , produces the identical patterns of functional values for as for , and for as for . 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 lawsIn formal logic, De Morgan's laws are rules relating the logical operators "and" and "or" in terms of each other via negation, namely:-Formal definition:In propositional calculus form:where:* is the negation operator...
.
Applications
Truth tables can be used to prove many other
logical equivalenceIn logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other....
s. For example, consider the following truth table:
Logical Equivalence : (p → q) = (¬p ∨ q)
| p |
q |
¬p |
¬p ∨ q |
p → q |
| T |
T |
F |
T |
T |
| T |
F |
F |
F |
F |
| F |
T |
T |
T |
T |
| F |
F |
T |
T |
T |
This demonstrates the fact that
p →
q is logically equivalent to ¬
p ∨
q.
Truth table for most commonly used logical operators
Here is a truth table giving definitions of the most commonly used 6 of the 16 possible truth functions of 2 binary variables (P,Q are thus boolean variables):
| |
|
|
|
|
|
|
|
|
| T |
T |
T |
T |
F |
T |
T |
T |
T |
| T |
F |
F |
T |
T |
F |
F |
T |
F |
| F |
T |
F |
T |
T |
F |
T |
F |
F |
| F |
F |
F |
F |
F |
T |
T |
T |
T |
Key:
- T = true, F = false = AND
In logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
(logical conjunction) = ORIn logic and mathematics, or, also known as logical disjunction or inclusive disjunction, is a logical operator that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are true. In grammar, or is a...
(logical disjunction) = XOR (exclusive or) = XNOR (exclusive nor) = conditional "if-then" = conditional "(then)-if"
biconditional or "if-and-only-if"In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements. In that it is biconditional, the connective can be likened to the standard material conditional combined with its reverse ; hence the name...
is
logically equivalentIn logic, statements p and q are logically equivalent if they have the same logical content.Syntactically, p and q are equivalent if each can be proved from the other....
to : XNOR (exclusive nor).
Logical operators can also be visualized using
Venn diagramVenn diagrams or set diagrams are diagrams that show all hypothetically possible logical relations between a finite collection of sets . Venn diagrams were conceived around 1880 by John Venn...
s.
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 logicBoolean logic is a complete system for logical operations, used in many systems. It was named after George Boole, who first defined an algebraic system of logic in the mid 19th century. Boolean logic has many applications in electronics, computer hardware and software, and is the base of all...
uses this condensed truth table notation:
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 functionality of hardware look-up tables (LUTs) in
digital logic circuitryDigital electronics are systems that represent signals as discrete levels, rather than as a continuous range. In most cases the number of states is two, and these states are represented by two voltage levels: one near to zero volts and one at a higher level depending on the supply voltage in use...
. 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
bitIn computing and telecommunications a bit is a basic unit of information storage and communication . It is the maximum amount of information that can be stored by a device or other physical system that can normally exist in only two distinct states...
in a
binary numberThe binary numeral system, or base-2 number system represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
, truth table values can be efficiently encoded as
integerThe integers are natural numbers including 0 and their negatives . They are numbers that can be written without a fractional or decimal component, and fall within the set {.....
values in
electronic design automation (EDA)Electronic Design Automation is the category of tools for designing and producing electronic systems ranging from printed circuit boards to integrated circuits. This is sometimes referred to as ECAD or just CAD...
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
kth bit of the integer. For example, to evaluate the output value of a LUT given an array of
n boolean input values, the bit index of the truth table's output value can be computed as follows: if the
ith input is true, let V
i = 1, else let V
i = 0. Then the
kth bit of the binary representation of the truth table is the LUT's output value, where
k = V0*2^0 + V1*2^1 + V2*2^2 + ... + V
n*2^
n.
Truth tables are a simple and straightforward way to encode boolean functions, however given the
exponential growthExponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
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 diagramIn the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...
s.
Applications of truth tables in digital electronics
In digital electronics (and computer science, fields of engineering derived from applied logic and math), truth tables can be used to reduce basic boolean operations to simple correlations of inputs to outputs, without the use of logic gates or code. For example, a binary addition can be represented with the truth table:
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
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.
In this case it can only be used for very simple inputs and outputs, such as 1's and 0's, 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 2x2, or four. So the result is four possible outputs of C and R. If one was to use base 3, the size would increase to 3x3, 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:
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
See also
Basic logical operators
- Exclusive disjunction
The logical operation exclusive disjunction, also called exclusive or , is a type of logical disjunction on two operands that results in a value of true if exactly one of the operands has a value of true...
- Logical conjunction
In logic and mathematics, logical conjunction or and is a two-place logical connective that has the value true if both of its operands are true, otherwise a value of false.-Notation:...
- Logical disjunction
In logic and mathematics, or, also known as logical disjunction or inclusive disjunction, is a logical operator that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are true. In grammar, or is a...
- Logical equality
Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus...
- Logical implication
In logic and mathematics, logical implication is a logical relation that holds between a set T of formulae and a formula B when every model of T is also a model of B. In symbols,# ,# #...
- Logical NAND
- Logical NOR
In boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
- Negation
In logic and mathematics, negation is an operation on propositions. For example, in classical logic negation is normally interpreted by the truth function that takes truth to falsity and vice versa...
(Inverter)
Related topics
- Ampheck
- Binary decision diagram
In the field of computer science, a binary decision diagram or branching program, like a negation normal form or a propositional directed acyclic graph , is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed...
- Boolean algebra (logic)
- Boolean algebra topics
- Boolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true. In mathematics and theoretical computer science, a Boolean domain is usually written as {0,1} or ....
- Boolean function
In mathematics, a Boolean function is a function of the form f : Bk → B, where B = {0, 1} is a Boolean domain and k is a nonnegative integer called the arity of the function...
- Boolean-valued function
A boolean-valued function, in some usages is a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain....
- Excitation table
In electronics design, an excitation table shows the minimum inputs that are necessary to generate a particular next state when the current state is known...
- Espresso heuristic logic minimizer
- First-order logic
First-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
- Karnaugh maps
- Logical connective
In logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the compound sentence produced has a truth value dependant on the respective truth values of the original sentences.Each logical connective can be expressed as a...
- Logical graph
A logical graph is a special type of diagramatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic....
- Logical value
In logic and mathematics, a logical value, also called a truth value, is a value indicating the relation of a proposition to truth.In classical logic, the truth values are true and false...
- Minimal negation operator
In logic and mathematics, the minimal negation operator is a multigrade operator where each is a k-ary boolean function defined in such a way that if and only if exactly one of the arguments is 0....
- Multigrade operator
In logic and mathematics, a multigrade operator is a parametric operator with parameter k in the set N of non-negative integers....
- Operation
In its simplest meaning in mathematics and logic, an operation is an action or procedure which produces a new value from one or more input values. There are two common types of operations: unary and binary. Unary operations involve only one value, such as negation and trigonometric functions...
- Parametric operator
In logic and mathematics, a parametric operator with parameter in the parametric set is a indexed family of operators with index in the index set .-See also:* Operation* Operator* Multigrade operator...
- Propositional calculus
In logic and mathematics, a propositional calculus or logic is a formal system in which formulae representing propositions can be formed by combining atomic propositions using logical connectives, and a system of formal proof rules allows certain formulae to be established as theorems.-...
- Sole sufficient operator
Further reading
- Enderton, H. (2001). A Mathematical Introduction to Logic, second edition, Harcourt Academic Press. ISBN 0-12-238452-0
- Quine, W.V. (1982), Methods of Logic, 4th edition, Harvard University Press, Cambridge, MA.
External links