离散数学 前束范式ppt课件
- 格式：ppt
- 大小：460.00 KB
- 文档页数：16
下载文档原格式
合集下载
离散数学26 前束范式
7
二、前束合取范式
第二步，约束变量换名： D (x)[P(x)(z)Q(z,y)(w)R(x,w)] 第三步，消去条件联结词： D (x)[(P(x)(z)Q(z,y)) (w)R(x,w)] 第四步，将深入： D (x)[(P(x) (z)Q(z,y))(w)R(x,w)] (x)[(P(x)(z)Q(z,y))(w)R(x,w)] 第五步，将量词提前： D (x)(z)(w)[(P(x)Q(z,y)) R(x,w)] (x)(z)(w) [(P(x)R(x,w))(Q(z,y) R(x,w) ) ]
3
一、前束范式
例：化下列公式为前束范式
1）x F(x) x G(x) 2）x F(x) x G(x) 解：（1）x F(x) x G(x) x F(x) x G(x) x F(x) x G(x) x (F(x) G(x)) （2）x F(x) x G(x) x F(x) x G(x) x F(x) x G(x) x F(x) y G(y) x (F(x) y G(y)) x y (F(x) G(y))
定理2-6.3：任何一个谓词公式都可以转化为与其
等价的前束析取范式。 任一个wff A转化成前束析取范式步骤与例4类同
9
本课小结
1.前束范式 2.前束析取范式 3.前束合取范式
10
作业
P75 （2）
11
8
三、前束析取范式
定义2-6.3：如果一个谓词公式wff A具有如下形式，
则称其为一个前束析取范式。 (□v1)(□v2)…(□vn)[(A11 A12 … A1l1) (A21 A22 … A2l2) … (Am1 Am2 … Amlm)]
二、前束合取范式
第二步，约束变量换名： D (x)[P(x)(z)Q(z,y)(w)R(x,w)] 第三步，消去条件联结词： D (x)[(P(x)(z)Q(z,y)) (w)R(x,w)] 第四步，将深入： D (x)[(P(x) (z)Q(z,y))(w)R(x,w)] (x)[(P(x)(z)Q(z,y))(w)R(x,w)] 第五步，将量词提前： D (x)(z)(w)[(P(x)Q(z,y)) R(x,w)] (x)(z)(w) [(P(x)R(x,w))(Q(z,y) R(x,w) ) ]
3
一、前束范式
例：化下列公式为前束范式
1）x F(x) x G(x) 2）x F(x) x G(x) 解：（1）x F(x) x G(x) x F(x) x G(x) x F(x) x G(x) x (F(x) G(x)) （2）x F(x) x G(x) x F(x) x G(x) x F(x) x G(x) x F(x) y G(y) x (F(x) y G(y)) x y (F(x) G(y))
定理2-6.3：任何一个谓词公式都可以转化为与其
等价的前束析取范式。 任一个wff A转化成前束析取范式步骤与例4类同
9
本课小结
1.前束范式 2.前束析取范式 3.前束合取范式
10
作业
P75 （2）
11
8
三、前束析取范式
定义2-6.3：如果一个谓词公式wff A具有如下形式，
则称其为一个前束析取范式。 (□v1)(□v2)…(□vn)[(A11 A12 … A1l1) (A21 A22 … A2l2) … (Am1 Am2 … Amlm)]
离散数学-2-6_前束范式
9
三、前束析取范式
定义2-6.3：如果一个谓词公式wff A具有如下形式，
则称其为一个前束析取范式。 (□v1)(□v2)…(□vn)[(A11 A12 … A1l1) (A21 A22 … A2l2) … (Am1 Am2 … Amlm)]
其中□ 可为或，vi(i=1,2,……n)是客体变元，Aij 是 原子公式或其否定。
6
二、前束合取范式
定义2-6.2：如果一个谓词公式wff A具有 如下形式，则称其为一个前束合取范式。 (□v1)(□v2)…(□vn)[(A11 A12 … A1l1) (A21 A22 … A2l2) … (Am1 Am2 … Amlm)] 其中□ 可为或，vi(i=1,2,……n)是客体 变元，Aij 是原子公式或其否定。
第二章谓词逻辑
2-6 前束范式 授课人：李朔 Email:chn.nj.ls@
1
一、前束范式
与命题逻辑类似，在谓词逻辑中也希望研 究其合式公式，即谓词公式的规范形式， 这就是前束范式。 定义2-6.1 设A为一个谓词公式，若A有形 式：Q1x1Q2x2QkxkB，则称A为前束范式， 其中Qi(1≤i≤k)为或，B为不含量词的谓 词公式。
3
一、前束范式
例：化下列公式为前束范式
1）x F(x) xG(x) 2) xF(x) xG(x) 解：(1) x F(x) xG(x) x F(x) xG(x) x (F(x) G(x)) (2) x F(x) xG(x) x F(x) x G(x) x F(x) y G(y) x (F(x) y G(y)) x y (F(x) G(y))
三、前束析取范式
定义2-6.3：如果一个谓词公式wff A具有如下形式，
则称其为一个前束析取范式。 (□v1)(□v2)…(□vn)[(A11 A12 … A1l1) (A21 A22 … A2l2) … (Am1 Am2 … Amlm)]
其中□ 可为或，vi(i=1,2,……n)是客体变元，Aij 是 原子公式或其否定。
6
二、前束合取范式
定义2-6.2：如果一个谓词公式wff A具有 如下形式，则称其为一个前束合取范式。 (□v1)(□v2)…(□vn)[(A11 A12 … A1l1) (A21 A22 … A2l2) … (Am1 Am2 … Amlm)] 其中□ 可为或，vi(i=1,2,……n)是客体 变元，Aij 是原子公式或其否定。
第二章谓词逻辑
2-6 前束范式 授课人：李朔 Email:chn.nj.ls@
1
一、前束范式
与命题逻辑类似，在谓词逻辑中也希望研 究其合式公式，即谓词公式的规范形式， 这就是前束范式。 定义2-6.1 设A为一个谓词公式，若A有形 式：Q1x1Q2x2QkxkB，则称A为前束范式， 其中Qi(1≤i≤k)为或，B为不含量词的谓 词公式。
3
一、前束范式
例：化下列公式为前束范式
1）x F(x) xG(x) 2) xF(x) xG(x) 解：(1) x F(x) xG(x) x F(x) xG(x) x (F(x) G(x)) (2) x F(x) xG(x) x F(x) x G(x) x F(x) y G(y) x (F(x) y G(y)) x y (F(x) G(y))
02离散数学课件资料
量
词 表示数量的词，分全称量词与存在量词。
：一切、所有的、任意的；
：存在着、有一个、至少有一个；
x：个体域中所有个体；
x：个体域中存在某个个体； xF(x)：个体域中所有个体具有性质F； xF(x)：个体域中存在着某个个体具有性质F。
将命题 “所有的人都是要死的”符号化
(个体域为人类集合）
为了在命题演算中，反映命题的内在联系， 常常要将简单命题分解成 个体词、谓词、量词 等，并对它们的形式结构及逻辑关系加以研究，总 结出正确的推理形式和规则，这就是本章一阶逻辑
要研究的内容。
第二章
一阶逻辑
§2.1 一阶逻辑基本概念 §2.2 一阶逻辑合式公式及解释 §2.3 一阶逻辑等值式及前束范式
5.多个量词同时出现时，不能随意颠倒顺序;
例:
对于任意的x, 存在y,使得x+y=5,
取个体域为实数集合,该如何符号化? x y H(x，y) , 其中H(x，y) : x+y=5
量词颠倒顺序成立吗?
例2.在谓词逻辑中将下列命题符号化 (1) 对所有的x，均有x2–1=(x+1)(x–1) (个体域为自然数集) (2) 存在x,使得x+5=2 (个体域为自然数集) (3) 凡偶数均能被2整除 (4) 存在着偶素数 (5) 没有不犯错误的人 (6) 在北京工作的人未必都是北京人
(8) 每个自然数都有后继数
解：F(x)：x自然数 H(x，y)：y是x的后继数
符号化：x(F(x) y (F(y) H(x，y)) 或： x(F(x) y (F(y) H(x，y)))
(9) 有的自然数无先驱数
解：F(x)：x是自然数 ，H(x，y)：y是x的先驱数 符号化：x(F(x) y(F(y) H(x，y))) 或：x(F(x)y(F(y) H(x，y)) (10) 有的有理数是整数 (个体域为实数集) 解： F(x)：x是有理数，G(x)：x是整数 符号化：x(F(x) G(x)) (11) 每个人都有一些缺点。 解：F(x,y)：x都有y，M(x)：x是人，G(y)：y是缺点 符号化： (x) (M(x)(y) (G(y)F(x,y)))
《离散数学讲义》课件
离散概率分布的定义
离散概率分布是描述随机事件在有限或可数无限的可 能结果集合中发生的概率的数学工具。
离散概率分布的种类
常见的离散概率分布包括二项分布、泊松分布、几何 分布等。
离散概率分布的应用
离散概率分布在统计学、计算机科学、物理学等领域 都有广泛的应用。
参数估计和假设检验
参数估计
参数估计是根据样本数据推断总体参数的过 程，包括点估计和区间估计两种方法。
假设检验
假设检验是用来判断一个假设是否成立的统计方法 ，包括参数检验和非参数检验两种类型。
参数估计和假设检验的应 用
在统计学中，参数估计和假设检验是常用的 数据分析方法，用于推断总体特征和比较不 同总体的差异。
方差分析和回归分析
方差分析
方差分析是一种用来比较不同组数据的平均值是否存在显著差异 的统计方法。
《离散数学讲义》ppt课件
目 录
• 离散数学简介 • 集合论 • 图论 • 离散概率论 • 逻辑学 • 离散统计学 • 应用案例分析
01
离散数学简介
离散数学的起源和定义
起源
离散数学起源于17世纪欧洲的数学研 究，最初是为了解决当时的一些实际 问题，如组合计数和图论问题。
定义
离散数学是研究离散对象（如集合、 图、树、逻辑等）的数学分支，它不 涉及连续的变量或函数。
联结词：如与(&&)、或(||)、非(!)等，用 于组合简单命题。
03
04
命题公式：由简单命题通过联结词组合而 成的复合命题。
命题逻辑的推理规则
05
06
肯定前件、否定后件、析取三段论、合取 三段论等推理规则。
谓词逻辑
个体词
表示具体事物的符号。
离散概率分布是描述随机事件在有限或可数无限的可 能结果集合中发生的概率的数学工具。
离散概率分布的种类
常见的离散概率分布包括二项分布、泊松分布、几何 分布等。
离散概率分布的应用
离散概率分布在统计学、计算机科学、物理学等领域 都有广泛的应用。
参数估计和假设检验
参数估计
参数估计是根据样本数据推断总体参数的过 程，包括点估计和区间估计两种方法。
假设检验
假设检验是用来判断一个假设是否成立的统计方法 ，包括参数检验和非参数检验两种类型。
参数估计和假设检验的应 用
在统计学中，参数估计和假设检验是常用的 数据分析方法，用于推断总体特征和比较不 同总体的差异。
方差分析和回归分析
方差分析
方差分析是一种用来比较不同组数据的平均值是否存在显著差异 的统计方法。
《离散数学讲义》ppt课件
目 录
• 离散数学简介 • 集合论 • 图论 • 离散概率论 • 逻辑学 • 离散统计学 • 应用案例分析
01
离散数学简介
离散数学的起源和定义
起源
离散数学起源于17世纪欧洲的数学研 究，最初是为了解决当时的一些实际 问题，如组合计数和图论问题。
定义
离散数学是研究离散对象（如集合、 图、树、逻辑等）的数学分支，它不 涉及连续的变量或函数。
联结词：如与(&&)、或(||)、非(!)等，用 于组合简单命题。
03
04
命题公式：由简单命题通过联结词组合而 成的复合命题。
命题逻辑的推理规则
05
06
肯定前件、否定后件、析取三段论、合取 三段论等推理规则。
谓词逻辑
个体词
表示具体事物的符号。
离散数学课件2-67 前束范式推理理论
3. 4.
利用量词作用域的扩张和收缩等价式， 利用量词作用域的扩张和收缩等价式，把量 词提到前面。 词提到前面。
前束合取范式
定义2-6.2 前束合取范式： 前束合取范式： 定义 一个wff A如果具有如下形式，则称为前束 如果具有如下形式， 一个 如果具有如下形式 合取范式： 合取范式： (Q1x1)(Q2x2)…(Qnxn)[(A11∨A12∨…∨ 1k1)∧ ∨…∨A ∧ (A21∨A22∨…∨ 2k2)∧…∧(Am1∨Am2∨…∨ mkm)] ∨…∨A ∧ ∨…∨A 其中Q 为客体变元， 其中 i (1≤i≤n）为∃或∀，xi为客体变元， ） Aij是原子变元或其否定。 是原子变元或其否定。
前束合取范式
定理2 每一个wff 定理2-6.2 ：每一个wff A都可转化为与其等价 的前束合取范式。 的前束合取范式。 转化方法： 转化方法： 取消多余量词。 1. 取消多余量词。 2. 换名 消去条件联结词。 3. 消去条件联结词。 利用量词转化公式， 否定深入到命题变元和 4. 利用量词转化公式 ， 把 否定深入 到命题变元和 谓词填式的前面。 谓词填式的前面。 5. 利用量词作用域的扩张和收缩等价式， 把量词 利用量词作用域的扩张和收缩等价式 ， 提到前面。 提到前面。
(2)全称推广规则（universal generalization）
全称量词引入规则，简称 规则。 全称量词引入规则，简称UG规则。 规则 P(x)⇒ (∀x)P(x) ⇒ ∀ 如果能够证明对论域中每一个客体c， 如果能够证明对论域中每一个客体 ， 命 都成立， 题 P(c)都成立 ， 则全称推广规则可得到结论 都成立 (∀x)P(x)成立。在应用本规则时，必须能够证 成立。 ∀ 成立 在应用本规则时， 明前提P(x)对论域中每一可能的 是真。 对论域中每一可能的x是真 明前提 对论域中每一可能的 是真。
精品课程《离散数学》PPT课件(全)
言1
为什么学习离散数学？
离散数学是现代数学的一个重要分支，是计算机科学与技术 的理论基础，所以又称为计算机数学，是计算机科学与技术 专业的核心、骨干课程。
它以研究离散量的结构和相互间的关系为主要目标，其研 究对象一般是有限个或可数个元素，因此它充分描述了计算 机科学离散性的特点。
离散数学是什么课？
真值为1
25
1.1 命题符号化及联结词
以下命题中出现的a是给定的一个正整数： (3) 只有 a能被2整除， a才能被4整除。
(4) 只有 a能被4整除， a才能被2整除。
解： 令r： a能被4整除， s： a能被2整除。 真值不确定 (3)符号化为 s r (4)符号化为 r s
真值为1
26
19
1.1 命题符号化及联结词
3.析取词 设p,q为二命题，复合命题“p或q” 称为p与q的析取式，记作p ∨ q，符号∨称 为析取联结词。 运算规则：
p 0 0 1 1 q 0 1 0 1 p∨q 0 1 1 1
20
1.1 命题符号化及联结词
析取运算特点：只有参与运算的二命题全为假时，运算结果才 为假，否则为真。 相容或：二者至少有一个发生，也可二者都发生 排斥或：二者只有一个发生，即非此即彼 例如： （1）小王爱打球或爱跑步。 设p：小王爱打球。 q：小王爱跑步。 则上述命题可符号化为：p ∨ q （2）张晓静是江西人或湖南人。 设p：江西人。 q：湖南人。 则上述命题就不可简单符号化为：p ∨ q 而应描述为(p∧ q) ∨( p∧q)(也可用异或联接词∨)
（1）星期天天气好，带儿子去了动物园； （2）星期天天气好，却没带儿子去动物园； （3）星期天天气不好，却带儿子去了动物园； （4）星期天天气不好，没带儿子去动物园。
数学离散数学PPT课件
(b) 对公式 A: F(x, y)∧M→F(u, x)中的 F, 欲代以 B: G(x1)∨H(x2, s)→H(t, x2), 则只需x , y , u不是B内的约 束变元, 而且s , t不是A内的约束变元。 代入结果为 (G(x)∨H(y, s)→H(t, y))∧M→(G(u)∨H(x, s)→H(t, x))
第22页/共41页
表 1.7 -1 含有量词的永真公式概要表
第23页/共41页
谓词演算规则
1、代入规则 2、替换规则 3、对偶原理
第24页/共41页
1. 代入规则
(i)自由个体变元的代入：在一公式中, 任一自由个体变元 可代以另一个体变元, 只需该个体变元出现的各处都同样代入, 且代入的变元不允许在原来公式中以约束变元出现。 例: 在公式xP(x, y)∨Q(w, y)中, 将y代以z, 则得xP(x, z)∨Q(w, z)， 将y代以w, 则得xP(x, w)∨Q(w, w)。 所得公式称为原公式的代入实例。
1.后边的r个自由变元 不允许在原公式中以约束变元出现; 2. F(x1,x2, …, xn)中的变元也不允许在代入的公式中以约束变元 出现。
第26页/共41页
例: (a) 对公式(P→Q) (P∨Q)中的P代以xP(x), Q代以S(x), 得
(xP(x)→S(x)) (xP(x)∨S(x))
Q4
xP(x) xQ(x)
E14
第31页/共41页
(b) 证明
x(P(x) Q(x)) x(R(x) Q(x)) (R(x) P(x))
证： 根据CP规则, 上式等价于
x(P(x) Q(x)) x(R(x) Q(x)) (R(x) P(x))
而 x(P(x) Q(x)) x(R(x) Q(x))
第22页/共41页
表 1.7 -1 含有量词的永真公式概要表
第23页/共41页
谓词演算规则
1、代入规则 2、替换规则 3、对偶原理
第24页/共41页
1. 代入规则
(i)自由个体变元的代入：在一公式中, 任一自由个体变元 可代以另一个体变元, 只需该个体变元出现的各处都同样代入, 且代入的变元不允许在原来公式中以约束变元出现。 例: 在公式xP(x, y)∨Q(w, y)中, 将y代以z, 则得xP(x, z)∨Q(w, z)， 将y代以w, 则得xP(x, w)∨Q(w, w)。 所得公式称为原公式的代入实例。
1.后边的r个自由变元 不允许在原公式中以约束变元出现; 2. F(x1,x2, …, xn)中的变元也不允许在代入的公式中以约束变元 出现。
第26页/共41页
例: (a) 对公式(P→Q) (P∨Q)中的P代以xP(x), Q代以S(x), 得
(xP(x)→S(x)) (xP(x)∨S(x))
Q4
xP(x) xQ(x)
E14
第31页/共41页
(b) 证明
x(P(x) Q(x)) x(R(x) Q(x)) (R(x) P(x))
证： 根据CP规则, 上式等价于
x(P(x) Q(x)) x(R(x) Q(x)) (R(x) P(x))
而 x(P(x) Q(x)) x(R(x) Q(x))
离散数学讲义ppt课件
课程概况
教材：
《离散数学（第三版）》，耿素云等编著 清华大学出版社，2004年3月
参考书：
（1） 《离散数学(第二版)》及其配套参考书《离散 数学题解》作者：屈婉玲，耿素云，张立昂 清华大学出版社
（2） 《离散数学》焦占亚主编 电子工业出版社 2005年1月
2
课程概况
选修课/必修课：选修 周学时：3（学时） 上课周：1－16周 总学时：48（学时）
3
课程内容及学时安排
第一篇 数理逻辑（14学时）
第一章 命题逻辑（8） 第二章 谓词逻辑（6）
第二篇 集合论（12学时）
第三章 集合（4） 第四章 二元关系与函数（8）
第四篇 图论（14学时）
第七章 图论（8） 第八章 一些特殊图（4） 第九章 树 （2）
4
课程考核
第四篇 代数系统（8学时）
第5、6章 图论（8）
所以，伊勒克持拉既知道并且又不知道这个人是她的 哥哥。
20
NO.3 M：著名的理发师悖论是伯特纳德·罗素提出的。一个理发 师的招牌上写着： 告示：城里所有不自己刮脸的男人都由我给他们刮脸，我 也只给这些人刮脸。 M：谁给这位理发师刮脸呢？ M：如果他自己刮脸，那他就属于自己刮脸的那类人。但 是，他的招牌说明他不给这类人刮脸，因此他不能自己来 刮。 M：如果另外一个人来给他刮脸，那他就是不自己刮脸的 人。但是，他的招牌说他要给所有这类人刮脸。因此其他 任何人也不能给他刮脸。看来，没有任何人能给这位理发 师刮脸了！
P
Q
PQ
P
0
0
0
1
0
1
0
1
1
0
0
0
1
1
1
离散数学课件（北航）第四章第二节范式[兼容模式]
第四章归结法原理§4.1命题逻辑的归结法§4.2前束范式与斯科伦范式§4.3谓词逻辑的归结法作业§4.2 前束范式与斯科伦范式在命题逻辑中，为了用归结法判断一个公式是否是另一些公式的逻辑推论，首先需要将公式化为标准形式—合取范式。
在谓词逻辑中，为了用归结法判断一个语句是否是另一些语句的逻辑推论，首先需要将语句化为标准形式—斯科伦范式。
定义4.5形式为Q1y1 … Q n y n B 的公式称为前束范式，其中n 为非负整数，每个Qi是∀或∃，B 是开公式，y1, …, y n 是不同变元。
称Q1y1…Q n y n 为该前束范式的前束词，称B 为它的母式。
开公式是前束范式，这时n= 0，前束词是空串。
当一个前束范式不是开公式时它的所有量词都出当一个前束范式不是开公式时，它的所有量词都出现在最前面，并且它们的辖域都一直管到底。
前束范式：∀x∃y∃z(P(x, y) →Q(u, v))，P(x, y)非前束范式：∀xP(x) ∧Q(y)，因为∀x 的辖域是P(x)，而不是P(x) ∧Q(y)。
可以通过等值演算将一个公式化为前束范式。
例通过等值演算将公式Q(x) ∧(∃xP(x)→∀xR(x))化为前束范式。
Q(x) ∧(∃xP(x)→∀xR(x))⇔Q(x) ∧∀x(P(x)→∀xR(x))因为x 是公式P(x) 中的自由变元，所以P(x)→∀xR(x) ⇔∀x(P(x)→R(x))不成立。
需要将约束变元换名。
Q(x) ∧∀x(P(x)→∀xR(x))⇔Q(x) ∧∀x(P(x)→∀yR(y))⇔Q(x) ∧∀x∀y(P(x)→R(y))因为x 是公式Q(x) 中的自由变元，所以Q(x) ∧∀x∀y(P(x)→R(y))⇔)∀x(Q(x) ∧∀y(P(x)→R(y)))不成立。
需要将约束变元换名。
Q(x) ∧∀x∀y(P(x)→R(y))⇔Q(x) ∧∀z∀y(P(z)→R(y))⇔∀z(Q(x) ∧∀y(P(z)→R(y)))⇔∀z∀y(Q(x) ∧(P(z)→R(y)))与公式A 等值的前束范式称为A 的前束范式。
离散数学PPT【共34张PPT】
15
18.4 点着色
定义17.9 (1) 图G的一种点着色——给图G的每个顶点涂上一种颜色，
使相邻顶点具有不同颜色 (2) 对G进行k着色（G是k-可着色的）——能用k种颜色给G
的顶点着色 (3) G的色数(G)=k——G是k-可着色的，但不是(k1)-可着色
的.
16
关于顶点着色的几个简单结果
定理17.19 (G)=1当且仅当G为零图 定理17.20 (Kn)=n 定理17.21 若G为奇圈或奇阶轮图，则(G)=3，若G为偶阶轮 图，则(G)=4. 定理17.22 若G的边集非空，则(G)=2当且仅当G为二部图.
路径 (7) M的交错圈——由M与EM中的边交替出现构成的G中圈
上图中，只有第一个图存在完美匹配
8
可增广路径及交错圈
(1)
(2)
(3)
设红色边在匹配M中，绿色边不在M中，则图(1)中的两条路 径均为可增广的交错路径；(2)中的全不是可增广的交错路 径；(3)中是一个交错圈. 不难看出，可增广交错路径中，不在M中的边比在M中的边 多一条. 交错圈一定为偶圈.
立集 (3) 最大点独立集——元素最多的点独立集 (4) 点独立数——最大点独立集中的元素个数，记为0
(1)
(2)
在图中，点独立数依次为2, 2, 3.
(3)
2
极大独立集与极小支配集
定理18.1 设G=<V,E>中无孤立点，则G的极大点独立集都是 极小支配集. 证明线索： (1) 设V*为G的极大点独立集，证明它也是支配集.
定理17.28 偶圈边色数为2，奇圈边色数为3. 定理17.29 (Wn) = n1, n4. 定理17.30 二部图的边色数等于最大度. 定理17.31 n为奇数（n1）时，(Kn)=n；
18.4 点着色
定义17.9 (1) 图G的一种点着色——给图G的每个顶点涂上一种颜色，
使相邻顶点具有不同颜色 (2) 对G进行k着色（G是k-可着色的）——能用k种颜色给G
的顶点着色 (3) G的色数(G)=k——G是k-可着色的，但不是(k1)-可着色
的.
16
关于顶点着色的几个简单结果
定理17.19 (G)=1当且仅当G为零图 定理17.20 (Kn)=n 定理17.21 若G为奇圈或奇阶轮图，则(G)=3，若G为偶阶轮 图，则(G)=4. 定理17.22 若G的边集非空，则(G)=2当且仅当G为二部图.
路径 (7) M的交错圈——由M与EM中的边交替出现构成的G中圈
上图中，只有第一个图存在完美匹配
8
可增广路径及交错圈
(1)
(2)
(3)
设红色边在匹配M中，绿色边不在M中，则图(1)中的两条路 径均为可增广的交错路径；(2)中的全不是可增广的交错路 径；(3)中是一个交错圈. 不难看出，可增广交错路径中，不在M中的边比在M中的边 多一条. 交错圈一定为偶圈.
立集 (3) 最大点独立集——元素最多的点独立集 (4) 点独立数——最大点独立集中的元素个数，记为0
(1)
(2)
在图中，点独立数依次为2, 2, 3.
(3)
2
极大独立集与极小支配集
定理18.1 设G=<V,E>中无孤立点，则G的极大点独立集都是 极小支配集. 证明线索： (1) 设V*为G的极大点独立集，证明它也是支配集.
定理17.28 偶圈边色数为2，奇圈边色数为3. 定理17.29 (Wn) = n1, n4. 定理17.30 二部图的边色数等于最大度. 定理17.31 n为奇数（n1）时，(Kn)=n；
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
前束范式的优点是全部量词集中在公式前面，其缺点是各量词 的排列无一定规则，这样当把一个公式化归为前束范式时， 其表达形式会显现多种情形，不便应用。1920年斯柯林 (Skolem)提出对前束范式首标中量词出现的次序给出规定： 每个存在量词均在全称量词之前。按此规定得到的范式形式， 称为斯柯林范式。显然，任一公式均可化为斯柯林范式。它 的优点是：全公式按顺序可分为三部分，公式的所有存在量 词、所有全称量词和辖域。这给Lp的研究提供了一定的方 便。
第五步将量词推到左边
D (x)(z)(w)[(P(x) Q(z, y)) R(x, w)]
(x)(z)(w)[(┐P(x)∨┐R(x,w))∧(┐Q(z,y)∨┐R(x,w))1]3
三、前束析取范式
定义2-6.3 一个wffA称为前束析取范式，如果它有如下形
8
举例 73页 例题1，例题2，例题3
9
例题2 化公式 (x)(y)((z)(P(x,z)∧P(y,z))(u)Q(x,y,u))为前束范式 解 原公式 (x)(y)(┐(z)(P(x,z)∧P(y,z))∨(u)Q(x,y,u)) (x)(y)((z)(┐P(x,z)∨┐P(y,z))∨(u)Q(x,y,u)) (x)(y)(z)(u)(┐P(x,z)∨┐P(y,z)∨Q(x,y,u))
第二步改名，以便把量词提到前面。
(x){(y)A(x, y) (u)(v)[B(u,v) (z)(A(z,u) B(u, z))]}
(x)(y)(u)(v)(z){A(x, y) [B(u,v) (A(z,u) B(u, z))]}
将约束变元x改名为u， 将约束变元y改名为z，
练习 75页（1）题
3
（3）量词与命题联结词之间的一些等价式 量词分配律
(x)(A(x) B(x)) (x)A(x) (x)B(x) (x)(A(x) B(x)) (x)A(x) (x)B(x) (x)(A(x) B(x)) (x)A(x) (x)B(x)
4
（4）指导变元、作用域、约束变元、自由变元
10
例题3 把公式
(x){(y)A(x, y) (x)(y)[B(x, y) (y)(A( y, x) B(x, y))]}
化为前束范式 解 第一步否定深入
原式 (x){(y)A(x, y) (x)(y)[B(x, y) (y)(A( y, x) B(x, y))]} (x){(y)A(x, y) (x)(y)[B(x, y) (y)(A(y, x) B(x, y))]}
自
由
约 束
变 元
量 词
变 元
(x)P(x, y)
指
辖
导
域
变
元
5
（5）约束变元换名和自由变元代入 在一公式中，有的个体变元既是约束出现，
又是自由出现，这就容易产生混淆。为了避免混 淆，可对约束变元换名或自由变元代入。
约束变元换名 将量词辖域中某个约束出现的个体变元及相 应指导变元，改成本辖域中未曾出现过的个体变 元，其余不变。 自由变元代入 对某自由出现的个体变元可用个体常元或用 与原子公式中所有个体变元不同的个体变元去代 入，且处处代入。
离散数学
Discrete Mathematics
1
第5讲 §2—6 前束范式
要求：理解前束范式、前束合取范式和前束 析取范式的定义，会将一个谓词公式wffA化 为前束范式、前束合取范式和前束析取范式。 学习本节的目的是掌握谓词公式的标准化形 式。 重点：化谓词公式为前束范式。
2
复习：
（1）量词与联结词¬之Байду номын сангаас的关系
(x)(z)(y){[P (x a) (z b)][Q(y) (a b)]}
是前束合取范式
12
定理2-6.2 每一个wffA都可转化为与其等价的前束合取范式。
例题4 将wffD：(x)[(y)P(x) (z)Q(z, y) (y)R(x, y)]
转化为与其等价的前束合取范式。
解 第一步取消多余量词
6
一、前束范式
定义2-6.1 一个合式公式称为前束范式，如果它有如下形式：
(Q1x1)(Q2x2)…(Qkxk)A 其中Qi(1≤i≤k)为或，A为不含有量词的谓词公式。称
Q1x1Q2x2…Qkxk为公式的首标。 特别地，若Ａ中无量词，则Ａ也看作是前束范式。
可见，前束范式的特点是，所有量词均非否定地出现在
11
二、前束合取范式
定义2-6.2 一个wffA称为前束合取范式，如果它有如下形式：
(Q1x1)(Q2x2)…(Qkxk)[(A11∨A12∨…∨A1l1)∧(A21∨A22∨…∨A2l2) ∧ …∧(Am1∨Am2∨…∨Amlm)] 其中Qi(1≤i≤k)为量词或，xi(i=1,2, …,n)是客体变元， Aij是原子公式或其否定。 例如公式 (x)(u)(z)((P(x) P(u)) (P(x) Q(y, z)) (Q(x, y) P(u)) (Q(x, y) Q(y, z)))
公式最前面，且它的辖域一直延伸到公式之末。
例如，(x)(y)(z)(P(x,y)Q(y,z))，R(x,y)等 都是前束范式，而(x)P(x)(y)Q(y)， (x)(P(x)(y)Q(x,y))不是前束范式。
7
定理2.6.1 (前束范式存在定理) Lp中任意公式A都有与之等价 的前束范式。
斯柯林范式
D (x)[P(x) (z)Q(z, y) (y)R(x, y)]
第二步换名
D (x)[P(x) (z)Q(z, y) (w)R(x, w)]
第三步消去条件联结词
D (x)[(P(x) (z)Q(z, y)) (w)R(x, w)]
第四步将否定深入
D (x)[P(x) (z)Q(z, y)) (w)R(x, w)]
(x)P(x) (x)P(x) (x)P(x) (x)P(x)
（2）量词扩张/收缩律
(x)A(x) B (x)(A(x) B) (x)A(x) B (x)(A(x) B) B (x)A(x) (x)(B A(x)) B (x)A(x) (x)(B A(x))
这里A(x)是任意包括个体变元x的谓词公式，B 是不包括个体变元x的任意谓词公式。
第五步将量词推到左边
D (x)(z)(w)[(P(x) Q(z, y)) R(x, w)]
(x)(z)(w)[(┐P(x)∨┐R(x,w))∧(┐Q(z,y)∨┐R(x,w))1]3
三、前束析取范式
定义2-6.3 一个wffA称为前束析取范式，如果它有如下形
8
举例 73页 例题1，例题2，例题3
9
例题2 化公式 (x)(y)((z)(P(x,z)∧P(y,z))(u)Q(x,y,u))为前束范式 解 原公式 (x)(y)(┐(z)(P(x,z)∧P(y,z))∨(u)Q(x,y,u)) (x)(y)((z)(┐P(x,z)∨┐P(y,z))∨(u)Q(x,y,u)) (x)(y)(z)(u)(┐P(x,z)∨┐P(y,z)∨Q(x,y,u))
第二步改名，以便把量词提到前面。
(x){(y)A(x, y) (u)(v)[B(u,v) (z)(A(z,u) B(u, z))]}
(x)(y)(u)(v)(z){A(x, y) [B(u,v) (A(z,u) B(u, z))]}
将约束变元x改名为u， 将约束变元y改名为z，
练习 75页（1）题
3
（3）量词与命题联结词之间的一些等价式 量词分配律
(x)(A(x) B(x)) (x)A(x) (x)B(x) (x)(A(x) B(x)) (x)A(x) (x)B(x) (x)(A(x) B(x)) (x)A(x) (x)B(x)
4
（4）指导变元、作用域、约束变元、自由变元
10
例题3 把公式
(x){(y)A(x, y) (x)(y)[B(x, y) (y)(A( y, x) B(x, y))]}
化为前束范式 解 第一步否定深入
原式 (x){(y)A(x, y) (x)(y)[B(x, y) (y)(A( y, x) B(x, y))]} (x){(y)A(x, y) (x)(y)[B(x, y) (y)(A(y, x) B(x, y))]}
自
由
约 束
变 元
量 词
变 元
(x)P(x, y)
指
辖
导
域
变
元
5
（5）约束变元换名和自由变元代入 在一公式中，有的个体变元既是约束出现，
又是自由出现，这就容易产生混淆。为了避免混 淆，可对约束变元换名或自由变元代入。
约束变元换名 将量词辖域中某个约束出现的个体变元及相 应指导变元，改成本辖域中未曾出现过的个体变 元，其余不变。 自由变元代入 对某自由出现的个体变元可用个体常元或用 与原子公式中所有个体变元不同的个体变元去代 入，且处处代入。
离散数学
Discrete Mathematics
1
第5讲 §2—6 前束范式
要求：理解前束范式、前束合取范式和前束 析取范式的定义，会将一个谓词公式wffA化 为前束范式、前束合取范式和前束析取范式。 学习本节的目的是掌握谓词公式的标准化形 式。 重点：化谓词公式为前束范式。
2
复习：
（1）量词与联结词¬之Байду номын сангаас的关系
(x)(z)(y){[P (x a) (z b)][Q(y) (a b)]}
是前束合取范式
12
定理2-6.2 每一个wffA都可转化为与其等价的前束合取范式。
例题4 将wffD：(x)[(y)P(x) (z)Q(z, y) (y)R(x, y)]
转化为与其等价的前束合取范式。
解 第一步取消多余量词
6
一、前束范式
定义2-6.1 一个合式公式称为前束范式，如果它有如下形式：
(Q1x1)(Q2x2)…(Qkxk)A 其中Qi(1≤i≤k)为或，A为不含有量词的谓词公式。称
Q1x1Q2x2…Qkxk为公式的首标。 特别地，若Ａ中无量词，则Ａ也看作是前束范式。
可见，前束范式的特点是，所有量词均非否定地出现在
11
二、前束合取范式
定义2-6.2 一个wffA称为前束合取范式，如果它有如下形式：
(Q1x1)(Q2x2)…(Qkxk)[(A11∨A12∨…∨A1l1)∧(A21∨A22∨…∨A2l2) ∧ …∧(Am1∨Am2∨…∨Amlm)] 其中Qi(1≤i≤k)为量词或，xi(i=1,2, …,n)是客体变元， Aij是原子公式或其否定。 例如公式 (x)(u)(z)((P(x) P(u)) (P(x) Q(y, z)) (Q(x, y) P(u)) (Q(x, y) Q(y, z)))
公式最前面，且它的辖域一直延伸到公式之末。
例如，(x)(y)(z)(P(x,y)Q(y,z))，R(x,y)等 都是前束范式，而(x)P(x)(y)Q(y)， (x)(P(x)(y)Q(x,y))不是前束范式。
7
定理2.6.1 (前束范式存在定理) Lp中任意公式A都有与之等价 的前束范式。
斯柯林范式
D (x)[P(x) (z)Q(z, y) (y)R(x, y)]
第二步换名
D (x)[P(x) (z)Q(z, y) (w)R(x, w)]
第三步消去条件联结词
D (x)[(P(x) (z)Q(z, y)) (w)R(x, w)]
第四步将否定深入
D (x)[P(x) (z)Q(z, y)) (w)R(x, w)]
(x)P(x) (x)P(x) (x)P(x) (x)P(x)
（2）量词扩张/收缩律
(x)A(x) B (x)(A(x) B) (x)A(x) B (x)(A(x) B) B (x)A(x) (x)(B A(x)) B (x)A(x) (x)(B A(x))
这里A(x)是任意包括个体变元x的谓词公式，B 是不包括个体变元x的任意谓词公式。