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.