第一章命题演算基础

1、醉雪醉雪风随心动风随心动 数理逻辑数理逻辑第一章第一章 命题演算基础命题演算基础第二章第二章 命题演算的推理理论命题演算的推理理论第三章第三章 谓词演算基础谓词演算基础第四章第四章 谓词演算的推理理论谓词演算的推理理论第五章第五章 递归函数论递归函数论数理逻辑数理逻辑集集 合合 论论图图 论论代代 数数24学时学时17学时学时19学时学时12学时学时醉雪醉雪风随心动风随心动 逻辑学逻辑学研究推理的科学研究推理的科学早期创始人早期创始人 亚里士多德亚里士多德(公元前公元前384322) 柏拉图柏拉图(公元前公元前429348), 首先把逻辑学的思首先把逻辑学的思想方法引入几何学想方法引入几何学

2、苏格拉底苏格拉底（前（前470前前399年）年）醉雪醉雪风随心动风随心动 数理逻辑数理逻辑数学化的逻辑学数学化的逻辑学 德国德国G.W. Leibniz (1626-1716)把数学引入形式逻辑，把数学引入形式逻辑，明确提出用数学方法研究推理。明确提出用数学方法研究推理。 英国英国G. Boole (1815-1864)等创立了逻辑代数，等创立了逻辑代数，1847年年Boole实现了命题演算。实现了命题演算。 德国德国G. Frege (1848-1925)在在1879年建立了第一个谓词年建立了第一个谓词演算系统。演算系统。 英国英国B. Russell (1872-1970)等从逻辑学的基本

3、法则建等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。立了自然数理论、实数理论及解析几何学等。 奥地利奥地利K. Godel (1906-1978)在在1931年提出年提出Godel不完不完全性定理。全性定理。 英国英国Alan M. Turing (1912-1954)在在1936年提出一种抽年提出一种抽象计算模型（数学逻辑机），引入图灵机象计算模型（数学逻辑机），引入图灵机一种一种理想的计算机。理想的计算机。醉雪醉雪风随心动风随心动 在计算机科学中的逻辑在计算机科学中的逻辑创建一种语言创建一种语言,使人们能够对计算机科学领域使人们能够对计算机科学领域中所遇到的情境进行建模中所

4、遇到的情境进行建模, 并在这种方式下并在这种方式下, 对对情境进行形式化推理。情境进行形式化推理。对情境进行推理意味着构造与其相关的论证，对情境进行推理意味着构造与其相关的论证，人们希望这个过程形式化，使这些论证经得起人们希望这个过程形式化，使这些论证经得起严格的推敲，或者能够在计算机上实现。严格的推敲，或者能够在计算机上实现。醉雪醉雪风随心动风随心动 例例1 前提？前提？ 结论？结论？ 怎么推理怎么推理?如果火车晚点，而且车站没有出租车，那么小如果火车晚点，而且车站没有出租车，那么小王参加会议就会迟到。小王没有迟到，火车的王参加会议就会迟到。小王没有迟到，火车的确晚点了，因此，车站有出租车。

5、确晚点了，因此，车站有出租车。P：火车晚点：火车晚点Q：车站有出租车：车站有出租车R：小王参加会议会迟到：小王参加会议会迟到如果如果P且非且非Q,那么那么R。非。非R，P，因此，因此，Q。醉雪醉雪风随心动风随心动 例例2 前提？前提？ 结论？结论？ 怎么推理怎么推理?如果下雨，小李没有带伞，就会被淋湿。而小如果下雨，小李没有带伞，就会被淋湿。而小李没有被淋湿，确实下雨了，因此，小李带伞李没有被淋湿，确实下雨了，因此，小李带伞了。了。P：下雨：下雨Q：小李带伞小李带伞R：小李被淋湿小李被淋湿如果如果P且非且非Q,那么那么R。非。非R，P，因此，因此，Q。醉雪醉雪风随心动风随心动 数理逻辑的学习数

6、理逻辑的学习“我现在年纪大了，搞了这么多年的我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。二十岁的话，我就去学逻辑。” Edsger. W. Dijkstra 1972年年Turing奖获得者奖获得者 (1930-2002)带权图的最短通路算法醉雪醉雪风随心动风随心动

7、第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3 合式公式合式公式1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用醉雪醉雪风随心动风随心动 (一一) 命题定义命题定义定义定义1： 凡是可以凡是可以判断真假判断真假的的陈述句陈述句称为命题。称为命题。命题的值命题的值 真真, 用用T(或或1)表示表示假假, 用用F(或或0)表示表示醉雪醉雪风随心动风随心动 例：下列句子都是命题吗？ 雪是白的。雪是白的。 雪是黑的。雪是黑的。 好大的雪啊！好大的雪啊！ 8大于大于12。 1+101=110。

