邏輯型決策蘊涵

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

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

0 引言

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

1 決策蘊涵

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

1.1 決策蘊涵邏輯

1.1.1決策蘊涵邏輯的語義

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

定義2[2]設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中語義導出，記為L├A→B。若任意的A1→B1∈L1都可以從L中語義導出，則稱L1可以從L中語義導出，記為L├L1。

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

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

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

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

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

性質1[2]設L是決策蘊涵集，A→B是一個決策蘊涵，則L├A→B當且僅當B?AL。

1.1.2決策蘊涵邏輯的語構 在決策蘊涵邏輯的語構方面，文獻[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當且僅當A→B可以使用擴增推理規(guī)則和合并推理規(guī)則從L1推出。

1.2 決策背景中的決策蘊涵

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

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

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

定義5[5]設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]設K=(G,C∪D,IC∪ID)為決策背景，A?C，B?D。若AC?BD，則稱A→B是K的一個決策蘊涵。

2 邏輯型決策蘊涵的語義

2.1 邏輯型決策蘊涵的引入

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

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

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

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

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

進一步可以驗證，與經典決策蘊涵相比，邏輯型決策蘊涵能夠提供更豐富的決策知識。以表1中的決策蘊涵{下雨}→?為例，顯然，條件“下雨”沒有蘊含任何結論。然而，當把邏輯算子“∨”和“”引入到決策蘊涵的結論中，從表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。

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

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

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

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

4)φ1≠0，φ≤φ1當且僅當φ∧φ1=0，且當且僅當φ∧φ1=0。

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

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

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

類似可證明φ≤φ1當且僅當φ∧φ1=0。

2.4 邏輯型決策蘊涵的語義導出

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

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

定義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中語義導出，記作L├φ→ψ，若滿足下列條件：(a) 存在T1?C∪D滿足T1╞L且T1?φ；(b) 對于任意的T?C∪D，T╞L蘊含T╞φ→ψ。

2)L1可以從L中語義導出，若任意的φ→ψ∈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是完備的。

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

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

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

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

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

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

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

是ψ的協(xié)調式。

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

性質3C是條件屬性集，D是決策屬性集，有下列結論成立。

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

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

3 邏輯型決策蘊涵的語構

本文提出一條關于邏輯型決策蘊涵的推理規(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∨。假設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∨。假設T?φ，因為T╞φ→φL∨，由定義12可知T?φL∨；又因為ψ≤φL∨，所以T?ψ，進而T╞φ→ψ，(b)成立。

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

證明首先證明φ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∨。

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

4 小結

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