蘊(yùn)涵的決策蘊(yùn)涵表示研究

王亞麗，翟巖慧,2+，張少霞，賈 楠，李德玉,2

1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006

2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006

形式概念分析（formal concept analysis，F(xiàn)CA）是由德國(guó)Wille 教授于1982 年提出的一種通過(guò)形式背景建立概念格來(lái)對(duì)數(shù)據(jù)進(jìn)行分析和提取規(guī)則的一個(gè)強(qiáng)有力的工具。它可以根據(jù)形式背景中對(duì)象和屬性之間的相互關(guān)系來(lái)得到數(shù)據(jù)與數(shù)據(jù)之間隱含的概念并建立它們之間的代數(shù)結(jié)構(gòu)，即概念格[1-2]。目前，F(xiàn)CA 已被廣泛地應(yīng)用到機(jī)器學(xué)習(xí)、社會(huì)網(wǎng)絡(luò)、軟件工程、信息檢索、基于認(rèn)知的概念學(xué)習(xí)、知識(shí)約簡(jiǎn)等相關(guān)領(lǐng)域[3-14]。

形式概念分析（概念格）中對(duì)知識(shí)獲取的研究就是對(duì)蘊(yùn)涵的研究[15-20]，但由于蘊(yùn)涵數(shù)目龐大，無(wú)法滿足用戶的需求，因此如何獲取完備無(wú)冗余的蘊(yùn)涵規(guī)則集仍是研究的熱點(diǎn)[16]。文獻(xiàn)[16]從邏輯方面對(duì)完備性和無(wú)冗余性進(jìn)行了討論，其中Ganter等已經(jīng)討論了蘊(yùn)涵的語(yǔ)義特征和語(yǔ)構(gòu)特征，提出了三條蘊(yùn)涵推理規(guī)則，而且證明了這三條推理規(guī)則相對(duì)于蘊(yùn)涵的語(yǔ)義是完備的，并給出了源于文獻(xiàn)[21]的一個(gè)蘊(yùn)涵基（完備無(wú)冗余的蘊(yùn)涵集合）。已經(jīng)證明，該蘊(yùn)涵基在所有蘊(yùn)涵基中所含的蘊(yùn)涵個(gè)數(shù)最少。Qu 等進(jìn)一步討論蘊(yùn)涵和邏輯的關(guān)系，提出了一種新的蘊(yùn)涵基，并給出一種有效的方法來(lái)生成該蘊(yùn)涵基[22]。

為了減少蘊(yùn)涵的數(shù)目，Qu 等提出了決策背景及決策蘊(yùn)涵的概念[23]，并討論了一種直觀的推理規(guī)則（α推理規(guī)則），該推理規(guī)則通過(guò)增加決策蘊(yùn)涵的前提或者減小決策蘊(yùn)涵的結(jié)論來(lái)導(dǎo)出新的決策蘊(yùn)涵[19]。文獻(xiàn)[19]還討論了基于該推理規(guī)則的完備性和冗余性，并提出了一種基于最小生成子[24]的決策蘊(yùn)涵規(guī)范基生成算法。另外，文獻(xiàn)[25]提出了一種基于真前提的決策蘊(yùn)涵規(guī)范基生成算法，實(shí)驗(yàn)結(jié)果表明該算法效率更高。

研究發(fā)現(xiàn)，α推理規(guī)則在語(yǔ)構(gòu)特征上并非是完備的，因此文獻(xiàn)[23]提出了合并推理規(guī)則，并證明合并推理規(guī)則和α推理規(guī)則（擴(kuò)增推理規(guī)則）是完備的推理規(guī)則集。在此基礎(chǔ)上，文獻(xiàn)[26]又給出一條新的推理規(guī)則——后件合并推理規(guī)則，它只對(duì)前件相同的決策蘊(yùn)涵的后件進(jìn)行合并。因此，后件合并推理規(guī)則在形式上更簡(jiǎn)潔。文獻(xiàn)[26]也證明了擴(kuò)增推理規(guī)則和后件合并推理規(guī)則是合理的、完備的并且是無(wú)冗余的。

此外，文獻(xiàn)[27]給出了一個(gè)決策蘊(yùn)涵基（稱為決策蘊(yùn)涵規(guī)范基）。該規(guī)范基基于決策前提[28]，即由決策前提作為該決策蘊(yùn)涵集的前提，由決策前提相對(duì)于決策子背景的閉包作為該決策蘊(yùn)涵集的結(jié)論。文獻(xiàn)[27]還證明了該決策蘊(yùn)涵規(guī)范基是完備的、無(wú)冗余的，并且在所有完備的決策蘊(yùn)涵集中所含的決策蘊(yùn)涵最少，因而決策蘊(yùn)涵規(guī)范基是最精簡(jiǎn)的和最優(yōu)的。研究結(jié)果表明，決策蘊(yùn)涵規(guī)范基是蘊(yùn)涵規(guī)范基[16]在決策背景下的對(duì)應(yīng)概念，并且具有蘊(yùn)涵規(guī)范基的所有優(yōu)點(diǎn)。

事實(shí)上，決策蘊(yùn)涵是一種特殊的蘊(yùn)涵，因此，決策蘊(yùn)涵的研究就是在蘊(yùn)涵中建立并研究一個(gè)/多個(gè)封閉的子系統(tǒng)（包括決策蘊(yùn)涵子系統(tǒng)及相應(yīng)的語(yǔ)義和語(yǔ)構(gòu)子系統(tǒng)），其中，不同的條件/決策屬性劃分決定了不同的封閉子系統(tǒng)。因此，蘊(yùn)涵與決策蘊(yùn)涵的研究本質(zhì)上就是封閉系統(tǒng)與封閉子系統(tǒng)的研究。

本文將從語(yǔ)構(gòu)方面深入研究由這些子系統(tǒng)（決策蘊(yùn)涵）能不能得到整個(gè)系統(tǒng)（所有的蘊(yùn)涵）。如果蘊(yùn)涵可以由決策蘊(yùn)涵推出，那么關(guān)于蘊(yùn)涵的研究就可以轉(zhuǎn)化為決策蘊(yùn)涵的研究。這樣就可以由決策蘊(yùn)涵來(lái)生成蘊(yùn)涵，甚至可以由決策蘊(yùn)涵規(guī)范基生成蘊(yùn)涵規(guī)范基。因此，蘊(yùn)涵是否能由決策蘊(yùn)涵表示是一個(gè)值得研究的問(wèn)題。事實(shí)上，這種研究對(duì)于進(jìn)一步厘清和發(fā)展蘊(yùn)涵和決策蘊(yùn)涵都是非常必要的。

1 FCA 基本概念

本章簡(jiǎn)要介紹形式概念分析中的一些基本概念。

定義1[16]形式背景是一個(gè)三元組K=(G,M,I)，其中G是對(duì)象集，M是屬性集，I?G×M是對(duì)象和屬性之間的二元關(guān)系。對(duì)于g∈G，m∈M，(g,m)∈I表示“對(duì)象g具有屬性m”。

定義2[16]設(shè)K=(G,M,I)是一個(gè)形式背景，對(duì)于集合A?G，記：

相應(yīng)地，對(duì)于集合B?M，記：

對(duì)于g∈G，為了簡(jiǎn)單起見(jiàn)，將{g}I記為gI。

定義3[16]設(shè)K=(G,M,I)是一個(gè)形式背景，對(duì)于集合A?G和B?M，若AI=B且BI=A，則稱二元組(A,B)為形式概念，簡(jiǎn)稱概念。其中A為該概念的外延，B為該概念的內(nèi)涵。?(K)稱為K的所有概念的集合。

定義4[16]設(shè)K=(G,M,I)是一個(gè)形式背景，C1=(A1,B1)和C2=(A2,B2)是K的兩個(gè)概念，定義偏序：

其中，C2是C1的超概念，C1是C2的子概念，所有概念在該偏序下構(gòu)成格，稱為概念格。

2 蘊(yùn)涵

在形式概念分析中，屬性之間的依賴可以通過(guò)蘊(yùn)涵來(lái)描述。M中屬性之間的蘊(yùn)涵是M的一對(duì)子集，記為A→B，集合A是蘊(yùn)涵A→B的前提，B是A→B的結(jié)論[16]。下面給出蘊(yùn)涵相關(guān)的一些定義。

定義5[16]設(shè)K=(G,M,I)是一個(gè)形式背景，A,B?M，如果每一個(gè)具有屬性集A的對(duì)象都具有屬性集B，則A→B叫作形式背景K下的一個(gè)蘊(yùn)涵。

定義6[16]設(shè)K=(G,M,I)是一個(gè)形式背景，T?M且A→B是形式背景K下的一個(gè)蘊(yùn)涵。如果屬性子集A?T或B?T，則稱T是蘊(yùn)涵A→B的一個(gè)模型，記為T╞(A→B)。設(shè)Θ為一蘊(yùn)涵集，如果對(duì)每一個(gè)(A→B)∈Θ都有T╞(A→B)，則稱T是Θ的一個(gè)模型，記為T╞Θ。

定義7[16]設(shè)K=(G,M,I)是一個(gè)形式背景，Θ為K的一個(gè)蘊(yùn)涵集，若對(duì)于任意的T?M，T╞Θ蘊(yùn)含T╞A→B，則稱A→B可以從Θ語(yǔ)義導(dǎo)出，記為Θ├A→B。若任意的A→B∈Θ且(Θ(A→B))├(A→B)，則稱A→B相對(duì)于Θ是冗余的。

定義8[16]設(shè)K=(G,M,I)是一個(gè)形式背景，Θ為K的一個(gè)蘊(yùn)涵集，若對(duì)任意的A→B，Θ├A→B均成立，則稱Θ是K的一個(gè)完備集。

以上是對(duì)蘊(yùn)涵語(yǔ)義方面的研究，事實(shí)上，除了語(yǔ)義特征，蘊(yùn)涵也有語(yǔ)構(gòu)特征。通過(guò)蘊(yùn)涵的語(yǔ)構(gòu)特征，可以使用推理規(guī)則集從蘊(yùn)涵集Θ導(dǎo)出新蘊(yùn)涵[16]：

（1）X→X，X?M（自反性推理規(guī)則）；

（2）若X→Y∈Θ，則X?Z→Y∈Θ，X，Y，Z?M（增廣性推理規(guī)則）；

（3）若X→Y∈Θ且Y?Z→W∈Θ，則X?Z→W∈Θ，W，X，Y，Z?M（偽傳遞性推理規(guī)則）。

