1
$\begingroup$

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

  1. $B \subseteq A$
  2. $A \subseteq \left[B\right]$
  3. $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.

1 Answers 1

1

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.

  • 0
    I think of it this way: let $f(x_{1}, x_{2}, x_{3}) = x_{1} ∨ x_{2}$. Even though the function formally depends on 3 variables, and has domain $\left\{0,1\right\}^{3}$, the 3rd component is always being put into a ghost variable, and is never used. So, for all purposes, the function is equivalent to $f(x_{1}, x_{2})$ with domain $\left\{0,1\right\}^{2}$. That is what my book says at least. Honestly, seems a little weird, but again I think this is purely a matter of agreement.2012-05-18