0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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 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 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 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 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 at 16:13
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I seriously doubt the OP will learn this proof in the near future. $\endgroup$ – Yuval Filmus Sep 16 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy