Truth function
|
|
In logic a truth function is a connective for which the truth value is determined systematically by the values of the statements it connects. Well known truth functions include the connectives or, and, not, nor, if... then, iff.
A statement or proposition is said to be truth-functional if its truth value is determined by the truth values of its components.
For example, since "Paul Martin was Prime Minister of Canada on April 20 2004." is true, and "George Bush was President of the USA on April 20 2004." is also true, the conjunction:
- "Paul Martin was Prime Minister of Canada and George Bush was President of the USA on April 20 2004."
is true. In this sentence, "and" serves as a truth function.
In contrast, there is no such correlation between "Al Gore was President of the USA on April 20 2004." and "Britney Spears believes Al Gore was President of the USA on April 20 2004.". Knowing that the former is false does not reveal the truth value of the latter: Britney Spears might or might not believe that Al Gore was President, and the fact that Al Gore was not President on that date is not required to affect the truth value. Thus, the word 'believes' is not a truth function.
In more mathematical terms, a truth function is a type of Boolean function, and using Boolean variables to hold the results of truth functions is a common practice in computer science. Determining the truth of statements is a fundamental act of both logic and mathematics; as a result, truth functions are commonly discussed in works concerned with the basis of logic and mathematics:
See also
- Tractatus Logico-Philosophicus, proposition (5.101) .
- Russell and Whitehead's Principia Mathematica (second edition)
- Alonzo Church, Introduction to Mathematical Logic 1944.
The values of simple truth functions such as AND, NOT, etc., may be determined by a truth table. More complex truth functions may require significant computation.
Mathematical definition
A truth function may be defined as a function that returns one of two values, one of which is interpreted as "true", and the other which is interpreted as "false". Typically either "T" and "F" are used, or "1" and "0", respectively. Using the latter, we can write
<math>f : \{0,1\}^n \rightarrow \{0,1\}<math>
defines a truth function. That is, is a mapping from any number n of true/false (0 or 1) values to a single value, which is 0 or 1.
History
Alonzo Church 1944. Introduction to Mathematical Logic. ISBN 0-691-02906-7 The history of the usage of truth function is covered, among other terms, in the Introduction chapter.