0
$\begingroup$

Prove that any boolean function (of any number of arguments) could be written using this three functions:

$1. x \leftrightarrow y$ $-$ equivalence ,

$2. x \oplus y$ $-$ addition modulo 2 (exclusive or)

$3.maj(x,y,z)$ - majority function, which returns the most common number between $x,y,z$

$\endgroup$

closed as off-topic by Parcly Taxel, Stefan4024, José Carlos Santos, kimchi lover, Rolf Hoyer Dec 8 '17 at 23:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Parcly Taxel, Stefan4024, José Carlos Santos, kimchi lover, Rolf Hoyer
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Do you already know some other functionally complete sets of Boolean operators? Pick such a set, and show that each of its members can be realized using the three tools you have available here. $\endgroup$ – Henning Makholm Nov 26 '17 at 22:27
  • $\begingroup$ OK, according to the Wikipedia i need to realize all from $\{\wedge,\lor,\neg,\rightarrow,\leftrightarrow\}$ using $\{\leftrightarrow, \oplus, maj\}$. But actually it is enough to realize only $\neg$ and one of $\{\wedge,\lor,\rightarrow\}$. So $\neg A:= maj(A \leftrightarrow A, A \oplus (A \leftrightarrow A), A \oplus (A \leftrightarrow A))$ and $A\lor B:=maj(A \oplus (\neg A),A,B)$. And all is done, am i right? $\endgroup$ – qHedg Nov 27 '17 at 1:05
  • $\begingroup$ You can also get $\neg A$ as $(A\leftrightarrow A)\oplus A$. $\endgroup$ – paw88789 Nov 27 '17 at 1:10
  • $\begingroup$ Yes, and also i can simplify $A\lor B:=maj(A \leftrightarrow A,A,B)$. $\endgroup$ – qHedg Nov 27 '17 at 1:17
  • $\begingroup$ @qHedg Of course, this argument only goes through if you've already established that $\{\neg,\lor\}$ is a functionally complete set. Last I checked, "Because Wikipedia said so" is not a valid proof step nor likely to be accepted by someone marking the answer. $\endgroup$ – Derek Elkins Nov 27 '17 at 1:28
1
$\begingroup$

We consider $\{\wedge,\lor,\neg,\rightarrow,\leftrightarrow\}$ a basic "functionally complete set" (i.e. set of boolean operators, combinations of which give us any possible boolean function) and hence our goal is to realize all from $\{\wedge,\lor,\neg,\rightarrow,\leftrightarrow\}$ using $\{\leftrightarrow, \oplus, maj\}$.

But it is enough to realize only $\neg$ and one of $\{\wedge,\lor,\rightarrow\}$, because

$A \to B := \neg A \lor B$,

$A \leftrightarrow B := (A \to B) \land (B \to A)$,

$A \lor B := \neg(\neg A \land \neg B)$,

$A \vee B := \neg A \rightarrow B$.

So we check (via truth table) that

$\neg A:= maj((A \leftrightarrow A) \oplus A))$,

$A\lor B:=maj(A \leftrightarrow A,A,B)$.

And we are done.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.