文獻(xiàn)[29]已經(jīng)證明這三條推理規(guī)則相對(duì)于蘊(yùn)涵的語(yǔ)義是完備的，即從Θ中導(dǎo)出的任意蘊(yùn)涵都可以重復(fù)使用上述三條推理規(guī)則從Θ中推出。

3 決策蘊(yùn)涵

決策蘊(yùn)涵可以從兩個(gè)角度進(jìn)行研究：邏輯角度和數(shù)據(jù)角度。本章主要介紹決策蘊(yùn)涵的邏輯研究，分為語(yǔ)義特征和語(yǔ)構(gòu)特征兩部分。

3.1 決策蘊(yùn)涵的語(yǔ)義特征

首先給出決策背景及決策蘊(yùn)涵的定義。

定義9[19]設(shè)K=(G,M,I)是一個(gè)形式背景，如果令M=C?D，I=IC?ID，其中C是條件屬性集，D是決策屬性集，C?D=?，IC=G×C是條件關(guān)系，ID=G×D是決策關(guān)系，此時(shí)K=(G,C,D,I) 為一個(gè)以C為條件，D為決策的決策背景。反過(guò)來(lái)，如果以D為條件屬性集，C為決策屬性集，ID=G×D為條件關(guān)系，IC=G×C為決策關(guān)系，此時(shí)K=(G,D,C,I)是一個(gè)以D為條件，C為決策的決策背景。

定義10[19]設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，對(duì)于集合A1?C，A2?D和B?G，記：

對(duì)于g∈G和A?C，將{g}C、{g}D和(AC)D簡(jiǎn)記為gC、gD和ACD。

定義11[19]設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，若A?C且B?D，則稱A→B是一個(gè)決策蘊(yùn)涵。此時(shí)，A為該決策蘊(yùn)涵的前提，B為該決策蘊(yùn)涵的結(jié)論。

3.2 決策蘊(yùn)涵的語(yǔ)構(gòu)特征

本文只關(guān)注決策蘊(yùn)涵的語(yǔ)構(gòu)，語(yǔ)義方面的研究請(qǐng)參考文獻(xiàn)[23]。

決策蘊(yùn)涵的語(yǔ)構(gòu)方面主要研究推理規(guī)則的合理性、完備性和無(wú)冗余性。文獻(xiàn)[23]提出兩條推理規(guī)則：

擴(kuò)增推理規(guī)則：

合并推理規(guī)則：

并且證明這兩條推理規(guī)則是合理的、完備的且是無(wú)冗余的。

文獻(xiàn)[26]在此基礎(chǔ)上又提出了一條新的推理規(guī)則——后件合并推理規(guī)則：

后件合并推理規(guī)則是一種特殊的合并推理規(guī)則，它只對(duì)前件相同的決策蘊(yùn)涵的后件進(jìn)行合并。因此，后件合并推理規(guī)則在形式上更簡(jiǎn)潔。文獻(xiàn)[26]也證明了擴(kuò)增推理規(guī)則和后件合并推理規(guī)則是合理的、完備的并且是無(wú)冗余的。

4 決策蘊(yùn)涵表示蘊(yùn)涵

首先從邏輯的角度來(lái)解釋決策蘊(yùn)涵表示蘊(yùn)涵的含義。邏輯角度的分析可以從語(yǔ)義和語(yǔ)構(gòu)兩方面進(jìn)行，為了簡(jiǎn)潔，本文主要使用語(yǔ)構(gòu)的方式來(lái)分析這個(gè)問(wèn)題。從語(yǔ)構(gòu)上看，如果將決策蘊(yùn)涵看作蘊(yùn)涵的一個(gè)子系統(tǒng)，那么決策蘊(yùn)涵可以表示蘊(yùn)涵就意味著可以在一個(gè)/多個(gè)決策蘊(yùn)涵集上應(yīng)用蘊(yùn)涵上的三條推理規(guī)則得出整個(gè)蘊(yùn)涵系統(tǒng)。同時(shí)，因?yàn)闆Q策蘊(yùn)涵上的推理規(guī)則（簡(jiǎn)稱決策推理規(guī)則）是蘊(yùn)涵上推理規(guī)則（簡(jiǎn)稱蘊(yùn)涵推理規(guī)則）的特例，因此，使用決策推理規(guī)則可以推導(dǎo)出的蘊(yùn)涵必然也可以使用蘊(yùn)涵推理規(guī)則推導(dǎo)出。另一方面，蘊(yùn)涵上的推理規(guī)則并不僅僅只有第2 章中描述的三條蘊(yùn)涵推理規(guī)則，還可能存在其他的推理規(guī)則。但是，文獻(xiàn)[29]已經(jīng)證明這三條推理規(guī)則是完備的，因此在這里只考慮這三條推理規(guī)則；換句話說(shuō)，如果蘊(yùn)涵不能由這三條推理規(guī)則歸結(jié)為決策蘊(yùn)涵，那么其他推理規(guī)則也必然不能將蘊(yùn)涵歸結(jié)為決策蘊(yùn)涵。

4.1 蘊(yùn)涵表示的邏輯簡(jiǎn)化

為了使用決策蘊(yùn)涵表示蘊(yùn)涵，先引入下面的引理對(duì)需要表示的蘊(yùn)涵進(jìn)行簡(jiǎn)化。

