趙威亦，陳相錦，董怡雯，周冰瀅，王 杰，賀勤斌＊

（1.臺州學院 航空工程學院，浙江 臺州 318000；2.臺州學院 電子與信息工程學院，浙江 臨海 317000；3.臺州學院 商學院，浙江 臺州 318000）

0 引言

人工智能目前在機器人、經(jīng)濟政治決策、控制系統(tǒng)以及仿真系統(tǒng)中得到廣泛應用.目前能夠用來研究人工智能的主要物質手段以及能夠實現(xiàn)人工智能技術的機器就是計算機.人工智能的發(fā)展歷史是和計算機科學與技術的發(fā)展史聯(lián)系在一起的.除了計算機科學以外，人工智能還涉及信息論、控制論、自動化、仿生學、生物學、心理學、數(shù)理邏輯、語言學、醫(yī)學和哲學等多門學科.隨著大量數(shù)據(jù)計算處理，計算機的計算速度成為計算瓶頸.目前人們對計算機速度處理，往往是采用多核處理器、大型計算機處理.但是人工智能的小型化發(fā)展是必然的趨勢，因此新的硬件設計和研究越來越重要.美國學者F.Rosenblatt提出的感知器網(wǎng)絡（Perceptron networks）是人工神經(jīng)網(wǎng)絡的重要組成部分，它具有人類大腦的自組織、自學習的功能，其應用非常廣泛，涉及電子科學與技術、信息科學、通信工程、計算機科學與技術、控制科學與技術等領域［1-4］.感知器神經(jīng)網(wǎng)絡成為了一個新的研究方向.感知器神經(jīng)網(wǎng)絡的線性可分判斷是感知器領域一個重要的研究內容［5］.

滿足性問題是多個不同學科的交叉問題，它是一類著名的NP-完全問題［6，7］.最優(yōu)可滿足性問題是一個重要的研究對象，國際上的研究十分活躍，這類典型的NP完全問題大量地出現(xiàn)在軍事系統(tǒng)、通訊網(wǎng)絡、計算機集成系統(tǒng)中［7］.在算法設計與分析的研究中，最優(yōu)可滿足性問題是一個重要而又困難的研究對象.但是，隨著滿足性判定算法性能的不斷提升，它已經(jīng)被大量的應用于實際問題的求解，例如計算機優(yōu)化算法、系統(tǒng)生物學、運籌學和管理科學領域.

本文對滿足性問題進行研究，把滿足性算法應用于感知器神經(jīng)網(wǎng)絡的線性可分判斷，我們希望取得較好的計算效果.

2 相關概念及算法

2.1 布爾函數(shù)

定義1：布爾函數(shù)可以由下列映射表示:

顯然，一個n輸入布爾函數(shù)可以由一個n維立方體表示.圖1給出兩個2輸入布爾函數(shù)的2維立方體表示.

圖1 兩個2輸入布爾函數(shù)的2維立方體表示

表1 n輸入布爾函數(shù)的輸入窗口表示

2.2 線性可分布爾函數(shù)

定義 2［8］：n 輸入的 Boolean 函數(shù)稱為線性可分的（Linearly separable），如果存在向量W=(w1,w2,…,wn)和閾值 θ，使得

幾何上看，一個n輸入布爾函數(shù)線性可分當且僅當存在一個n-1維超平面w1x1+w2x2+…+wnxn-θ=0，它將 n維超立方體的-1頂點與+1頂點分離兩個部份 .自然，圖 1（a）函數(shù)是線性可分的，圖1（b）函數(shù)是非線性可分的.

任一個非線性可分布爾函數(shù)可以由線性可分布爾函數(shù)通過“異或”（XOR）得到［9，10］.而線性可分布爾函數(shù)在硬件電路上實現(xiàn)比較容易.但是，依照定義判斷一個布爾函數(shù)是否線性可分非常困難.因此，對于任意一個布爾函數(shù)的線性可分判斷變得重要.

定義 3［11］：記的極小子系統(tǒng)，如果滿足i0+i3=i1+i2和σi0+ σi3=σi1+σi2.當極小子系統(tǒng)是線性可分的，則稱為相容極小子系統(tǒng)，否則稱為不相容極小子系統(tǒng).

