Consider a system with $n$ units where each unit is either working or failing. $x_j=1$ represents the condition that $j$-th unit is working. Suppose each unit is working with independent probability $p_j$, then show that the Boolean function $f(x_1, x_2, \dots x_n)$ is true with probability $F(p_1, p_2, \dots p_n)$ where $F$ is a polynomial in the variables in $p_1, p_2, \dots, p_n$.

I haven't understood the question properly. I understand what the Boolean variable $x_j$ means but what does the Boolean function $f$ mean and how do we prove anything about its probability ?

The solution uses the fact that $F$ is a multi linear integral representation of $f$, and that proves it. Now, I've read that a multilinear representation of a Boolean function is a sum of zero or more of its $2^n$ possible terms mod $2$. Now, an integral multilinear representation is this same multilinear representation such that each term is weighted with an integral coefficient so that $f(x_1,\dots x_n)$ has the correct value at all $2^n$ possible vectors without taking the reminder mod 2.But I don't understand how it relates. Please help.

My main questions are : 1. What is this Boolean function $f$ ? There can be any number of Boolean functions. How to prove something in general for all ?

  1. The concept of multilinear integral representation isn't clear. The author just said that a polynomial in its probabilities will be a multilinear integral representation of the Boolean function and that's that.

I think it is a parrallel system, not a series system becauae the probability for each unit is independent of other units.

So, the problem changes into this simple question; for a parallel system with n units, find the probability that the system will not fail. (with the variables $x$ and $p$ given the same characteristic as mentioned above)

Then, $f=x_1+x_2+x_3+....\pmod2$. Assuming that + in this equation is or operation, if at least one $x$ can do work, that $x$ value becomes $1$, and $f$ has a value $1$ which means the system is working fine.

1 in probability means that it is true for any condition. So we minus the probability that all of its units fail to $1$. which results in this polynomial expression of all $p$ s. $F=1 - (1-p_1)\cdot(1-p_2)\cdot(1-p_3)....$ And that would be the answer for this question if it is a parallel system.

  • $\begingroup$ The author clarified that the assumption that they're independent is a gross one to simplify the mathematics. $\endgroup$ – user230452 Jul 2 '16 at 9:48
  • $\begingroup$ I see you're new to the site and my question is your first post ! Thanks ! xD I edited your answer to put in $LaTeX$. This link was very helpful to me when I started out learning MathJax meta.math.stackexchange.com/questions/5020/… $\endgroup$ – user230452 Jul 2 '16 at 9:53
  • $\begingroup$ Thanks! I would try out the LaTeX later in my answer! $\endgroup$ – Chul Hyun Kim Jul 2 '16 at 10:23
  • $\begingroup$ Can you elaborate on why you chose $f$ the way you did ? If it's or, there's no need to put the modulo $2$ as that changes the meaning. (It becomes XOR). $\endgroup$ – user230452 Jul 2 '16 at 10:40
  • $\begingroup$ After scanning my answer, I realized that there is no need to put mod2 at there, and whether or not you put it the answer does not change because 0 or 1 is less than 2, and f can have only values 0 or 1. f tells in this case whether or not the system will work. $\endgroup$ – Chul Hyun Kim Jul 2 '16 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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