A generalization of truth functional semantics for propositional and first-order deductive systems in which the truth value assigned to a formula is not determined by the values assigned to its subformulae, but rather constrained by them. In other words, an $n$-ary logical connective is interpreted by a function mapping each $n$-tuple of truth values to a set of truth values—the set of ‘legal’ values. More precisely, nondeterministic semantics demands that the value $v\left(\phi \circ \psi \right)$ is merely constrained by the values $v\left(\phi \right)$ and $v\left(\phi \right)$ so that the corresponding constraint on valuations is:

• • $v\left(\phi \circ \psi \right)\in f^{\circ }\left(v\left(\phi \right),v\left(\psi \right)\right)$

A function from formulae to truth values is a valuation if it respects the conditions particular to the deductive system in all cases.