引理1設(shè)A→B是形式背景K下的一個(gè)蘊(yùn)涵，則蘊(yùn)涵A→B成立，當(dāng)且僅當(dāng)?bi∈B，A→bi均成立。

證明（必要性）因?yàn)閎i∈B，所以有B={bi}?(B-{bi}) 。又因?yàn)锳→B成立，所以A→{bi}?(B-{bi}) 。由自反性推理規(guī)則可知{bi}→{bi}成立，再由增廣性推理規(guī)則可知{bi}?(B-{bi})→{bi}成立，最后由偽傳遞性推理規(guī)則及A→{bi}?(B-{bi})且{bi}?(B-{bi})→{bi}成立可知A→bi成立。

（充分性）先證明A→{b1}?{b2}成立。由自反性推理規(guī)則可知{b1}?{b2}→{b1}?{b2}成立，因?yàn)锳→bi成立，由偽傳遞性推理規(guī)則及A→b1且{b1}?{b2}→{b1}?{b2} 成立可知A?{b2}→{b1}?{b2} 成立，即A→{b1}?{b2}成立，因?yàn)锳?{b2}=A。接下來(lái)，令B1?{b1}?{b2}，按照上述方法可證明A→B1?{b3}成立。以此類推，可證明A→B成立。

由引理1 可知，如果所有的A→bi均可由決策蘊(yùn)涵表示，則A→B可由A→bi合并得出，因此也可由決策蘊(yùn)涵表示，故只討論后件中只有一個(gè)屬性的蘊(yùn)涵即可。

進(jìn)一步，蘊(yùn)涵的前件也可以被簡(jiǎn)化。

引理2設(shè)A→b是形式背景K下的一個(gè)蘊(yùn)涵，A1?A。若A1→b成立，則A→b成立。

證明由增廣性推理規(guī)則可知結(jié)論成立。

引理2 說(shuō)明只要求出b成立的最小前件A1，就可以得到蘊(yùn)涵A→b，因此，只要A1→b可由決策蘊(yùn)涵表示，則A→b可由A1→b通過(guò)增廣性推理規(guī)則得出，進(jìn)而也可由決策蘊(yùn)涵表示。故只討論前件最小的蘊(yùn)涵A→b即可。顯然，此時(shí)有b?A，因?yàn)锳→b成立當(dāng)且僅當(dāng)A→b，這與A是最小前件矛盾。

綜合引理1 和引理2 的結(jié)論可知，形如A→b(b?A)的蘊(yùn)涵可由決策蘊(yùn)涵表示，則所有的蘊(yùn)涵都可由決策蘊(yùn)涵表示。

4.2 蘊(yùn)涵表示的幾種情況

接下來(lái)，具體分析形如A→b(b?A)的蘊(yùn)涵。

在形式背景K=(G,M,I) 中，如果令M=C?D，I=IC?ID，即K=(G,C?D,IC?ID)，則蘊(yùn)涵A→b在K中存在六種情形：

（1）A?C，b∈D；

試驗(yàn)固定鮮花椒的添加量為 150 g，菜籽油添加量為 650 g，考察十三香添加量對(duì)“貢椒魚”火鍋品質(zhì)的影響，結(jié)果見(jiàn)圖2。

（2）A?D，b∈D；

（3）A?C≠?，A?D≠?，b∈D；

（4）A?C，b∈C；

（5）A?D，b∈C；

（6）A?C≠?，A?D≠?，b∈C。

情形（1）、（2）、（3）可綜合表示為A2?A3→b，其中A2?C，A3?D，b∈D，A2?A3=A；情形（4）、（5）、（6）可綜合表示為A2?A3→b，其中A2?C，A3?D，b∈C，A2?A3=A。

顯然，情形（1）為K=(G,C,D,I)上的決策蘊(yùn)涵，情形（5）為K=(G,D,C,I) 上的決策蘊(yùn)涵；情形（2）為K=(G,D,I) 上的蘊(yùn)涵，情形（4）為K=(G,C,I) 上的蘊(yùn)涵。這說(shuō)明，情形（1）和（5）已經(jīng)歸結(jié)為決策蘊(yùn)涵；情形（2）和（4）已經(jīng)歸結(jié)為子背景上的蘊(yùn)涵，因此可以按照后述方法，進(jìn)一步將（2）和（4）歸結(jié)為子背景上的決策蘊(yùn)涵。

需要判斷形如情形（3）和（6）的蘊(yùn)涵是否能由決策蘊(yùn)涵表示出來(lái)。在語(yǔ)義上，若形如情形（3）、（6）的蘊(yùn)涵能由形如情形（1）、（2）、（4）、（5）的蘊(yùn)涵通過(guò)蘊(yùn)涵推理規(guī)則得出，則形如情形（3）、（6）的蘊(yùn)涵是冗余的。另外，注意到互換情形（3）中C和D即可得到情形（6），反之亦然。這說(shuō)明，如果情形（3）是冗余的，則情形（6）必然也是冗余的；如果情形（3）不是冗余的，需要一些特殊的方法才能生成，則互換方法中C和D，即可生成情形（6）的蘊(yùn)涵。因此，只需考慮情形（3）即可。

現(xiàn)在考慮情形（3）中蘊(yùn)涵A→b的表示。首先，有下面的結(jié)論。

