0

A read-once boolean formula is a function $f:\{0,1\}^n\rightarrow \{0,1\}$ which can be represented by a boolean formula involving AND and OR such that each variable appears only once.

Is it true that any such formula can be uniquely expressed as an alternating AND/OR tree with $n$ leaves labeled by input boolean variables?

flag
1 
 What is your interest in this question/command? – Michael Greinecker Dec 7 2011 at 21:19
1 
 I am trying to read up a paper of Rahul Jain on Read-once boolean formula. This question seems to be a pretty basic foundational question in that paper. – Sagnik Dec 7 2011 at 21:35
6 
 Using the imperative ('Prove this thing for me') is not generally MO style. You are asking a question, not giving an assignment. – David Roberts Dec 7 2011 at 22:42
1 
 I suspect feasibility is the issue. Until things are made explicit, I assume multiple fanin is allowed, as is representing x by x AND x or x OR x. Gerhard "Ask Me About System Design" Paseman, 2011.12.07 – Gerhard Paseman Dec 8 2011 at 6:23
1 
 It would really be nice if (at least) one of those voting to close had left a comment. – Gerry Myerson Dec 8 2011 at 11:53
show 4 more comments

closed as too localized by Andres Caicedo, Benjamin Steinberg, Alain Valette, Felipe Voloch, Qiaochu Yuan Dec 7 2011 at 23:36

Browse other questions tagged or ask your own question.