8、醉雪醉雪风随心动风随心动 例：下列句子都是命题吗？上海世博会开幕时天晴上海世博会开幕时天晴 21世纪末，人类将住在月球世纪末，人类将住在月球 大于大于2的偶数可表示成两个素数之和的偶数可表示成两个素数之和X0， 则则 x20。例例3 a=0当且仅当当且仅当 |a|=0。醉雪醉雪风随心动风随心动 真值函项的定义以真假为以真假为定义域定义域并以真假为并以真假为值域值域的函数的函数T, F(T, T), (T,F),(F,T), (F,F)T, F一元真值函项一元真值函项二元真值函项二元真值函项醉雪醉雪风随心动风随心动 一元联结词的真值表一个命题变项一个命题变项P，可取，可取“T”和和“F”两种值。

9、两种值。可定义四个一元真值函项可定义四个一元真值函项 f0，f1，f2，f3。P f0(P) f1(P) f2(P) f3(P)T T T F FF T F T F永永真真恒恒等等否否定定 P永永假假醉雪醉雪风随心动风随心动 二元联结词 P Q f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15T T T F T T T F F F T T T T F F F FT F T T F T T F T T F F T F T F F FF T T T T F T T F T F T F F F T F FF F T T T T F T T F

10、 T F F F F F T Ff4为析取f2为蕴含f8为等价f11为合取醉雪醉雪风随心动风随心动 三元联结词共有多少个？f0f1f2f?(0,0,0)0101(0,0,1)0011(0,1,0)0001(0,1,1)0001(1,0,0)0001(1,0,1)0001(1,1,0)0001(1,1,1)000128醉雪醉雪风随心动风随心动 第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.1.1 命题命题 1.1.2 联结词联结词 1.1.3 合式公式合式公式 1.2 1.2 真假性真假性1.3 1.3 范式及其应用范式及其应用醉雪醉雪风随心动风随心动 合式公

11、式(Well formed formulae) 合式公式为如下定义的式子，简称为公式：合式公式为如下定义的式子，简称为公式： 任何命题变元均是公式；任何命题变元均是公式； 如果如果P为公式，则为公式，则 P为公式；为公式； 如果如果P，Q为公式，则为公式，则 P Q, P Q, PQ, PQ 为公式；为公式；当且仅当经过有限次使用当且仅当经过有限次使用、所组成的所组成的符号串才是公式，否则不为公式符号串才是公式，否则不为公式 。醉雪醉雪风随心动风随心动 n 元公式 若公式若公式 中有中有n n个不同的命题变元，个不同的命题变元，就说就说 为为n n 元公式。元公式。3元公式的例子：元公式的例子

12、： （P Q） R）（ P Q）（P Q R）（ P Q）醉雪醉雪风随心动风随心动 优先级约定 非非 比其它联结词比其它联结词有更高的优先级有更高的优先级 括号括号（）（）内的运算优先内的运算优先本书未约定本书未约定 和比有更高的优先级 是右结合的醉雪醉雪风随心动风随心动 命题符号化步骤：步骤：分析出简单命题，符号化分析出简单命题，符号化用联结词联结简单命题用联结词联结简单命题提示：根据命题的实际含义，不拘泥于原句形式地确提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词。定原子命题和选用联结词。醉雪醉雪风随心动风随心动 例4(p5)已知三个命题：已知三个命题： P：今晚我在

13、家上网；：今晚我在家上网；Q：今晚我去球场看足球比赛；：今晚我去球场看足球比赛；R：今晚我在家上网或去球场看足球比赛。：今晚我在家上网或去球场看足球比赛。试问试问P Q和和R是否表达同一命题？是否表达同一命题？请用真值表说明之。请用真值表说明之。 R=( P Q) (PQ)P Q PQ R T T T F T F T T F T T T F F F F不可兼 或或 醉雪醉雪风随心动风随心动 例 将下述命题符号化，并指出真值: （1）豆沙包是由面粉和红小豆做成的。 （2）2是质数或合数。 （3）吃一堑，长一智。 （4）n是偶数当且仅当它能被3整除。 （n为一固定的自然数）醉雪醉雪风随心动风随心动

14、 例 令 p：北京比天津人口多。 q：2+24。 r：乌鸦是白色的。 求下列公式的真值： (1) (qr)(pr) (2) (pr) (pr) 醉雪醉雪风随心动风随心动 第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1 解释解释 1.2.2 1.2.2 等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式1.3 1.3 范式及其应用范式及其应用醉雪醉雪风随心动风随心动 完全解释、部分解释完全解释、部分解释定义：设定义：设n元公式元公式 中所有

15、的不同的命题变元为中所有的不同的命题变元为 P1, ,Pn 如果对每个命题变元均给予一个确定的值，如果对每个命题变元均给予一个确定的值，则称对公式则称对公式 给了一个给了一个完全解释完全解释； 如果仅对部分变元给予确定的值，如果仅对部分变元给予确定的值， 则称对公式则称对公式 给了一个给了一个部分解释部分解释。n元公式元公式 有有2n个完全解释。个完全解释。醉雪醉雪风随心动风随心动 例 考察公式考察公式 =（P Q） R PQR TTTTTTFFTT*不能确定F*T醉雪醉雪风随心动风随心动 成真解释与成假解释定义：对于任何公式定义：对于任何公式 ，凡使得，凡使得 取真值的解释，不管取真值的解释

