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?
Asked
Active
Viewed 1,292 times
1
-
2What other sets? – Mauro ALLEGRANZA Jan 19 '21 at 11:30
-
1Yes, the basic tool is to show that other connectives are reducible to these three – Mauro ALLEGRANZA Jan 19 '21 at 11:31
-
1Even ${\lnot,\land}$ is complete, because $a\lor b=\lnot(\lnot a\land\lnot b)$. – Jan 19 '21 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 '21 at 11:41
-
1See this post – Mauro ALLEGRANZA Jan 19 '21 at 11:55
3 Answers
1
Hint: every Boolean formula can be written in CNF (conjunctive normal form) or DNF (disjunctive normal form), quite constructively.
Henno Brandsma
- 242,131
1
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.$$
0
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.
Prime Mover
- 5,005