引理1［11］n輸入布爾函數(shù)的極小子系統(tǒng)的個數(shù)為：例如，當n=3時，若給定某一函數(shù)則該函數(shù)有12個極小子系統(tǒng)，分別為

引理2［11］n輸入布爾函數(shù)線性可分當且僅當其N(n)個極小子系統(tǒng)都是相容的，即任一極小子系統(tǒng)滿足

則引理1和引理2容易得到下列結果：

推論1 n輸入布爾函數(shù)的所有可能不相容極小子系統(tǒng)個數(shù)為2N(n).

在不引起混淆情況下，本文的二值輸入輸出變量{- 1,1}可以用{0 ,1}或{F ,T}表示.基本邏輯運算有邏輯與(∧)、邏輯并(∨)、邏輯非(～)、蘊含(→ )以及等價(? 或=)等.

定 義 4［12］：邏 輯 式，稱 邏 輯 式 φ 為 析 取 范 式 .這 里是子句，li1∈{0 ,1}為文字.

在邏輯式析取范式φ中當某一子句為“真”，則φ為“真”，即φ=T.

定 義 5［12］：邏 輯 式稱 邏 輯 式 φ 為 合 取 范 式 .這 里

在邏輯式合取范式φ中當某一子句為“假”，則φ為“假”，即φ=F.

定理 1［12］若 f，p是邏輯式，則

顯然，邏輯蘊含滿足分配律、結合律.

推論2 若f，p(i=1,2,…,k)是邏輯式，則

定理2 單元消解：若p為文字，A為邏輯式，則滿足

證明：我們通過計算真值表，

另外，

顯然，所證成立.

定理3 記p為n輸入布爾函數(shù)的一個極小不相容子系統(tǒng)，對于任意一個布爾函數(shù)f，若存在p滿足f∧～p=F，則布爾函數(shù)f非線性可分，否則布爾函數(shù)f線性可分.

證明：由p為n輸入布爾函數(shù)的一個極小不相容子系統(tǒng)；若f→p=T，即～(f→p)=F，則布爾函數(shù)f至少含有一個極小不相容子系統(tǒng).由定理1上式即，～(f→p)=～(～f∨p)=F.另外，由引理1和引理2知，布爾函數(shù)f非線性可分；自然，若f∧～p=T即布爾函數(shù)f線性可分.證畢.

定理4 記pi(i=1,2,3,…,2N(n))為n輸入布爾函數(shù)的極小不相容子系統(tǒng)，對于任意一個布爾函布爾函數(shù)f非線性可分，否則布爾函數(shù)f線性可分.

證明：由推論2、定理3和摩爾定律顯然成立.

由定理2和定理3，

即f為3輸入非線性可分布爾函數(shù).

邏輯滿足性算法與判斷應用非常廣泛，現(xiàn)今有大量的研究文獻，人們也提出各種各樣的算法.在許多工具軟件，比如R語言、python語言、matlab等都有滿足性求解器或相應的支持包文件.實際上對任意一個布爾函數(shù)的線性可分性判斷我們可以通過現(xiàn)有滿足性求解器來判斷.

由引理1易知3輸入布爾函數(shù)有如下24個極小不相容子系統(tǒng)：

對于例1，我們也可以利用定理4和matlab滿足性求解器來計算.對于合取范式matlab滿足性求解器，我們得到即f為3輸入非線性可分布爾函數(shù).

3 結論

判斷一個n輸入布爾函數(shù)f線性可分性問題，通常只要遍歷其可能的所有極小子系統(tǒng)，當存在其某一極小子系統(tǒng)為不相容的，則該布爾函數(shù)f是非線性可分的，否則該布爾函數(shù)f是線性可分的.本文提出利用邏輯滿足性算法判斷布爾函數(shù)的線性可分性.雖然，我們利用邏輯滿足性算法在判斷函數(shù)線性可分性的速度上并沒有提高.但是，我們給出了n輸入布爾函數(shù)f線性可分性判斷的一個新的方法.另外，滿足性算法也有可能應用于n輸入布爾函數(shù)f的線性分解以及實施，這也為我們以后的進一步研究提供了思路和方向.