16、，不管是完全解释还是部分解释，均称为是完全解释还是部分解释，均称为 的成真解释。的成真解释。定义：对于任何公式定义：对于任何公式 ，凡使得，凡使得 取假值的解释，不管取假值的解释，不管是完全解释还是部分解释，均称为是完全解释还是部分解释，均称为 的成假解释。的成假解释。醉雪醉雪风随心动风随心动 例 考察公式考察公式 =（P Q） R PQR TTTT1个成真解释TTFF1个成假解释TT*不能确定1个成真解释1个成假解释F*T4个成真解释醉雪醉雪风随心动风随心动 永真公式与永假公式永真公式与永假公式定义：如果一个公式的所有完全解释均为成真定义：如果一个公式的所有完全解释均为成真解释，则称该公式为

17、解释，则称该公式为永真公式永真公式或称为重或称为重言式。言式。定义定义: 如果一个公式的所有完全解释均为成假如果一个公式的所有完全解释均为成假解释，则称该公式为解释，则称该公式为永假公式永假公式或称为予或称为予盾式。盾式。例例 P P 永假公式永假公式 P P 永真公式永真公式 P P 永真公式永真公式醉雪醉雪风随心动风随心动 可满足公式与非永真公式可满足公式与非永真公式定义：如果一个公式存在成真解释，定义：如果一个公式存在成真解释， 则称该公式为则称该公式为可满足公式可满足公式； 如果一个公式存在成假解释，如果一个公式存在成假解释， 则称该公式为则称该公式为非永真公式非永真公式。例例 P Q

18、 可满足公式，非永真公式可满足公式，非永真公式 P Q 可满足公式，非永真公式可满足公式，非永真公式醉雪醉雪风随心动风随心动 第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1 解释解释 1.2.2 1.2.2 等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式1.3 1.3 范式及其应用范式及其应用醉雪醉雪风随心动风随心动 逻辑等价逻辑等价定义：给定两个公式定义：给定两个公式 和和 ， 设设P1，P2，Pn为为 和和 的所有命题变元，的所有

19、命题变元， 那么那么 和和 有有2n个解释。个解释。 如果对每个解释，如果对每个解释， 和和 永取相同的真假值，永取相同的真假值， 则称则称 和和 是是逻辑等价逻辑等价的，记为的，记为 = 。 醉雪醉雪风随心动风随心动 例例 问：问： P P = P?从真值表，可以看出：从真值表，可以看出： P P = PP P P P TFTF=FFTFT=T考察真值表如下考察真值表如下醉雪醉雪风随心动风随心动 八组重要的等价公式 双重否定律双重否定律 P=P结合律结合律 （P Q） R = P （Q R） （P Q） R = P （Q R）分配律分配律 P （Q R）=（P Q ） （P R） P （Q

20、R）=（P Q ） （P R）醉雪醉雪风随心动风随心动 八组重要的等价公式交换律交换律 P Q= Q P P Q= Q P等幂律等幂律 P P = P P P = P P P = T P P = T醉雪醉雪风随心动风随心动 八组重要的等价公式等值公式等值公式 P Q = P Q P Q =（PQ） （Q P） =（ P Q） （P Q） =（P Q） （ P Q） （P Q）= PQ （P Q）= PQ醉雪醉雪风随心动风随心动 八组重要的等价公式 部份解释部份解释 P T = P P F = F P T = T P F = P T P = P F P = T P T = T P F = P T

21、 P = P F P = P?醉雪醉雪风随心动风随心动 八组重要的等价公式吸收律吸收律 P （P Q）= P P （P Q）= P醉雪醉雪风随心动风随心动 例 判断下列公式的类型 q ( pq) p)解解: 考察真值表考察真值表 所以，它是永真的所以，它是永真的。 pqA= pqB=ApC= BqCTTTTFTTFFFTTFTTFTTFFTFTT醉雪醉雪风随心动风随心动 例 判断下列公式的类型 q ( pq) p)解解: q ( pq) p) =q( ( pq) ) p =(q p )( ( pq) ) =T 所以，它是永真的所以，它是永真的。 醉雪醉雪风随心动风随心动 例 判断下列公式的类型

22、判断下列公式的类型 (pq) p解解: 考察真值表考察真值表 所以，它是可满足的所以，它是可满足的。 pqA=pqB= pABTTTFFTFFFFFTTTTFFTTT醉雪醉雪风随心动风随心动 例 判断下列公式的类型判断下列公式的类型 (pq) p解解: (pq) p =( pq) p = p 所以，它是可满足的。所以，它是可满足的。醉雪醉雪风随心动风随心动 例 判断下列公式的类型 (p p) (q q) r)解解: (p p) (q q) r) = T (q q) r) = (q q) r =Fr =F 所以，它是永假的。所以，它是永假的。醉雪醉雪风随心动风随心动 成真解释和成假解释的求解方法

