当前位置：文档之家 › 离散数学---范式

离散数学---范式

  • 格式：ppt
  • 大小：534.50 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

离散数学26 前束范式

离散数学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)]

离散数学第三讲-范式与主范式

离散数学第三讲-范式与主范式

Mj mj
n 2 k
n 2 k
17
极小项与极大项之间的关系
3.
主析取范式与主合取范式的关系
例题： A (P Q ) R m1 m3 m5 m 6 m7 主合取范式 3 5 6 7 （ 1，，，，） 主析取范式
M0 M2 M4 （ 0 ，，） 2 4
(0,2,4) 其中表示合取.
16
极小项与极大项之间的关系
1.
极小项与极大项的关系

一个命题公式的主析取范式和主合取范式紧密相关, 在它们的简 记式中, 代表极小项和极大项的足标是互补的,
mi Mi,
2.

M i m i.
原命题A与其否命题A的关系
设命题公式A中含n个命题变元，且设A的主析取范式中含k个极 小项mil,mi2,…,mik则 A的主析取范式中必含2n-k个极小项,设为 mjl,mj2, …, ,
则称它为A 的合取范式。 合取式---称为积 析取式---称为和
3
1、范式---析取范式与合取范式
析取范式:
A A 1 A 2 A n ( n 1), n 1时，单个质合取式也是 A ：质合取式 i
析取范式
合取范式:
A B 1 B 2 B m ( m 1) m 1时，单个质析取式也是 B ：质析取式 i
(1)求出A的主析取范式中没包含的极小项mj1,mj2,··m j ·, (2)求出与(1)中极小项下标相同的极大项Mj1,Mj2,··M j ·, (3)由以上极大项构成的合取式为A的主合取范式.
n
n 2 k
.
.
2 k
18
2、主范式

离散数学---范式

离散数学---范式

西 华 大 学
例如：求A=p∧(q→r)→s的析(合)取范式 解:A p∧(q∨r)→s 化掉→ (p∧(q∨r)) ∨ s 化掉→ p∨ (q∨r)∨ s 否定深入 p∨ (q∧ r) ∨ s 否定深入 析取范式 p∨ s∨ (q∧ r) ( p∨ s∨ q)∧( p∨ s∨ r) 分配律 合 取范式 课堂作业： 求( p→q)→(q∨p)的析（合）取范式。
例如：求A=p∧(q→r)的主析、合取范式
法一：Ap∧(q∨r)
西 华 大 学
合取范式
……
(p∨q∨r) ∧(p∨q∨r)
∧
(p∨q∨r) ∧(p∨q∨r) ∧
(p∨q∨r) ∧(p∨q∨r)
1 1 0 1 0 M 0∧M1 ∧M2 ∧M3 ∧M6（主合取范式 (0,1,2,3,6) ） 0 0 1 0 0 1 1
~ ~ ~ ~ 1.简单合取式（基本积）: P ∧ P2 ∧… ∧ Pn ,（ Pi 为Pi 1 或Pi） ~ ~ ~ 2 ∨… ∨P n 1∨P 西简单析取式（基本和）： P
华 大 2. 析取范式：基本积的析取式 学
合取范式：基本和的合取式
3. 任何公式A都存在与之等价的 析(合)取范式 证(构造法)：1）将A中的→、化掉，使其只含 ∨ ∧； 2）将否定深入到变元前面； 3）使用分配律将公式化为析（合）取范式
q∨p
~ ~ ~ ~ 1. 极小项： P ∧P2 ∧… ∧Pn ,（Pi 为Pi或Pi）中， 1 1) n个变元全部出现； 2) n个变元的位置有序； 西 华 2) Pi、Pi不同时出现； 大 ~ ~ ~ 学 极大项： P ∨… ∨ Pn 1∨ P 2 极小项、极大项的足标与形式的对应
2. 主析取范式：极小项的析取式 主合取范式：极大项的合取式 3. 任何公式A都存在与之等价的主析(合)取范式 方法 1)：真值表法 2)：先求析(合)取范式，再求主析、合取范式

范式--离散数学

范式--离散数学

