二章命题逻辑等值演算.ppt
《二章命题逻辑等值演算.ppt》由会员分享,可在线阅读,更多相关《二章命题逻辑等值演算.ppt(70页珍藏版)》请在三一文库上搜索。
1、第二章:命题逻辑等值演算,主要内容: 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式,主析取范式与主合取范式 联结词完备集 本章与其他各章的联系 是第一章的抽象与延伸 是后续各章的先行准备,第一节:等值式,2.1 等值式,若等价式AB是重言式,则称A与B等值,记作AB,并称AB是等值式 几点说明: 定义中,A, B, 均为元语言符号 A或B中可能有哑元出现. 例如,在 (pq) (pq) (rr) 中,r为左边公式的哑元. 用真值表可验证两个公式是否等值,2.1 等值式,例子 判断pp,2.1 等值式,例子 判断 pq pq,2.1 等值式,如果命题变项很多,怎么办? - 利用已
2、知的等值式通过代换得到新的等值式 命题:设A是一个命题公式,含有命题变项p1,p2,pn,又设A1,A2,An是任意的命题公式. 对每个i(i=1,2,n),把pi在A中的所有出现都替换成Ai,所得到的新命题公式记作B. 那么,如果A是重言式,则B也是重言式.,2.1 等值式,否定律 双重否定律 pp 德摩根律 (p q) p q (p q) p q 幂等律 p p p, p p p 交换律 p q q p p q q p p q q p,2.1 等值式,结合律 (p q) r p (q r) (p q) r p (q r) (p q) r p (q r) 分配律 p (q r) (p q)
3、(p r) p (q r) (p q) (p r),2.1 等值式,常元律 零律: p 1 1, p 0 0 同一律: p 0 p, p 1 p 排中律: p p 1 矛盾律: p p 0 吸收律 p (p q) p p (p q) p,2.1 等值式,蕴涵等值式 p q p q 等价等值式 p q (p q) (q p) 假言易位 p q q p 等价否定等值式 p q p q 归谬论 (p q ) (p q ) p,2.1 等值式,说明: (1)16组等值模式都可以给出无穷多个同类型的具体的等值式。 (2)证明上述16组等值式的代入实例方法可用真值表法,把改为所得的命题公式为永真式,则成立
4、。,2.1 等值式,等值演算:由已知的等值式推演出另外一些等值式的过程 置换规则:设(A)是含公式A的命题公式, (B)是用公式B置换了(A)中所有A后得到的命题公式,若B ,则(A) (B) 说明: 等值演算过程中遵循的重要规则 一个命题公式A,经多次置换,所得到的新公式与原公式等价,2.1 等值式,1.用等值演算验证等值式 试证:p(qr) (p q)r 证明: p(qr)p(qr) p(qr)pqr pqr(p q) r (p q) r (p q)r,2.1 等值式,试证: (p q)(p(p q)(pq) 左边 (p q) (p(p q) (p q) (p(p q) (p q) (p
5、q) (p p q) (q p q) (p q),2.1 等值式,2. 用等值演算判断公式的类型 证明: (pq) (p (qr)(pq)(p r)为一永真式 证明:原式 (pq) (p(q r)(pq)(pr) (pq) (pq) (pr)(pq) (pr) (pq) (pr)(pq) (pr) 1,2.1 等值式,3解判定问题 在某次研讨会的中间休息时间,3名与会者根据王教授的口音对他是哪个省市的人判断如下: 甲:王教授不是苏州人,是上海人 乙:王教授不是上海人,是苏州人 丙:王教授既不是上海人,也不是杭州人 听完这3人的判断后,王教授笑着说,你们3人中有一人说得全对,有一人说对了一半,另
6、一人说得全不对。试用逻辑演算分析王教授到底是哪里人。,第二节:析取范式与合取范式,2.2 析取范式和合取范式,文字(literal): 命题变项及其否定 简单析取式:仅由有限个文字构成的析取式 简单合取式:仅由有限个文字构成的合取式 例:设p、q为二个命题变元 p,q,pp,qq,pq, q p,pq,p q 称为简单析取式 p,q,pp,qq, pq, q p,pq,p q 称为简单合取式。,2.2 析取范式和合取范式,定理: 1)一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否定式 2)一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否定式,2.2 析取范式和合取范式,析
7、取范式:由有限个简单合取式构成的析取式 A1 An, Ai 为简单合取式 (p q) (p r) 合取范式:由有限个简单析取式构成的合取式 A1 An, Ai 为简单析取式 (p q) (p r) 析取范式与合取范式统称为范式,2.2 析取范式和合取范式,定理: Ai 简单合取式, A1 An F 当且仅当 Ai F,任意Ai Ai 简单析取式, A1 An T 当且仅当 Ai T,任意Ai,2.2 析取范式和合取范式,范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法: 步骤一:消去“”、“”联结词 步骤二:消去双重否定符,内移否定符 步骤三:使用分配律,2.2 析取范式
8、和合取范式,范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法: 步骤一:消去“”、“”联结词 步骤二:消去双重否定符,内移否定符 步骤三:使用分配律,2.2 析取范式和合取范式,步骤一:利用等值公式:化去“”、“”联结词 p q p q p q (p q) (q p),2.2 析取范式和合取范式,范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法: 步骤一:消去“”、“”联结词 步骤二:消去双重否定符,内移否定符 步骤三:使用分配律,2.2 析取范式和合取范式,消去双重否定符,内移否定符 德摩根律 (p q) p q (p q) p q 双重否定律 p
9、 p,2.2 析取范式和合取范式,范式存在定理: 任意命题公式都存在着与之等值的析取范式与合取范式 方法: 步骤一:消去“”、“”联结词 步骤二:消去双重否定符,内移否定符 步骤三:使用分配律,2.2 析取范式和合取范式,利用“”对“”的分配,将公式化成为析取范式 p (q r) (p q) (p r) 利用“”对“”的分配,将公式化成为合取范式 p (q r) (p q) (p r),2.2 析取范式和合取范式,例:求(p q) (p q)的析取范式 化去 ( p q) (p q) “”对“”分配,化为析取范式 ( p p q) (q p q) 最简析取范式 p q,2.2 析取范式和合取范
10、式,例:求(p q) r) p的析取范式和合取范式 (一) 求析取范式 原式 (p q) r) p (p q) r) p ( (p q) r) p (p q) r) p (p r) (q r) p p (p r) (q r) p (q r),2.2 析取范式和合取范式,(二)求合取范式 原式 (p q) r) p (p q) r) p ( (p q) r) p (p q) r) p (p p q) (p r) (p q) (p r),2.2 析取范式和合取范式,问题: 一个命题公式的析取范式是不是唯一的? 同一命题公式的析取范式是不是等值的?,2.2 析取范式和合取范式,极小项(极大项):含有
11、n个命题变项的简单合取式 (简单析取式),并满足 每个命题变元和它的否定式不同时出现,而二者之一必出现且仅出现一次 第i个命题变项或它的否定式出现在从左算起的第i位上(若无角标,则按字典顺序排列) 若有个命题变项,则有2n个极小项(极大项) 如果我们把不带否定符的命题变项取成1,带否定符的命题变项取成0,那么每一个极小项都对应一个二进制数,因而也对应一个十进制数,2.2 析取范式和合取范式,极小项的编码:对应成真赋值 三个变元p、q、r可构造8个极小项: pqr FFF 0 记作 m0 pqr FFT 1 记作 m1 pqr FTF 2 记作 m2 pqr FTT 3 记作 m3 pqr TF
12、F 4 记作 m4 pqr TFT 5 记作 m5 pqr TTF 6 记作 m6 pqr TTT 7 记作 m7,2.2 析取范式和合取范式,极大项的编码:对应成假赋值 如三个变元 p、q、r,其记法如下: pqr F F F 0 记作 M0 p q r F F T 1 记作 M1 p qr F T F 2 记作 M2 p q r F T T 3 记作 M3 p q r T T T 7 记作 M7,2.2 析取范式和合取范式,定理:设mi和Mi是命题变元p1, p2 pn形成的极小项和极大项,则: (1) mi mj F, (ij) (2) Mi Mj T, (ij) (3) mi Mi;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 命题逻辑 等值 演算
链接地址:https://www.31doc.com/p-3106337.html