Truth function
In logic, a truth function is a function that takes one or more truth values—typically true (T) or false (F)—as inputs and produces a single truth value as output, determining the truth of a compound proposition based solely on the truth values of its components.[1] Truth functions form the foundation of classical propositional logic, where standard logical connectives such as negation (~), which reverses the truth value of its single input; conjunction (∧), true only if both inputs are true; disjunction (∨), true if at least one input is true; material implication (→), false only when the first input is true and the second is false; and biconditional (↔), true when both inputs share the same truth value, all operate as truth functions.[2][3] These connectives enable the construction of complex propositions whose overall truth depends mechanically on the atomic propositions' truth values, without regard to their content or context.[1] The behavior of truth functions is systematically represented using truth tables, which list all possible input combinations and the resulting output for a given function, allowing for the evaluation of any propositional formula.[2] For n-ary truth functions, the total number is $2^{2^n}, so there are 2 unary functions, 16 binary functions (corresponding to the 16 possible ways to assign outputs across the 4 input rows of a truth table), and 256 ternary functions.[4][5] Among the binary functions, notable ones include the constant functions (always T or always F), the identity functions (outputting the first or second input), and projections, with the standard connectives like NAND and NOR being functionally complete—meaning any truth function can be expressed using them alone. The development of truth functions traces to the late 19th century, with Gottlob Frege introducing truth values in 1891 as part of his foundational work in logic, though the explicit truth-functional analysis and the first truth table emerged from Charles Sanders Peirce's manuscripts in 1883–1893, where he articulated graphical methods for conditionals equivalent to modern material implication.[6] Ludwig Wittgenstein later popularized truth tables in his 1921 Tractatus Logico-Philosophicus, formalizing their role in analyzing propositional logic.[6] In broader logical systems, truth functions distinguish classical propositional logic from non-truth-functional frameworks, such as modal logic (e.g., "necessarily") or temporal logic (e.g., "until"), where a compound's truth value may depend on modal accessibility, time, or epistemic factors beyond mere input truth values.[1][3]Fundamentals
Definition
In propositional logic, a truth function is formally defined as a function f: \{\top, \bot\}^n \to \{\top, \bot\} for some non-negative integer n, where it maps an n-tuple of truth values assigned to n atomic propositions to a single truth value for the resulting compound proposition.[4] This definition captures the essence of how logical connectives, such as negation or conjunction, operate by determining the overall truth value based exclusively on the truth values of their components.[7] The concept originates from early work in mathematical logic, where Emil Post described such functions as operations that generate compound statements from elementary ones using truth tables to specify their behavior.[8] The domain and codomain of a truth function consist of the classical two-element set of truth values, often denoted as \{0, 1\} (with 1 for true and 0 for false) or \{T, F\} (for true and false), reflecting the bivalent nature of classical propositional logic.[7] These values represent the exhaustive and mutually exclusive possibilities for any proposition, ensuring that the function's output is always definitively true or false without intermediate degrees.[4] Truth functions are distinguished from non-truth-functional operators, such as those involving epistemic modals, because the latter's truth value cannot be computed solely from the truth values of their propositional arguments; instead, they depend on contextual factors like knowledge states or possible worlds.[9] A simple illustrative example is the unary identity truth function of arity 1, defined by f(p) = p, which simply returns the truth value of its single input proposition without alteration.[4] The parameter n specifies the function's arity, or number of inputs, which varies across different connectives and is explored further in the discussion of arity.Arity
In propositional logic, the arity of a truth function refers to the number n of propositional variables, or inputs, on which the function depends to determine its output truth value.[10] The total number of distinct n-ary truth functions is given by the formula $2^{2^n}. This arises because there are $2^n possible combinations of truth values for the n input variables, and for each combination, the function can output either true or false, yielding $2^{2^n} possible functions overall.[10] For example, when n=1 (unary truth functions), there are $2^{2^1} = 4 such functions: the constant true function (always outputs true regardless of input), the constant false function (always outputs false), the identity function (outputs the input value), and the negation function (outputs the opposite of the input value). For n=2 (binary truth functions), there are $2^{2^2} = 16 possible functions, which form a common case in logical analysis. When n=3 (ternary truth functions), the number rises to $2^{2^3} = 256.[10] Constant functions, which output a fixed truth value independent of any inputs, are considered 0-ary truth functions, with exactly two possibilities: the always-true function and the always-false function; these serve as degenerate cases in the study of truth functions.[10]Binary Truth Functions
Classification
Binary truth functions, also known as binary Boolean functions, total 16 possible distinct operations on two inputs, each taking values in {0,1} or {false,true}. These functions are classified into categories based on their logical behavior, reflecting common patterns in propositional logic and digital circuit design. The primary groupings include constant functions, unary-like projections, and proper binary connectives, with standard names assigned to highlight their roles in logical inference and computation.[11] Constant functions form the simplest category: the tautology, which always outputs true regardless of inputs, and the contradiction, which always outputs false. These represent unchanging logical values independent of the arguments. Projection functions, which depend on only one input, include the first projection (output equals the first input) and the second projection (output equals the second input); their negations yield the negation of the first input and negation of the second input, respectively. These four functions effectively reduce binary operations to unary or constant behaviors by ignoring one argument.[11] The remaining 10 functions exhibit true binary dependence and are further subdivided into basic connectives, exclusive operations, implications, and inhibitions. Basic connectives encompass conjunction (AND, true only when both inputs are true), disjunction (OR, true when at least one input is true), the Sheffer stroke (NAND, the negation of AND), and the Peirce arrow (NOR, the negation of OR). Exclusive operations include exclusive or (XOR, true when inputs differ) and its negation, exclusive nor (XNOR or equivalence, true when inputs are equal). Implication functions cover material implication (A implies B, false only when A is true and B is false) and its converse (B implies A, false only when B is true and A is false). Inhibition functions include A inhibits B (true when A is true and B is false) and B inhibits A (true when B is true and A is false). These names, such as AND and OR, originated in early 20th-century logic but were systematized in Boolean algebra contexts.[11] A key property in classification is logical monotonicity, where a function is monotone if increasing any input (from false to true) does not decrease the output. Among the 16 binary functions, 14 are monotone, including all constants, projections, negations of projections (when considering appropriate orderings), AND, OR, NAND, NOR, implications, and inhibitions; the exceptions are XOR and XNOR, which are non-monotone due to their sensitivity to input parity. This distinction is crucial for applications in optimization and learning, as monotone functions preserve orderings in lattices.[12] Historically, the Sheffer stroke (NAND) gained prominence through Henry M. Sheffer's 1913 paper, which demonstrated its functional completeness for expressing all Boolean operations, influencing the development of minimal axiom systems for Boolean algebra.[13]Truth Table
A truth table provides a complete enumeration of all possible binary truth functions by specifying their outputs for every combination of input truth values. For two propositions p and q, each of which can be true (T) or false (F), there are four input combinations: TT, TF, FT, and FF. This yields $2^4 = 16 distinct binary truth functions, each uniquely identified by an index from 0 to 15 based on the binary encoding of its output vector (where T corresponds to 1 and F to 0, read from FF to TT, with FF as the least significant bit). Standard names are assigned to several functions, such as FALSE for the constant false function and AND for the conjunction.[14] To interpret the table, examine the input rows for [p](/page/P′′) and [q](/page/Q), followed by columns for each function f_i (where i = 0 to 15). The entry in row j and column f_i gives the output of that function for the corresponding input pair. For instance, the function at index 1 (AND) yields T only for the TT input and F otherwise, matching the behavior of [p](/page/P′′) \land [q](/page/Q). Similarly, index 7 (OR) outputs T for all inputs except FF, as in [p](/page/P′′) \lor [q](/page/Q).[14] Common logical notations include \land for AND (conjunction), \lor for OR (disjunction), and \lnot for negation (NOT), which appear in symbolic representations of these functions; for example, the XOR function at index 6 corresponds to (p \land \lnot q) \lor (\lnot p \land q).[14] Truth functions are extensional, defined solely by their truth tables regardless of the syntactic formulas used to express them.[15]| p | q | f_0 (FALSE) | f_1 (AND) | f_2 (p AND NOT q) | f_3 (p) | f_4 (NOT p AND q) | f_5 (q) | f_6 (XOR) | f_7 (OR) | f_8 (NOR) | f_9 (XNOR) | f_{10} (NOT q) | f_{11} (p OR NOT q) | f_{12} (NOT p) | f_{13} (NOT p OR q) | f_{14} (NAND) | f_{15} (TRUE) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | T | F | T | F | T | F | T | F | T | F | T | F | T | F | T | T | T |
| T | F | F | F | T | T | F | F | T | T | F | F | T | T | F | T | T | T |
| F | T | F | F | F | F | T | T | T | T | F | F | F | F | T | T | T | T |
| F | F | F | F | F | F | F | F | F | F | T | T | T | T | T | F | T | T |