Prove that the monotonic connectives and self dual connectives are not functionally complete

logic

A set of logical connectives is functionally complete if and only if it is not a subset of any of these sets of connectives:

The monotonic connectives, The affine connectives, The self-dual connectives, The truth-preserving connectives, The falsity preserving connectives.

How do I prove that the monotonic connectives are not functionally complete?
How do I prove that the self-dual connectives are not functionally complete?

Proving that the truth-preserving and falsity-preserving connectives are not functionally complete is easy. For proving that the affine connectives are not functionally complete one can show that the truth table will always have an even number of true values under any valuation.

Best Answer

In each case, because the class of monotonic (resp. self-dual) Boolean functions is closed under composition.

This means that every formula you build out of these connectives will itself express a monotonic (or self-dual) function of the free variables.

Since there exists truth functions that are not monotonic (e.g., negation) or self-dual (e.g., conjunction) this shows that not everything can be built from your class.


(This approach works equally for affine or truth-preserving or falsity-preserving functions).