第二章 命题逻辑.

Slides:



Advertisements
Similar presentations
12.1 轴对称( 1 ) 给我最大快乐的, 不是已懂的知识, 而是不断的学习 高斯.
Advertisements

大不列颠的历史.
词语(成语) 的理解与运用 真 题 例 析 方 法 总 结 1.
小学科学中的化学 武威十九中 刘玉香.
制作人:徐嘉辉 郭海霞.
(教育学博士,曾任中学副校长,兼职南京大学博士后)
第一章 命题逻辑 杨圣洪 (qq) Kczx.hnu.cn 课程网站点击排行-更多-离散数学.
过早搏动.
第六节 心律失常 蚌埠医学院附属医院诊断学教研室.
南美洲 吉林省延吉一高中 韩贵新.
高考复习专题 高考命题与地理计算: 地理计算
1.动车组运用计划的含义 2.动车组运用计划编制影响因素的确定 3.主要影响因素分析
全力以赴的德忠精神 人力资源部王丽玲主任,从员工关系的工作,到招聘工作,再到现在的薪酬工作,不管在哪个岗位,她总是一丝不苟,尽职尽责。
第一章 体育统计的基本知识 主讲教师:王丽艳 徐栋.
第二章 命题逻辑(上) 主讲人:耿国华.
数理逻辑.
第3课时 逻辑连结词和四种命题 要点·疑点·考点 课 前 热 身   能力·思维·方法   延伸·拓展 误 解 分 析.
命题及其关系 命题.
命题与四种命题 高二数学 选修2-1 第一章 常用逻辑用语.
高二数学 选修2-1(理) 四种命题的关系 湖南省汉寿县第三中学 制作人:艾镇南.
常用逻辑语.
常用逻辑用语 第一章 “数学是思维的科学” 逻辑是研究思维形式和规律的科学. 逻辑用语是我们必不可少的工具.
第4讲 充分条件和必要条件.
1、命题:可以判断真假的语句,可写成:若p则q。 2、四种命题及相互关系:
钳加工技术 广西玉林高级技工学校|数控教研组.
让智慧的光芒照亮前进的路 《经济生活》教材分析及教学建议 春晖中学 杜随旺 2013年8月.
时政发布 制作:宋虹雷.
第五讲 地球公转及其地理意义 一、地球公转的 1.公转特征 (1)轨道:近似正圆的 轨道,太阳位于其中一个 上。
邏 輯 課程網頁: /
八桥初中九年级思想品德课复习导学案之五---
勾股定理 说课人:钱丹.
第一部分 流体力学 6 孔口、管嘴出流和 气体射流
第二章:命题逻辑等值演算 主要内容: 本章与其他各章的联系 等值式与基本的等值式 等值演算与置换规则
第6章 轴测投影图 图6.1 三视图和轴测图 (a)三视图 (b)正等测 (c)斜二测.
第十章 原子核 核外电子-原子物理学 原子核-原子核物理学.
命 题 # 判 断 复合命题. 命 题 # 判 断 复合命题 一、复合命题概述 1.定义 复合命题(compound proposition) ,就是以命题作为直接构成成分的命题,或者,包含有其他命题成分的命题。 例如: ① 并非所有去过作案现场的人都是作案人; ② 张××是法官,并且,张××是中共党员;
等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式,主析取范式与主合取范式 联结词完备集 可满足性问题与消解法
离散数学 东南大学 薛 晖 1.
第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备.
离散数学─逻辑和证明 南京大学计算机科学与技术系
第1章 基础:逻辑和证明 1.1 命题逻辑.
2019年1月2日星期三 离散  数学 计算机学院 冯伟森 2019年1月2日星期三.
人教版数学四年级(下) 乘法分配律 单击页面即可演示.
國中二年級 三角形的內心與外心 教學目標 教學設計 學習活動 學習評量.
李伟庭老师 (彩虹村天主教英文中学老师) 相似三角形.
Ch2 空間中的平面與直線 2-2 空間中的直線 製作老師:趙益男/基隆女中教師 發行公司:龍騰文化事業股份有限公司.
材料力学 第十二章 能量方法.
第二章 需求、供给和均衡价格 第一节 需求理论
簡介與使用說明 『數學的學習注重循序累進的邏輯結構』
第六章 文化需求 (文化消费的测量、影响因素)
Herbrand定理 王珏 张文生 中国科学院自动化研究所.
公式的真值表 离散结构 西安工程大学 计算机学院 王爱丽.
第二章 市场理论:产品市场及其均衡 在市场经济中,价格是由供求关系决定的,所以,供给与需求分析是分析产品市场及其均衡的起点。本章首先分析产品市场的需求和供给,并在此基础上分析产品市场上均衡的形成和均衡价格的决定。
——解题思维中的金钥匙 主讲人:马立丽 元认知心理干预技术研究所
选修2-1简易逻辑第一节 命题和充要条件.
軌跡圖 Loci Drawing 姓名: 班別: ( ) 軌跡圖.
Welcome 实验:筷子提米.
小学5.
§3 命题演算的形式证明 一个数学系统通常由一些描述系统特有性质的陈述句所确定,这些陈述句称为假设,
花盆邂逅弹簧的传奇 胡 越 强 手机: QQ:
§3 谓词演算的形式证明 一、形式证明 P(Y)上的一阶谓词演算用Pred(Y)表示
信用部財務專業人員初級研習班 台灣債券市場簡介
重庆市万州高级中学 三角函数热点专题复习 重庆市万州高级中学 2019年5月22日星期三7时41分18秒.
寡头竞争模型 寡头垄断市场不同于完全竞争和完全垄断市场:厂商间的策略性相互作用非常重要。 决策变量 博弈类型 产量 价格 静态 动态
§1-5(2) 系统框图的等效变换.
离散数学─逻辑和证明 南京大学计算机科学与技术系
第二章 命题逻辑等值演算 主要内容 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式,主析取范式与主合取范式 联结词完备集
八年级下册物理第十章 浮力 全章复习 《浮力难点专题突破》.
第二章 数控车削加工常用指令及应用 1.常用辅助功能指令 2.直线车削指令——G01/G00 3.圆弧车削指令——G02/G03
函数与导数 临猗中学 陶建厂.
Presentation transcript:

第二章 命题逻辑