蕴含等值式 等价等值式 蕴含等值式 双重否定律
德.摩根定律
11
(P Q R ) Q ( P R ) 分配律
范式的表达式不唯一。
例3
PQ PQ （R R) P （Q R) (Q R)
P (Q R) P Q P R ( P Q P) ( P Q R) ( P P) (Q P) ( P R) (Q R)
8
（4）范式求解步骤
求公式A的范式的步骤：
(1) 消去A中的蕴涵词和等价词 。
ABAB， AB(AB)(AB) (2) 否定联结词的内移或消去 A A，(AB)AB，(AB)AB (3) 使用分配律进行化简、整合。 A(BC)(AB)(AC) 求合取范式 A(BC) (AB)(AC) 求析取范式
(3) 消去重复出现的极大项, 即用Mi代替MiMi；
(4) 将极大项按下标从小到大排列。
21
例5 求(pq)r 的主合取范式。
(pq)r (pr)(qr) pr p0r p(qq)r (pqr)(pqr) M1M3 qr (pp)qr (pqr)(pqr) M3M7 得 (pq)r M1M3M7 可记作 (1,3,7)
13

说明:
(1) n个命题变项产生2n个极小项和2n个极大项。 (2) 2n个极小项(极大项)均互不等值。 (3) 用mi表示第i个极小项，其中i是该极小项成真赋值的十 进制表示；用Mi表示第i个极大项，其中i是该极大项成假赋 值的十进制表示，mi(Mi)称为极小项(极大项)的名称。
14

2个变元的极大项与极小项
同一律 矛盾律 分配律 同一律, 矛盾律 分配律

离散数学14.主合取范式

离散数学14.主合取范式
课程资源
参考书目，网上教学视频，网络微课。
教学过程：
由于一个命题公式的析(合)取范式不是唯一,因而它们不能作为命题公式的规范形式(标准形式),为了使任意命题公式化为唯一的标准形式,下面引入主范式的概念.
1.定义：给定的命题公式，合取范式.
教学设计
课程名称
《离散数学》
教师姓名
授课题目
主合取范式
授课章节
§1.7对偶与范式
授课对象
数学与应用数学专业
教学目标
掌握利用真值表、等值演算求命题公式的主合取范式的方法
教学方式
启发式
教学内容
真值表法、等值演算法求命题公式的主合取范式
教学重点
主析取合取范式的求解
教学难点
等值演算法求主合取范式
教学方法和策略
例2求((PQ)R)P的主合取范式。
解:原式((P∨Q)∨R)∨P
(P∨Q)∧(R∨P ) (合取范式)
((P∨Q)∨(R∧R ))∧((R∨P )∨(Q∧Q))
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧
(P∨Q∨R)
(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)
M0∧M1∧M3
补充说明
2.主合取范式的求法
方法1：列真值表
⑴列出给定公式的真值表.
⑵找出真值表中每个“F”对应的大项.
如何根据一组指派写对应的为“F”的大项：如果变元P被指派为F，P在大项中以P形式出现；如变元P被指派为T，P在大项中以P形式出现(确保该大项为F).
⑶用“∧”联结上述大项，即可.
例1求PQ和PQ的主合取范式
采用多媒体课件辅助，分析主合取范式的概念及特点，分析利用命题公式的真值表求解主合取范式；注意师生互动，以学生为教学主体，共同完成教学目标。

离散数学 等值式 范式 消解算法

离散数学 等值式 范式 消解算法
ABAB AB(AB)(AB) (2) 否定联结词的内移或消去 A A (AB)AB (AB)AB
15
命题公式的范式
(3) 使用分配律 A(BC)(AB)(AC) A(BC) (AB)(AC)
求合取范式 求析取范式
公式范式的不足不惟一
16
求公式的范式
例5 求下列公式的析取范式与合取范式 (1) (pq)r (2) (pq)r
p q r 1 1 0 M6
p q r 1 1 1 M7
mi与Mi的关系： mi Mi, Mi mi
23
主析取范式与主合取范式
主析取范式——由极小项构成的析取范式 主合取范式——由极大项构成的合取范式 例如，n=3, 命题变项为 p, q, r 时，
(pqr)(pqr) m1m3 ——主析取范式 (pqr)(pqr) M1M7——主合取范式 公式A的主析取(合取)范式——与A 等值的主析取(合取)范式 定理2.5 (主范式的存在惟一定理) 任何命题公式都存在与之等值的主析取范式和主合取范式, 并且是惟一的
等值演算与置换规则
1. 等值演算——由已知的等值式推演出新的等值式的过程 2. 等值演算的基础：
(1) 等值关系的性质：自反性、对称性、传递性 (2) 基本的等值式 (3) 置换规则（见3） 3. 置换规则 设 (A) 是含公式 A 的命题公式，(B) 是用公式 B 置换 (A) 中所有的 A 后得到的命题公式 若 BA，则 (B)(A)
(pr)(qr) （对分配律） 合取范式
18 r (pq) r 消去 ((pq) r) (r (pq)) 消去 ( (pq) r) (r pq) 消去
((p q) r) ( p q r ) 否定内移
合取范式：

