布尔导数和e导数能反映布尔函数值随变量变化的关系，二者被广泛应用于图像处理^[1]、逻辑电路的故障检测^[2-5]和布尔函数密码学性质的研究^[6-9].

目前，学者对布尔e导数求解方法的研究主要有3种：基于K图和降维K图的图形法^[10]、基于最小项的表格法^[11]和基于改进D图的算法^[12].利用K图和降维K图求解布尔e导数，具有计算方法简单、物理意义清晰的特点，但随着输入变量数n的增大，其图形规模将以2ⁿ的速度迅速增加，因此此方法对输入变量超过30的大逻辑函数不适用；同样，通过列布尔1值最小项表求解布尔e导数，其最小项数量与输入变量数n成2ⁿ关系，亦不适合处理大函数；而基于改进D图求解布尔e导数的方法，其图形规模不仅与输入变量数n成aⁿ(1＜a≤2)关系，而且还与阶数有关，同样不适合处理大函数.

布尔e偏导数^[13]的求解较布尔e导数更难.文献[11]提出了一种基于最小项表求解布尔e偏导数的方法，即根据待求导变量累次列布尔1值最小项求解布尔e偏导数，其与基于最小项的布尔e导数求解方法一样，亦不适合求解大函数的布尔e偏导数.

本文给出了一种便于计算机编程实现的逻辑函数高阶布尔e导数和e偏导数的求解算法.利用乘积项集合之间的不相交操作^[14]，实现逻辑函数的逻辑“与”操作，并结合布尔e导数和e偏导数的定义，给出了求解算法.采用二级逻辑综合工具espresso，对算法的最终输出结果进行简化，进而得到更加紧凑的求导结果.

1 定义

一个n变量布尔函数f(x₁~x_n)总可以写成式(1)所示的乘积项之和(sum of product, SOP)：

$ f = \sum\limits_{i = 0}^{k - 1} {{p_i}} , $

(1)

式(1)中p_i为布尔函数f的第i个乘积项，k为乘积项的个数，符号“∑”表示乘积项之间是逻辑“或”关系，并记f的乘积项集合为C_f.若乘积项p_i∈C_f，则p_i可写成：

$ {p_i} = {{\dot x}_0}{{\dot x}_1} \cdots {{\dot x}_j} \cdots {{\dot x}_{n - 1}}, $

(2)

式(2)中，n为变量的个数，${\dot x_j}$分别表示x_j取原变量、反变量或不出现，分别用{1, 0, -}表示.

本文约定：DC(x₁, x₂, …, x_k)表示k个变量x₁~x_k的取值全为“-”，且DC(X)=DC(X)，X表示k变量矢量；EN(x₁, x₂, …, x_k)表示k个变量x₁~x_k中至少有1个变量取值不为“-”.

例如，乘积项p=x₁x₂x₃=-1-，按上述约定可将变量x₁, x₃全取“-”，写成DC(x₁, x₃)；变量x₁, x₂, x₃不全取“-”写成EN(x₁, x₂, x₃).

定义1  设f(x₁~x_n)为n变量的布尔函数，则f(x₁~x_n)对于变量x_j(1≤j≤n)的一阶布尔e导数为

$ \begin{array}{*{20}{c}} {\frac{{{\rm{e}}f\left( {{x_1} \sim {x_n}} \right)}}{{{\rm{e}}{x_j}}} \buildrel \Delta \over = f\left( {{x_1} \cdots {x_j} \cdots {x_n}} \right) \cdot f\left( {{x_1} \cdots \overline {{x_j}} \cdots {x_n}} \right) = }\\ {\sum\limits_{i = 0}^{k - 1} {{p_{i\left| {{x_j}} \right.}}} \cdot \sum\limits_{i = 0}^{k - 1} {{p_{i\left| {\overline {{x_j}} } \right.}}} ,} \end{array} $

(3)