数理逻辑 数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号,简洁地表达出各种推理的逻辑关系,因此,数理逻辑一般又称为符号逻辑。 数理逻辑和计算机的发展有着密切的联系,它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。 古典数理逻辑:命题逻辑和谓词逻辑—是计算机科学很重要的数学基础。 现代数理逻辑:逻辑演算、证明论、公理集合论、递归论和模型论 。

数理逻辑的创始人--莱布尼茨 (Leibniz, Gottfried Wilhelm) 1646.7.1-1716.11.14 德国数学家、物理学家、哲学家等,一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法学、历史学、语言学、生物学以及外交、神学等诸多方面. 出生于德国东部莱比锡的一个书香之家,父亲是莱比锡大学的道德哲学教授,母亲出生在一个教授家庭。莱布尼兹的父亲在他年仅6岁时便去世了,给他留下了丰富的藏书。

15岁时,进了莱比锡大学学习法律,一进校便跟上了大学二年级标准的人文学科的课程,还广泛阅读了培根、开普勒、伽利略等人的著作,并对他们的著述进行深入的思考和评价。在听了教授讲授欧几里德的《几何原本》的课程后,莱布尼兹对数学产生了浓厚的兴趣。17岁时他在耶拿大学学习了短时期的数学,并获得了哲学硕士学位 。 26岁设计出世界第一台乘法器,被认为是现代机器数学的先驱者。 Leibniz(1646~1716年) 之梦:有一天所有的知识,包括精神和无形的真理,能够通过通用的代数演算放入一个单一的演绎系统。 1693年,发现了机械能的能量守恒定律。 与牛顿并称为微积分的创立者。 系统阐述了二进制记数法,并把它和中国的八卦联系起来。

第二章 命题逻辑 2.1 命题以及逻辑联结词 2.2 命题公式 2.3 命题公式的等价关系和蕴涵关系 2.4 范式 第二章 命题逻辑 2.1 命题以及逻辑联结词 2.2 命题公式 2.3 命题公式的等价关系和蕴涵关系 2.4 范式 2.5 命题逻辑在二值逻辑器件 和语句逻辑中的应用

2.1 命题以及逻辑联结词

1 命题 所谓命题是指一句有真假意义的话。 例如:上海是中国最大的城市 今天是星期二 所有素数都是奇数 1+1=2 命题用大写英文字母P,Q,…,P1,P2,…,表示。 “我在说谎”,这是既不能为真,又不能为假的句子,称为“悖论”。

下列句子中不是命题的有( ) A. 我不会解答这道题。 B. 严禁吸烟。 C. 我正在说谎。 D. 如果太阳从西方升起,你就可以长生不老。 下列句子中不是命题的有( ) A. 我不会解答这道题。 B. 严禁吸烟。 C. 我正在说谎。 D. 如果太阳从西方升起,你就可以长生不老。 E. 别的星球上有生物。 F. 几点了? G. 1960年长春春城电影院放映了国产故事片“白毛女”。 H. 1+101=110 I. 全体起立! J. 这个教室好大呀!

如果一个命题是真的,就说它的真值是1; 如果一个命题是假的,就说它的真值是0。 也用“1”代表一个抽象的真命题,用“0”代表一个抽象的假命题。

2 逻辑联结词 定义2.1.1 设P是一个命题,命题 “P是不对的”称为P的否定,记以P,读作非P。 2 逻辑联结词 定义2.1.1 设P是一个命题,命题 “P是不对的”称为P的否定,记以P,读作非P。 真值规定:P是真的当且仅当P是假的。 例. P:吉大是中国最大的大学。 P:吉大不是中国最大的大学。 Q:张三是好人  Q :张三不是好人

定义2.1.2 设P,Q是两个命题,命题 “P或者Q”称为P,Q的析取,记以PQ,读作P或Q。

定义2.1.3 设P,Q是两个命题,命题 “P并且Q”称为P,Q的合取,记以PQ,读作P且Q。

注意: 自然语言中的“或者”一词有两种用法: 1) “张三或者李四考了90分”, 表示两者可以同时成立。这是“可兼或”。 按照联结词“”的定义,当P,Q都为真时,PQ也为真,因此,“”所表示的“或”是“可兼或”。

2) “我明天到北京出差或者到广州去度假”,表示的是二者只能居其一,不会同时成立。这是“不可兼或”。 “不可兼或” 不可以用来表示. 表示为:(PQ)  ( PQ) –异或

判断: (1)今天晚上我在家中看戏或去剧场看戏。 (2)他可能是100米或400米冠军。 (3)我第一节课上数学课或上英语课。 (4)李梅是三好学生或优秀团员。 (5)张三生于1987年或1988年。 (6)老王或小李有一个去上海出差。 (7)李明是软件学院的学生,他住在312室或 313室。

定义2.1.4 设P,Q是两个命题,命题 “如果P,则Q”称为P蕴涵Q,记以PQ。 真值规定: PQ是假的当且仅当P是真的而Q是假的。 例. P:f(x)是可微的, Q:f(x)是连续的, PQ: 若f(x)是可微的,则f(x)是连续的。

由定义知,如果P是假命题,则不管Q是什么命题,命题 “如果P,则Q”在命题逻辑中都被认为是真命题。 —与自然语言不一样的地方

定义2.1.5 设P,Q是两个命题,命题 “P当且仅当Q”称为P等价Q,记以PQ。 例如, P : a2+b2=a2, Q: b=0, PQ: a2+b2=a2当且仅当b=0 。

例2.1.1 如果你走路时看书,那么你会成为近视眼。 令P:你走路;Q:你看书; R:你会成为近视眼。

例2.1.2 除非他以书面或口头的方式正式通知我,否则我不参加明天的会议。 令P:他书面通知我; Q:他口头通知我; R:我参加明天的会议。

例2.1.3 设P,Q,R的意义如下: P:苹果是甜的;Q:苹果是红的; R:我买苹果。 试用日常语言复述下述复合命题: (1) (PQ)R (2) (PQ)R 解:(1)如果苹果甜且红,那么我买; (2)我没买苹果,因为苹果不甜也不红. 非P应该是什么?

2.2 命题公式

1 公式 我们用大写的英文字母P,Q,R,…等代表一个抽象的命题,或称为命题符号。 定义2.2.1 命题符号称为原子。 定义2.2.1 命题符号称为原子。 例如,Q,S,…等都是原子。