离散数学第三讲范式和主范式


Q∧R
P∧Q∧R ∨ P∧Q∧ R ∨ P∧ Q ∧ R ∨ m1 ∨ m3 ∨ m5 ∨ m6 ∨ m7
Σ(1 , 3 , 5 , 6 , 7)
12
2、主范式
主析取范式与真值表的关系 例如： 极小项 m5 --- P Q R 极小项的性质： 1).极小项之间彼此不等价； 足标 101 指 派 1 ，0，1
第三讲
范式与主范式
1.为什么引入范式？ 命题公式千变万化，不易于研究其性质和应用。 2.解决办法：将命题公式转化为逻辑等价的标准形。
范式----逻辑等价的标准形式
1
第三讲
讲授内容：
1. 范式
范式与主范式
析取范式 合取范式
2. 主范式
主析取范式 主合取范式 3. 主析取范式的个数
讲授重点：范式与主范式的求法 讲授难点：主范式的求法
则称它为A 的合取范式。 合取式---称为积 析取式---称为和
3
1、范式---析取范式与合取范式
析取范式:
A A1 A 2 A n (n 1), A：质合取式 i n1 时，单个质合取式也是 析取范式
合取范式:
A B1 B2 Bm (m 1) B：质析取式 i m1 时，单个质析取式也是 合取范式
极大项： 1. P1,P2 ,Pn的顺序确定；
2. Pi与Pi不同时存在，二者之一 必出现一次，且仅出现 一次
~ ~ ~ P1 P2 Pn M1 2 n M r (r 0,1,,2 n 1) ~ 1, Pi 为Pi i ~ 0 P i 为Pi
P P P, P P F
4) 排序：小项的序号从小到大。
11

离散数学23.前束范式

1.定义：如果一个谓词公式符合下面条件，它就是前束范式：所有量词都在公式的开头；所有量词的辖域都延伸到公式的末尾.
例如(y)(x)(z)(A(x)→(B(x,y)∨C(x,y,z))) ,
(x)(A(x)→B(x)),就是前束范式.
而(x)A(x)∧(y)B(y),
(x)(y)(A(x)→(B(x,y)∧(z)C(z))),
学情分析
学生已经学习了变元的约束，能够利用谓词演算的等价公式进行演算。
教学评价
师生互动，启发式教学引导学生思考并进而解决问题；深入分析，用例题加深学生对知识点的理解。
课程资源
参考书目，网上教学视频，网络微课。
教学过程：
与命题公式的范式类似，谓词公式也有规范形式。这里主要介绍前束范式--所有量词都在公式前边约束变元.
(x)(P(x)∨R(x))∨((y)P(y)∧Q(z)) (换变元)
(x)(P(x)∨R(x))∨(y)(P(y)∧Q(z)) (扩量词辖域)
(x)(y)((P(x)∨R(x))∨(P(y)∧Q(z))) (扩量词辖域)
定义2.6.2一个谓词公式A，如果具有形式：
(v1)(v2)…(vn)((A11A12…A1l1)(A21A22…A2l2)…(Am1Am2…Amlm))
将一个谓词公式化为前束合取范式或前束析取范式时，只需在前面求前束范式的（1）～（4）四个步骤基础上再增加一个步骤：
（5）利用分配律将公式化为前束合取范式或前束析取范式.
补充说明
4)用量词辖域扩张公式提取量词，使之成为前束范式形式.
例1. (x)A(x)→(x)B(x)
(x)A(x)∨(x)B(x)
(x)A(x)∨(x)B(x)
(x)A(x)∨(y)B(y) (换元)

离散数学-1-7 对偶与范式

