On Non-deterministic Functional Completeness

We introduce N-functional completeness as a natural generalization to non-deterministic matrices of the notion of functional completeness in ordinary (deterministic) matrices. We also provide an effective criterion for N-functional completeness. Then we show that in the two-valued case the set \(\{\to ,\sim \}\) is N-functionally complete, where \({\to }\) is the classical implication, and \({\sim }\) is a unary, non-deterministic, semi-negation. We also present a single ternary two-valued non-deterministic connective which is N-functionally complete, and show that no single binary connective can have this property.