23、 （1）否定深入：即把否定词一直深入至命题变）否定深入：即把否定词一直深入至命题变元上；元上；（2）部分解释：选定某个出现次数最多的变元）部分解释：选定某个出现次数最多的变元对它作真或假的两种解释从而对它作真或假的两种解释从而得公式；得公式；（3）化简；）化简；（4）依次类推，直至产生公式的所有解释。）依次类推，直至产生公式的所有解释。醉雪醉雪风随心动风随心动 例(p7) 试判定公式 (P Q)( QP)R) 的永真性和可满足性。的永真性和可满足性。解解1：否定深入：否定深入 原式原式 = ( P Q)( QP)R) 对对 P=T 进行解释并化简，进行解释并化简， 结果见教材。结果见教材。醉雪

24、醉雪风随心动风随心动 解解2：否定深入：否定深入 原式原式 = ( P Q)( QP)R) 对对P=F进行解释并化简。进行解释并化简。 原式原式=（ FQ）（ QF）R） = （ QF）R = Q R Q=T 时，时， 原式原式 =TR = R， 于是于是 R=T 时，原式时，原式=F R=F 时，原式时，原式=T 因此因此,公式存在成真解释公式存在成真解释 (P，Q，R)=(F，T，F) ； 公式存在成假解释公式存在成假解释(P，Q，R)=(F，T，T)。 故公式可满足但非永真。故公式可满足但非永真。醉雪醉雪风随心动风随心动 解解3：考察：考察 (P Q)( QP)R)所以，公式存在成真解释

25、：所以，公式存在成真解释： (T,T,*), (T,F,F), (F,T,F), (F,F,T); 公式存在成假解释：公式存在成假解释： (T,F,T), (F,T,T), (F,F,F)。故公式可满足但非永真。故公式可满足但非永真。(P,Q,R)A=(PQ)B=QPC=BRAC(T,T,T)FTFT(T,T,F)FFFT(T,F,T)TTFF(T,F,F)TTTT(F,T,T)TTFF(F,T,F)TTTT(F,F,T)TFTT(F,F,F)TFFF醉雪醉雪风随心动风随心动 例例 试求下列公式的成真解释和成假解释试求下列公式的成真解释和成假解释 （PQ） （Q （ R P）解解:当当P=T时

