Definition:Definable Truth Function

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: example You 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

• Definition:Functional Completeness

Sources

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