式(3)中${p_{i{\rm{|}}\overline {{x_j}} }}$表示对布尔函数f(x₁…x_j…x_n)中乘积项p_i中的变量x_j进行取反操作，因此$f({x_1} \cdots {x_j} \cdots {x_n}) = \sum\limits_{i = 0}^{k-1} {{p_{i{\rm{|}}\overline {{x_j}} }}, } f({x_1} \cdots \overline {{x_j}} \cdots {x_n}) = \sum\limits_{i = 0}^{k-1} {{p_{i{\rm{|}}\overline {{x_j}} }}} $；符号“·”表示函数之间是逻辑“与”关系.为方便起见，文中将$f({x_1} \cdots {x_j} \cdots {x_n}) \cdot f({x_1} \cdots \overline {{x_j}} \cdots {x_n})$简写成$f({x_j}) \cdot f(\overline {{x_j}})$.

定义2 设f(x₁~x_n)为n变量的布尔函数，则f(x₁~x_n)对于变量x_j1~x_jk(2≤k≤n)的k阶布尔e导数可表示为

$ \begin{array}{l} \frac{{{{\rm{e}}^k}f\left( {{x_1} \sim {x_n}} \right)}}{{{\rm{e}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)}} \buildrel \Delta \over = \\ f\left( {{x_1} \cdots {x_{{j_1}}} \sim {x_{{j_k}}} \cdots {x_n}} \right) \cdot f\left( {{x_1} \cdots {{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}} \cdots {x_n}} \right) = \\ \sum\limits_{i = 0}^{m - 1} {{p_{i\left| {{x_{{j_1}}} \sim {x_{{j_k}}}} \right.}}} \cdot \sum\limits_{i = 0}^{m - 1} {{p_{i\left| {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right.}}} , \end{array} $

(4)

式(4)中，${p_{i{\rm{|}}\overline {{x_{{j_1}}}} {\text{~}}\overline {{x_{{j_k}}}} }}$和$f({x_1} \cdots \overline {{x_{{j_1}}}} {\text{~}}\overline {{x_{{j_k}}}} \cdots {x_n})$的含义同式(3).

推论1  设n变量布尔函数f对应的乘积项集合C_f由(s+t)个不相交乘积项构成，即p_i·p_j=∅ (i≠j)，其中, s个乘积项中的待求导变量均不出现，而另外t个乘积项中的每个乘积项至少有1个待求导变量出现，则k(1≤k≤n)阶布尔e导数可表示为

$ \begin{array}{l} \frac{{{{\rm{e}}^k}f}}{{{\rm{e}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)}} = \\ \sum\limits_{i = 0}^{s - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right.}}} + \sum\limits_{i = 0}^{t - 1} {{p_{i\left| {{\rm{EN}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right.}}} \cdot \sum\limits_{i = 0}^{t - 1} {{p_{i\left| {{\rm{EN}}\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right)} \right.}}} , \end{array} $

(5)

式(5)中，${p_{i{\rm{|DC(}}{x_{{j_1}}}{\text{~}}{x_{{j_k}}})}}$表示乘积项p_i的变量x_j1~x_jk取值全为“-”；${p_{i{\rm{|EN(}}{x_{{j_1}}}{\text{~}}{x_{{j_k}}})}}$表示乘积项p_i的变量x_j1~x_jk中至少有1个取值不为“-”；${p_{i{\rm{|EN(}}{{\bar x}_{{j_1}}}{\text{~}}{{\bar x}_{{j_k}}})}}$表示对乘积项p_i的变量x_j1~x_jk取反.

证明  将构成逻辑函数f的(s+t)个不相交乘积项拆分成g和h两部分，且f=g+h.其中，g中包含s个不相交乘积项，且任一乘积项中的待求导变量均未出现；h中包含t个不相交乘积项，显然属于h的任一乘积项中的待求导变量至少出现1个.因此，g和h可以表示为

$ g = \sum\limits_{i = 0}^{s - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right.}}} ,h = \sum\limits_{i = 0}^{t - 1} {{p_{i\left| {{\rm{EN}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right.}}} , $

由条件p_i·p_j=∅(i≠j)可知g·h=∅，故

$ \begin{array}{l} \frac{{{{\rm{e}}^k}f}}{{{\rm{e}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)}} = \frac{{{{\rm{e}}^k}\left( {g + h} \right)}}{{{\rm{e}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)}} = \\ \left\{ {g\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) + h\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right\} \cdot \left\{ {g\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) + h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right)} \right\} = \\ g\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot g\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) + h\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) + \\ g\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) + h\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) = \\ g\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) + g\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) + h\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) = \\ g\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot \left( {1 + h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right)} \right) + h\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) = \\ g\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) + h\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right) \cdot h\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right) = \\ \sum\limits_{i = 0}^{s - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right.}}} + \sum\limits_{i = 0}^{t - 1} {{p_{i\left| {{\rm{EN}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right.}}} \cdot \sum\limits_{i = 0}^{t - 1} {{p_{i\left| {{\rm{EN}}\left( {{{\bar x}_{{j_1}}} \sim {{\bar x}_{{j_k}}}} \right)} \right.}}} . \end{array} $

证毕!

例1   $f({x_1}-{x_4}) = {x_1}{x_2}{x_3} + {{\bar x}_1}{x_3} + {{\bar x}_3}{x_4}$，用推论1计算$\frac{{{{\rm{e}}^2}f}}{{{\rm{e}}({x_1}, {x_2})}}$.

解  由推论1可得

$ \begin{array}{l} \frac{{{{\rm{e}}^2}f}}{{{{\rm{e}}^2}\left( {{x_1},{x_2}} \right)}} = \sum\limits_{i = 0}^{1 - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_1},{x_2}} \right)} \right.}}} + \sum\limits_{i = 0}^{2 - 1} {{p_{i\left| {{\rm{EN}}\left( {{x_1},{x_2}} \right)} \right.}}} \cdot \sum\limits_{i = 0}^{2 - 1} {{p_{i\left| {{\rm{EN}}\left( {{{\bar x}_1},{{\bar x}_2}} \right)} \right.}}} = \\ \left\{ {{{\bar x}_3}{x_4}} \right\} + \left\{ {{x_1}{x_2}{x_3} + {{\bar x}_1}{x_3}} \right\} \cdot \left\{ {{{\bar x}_1}{{\bar x}_2}{x_3} + {x_1}{x_3}} \right\} = \\ {{\bar x}_3}{x_4} + {x_1}{x_2}{x_3} + {{\bar x}_1}{{\bar x}_2}{x_3}, \end{array} $

