Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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? –  user825089 May 18 '12 at 17:35
    
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$. –  user825089 May 18 '12 at 17:39
    
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. –  user825089 May 18 '12 at 17:46
    
@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 monotone –  Brian M. Scott May 18 '12 at 19:31
    
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. –  user825089 May 18 '12 at 21:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.