2
$\begingroup$

I'm currently trying to understand a step in the proof for in the Crama and Hammer book on Boolean Functions. The proof is Proposition 4.12, which claims that the self-dualization of Boolean $f$ is bijective.

The specific statement that I am confused about is a step showing that:

$$f^d(X)f(X) \lor f(X) \bar{x}_{n+1} \lor f^d(X) {x}_{n+1} = f(X) \bar{x}_{n+1} \lor f^d(X) {x}_{n+1}.$$

Here $f(X)$ is a d-dimensional Boolean function, $X = (x_1,x_2,\ldots, x_n) \in \mathcal{B}^n$, and $f^d(X) := \overline{f(\overline{X})}$ is the dual of $f$.

This equality above seems to require that $f^d(X)f(X) = 0.$ I am wondering why this is? I think that I am missing something simple, or maybe I've found a typo in the proof. If someone has a different proof for the broader claim that self-dualization is bijective, that would be fine.


I've copied the full proposition below in case it helps:

Proposition 4.12

Here $f^{SD}(X)$ is the self-dual extension of $f$. This is a function over the (d+1)-dimensional Boolean hypercube such that $$f^{SD}(x_1,x_2,\ldots, x_n, x_{n+1}) = f(x_1,x_2,\ldots, x_n)\bar{x}_{n+1} \lor f^d(x_1,x_2,\ldots, x_n)\bar{x}_{n+1}.$$

$\endgroup$
3
  • 1
    $\begingroup$ Your question is hard to answer without the requisite definitions. What is $f^d$? What is $f^{SD}$? $\endgroup$ Mar 16, 2022 at 7:19
  • 1
    $\begingroup$ Dual for conjunction is disjunction, but both are true for true arguments. $\endgroup$
    – zkutch
    Mar 16, 2022 at 12:10
  • $\begingroup$ please edit your question and put the definitions into the text $\endgroup$
    – kodlu
    Mar 16, 2022 at 14:13

1 Answer 1

4
$\begingroup$

$$f^d(X)f(X) \lor f(X) \bar{x}_{n+1} \lor f^d(X) {x}_{n+1} = f(X) \bar{x}_{n+1} \lor f^d(X) {x}_{n+1}$$ The equality above comes from the general equality below. It has nothing to do with the context.

$\begin{aligned} &\quad\ yz\lor y\overline{x_{n+1}} \lor z{x}_{n+1}\\ &=yz(\overline{x_{n+1}} \lor x_{n+1})\lor y\bar{x}_{n+1} \lor z{x}_{n+1}\\ &=(yz\overline{x_{n+1}} \lor yzx_{n+1})\lor y\bar{x}_{n+1} \lor z{x}_{n+1}\\ &=(yz\overline{x_{n+1}}\lor y\bar{x}_{n+1})\lor (yzx_{n+1}\lor z{x}_{n+1})\\ &=y\bar{x}_{n+1}\lor z{x}_{n+1}\\ \end{aligned}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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