What is the meaning of this Boolean function definition?

87 Views Asked by At

For every Boolean function except the one identically equal to zero we can say that:

$$f(x_1,x_2,...x_n)=\bigvee [f(\alpha_1,...\alpha_n)\land x_1^{\alpha_1}\land...x_n^{\alpha_n}] \\ f(x_1,x_2,...x_n)=\bigwedge [f(\alpha_1,...\alpha_n)\lor x_1^{\alpha_1}\lor...x_n^{\alpha_n}]$$

where $\alpha_i \in \{0,1\}$

The use of $\lor$ and $\land$ outside the brackets and $f(\alpha_1,...\alpha_n)$ confuse me. Is this just a way of saying that any Boolean function can be written in disjunctive normal form and conjunctive normal form?

1

There are 1 best solutions below

0
On BEST ANSWER

This would make sense if the $\bigvee[\cdots]$ means to take the disjunction of one instance of the formula in brackets for each possible combination of values for the $\alpha_i$s.

In that case then, yes, it's just a way of saying that the function can be written in disjunctive and conjunctive normal forms. Why they exclude the always-0 function is a mystery.

But it is not really standard to omit the index range like that. And the notation also seems to depend on using $x^0$ and $x^1$ to denote $x$ and $\neg x$ (or vice versa), which is definitely not a standard notation.