命题逻辑中的公式,是如下定义的一个符号串: (1) 原子是公式; (2) 0、1是公式; 定义2.2.2 命题公式 命题逻辑中的公式,是如下定义的一个符号串: (1) 原子是公式; (2) 0、1是公式; (3) 若G,H是公式,则(G),(GH), (GH),(GH),(GH)是公式; (4) 所有公式都是有限次使用(1),(2),(3) 得到的符号串。

规定: 公式(G)的括号可以省略,写成G。 整个公式的最外层括号可以省略。 五种逻辑联结词的优先级按如下次序递增: ,,,, 五种逻辑联结词的优先级按如下次序递增: ,,,, 例如,我们写符号串 PQRQSR 就意味着是如下公式: ((P(QR))(Q((S)R)))

2 解释 定义2.2.3 设G是命题公式,A1, …, An是出现在G中的所有原子。 指定A1, …, An的一组真值,则这组真值称为G的一个解释。 设G是公式,I是G的一个解释,显然,G在I下有真值,通常记为TI(G)。

例 G=PQ,设解释I,I’如下: I: I’: 则TI (G)=1,TI’ (G)=0 注意:该例子中写成G=1或G=0是错误的! 1 1 P Q 1 0

定义2.2.4 公式G在其所有可能的解释下所取真值的表,称为G的真值表。 显然,有n个不同原子的公式,共有2n个解释。

例:G=(PQ)R,其真值表如下: P Q R G 1

练习:请画出 P , PQ, PQ, PQ,PQ的真值表。

若公式G中出现的所有原子为A1,…,An,有时我们用{m1,…,mn}表示G的一个解释I,其中 例.公式G=(PQ)R的真值表中第二个解释就可以记为{P,Q,R}

定义2.2.5 公式G称为恒真的(或有效的),如果G在它的所有解释下都是真的;

从真值表可以看出G1对所有解释具有“真”值,公式G3对所有解释具有“假”值,而G2具有“真”和“假”值。 考虑G1= (P→Q) →P, G2=(P →Q) P, G3=P   P。 从真值表可以看出G1对所有解释具有“真”值,公式G3对所有解释具有“假”值,而G2具有“真”和“假”值。 P Q G1 G2 G3 1

练习:用真值表判断公式 (P→Q)→((Q →R)→(P→R))的类型

G是恒真的 iff G是恒假的。 G是可满足的 iff 至少有一个解释I,使G在I下为真。 若G是恒真的,则G是可满足的; 反之不对。 如果公式G在解释I下是真的,则称I满足G; 如果G在解释I下是假的,则称I弄假G。

练习:求满足公式( P →Q )→P Q的解释和弄假它的解释。

在逻辑研究和计算机推理以及决策判断中,人们对于所研究的命题,最关心的莫过于“真”、“假”问题,所以恒真公式在数理逻辑研究中占有特殊且重要的地位。

3 判定问题 能否给出一个可行方法,对任意的公式,判定其是否是恒真公式。 因为一个命题公式的原子数目有限(n),从而解释的数目是有限的(2n),所以命题逻辑的判定问题是可解的(可判定的,可计算的). 结论:命题公式的恒真,恒假性是可判定的.

作业: 习题2.1-3, 习题2.2-1、3、4 下周二(2007年4月10日)交

§2.3 命题公式的等价关系 和蕴涵关系

1 公式的等价 定义2.3.1 称公式G,H是等价的,记以G=H,如果G,H在其任意解释I下,其真值相同。 公式G,H等价 iff 公式GH恒真。 公式间的等价关系有自反性、对称性、传递性。

基本等价式 1) (GH)=(GH)(HG); 2) (GH)=(GH); 3) GG=G,GG=G; (等幂律) 4) GH=HG,GH=HG; (交换律) 5) G(HS)=(GH)S, G(HS)=(GH)S; (结合律) 证明方法?

6) G(GH)=G,G(GH)=G; (吸收律) 7) G(HS)=(GH)(GS), G(HS)=(GH)(GS); (分配律) 8) G0=G,G1=G; (同一律) 9) G0=0,G1=1; (零一律) 10) (GH)=GH, (GH)=GH。 (De Morgan律) (互补律: G G=1;G G=0 双重否定律:  G=G ) 上述等价式可用真值表验证。

证明命题公式恒真或恒假的两个方法 方法一. 真值表方法。 即列出公式的真值表,若表中对应公式所在列的每一取值全为1,这说明该公式在它的所有解释下都是真,因此是恒真的;若表中对应公式所在列的每一取值全为0,这说明该公式在它的所有解释下都为假,因此是恒假的。

方法二. 以基本等价式为基础,通过反复对一个公式的等价代换,使之最后转化为一个恒真式或恒假式,从而实现公式恒真或恒假的证明。 例.(P→Q)→((Q →R)→(P→R)) = ( P Q) (( Q R) ( P R)) = (P  Q) ((Q  R) ( P R)) = (P  Q) ((Q  P R) (R P R)) = (P  Q) ( (Q  P R) 1) = (P  Q)  (Q  P R) =(P  Q  P R) (Q Q  P R) =1 1=1

应用基本等价式的例子 例. ( P →Q )→ P Q = ( P Q)  (P Q) = (P   Q)  (P Q) = P  ( Q  Q) =P 1=P

