二进神经网络的Boolean函数化简

贺勤斌

(台州学院 数学与信息工程学院，浙江 临海 317000）

二进神经网络的Boolean函数化简

贺勤斌

(台州学院 数学与信息工程学院，浙江 临海 317000）

利用二进神经网络方法对Boolean函数逻辑化简具有理论研究与实际应用意义。通过二进神经网络化简复杂非线性可分Boolean函数的方法，说明对非线性可分Boolean函数化简采用二进神经网络方法能够取得比传统方法更加高效、简便的化简。同时，给出几个二进神经网络化简非线性可分Boolean函数的实例，具体说明该方法的有效性。

卡诺图；二进神经网络；神经元；Boolean函数

0 引言

逻辑代数又称为Boolean代数，是研究逻辑电路的基本工具.Boolean函数的实现问题在密码学、数字逻辑设计等领域有着重要的理论和应用意义.［1-6］卡诺图化简逻辑函数的方法具有简单、直观、有一定的化简步骤可循的优点.传统的电路化简，对于小规模电路可采用卡诺图化简.当输入变量多于4个时，一般不采用卡诺图化简法而采用其他方法.

二进神经网络的Boolean函数化简，是使非线性可分Boolean函数分解成较少的线性可分Boolean函数的异或.卡诺图化简的Boolean函数的目的是使非线性可分Boolean函数化简成相应的乘积项个数最少.二进神经网络实现逻辑函数化简上某些方面有着比卡诺图高得多的效率.虽然，它们在电路具体实现上是不同的，但是数字电路和信息处理中的一个核心问题是各种逻辑函数（即Boolean函数）的实现.从非线性可分Boolean函数的化简意义上二者的目的是相同的.

逻辑函数的乘积项一定是线性可分的Boolean函数.而事实上线性可分的Boolean函数个数远远大于逻辑函数的乘积项个数.另外，逻辑“异或”运算相对于逻辑“与”运算也更具灵活性，这使得二进神经网络逻辑化简比传统逻辑电路方法更有优势.理论上已经证明：采用三层前向神经网络可实现任意布尔函数.1993年，Andree对前向网络实现Boolean函数与用逻辑电路实现Boolean函数进行深入和比较，指出用神经网络实现Boolean函数的优越性在于可以用更小的规模实现Boolean函数的功能.［1］

二进神经网的基本功能是分类和函数逼近，因而被广泛地应用于模式识别、信号处理以及语音识别等领域.前向神经网络结构的优化问题与Boolean函数的线性与非线性可分问题有着本质和内在的联系.任一个线性可分Boolean函数的功能在电路上可以由一个感知器神经元实现；而任意非线性可分Boolean函数用前向神经网络实现时，需要至少2个隐层神经元和1个输出神经元(或者所有隐层神经元输出的逻辑异或).到底需要多少个隐层神经元，这关系到对二进神经网逻辑函数化简的程度.关于非线性Boolean函数的分解最短问题也是当今一个没有解决的难题.［3］二进神经网络实现Boolean函数化简实现数字逻辑电路的设计，本质上就是减少感知器神经元的个数.文献[7-10]对非线性Boolean函数的分解的隐层神经元个数进行了研究及讨论，取得了一定的成果.

1 二进神经网的Boolean函数化简

Boolean函数的复杂性一方面在于Boolean函数的总数目随着维数n增加而快速增加.维数n≤8的情况下，线性可分Boolean函数的数目及Boolean函数总数如表1所示［6］：

表1 n变量线性可分Boolean函数数目与Boolean函数总数目

神经元是神经网络的基本处理单元，一个简单的感知器神经元如图1所示．图 1 中 ui∈｛0，1｝为神经元的第 i个输入，wi为第 i个输入到处理单元的连接权值，θ为神经元阈值.

则σi满足表 2 关系［10］：

图1 简单感知器神经元模型

表2 n输入 Boolean函数f的σi，vi关系

另外，感知器神经元一定是线性可分的，所以逻辑函数的乘积项一定是线性可分的Boolean函数.证毕.

定理表明逻辑函数的乘积项一定是线性可分的Boolean函数；而事实上线性可分的Boolean函数个数远远大于逻辑函数的乘积项个数.另外，逻辑“异或”运算相对于逻辑“与”运算也更具灵活性，这使得二进神经网络逻辑化简比传统逻辑电路方法更有优势.

2 二进神经网络的Boolean函数化简举例

下文中出现的二进制数的左边是低位右边是高位.

图2 Boolean函数十进制代码27030的神经元实现模型

由二进神经网络方法计算的分解结果经过检验完全正确.对比本例的卡诺图化简分解长度为3，而利用二进神经网络方法计算Boolean函数f的分解长度为2，显然，比卡诺图化简更短，且这时是最短分解.十进制代码58623的Boolean函数f的二进神经网络方法的分解结果用图3表示.显然，十进制代码为50431的Boolean函数并不能用一个卡诺图的逻辑乘积项来表示，但是它却是线性可分的Boolean函数.

图3 Boolean函数十进制代码58623的神经元线性分解图

从上面分解结果可以知道，本例的8输入Boolean函数f的分解，共可以分成21个线性可分Boolean函数逻辑异或；从而在电路实现上只需要21个隐形神经元。而传统方法化简该8输入Boolean函数相对非常复杂.

3 结论与分析

本文对二进神经网络Boolean函数化简进行分析，通过几个实例说明二进神经网络对Boolean函数逻辑化简方法，并指出二进神经网络方法Boolean函数逻辑化简比传统方法有着明显的优势，特别对多变量情况的逻辑化简优势更加明显.而且，利用二进神经网络方法Boolean函数逻辑化简，得到的化简式在电路实现上也具有优势.另外，利用二进神经网络方法Boolean函数逻辑化简具有理论研究与实际应用意义.

［1］Andree M.A..A Comparison Study of Binary Feedforward Neural Networks and Digital Circuits［M］.Neural Networks，1993.

［2］Negnevitsky M..Artificial Intelligence：A Guide to Intelligent Systems （Second Edition）［M］.Addision-Wesley，New York，2004.

［3］张军英，许 进.二进前项人工神经网络－理论及应用［M］.西安：西安电子科技大学出版社.2001.

［4］朱大奇，史 慧.人工神经网络原理及应用［M］.北京：科学出版社，2006.

［5］Chua L.O..“CNN：A paradigm for complexity”［M］.in Visions of Nonlinear Science in the 21st Century.Singapore：World Scientific，1999.

［6］Hassoun M.H..Fundamentals of Artificial Networks［M］.Cambridge，MS：MIT Press，1995；

［7］Chen F.Y.，Chen G..“Realization and Bifurcation of Boolean Functions via Cellular Neural Networks”［J］.International Journal of Bifurcation and Chaos，2005，15（7），2109-2129.

［8］Chen F.Y.，Chen G.，He G.L.，Xu X.B.. “Realization of Boolean Functions and Gene Bank of Cellular Neural Networks”［A］.Proceedingsof9th IEEE InternationalWorkshop on Cellular NeuralNetworksand their Applications，Hsinchu，Taiwan，2005.

［9］Chen F.Y.，He G.L.，Chen G..“Realization of Boolean Functions via CNN：Mathematical Theory，LSBF and Template Design”［J］.IEEE Transactions on Circuits and Systems-1：Regular papers，2006，53（10），2203-2213.

［10］Chen F.Y.，He G.L.，Chen G.. “Realization ofBoolean Functionsvia CNN with the Von Neumann Neighborhood”［J］.International Journal of Bifurcation and Chaos，2006，16（5），1389-1403.

［11］K.R.Crounse，E.L.Fung，L.O.Chua，“Efficient implementation of neighborhood logic for cellularautomata viatheCellularNeuralNetworkUniversalMachine”［J］.IEEE Transacti-onson Circuitsand SystemsI：Fundamental Theory and Applications，1997，4（3）：355-361.

［12］周宦银，刘家华.卡诺图法化简多变量逻辑函数的探讨［J］.电子工程师，2006，32（7）：30-35.

The Simplification of Boolean Functions of Binary Feedforward Neural Network

HE Qin-bin
(School of Mathematics and Information Engineering,Taizhou University,Linhai 317000,China)

There is some significance in theoretical study and practical application by using the method of Binary Feedforward Neural Networks to simplify Boolean function. In this paper, by using the method of Binary Feedforward Neural Networks, we simplify Boolean function to show that simplification method sometimes is more efficient and simple than the traditional methods. In addition, examples are given to illustrate the effectiveness of the method.

Karnaugh map;binary feedforward neural networks;neuron;Boolean function

耿继祥）

TP183

A

1672-3708（2010）03-0013-07

2009-03-26；

2010-06-10

台州学院校立项目（082D04）

贺勤斌（1972- ），男,浙江台州人，副教授，硕士，研究方向：非线性动力系统，神经网络，Boolean函数。