Truth function

Last updated

In logic, a truth function [1] 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. [2]

Contents

Classical propositional logic is a truth-functional logic, [3] 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. [4] On the other hand, modal logic is non-truth-functional.

Overview

A logical connective is truth-functional if the truth-value of a compound sentence is a function of the truth-value of its sub-sentences. A class of connectives is truth-functional if each of its members is. For example, the connective "and" is truth-functional since a sentence like "Apples are fruits and carrots are vegetables" is true if, and only if each of its sub-sentences "apples are fruits" and "carrots are vegetables" is true, and it is false otherwise. Some connectives of a natural language, such as English, are not truth-functional.

Connectives of the form "x believes that ..." are typical examples of connectives that are not truth-functional. If e.g. Mary mistakenly believes that Al Gore was President of the USA on April 20, 2000, but she does not believe that the moon is made of green cheese, then the sentence

"Mary believes that Al Gore was President of the USA on April 20, 2000"

is true while

"Mary believes that the moon is made of green cheese"

is false. In both cases, each component sentence (i.e. "Al Gore was president of the USA on April 20, 2000" and "the moon is made of green cheese") is false, but each compound sentence formed by prefixing the phrase "Mary believes that" differs in truth-value. That is, the truth-value of a sentence of the form "Mary believes that..." is not determined solely by the truth-value of its component sentence, and hence the (unary) connective (or simply operator since it is unary) is non-truth-functional.

The class of classical logic connectives (e.g. &, ) used in the construction of formulas is truth-functional. Their values for various truth-values as argument are usually given by truth tables. Truth-functional propositional calculus is a formal system whose formulae may be interpreted as either true or false.

Table of binary truth functions

In two-valued logic, there are sixteen possible truth functions, also called Boolean functions, of two inputs P and Q. Any of these functions corresponds to a truth table of a certain logical connective in classical logic, including several degenerate cases such as a function not depending on one or both of its arguments. Truth and falsehood are denoted as 1 and 0, respectively, in the following truth tables for sake of brevity.

Contradiction/False
NotationEquivalent
formulas
Truth tableVenn diagram

"bottom"
P ¬P
Opq
 Q
01
P0   0  0 
1   0  0 
Venn0000.svg
Tautology/True
NotationEquivalent
formulas
Truth tableVenn diagram

"top"
P ¬P
Vpq
 Q
01
P0   1  1 
1   1  1 
Venn1111.svg
Proposition P
NotationEquivalent
formulas
Truth tableVenn diagram
Pp
Ipq
 Q
01
P0   0  0 
1   1  1 
Venn0101.svg
Negation of P
NotationEquivalent
formulas
Truth tableVenn diagram
¬P
~P
Np
Fpq
 Q
01
P0   1  1 
1   0  0 
Venn1010.svg
Proposition Q
NotationEquivalent
formulas
Truth tableVenn diagram
Qq
Hpq
 Q
01
P0   0  1 
1   0  1 
Venn0011.svg
Negation of Q
NotationEquivalent
formulas
Truth tableVenn diagram
¬Q
~Q
Nq
Gpq
 Q
01
P0   1  0 
1   1  0 
Venn1100.svg
Conjunction
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
P & Q
P · Q
P AND Q
P ↛¬Q
¬PQ
¬P ↓ ¬Q
Kpq
 Q
01
P0   0  0 
1   0  1 
Venn0001.svg
Alternative denial
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
P|Q
P NAND Q
P → ¬Q
¬PQ
¬P ¬Q
Dpq
 Q
01
P0   1  1 
1   1  0 
Venn1110.svg
Disjunction
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
P OR Q
P ← ¬Q
¬PQ
¬P ↑ ¬Q
¬(¬P ¬Q)
Apq
 Q
01
P0   0  1 
1   1  1 
Venn0111.svg
Joint denial
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
P NOR Q
P ↚ ¬Q
¬PQ
¬P ¬Q
Xpq
 Q
01
P0   1  0 
1   0  0 
Venn1000.svg
Material nonimplication
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
PQ
PQ
P ¬Q
¬PQ
¬P ↚ ¬Q
Lpq
 Q