例. 证明: (P Q)  (P R) (Q R)=(PQ)(P R) 证明: 左= (P Q)  (P R) ((PP)(QR)) = (P Q)  (P R) (PQR) (PQR) =((PQ)(PQR))((PR)(PRQ) =(PQ)(P R) =右

练习: 证明: P →(Q →R)= P Q →R 问: (P →Q)→R与P Q →R是否等价?

例.世界冰球赛正在激烈进行,看台上三位观众 正在热烈地议论着这次比赛的名次。 甲:中国第一,匈牙利第三 乙:奥地利第一,中国第三 丙:匈牙利第一,中国第二 比赛结束后,发现这三位观众每人恰好都猜对了 一半。假设无并列名次。 问:中国、奥地利、匈牙利各队的名次。 解: 设P1:中国第一; P2:中国第二; P3:中国第三 Q1:奥地利第一 R1:匈牙利第一; R3:匈牙利第三

由于甲、乙、丙个猜对一半,故有: (P1  R3) ( P1  R3)=1 (1) (Q1  P3) ( Q1  P3)=1 (2) (R1  P2) ( R1  P2)=1 (3) 无并列名次: P1Q1=0, P1R1=0,Q1R1=0,P3R3=0 (*) 每个国家只能得一个名次: P1P2=0,P1P3=0,P2P3=0,R1R3=0 (**)

(1)(2)左边合取,利用(*)(**)化简得:  P1  R3  Q1   P3 (4) (4)(3)左边合取,利用(*)(**)化简得:  P1  R3  Q1   P3   R1  P2 而右边合取得1。 由此得出结论: 奥地利第一,中国第二,匈牙利第三

2 完备集 定义2.3.2 完备集 设Q是逻辑运算符号集合,若所有逻辑运算都能由Q中元素表示出来,而Q的任意真子集无此性质,则称Q是一个完备集。 可以证明,{,},{,}都是完备集。

证明 {,} 是完备集 证明: PQ = ( P  Q) PQ = PQ= (PQ) PQ = (PQ) (QP) = ( P  Q) ( Q  P) = ((P  Q)) ((QP))

定义2.3.3 与非式 设P,Q是两个命题,命题 “P与Q的否定”称为P与Q的与非式,记作PQ。 “”称作与非联结词。 真值规定:PQ为真 iff P,Q不同时为真。 由定义可知: PQ=(PQ)。

定义2.3.4 或非式 设P,Q是两个命题,命题 “P或Q的否定”称为P与Q的或非式,记作PQ, 称作或非联结词。 定义2.3.4 或非式 设P,Q是两个命题,命题 “P或Q的否定”称为P与Q的或非式,记作PQ, 称作或非联结词。 真值规定:PQ为真 iff P,Q同时为假。 由定义可知: PQ=(PQ)

{}是完备集 P = (P  P) =PP PQ = ( P  Q) = (P)  (Q) =(PP)(QQ) PQ=  (PQ)=  (PQ) = ((PQ)  (PQ))=(PQ)(PQ) 读者可以自己证明{}也是完备集。

3 公式的蕴涵 逻辑的一个重要功能是研究推理。固然, 依靠等价关系可以进行推理。但是,进行 推理时,不必一定要依靠等价关系,只需 蕴涵关系就可以了。 例.若三角形等腰,则两底角相等, 这个三角形等腰, 所以,这个三角形两底角相等。 例.若行列式两行成比例,则行列式值为0, 这个行列式两行成比例, 所以,这个行列式值为0。

上面两个例子的推理关系涵义不同,但依据的推理规则相同,推理形式为: 若P则Q,P,所以Q。

设G,H是两个公式。 称H是G的逻辑结果(或称G蕴涵H),当且仅当对G,H的任意解释I,如果I满足G,则I也满足H,记作GH。 定义2.3.5 蕴涵 设G,H是两个公式。 称H是G的逻辑结果(或称G蕴涵H),当且仅当对G,H的任意解释I,如果I满足G,则I也满足H,记作GH。

注意: 符号“”和“=” 一样,它们都不是逻辑联结词,因此,G=H,GH也都不是公式。 定义2.3.5 蕴涵 注意: 符号“”和“=” 一样,它们都不是逻辑联结词,因此,G=H,GH也都不是公式。 是一种部分序关系。 公式G蕴涵公式H iff 公式GH是恒真的。 例. (PQ)P,(PQ)Q

GH当且仅当GH是恒真的 证明:必要性,任取G, H的解释I, 若I满足G( TI(G)=1),则由GH知, TI(H)=1 ,因此TI(GH)=1; 若I弄假G(TI(G)=0),则TI(GH)=1 。 从而,对G, H的任意解释I,都有GH为 真, 故GH是恒真的. 充分性,任取G, H的解释I,若TI(G)=1,由 GH恒真,知, TI(H)=1。从而有GH。

是一种部分序关系 证明:要证明公式间的蕴涵关系是部分序关系,需要证明其具有自反性、反对称性和传递性。 自反性:任取公式G,有G  G 恒真,因此, G G。 反对称性:若G  H,H  G,则 G  H,H  G恒真,从而, (G  H) (H  G)恒真,即,G  H恒真,故G=H。

是一种部分序关系 传递性:若GG1,G1H,则对G, G1, H的任意解释I,若I满足G,则由GG1知,I满足G1,再由G1H知,I满足H。因此,GH。

定义2.3.6 设G1, …, Gn,H是公式。 称H是G1, …,Gn的逻辑结果(或称G1, …, Gn共同蕴涵H),当且仅当 (G1 … Gn)  H。 显然,公式H是G1, …, Gn的逻辑结果 iff 公式((G1 … Gn)H)是恒真的。 例如,P,PQ共同蕴涵Q。 设G’ = G1 … Gn ,则公式H是G1, …, Gn的逻辑结果 当且仅当公式G’ 蕴涵 H 当且仅当公式 G’ H 是恒真的 当且仅当公式((G1 … Gn)H)是恒真的。 一个前提扩展到了多个前提。

定理2.3.1 如果H1, …, Hm,P共同蕴涵公式Q,则H1, …, Hm共同蕴涵公式PQ。 例. 因为公式PQ,QR,P共同蕴涵R,所以PQ,QR共同蕴涵PR。

定理2.3.1 证明:因为(H1 …HmP)Q,所以公式(H1 …HmP)Q是恒真的。 利用下面的基本等价公式: P1(P2P3)=(P1P2)P3 于是,(H1 …HmP)Q=(H1 …Hm)(PQ)。 故(H1 …Hm)(PQ)是恒真的。 所以H1,…,Hm共同蕴涵PQ。

4 演绎 定义2.3.7 设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列: G1, G2, …, Gk 其中,Gi (1≤i ≤ k)或者属于S,或者是某些 Gj (j<i)的逻辑结果。 并且 Gk就是G。 称公式G为“此演绎的” 逻辑结果,或称从S演绎出G。 有时也记为SG。

例 设S={PQ,QR,PM,M} 则下面的公式序列: M,PM,P,PQ,Q,QR,R 就是从S推出R的一个演绎。

5 演绎方法的可靠性与完备性 引理 设G,H1,H2是公式。 如果 GH1,GH2,则G(H1 H2) 。 证明:任取G,H1,H2的一个解释I。 若I满足G,由假设知,H1, H2都是G的逻辑结果,从而I满足 H1,而且I满足H2,故I满足 H1 H2。由I的任意性,知,G (H1 H2)。

定理2.3.2 设S是公式集合,G是一个公式。于是,从S演绎出G的充要条件是G是S的逻辑结果。 证明:必要性,设从S演绎出G,令 G1,…,Gk(即是G) 是这个演绎。 对任意 Gi (i=1,…,k),往证Gi 是S的逻辑结果。 对i用归纳法: (1) 当i=1时,因G1S,显然, G1 … G1 是恒真公式,故S G1 ,即 G1 是S的逻辑结果。

(2) 设i<n时,命题成立。 (3) 当i=n时, 若 GnS,则S Gn,归纳法完成. 若Gn是某些Gj (j<n)的逻辑结果,不妨设 (Gj1 …Gjh )Gn (1) 其中j1,…,jh都小于n。 由归纳假设知,SGjm ,m=1,…,h。由引理知:S( Gj1 …Gjh ) (2) 根据(1),(2)式及蕴涵关系的传递性,得 S Gn 即Gn是S的逻辑结果,归纳完成。

充分性,若G是S的逻辑结果,由演绎的定义知,G是如下演绎: H1 ,…,Hm ,G 的逻辑结果,其中 H1 ,…,Hm 是S中所有公式. 注:如果S中一部分公式就可以演绎出G, 则再添加上S中剩余的公式, 也是可以演绎出G的。

演绎定理 定理2.3.3 设S是前提公式集合,G,H是两个公式。 如果从S∪{G}可演绎出H,则从S可演绎出GH。 证明:因为从S∪{G}可演绎出H,由定理2.3.2知,H是S ∪{G}的逻辑结果。 亦即 (G1  … Gk G)H 其中 G1 ,…,Gk 是S中所有公式。 由定理2.3.1知: (G1  … Gk )(GH) 即GH是S的逻辑结果,再由定理2.3.2知,从S可演绎出GH。

基本蕴涵式 PQP PQQ PPQ QPQ P(PQ) Q(PQ) (PQ)P

基本蕴涵式 (PQ)Q P,QPQ P,PQQ P,PQQ Q,PQP PQ,QRPR PQ,PR,QRR

7 小结:公式间蕴涵的证明方法 给出两个公式G,H,证明G蕴涵H。 真值表法; 证G H是恒真公式; 利用一些基本等价式及蕴涵式进行推导; 7 小结:公式间蕴涵的证明方法 给出两个公式G,H,证明G蕴涵H。 真值表法; 证G H是恒真公式; 利用一些基本等价式及蕴涵式进行推导; 任取解释I,若I满足G,往证I满足H; 反证法,设结论假,往证前提假 (即证明H  G)。

真值表法 将公式G和公式H同列在一张真值表中,扫描公式G所对应的列,验证该列真值为1的每一项,它所在行上相应公式H所对应列上的每一项必为1(真),则公式G蕴涵H。

证G H是恒真公式 1 例. 设A、B和C为命题公式,且AB。请分别阐述(肯定或否定)下列关系式的正确性。 (1)(AC)  (BC);--正确 (2)(AC) ( BC)。--不正确 A B C AB AC BC ACBC AC BC (AC)(BC) 1

例 设A=(R P)  Q,B= P Q, 证明A蕴涵B。 证明:证明AB恒真。 ((R P)  Q) ( P Q) =  ( ( RP) Q) (PQ) =((RP)  Q) (PQ) =(R Q) ( P  Q) ( P  Q) =1

利用一些基本等价式及蕴涵式进行推导 例 设A=(R P)  Q,B= P Q, 证明A蕴涵B。 证明:由基本等价式可得: A=(R P)  Q = ( RP) Q = (R P) Q =( RQ) ( PQ) =( RQ) ( P Q) 由基本蕴涵式2. PQQ可知, ( RQ) ( P Q) (P Q),即A蕴涵B。

例. 设A= P Q,B=(RQ) ((PR) Q), 任取解释I,若I满足G,往证I满足H 例. 设A= P Q,B=(RQ) ((PR) Q), 证明A蕴涵B。 证明: 任取解释I,若I满足A,则有如下两种情况: (1)在解释I下,P为假,这时, TI(B)= (RQ) (R Q)=1, 因此,I亦满足B。 (2)在解释I下,Q为真,这时, TI(B)= 1 1=1,即,I亦满足B。 综上,I满足B,因此,A蕴涵B。

反证法,设结论假,往证前提假 (即证明H  G)。 例 设A=(R P)  Q,B= P Q, 证明A蕴涵B。 证明:假设存在解释I使P Q为假,则只有一种情形:P在I下为真,且Q在I下为假,这时R P在I下为真,故I弄假 (R P)  Q。因此,(RP) Q蕴涵 P Q。

7 公式蕴涵的证明方法 若给出前提集合S={G1 ,…,Gk },公式G,证明SG有如下两种方法: 1. G1  … Gk G 2. 形式演绎法

8 形式演绎法 根据一些基本等价式和基本蕴涵式,从S出发,演绎出G,在演绎过程中遵循以下三条规则: 8 形式演绎法 根据一些基本等价式和基本蕴涵式,从S出发,演绎出G,在演绎过程中遵循以下三条规则: 规则1. 可随便使用前提。 (根据演绎定义) 规则2. 可随便使用前面演绎出的某些公 式的逻辑结果。 (根据演绎的定义) 规则3. 如果需要演绎出的公式是PQ的 形式,则可将P做为附加前提使 用,而力图去演绎出Q。 (根据定理2.3.3)。

例2.3.1 证明{(PQ),(PR),(QS)}SR PQ 规则1 PQ 规则2,根据1 QS 规则1 PS 规则2,根据2,3 SP 规则2,根据4 PR 规则1 SR 规则2,根据5,6 SR 规则2,根据7

例2.3.2 证明{P(QS),RP,Q}RS RP 规则1 R 规则3 P 规则2,根据1,2 P(QS) 规则1

例2.3.3 若厂方拒绝增加工资,则罢工不会停止,除非罢工超过一年并且工厂经理辞职。 问:如果厂方拒绝增加工资,而罢工又刚刚开始,罢工是否能停止? 令 P: 厂方拒绝增加工资; Q: 罢工停止; R: 工厂经理辞职; S: 罢工超过一年。

于是, G1:(P(RS))Q G2:P G3:S H: Q 要证明: H是{G1,G2,G3}的逻辑结果。 1. S 规则1 2. SR 规则2,根据1

3. (RS) 规则2,根据2 4. P 规则1 5. P(RS) 规则2,根据3,4 6. (P(RS))Q 规则1 7. Q 规则2,根据5,6 亦即,罢工不会停止。

例.一个公安人员审查一件盗窃案,已知的事实如下: (1)A或B盗窃了x (2)若A盗窃了x,则作案时间不能发生在午夜前 (3)若B证词正确,则在午夜时屋里灯光未灭 (4)若B证词不正确,则作案时间发生在午夜前 (5)午夜时屋里灯光灭了 (6)A并不富裕 试用演绎法找出盗窃犯。 解:先将已知事实中的各简单命题符号化,设: P:A盗窃了x Q:B盗窃了x R:作案时间发生在午夜前 S:B证词正确 T:在午夜时屋里灯光未灭 U:A并不富裕

再将各前提写出: G1:P∨Q G2:P → R G3:S→T G4:S→R G5:T G6:U 演绎过程为: (1) S→T   规则1 (2) T 规则1 (3) S 规则2,根据(1),(2) (4) S→R 规则1 (5) R 规则2,根据(3),(4) (6) P → R 规则1 (7) P 规则2,根据(5),(6) (8) P∨Q 规则1 (9) Q 规则2,根据(7),(8) 因此,是B盗窃了x

作业 习题2.3 –1、7、8、9 2007年4月17日交

§2.4 范式

范式的引入 在命题逻辑中,对于含有有限个原子的命题公式来说,用真值表的方法,总可以在有限的步骤内确定它的真值,因此判定问题总是可解的。 但是我们知道,这种方法并不理想,因为公式每增加一个原子,真值表的行数就增加一倍。为了给出另一种方法,我们将介绍命题公式的一种标准形式,即范式,两个命题公式是否等价及一个公式恒真、恒假、可满足的判定,都将由公式的范式来解决。

1 析取范式和合取范式 定义2.4.1 原子或原子的否定称为文字。 例. P,P是文字。 1 析取范式和合取范式 定义2.4.1 原子或原子的否定称为文字。 例. P,P是文字。 定义2.4.2 有限个文字的析取式称为一个子句; 有限个文字的合取式称为一个短语。 特别,一个文字既可称为是一个子句,也可称为是一个短语。 例. P,PQ,PQ是子句,P,PQ,PQ是短语。 在命题逻辑中,对于含有有限个原子的命题公式来说,用真值表的方法,总可以在有限的步骤内确定它的真值,因此判定问题总是可解的。但是我们知道,这种方法并不理想,因为公式每增加一个原子,真值表的行数就增加一倍。为了给出另一种方法,我们将介绍命题公式的一种标准形式,即范式,两个命题公式是否等价及一个公式是否恒假(或恒真)的判定,都将由公式的范式来解决。

定义2.4.3 析取范式、合取范式 有限个短语的析取式称为析取范式; 有限个子句的合取式称为合取范式。 有限个短语的析取式称为析取范式; 有限个子句的合取式称为合取范式。 特别,一个文字既可称为是一个合取范式,也可称为是一个析取范式。一个子句,一个短语既可看做是合取范式,也可看做是析取范式。 例如,P,PQ,PQ,(PQ)(PQ)是析取范式。 P,PQ,PQ,(PQ)(PR)是合取范式。

定理2.4.1 对于任意命题公式,都存在等价于它的析取范式和合取范式。 证明:对于公式G,通过如下算法即可得出等价于G的范式: 步2. 使用(H)=H和摩根律,将G中所有的否定 号都放在原子之前。 步3. 反复使用分配律,即可得到等价于G的范 式。

例: G = (P(QR))S =P(QR)S =P(QR)S ……………. (析取范式) =P(QR)(S(QQ)) =P(QR)(SQ)(SQ) (析取范式) =(PS)(QR) =(PSQ)(PSR) …… (合取范式)

2 主析取范式 定义2.4.4 设P1,…,Pn是n个不同原子,一个短语如果恰好包含所有这n个原子或其否定,且其排列顺序与P1,…,Pn的顺序一致,则称此短语为关于P1,…,Pn的一个极小项。 例.对原子P,Q,R而言,PQR,PQR,PQR都是极小项,但是,P,PQ不是极小项,而PQ对原子P,Q而言是极小项。 显然,共有2n个不同的极小项。

极小项与解释的1-1对应关系 对于n个原子P1,…,Pn而言,其不同的解释共有2n个,对于P1,…,Pn的任一个极小项m,2n个解释中,有且只有一个解释使m取1值。 证明:任取一个极小项,按照如下方法构造其解释:对原子Pi (1≤i≤n),如果Pi出现在该极小项中,Pi指定为1;如果Pi的否定出现在该极小项中,Pi指定为0。则构造出来的解释使该极小项取1值, 而且只能构造出来一个这样的解释。

极小项与解释的1-1对应关系 例如,对P,Q,R而言,PQR是极小项,解释{P,Q,R}使该极小项取1值,其他解释都使该极小项取0值。

解释与n位二进制数的1-1对应关系 如果将真值1,0看做是数,则每一个解释对应一个n位二进制数。 假设使极小项m取1值的解释对应的二进制数为i,今后将m记为mi。

例: 对P,Q,R而言,PQR是极小项,解释(0,1,0)使该极小项取1值,解释(0,1,0)对应的二进制数是2,于是PQR记为m2。 对P,Q,R而言,8个极小项与其对应的解释如下:

极小项 解释 记法 PQR 000 m0 PQR 001 m1 PQR 010 m2 PQR 011 m3 PQR 100 m4 PQR 101 m5 PQR 110 m6 PQR 111 m7

一般地,对P1,…,Pn而言,2n个极小项为

定义2.4.5主析取范式 设命题公式G中所有不同原子为P1,…,Pn,如果G的某个析取范式G’中的每一个短语,都是关于P1,…,Pn的一个极小项,则称G’为G的 主析取范式。 恒假公式的主析取范式用0表示。

3 主析取范式(存在性) 定理2.4.2 对于命题公式G,都存在等价于它的主析取范式。 3 主析取范式(存在性) 定理2.4.2 对于命题公式G,都存在等价于它的主析取范式。 证明:设命题公式G中所有不同原子为P1,…,Pn,则等价于它的主析取范式的求法如下: (a) 将公式G化为析取范式G’。(由定理2.4.1知,存在析取范式G’,使得G=G’) (b) 删去析取范式中所有恒假的短语。 (c) 用等幂律将短语中重复出现的同一文字化简为一次出现,如,PP=P。

(d) 对于所有不是关于P1,…,Pn的极小项 的短语使用同一律,补进短语中未出现的 所有命题原子,并使用分配律展开,即, 如果Gi’不是关于P1,…,Pn的极小项,则Gi’ 中必然缺少原子P j1,…,Pjk,则 在定理2.4.2的证明中,实际上已经给出了求公式的主析取范式的方法。 于是将G’中非极小项Gi’化成了一些极小项之析取。对G’中其他非极小项也做如上处理,最后得等价于G的主析取范式G*。

例 求G=(RP)(Q(PR)) 的主析取范式 解: G =(RP)(Q(PR)) =(R  P)(Q  P)(Q  R) =(P  R)(P  Q)(Q  R) =((PR)(QQ))((PQ)(RR)) ((QR)(PP)) =(PQR)(PQR)(PQR) (PQR)

G的主析取范式为(PQR) (PQR) (PQR) (PQR) 求G=(PQ)(PR)(QR)的主析取范式 P Q R G 1 寻找与公式G等价的主析取范式,也可以通过真值表来做。 如果真值表中没有一行真值为1,则G’=0 G的主析取范式为(PQR) (PQR) (PQR) (PQR)

真值表法写主析取范式的正确性 定理. 在真值表中,使得公式为真的解释所对应的极小项的析取 即为此公式的主析取范式。    即为此公式的主析取范式。 证明:给定公式G,设用这种方法写出主析取范式为G’, 往证G= G’。 对G的任意解释I, (1)若解释I使G取1值,则在I下取1值的极小项写在G’中,故 G’在I下也取1值。 (2)若I使G取0值,而在I下取1值的极小项不在G’中且I弄假其 它所有极小项,故G’在I下也取0值。 所以G’是与G等价的主析取范式。

4 用范式判断公式的等价性 定理2.4.3 设公式G,H是关于原子P1,…,Pn的两个主析取范式。 如果G,H不完全相同,则G,H不等价。 证明:因为G,H不完全相同,所以或者G中有一个极小项不在H中; 或者反之。不妨设极小项mi 在G中而不在H中。 于是根据极小项的性质,二进制数i所对应的关于P1,…,Pn的解释Ii使mi取1值,从而使公式G取1值。 Ii使所有不是mi的极小项取0值,从而使公式H取0值。 故G,H不等价。

5 主析取范式(唯一性) 定理2.4.4 对于任意公式G,存在唯一一个与G等价的主析取范式。 (唯一性)

6 用范式判定公式的恒真恒假性 引理 短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。 6 用范式判定公式的恒真恒假性 引理 短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。 证明:充分性,若有一个原子P及其否定P同时出现在短语中,则此短语有形式: PP… 显然,不管是什么解释I,PP在I下取0值,于是此短语在I下取0值,故此短语恒假。

必要性. 若短语恒假,而任意原子及其否定均不同时在短语中出现。那么,取这样的解释I:指定带有否定号的原子取0值,不带否定号的原子取1值,显然,此短语在这个解释I下取1值,与此短语恒假矛盾。

定理2.4.5 命题公式G是恒假的当且仅当在等价于它的析取范式中,每个短语均至少包含一个原子及其否定。 证明: 设G的析取范式如下: G=G1…Gn 其中Gi是短语,i=1,…,n。 显然,公式G恒假的充要条件是每个Gi恒假。 再根据引理,此定理结论显然成立。

例2.4.1 判断公式G=(PQ)(QR)(RP)是否恒假? 解: G=(PQ)(QR)(RP) =((PQ)(QQ)(PR)(QR))(RP) =(PQR)(QQR)(PRR)(Q RR)(PQP)(QQP)(PRP) (QRP) 故公式G不是恒假的。

例2.4.2 判断公式G=(PQ)PQ是否恒假? 解:G=(PQ)PQ =(PQ)PQ =(PPQ)(QPQ) 故公式G是恒假的。

7 判定公式是否恒真的其它方法 把公式化成主析取范式, 公式恒假时,主析取范式没有极小项; 公式恒真时,主析取范式有全部极小项。

2. 一种判定算法 对任给要判定的命题公式G,设其中有原子P1,P2,…,Pn,令P1取1值,求G的真值,或为1,或为0,或成为新公式G1且其中只有原子P2,…, Pn,再令P1取0值,求G真值,如此继续,到最终只含0或1为止,若最终结果全为1,则公式G恒真,若最终结果全为0,则公式G恒假,若最终结果有1,有0,则是可满足的。

例2.4.3 (PQR)(PQ)(PR) (QR)QR RR 1 P取1值 P取0值 Q取1值 Q取0值 R取1值

补充:主合取范式 模仿主析取范式的概念,引进主合取范式的概念。 定义:设P1,…,Pn是n个不同原子,一个子句如果恰好包含所有这n个原子或其否定,且其排列顺序与P1,…,Pn的顺序一致,则称此子句为关于P1,…,Pn的一个极大项。 定义:设命题公式G中所有不同原子为P1,…,Pn,如果G的某个合取范式G’中的每一个子句,都是关于P1,…,Pn的一个极大项,则称G’为G的主合取范式。

极小项与极大项性质 P Q R 极小项 极大项 1 m0= P QR M0=PQR m1= P QR m0= P QR M0=PQR 1 m1= P QR M1=PQR m2= P QR M2=PQR m3= P QR M3=PQR m4= P  Q  R M4=PQR m5= P  Q R M5=PQ R m6= P Q  R M6=P Q R m7= P Q R M7=PQR

极小项与极大项性质 对n个命题原子P1,…,Pn 极小项有如下性质: (1)n个命题原子P1,…,Pn有2n个不同的解释,每个解释对应P1,…,Pn的一个极小项。 (2)对P1,…,Pn的任意一个极小项m,有且只有一个解释使m取1值,若使极小项取1的解释对应的二进制数为i,则m记为mi。 (3)任意两个不同的极小项的合取式恒假: mi mj=0,i≠j。 (4)所有极小项的析取式恒真。

极大项有如下性质: (1)n个命题原子P1,…,Pn有2n个不同的解释,每个解释对应P1,…,Pn的一个极大项。 (2)对P1,…,Pn的任意一个极大项M,有且只有一个解释使M取0值,若使极大项取0的解释对应的二进制数为i,则M记为Mi。 (3)任意两个不同的极大项的析取式恒真: Mi  Mj=1,i≠j。 (4)所有极大项的合取式恒假。 极小项和极大项的关系:mi= Mi ,Mi=mi

主合取范式与主析取范式之间的关系 例. 若PQR为一公式G的主合取范式,则 G =G = M0 =(M1M2…M7)

从一公式A的主合取范式(PQ)求其主析取范式的步骤为: (1)求出A的主合取范式中没有包含的所有极大项。 P  Q, P  Q, P  Q (2)求出与(1)中极大项下标相同的极小项。 P  Q, P  Q, P  Q (3)将(2)求出的所有极小项析取起来,即得A的主析取范式。 (P  Q)  ( P  Q)  (P  Q)

例.若(PQ)(PQ)(PQ)为一公式H的主析取范式, H=H =((PQ)(PQ)(PQ)) =((m0 m1 m3) =  (m2) =M2 = PQ 为H的主合取范式。

由主析取范式求主合取范式: (1)求出A的主析取范式中没有包含的所有极小项。m2 (2)求出与(1)中极小项下标相同的极大项。 M2 (3)将(2)求出的所有极大项合取起来,即得A的主合取范式。

定理. 对任意命题公式,存在唯一一个与其等价的主合取范式。 证明: (存在性) 设命题公式G中所有不同原子为P1,…,Pn,则等价于它的主合取范式的求法如下: (a) 将公式G化为合取范式G’。(由定理2.4.1知,存在合取范式G’,使得G=G’) (b) 删去合取范式中所有恒真的子句。 (c) 用等幂律将子句中重复出现的同一文字化简为一次出现,如,P  P=P。

(d)对于G’中的每一个子句G’i进行检查,如果G’i不是关于P1,…,Pn的极大项,则G’i必然缺少原子Pj1,…Pjk。则可以通过如下方式扩展G’i G’i= G’i (Pj1 Pj1) …( Pjk Pjk) =Mi1…Mi2k 于是将G’中的非极大项G’i化成了一些极大 项的合取。 对其它非极大项也做同样处理,得到等价 于G的主合取范式G’’。

(唯一性)也就是证明对任意两个关于P1,…,Pn的主合取范式,如果公式不完全相同,则G与H不等价。 设公式G、H是关于P1,…,Pn的任意两个主合取范式。若G和H不完全相同,则必然存在一个极大项Mi在G中而不在H中(或相反),则取一解释I使Mi取0值,即,使公式G取0值。由定义可知I使非Mi的极大项都为1,从而有I使H取1值。所以G与H不等价。

用真值表法求主合取范式的正确性 定理. 在真值表中,使得公式为假的解释所对应的极大项 的合取即为此公式的主合取范式。 定理. 在真值表中,使得公式为假的解释所对应的极大项     的合取即为此公式的主合取范式。 证明: 给定公式G,设用这种方法写出主合取范式为G’,往证G= G’。 任意取G, G’ 的一个解释I。 如果I满足G,则唯一的一个在I下为假的那个极大项不在G’中出现,而I使所有其他的极大项取1,这样,G’在I下的真值是1; 如果I弄假G,则唯一的一个在I下为假的那个极大项出现在G’中,从而G’在下取0值。 这样,G与G’是等价的。

求主合取范式和主析取范式的方法 方法一. 真值表法。主析取范式恰好是使得公式为真的解释所对应的极小项的析取组成,主合取范式恰好是使得公式为假的解释所对应的极大项的合取组成。 方法二. 公式推导法。

例 求公式G= P→(Q→R)的主析取范式与主合取范式。 1

解:(1)使用真值表法。 根据真值表中使得公式为真的解释,所对应的极 小项的析取即为其主析取范式: G=(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) = m0 m1 m2  m3 m4 m5 m7 根据真值表中使得公式为假的解释,所对应的极 大项的合取即为其主合取范式: G=  P  Q  R= M6

(2)公式推导法 G= P→(Q→R) = P  Q  R =(P(QQ)(RR)) ( Q(PP)(RR)) (R(PP)(QQ)) = (PQR) (PQR)(PQR)  ( PQR)  (PQR)  (PQR) = m0 m1 m2  m3 m4 m5 m7 = M6

定理. 命题公式G是恒真的当且仅当在等价于它的合取范式中,每个子句均至少包含一个原子及其否定。 证明:设公式G的合取范式为:G’=G1G2…Gn 若公式G恒真,则G’恒真,即子句Gi,i=1,2,…n恒真 为其充要条件。下面只需证明:子句是恒真的当且仅当 至少有一个原子及其否定(也称互补对)同时在此子句中 出现。 若有一个原子P及其否定P同时出现在子句中,则此子句有形式: PP…  显然,不管是什么解释I,PP在I下取1值,于是此子句在I下取1值,故恒真。 假设子句恒真,但每个原子和其否定都不同时出现在其中。则可以给定一个解释I,使带否定号的原子为1,不带否定号的原子为0,那么此子句在解释I下的取值为0。这与子句恒真矛盾。

主合取范式与主析取范式的应用 利用主合取范式与主析取范式可求解判定问题 主析取范式:公式恒假时,主析取范式没有极小项(G’=0);公式恒真时,主析取范式包含所有极小项。 主合取范式:公式恒假时,主合取范式包含所有极大项;公式恒真时,主合取范式没有极大项(G’=1)。

由于任意公式的主范式是唯一的,所以可以分别求出两 个给定的公式的主范式,若二者主范式相同,则给定的 证明等价式成立 由于任意公式的主范式是唯一的,所以可以分别求出两 个给定的公式的主范式,若二者主范式相同,则给定的 两公式是等价的,否则,给定的两公式不等价。 例 判断P→(Q→R)与(P Q)→ R是否等价。 证明: 利用求主合取范式的方法来判断。 由前知,P→(Q→R)的主合取范式为:M6。 下面求(P Q)→ R的主合取范式。  (P Q)→ R = (P Q) R =( PQ)R =( PR)(QR) =( P(QQ)R)((PP)QR) =( PQR) ( PQR) (PQR) = M2  M4  M6 二者的主合取范式不相同,因此,这两个公式不等价。

作业 习题2.4--5