引理3設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，A→b是K上的一個(gè)蘊(yùn)涵，其中A?C≠?，A?D≠?，b∈D。如果A→b可以被決策蘊(yùn)涵表示，則A→b最后一步必然是使用偽傳遞性推理規(guī)則推導(dǎo)出的。

證明如果A→b可以被表示，那么A→b必然是由三條蘊(yùn)涵推理規(guī)則推導(dǎo)出來(lái)的。如果利用自反性推理規(guī)則，因?yàn)樵撏评硪?guī)則具有自反性，顯然不能說(shuō)明A→b可以被決策蘊(yùn)涵表示。因此，不能使用該推理規(guī)則推導(dǎo)出A→b。

對(duì)于增廣性推理規(guī)則，若X?Z→Y可應(yīng)用于A→b，則X?Z=A和Y=。由于A為能使蘊(yùn)涵b成立的最小前件，因此對(duì)于任何N?A，N→均不成立。顯然，為了使推理規(guī)則有意義，Z≠?，此時(shí)仍有X?A。當(dāng)X?A時(shí)，X→不成立，即不能由X→得到A→b；當(dāng)X=A時(shí)，X→即為A→b，這表示A→b依賴于A→b。因此，增廣性推理規(guī)則不能說(shuō)明A→b可以被決策蘊(yùn)涵表示，不能使用該推理規(guī)則推導(dǎo)出A→b。

下面考慮偽傳遞性推理規(guī)則。顯然，如果A→b可以使用偽傳遞性推理規(guī)則推導(dǎo)出，則必有

成立。此時(shí)有X?Z=A。顯然，當(dāng)X→Y或Y?Z→b等于A→b時(shí)，該推理事實(shí)上是無(wú)效的。同時(shí)，若X→Y或Y?Z→b依賴于A→b時(shí)，則A→b也不能用偽傳遞性推理規(guī)則推導(dǎo)出；其中，X→Y依賴于A→b是指滿足條件b∈Y且A?X，因?yàn)閄→Y依賴于X→b，而X→b可由A→b使用增廣性推理規(guī)則推得；類似地，Y?Z→b依賴于A→b是指A?Y?Z。進(jìn)一步，有下面的結(jié)論。

定理1設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，A→b是K上的一個(gè)蘊(yùn)涵，其中A?C≠?，A?D≠?，b∈D。A→b可以使用偽傳遞性推理規(guī)則推導(dǎo)出，當(dāng)且僅當(dāng)存在X,Y,Z?C?D，滿足X≠?，Y≠?，b?Y，Y?Z?A，A?Y?Z，X?Z=A且使式（1）成立。

證明（必要性）若X=?，則Z=A，而要使?→Y成立，Y只能為?，從而Y?Z→b即 為A→b，因此X≠?。

現(xiàn)證Y≠?。由于A為能使蘊(yùn)涵b成立的最小前件，因此對(duì)于任何N?A，N→均不成立。由X?Z=A可知Z?A；當(dāng)Z?A時(shí)Z→不成立，為使Y?Z→b成立，有Y≠?；當(dāng)Z=A時(shí)，Z→即為A→b，若Y=?，則Y?Z→b即為A→b，這表示A→b依賴于A→b，因此A→b不能用偽傳遞性推理規(guī)則推導(dǎo)出，仍有Y≠?。

現(xiàn)假設(shè)b∈Y，因?yàn)閄→Y成立，由引理1 可知X→b成立。此時(shí)，由X?Z=A可 知X?A，因 為X?Z為能使蘊(yùn)涵X?Z→b成立的最小前件，所以，當(dāng)X?A時(shí)X→b不成立，矛盾；當(dāng)X=A時(shí)，X→b即為A→b，因此X→Y依賴于A→b，這表示A→b不能用偽傳遞性推理規(guī)則推導(dǎo)出。因此有b?Y。

現(xiàn)假設(shè)Y?Z?A。因?yàn)锳為能使蘊(yùn)涵A→b成立的最小前件，所以，當(dāng)Y?Z?A時(shí)Y?Z→b不成立，矛盾。因此有Y?Z?A。

現(xiàn)假設(shè)A?Y?Z，由增廣性推理規(guī)則可知，Y?Z→b可以由A→b推得，這表示Y?Z→b依賴于A→b。因此有A?Y?Z。

（充分性）因?yàn)锳為能使蘊(yùn)涵A→b成立的最小前件，所以對(duì)于任何N?A，N→ 均不成立，Y?Z?A保證了Y?Z→b的可成立性。由題設(shè)可知，為證明A→b可以使用偽傳遞性推理規(guī)則推導(dǎo)出，只需證X→Y和Y?Z→b不等于且不依賴 于A→b即可。

由b?Y可知X→Y不等于且不依賴于A→b。

由A?Y?Z可知，Y?Z→b不等于且不依賴于A→b。

在定理1 中，因?yàn)閄,Y,Z?C?D，所以X→Y和Y?Z→b均可能屬于情形（3）或情形（6），換句話說(shuō)，情形（3）又依賴于情形（3）或情形（6）。因此，可將定理1 進(jìn)一步分為兩種情況：一種情況是可以使用偽傳遞性推理規(guī)則由情形（1）、（2）、（4）、（5）推導(dǎo)出情形（3），稱為直接表示；另一種情況是情形（3）必須依賴于情形（3）或（6）才能推導(dǎo)出，稱為間接表示。