01
P0   0  0 
1   1  0 
Venn0100.svg
Material implication
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
PQ
PQ
P ↑ ¬Q
¬PQ
¬P ← ¬Q
Cpq
 Q
01
P0   1  1 
1   0  1 
Venn1011.svg
Converse nonimplication
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
PQ
PQ
P ↓ ¬Q
¬PQ
¬P ↛ ¬Q
Mpq
 Q
01
P0   0  1 
1   0  0 
Venn0010.svg
Converse implication
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
PQ
PQ
P ¬Q
¬PQ
¬P → ¬Q
Bpq
 Q
01
P0   1  0 
1   1  1 
Venn1101.svg
Exclusive disjunction
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
PQ
PQ
P XOR Q
P ¬Q
¬PQ
¬P ↮ ¬Q
Jpq
 Q
01
P0   0  1 
1   1  0 
Venn0110.svg
Biconditional
NotationEquivalent
formulas
Truth tableVenn diagram
PQ
PQ
P XNOR Q
P IFF Q
P ↮ ¬Q
¬PQ
¬P ¬Q
Epq
 Q
01
P0   1  0 
1   0  1 
Venn1001.svg

Functional completeness

Because a function may be expressed as a composition, a truth-functional logical calculus does not need to have dedicated symbols for all of the above-mentioned functions to be functionally complete. This is expressed in a propositional calculus as logical equivalence of certain compound statements. For example, classical logic has ¬P ∨ Q equivalent to P → Q. The conditional operator "→" is therefore not necessary for a classical-based logical system if "¬" (not) and "∨" (or) are already in use.

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: [5]

One element
{↑}, {↓}.
Two elements
, , , , , , , , , , , , , , , , , .
Three elements
, , , , , .

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:

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:

Arity

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 n-ary operators. In three-valued logic there are 3 nullary operators (constants), 27 unary operators, 19683 binary operators, 7625597484987 ternary operators, and n-ary operators. In k-valued logic, there are k nullary operators, unary operators, binary operators, ternary operators, and n-ary operators. An n-ary operator in k-valued logic is a function from . Therefore, the number of such operators is , 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 ignores the rest of the inputs. Out of the 256 ternary boolean operators cited above, of them are such degenerate forms of binary or lower-arity operators, using the inclusion–exclusion principle. The ternary operator 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 (PQ, PQ, PQ, PQ).

The set of logical operators Ω may be partitioned into disjoint subsets as follows:

In this partition, is the set of operator symbols of arity j.

In the more familiar propositional calculi, is typically partitioned as follows:

nullary operators:
unary operators:
binary operators:

Principle of compositionality

Instead of using truth tables, logical connective symbols can be interpreted by means of an interpretation function and a functionally complete set of truth-functions (Gamut 1991), as detailed by the principle of compositionality of meaning. Let I be an interpretation function, let Φ, Ψ be any two sentences and let the truth function fnand be defined as:

Then, for convenience, fnot, forfand and so on are defined by means of fnand:

or, alternatively fnot, forfand and so on are defined directly:

Then

etc.

Thus if S is a sentence that is a string of symbols consisting of logical symbols v1...vn representing logical connectives, and non-logical symbols c1...cn, then if and only if I(v1)...I(vn) have been provided interpreting v1 to vn by means of fnand (or any other set of functional complete truth-functions) then the truth-value of is determined entirely by the truth-values of c1...cn, i.e. of I(c1)...I(cn). In other words, as expected and required, S is true or false only under an interpretation of all its non-logical symbols.

Computer science

Logical operators are implemented as logic gates in digital circuits. Practically all digital circuits (the major exception is DRAM) are built up from NAND, NOR, NOT, and transmission gates. NAND and NOR gates with 3 or more inputs rather than the usual 2 inputs are fairly common, although they are logically equivalent to a cascade of 2-input gates. All other operators are implemented by breaking them down into a logically equivalent combination of 2 or more of the above logic gates.

The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to Turing equivalence.

The fact that all truth functions can be expressed with NOR alone is demonstrated by the Apollo guidance computer.

See also

Notes

  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: 11732. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between and .

Related Research Articles

Logical disjunction Logical connective OR

