張少霞， 李德玉,2， 翟巖慧,2

(1. 山西大學(xué) 計算機與信息技術(shù)學(xué)院 山西 太原 030006； 2. 山西大學(xué) 計算智能與中文信息 處理教育部重點實驗室 山西 太原 030006)

0 引言

形式概念分析是一種從形式背景建立概念格來進行數(shù)據(jù)分析、知識表示和規(guī)則提取的強有力工具。蘊涵是形式概念分析中進行知識表示的基本形式，決策蘊涵[1-7]是蘊涵在決策情形下的擴展。然而，決策蘊涵并不能夠表達(dá)所有的決策知識，即存在信息的損失。這是因為決策蘊涵制定了嚴(yán)格的決策規(guī)則，只有當(dāng)條件的所有屬性都被滿足時，結(jié)論的所有屬性才能被滿足，而忽略了條件和結(jié)論的部分或全部屬性不被滿足的情況下所蘊含的決策知識。屬性?；切问礁拍罘治鲋辛Ｓ嬎惴椒ǖ闹饕芯績?nèi)容之一[8-9]，可以通過邏輯算子“∧”“∨”“”將若干屬性進行組合，獲得邏輯公式，實現(xiàn)功能強大的對象描述能力。為了獲取更加豐富的決策知識，本文基于邏輯公式定義了邏輯型決策蘊涵，驗證了邏輯型決策蘊涵能夠比經(jīng)典決策蘊涵提供更豐富的決策知識；類似于經(jīng)典決策蘊涵，對邏輯型決策蘊涵進行了邏輯方面的研究。鑒于利用邏輯型決策蘊涵進行知識推理時會引起矛盾的結(jié)論，而矛盾的結(jié)論不能為用戶提供正確的決策，本文設(shè)計了邏輯型決策蘊涵的語義框架，該框架可以過濾掉推導(dǎo)結(jié)論中的矛盾。語構(gòu)方面定義了閉包縮小推理規(guī)則，并證明了其相對于語義的合理性和完備性。

1 決策蘊涵

決策蘊涵有邏輯研究和數(shù)據(jù)研究兩種研究方式。決策蘊涵的邏輯研究包括語義和語構(gòu)兩個方面：語義方面研究決策蘊涵的合理性、完備性和無冗余性；語構(gòu)方面研究推理規(guī)則的合理性、完備性和無冗余性。決策蘊涵的數(shù)據(jù)研究就是決策背景中的決策蘊涵研究。

1.1 決策蘊涵邏輯

1.1.1決策蘊涵邏輯的語義

定義1[2]設(shè)C是條件屬性集，D是決策屬性集，其中C∩D=?。若A?C且B?D，則稱A→B是一個決策蘊涵。此時，A為該決策蘊涵的前提，B為該決策蘊涵的結(jié)論。

定義2[2]設(shè)C是條件屬性集，D是決策屬性集,L和L1是決策蘊涵集。定義：

1)T?C∪D，A→B是決策蘊涵。若AT∩C或B?T∩D，則稱T滿足A→B(或稱T是A→B的模型)，記為T╞A→B。若T滿足L中的任意一個決策蘊涵，則T是L的模型，記為T╞L。

2) 若對于任意的T?C∪D，T╞L蘊含T╞A→B，則稱A→B可以從L中語義導(dǎo)出，記為L├A→B。若任意的A1→B1∈L1都可以從L中語義導(dǎo)出，則稱L1可以從L中語義導(dǎo)出，記為L├L1。

3) 若L{A→B}├/{A→B}，則稱L是無冗余的。

4) 若任意可以從L中語義導(dǎo)出的決策蘊涵都包含在L中，則稱L是封閉的。

5) 對于封閉的決策蘊涵集L，若L1?L且L1├L，則稱L1相對于L是完備的。

定義3[2]設(shè)C是條件屬性集，L是決策蘊涵集，A?C在L上的閉包為

AL=∪{Bi|Ai→Bi∈L,Ai?A}。

性質(zhì)1[2]設(shè)L是決策蘊涵集，A→B是一個決策蘊涵，則L├A→B當(dāng)且僅當(dāng)B?AL。

1.1.2決策蘊涵邏輯的語構(gòu) 在決策蘊涵邏輯的語構(gòu)方面，文獻[7]提出了兩條推理規(guī)則，并證明了它們相對于語義的合理性和完備性。

定理1[2]擴增推理規(guī)則和合并推理規(guī)則是合理的，即

1)A→B是一個決策蘊涵，若A1?A且B1?B，則A→B├A1→B1。

2)A→B和A1→B1是決策蘊涵，則{A→B,A1→B1}├A∪A1→B∪B1。

定理2[2]擴增推理規(guī)則和合并推理規(guī)則是完備的，即對任意封閉的決策蘊涵集L及其完備集L1?L，A→B∈L當(dāng)且僅當(dāng)A→B可以使用擴增推理規(guī)則和合并推理規(guī)則從L1推出。

1.2 決策背景中的決策蘊涵

定義4[5]決策背景是一個三元組K=(G,C∪D,IC∪ID)，其中G是對象集，C是條件屬性集，D是決策屬性集，IC?G×C是條件關(guān)聯(lián)關(guān)系，ID?G×D是決策關(guān)聯(lián)關(guān)系。對于g∈G，m∈C∪D，(g,m)∈IC或(g,m)∈ID表示對象g具有屬性m。

例1表1給出了一個與現(xiàn)實生活相關(guān)的決策背景K=(G,C∪D,IC∪ID)，其中G={g1,g2,g3,g4}，C={下雨,刮風(fēng)}，D={打傘,穿雨衣,打羽毛球}。表中某行與某列的交點處為1表示這個對象含有這個屬性。

表1 決策背景實例Table 1 A decision context example

定義5[5]設(shè)K=(G,C∪D,IC∪ID)為決策背景，對于集合A1?C，A2?D，B?G，記

3)BC={m∈C|(g,m)∈IC,?g∈B}；

4)BD={m∈D|(g,m)∈ID,?g∈B}。

定義6[5]設(shè)K=(G,C∪D,IC∪ID)為決策背景，A?C，B?D。若AC?BD，則稱A→B是K的一個決策蘊涵。

2 邏輯型決策蘊涵的語義

2.1 邏輯型決策蘊涵的引入

盡管已經(jīng)提出了完備的決策蘊涵集，但決策蘊涵仍然存在決策信息的損失，如例2所示。

例2以表1中的決策背景為例，根據(jù)定義6可以計算得到所有的決策蘊涵，即?→?，{刮風(fēng)}→?，{下雨,刮風(fēng)}→?,?→{打羽毛球}，{下雨}→?和{下雨，刮風(fēng)}→{穿雨衣}，其中只有{下雨,刮風(fēng)}→{穿雨衣}是有意義的決策知識。

事實上，表1還蘊含著其他的決策知識，如“若刮風(fēng)，則不能打羽毛球”和“若下雨，則打傘或穿雨衣”等，而這些知識并不能被決策蘊涵所表達(dá)。這是因為決策蘊涵規(guī)定：只有當(dāng)條件的所有屬性都被滿足時，結(jié)論的所有屬性才能被滿足，而忽略了條件和結(jié)論的部分或全部屬性不被滿足的情況下所蘊含的決策知識。基于此，將邏輯算子“∧”“∨”和“”引入到?jīng)Q策蘊涵中，進而從表1得到了更多的決策知識，如表2所示。

表2 表1中的決策知識Table 2 The decision knowledge in Table 1

決策蘊涵可以看作是只引入了“∧”算子的邏輯型決策蘊涵，因此后者可以蘊含前者的所有決策知識。以表1的決策蘊涵{下雨，刮風(fēng)}→{穿雨衣}為例，表2的“下雨∧刮風(fēng)→打傘∧穿雨衣∧打羽毛球”蘊含該知識。

進一步可以驗證，與經(jīng)典決策蘊涵相比，邏輯型決策蘊涵能夠提供更豐富的決策知識。以表1中的決策蘊涵{下雨}→?為例，顯然，條件“下雨”沒有蘊含任何結(jié)論。然而，當(dāng)把邏輯算子“∨”和“”引入到?jīng)Q策蘊涵的結(jié)論中，從表1可以看出，該條件事實上蘊含了“打傘或穿雨衣，且不打羽毛球”，即表2的“下雨→打傘∨穿雨衣∧打羽毛球”。

2.2 邏輯公式

定義7[10]C是一個屬性集，對于p∈C，稱p為C的原子公式。用邏輯連接詞“”“∧”或“∨”將C的有限個原子公式連接起來的式子叫作C的邏輯公式，簡稱為邏輯公式。稱原子公式p及其否定p為文字。φ是C的邏輯公式，記l(φ)為φ中文字的集合。

2.3 邏輯公式的模型及其偏序

定義9C是一個屬性集，φ和ψ是C的邏輯公式，T?C。對于φ=a，若a∈T，稱T滿足φ。若T滿足φ和ψ，稱T滿足φ∧ψ；若T滿足φ或ψ，稱T滿足φ∨ψ。若T不滿足φ，稱T滿足φ；若T滿足φ，稱T是φ的模型，記作T?φ。φ的所有模型記為M(φ)。

若M(φ)=?，稱φ是矛盾的，記φ=0。若l(φ)=?，記φ=null，且任意的T?C有T?φ。

