布尔函数和伪布尔函数多项式表示的快速实现算法

布尔函数和伪布尔函数在不同的领域有着广泛的应用,利用多项式表示有利于刻划它们的一些特征属性。论文首先在已知输入都能得到输出的条件下给出了布尔函数多项式表示的快速实现算法,该算法仅用到模2加运算,运算次数少,具有简洁、易于编程实现、准确而快速的特点,而且该算法很易推广为伪布尔函数多项式表示的快速实现算法,只需把模2加运算换成实数加运算即可。接着通过比较说明了伪布尔函数多项式表示的快速实现算法,同时指出任何伪布尔函数都能通过多项式形式表示出来。最后通过实例进一步验证了算法的正确性。

Fast algorithms for polynomial representations of boolean functions and pseudo-boolean functions

Boolean functions and pseudo-Boolean functions have been widely used in different fields,whose polynomial representations contribute to depicting their some characteristic properties.In this paper,under the condition of that the output value can be gotten directly from the input value of a Boolean function,the fast algorithm for the polynomial representation of the Boolean function is given firstly,where only XORs are required.The algorithm appears quite simple,easy to be programmed and runs very fast,furthermore the algorithm can be easy to change into the fast algorithm for the polynomial representation of a pseudo-Boolean function with real additions instead of XORs.And then,the fast algorithm for the polynomial representation of a pseudo-Boolean function is illustrated through comparisons and the result of that every pseudo-Boolean function can be expressed in polynomial form is pointed out at the same time.At last,an example further shows the validity of the algorithm in this paper.