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.

A minimal set of operators that can express every statement expressible in the propositional calculus is called a minimal functionally complete set. A minimally complete set of operators is achieved by NAND alone {↑} and NOR alone {↓}.

The following are the minimal functionally complete sets of operators whose arities do not exceed 2:

One element

{↑}, {↓}.

Two elements

{→,¬}, {←,⊥}, {→,↛}, {←,↚}, {↛,⊤}, {↚,↔}.

Three elements

{∨,↮,⊤}, {∧,↮,⊤}.

Some truth functions possess properties which may be expressed in the theorems containing the corresponding connective. Some of those properties that a binary truth function (or a corresponding logical connective) may have are:

• associativity: Within an expression containing two or more of the same associative connectives in a row, the order of the operations does not matter as long as the sequence of the operands is not changed.
• commutativity: The operands of the connective may be swapped without affecting the truth-value of the expression.
• 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 ∨,∧,⊤,⊥.
• 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., ¬.
• 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., 33n n-ary operators. In k-valued logic, there are k nullary operators, kk3 ternary operators, and |ℤk||ℤkn|=kkn, 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, P ∧ Q,P ∨ Q,P → Q,P ↔ Q).

  The set of logical operators Ωj is the set of operator symbols of arity Ω0={⊥,⊤}

  unary operators: I be an interpretation function, let not</sub>\n"},"2":{"wt":" ''I''(&) {{=}} ''I''({{and}}) {{=}} ''f''_and\n"},"3":{"wt":" ''I''(''v'') {{=}} ''I''({{or-}}) {{=}} ''f''_or\n"},"4":{"wt":" ''I''(~Φ) {{=}} ''I''({{not}}Φ) {{=}} ''I''({{not}})(''I''(Φ)) {{=}} ''f''_not(''I''(Φ))\n"},"5":{"wt":" ''I''(Φ{{and}}Ψ) {{=}} ''I''({{and}})(''I''(Φ), ''I''(Ψ)) {{=}} ''f''_and(''I''(Φ), ''I''(Ψ))\n"}},"i":0}}]}">

  • I(~) = I(∨) = for
  • I(~Φ) = I(∧Ψ) = I(⁠ϕ to a new function {T,F}.
    1. If ϕ‾(¬A)=fnot(ϕ‾(A)).
    2. ϕ‾(A→B)=ϕ‾(¬A∨B).
    3. {T,F}.

       It is defined, for each truth assignment ϕ‾(A) is the same as the one displayed in the final column of the truth table of A, on the row identified with

       1. ↑ Roy T. Cook (2009). A Dictionary of Philosophical Logic, p. 294: Truth Function. Edinburgh University Press.
       2. ↑ Roy T. Cook (2009). A Dictionary of Philosophical Logic, p. 295: Truth Functional. Edinburgh University Press.
       3. ↑ Internet Encyclopedia of Philosophy: Propositional Logic, by Kevin C. Klement
       4. ↑ Roy T. Cook (2009). A Dictionary of Philosophical Logic, p. 47: Classical Logic. Edinburgh University Press.
       5. ↑ Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between This article incorporates material from TruthFunction on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

  Further reading

  edit

  • Józef Maria Bocheński (1959), A Précis of Mathematical Logic, translated from the French and German versions by Otto Bird, Dordrecht, South Holland: D. Reidel.
  • Alonzo Church (1944), Introduction to Mathematical Logic, Princeton, NJ: Princeton University Press. See the Introduction for a history of the truth function concept.

  Classical logic