Boolean simplicity

Hello Scott (and Mohamed),

Just to tell you that I have received your two last mails! Shall we try to meet this week to make a point (tomorrow I am busy writing an ECAI paper with Gen and I am busy tuesday afternoon, but other days should be ok)?

Concerning the corner things, this works for any Boolean formula, as any such formula can be written in a multilinear form (sum of products of variables where variables in product appear with exponent one), for which we know that it is locally monotone (if we fix all variables to a given value save one, then the function is either increasing or decreasing in the last variables, with the direction of the monotonicity being possibly dependent of the fixed values of the other variables), and for which type of functions we know that extrema lies on vertices of the hypercube. Not Sure I am clear, but this is the answer :). I am still puzzled about the Birnbaum and derivative thing, but this may be due to this multilinear form (seeing an actual proof would probably explain us why)

Cheers

Seb

Okay, but where I come from the phrase "any Boolean formula" would mean any well-formed formula involving conjunction, disjunction and negation, and not any function at from Boolean inputs to a Boolean output.  It's easy to believe the claim about such formulas, but we're talking about arbitrary functions with subtractions and other operations.

I found a website that says:

A boolean function is any function f:{0,1}^n→{0,1} . Volume 4 of Knuth's Art of Computer Programming contains a proof that any boolean function is equivalent to a multilinear expression using only products and sums in {0,1}.

(Actually he had Z_2 which I've replaced with {0,1}.)   I guess this is the same thing you're saying.  I guess iit could be true for this space, and I guess this works for us because the state of the system is Boolean, even though the characterization is probabilistic, i.e., on [0,1].

Okay, then I guess we are back in business.

Any day this week would be fine with me.

Scott

Hi Scott and Sebastien,

This is the  proof of the fact that: B(i)=dR/dr_i=R(1_i)-R(0_i) (R: reliability of system and r_i : reliability of component i)

By pivotal decomposition, we have: 

R=r_i.R(1_i)+(1-r_i).R(0_i)

 = r_i(R(1_i)-R(0_i))-R(0_i)

Thus : dR/dr_i=R(1_i)-R(0_i)

I also attached my source code for computation of importance measures. I am reading another paper :

"The application of constrained mathematics in probabilistic uncertainty analysis",Cooper, J.A. ; Sandia Nat. Labs., Albuquerque, NM, USA, Fuzzy Information Processing Society, 1999. NAFIPS. 18th International Conference of the North American

and I send you my opinion latter.

Mohamed