由于蘊(yùn)涵推理的復(fù)雜性，目前暫未發(fā)現(xiàn)需要間接表示的蘊(yùn)涵，因此本文只考慮直接表示。首先給出直接表示A→b的判定條件。

定理2設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，A→b是K上的一個(gè)蘊(yùn)涵，其中A?C≠?，A?D≠?，b∈D。A→b可以使用偽傳遞性推理規(guī)則直接表示當(dāng)且僅當(dāng)存在X≠?，Y≠?，b?Y，Y?Z?A，A?Y?Z，X?Z=A且滿足以下條件之一：

（1）X=A2，Z=A3，且存在Y?D使式（1）成立；

（2）X=A3，Z=A2，且存在Y?C使式（1）成立。

證明根據(jù)題設(shè)，A→b屬于情形（3）中的蘊(yùn)涵。

（必要性）若情形（3）中A→b可以使用偽傳遞性推理規(guī)則直接表示，則必滿足定理1 所給條件；進(jìn)一步，X→Y和Y?Z→b均不屬于情形（3）或（6）的蘊(yùn)涵。因此，X必不滿足X?C≠?且X?D≠?，Z必不滿足Z?C≠?且Z?D≠?，此時(shí)有X=A2,Z=A3或X=A3,Z=A2。當(dāng)X=A2,Z=A3時(shí)，X→Y必不屬于情形（3）或（6），Y?Z→b不屬于情形（3）或（6）時(shí)Y需滿足Y?C=?，即Y?D；當(dāng)X=A3,Z=A2時(shí)，X→Y必不屬于情形（3）或（6），Y?Z→b不屬于情形（3）或（6）時(shí)Y需滿足Y?D=?，即Y?C。

（充分性）由假設(shè)和定理1 可知，A→b可以使用偽傳遞性推理規(guī)則表示。

現(xiàn)分別假設(shè)條件（1）、（2）成立時(shí)來(lái)證X→Y和Y?Z→b必不屬于或依賴于情形（3）或（6）。

（1）當(dāng)X=A2，Z=A3且存在Y?D時(shí)，顯然，X→Y屬于情形（1），Y?Z→b屬于情形（2）。

（2）當(dāng)X=A3，Z=A2且存在Y?C時(shí)，顯然，X→Y屬于情形（5），Y?Z→b屬于情形（1）。

定理1 雖然給出了情形（3）中A→b冗余的充要條件，但仍不能確定情形（3）的冗余性。下面給出一個(gè)例子，來(lái)說(shuō)明情形（3）不是冗余的，換句話說(shuō)，存在情形（3）所示的蘊(yùn)涵不能被決策蘊(yùn)涵表示。

例1一個(gè)決策背景如表1 所示，其中{x1,x2,x3,x4}代表4個(gè)對(duì)象，{a}是條件屬性集，{b,d}是決策屬性集。

Table 1 Decision context表1 決策背景

顯然，{a}?j5i0abt0b→b是該決策背景的蘊(yùn)涵，令A(yù)2{a}，A3j5i0abt0b，則{a}?j5i0abt0b→b屬于情形（3）。接下來(lái)，利用偽傳遞性推理規(guī)則來(lái)推導(dǎo)該蘊(yùn)涵。由定理1，首先假設(shè)X≠?，Y≠?。

首先考慮Z=?的情況。此時(shí)，需要找到Y(jié)使

成立。Y所有可能的取值為{a,b,d,ab,ad,bd,abd} 。當(dāng)Y取{a,d}中的任意一個(gè)時(shí)，Y→b均不成立；當(dāng)Y取{b,ab,ad,bd,abd}中的任意一個(gè)時(shí)，用到{a}?j5i0abt0b→b本身。因此，當(dāng)Z=?時(shí)，不存在Y使{a}?j5i0abt0b→b可以由其他蘊(yùn)涵推導(dǎo)出，即{a}?j5i0abt0b→b不冗余。

接下來(lái)考慮Z≠?的情況。此時(shí)需要找到Y(jié)使

成立。Y所有可能的取值為{a,b,d,ab,ad,bd,abd} 。當(dāng)Y取{b,d,ab,ad,bd,abd}中的任意一個(gè)時(shí)，{a}→Y不成立；當(dāng)Y取{ }a時(shí)，用到{a}?j5i0abt0b→b本身。類似地，當(dāng)Y取{a,b,ab,ad,bd,abd}中的任意一個(gè)時(shí)，j5i0abt0b→Y不成立；當(dāng)Y取j5i0abt0b 時(shí)，Y?{a}→b不成立。因此，當(dāng)Z≠?時(shí)，不存在Y使{a}?j5i0abt0b→b可以由其他蘊(yùn)涵推導(dǎo)出，即{a}?j5i0abt0b→b不冗余。

4.3 蘊(yùn)涵表示的具體方法

例1 表明，某些蘊(yùn)涵確實(shí)不可直接歸結(jié)為決策蘊(yùn)涵和子背景的蘊(yùn)涵。因此，需找到蘊(yùn)涵不可以被直接表示時(shí)Y應(yīng)滿足的條件，并生成相應(yīng)的蘊(yùn)涵。為此，首先討論決策屬性只有一個(gè)屬性的情形下，Y存在或不存在的情況。有下面的結(jié)論。

