Lupanov representation

<h2 id="definition">Definition</h2>
The idea is to represent the values of a boolean function ƒ in a table of 2k rows, representing the possible values of the k first variables x1, ..., ,xk, and 2n−k columns representing the values of the other variables.
Let A1, ..., Ap be a partition of the rows of this table such that for i < p, |Ai| = s and 
 
 
 
 
 |
 
 
 A
 
 p
 
 
 
 |
 
 =
 
 s
 ′
 
 ≤
 s
 
 
 {\displaystyle |A_{p}|=s'\leq s}
 
.
Let ƒi(x) = ƒ(x) <a href="/facts/Iff/bYSxGJ66">iff</a> x ∈ Ai.
Moreover, let 
 
 
 
 
 B
 
 i
 ,
 w
 
 
 
 
 {\displaystyle B_{i,w}}
 
 be the set of the columns whose intersection with 
 
 
 
 
 A
 
 i
 
 
 
 
 {\displaystyle A_{i}}
 
 is 
 
 
 
 w
 
 
 {\displaystyle w}
 
.

<h2 id="external-links">External links</h2>
<ul><li><a href="http://courses.cs.vt.edu/cs4124/fall2005/resources/lupanov.pdf">Course material describing the Lupanov representation</a></li>
<li><a href="http://courses.cs.vt.edu/cs4124/fall2005/resources/lupanov_example.pdf">An additional example from the same course material</a></li></ul>

Lupanov representation open-in-new

Lupanov representation