In logic, disjunction is a logical connective typically notated whose meaning either refines or corresponds to that of natural language expressions such as "or". In classical logic, it is given a truth functional semantics on which is true unless both and are false. Because this semantics allows a disjunctive formula to be true when both of its disjuncts are true, it is an inclusive interpretation of disjunction, in contrast with exclusive disjunction. Classical proof theoretical treatments are often given in terms of rules such as disjunction introduction and disjunction elimination. Disjunction has also been given numerous non-classical treatments, motivated by problems including Aristotle's sea battle argument, Heisenberg's uncertainty principle, as well the numerous mismatches between classical disjunction and its nearest equivalents in natural language.

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.

Logical conjunction Logical connective AND

In logic, mathematics and linguistics, And is the truth-functional operator of logical conjunction; the and of a set of operands is true if and only if all of its operands are true. The logical connective that represents this operator is typically written as or .

Logical connective Symbol connecting sentential formulas in logic

In logic, a logical connective is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary connective can be used to join the two atomic formulas and , rendering the complex formula .

Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions.

Exclusive or True when either but not both inputs are true

Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ.

Negation Logical operation

In logic, negation, also called the logical complement, is an operation that takes a proposition to another proposition "not ", written , or . It is interpreted intuitively as being true when is false, and false when is true. Negation is thus a unary logical connective. It may be applied as an operation on notions, propositions, truth values, or semantic values more generally. In classical logic, negation is normally identified with the truth function that takes truth to falsity. In intuitionistic logic, according to the Brouwer–Heyting–Kolmogorov interpretation, the negation of a proposition is the proposition whose proofs are the refutations of .

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

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. It is logically equivalent to and , where the symbol signifies logical negation, signifies OR, and signifies AND. In grammar, nor is a coordinating conjunction.

Logical biconditional

In logic and mathematics, the logical biconditional, sometimes known as the material biconditional, is the logical connective used to conjoin two statements P and Q to form the statement "P if and only if Q", where P is known as the antecedent, and Q the consequent. This is often abbreviated as "P iff Q". Other ways of denoting this operator may be seen occasionally, as a double-headed arrow, a prefixed E "Epq", an equality sign (=), an equivalence sign (≡), or EQV. It is logically equivalent to both and , and the XNOR boolean operator, which means "both or neither".

Computation tree logic (CTL) is a branching-time logic, meaning that its model of time is a tree-like structure in which the future is not determined; there are different paths in the future, any one of which might be an actual path that is realized. It is used in formal verification of software or hardware artifacts, typically by software applications known as model checkers, which determine if a given artifact possesses safety or liveness properties. For example, CTL can specify that when some initial condition is satisfied, then all possible executions of a program avoid some undesirable condition. In this example, the safety property could be verified by a model checker that explores all possible transitions out of program states satisfying the initial condition and ensures that all such executions satisfy the property. Computation tree logic belongs to a class of temporal logics that includes linear temporal logic (LTL). Although there are properties expressible only in CTL and properties expressible only in LTL, all properties expressible in either logic can also be expressed in CTL*.

Logical equality

Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus. It gives the functional value true if both functional arguments have the same logical value, and false if they are different.

In mathematical logic, a tautology is a formula or assertion that is true in every possible interpretation. An example is "x=y or x≠y". Similarly, "either the ball is green, or the ball is not green" is always true, regardless of the colour of the ball.

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }, consisting of binary conjunction and negation. Each of the singleton sets { NAND } and { NOR } is functionally complete.

Conditioned disjunction

In logic, conditioned disjunction is a ternary logical connective introduced by Church. Given operands p, q, and r, which represent truth-valued propositions, the meaning of the conditioned disjunction [p, q, r] is given by:

In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. The contrapositive of a statement has its antecedent and consequent inverted and flipped.

T-norm fuzzy logics are a family of non-classical logics, informally delimited by having a semantics that takes the real unit interval [0, 1] for the system of truth values and functions called t-norms for permissible interpretations of conjunction. They are mainly used in applied fuzzy logic and fuzzy set theory as a theoretical basis for approximate reasoning.

An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation. The general study of interpretations of formal languages is called formal semantics.

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables. In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, logically valid.

References

Further reading