引理4設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，A→b是K上的一個(gè)蘊(yùn)涵，其中A?C≠?，A?D≠?，b∈D。若決策屬性D中只有一個(gè)屬性，則A→b是冗余的。

證明根據(jù)題設(shè)，A→b屬于情形（3）中的蘊(yùn)涵。若決策屬性D中只有一個(gè)屬性，由于b∈D，因此有A3=，故A→b是冗余的。事實(shí)上，由自反性推理規(guī)則可知→b成立，再由增廣性推理規(guī)則可知A→b成立。

接下來(lái)，分析當(dāng)決策屬性D中只有一個(gè)屬性時(shí)，情形（6）中的蘊(yùn)涵是否可以被直接表示?；谠撉樾蔚姆治?，可以將形式背景分為只含有一個(gè)決策屬性的決策背景，然后生成該決策背景中的決策蘊(yùn)涵，因?yàn)榍樾危?）的蘊(yùn)涵是冗余的，因此不需要生成，如果情形（6）中的蘊(yùn)涵是不可以被直接表示的，則可以生成不可以被直接表示的蘊(yùn)涵；接下來(lái)，就可以考慮去掉該決策屬性之后的形式背景；以此類推，可以生成所有的蘊(yùn)涵集。

容易證明，定理1、定理2對(duì)于情形（6）也是成立的。

推論1設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，A→b是K上的一個(gè)蘊(yùn)涵，其中A?C≠?，A?D≠?，b∈C。A→b可以使用偽傳遞性推理規(guī)則推導(dǎo)出，當(dāng)且僅當(dāng)存在X,Y,Z?C?D，滿足X≠?，Y≠?，b?Y，Y?Z?A，A?Y?Z，X?Z=A且使式（1）成立。

推論2設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，A→b是K上的一個(gè)蘊(yùn)涵，其中A?C≠?，A?D≠?，b∈C。A→b可以使用偽傳遞性推理規(guī)則直接表示當(dāng)且僅當(dāng)存在X≠?，Y≠?，b?Y，Y?Z?A，A?Y?Z，X?Z=A且滿足以下條件之一：

（1）X=A2，Z=A3，且存在Y?D使式（1）成立；

（2）X=A3，Z=A2，且存在Y?C使式（1）成立。

下面的例子表明，當(dāng)決策屬性D中只有一個(gè)屬性時(shí)，對(duì)于推論2 所示的兩種情況，情形（6）中的蘊(yùn)涵不總是可以被直接表示的。

例2對(duì)于表1 中的決策背景，令{a,b}是條件屬性集，j5i0abt0b 是決策屬性集，則{a}?j5i0abt0b→b為蘊(yùn)涵。令A(yù)2?{a}，A3?j5i0abt0b，則{a}?j5i0abt0b→b屬于情形（6）。接下來(lái)，利用偽傳遞性推理規(guī)則來(lái)推導(dǎo)該蘊(yùn)涵。

首先考慮推論2 中（1）。此時(shí)，需要找到Y(jié)?D使式（1）成立。由表1 可知Y只能取j5i0abt0b，由j5i0abt0b→b不成立可知{a}?j5i0abt0b→b不可以被直接表示。

接下來(lái)考慮推論2 中（2）。此時(shí)，需要找到Y(jié)?C使式（1）成立。Y所有可能的取值為{a,b,ab}。無(wú)論Y取何值，j5i0abt0b→Y均不成立，因此{(lán)a}?j5i0abt0b→b不可以被直接表示。

由例2 可知，需找出當(dāng)決策屬性D中只有一個(gè)屬性時(shí)，對(duì)于推論2 所示的兩種情況，情形（6）中的蘊(yùn)涵A→b不可以被直接表示的充要條件及發(fā)現(xiàn)算法。

對(duì)于推論2 中（1），有下面的結(jié)論。

引理5設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景，A→b是K上的一個(gè)蘊(yùn)涵，其中A?C≠?，A?D≠?，b∈C。若決策屬性D中只有一個(gè)屬性，則X=A2，Z=A3，Y?D時(shí)，A→b不可以被直接表示。

證明當(dāng)D中只有一個(gè)屬性d時(shí)，由Y≠?和Y?D可 知Y=j5i0abt0b，由Z=A3?D可 知Z=j5i0abt0b，由A?D≠?和A?C≠?可知Y?Z?A，再由A為能使蘊(yùn)涵b成立的最小前件可知Y?Z→b不成立，從而A→b必不可以被直接表示。

由引理5 可知，當(dāng)決策屬性D中只有一個(gè)屬性時(shí)，對(duì)于推論2 中（1），情形（6）中的蘊(yùn)涵A→b是不可以被直接表示的，由于A→b可以被直接表示時(shí)只需滿足推論2 條件之一，因此，若對(duì)于推論2 中（2），A→b也不可以被直接表示，那么情形（6）中的蘊(yùn)涵A→b必不可以被直接表示。接下來(lái)給出對(duì)于推論2中（2）情形（6）中的蘊(yùn)涵A→b也不可以被直接表示的判定條件。

