粗糙集理论第3章.docVIP

第 页 PAGE \* Arabic 1 知识的化简 第3.1节 引言 本章讨论如何约减知识库，即如何消除知识库中的冗余知识，分为两种基本类型的约减： 知识（等价关系）的约减； 概念（等价类）的约减； 第3.2节 知识的简式与核 定义3.1 设R是一个等价关系簇。若有一等价关系R∈R，使得IND(R)＝IND(R?{R})，则称R在R中是不必要的(dispensable)，否则称R在R中是必要的(indispensable)。 若?R∈R都是必要的，则说R是独立的(independent)，否则说R是相关的(dependent)。 定理3.1 如果R是独立的，且P ? R，则P也是独立的。 证明：用反证法。 假设P ? R且P是相关的，则存在S ?P 使得IND(S)?IND(P )，故有IND(S ?(R?P ))?IND(R )。IND(R ) = ? R ? ? (P ?(R?P ))= (?(R?P )) ? (?P ) = (?(R?P )) ? (?S ) =? (S ?(R?P )) =IND(S ?(R?P )) 显然又有S ?(R?P)?R，这与R是独立的矛盾. ■ 定义3.2 如果Q ? P，Q是独立的且IND(Q )＝IND(P )，则称Q为P的简式。 显然，P可能有多个简式。 定义3.3 P中所有必要的等价关系的集合称为P的核，记为CORE(P ). 下面的定理给出了简式与核的关系。 定理3.2 P的核CORE(P )＝?RED(P )，其中RED(P )是P的所有简式的簇。 Note：即，对?Q?RED(P )，都有CORE(P )?Q，CORE(P ) 是RED (P )中所有元素的公共部分。 证明： 欲证明定理3.2，我们只需证明CORE(P ) ? ? RED(P )且CORE(P ) ? ? RED(P ) . 为此 先证CORE(P ) ? ? RED(P ) 对于?R，若R?CORE(P )，则R? ? RED(P ) ? 对于?R，若R? ? RED(P )，则R ? CORE(P ) //* G?H= ?G?H；?H??G = ?(?H)?(?G) = ?G?H ? G?H = ?H??G *// 假定存在R使得 R? ? RED(P ). 则一定存在P的某个简式Q使得 R ? Q，即有Q ? P ?{R}?P Q是P的简式? IND(Q )? IND(P ) P ?{R}?P? IND(P ?{R} )IND(P ) ?IND(Q ) Q ? P ?{R}? IND(Q ) IND(P ?{R}) 所以，IND(Q )= IND(P ?{R})= IND(P ) 所以，R是不必要关系，即R ? CORE(P ). 再证CORE(P )? ? RED(P ) 同理，我们只需证明对?R? CORE(P )，必有R?? RED(P ) . 假设R?CORE(P )，R是P中不必要的，即IND(P )?IND(P?{R})，这意味着P中存在一个的独立的等价关系子集S ?P ?{R}，使得IND(S )?IND(P )且R?S（注意此S是P的不包含R的简式）。这意味着如果存在R?CORE(P )，则存在一个不包含R的P的简式S，这使得所有简式的交集也不包含R,即 R?? RED(P )＝?{Q :Q ? RED(P )}成立。即对?R? CORE(P )，则R?? RED(P ) . 故有CORE(P )? ?{Q :Q?RED(P )}成立。 证毕 ■ 讨论：核概念有两个用途 第一、它可作为求解简式的基础，因为任意简式都包含核，且核的计算是直截了当的； 第二、核是最具特点的知识的集合，在知识化简过程中它不能被除去。 例1 设R＝｛P，Q，R｝是由下述三个等价关系组成的簇： U?{x1, x2, x3, x4, x5, x6, x7, x8} U/P＝{{x1, x4, x5}, {x2, x8}, {x3}, {x6, x7}} U/Q＝{{x1, x3, x5}, {x6}, {x2, x4, x7, x8}} U/R＝{{x1, x5}, {x6}, {x2, x7, x8}, {x3, x4}} 于是，IND(R)具有等价类簇 U/IND(R)＝{{x1, x5}, {x2, x8}, {x3}, {x4}, {x6}, {x7}} P是不可缺少的，∵U/IND(R?{P})＝{{x1, x5}, {x2, x7, x8}, {x3}, {x4}, {x6}}?U/IND(R) . Q是冗余的，∵U/IND(R－{Q})＝{{x1, x5}, {x2, x8}, {x3}, {x4}, {x6}, {x7}}＝U/IND（R）. R也是冗余的，∵U/IND(R