# Definition:Definable Truth Function

Jump to navigation
Jump to search

## Definition

Let $f: \Bbb B^n \to \Bbb B$ be a truth function.

Let $S$ be a set of truth functions.

Then $f$ is **definable from $S$** if and only if there exist:

- a truth function $g: \Bbb B^m \to \Bbb B$, obtained by composition of truth functions from $S$
- an injection $i: \Bbb B^n \to \Bbb B^m$

such that:

- $f = g \circ i$

This article is complete as far as it goes, but it could do with expansion.In particular: exampleYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Expand}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

## Also known as

Some sources refer to $f$ being **defined from $S$**.

## Also see

## Sources

- 2012: M. Ben-Ari:
*Mathematical Logic for Computer Science*(3rd ed.) ... (previous) ... (next): $\S 2.4.2$