# prove that {$↔,⊕$} is incomplete set?

How do i prove that Is {$$↔,⊕$$} not a complete set ? I have no clue how to prove it .

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.

• 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 ? – user109629 Sep 16 '19 at 15:24
• I’m afraid that’s something you’ll have to figure out on your own. – Yuval Filmus Sep 16 '19 at 15:24
• If you help me in this step then probably induction step will be over .Can you give slightest hint ? – user109629 Sep 16 '19 at 15:26
• Unfortunately, I’m not willing to do your homework. I already gave you a huge hint. – Yuval Filmus Sep 16 '19 at 15:27
• I did using induction , do you know any other method .Knowing more than one method always helps ! – user109629 Sep 16 '19 at 16:13

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.

• I seriously doubt the OP will learn this proof in the near future. – Yuval Filmus Sep 16 '19 at 18:12