How do i prove that Is {$↔,⊕$} not a complete set ? I have no clue how to prove it .
$\begingroup$
$\endgroup$
Prove by induction that any formula using only these connectives is affine, that is, has one of the following forms: $$ x_{i_1} \oplus \cdots \oplus x_{i_\ell}, \\ x_{i_1} \oplus \cdots \oplus x_{i_\ell} \oplus 1. $$ Then show that there are functions not expressible in this form.
answered Sep 16 '19 at 15:12
-
$\begingroup$ Suppose B = ($x_1 ⊕ x_2 $)$↔$($y_1 ⊕ y_2$) , How do i prove that B can be written in one of the two forms you mentioned ? $\endgroup$ – user109629 Sep 16 '19 at 15:24
-
1$\begingroup$ I’m afraid that’s something you’ll have to figure out on your own. $\endgroup$ – Yuval Filmus Sep 16 '19 at 15:24
-
$\begingroup$ If you help me in this step then probably induction step will be over .Can you give slightest hint ? $\endgroup$ – user109629 Sep 16 '19 at 15:26
-
1$\begingroup$ Unfortunately, I’m not willing to do your homework. I already gave you a huge hint. $\endgroup$ – Yuval Filmus Sep 16 '19 at 15:27
-
$\begingroup$ I did using induction , do you know any other method .Knowing more than one method always helps ! $\endgroup$ – user109629 Sep 16 '19 at 16:13
$\begingroup$
$\endgroup$
The universal method to check whether a set of connectives is complete in this sense is Post's classes: there are 5 function classes such that a set of functions is complete iff it isn't a subset of any of these 5. One of the 5 is affine functions, as described in Yuval's answer; the rest are monotone, self-dual, 0-preserving, and 1-preserving functions.
It's pretty easy to show that all 5 classes are closed: any composition of functions from one of them will also belong to the same class. So if your set is a subset of a Post's class, it can't be complete. Showing the other direction is more complicated, but likely you'll learn the proof in the near future.
-
$\begingroup$ I seriously doubt the OP will learn this proof in the near future. $\endgroup$ – Yuval Filmus Sep 16 '19 at 18:12
