Method to minimize boolean function in SOP-form

Question

I'm dealing with boolean functions of which I can only (but safely) assume that they come in as a SOP and contain no negations (e.g. (A && B && C) || (A && B && D)). The number of disjunctions is usually > 5, the number of conjunctions within usually > 10.

Because in my case computing the value of each variable is hard and the result is to be considered ephemeral, I need to be able to minimize said functions with respect to variable occurrence. The result of this minimization does not need to be in any normal form and is allowed to be nested arbitrarily deep.

Having asked a similar question before, SO points to general solutions using fanout-minimization, Karnough maps, QM or BDDs. Before dealing with these approaches - which would blow up my code extensively - I'd like to double-check if the a priori known facts about the input function do not yield the possibility to use a smaller though less general approach of minimization.

AFAICS applying the absorption and distributivity laws will always provide the minimal form. Is there a possibility to exploit the fact that the functions come in as SOPs and have no negations? It appears to me that there should be a recursive algorithm of simple intersection- and union-operations on the variables that will yield the desired result.

Can one describe that algorithm?

Edit: Request for comments: Having done some research on the topic, it appears to me that the question asked here is equivalent to finding the optimal variable ordering of the reduced BDD of the given functions.

---

Background: The minimized function is passed on to a job queue to figure out the value of all required variables. The function is evaluated afterwards. Consider the application examples:

• The input function (A && B && C) || (A && B && D) can be written as A && B && (C || D), which eliminates having to evaluate A and B twice. Evaluation of C and D is serialized in the job queue because only one of them needs to be proven true.
• (A && B && C) || (A && B && C && D) || (A && B && X && E) is reduced to A && B && (C || (X && E)). The evaluation of X && E is considered more hard and therefor placed behind evaluation of C in the queue, the evaluation of D is dropped.

Answer 1

Here is a simple algorithm :

let's consider an exampe : ABC+ABD

there is

• 2 terms T1 = ABC and T2=ABD
• 4 vars A,B,C and D

First convert your expression to a 2D table (it's not a k-map) :

    T1  T2
A   1   1 
B   1   1   
C   1   0
D   0   1 

---

**begin** 
**While** the table is not empty do :
    **if** a row or a column have only zeros, **then** 
           remove it from table and continue. 
    **end if**
    **if** there is a row or more with only ones **then** 
           factor the vars corresponding to the rows 
           and remove the rows from the table 
    **else** 
           get the rows having a max number of ones, 
           do their scalar prod 
           from the scalar prod obtained, 
           get the columns corresponding to zeros (terms) 
           and put aside the one having a min number of ones 
           and remove its column from the table
    **end else**

**end while**

close brackets
**end**

Application to the table above :

    T1  T2
A   1   1 
B   1   1   
C   1   0
D   0   1 

iteration 1 : there is 2 rows having only ones, A and B, factor them and remove them from table :

the expression will begin with : AB(... and the table is now :

    T1  T2  
C   1   0
D   0   1 

iteration 2 : no rows having only ones. two rows having a max number of ones equal to 1 , their scalar prod is 0 0 , two columns having a zero, T1 and T2 both have the same number of 1 , no min , take one of them aside, let's take T1 and remove it from the table : the expression will begin with : AB(T1+ and T1 is 1*C+0*D = C the expression will begin with : AB(C+... the table is now :

    T2  
C   0
D   1 

iteration 3 : the row C have only zeros, we shall remove it , the row D have only ones, we factor it and remove it from table

the expression is now : AB(C+D(...

the table is now : empty

iteration4: the table is empty -> end of while

close brackets :

the expression is AB(C+D)

it's not an optimal algorithm but it's less general than k-maps because it takes into consideration the fact that the expression is SOP and without negations