I've been tasked to find a basis for the following system of Boolean functions: $L\cap M$, where $L$ is a class of linear functions and $M$ is a class of monotone functions.
Attempt at solution
By definition, a system $B$ is a basis of a closed systen $A$ if
- $B \subseteq A$
- $A \subseteq \left[B\right]$
- $B$ is independent
I started guessing which functions might be both linear and monotone, and among elementary functions, only $0$ and $1$ seem to satisfy both properties. So, my candidate for a basis is $ B = \left\{0,1\right\}$, but I cannot prove there are no other functions that are both linear and monotone.
I also know that for any linear function there exists ANF of the form: $x_{1} ⊕ x_{2} ⊕ \ldots ⊕ x_{n} ⊕ c $ , and any monotone function is either $0, 1$, or there exists a positive DNF for that function. However, I don't know how to combine these two forms and devise a general "look" of the linear and monotone function.
Thank you!
EDIT:
I came up with a sketch of a proof: Let $f \in M$, and $f \neq 0,1$, then there exists a positive DNF equivalent to $f$. But every positive DNF must $\in T_{0} $ and $\in T_{1} $, hence $f \in T_{0}, T_{1}$. Therefore, ANF of $f$ will look like this: $x_{1} ⊕ x_{2} ⊕ \ldots ⊕ x_{2k + 1} $, but such function obviously cannot be monotone, there will always exist $\tilde{\alpha}, \tilde{\beta} \in B^{n}$, such that $\tilde{\alpha} \leq \tilde{\beta}$, but $\tilde{\alpha}$ has odd number of "1s" and $\tilde{\beta}$ has even number of "1s", so $f\left(\tilde{\alpha}\right) > f\left(\tilde{\beta}\right)$
It would be great if someone checked the argument.
I’m not familiar with all of your notation, so I can’t say for sure, but I think that you have the right general idea but have overlooked some details.
A linear Boolean function that actively depends on more than one variable cannot be monotone. If $f$ depends on both $\alpha_i$ and $\alpha_k$, hold the other inputs fixed and let $\langle\alpha_i,\alpha_k\rangle$ change from $\langle 0,0\rangle$ to $\langle 0,1\rangle$ to $\langle 1,1\rangle$: the value of $f$ must change either from $0$ to $1$ to $0$ or from $1$ to $0$ to $1$, and in either case there’s one change in the wrong direction.
However, the projections $p_i:\{0,1\}^n\to\{0,1\}:\alpha\mapsto\alpha_i$ are both linear and monotone, so $L\cap M$ contains more than just the constant functions.