由定义2及计算可得

$ \begin{array}{l} \frac{{{{\rm{e}}^2}f}}{{{\rm{e}}\left( {{x_1},{x_2}} \right)}} = \sum\limits_{i = 0}^{3 - 1} {{p_{i\left| {{x_1},{x_2}} \right.}}} \cdot \sum\limits_{i = 0}^{3 - 1} {{p_{i\left| {{{\bar x}_1},{{\bar x}_2}} \right.}}} = \\ \;\;\;\;\;\;\;\left\{ {{x_1}{x_2}{x_3} + {{\bar x}_1}{x_3} + {{\bar x}_3}{x_4}} \right\} \cdot \left\{ {{{\bar x}_1}{{\bar x}_2}{x_3} + {x_1}{x_3} + {{\bar x}_3}{x_4}} \right\} = \\ \;\;\;\;\;\;\;{x_1}{x_2}{x_3} + {{\bar x}_1}{{\bar x}_2}{x_3} + {{\bar x}_3}{x_4}. \end{array} $

以上2种方法的计算结果是一致的.用推论1来实现布尔e导数，其求导过程中逻辑表达式之间的逻辑“与”操作更加简单.

定义3  设f(x₁~x_n)为n变量的布尔函数，则f(x₁~x_n)对于变量x_j(1≤j≤n)的一阶布尔e偏导数为一阶布尔e导数.

定义4  设f(x₁~x_n)为n变量的布尔函数，则f(x₁~x_n)对于变量x_j1~x_jk(2≤k≤n)的k阶布尔e偏导数可表示为

$ \begin{array}{l} \frac{{{{\rm{e}}^k}f\left( {{x_1} \sim {x_n}} \right)}}{{{\rm{e}}{x_{{j_1}}} \sim {\rm{e}}{x_{{j_k}}}}} \buildrel \Delta \over = \\ \;\;\;\;\;\;\;\;\;\frac{{\rm{e}}}{{{\rm{e}}{x_{{j_k}}}}}\left( {\frac{{\rm{e}}}{{{\rm{e}}{x_{{j_{k - 1}}}}}} \cdots \left( {\frac{{\rm{e}}}{{{\rm{e}}{x_{{j_2}}}}}\left( {\frac{{{\rm{e}}f\left( {{x_1} \sim {x_n}} \right)}}{{{\rm{e}}{x_{{j_1}}}}}} \right)} \right) \cdots } \right). \end{array} $