(P →Q) ∧(Q →P)(┐P ∨Q) ∧(┐ Q ∨ P)
(2)利用双重否定律消去否定联结词“¬”或利用德摩根 律将否定联结词“¬”移到各命题变元前(¬内移)
⑶利用分配律、结合律将公式归约为合取范式或析取
范式。 P ∧(Q ∨R) ?
13
二、析取范式与合取范式
例：求命题公式(P∨Q)↔P的合取范式和析取范式。
10
二、析取范式与合取范式
定义（补充）仅有有限个命题变元或其否 定构成的合(析)取式称作简单合(析)取式。 如：
┐P,Q等为一个文字(一个命题变元或它的否定称为文字)构成的简 单合取式，┐P∧P，P∧┐Q等为2个文字构成的简单合取， P∧Q∧┐R,┐P∧P∧Q等为3个文字构成的简单合取式
P,┐Q等为一个文字（一个变元或变元的否定）的简单析趋式， P∨┐P，┐P∨Q等为2个变元（或变元的否定）简单析取式， ┐P∨┐Q∨R,P∨┐Q∨R等为3个文字构成的简单析取式。
所以，¬A(P,Q,R) A*(¬P,¬Q,¬R)
⑵验证 A(¬P,¬Q,¬R)¬A*(P,Q,R) A(¬P,¬Q,¬R)(¬P∨¬Q)∧¬R ¬((P∧Q)∨R)¬A*(P,Q,R)
6
一、对偶式与对偶原理
定理1-7.2 设P1，P2，…，Pn是出现在公式A和B中 的所有原子变元，如果AB，则A*B*。
11
二、析取范式与合取范式
定义1-7.2 一个命题公式称为合取范式，当且仅 当它具有形式：
A1∧A2∧……∧An (n 1)
其中A1，A2，……，An 都是简单析取式。 如: (P∨┐Q∨R)∧(┐P∨Q)∧┐Q 定义1-7.2 一个命题公式称为析取范式，当且仅 当它具有形式：
A1∨A2 ∨…… ∨An (n 1)

