Truth function

In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: the input and output of a truth function are all truth values; a truth function will always output exactly one truth value, and inputting the same truth value(s) will always output the same truth value. The typical example is in propositional logic, wherein a compound statement is constructed using individual statements connected by logical connectives; if the truth value of the compound statement is entirely determined by the truth value(s) of the constituent statement(s), the compound statement is called a truth function, and any logical connectives used are said to be truth functional. Classical propositional logic is a truth-functional logic, in that every statement has exactly one truth value which is either true or false, and every logical connective is truth functional (with a correspondent truth table), thus every compound statement is a truth function. On the other hand, modal logic is non-truth-functional.

In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: the input and output of a truth function are all truth values; a truth function will always output exactly one truth value, and inputting the same truth value(s) will always output the same truth value. The typical example is in propositional logic, wherein a compound statement is constructed using individual statements connected by logical connectives; if the truth value of the compound statement is entirely determined by the truth value(s) of the constituent statement(s), the compound statement is called a truth function, and any logical connectives used are said to be truth functional. Classical propositional logic is a truth-functional logic, in that every statement has exactly one truth value which is either true or false, and every logical connective is truth functional (with a correspondent truth table), thus every compound statement is a truth function. On the other hand, modal logic is non-truth-functional. distributivity: A connective denoted by · distributes over another connective denoted by +, if a · (b + c) = (a · b) + (a · c) for all operands a, b, c. idempotence: Whenever the operands of the operation are the same, the connective gives the operand as the result. In other words, the operation is both truth-preserving and falsehood-preserving (see below). absorption: A pair of connectives \land, \lor satisfies the absorption law if a\land(a\lor b)=a\lor(a\land b)=a for all operands a, b. A set of truth functions is functionally complete if and only if for each of the following five properties it contains at least one member lacking it: monotonic: If f(a 1 , ..., a n ) ≤ f(b 1 , ..., b n ) for all a 1 , ..., a n , b 1 , ..., b n ∈ {0,1} such that a 1 ≤ b 1 , a 2 ≤ b 2 , ..., a n ≤ b n . E.g., \vee, \wedge, \top, \bot . affine: For each variable, changing its value either always or never changes the truth-value of the operation, for all fixed values of all other variables. E.g., \neg, \leftrightarrow , \not\leftrightarrow, \top, \bot . self dual: To read the truth-value assignments for the operation from top to bottom on its truth table is the same as taking the complement of reading it from bottom to top; in other words, f(¬a 1 , ..., ¬a n ) = ¬f(a 1 , ..., a n ). E.g., \neg . truth-preserving: The interpretation under which all variables are assigned a truth value of true produces a truth value of true as a result of these operations. E.g., \vee, \wedge, \top, \rightarrow, \leftrightarrow, \subset . (see validity) falsehood-preserving: The interpretation under which all variables are assigned a truth value of false produces a truth value of false as a result of these operations. E.g., \vee, \wedge, \nleftrightarrow, \bot, \not\subset, \not\supset . (see validity) A concrete function may be also referred to as an operator. In two-valued logic there are 2 nullary operators (constants), 4 unary operators, 16 binary operators, 256 ternary operators, and 2^{2^n} n-ary operators. In three-valued logic there are 3 nullary operators (constants), 27 unary operators, 19683 binary operators, 7625597484987 ternary operators, and 3^{3^n} n-ary operators. In k-valued logic, there are k nullary operators, k^k unary operators, k^{k^2} binary operators, k^{k^3} ternary operators, and k^{k^n} n-ary operators. An n-ary operator in k-valued logic is a function from \mathbb{Z}_k^n \to \mathbb{Z}_k . Therefore, the number of such operators is |\mathbb{Z}_k|^ = k^{k^n} , which is how the above numbers were derived. However, some of the operators of a particular arity are actually degenerate forms that perform a lower-arity operation on some of the inputs and ignore the rest of the inputs. Out of the 256 ternary Boolean operators cited above, \binom{3}{2}\cdot 16 - \binom{3}{1}\cdot 4 + \binom{3}{0}\cdot 2 of them are such degenerate forms of binary or lower-arity operators, using the inclusion–exclusion principle. The ternary operator f(x,y,z)=\lnot x is one such operator which is actually a unary operator applied to one input, and ignoring the other two inputs. "Not" is a unary operator, it takes a single term (¬P). The rest are binary operators, taking two terms to make a compound statement ( ). The set of logical operators may be partitioned into disjoint subsets as follows: \Omega = \Omega_0 \cup \Omega_1 \cup \ldots \cup \Omega_j \cup \ldots \cup \Omega_m \,. In this partition, \Omega_j is the set of operator symbols of arity . In the more familiar propositional calculi, \Omega is typically partitioned as follows: nullary operators: \Omega_0 = \{\bot, \top \} unary operators: \Omega_1 = \{ \lnot \} binary operators: \Omega_2 \supset \{ \land, \lor, \rightarrow, \leftrightarrow \} f nand (T,T) = F; f nand (T,F) = f nand (F,T) = f nand (F,F) = T Then, for convenience, f not , f or f and and so on are defined by means of f nand : f not (x) = f nand (x,x) f or (x,y) = f nand (f not (x), f not (y)) f and (x,y) = f not (f nand (x,y)) or, alternatively f not , f or f and and so on are defined directly: f not (T) = F; f not (F) = T; f or (T,T) = f or (T,F) = f or (F,T) = T; f or (F,F) = F f and (T,T) = T; f and (T,F) = f and (F,T) = f and (F,F) = F Then etc. Thus if S is a sentence that is a string of symbols consisting of logical symbols v 1 ...v n representing logical connectives, and non-logical symbols c 1 ...c n , then if and only if have been provided interpreting v 1 to v n by means of f nand (or any other set of functional complete truth-functions) then the truth-value of is determined entirely by the truth-values of c 1 ...c n , i.e. of . In other words, as expected and required, S is true or false only under an interpretation of all its non-logical symbols. PROP = \{p_1,p_2,\dots\} We define a truth assignment to be any function \phi:PROP\to \{T,F\} . A truth assignment is therefore an association of each propositional variable with a particular truth value. This is effectively the same as a particular row of a proposition's truth table. For a truth assignment, \phi , we define its extended truth assignment, \overline\phi , as follows. This extends \phi to a new function \overline \phi which has domain equal to the set of all propositional formulas. The range of \overline\phi is still \{T,F\} . If A \in PROP then \overline\phi(A) = \phi(A) . If A and B are any propositional formulas, then \overline\phi(\neg A) = f_{\text{not}} (\overline\phi(A)) . \overline\phi(A\land B) = f_{\text{and}} (\overline\phi(A),\overline\phi(B)) . \overline\phi(A\lor B) = f_{\text{or}} (\overline\phi(A),\overline\phi(B)) . \overline\phi(A\to B) = \overline\phi(\neg A\lor B) . \overline\phi(A\leftrightarrow B) = \overline\phi((A\to B)\land (B\to A)) . Finally, now that we have defined the extended truth assignment, we can use this to define the truth-function of a proposition. For a proposition, A, its truth function, f_A , has domain equal to the set of all truth assignments, and range equal to \{T,F\} . It is defined, for each truth assignment \phi , by f_A(\phi) = \overline\phi(A) . The value given by \overline\phi(A) is the same as the one displayed in the final column of the truth table of A, on the row identified with \phi .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1358780673 under CC BY-SA 4.0; modifications have been made.