定義10C是一個屬性集，φ1和φ2是C的邏輯公式，且φ1,φ2≠0。若M(φ1)?M(φ2)，稱φ2≤φ1；若M(φ1)=M(φ2)，稱φ2≈φ1。

性質(zhì)2C是一個屬性集，φ是C的邏輯公式，有下列結(jié)論成立。

1) (范式存在定理[10])φ可以通過雙重否定律、德摩根律和分配率得到其析取范式和合取范式，將φ的析取范式和合取范式分別記為φ∧∨和φ∨∧。

2)φ≈φ∧∨≈φ∨∧。

3)φ=0當(dāng)且僅當(dāng)對于任意的φ∧∈L(φ∧∨)，存在a∈C滿足{a,a}?l(φ∧)。

4)φ1≠0，φ≤φ1當(dāng)且僅當(dāng)φ∧φ1=0，且當(dāng)且僅當(dāng)φ∧φ1=0。

證明2) 的證明過程類似于范式存在定理的證明[10]，3) 顯然成立。

下面證明4)。首先證明φ≤φ1當(dāng)且僅當(dāng)φ∧φ1=0。

充分性。因為φ1≠0，可令T?C且T?φ1。又因為φ∧φ1=0，顯然T?/φ，根據(jù)定義9可知T?φ。綜上所述，任意的T?φ1，有T?φ，即φ≤φ1。

類似可證明φ≤φ1當(dāng)且僅當(dāng)φ∧φ1=0。

2.4 邏輯型決策蘊涵的語義導(dǎo)出

定義11C是條件屬性集，D是決策屬性集，φ是C的邏輯公式，ψ是D的邏輯公式。若φ≠0且ψ≠0，則稱φ→ψ是邏輯型決策蘊涵。

例3給定邏輯型決策蘊涵“下雨∧刮風(fēng)→打羽毛球∨跑步”和“天陰→打羽毛球”。條件“下雨∧刮風(fēng)∧天陰”，同時滿足這兩條決策蘊涵的條件，根據(jù)決策蘊涵的合并推理規(guī)則，可以得到結(jié)論“打羽毛球∨跑步∧打羽毛球”，即“(打羽毛球∧打羽毛球)∨(跑步∧打羽毛球)”。然而，結(jié)論中“打羽毛球∧打羽毛球”是矛盾的。因此，需要定義合適的語義來解決這種矛盾。

定義12C是條件屬性集，D是決策屬性集，T?C∪D，φ→ψ是邏輯型決策蘊涵，L是邏輯型決策蘊涵集。定義：

1)T是φ→ψ的模型，若T∩C?/φ或T∩D?ψ，記作T╞φ→ψ。

2)T是L的模型，若任意的φ1→ψ1∈L，有T╞φ1→ψ1，記作T╞L。

定義13C是條件屬性集，D是決策屬性集，φ→ψ是邏輯型決策蘊涵，L和L1是邏輯型決策蘊涵集。定義：

1)φ→ψ可以從L中語義導(dǎo)出，記作L├φ→ψ，若滿足下列條件：(a) 存在T1?C∪D滿足T1╞L且T1?φ；(b) 對于任意的T?C∪D，T╞L蘊含T╞φ→ψ。

2)L1可以從L中語義導(dǎo)出，若任意的φ→ψ∈L1，有L├φ→ψ，記作L├L1。

3) 若L├L1且L1├L，則稱L和L1等價。

4)L是無冗余的，若任意的φ→ψ∈L，都有L{φ1→φ2}├φ1→φ2。

5)L是封閉的，若任意的L├φ→ψ，有φ→ψ∈L。進一步，若L1?L且L1├L，稱L1相對于L是完備的。

值得注意的是，一些經(jīng)典決策蘊涵中的結(jié)論并不適用于邏輯型決策蘊涵，如例4所示。

例4邏輯型決策蘊涵的語義推導(dǎo)不具有傳遞性，即L├L1且L1├L2并不意味著L├L2。

令C={下雨,刮風(fēng),天陰}，D={打羽毛球}，L={下雨∧刮風(fēng)→打羽毛球，天陰→打羽毛球}，L1={下雨∧刮風(fēng)→打羽毛球}，L2={下雨∧刮風(fēng)∧天陰→打羽毛球}。

可以驗證L├L1且L1├L2。進一步，可以驗證不存在T?C∪D同時滿足T╞L且T?下雨∧刮風(fēng)∧天陰，根據(jù)定義13可知L├/L2。例4也說明L1├φ→ψ并不意味著L├φ→ψ，其中L1?L。