离散数学-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))
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3. 对偶原理
若AB，则A * B * 证：设因则故永P为真1.AA, A((P(P┐2P1,…P1, P,1,P,P2┐2,n…是,…P,出P2,P,n…现)n),于┐BAB(P和(PnP1)B,1中P, P2B的,2(…,┐所…,PP,有Pn1)n,原)永┐子真P变2.,…元,.┐Pn)
由定理1.7.1得 ┐A*(P1 , P2 ,…,Pn)┐B*(P1 , P2 ,…,Pn )
( p∨ s∨ q)∧( p∨ s∨ r) 分配律 合 取范式
课堂作业： 求( p→q)→(q∨p)的析（合）取范式。 q∨p
1. 极小项： P~1 ∧P~2 ∧… ∧P~n ,（P~i 为Pi或Pi）中， 1) n个变元全部出现；
西 2) n个变元的位置有序；
华 大 学
极大2)项P：i、P~1P∨i不P~同2∨时…出∨现；P~n
法一：Ap∧(q∨r) 合取范式
西
……
华
大 学
(p∨q∨r) ∧(p∨q∨r) ∧
(p∨q∨0r) ∧0 (p0∨q∨0 0r) 1∧
(p0∨1q∨0r) ∧(0 p∨1 q∨1 r)
0
10
1
10
M 0∧M1 ∧M2 ∧M3 ∧M6（主合取范式 (0,1,2,3,6)）
m4∨m5∨m7
（主析取范式 (4,5,7) ）
§1.5范式
从前面的讨论可知,存在大量互不相同的命题公式，实
西 华 大 学
际上互为等价,因此,有必要引入命题公式的标准形式, 使得相互等价的命题公式具有相同的标准形式。这无 疑对判别两个命题公式是否等价以及判定命题公式的 类型是一种好方法,同时对命题公式的简化和推证也是
十分有益的.
命题公式的标准形式： • （主）析取范式 • （主）合取范式
因此 A*B* . 显然：如果A是永真式，则A *是永假式。
1.简单合取式（基本积）: P~1 ∧ P~2 ∧… ∧ P~n ,（ P~i 为Pi
或Pi） 西简单析取式（基本和）：
P~1∨P~2
∨…
∨P~n
华
大学2. 析取范式：基本积的析取式
合取范式：基本和的合取式
3. 任何公式A都存在与之等价的 析(合)取范式 证(构造法)：1）将A中的→、化掉，使其只含 ∨ ∧；
对偶式和对偶原理
•
西
华•
大 学
•
•
对偶式：将只含∨∧（如有→ ，则应该 化去）联结词公式A中的联结词
∨------->∧, ∧------->∨,
0 ------->1,
•
1 -------> 0
•
得到的新公式A*称为A的对偶式。
• 例如：A = (p ∧ ( p∧q) ∨T)
A*=((p ∨( p∨q))∧F)
(合取范式)
11 1 1 1
成真赋值 111 m7
m m m 所以其主析取范式为： 4∨ 5∨ 7=∑(4,5,7)
相应的，其主合取范式为：M 0∧M1 ∧M2 ∧M3 ∧M6= ∏(0,1,2,3,6)
例2：求((PQ)R)P的主合取范式。
解: 原式┐(┐(P∨Q)∨R)∨P
西 (P∨Q)∧(┐R∨P ) (合取范式)
——等价演算法
1.在公式中消去→ 及 ；
西
华 大
2.利用∧对∨的分配律或∨对∧的分配律
学 得到析取或合取范式。
3.进一步由各个基本积推出所有极小项得 到主析取范式或由各个基本和推出所有 极大项得到主合取范式。
4.由主范式可直接利用上述两个性质2判定 该命题公式是否是可满足的。
例如：求A=p∧(q→r)的主析、合取范式
1
0
0
1
0
0
1
从真值表求主析(合)取范式：
已知公式A＝
p q r p∧ (q→r)
p∧(q→r)的真值表，
00 0 0 1
西 华
00 1 0 1
求A的主析取、主 合取范式
大 学
01 0 0 0
01 1 0 1
10 0 1 1
成真赋值 100 m4
10 1 1 1
成真赋值 101 m5
11 0 0 0
从主析(合)取范式求真值表：
A=p∧(q→r)
西 (p∨q∨r)
华 大 学
∧(p∨q∨r) ∧ (p∨q∨r)
000 001 010
∧(p∨q∨r) 011
∧(p∨q∨r) 110
pq 00 00 01 01
=M 0∧M1 ∧M2 ∧M3 ∧M6
10 10 11
11
r p∧ (q→r)
0
0
1
0
0
0
2）将否定深入到变元前面； 3）使用分配律将公式化为析（合）取范式
例如：求A=p∧(q→r)→s的析(合)取范式
解:A p∧(q∨r)→s
化掉→
(p∧(q∨r)) ∨ s 化掉→
西 华
p∨ (q∨r)∨s 否定深入
大 p∨ (q∧ r) ∨ s 否定深入 析取范式
学 p∨ s∨ (q∧ r)
M000/M0
000
0
西 PQ┐R 华 P┐QR
M001/M1
001
M010/M2
010
0 0
大 学
P┐Q┐R ┐PQR
M011/M3 M100/M4
011 100
0 0
┐PQ┐R
M101/M5
101
0
┐P┐QR
M110/M6
110
0
┐P┐Q┐R M111/M7 111
0
求主析取和主合取范式的方法（一）
显然：一般情况A≠A* (A*)*=A
1. 对偶式
2. 引理:A(p1,p2,…,pn) A* ( p1, p2,…, pn)
A *(p1,p2,…,pn) A ( p1, p2,…, pn)
证明:
西 华 大 学
因为 ┐(PQ)(┐P┐Q) ┐(PQ)┐P┐Q
所同以理┐┐AA(P*(1P, 1P,2P,…2 ,…,P,nPn))A*（A（┐┐PP1 ,1 ┐, ┐PP2 ,2…,…, ┐, ┐PPn）n）
极小项、极大项的足标与形式的对应
2. 主析取范式：极小项的析取式 主合取范式：极大项的合取式
3. 任何公式A都存在与之等价的主析(合)取范式 方法 1)：真值表法 2)：先求析(合)取范式，再求主析、合取范式
西 华 大 学
三个命题变元P,Q,R,极大项共有8个:
大项 编码 真值指派 大项的真值
PQR
华 大 学
((P∨Q)∨(R∧┐R ))∧((┐R∨P )∨(Q∧ ┐Q))
(P∨Q∨R)∧(P∨Q∨┐R)∧(P∨Q∨┐R)
∧
(P∨┐Q∨┐R) (P∨Q∨R)∧(P∨Q∨┐R)∧(P∨┐Q∨┐R)
(主合取范式)
M0∧M1∧M3
求(P Q) R的析取范式与合取范式。
解 : 原 式 ((P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q )