1

I'm stuck with one problem. I have two boolean functions:

$1)$ $x \oplus 1$

$2)$ $x \oplus y \oplus 1$

The question is which of them is self-dual and which is not. I know the definition that one boolean function is self-dual iff it is equivalent to its dual function (i.e. if their outputs are respectively equal). As a result I get that 1) is not self-dual, and 2) is self-dual. When I checked the answer, it claims the absolute opposite - 1) is self-dual and 2) is not. I will show my truth table for case 1):

$1)$ $x \oplus 1$

$x$ $\quad$ $1$ $\quad$ $x \oplus 1$

$0$ $\quad$ $1$ $\qquad$ $1$

$1$ $\quad$ $1$ $\qquad$ $0$

Dual of $x \oplus 1$: $\lnot (\lnot x \oplus 0)$

$\lnot x$ $\quad$ $0$ $\quad$ $\lnot x \oplus 0$ $\quad$ $\lnot (\lnot x \oplus 0)$

$1$ $\quad$ $0$ $\qquad$ $1$ $\qquad \qquad$ $0$

$0$ $\quad$ $0$ $\qquad$ $0$ $\qquad \qquad$ $1$

The one mistake I've made could probably be putting the brackets - maybe negation should be applied before XOR, but then the second function will also be self-dual. I'm a little confused and will be grateful if anyone clarifies this to me. I've used the following definition for dual function:

The dual of $f(x,y,z) \quad$ is $\quad \lnot f(\lnot x, \lnot y, \lnot z)$.

ash975
  • 13
  • I guess only the variables need to be negated, so the dual of 1) could be $\lnot(\lnot x\oplus 1)$. – Berci Jul 28 '21 at 23:25
  • We have to take the dual of constants as well - so 1 switches to 0 and vice versa. It has to be something else that I miss but I can't figure it out. – ash975 Jul 29 '21 at 08:41
  • No, no. The dual of a unary function $f$ is the mapping $x\mapsto \lnot f(\lnot x)$, right? If you apply it for $f(x)=x\oplus1$, the constant $1$ inside the definition of $f$ stays untouched. – Berci Jul 29 '21 at 08:43
  • Yes, that is the mapping. But I also found this: In a dual function:

    AND operator of a given function is changed to OR operator and vice-versa. A constant 1 (or true) of a given function is changed to a constant 0 (or false) and vice-versa; which perplexed me more.

     – ash975 Jul 29 '21 at 14:36

1 Answers1

0

You should only insist the definition you gave at the end of the post: the dual of (a ternary) $f$ is the mapping $$(x,y,z)\mapsto\lnot f(\lnot x,\,\lnot y,\,\lnot z)$$ and analogously for binary or unary functions.

Then the dual of the constant map $x\mapsto 1$ is indeed the constant map $x\mapsto 0$.
The dual of the map $(x,y)\mapsto x\lor y$ is indeed the map $(x,y)\mapsto x\land y$ by the de Morgan laws.

However, when calculating the dual of terms like $f(x)=x\oplus 1$ (which is by the way just $\lnot x$), we don't need to involve the dual of any subterm, just apply the above definition right away to obtain $x\mapsto \lnot(\lnot x\oplus 1))$.

Alternatively, we should indeed arrive to the same conclusion by using the dual of every occuring operation.
Here you can verify that the dual of $\oplus$ is just $\leftrightarrow$, and with that, the dual of $f$ is $x\mapsto (x\leftrightarrow 0)$ which is the same as $x\mapsto\lnot x$ that is the same as $f$.

Berci
  • 90,745