26、时, 原式原式= (TQ) (Q ( R T) = Q (Q ( R)= QR 当当P=F时时, 原式原式= (FQ) (Q ( R F) = T (Q F)=Q由上可知由上可知: 公式不是永真公式公式不是永真公式,是可满足的是可满足的. 成真解释为成真解释为(P,Q,R)=(T,F,F),(F,T,*), 成假解释为成假解释为(P,Q,R)=(T,T,T),(T,F,T),(T,T,F),(F,F*).醉雪醉雪风随心动风随心动 第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1 解释解释 1.2.2 1.2.2

27、等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式1.3 1.3 范式及其应用范式及其应用醉雪醉雪风随心动风随心动 联结词的完备集 定义定义 设设S是联结词的集合，如果是联结词的集合，如果 对任何命题演算公式均可以由对任何命题演算公式均可以由S中的联中的联结词表示出来的公式与之等价结词表示出来的公式与之等价， 则说则说S是联结词的完备集。是联结词的完备集。由联结词的定义知，联结词集合由联结词的定义知，联结词集合 ， ， ，是完备的。是完备的。 醉雪醉雪风随心动风随心动 定理1 联结词的集合联结词的集合 ， ， 是完备的。

28、是完备的。思路思路: 去蕴含词与等价词去蕴含词与等价词 PQ = P Q PQ =（ P Q） （P Q） 醉雪醉雪风随心动风随心动 定理定理 联结词的集合联结词的集合 ， 是完备的。是完备的。思路思路: 在去蕴含词与等价词的基础上在去蕴含词与等价词的基础上, PQ = P Q PQ =（ P Q） （P Q） 去析取词：去析取词： P Q = （ P Q） 醉雪醉雪风随心动风随心动 定理定理 联结词的集合联结词的集合 ， 是完备的。是完备的。思路思路: 在去蕴含词与等价词的基础上在去蕴含词与等价词的基础上, PQ = P Q PQ =（ P Q） （P Q） 去合取词去合取词 P Q = （

29、 P Q）醉雪醉雪风随心动风随心动 定理定理 联结词的集合联结词的集合 ， 是完备的。是完备的。思路思路: 去等价词、析取词、合取词：去等价词、析取词、合取词： PQ =（ PQ ） （ PQ ） P Q= PQ PQ = （ P Q）= （P Q） 醉雪醉雪风随心动风随心动 与非与非: P Q = （P Q） P Q P Q T T FT F TF T TF F T定理定理2(p8) 联结词的集合联结词的集合是完备的。是完备的。 思路：思路： 去否定词与合取词：去否定词与合取词： P = P P P Q= （P Q）醉雪醉雪风随心动风随心动 或非：或非： PQ= (PQ) 定理：定理： 联结

30、词的集合联结词的集合是完备的。是完备的。 P Q PQ T T FT F FF T FF F T思路：思路： 去否定词与析取词：去否定词与析取词： P = P P P Q= （P Q）醉雪醉雪风随心动风随心动 例例(p8) 试证明联结词集合试证明联结词集合不完备。不完备。证明：证明： 对于任意公式对于任意公式P， P也是公式也是公式 。 假设假设是完备的。根据完备性的定义知，是完备的。根据完备性的定义知， P = Q1 Q2 Q3 Qn 当当P，Q1, Q2, Q3, , Qn全取为真时，全取为真时，公式左边公式左边=F，公式右边，公式右边=T。 显然矛盾。显然矛盾。 故联结词集合故联结词集合

31、不完备。不完备。 醉雪醉雪风随心动风随心动 例例 试证明联结词集合试证明联结词集合不完备。不完备。证明：证明： 对于任意公式对于任意公式P， P也是公式也是公式 。 假设假设是完备的。根据完备性的定义知，是完备的。根据完备性的定义知， P = Q1 Q2 Q3 Qn 当当P，Q1, Q2, Q3, , Qn全取为假时，全取为假时，公式左边公式左边=T，公式右边，公式右边=F。 显然矛盾。显然矛盾。 故联结词集合故联结词集合不完备。不完备。 醉雪醉雪风随心动风随心动 第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.2.1 1.2.1

32、 解释解释 1.2.2 1.2.2 等价公式等价公式 1.2.3 1.2.3 联结词的完备集联结词的完备集 1.2.4 1.2.4 对偶式和内否式对偶式和内否式 1.3 1.3 范式及其应用范式及其应用醉雪醉雪风随心动风随心动 对偶式对偶式的定义 定义：将任何一个定义：将任何一个不含不含蕴含词和等价词的命题蕴含词和等价词的命题演算公式演算公式 中的中的 换为换为 ， 换为换为 后所得的公式称为后所得的公式称为 的的对偶式对偶式， 记为记为 *。 醉雪醉雪风随心动风随心动 例例 已知公式已知公式 = P （QR）, 求对偶式求对偶式 *、 （ *）* 。解：解： = P （QR） *= P （Q

33、R） ( *)*= P （QR）醉雪醉雪风随心动风随心动 内否式的定义定义：将任何命题演算公式定义：将任何命题演算公式 中的所有中的所有 肯定形式换为否定形式、肯定形式换为否定形式、 否定形式换为肯定形式否定形式换为肯定形式 后所得的公式称为后所得的公式称为 的的内否式内否式， 记为记为 。醉雪醉雪风随心动风随心动 例例 已知公式已知公式 = P （QR）, 求内否式求内否式 、 （ ） 。解：解： = P （QR） = P （ Q R）（ ） = P （Q R）醉雪醉雪风随心动风随心动 对偶式和内否式的性质对偶式和内否式的性质 性质性质1 （ *）* = （ ） = 醉雪醉雪风随心动风随心动

34、 对偶式和内否式的否定对偶式和内否式的否定定理定理1(p9) （A*）=（ A）* （A）=（ A）醉雪醉雪风随心动风随心动 定理定理2(p9) A =A*证明：证明：思路是对公式思路是对公式A中出现的联结词的个数中出现的联结词的个数n进行归纳证明进行归纳证明。 当当n=0时，时， A中无联结词，便有中无联结词，便有 A=P， 从而有从而有 A= P， A*=P ， 所以所以 A* = P= A， 即定理成立。即定理成立。 醉雪醉雪风随心动风随心动 证明证明(续续): 归纳假设：设归纳假设：设n k时定理成立。时定理成立。 考察考察n=k+1 1，A中至少有一个联结词，中至少有一个联结词， 可

35、分为下面三种情形：可分为下面三种情形： A= A1， A=A1 A2， A=A1 A2 其中其中A1，A2中的联结词个数中的联结词个数 k 。 依归纳假设依归纳假设 A1= A1* ， A2= A2* 。 对于上述三种情形，可以分别证明结论成立：对于上述三种情形，可以分别证明结论成立： A =A*。 由数学归纳法知，定理得证。由数学归纳法知，定理得证。醉雪醉雪风随心动风随心动 第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.3 1.3 范式及其应用范式及其应用 1.3.1 1.3.1 范式范式 1.3.2 1.3.2 主范式主范式

36、 1.3.3 1.3.3 范式的应用范式的应用醉雪醉雪风随心动风随心动 合取式、析取式合取式、析取式定义定义1 命题变元、或者命题变元的否定、或由它们命题变元、或者命题变元的否定、或由它们利用合取词组成的合式公式称为利用合取词组成的合式公式称为合取式合取式。定义定义2 命题变元、或者命题变元的否定、或由它们命题变元、或者命题变元的否定、或由它们利用析取词组成的合式公式称为利用析取词组成的合式公式称为析取式析取式。例例 显然，显然， P， P，P Q， P QR 均为合取式；均为合取式； P， P，P Q， P QR 均为析取式。均为析取式。醉雪醉雪风随心动风随心动 (一一) 解释与合取式、析取

37、式之间的关系解释与合取式、析取式之间的关系 定理定理1 任给一个成真解释有且仅有一个合取式任给一个成真解释有且仅有一个合取式与之对应；与之对应； 任给一个成假解释有且仅有任给一个成假解释有且仅有一个析取式与之对应。一个析取式与之对应。 反之亦然。反之亦然。例例 成真解释成真解释(P，Q，R)= (T,F,T) 成假解释成假解释(P，Q，R)= (F,F,T)合取式合取式PQ R析取式析取式P QR醉雪醉雪风随心动风随心动 析取范式、合取范式析取范式、合取范式定义定义3 形如形如A1 A2 An的公式称为的公式称为析取范式析取范式， 其中其中Ai(i=1,2,n)为合取式。为合取式。定义定义4

38、形如形如A1 A2 An的公式称为的公式称为合取范式合取范式， 其中其中Ai(i=1,2,n)为析取式。为析取式。例例 P， P，P Q，P Q ，( P Q) (SR) 均为析取范式。均为析取范式。 P， P，P Q，P Q ， ( P Q) (SR)均为合取范式。均为合取范式。醉雪醉雪风随心动风随心动 例例: 考察公式考察公式 =PQ的的析取范式析取范式有两个成真解释：有两个成真解释： (T, T), (F, F), 分别对应于两个合取式为分别对应于两个合取式为 PQ, P Q于是，有于是，有 = (PQ) ( P Q)P Q P QT T TT F FF T FF F T醉雪醉雪风随心动

39、风随心动 例例: 考察公式考察公式 =PQ的的合取范式合取范式成假解释成假解释 (T, F), (F, T), 对应析取式为对应析取式为 PQ, P Q于是，有：于是，有： = ( PQ) (P Q)P Q P QT T TT F FF T FF F T醉雪醉雪风随心动风随心动 定理定理2 任何命题演算公式均可以化为合任何命题演算公式均可以化为合取范式，也可以化为析取范式。取范式，也可以化为析取范式。证明：证明： (1)设公式设公式 为永真公式为永真公式 =PP (2)设公式设公式 为永假公式为永假公式 =P P醉雪醉雪风随心动风随心动 证明证明(3)： 设公式设公式 既非永真又非永假。既非永

40、真又非永假。设公式设公式 的成真解释为的成真解释为 1， 2， n， 成假解释为成假解释为 1， 2， t。根据解释和范式的关系知：根据解释和范式的关系知：对应于成真解释对应于成真解释 1， 2， n的合取式为的合取式为 1， 2， n对应于成假解释对应于成假解释 1， 2， t的析取式为的析取式为 1， 2， t而公式而公式 12 n的成真解释为的成真解释为 1， 2， n；公式公式 12 t的成假解释为的成假解释为 1， 2， t。根据根据两个公式逻辑等价的定义两个公式逻辑等价的定义知知 = 12 n = 12 t故公式故公式 既可表示为析取范式又可表示为合取范式。既可表示为析取范式又可表

41、示为合取范式。醉雪醉雪风随心动风随心动 (二二) 析取范式和合取范式的求解方法析取范式和合取范式的求解方法 等价变换法等价变换法解释法解释法醉雪醉雪风随心动风随心动 等价变换法等价变换法(1)去蕴含词与等价词：去蕴含词与等价词： PQ = P Q PQ =（ P Q） （P Q）(2)否定深入：否定深入： (P Q)= PQ (P Q)= PQ， P = P(3)重复使用分配律：重复使用分配律： P (Q R)=(P Q ) (P R) P (Q R)=(P Q ) (P R)醉雪醉雪风随心动风随心动 解释法解释法(1) 求所有成真解释、成假解释；求所有成真解释、成假解释；(2) 写出成真解释

42、对应的合取式、写出成真解释对应的合取式、 成假解释对应的析取式；成假解释对应的析取式；(3) 把所有的合取式用析取词联结起来就构成析把所有的合取式用析取词联结起来就构成析取范式，把所有的析取式用合取词联结起取范式，把所有的析取式用合取词联结起来就构成合取范式。来就构成合取范式。醉雪醉雪风随心动风随心动 例例 求公式的范式求公式的范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取范式析取范式 = P ( QR) 合取范式合取范式醉雪醉雪风随心动风随心动 解：解：P=T时时, 原式原式

43、= (TQ) (RQ)T) = Q R P=F时时, 原式原式= (FQ) (RQ)F) =F 所以有所以有: 成真解释为：成真解释为：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F) 成假解释为：成假解释为：(P,Q,R)=(T,T,T), (F, , )例例 求公式的范式求公式的范式 (PQ)(RQ)P)于是析取范式为于是析取范式为: (PQ R) (P Q R) (P Q R) 合取范式为：合取范式为： ( P QR) P醉雪醉雪风随心动风随心动 范式不唯一性范式不唯一性例例 求公式的范式求公式的范式 (PQ)(RQ)P)解解1： 原式原式=(PQ) (PR) 析取范式

44、析取范式 = P ( QR) 合取范式合取范式解解2: 析取范式为析取范式为: (PQ R) (P Q R) (P Q R) 合取范式为：合取范式为： ( P QR) P醉雪醉雪风随心动风随心动 第一章第一章 命题演算基础命题演算基础1.11.1 命题和联结词命题和联结词 1.2 1.2 真假性真假性 1.3 1.3 范式及其应用范式及其应用 1.3.1 1.3.1 范式范式 1.3.2 1.3.2 主范式主范式 1.3.3 1.3.3 范式的应用范式的应用醉雪醉雪风随心动风随心动 (一一) 主析取范式主析取范式定义定义1 对于对于n个命题变元个命题变元P1，P2，Pn，公式，公式 Q1 Q2

45、 Qn 称为称为极小项极小项，其中，其中Qi=Pi或或 Pi(i=1，n)。例例 由两个命题变元由两个命题变元P，Q组成的极小项有四个，它们组成的极小项有四个，它们分别为：分别为： PQ P QPQ P Q醉雪醉雪风随心动风随心动 三个命题变元三个命题变元P、Q和和R可构造可构造8个极小项个极小项把命题变元的否定形式看成把命题变元的否定形式看成0，肯定形式看成，肯定形式看成1，则每，则每个极小项对应一个二进制数，也对应一个十进制数。个极小项对应一个二进制数，也对应一个十进制数。它们对应如下：它们对应如下： PQR 与与000 或或0对应，简记为对应，简记为 m0 PQ R 与与001 或或1对

46、应，简记为对应，简记为 m1 P QR 与与010 或或2对应，简记为对应，简记为 m2 P Q R 与与011 或或3对应，简记为对应，简记为 m3 PQR 与与100 或或4对应，简记为对应，简记为 m4 PQ R 与与101 或或5对应，简记为对应，简记为 m5 P QR 与与110 或或6对应，简记为对应，简记为 m6 P Q R 与与111 或或7对应，简记为对应，简记为 m7醉雪醉雪风随心动风随心动 n个命题变元组成的极小项有个命题变元组成的极小项有2n个个 公式的每一个完全成真解释对应一个极小项公式的每一个完全成真解释对应一个极小项 公式的所有完全成真解释对应极小项的析取公式的所

47、有完全成真解释对应极小项的析取醉雪醉雪风随心动风随心动 主析取范式主析取范式 定义定义2 仅有极小项构成的析取范式称为仅有极小项构成的析取范式称为主析取范式主析取范式。定理定理1 任何一个合式公式，均有惟一的一个主析取范式任何一个合式公式，均有惟一的一个主析取范式与该合式公式等价。与该合式公式等价。主析取范式就是主析取范式就是公式的所有完全成真解释对应极小项的析取。公式的所有完全成真解释对应极小项的析取。 醉雪醉雪风随心动风随心动 求主析取范式的两种方法(1)解释法解释法: 根据公式的所有完全成真解释，求出与这些根据公式的所有完全成真解释，求出与这些成真解释对应的合取式，所有合取式的析取就为成

48、真解释对应的合取式，所有合取式的析取就为公式的主析取范式。公式的主析取范式。(2)等价变换法等价变换法: 将析取范式中的每一个合取式用将析取范式中的每一个合取式用AA填填满命题变元，然后用等价公式进行变换，消去相满命题变元，然后用等价公式进行变换，消去相同部分，即得公式的主析取范式。同部分，即得公式的主析取范式。醉雪醉雪风随心动风随心动 例例 求公式的求公式的主析取范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取范式析取范式 =(PQ (R R) (P (QQ)R) = (PQ

49、R) (PQ R) (P QR) =101 100 110=4 5 6醉雪醉雪风随心动风随心动 解：解：P=T时时, 原式原式= (TQ) (RQ)T) = Q R P=F时时, 原式原式= (FQ) (RQ)F) =F 所以有所以有: 成真解释为：成真解释为：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F) 例例 求公式的求公式的主析取范式 (PQ)(RQ)P)于是主析取范式为于是主析取范式为: (PQ R) (P Q R) (P Q R) =101 100 110=4 5 6醉雪醉雪风随心动风随心动 (二二) 主合取范式主合取范式定义定义3 对于对于n个命变元个命变元P1

50、，P2，Pn，公式，公式 Q1 Q2 Qn 称为称为极大项极大项，其中，其中Qi=Pi或或 Pi(i=1，n)。例例 由两个命题变元由两个命题变元P，Q组成的极大项有四个，它们组成的极大项有四个，它们分别为：分别为： PQ P Q PQ P Q醉雪醉雪风随心动风随心动 三个命题变元三个命题变元P、Q和和R可构造可构造8个极大项个极大项 把命题变元的否定形式看成把命题变元的否定形式看成1，肯定形式看成，肯定形式看成0，则每个，则每个极大项对应一个二进制数，也对应一个十进制数。它们极大项对应一个二进制数，也对应一个十进制数。它们对应如下：对应如下： P Q R 与与000 或或0对应，简记为对应，

51、简记为 M0 P QR 与与001 或或1对应，简记为对应，简记为 M1 PQ R 与与010 或或2对应，简记为对应，简记为 M2 PQR 与与011 或或3对应，简记为对应，简记为 M3 P Q R 与与100 或或4对应，简记为对应，简记为 M4 P QR 与与101 或或5对应，简记为对应，简记为 M5 PQ R 与与110 或或6对应，简记为对应，简记为 M6 PQR与与111 或或7对应，简记为对应，简记为 M7醉雪醉雪风随心动风随心动 n个命题变元组成的极大项有个命题变元组成的极大项有2n个个 公式的每一个完全成假解释对应一个极大项公式的每一个完全成假解释对应一个极大项 公式的所

52、有完全成假解释对应极大项的合取公式的所有完全成假解释对应极大项的合取醉雪醉雪风随心动风随心动 主合取范式主合取范式定义定义4 仅有极大项构成的合取范式称为仅有极大项构成的合取范式称为主合取范式主合取范式。 定理定理2 任何一个合式公式，均有惟一的一个主合取范式与任何一个合式公式，均有惟一的一个主合取范式与该合式公式等价。该合式公式等价。主合取范式就是主合取范式就是公式的所有完全成假解释对应的极大项的合取。公式的所有完全成假解释对应的极大项的合取。醉雪醉雪风随心动风随心动 求主合取范式的两种方法求主合取范式的两种方法(1)解释法解释法 根据公式的所有完全成假解释，求出与这些根据公式的所有完全成假

53、解释，求出与这些成假解释对应的析取式，所有析取式的合取就为成假解释对应的析取式，所有析取式的合取就为公式的主合取范式。公式的主合取范式。(2)等价变换法等价变换法 将合取范式中的每一个析取式用将合取范式中的每一个析取式用AA填满命题变元，然后用等价公式进行变换，消去填满命题变元，然后用等价公式进行变换，消去相同部份，即得公式的主合取范式。相同部份，即得公式的主合取范式。醉雪醉雪风随心动风随心动 例例 求公式的主合取范式求公式的主合取范式 (PQ)(RQ)P)解解：原式原式= ( P Q)( ( RQ)P) =(PQ) ( RQ) P) =(PQ) (PR) (PQ) =(PQ) (PR) 析取

54、范式析取范式 = P ( QR) 合取范式合取范式 =(P (QQ) (RR) ( QR) (PP) =(P Q R) (P QR) (PQ R) (PQR) ( PQR) =000 001 010 011 111=0 1 2 3 7醉雪醉雪风随心动风随心动 解：解：P=T时时, 原式原式= (TQ) (RQ)T) = Q R P=F时时, 原式原式= (FQ) (RQ)F) =F 所以有所以有: 成假解释为：成假解释为：(P,Q,R)=(T,T,T), (F, , )例例 求公式的主合取范式求公式的主合取范式 (PQ)(RQ)P)于是于是主合取范式主合取范式= ( PQR) (PQR) (P

55、Q R) (P QR) (P Q R) =111 011 010 001 000=0 1 2 3 7(F,TT),(F,T,F),(F,F,T),(F,F,F)醉雪醉雪风随心动风随心动 例例 试求试求 =(PR)( P ( Q R) 的主析取范式和主合取范式的主析取范式和主合取范式解解: =( PR) ( P( QR)(P( ( QR)（去蕴涵词、等价词）（去蕴涵词、等价词） =( PR) ( P QR) (PQ) (P R)（化简）（化简） =(P R) ( P QR) (PQ) (P R)（去蕴涵词）（去蕴涵词） = (P R) ( P QR)(PQ) =(110 100) 001 (111 110)=(1,4,6,7)醉雪醉雪风随心动风随心动 解解(续续): 已经得到已经得到主析取范式如下主析取范式如下: = ( P QR)(PQ)(P R)=( PP)( PQ)( QP) ( QQ)(PR)(QR)(P R) =( PQ)( QP)(PR)(QR)