定理3設(shè)K=(G,C?D,IC?ID)是一個(gè)決策背景且D中只有一個(gè)屬性d。A→b是K上的一個(gè)蘊(yùn)涵，其中A?C≠?，A?D≠?，b∈C。蘊(yùn)涵A→b不可以被直接表示，當(dāng)且僅當(dāng)任意的Y?C均滿足以下條件之一：

（1）Y=?；

（2）b∈Y；

（3）Y?A2?A；

（4）A?Y?A2；

（5）存在g滿足gD=j5i0abt0b且Y?gC；

（6）存在g滿足(Y?A2)?gC且b?gC。

其中A=A3?A2,A3?D,A2?C,b∈C,g∈G。

證明根據(jù)題設(shè)，A→b屬于情形（6）中的蘊(yùn)涵。由推論2 可知，情形（6）中的蘊(yùn)涵A→b不可以被直接表示當(dāng)且僅當(dāng)條件（1）～（4）之一成立或推論2 中（1）和（2）皆不成立。若D中只有一個(gè)屬性d時(shí)，由引理5 可知，推論2 中（1）必不成立；因此，若D中只有一個(gè)屬性d時(shí)，情形（6）中的蘊(yùn)涵A→b不可以被直接表示當(dāng)且僅當(dāng)條件（1）～（4）之一成立或推論2 中（2）不成立?，F(xiàn)只需證推論2 中（2）不成立當(dāng)且僅當(dāng)條件（5）或（6）成立即可。

因?yàn)镈中只有一個(gè)屬性d，所以A3=j5i0abt0b。因此，只需證不存在Y?C使式（2）成立

當(dāng)且僅當(dāng)條件（5）或（6）成立。這是顯然的，因?yàn)椴淮嬖赮?C使式（2）成立當(dāng)且僅當(dāng)不存在Y?C使j5i0abt0b→Y或Y?A2→b成立，當(dāng)且僅當(dāng)（存在g滿足gD=j5i0abt0b且Y?gC）或（存在g滿足(Y?A2)?gC且b?gC），當(dāng)且僅當(dāng)條件（5）或（6）成立。

當(dāng)D中只有一個(gè)屬性d時(shí)，由引理5 可知，情形（3）中的蘊(yùn)涵都是冗余的，因此不必生成；對(duì)于情形（6），定理3 事實(shí)上給出了不可被直接表示的蘊(yùn)涵的生成方法。

對(duì)于形式背景K=(G,M,I)，令D=j5i0abt0b，C=MD，I=IC?ID，即得到只含一個(gè)決策屬性的決策背景KC|D=(G,C?D,IC?ID)和只含一個(gè)條件屬性的決策背景KD|C=(G,D?C,ID?IC)。生成形式背景K的具體步驟如下：

（1）生成決策背景KC|D的決策蘊(yùn)涵。

（2）生成決策背景KD|C的決策蘊(yùn)涵。

（3）生成K不可被直接表示的蘊(yùn)涵：

①對(duì)于任意的A2?C和任意的b∈C執(zhí)行②和③。

②令A(yù)3=j5i0abt0b?D，A=A3?A2，根據(jù)定理3檢查是否存在Y?C滿足定理3 條件（1）～（6）之一。若滿足，則執(zhí)行步驟③，否則執(zhí)行①。

③判斷A→b是否成立。若成立，則生成蘊(yùn)涵A→b。

（4）從K中移除屬性d，并記Kd=(G,Mj5i0abt0b,II{}d)，對(duì)Kd重新執(zhí)行該算法。

顯然，上述算法的復(fù)雜度較高，因此難以應(yīng)用于具體的數(shù)據(jù)集中。

5 結(jié)論與展望

本文首先對(duì)蘊(yùn)涵進(jìn)行了邏輯簡(jiǎn)化，然后使用蘊(yùn)涵推理規(guī)則研究蘊(yùn)涵是否可以由決策蘊(yùn)涵表示，首先給出了蘊(yùn)涵可以被直接表示時(shí)應(yīng)滿足的條件。實(shí)例表明，不是所有的蘊(yùn)涵都可以直接歸結(jié)為決策蘊(yùn)涵，因此找出了不可以直接歸結(jié)為決策蘊(yùn)涵的蘊(yùn)涵應(yīng)滿足的充要條件，并給出了不可以直接歸結(jié)為決策蘊(yùn)涵的蘊(yùn)涵的生成方法。

文中提到了蘊(yùn)涵的間接表示，但由于蘊(yùn)涵推理的復(fù)雜性，暫未對(duì)其進(jìn)行深入研究。另外，即使不能被直接表示的蘊(yùn)涵的生成算法也有較大的復(fù)雜度，因此難以應(yīng)用于具體的數(shù)據(jù)。這些都是下一步需要研究的問(wèn)題。

另外可以發(fā)現(xiàn)，存在一些蘊(yùn)涵可以由決策蘊(yùn)涵表示，那么決策蘊(yùn)涵規(guī)范基與蘊(yùn)涵規(guī)范基、決策蘊(yùn)涵推理規(guī)則與蘊(yùn)涵推理規(guī)則以及決策背景上的概念格與形式背景上的概念格之間又存在怎樣的聯(lián)系?進(jìn)一步，本文的研究是否可以推廣到模糊決策蘊(yùn)涵[17-18，30]以及可變決策蘊(yùn)涵[31]？這些問(wèn)題也是接下來(lái)需要研究的。