Definition:Definable Truth Function

From ProofWiki
Jump to navigation Jump to search


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$

Also known as

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

Also see