Truth function: Difference between revisions

Revision as of 04:57, 13 March 2024

Latest revision as of 14:01, 20 August 2025

(11 intermediate revisions by 8 users not shown)

Line 1:

{{Short description|A functionFunction in Classical logic}}

{{Logical connectives sidebar}}

<!-- :''"Truth functional" redirects here. For the truth functional conditional, see [[Material conditional]].''

IMHO by no means the material conditional may not be referred to or abbreviated as the adjective "truth functional", omitting a noun like "conditional" or "implication". Seems more like an internal link spamming rather than an appropriate dab hatnote. --Incnis Mrsi -->

In [[logic]], a '''truth function'''<ref>Roy T. Cook (2009). ''A Dictionary of Philosophical Logic'', p. 294: Truth Function. Edinburgh University Press.</ref> is a [[function (mathematics)|function]] that accepts [[truth value]]s 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 calculus|propositional logic]], wherein a compound statement is constructed using individual statements connected by [[logical connective]]s; 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'''.<ref>Roy T. Cook (2009). ''A Dictionary of Philosophical Logic'', p. 295: Truth Functional. Edinburgh University Press.</ref>

Line 243 ⟶ 245:

A concrete function may be also referred to as an ''operator''. In two-valued logic there are 2 nullary operators (constants), 4 [[unary operation|unary operators]], 16 [[binary operation|binary operators]], 256 [[ternary operation|ternary operators]], and <math>2^{2^n}</math> ''n''-ary operators. In three-valued logic there are 3 nullary operators (constants), 27 [[unary operation|unary operators]], 19683 [[binary operation|binary operators]], 7625597484987 [[ternary operation|ternary operators]], and <math>3^{3^n}</math> ''n''-ary operators. In ''k''-valued logic, there are ''k'' nullary operators, <math>k^k</math> unary operators, <math>k^{k^2}</math> binary operators, <math>k^{k^3}</math> ternary operators, and <math>k^{k^n}</math> ''n''-ary operators. An ''n''-ary operator in ''k''-valued logic is a function from <math>\mathbb{Z}_k^n \to \mathbb{Z}_k</math>. Therefore, the number of such operators is <math>|\mathbb{Z}_k|^{|\mathbb{Z}_k^n|} = k^{k^n}</math>, 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 booleanBoolean operators cited above, <math>\binom{3}{2}\cdot 16 - \binom{3}{1}\cdot 4 + \binom{3}{0}\cdot 2</math> of them are such degenerate forms of binary or lower-arity operators, using the [[inclusion–exclusion principle]]. The ternary operator <math>f(x,y,z)=\lnot x</math> is one such operator which is actually a unary operator applied to one input, and ignoring the other two inputs.

[[Negation|"Not"]] is a [[unary operation|unary operator]], it takes a single term (¬''P''). The rest are [[binary operation|binary operators]], taking two terms to make a compound statement ({{math|''P'' &and; ''Q'', {{wrap}}''P'' &or; ''Q'', {{wrap}}''P'' → ''Q'', {{wrap}}''P'' ↔ ''Q''}}).

The set of logical operators {{math|&Omega;}} may be [[Partition of a set|partitioned]] into disjoint subsets as follows:

Line 264 ⟶ 266:

Instead of using [[truth table]]s, 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 ''{{mvar|I''}} be an interpretation function, let ''{{math|Φ'', ''Ψ''}} be any two sentences and let the truth function ''f''_nand be defined as:

* ''f''_nand(T,T) = F; ''f''_nand(T,F) = ''f''_nand(F,T) = ''f''_nand(F,F) = T

Line 284 ⟶ 286:

| ''I''(&) {{=}} ''I''({{and}}) {{=}} ''f''_and

| ''I''(''v'') {{=}} ''I''({{or-}}) {{=}} ''f''_or

| ''I''(~''Φ'') {{=}} ''I''({{not}}''Φ'') {{=}} ''I''({{not}})(''I''(''Φ'')) {{=}} ''f''_not(''I''(''Φ''))

| ''I''(''Φ''{{and}}''Ψ'') {{=}} ''I''({{and}})(''I''(''Φ''), ''I''(''Ψ'')) {{=}} ''f''_and(''I''(''Φ''), ''I''(''Ψ''))

}}

etc.

Thus if ''S'' is a sentence that is a string of symbols consisting of logical symbols ''v''₁...''v''_''n'' representing logical connectives, and non-logical symbols ''c''₁...''c''_''n'', then if and only if {{math|size=100%|''I''(''v''₁)...''I''(''v''_''n'')}} have been provided interpreting ''v''₁ to ''v''_''n'' by means of ''f''_nand (or any other set of functional complete truth-functions) then the truth-value of {{tmath|I(s)}} is determined entirely by the truth-values of ''c''₁...''c''_''n'', i.e. of {{math|size=100%|''I''(''c''₁)...''I''(''c''_''n'')}}. In other words, as expected and required, ''S'' is true or false only under an interpretation of all its non-logical symbols.

== Definition ==

Using the functions defined above, we can give a formal definition of a proposition's truth function.<ref>{{Cite web |title=An Introduction to Mathematical Logic |url=https://store.doverpublications.com/products/9780486497853?srsltid=AfmBOoo9mFyD06QpIypwYtJnNn2CYOf-Ps2CCwMYl_IgAfLRwgeh7v1s |access-date=2025-02-20 |website=Dover Publications |language=en}}</ref>

Let ''PROP'' be the set of all propositional variables,

: <math> PROP = \{p_1,p_2,\dots\}</math>

We define a '''truth assignment''' to be any function <math>\phi:PROP\to \{T,F\}</math>. 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, <math>\phi</math>, we define its '''extended truth assignment''', <math>\overline\phi</math>, as follows. This extends <math>\phi</math> to a new function <math>\overline \phi</math> which has ___domain equal to the set of all propositional formulas. The range of <math>\overline\phi</math> is still <math>\{T,F\}</math>.

# If <math>A \in PROP</math> then <math>\overline\phi(A) = \phi(A)</math>.

# If ''A'' and ''B'' are any propositional formulas, then

## <math>\overline\phi(\neg A) = f_{\text{not}} (\overline\phi(A))</math>.

## <math>\overline\phi(A\land B) = f_{\text{and}} (\overline\phi(A),\overline\phi(B))</math>.

## <math>\overline\phi(A\lor B) = f_{\text{or}} (\overline\phi(A),\overline\phi(B))</math>.

## <math>\overline\phi(A\to B) = \overline\phi(\neg A\lor B)</math>.

## <math>\overline\phi(A\leftrightarrow B) = \overline\phi((A\to B)\land (B\to A))</math>.

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''', <math>f_A</math>, has ___domain equal to the set of all truth assignments, and range equal to <math>\{T,F\}</math>.

It is defined, for each truth assignment <math>\phi</math>, by <math>f_A(\phi) = \overline\phi(A)</math>. The value given by <math>\overline\phi(A)</math> is the same as the one displayed in the final column of the truth table of ''A'', on the row identified with <math>\phi</math>.

== Computer science ==

Line 296 ⟶ 322:

The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to [[Turing equivalence (theory of computation)|Turing equivalence]].

The fact that all truth functions can be expressed with NOR alone is demonstrated by the [[Apollo guidanceGuidance computerComputer]].

== See also ==