(6)

推论2  设n变量布尔函数f对应乘积项集合C_f由p_i·p_j=∅(i≠j)个不相交乘积项构成，即p_i·p_j=∅(i≠j)，其中s个乘积项中的待求偏导变量均不出现，而另外t个乘积项中每项至少有1个待求偏导变量，则k(1≤k≤n)阶布尔e偏导数可表示为

$ \frac{{{{\rm{e}}^k}f}}{{{\rm{e}}{x_{{j_1}}} \sim {\rm{e}}{x_{{j_k}}}}} = \sum\limits_{i = 0}^{s - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right.}}} + \frac{{{{\rm{e}}^k}h}}{{{\rm{e}}{x_{{j_1}}} \sim {\rm{e}}{x_{{j_k}}}}}, $

(7)

式(7)中，h为布尔函数f的子函数，

$ h = \sum\limits_{i = 0}^{t - 1} {{p_{i\left| {{\rm{EN}}\left( {{x_{{j_1}}} \sim {x_{{j_k}}}} \right)} \right.}}} . $

证明  用数学归纳法：

(1) 当阶数k=1时，由定义3知，利用推论1可证明式(7)成立，即

$ \begin{array}{l} \frac{{{\rm{e}}f}}{{{\rm{e}}{x_j}}} = \sum\limits_{i = 0}^{s - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_j}} \right)} \right.}}} + \sum\limits_{i = 0}^{t - 1} {{p_{i\left| {{\rm{EN}}\left( {{x_j}} \right)} \right.}}} \cdot \sum\limits_{i = 0}^{t - 1} {{p_{i\left| {{\rm{EN}}\left( {{{\bar x}_j}} \right)} \right.}}} = \\ \;\;\;\;\;\;\;\;\sum\limits_{i = 0}^{s - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_j}} \right)} \right.}}} + \frac{{{\rm{e}}h}}{{{\rm{e}}{x_j}}}. \end{array} $

(2) 假设当阶数k=q(1＜q＜n)时，式(7)成立，即

$ \frac{{{{\rm{e}}^q}f}}{{{\rm{e}}{x_{{j_1}}} \sim {\rm{e}}{x_{{j_q}}}}} = \sum\limits_{i = 0}^{s - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_{{j_1}}} \sim {x_{{j_q}}}} \right)} \right.}}} + \frac{{{{\rm{e}}^q}h}}{{{\rm{e}}{x_{{j_1}}} \sim {\rm{e}}{x_{{j_q}}}}}, $

