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
    Thank you for the input! But could you please tell me, what does projection $p_{i} : \left\{0,1\right\}^{n} \rightarrow \left\{0,1\right\} : \alpha \rightarrow \alpha_{i}$ mean? Are you projecting every binary n-tuple to $\alpha_{i}$ ? But what does $\alpha_{i}$ stand for?2012-05-18
  • 0
    You are definitely right, though. I did miss one function: the identity function $f(x) = x$. So, I think $\left\{0,1,x\right\}$ is the basis for $L \cap M$.2012-05-18
  • 0
    I think I got what you meant by those projections. Is it the projection of $i$-th components of binary n-tuples onto themselves? E.g. $p_{3}(00100) = 1$ But this is exactly the identity function, because it does not depend on other variables, except $x_{i}$. So, I suppose, out basis is complete.2012-05-18
  • 0
    @user825089: Yes, that’s what I meant by the projection. But it’s not the identity function. The identity function would take $00100$ to $00100$ and wouldn’t be a function from $\{0,1\}^n$ to $\{0,1\}$. If $n=5$, as in this example, there are $5$ different projection functions, each depending on just one variable. In addition, you have the two constant functions, for a total of $7$ functions from $\{0,1\}^5$ to $\{0,1\}$ that are linear and monotone2012-05-18
  • 0
    This definitely makes sense, because projections and the identity function have different domains (when $n > 1$), so they cannot be equal as functions. Yet, my book says, that if we remove all the fake variables (obviously, all variables are fake except the $i$-th variable if we are projecting the $i$-th column), then we get a function, equivalent to the original. But I believe this is just a matter of agreement how the identity function really works when $n > 1$. What you call projection my book probably treats as identity functions.2012-05-18
  • 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