Truth Function - Algebraic Properties

Algebraic Properties

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.
• Absorption: A pair of connectives, satisfies the absorption law if 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₁, ..., a_n) ≤ f(b₁, ..., b_n) for all a₁, ..., a_n, b₁, ..., b_n ∈ {0,1} such that a₁ ≤ b₁, a₂ ≤ b₂, ..., a_n ≤ b_n. E.g., .
• affine: Each variable always makes a difference in the truth-value of the operation or it never makes a difference. E.g., .
• 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₁, ..., ¬a_n) = ¬f(a₁, ..., a_n). 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., ⊂. (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., ⊄, ⊅. (see validity)