(3) 令$F = \frac{{{{\rm{e}}^q}f}}{{{\rm{e}}{x_{{j_1}}}{\text{~}}{\rm{e}}{x_{{j_q}}}}}$，F的乘积项集合为C_F, p_i∈C_F, p_i·p_j=∅(i≠j)，设G, H是F的子函数，且$G = \sum\limits_{i = 0}^{u-1} {{p_{i{\rm{|DC(}}{x_{{j_1}}}{\text{~}}{x_{{j_{q + 1}}}})}}}, H = \sum\limits_{i = 0}^{v-1} {{p_{i{\rm{|EN(}}{x_{{j_1}}}{\text{~}}{x_{{j_{q + 1}}}})}}} = \frac{{{{\rm{e}}^q}h'}}{{{\rm{e}}{x_{{j_1}}}{\text{~}}{\rm{e}}{x_{{j_q}}}}}$，并有F=G+H, G·H=∅，则当阶数k=q+1时，

$ \begin{array}{l} \frac{{{{\rm{e}}^{q + 1}}f}}{{{\rm{e}}{x_{{j_1}}} \sim {\rm{e}}{x_{{j_{q + 1}}}}}} = \frac{{\rm{e}}}{{{\rm{e}}{x_{{j_{q + 1}}}}}}\left\{ {\frac{{{{\rm{e}}^q}f}}{{{\rm{e}}{x_{{j_1}}} \sim {\rm{e}}{x_{{j_q}}}}}} \right\} = \\ \;\;\;\;\;\;\frac{{{\rm{e}}F}}{{{\rm{e}}{x_{{j_{q + 1}}}}}} = \frac{{{\rm{e}}\left( {G + H} \right)}}{{{\rm{e}}{x_{{j_{q + 1}}}}}} = \\ \;\;\;\;\;\;\left\{ {G\left( {{x_{{j_{q + 1}}}}} \right) + H\left( {{x_{{j_{q + 1}}}}} \right)} \right\} \cdot \left\{ {G\left( {{{\bar x}_{{j_{q + 1}}}}} \right) + H\left( {{{\bar x}_{{j_{q + 1}}}}} \right)} \right\} = \\ \;\;\;\;\;\;G\left( {{x_{{j_{q + 1}}}}} \right) + H\left( {{x_{{j_{q + 1}}}}} \right) \cdot H\left( {{{\bar x}_{{j_{q + 1}}}}} \right) = \\ \;\;\;\;\;\;G\left( {{x_{{j_{q + 1}}}}} \right) + \frac{{{\rm{e}}H}}{{{\rm{e}}{x_{{j_{q + 1}}}}}} = \\ \;\;\;\;\;\;\sum\limits_{i = 0}^{u - 1} {{p_{i\left| {{\rm{DC}}\left( {{x_{{j_1}}} \sim {x_{{j_{q + 1}}}}} \right)} \right.}}} + \frac{{{{\rm{e}}^{q + 1}}h'}}{{{\rm{e}}{x_{{j_1}}} \sim {\rm{e}}{x_{{j_{q + 1}}}}}}. \end{array} $

其中，h′是f的子函数，且$h' = \sum\limits_{i = 0}^{w-1} {{p_{i{\rm{|EN(}}{x_{{j_1}}}{\text{~}}{x_{{j_{q + 1}}}})}}} $, p_i∈C_f.所以，当阶数k=q+1时，式(7)也成立.

由步骤(1)~(3)可知，对任意阶数k(1≤k≤n)，推论2成立.

证毕!

2 算法实现

由布尔e导数和e偏导数的定义可知，逻辑函数的布尔e导数和e偏导数的求解过程中都涉及求解函数之间的“与”运算.因此，求解逻辑函数的逻辑“与”直接影响布尔e导数的求解速度和规模.下文将讨论逻辑函数之间“与”运算的求解方法以及大函数高阶布尔e导数和e偏导数算法.考虑现有的布尔e导数和e偏导数的求解方法只适用于输入变量较少的逻辑函数的低阶求导，且对求导结果未进行逻辑简化，本文将借用已有的二级逻辑综合工具espresso，对布尔e导数及e偏导数的计算结果进行逻辑简化.

2.1 逻辑函数之间逻辑“与”运算的实现

定义5  若C_f和C_g分别为逻辑函数f和g所对应的乘积项集合，则C_f与C_g之间的不相交运算用C_fⓧC_g表示，且C_fⓧC_g=C_f-C_f∩C_g，符号“ⓧ”为2个逻辑函数之间的不相交运算符.

从定义5可以看出，C_fⓧC_g的实质是在C_f中除去与C_g相交的部分，因此，C_fⓧC_g的结果属于C_f且不与C_g相交的部分；由此可得：C_f与C_g相交部分等于在C_f中除去与C_g不相交的部分，即逻辑函数f和g“与”的结果可表示为

$ {C_f} \cap {C_g} = {C_f} \otimes \left( {{C_f} \otimes {C_g}} \right). $

(8)

算法伪代码如下：

图 1中，C_f和C_g分别包含w和v个乘积项，C_dis=p_iΘq_j表示乘积项p_i与q_j之间进行不相交锐积运算，运算结果寄存在C_dis中.显然，结合图 1算法和式(8)可实现逻辑函数f和g之间的逻辑“与”运算.

2.2 k阶布尔e导数算法的实现

由推论1可知，k(1≤k≤n)阶布尔e导数的求解结果由两部分组成：(1)待求导变量均不出现的乘积项集合部分，即$\sum\limits_{i = 0}^{s-1} {{p_{i{\rm{|DC(}}{x_{{j_1}}}{\text{~}}{x_{{j_k}}})}}} $，将这部分记作乘积项集合C_DC；(2)待求导变量非均不出现的乘积项集合之间的逻辑“与”操作部分，即$\sum\limits_{i = 0}^{t-1} {{p_{i{\rm{|EN(}}{x_{{j_1}}}{\text{~}}{x_{{j_k}}})}}} \cdot \sum\limits_{i = 0}^{t-1} {{p_{i{\rm{|EN(}}{{\bar x}_{{j_1}}}{\text{~}}{{\bar x}_{{j_k}}})}}} $，将这部分记作乘积项集合C_and.

本文中，k阶布尔e导数运算用程序E_Derivative(C_f, L)来实现，其中C_f是布尔函数f转化为不相交乘积项SOP形式的乘积项集合，L是一个链表，用来寄存待求导变量，其伪代码如下：

图 2中，C_en和C_{r_en}为2个乘积项集合缓存，C_T是运算结果；子函数Apart(C_f, L)的功能是根据链表L中寄存的待求导变量出现的情况将C_f中的乘积项拆分成两部分，其中集合C_dc中寄存待求导变量均不出现的乘积项，剩余部分寄存在集合C_en中；子函数Reverse(C_en, L)的功能是将C_en中在全部乘积项中出现的待求导变量取反；C_and=C_enⓧ(C_enⓧC_{r_en})实现了C_en∩C_{r_en}功能，即实现2个逻辑函数之间的逻辑“与”运算；最后，借用espresso工具对C_T进行逻辑简化，得到更加紧凑的逻辑表达形式.

2.3 k阶布尔e偏导数算法的实现

由推论2可知，k(1≤k≤n)阶布尔e偏导数的求解结果由两部分组成：(1)待求偏导变量均不出现的乘积项集合部分，即$\sum\limits_{i = 0}^{s-1} {{p_{i{\rm{|DC(}}{x_{{j_1}}}{\text{~}}{x_{{j_k}}})}}} $，记作乘积项集合C_dc；(2)待求偏导变量非均不出现时的乘积项集合的k阶布尔e偏导数部分，即$\frac{{{{\rm{e}}^k}h}}{{{\rm{e}}{x_{{j_1}}}{\text{~}}{\rm{e}}{x_{{j_k}}}}}$，记作乘积项集合C_par.

本文k阶布尔e偏导数运算可用程序E_PartialDerivative(C_f, L)来实现，其中Apart(C_f, L)的含义同图 2，其伪代码如下：

图 3中的C_en是乘积项集合缓存，C_T是运算结果；C_par=e_Derivative(C_en, L_xi)表示对链表L_xi中的唯一待求偏导变量x_i求一阶布尔e导数，即一阶布尔e偏导数；最后，借用espresso对C_T实现逻辑简化.

例2  设f(x₁~x₅)=x₁x₂x₃+x₁x₂x₄+x₁x₅，求$\frac{{{{\rm{e}}^3}f}}{{{\rm{e}}{x_2}{\rm{e}}{x_3}{\rm{e}}{x_4}}}$.

解  首先，将函数f对应的乘积项集合C_f拆分成C_dc和C_en两部分，拆分结果为C_dc={x₁x₅}，C_en={x₁x₂x₃, x₁x₂x₄}.

其次，将C_en中每个乘积项中的变量x₂取反，其结果为C_{r_en}= {x₁x₂x₃, x₁x₂x₄}.

之后求C_en∩C_{r_en}，即

$ \begin{array}{l} {C_{{\rm{en}}}} \cap {C_{r\_{\rm{en}}}} = {C_{{\rm{en}}}} \otimes \left( {{C_{{\rm{en}}}} \otimes {C_{r\_{\rm{en}}}}} \right) = \\ \left\{ {{x_1}{x_2}{x_3},{x_1}{{\bar x}_2}{x_4}} \right\} \cap \left( {\left\{ {{x_1}{x_2}{x_3},{x_1}{{\bar x}_2}{x_4}} \right\} \cap } \right.\\ \left. {\left\{ {{x_1}{{\bar x}_2}{x_3},{x_1}{x_2}{x_4}} \right\}} \right) = \\ \left\{ {{x_1}{x_2}{x_3},{x_1}{{\bar x}_2}{x_4}} \right\} \cap \left\{ {{x_1}{x_2}{x_3}{x_4},{x_1}{{\bar x}_2}{x_3}{x_4}} \right\} = \\ \left\{ {{x_1}{x_2}{x_3}{x_4},{x_1}{{\bar x}_2}{x_3}{x_4}} \right\}. \end{array} $

然后，令${C_{{\rm{en}}}} = \{ {x_1}{x_2}{x_3}{x_4}, \overline {{x_2}} {x_3}{x_4}\} $，且再次将C_en中每个乘积项中的变量x₃取反，其结果为C_{r_en}={x₁x₂x₃x₄, x₁x₂x₃x₄}；同理可求得C_en∩C_{r_en}=∅，结束循环.

最终C_T=C_dc∪∅={x₁x₅}，即为求解结果.

而按照定义4直接可求得$\frac{{{{\rm{e}}^3}f}}{{{\rm{e}}{x_2}{\rm{e}}{x_3}{\rm{e}}{x_4}}} = {{\bar x}_1}{x_5}$.可见2种方法结果相同.

3 实验结果与分析

本文给出的逻辑函数高阶布尔e导数和e偏导数的求解算法已经在Windows10/CPU 2.40 GHz/ RAM 8.00 GB/VS2010环境下使用C语言编程实现，并利用MCNC标准测试电路进行了实验验证.

表 1给出的是k阶布尔e导数和e偏导数的实验数据.表 1中的电路f取自MCNC标准测试电路；i/o/p分别表示电路f对应的输入变量、输出变量和乘积项的数量；阶数k表示对电路f的任意k个变量求解布尔e导数和e偏导数，1≤k≤n，n为变量数；C_d表示布尔e导数计算结果经espresso逻辑简化后的乘积项数量；C_p表示布尔e偏导数计算结果经espresso逻辑简化后的乘积项数量；t_d表示布尔e导数的求解时间，单位ms；t_p表示布尔e偏导数的求解时间，单位ms；“＜1”表示求解时间小于1 ms.

表 1给出了11组MCNC测试电路的实验数据，这些电路的变量数为7~199，其输出和乘积项数均具有一定的规模；每个电路均测试了3组不同阶数k的情况.从表 1中可以明显看出，算法处理时间较短，大部分都＜1 ms，无超过1 s的.

如果用|C_d|和|C_p|分别表示C_d和C_p中所包含的乘积项数量，从表 1可以看出，一般情况下|C_d|≥|C_P|，其原因除了与espresso逻辑优化有关外，还与它们的定义有关.对于逻辑函数f的k阶布尔e导数而言，是2个逻辑函数之间的“与”运算；但对于k阶布尔e偏导数，则是2^k个逻辑函数之间的“与”运算；一般情况下，2^k个逻辑函数之间的公共部分更少，即多次“与”运算后对应的乘积项数量更少，导致|C_d|≥|C_p|.

函数间不相交运算的速度与每个函数包含的乘积项数量有关，待处理的逻辑函数的输入变量数对其不敏感.有些函数适合拆分，拆分后实际参与不相交运算的乘积项数量不多，因此速度快.例如电路i7、xparc.本文中逻辑函数的布尔e导数用不相交运算来求解，显然不相交运算的调用次数将直接影响算法的速度.对于逻辑函数f的k阶布尔e导数而言，由式(8)知，需要2次不相交运算，但k阶布尔e偏导数却需要2^k次不相交运算，因此有t_p≥t_d.

4 结论

实现大函数的布尔e导数和e偏导数的求解主要由以下两部分构成：(1)用逻辑函数之间的不相交运算替代.待处理的逻辑函数的输入变量数对不相交运算的速度不敏感，故在处理大逻辑函数时效率较高；(2)在求导过程中，将函数拆分成两部分，即不包含待求导变量的乘积项集合C_dc和包含待求导变量的乘积项集合C_en.C_dc求布尔e导数的结果是其本身，因此，实际上只有C_en参与了求导过程中的不相交运算，显然C_en中包含的乘积项数量不会大于原函数，从而达到减少参与不相交运算的乘积项数量的目的，提高了算法速度.实验表明，本文提出的方法可以快速计算输入变量数在199内的大函数的高阶布尔e导数和e偏导数.为了简化求导后的逻辑函数的表达式，算法最后借用二级逻辑综合工具espresso，实现了函数的逻辑简化.