除此之外，φ→ψ∈L并不意味著L├φ→ψ。令C={下雨}，D={打傘，穿雨衣}，L={下雨→打傘，下雨→打傘∧穿雨衣}，可以驗證不存在T?C∪D同時滿足T╞L且T?下雨，根據(jù)定義13可知L├/下雨→打傘。

邏輯型決策蘊涵的語義可以過濾掉推導(dǎo)結(jié)論中的矛盾，首先定義邏輯公式的協(xié)調(diào)式。

定義14D是決策屬性集，ψ是D的邏輯公式，稱

是ψ的協(xié)調(diào)式。

顯然，協(xié)調(diào)式的結(jié)論中不存在矛盾。

性質(zhì)3C是條件屬性集，D是決策屬性集，有下列結(jié)論成立。

2)φ→ψ∨ψ∨ψ1是邏輯型決策蘊涵，φ→ψ∨ψ∨ψ1和φ→null等價。

2) 顯然，對于任意的T?C∪D，T?ψ∨ψ∨ψ1且T?null，即ψ∨ψ∨ψ1≈null。在此基礎(chǔ)上，易證φ→ψ∨ψ∨ψ1和φ→null等價。

3 邏輯型決策蘊涵的語構(gòu)

本文提出一條關(guān)于邏輯型決策蘊涵的推理規(guī)則——閉包縮小推理規(guī)則：

并證明其相對于語義的合理性和完備性。

定理3(合理性)L是邏輯型決策蘊涵集，若φ≠0，φL∨≠0且ψ≤φL∨，則L├φ→ψ。

證明首先證明L├φ→φL∨，只需證明定義13的1)中(a)和(b)成立。首先證明(a)。根據(jù)定義15可知

φL∨=∧{ψ1|φ1→ψ1∈L∨,φ1≤φ}。

(1)

因為φL∨≠0，所以存在T1?D滿足T1?φL∨。令

L1={φ1→ψ1∈L|φ1≤/φ,T1?/ψ1}，

(2)

繼續(xù)證明(b)。令T?C∪D且T╞L，為了證明(b)，只需證明T╞φ→φL∨。假設(shè)T?φ，對于任意的φ1→ψ1∈L∨，根據(jù)定義15可知必存在??L1?L，使得

(3)

綜上所述，若T?φ，則T?φL∨，進而T╞φ→φL∨。

最后證明L├φ→ψ，只需證明定義13的1)中(a)和(b)成立。因為L├φ→φL∨，顯然(a)成立。對于任意的T?C∪D，T╞L蘊含T╞φ→φL∨。令T?C∪D且T╞L，此時T╞φ→φL∨。假設(shè)T?φ，因為T╞φ→φL∨，由定義12可知T?φL∨；又因為ψ≤φL∨，所以T?ψ，進而T╞φ→ψ，(b)成立。

定理4(完備性) 閉包縮小推理規(guī)則是完備的，即對于封閉的邏輯型決策蘊涵集L，若L1?L且L1├L，則任意可以從L導(dǎo)出的邏輯型決策蘊涵φ→ψ都可以運用閉包縮小推理規(guī)則從L1導(dǎo)出。

證明首先證明φL∨≠0。因為L├φ→ψ，根據(jù)定義13可知，存在T╞L滿足T?φ。對于任意的φ1→ψ1∈L∨，根據(jù)定義15可知必存在??L1?L，使得

(4)

再證明ψ≤φL∨。因為φL∨≠0，可令T1?D且T1?φL∨，再令

L1={φk→ψk∈L|φk≤/φ,T1?/ψk}，

(5)

因為L├φ→ψ且T╞L，所以T╞φ→ψ。又因為T2=T∩C?φ，所以T∩D=T1?ψ，即T1?ψ。綜上所述，對于任意的T1?D，若T1?φL∨，則T1?ψ，即ψ≤φL∨。

已經(jīng)證明φL∨≠0且ψ≤φL∨。又因為φ→ψ是邏輯型決策蘊涵，所以φ≠0。此時，根據(jù)定理3可知，運用閉包縮小規(guī)則，可以從L得到φ→ψ。

4 小結(jié)

屬性邏輯是形式概念分析中重要的研究內(nèi)容，決策蘊涵是蘊涵在決策情形下的擴展。與決策蘊涵相比，邏輯型決策蘊涵能夠提供更豐富的決策知識。本文定義了邏輯型決策蘊涵的語義框架，該框架可以過濾掉利用邏輯型決策蘊涵進行知識推理時產(chǎn)生的矛盾的結(jié)論；語構(gòu)方面提出了閉包縮小推理規(guī)則，并證明了其相對于語義的合理性和完備性。邏輯型決策蘊涵的數(shù)據(jù)研究，即決策背景上的邏輯型決策蘊涵，將是下一步研究的重點。