# Prove that the set {¬,∧,∨} is functionally complete.

So far I have been using the given set to prove the functional completeness of other sets, but I don't know how to prove this one. That seems to be the case for similar questions too.Do I need to construct the truth table with every connective and build their equivalent with 3 given connectives?

• What other sets? – Mauro ALLEGRANZA Jan 19 at 11:30
• Yes, the basic tool is to show that other connectives are reducible to these three – Mauro ALLEGRANZA Jan 19 at 11:31
• Even $\{\lnot,\land\}$ is complete, because $a\lor b=\lnot(\lnot a\land\lnot b)$. – Yves Daoust Jan 19 at 11:32
• Sorry if the description is unclear.We used to prove the functional completeness of other sets({→,¬},for example) by assuming,that the set in the title was functionally correct. – Tabris Jan 19 at 11:41
• See this post – Mauro ALLEGRANZA Jan 19 at 11:55

## 3 Answers

The way I addressed this problem was to demonstrate that each of the 16 possible truth functions on 2 variables was derivable using the set of connectives provided. You can cut corners on that by demonstrating equivalence of various combinations of those connectives with other connectives, e.g. showing that $$\lnot$$ and $$\land$$ can make $$\lor$$, and hence exclusive or, equivalence, various implications, and so on.

But first it makes sense to establish exactly what those 16 possible truth functions are, which can be done using a table of some kind, and (if you care to) describing what connective (or combination of connectives) give rise to each one.

When you've done that exhaustively for some subset of connectives, then you can work out how to replace certain connectives with those of a smaller subset, until you have reached the subset you are expected to demonstrate is complete.

Hint: every Boolean formula can be written in CNF (conjunctive normal form) or DNF (disjunctive normal form), quite constructively.

There are only $$16$$ possible boolean functions of two arguments. They have the outputs

$$0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111.$$

From these, we can withdraw those that are independent of one or two arguments. Remain

$$0001,0010,0100,0110,0111,1000,1001,1011,1101,1110.$$

We can also withdraw those obtained by negation.

$$0001,0010,0100,0110,1000.$$

These can be synthetized as

$$a\land b,a\land\lnot b,\lnot a\land b,(a\land\lnot b)\lor(\lnot a\land b),\lnot a\land \lnot b.$$