θ（简记作x=θ）,当且仅当下面的条件被.PDF

研究生教材《智能信息处理》 5.3 规则提取 规则提取是粗糙集理论研究中一个重要内容之一，已经在数据挖掘、机器学习等领域取得重大进展并得到广 泛应用。为进一步研究决策表约简的规则提取问题，本节主要介绍采用另一种方法，即符号化的方法来研究相容 与不相容算法的约简、最小化以及决策规则的约简问题。 5.3.1 决策规则和算法 为了论述决策规则和算法，我们先来了解一下有关决策逻辑语言的一些定义和命题。Pawlak 的粗糙集理论对 单值知识系统的决策逻辑语言进行了详细的讨论。简单的说，决策逻辑语言是一种特殊的经典谓词逻辑，其语义 采用 Tarski 意义下的模型和可满足性，即知识系统S (U, A) 表示模型，对符号以及公式进行解释，若S 是可 理解的，一个对象x 在模型S 的解释下满足公式θ则记为x θ 。 s 这里我们定义和讨论的决策逻辑语言由原子公式组成。公式是一种属性-数据对，用命题联词（与、或、非 等）通过标准的方法构成复合公式。 首先我们定义决策逻辑语言的字母表如下： （1）A ——属性常数集合； （2）V UV ，a ∈A ；V ——属性值常数集合； a （3）命题联词的集合：{~，∨，∧，→，≡}，分别表示：否定、分解、合并、蕴含和等价。 定义 1 决策逻辑语言的公式是满足下列条件的极小集： （1）公式(a,v) （或简写成a ）称为初等原子公式。其中，a ∈A ，v ∈V ； v a （2）若θ和Ψ是决策逻辑语言的公式，则~θ，θ ∧Ψ，θ∨Ψ，θ→Ψ和θ≡Ψ也是决策逻辑语言的 公式； （3）有限步利用1）和2）规则得到的也是决策逻辑语言的公式。 公式是用来描述论域中对象的工具，公式也可以是用来描述论域中具有某些性质的对象的子集，例如在原 子公式中，(a,v) 解释为对属性a 有值v 的所有对象的描述。 定义 2 一个对象x ∈U 满足S (U, A) 中的公式θ，记作x s θ （简记作x θ ），当且仅当下面的条件被 满足： 1）x (a,v) 当且仅当f (a,x) v ； 2）x ~ θ当且仅当非x θ ； 3）x θ∨Ψ当且仅当x θ或x Ψ； 4）x θ∧Ψ当且仅当x θ且x Ψ； 5）x θ →Ψ当且仅当x ~ θ∨Ψ； 6）x θ ≡Ψ当且仅当x θ →Ψ且x Ψ→θ 。 定义3 设θ为一公式，定义θ 为：θ ＝{x | x ∈U,x s θ}， s s 称为S 中公式θ的含义，其自变量为逻辑语言的公式，因变量为S 中对象集合的子集。 在决策逻辑语言中，公式θ在知识系统S 中为真，当且仅当θ U ；公式θ和Ψ在S 中等价，当且仅当 s θ Ψ 。 s s 下面这个命题解释了公式的含义。 命题１ １）(a,v) {x | x ∈U, a(x) v} s ２）~ θ −θ s ３）θ∨Ψ θ U Ψ s s ４）θ∧Ψ θ I Ψ s s ５）θ →Ψ −θ U Ψ s s