# Is $f(X)f^d(X) = 0$ for a Boolean function $f$?

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:

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}.$$

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

$$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}