4
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ I mean how to prove it from first principles without using the knowledge of these sets of connectives that are not functionally complete. For example by induction on the construction of a formula for the affine connectives to show that their truth table will always have an even number of true values. $\endgroup$
    – macco
    Aug 21, 2018 at 10:18
  • $\begingroup$ @macco: I don't understand what you're asking. You can't prove anything about anything without using some knowledge of what it is. $\endgroup$
    – hmakholm left over Monica
    Aug 21, 2018 at 10:25
  • $\begingroup$ Ah sorry I didn’t understand your argument. Wow seems like a very easy way to prove that a set is not functionally complete? Just combine every formula formed by a connective in the set with eachother and all their products with eachother and if you don’t end up with a set that is needed for it to be functionally complete then it isn’t? A small example would be great I guess. $\endgroup$
    – macco
    Aug 21, 2018 at 10:30
  • $\begingroup$ @macco: Well, yes, because "all monotonic connectives" happens to be a large enough set already. For example, if you start with just $\{{\land},{\lor}\}$ you're going to end up outside that set when you start combining everything with everything (for example you can make a three-input function, which is not in your original set). You can know you won't get outside the larger set of all monotonic functions, though. $\endgroup$
    – hmakholm left over Monica
    Aug 21, 2018 at 10:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .