第一章 命题演算基础ppt课件.ppt

《第一章 命题演算基础ppt课件.ppt》由会员分享，可在线阅读，更多相关《第一章 命题演算基础ppt课件.ppt（132页珍藏版）》请在三一办公上搜索。

1、数理逻辑,第一章 命题演算基础第二章 命题演算的推理理论第三章 谓词演算基础第四章 谓词演算的推理理论第五章 递归函数论,数理逻辑,集 合 论,图 论,代 数,24学时,17学时,19学时,12学时,逻辑学研究推理的科学,早期创始人亚里士多德(公元前384322)柏拉图(公元前429348), 首先把逻辑学的思想方法引入几何学苏格拉底（前470前399年）,数理逻辑数学化的逻辑学,德国G.W. Leibniz (1626-1716)把数学引入形式逻辑，明确提出用数学方法研究推理。英国G. Boole (1815-1864)等创立了逻辑代数，1847年Boole实现了命题演算。德国G. Freg

2、e (1848-1925)在1879年建立了第一个谓词演算系统。英国B. Russell (1872-1970)等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。奥地利K. Godel (1906-1978)在1931年提出Godel不完全性定理。英国Alan M. Turing (1912-1954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机一种理想的计算机。,在计算机科学中的逻辑,创建一种语言,使人们能够对计算机科学领域中所遇到的情境进行建模, 并在这种方式下, 对情境进行形式化推理。对情境进行推理意味着构造与其相关的论证，人们希望这个过程形式化，使这些论证经得

3、起严格的推敲，或者能够在计算机上实现。,例1 前提？ 结论？ 怎么推理?,如果火车晚点，而且车站没有出租车，那么小王参加会议就会迟到。小王没有迟到，火车的确晚点了，因此，车站有出租车。,例2 前提？ 结论？ 怎么推理?,如果下雨，小李没有带伞，就会被淋湿。而小李没有被淋湿，确实下雨了，因此，小李带伞了。,数理逻辑的学习,“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。” Edsger. W. Dijkstra 1972年Tur

4、ing奖获得者 (1930-2002),带权图的最短通路算法,第一章 命题演算基础,1.1 命题和联结词 1.1.1 命题 1.1.2 联结词 1.1.3 合式公式1.2 真假性1.3 范式及其应用,(一) 命题定义,定义1： 凡是可以判断真假的陈述句称为命题。,例：下列句子都是命题吗？,雪是白的。 雪是黑的。 好大的雪啊！ 8大于12。 1+101=110。,例：下列句子都是命题吗？,上海世博会开幕时天晴 21世纪末，人类将住在月球 大于2的偶数可表示成两个素数之和X0 如果x大于3，则x2大于9。,例：下列句子都是命题吗？,8大于12吗？ 请勿吸烟。 姚明很帅。 南京很美。 我正在说谎 。

5、,悖论,命题的真假问题,在数理逻辑的学习中，不能去纠缠各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句,带联结词的命题,今晚我看书。 今晚我玩网络游戏。 今晚我不看书。 今晚我不玩网络游戏。 今晚我不看书， 我玩网络游戏。 今晚我看书，或者我玩网络游戏。,否定,并且,或者,(二) 原子命题和复合命题,原子命题不可剖开或分解为更简单命题的命题，也称为简单命题。本书约定用大写字母表示。复合命题由原子命题利用联结词构成的命题,复合命题例子,（1）雪不是白的（并非雪是白的）（2）今晚我看书或者去看电影。（3）如果天气好，那么我去接你。（4）

6、偶数a是质数，当且仅当a=2（a是常数）。（5） 2是偶数且3也是偶数。 （6）你去了学校，我去了工厂。,其中红字为逻辑联结词，（6）中省略了“且”,(三)命题变元,定义2：如果当P表示任意命题时， P称为命题变元。,字母P表示,命题具体的、特定的命题， 有确定的真值,命题变元任意命题， 没有确定的真值,第一章 命题演算基础,1.1 命题和联结词 1.1.1 命题 1.1.2 联结词 1.1.3 合式公式1.2 真假性1.3 范式及其应用,常用的联结词,否定词 合取词 析取词 蕴含词 等价词 ,P， “非P”,设P是一个命题， P是指如下命题：“P是不对的”,P PT FF T,日常语句中有：

7、不，并非， ,真值表,否定词的例子,例 P：上海是中国的城市。 P：上海不是中国的城市。 例 P：雪是黑色的。 P：雪不是黑色的。,否定联结词使用的原则,将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。,例 P: 这些都是学生。 P：这些不都是学生 这些都不是学生,PQ， “ P合取Q”,设P、Q是两个命题， PQ是指如下命题：“P并且Q”,日常语句中有： 且，与，,合取词的例子,P: 225 Q：雪是白的。 PQ：225并且雪是白的。,P: 今天刮风。 Q：今天下雨。 PQ：今天刮风并且今天下雨。,PQ， “P析取Q”,设P、Q是两个命题，PQ是指如下命题：“

8、P或者Q”,P Q P QT T TT F TF T TF F F,日常语言中有： 或，或者，,析取词的例子,P: 225 Q：雪是白的。 PQ：225或者雪是白的。,P:今天刮风。 Q：今天下雨。 PQ ：今天刮风或者今天下雨。,可兼的“或”,P Q PQT T TT F TF T TF F F,他会英语或法语。,不可兼的“或”,P Q PQ (P Q)(PQ)T T T F T F T TF T T TF F F F,今天晚上我去看电影，或去看球赛。,PQ, “P蕴含Q”,设P、Q是两个命题， PQ是指如下命题：“如果P则Q”,日常语言中有： 如果则, 只要就，,P Q P QT T TT

9、 F FF T TF F T,蕴含词的例子,P：236 Q：(23)+1=6+2 PQ: 如果236，则（23）16+2,P: 天气不好 Q：我去接你 PQ: 如果天气不好，那么我去接你。,注1. 前件为假时，命题为真,如果蕴含前件P是假命题，那么不管Q是什么命题，命题 PQ在逻辑中都被认为是真命题。例： 如果1=2，那太阳从西边升起。,注2. 前件、后件可以毫不相关,在日常语言中“如果则”所联结的句子之间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的。 例： P：235 Q：雪是黑色的 PQ：如果235，则雪是黑色的,蕴含词的例子,设 p：天下雨。 q：

10、我回家。 试表示下列命题：（1）只要天下雨，我就回家。（2）只有天下雨，我才回家。（3）除非天下雨，否则我不回家。（4）仅当天下雨，我才回家。,pq,qp,qp,qp,或pq,例. 将下列命题符号化:（1）只要星期六天气好，我就去公园玩。 （2）只有星期六天气好，我才去公园玩。 （3）除非星期六天气好，否则我不去公园玩。,要特别注意蕴涵联结的应用，要弄清三个问题： pq的逻辑关系 pq的真值 pq的灵活的叙述方法,PQ， “P等价于Q”,设P、Q是两个命题， PQ 是指如下命题：“P当且仅当Q”,P Q P QT T TT F FF T FF F T,日常语言中有：当且仅当，,等价词的例子,P

11、: 224 Q：雪是白色的。 P Q：224当且仅当雪是白色的。,P: 225 Q：雪是黑色的。 P Q：225当且仅当雪是黑色。,等价词的例子,P: 225 Q：雪是白色的。 P Q：225当且仅当雪是白色的。,P: 224 Q：雪是黑色的。 P Q：224当且仅当雪是黑色。,是否复合命题？,例1 Tom和John是兄弟。例2 如果x0， 则 x20。例3 a=0当且仅当 |a|=0。,真值函项的定义,以真假为定义域并以真假为值域的函数,T, F,(T, T), (T,F),(F,T), (F,F),T, F,一元真值函项,二元真值函项,一元联结词的真值表,一个命题变项P，可取“T”和“F”

12、两种值。可定义四个一元真值函项 f0，f1，f2，f3。,永真,恒等,否定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 T F F F F F T F,f4为析取,f2为蕴含,f8为等价,f11为合取,三元联结词共有多少个？,28,第一章 命题演算基础,1.1

13、 命题和联结词 1.1.1 命题 1.1.2 联结词 1.1.3 合式公式 1.2 真假性1.3 范式及其应用,合式公式(Well formed formulae),合式公式为如下定义的式子，简称为公式： 任何命题变元均是公式； 如果P为公式，则P为公式； 如果P，Q为公式，则 PQ, PQ, PQ, PQ 为公式；当且仅当经过有限次使用、所组成的符号串才是公式，否则不为公式 。,n 元公式,若公式中有n个不同的命题变元，就说为n 元公式。,3元公式的例子： （PQ）R）（ PQ）,（PQR）（ PQ）,优先级约定,非 比其它联结词有更高的优先级 括号（）内的运算优先,本书未约定 和比有更高的

14、优先级 是右结合的,命题符号化,步骤：分析出简单命题，符号化用联结词联结简单命题,提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词。,例4(p5)已知三个命题： P：今晚我在家上网；Q：今晚我去球场看足球比赛；R：今晚我在家上网或去球场看足球比赛。试问PQ和R是否表达同一命题？请用真值表说明之。,R=(PQ)(PQ),不可兼 或,例 将下述命题符号化，并指出真值: （1）豆沙包是由面粉和红小豆做成的。 （2）2是质数或合数。 （3）吃一堑，长一智。 （4）n是偶数当且仅当它能被3整除。 （n为一固定的自然数）,例 令 p：北京比天津人口多。 q：2+24。 r：乌鸦是白色的

15、。 求下列公式的真值：(1) (qr)(pr) (2) (pr) (pr),第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式1.3 范式及其应用,完全解释、部分解释,定义：设n元公式中所有的不同的命题变元为 P1, ,Pn 如果对每个命题变元均给予一个确定的值，则称对公式给了一个完全解释； 如果仅对部分变元给予确定的值， 则称对公式给了一个部分解释。,n元公式有2n个完全解释。,例 考察公式 =（PQ） R,成真解释与成假解释,定义：对于任何公式，凡使得取真值的解释，不管是完全解释还是部分

16、解释，均称为的成真解释。定义：对于任何公式，凡使得取假值的解释，不管是完全解释还是部分解释，均称为的成假解释。,例 考察公式 =（PQ） R,永真公式与永假公式,定义：如果一个公式的所有完全解释均为成真解释，则称该公式为永真公式或称为重言式。定义: 如果一个公式的所有完全解释均为成假解释，则称该公式为永假公式或称为予盾式。,例 P P 永假公式 P P 永真公式 P P 永真公式,可满足公式与非永真公式,定义：如果一个公式存在成真解释， 则称该公式为可满足公式； 如果一个公式存在成假解释， 则称该公式为非永真公式。,例 PQ 可满足公式，非永真公式 PQ 可满足公式，非永真公式,第一章 命题演

17、算基础,1.1 命题和联结词 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式1.3 范式及其应用,逻辑等价,定义：给定两个公式和， 设P1，P2，Pn为和的所有命题变元， 那么和有2n个解释。 如果对每个解释，和永取相同的真假值， 则称和是逻辑等价的，记为=。, ,例 问： P P = P?,从真值表，可以看出： P P = P,考察真值表如下,八组重要的等价公式,双重否定律 P=P结合律 （P Q） R = P （Q R） （P Q） R = P （Q R）分配律 P （Q R）=（P Q ）（P R） P （QR）=（P Q

18、）（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 P = P F P = P,?,八组重要的等价公式,吸收律 P （PQ）= P P （P Q）= P,例 判断下列公式的类

19、型 q(pq) p),解: 考察真值表 所以，它是永真的。,例 判断下列公式的类型 q(pq) p),解: q(pq) p) =q(pq) ) p =(q p )(pq) ) =T 所以，它是永真的。,例 判断下列公式的类型 (pq) p,解: 考察真值表 所以，它是可满足的。,例 判断下列公式的类型 (pq) p,解: (pq) p =(pq) p =p 所以，它是可满足的。,例 判断下列公式的类型 (pp) (qq) r),解: (pp) (qq) r) = T (qq) r) = (qq) r =Fr =F 所以，它是永假的。,成真解释和成假解释的求解方法,（1）否定深入：即把否定词一直

20、深入至命题变元上；（2）部分解释：选定某个出现次数最多的变元对它作真或假的两种解释从而得公式；（3）化简；（4）依次类推，直至产生公式的所有解释。,例(p7) 试判定公式 (PQ)(QP)R) 的永真性和可满足性。,解1：否定深入 原式 = (PQ)(QP)R) 对 P=T 进行解释并化简， 结果见教材。,解2：否定深入 原式 = (PQ)(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) ； 公式存在成假解

21、释(P，Q，R)=(F，T，T)。 故公式可满足但非永真。,解3：考察 (PQ)(QP)R),所以，公式存在成真解释： (T,T,*), (T,F,F), (F,T,F), (F,F,T); 公式存在成假解释： (T,F,T), (F,T,T), (F,F,F)。故公式可满足但非永真。,例 试求下列公式的成真解释和成假解释 （PQ）（Q（RP）,解:当P=T时, 原式= (TQ)(Q(RT) =Q(Q(R)=QR 当P=F时, 原式= (FQ)(Q(RF) = T(QF)=Q由上可知: 公式不是永真公式,是可满足的. 成真解释为(P,Q,R)=(T,F,F),(F,T,*), 成假解释为(P,

22、Q,R)=(T,T,T),(T,F,T),(T,T,F),(F,F*).,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式1.3 范式及其应用,联结词的完备集,定义 设S是联结词的集合，如果 对任何命题演算公式均可以由S中的联结词表示出来的公式与之等价， 则说S是联结词的完备集。,由联结词的定义知，联结词集合 ，是完备的。,定理1 联结词的集合，是完备的。,思路: 去蕴含词与等价词 PQ =P Q PQ =（P Q） （P Q）,定理 联结词的集合， 是完备的。,思路: 在去蕴含词与等价词

23、的基础上, PQ =P Q PQ =（P Q） （P Q） 去析取词： P Q = （P Q）,定理 联结词的集合， 是完备的。,思路: 在去蕴含词与等价词的基础上, PQ =P Q PQ =（P Q） （P Q） 去合取词 P Q = （P Q）,定理 联结词的集合， 是完备的。,思路: 去等价词、析取词、合取词： PQ =（ PQ ） （ PQ ） P Q= PQ PQ = （PQ）=（P Q）,与非: PQ = （P Q）,P Q PQ T T FT F TF T TF F T,定理2(p8) 联结词的集合是完备的。,思路： 去否定词与合取词： P = P P P Q= （PQ）,或非：

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

25、然矛盾。 故联结词集合不完备。,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.2.1 解释 1.2.2 等价公式 1.2.3 联结词的完备集 1.2.4 对偶式和内否式 1.3 范式及其应用,对偶式的定义,定义：将任何一个不含蕴含词和等价词的命题演算公式中的 换为 ， 换为 后所得的公式称为的对偶式， 记为*。,例 已知公式 = P （QR）, 求对偶式*、 （*）* 。,解： = P（QR） *= P （QR） (*)*= P （QR）,内否式的定义,定义：将任何命题演算公式中的所有 肯定形式换为否定形式、 否定形式换为肯定形式 后所得的公式称为的内否式， 记为 。,例 已

26、知公式 = P （QR）, 求内否式 、 （ ） 。,解： = P（QR） = P（Q R）（） = P （Q R）,对偶式和内否式的性质,性质1 （*）* = （） = ,对偶式和内否式的否定,定理1(p9) （A*）=（A）* （A）=（A）,定理2(p9) A =A*,证明：思路是对公式A中出现的联结词的个数n进行归纳证明。 当n=0时， A中无联结词，便有 A=P， 从而有 A=P， A*=P ， 所以 A* = P= A， 即定理成立。,证明(续): 归纳假设：设nk时定理成立。 考察n=k+11，A中至少有一个联结词， 可分为下面三种情形： A=A1， A=A1A2， A=A1A2

27、 其中A1，A2中的联结词个数 k 。 依归纳假设 A1= A1* ， A2= A2* 。 对于上述三种情形，可以分别证明结论成立： A =A*。 由数学归纳法知，定理得证。,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.3 范式及其应用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的应用,合取式、析取式,定义1 命题变元、或者命题变元的否定、或由它们利用合取词组成的合式公式称为合取式。定义2 命题变元、或者命题变元的否定、或由它们利用析取词组成的合式公式称为析取式。例 显然， P，P，PQ，PQR 均为合取式； P，P，PQ，PQR 均为析取式。,(一) 解释与合

28、取式、析取式之间的关系,定理1 任给一个成真解释有且仅有一个合取式与之对应； 任给一个成假解释有且仅有一个析取式与之对应。 反之亦然。,例 成真解释(P，Q，R)= (T,F,T) 成假解释(P，Q，R)= (F,F,T),合取式PQR,析取式PQR,析取范式、合取范式,定义3 形如A1 A2 An的公式称为析取范式， 其中Ai(i=1,2,n)为合取式。定义4 形如A1 A2 An的公式称为合取范式， 其中Ai(i=1,2,n)为析取式。例 P，P，PQ，PQ ，(PQ)(SR) 均为析取范式。 P，P，PQ，PQ ， (PQ)(SR)均为合取范式。,例: 考察公式 =PQ的析取范式,有两个

29、成真解释： (T, T), (F, F), 分别对应于两个合取式为 PQ, PQ于是，有 = (PQ) (PQ),例: 考察公式 =PQ的合取范式,成假解释 (T, F), (F, T), 对应析取式为 PQ, PQ于是，有： = (PQ) (PQ),定理2 任何命题演算公式均可以化为合取范式，也可以化为析取范式。,证明： (1)设公式为永真公式 =PP (2)设公式为永假公式 =PP,证明(3)： 设公式既非永真又非永假。设公式的成真解释为1，2，n， 成假解释为1，2，t。根据解释和范式的关系知：对应于成真解释1，2，n的合取式为1，2，n对应于成假解释1，2，t的析取式为1，2，t而公式

30、 12n的成真解释为1，2，n；公式12t的成假解释为1，2，t。根据两个公式逻辑等价的定义知 =12n =12t故公式既可表示为析取范式又可表示为合取范式。,(二) 析取范式和合取范式的求解方法,等价变换法解释法,等价变换法,(1)去蕴含词与等价词： PQ =P Q PQ =（P Q） （P Q）(2)否定深入： (P Q)= PQ (P Q)= PQ， P = P(3)重复使用分配律： P (QR)=(P Q )(P R) P (QR)=(P Q )(P R),解释法,(1) 求所有成真解释、成假解释；(2) 写出成真解释对应的合取式、 成假解释对应的析取式；(3) 把所有的合取式用析取词

31、联结起来就构成析取范式，把所有的析取式用合取词联结起来就构成合取范式。,例 求公式的范式 (PQ)(RQ)P),解：原式=(PQ)(RQ)P) =(PQ)(RQ)P) =(PQ)(PR)(PQ) =(PQ)(PR) 析取范式 = P(QR) 合取范式,解：P=T时, 原式=(TQ)(RQ)T) =QR 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),于是析取范式为: (PQR)(P Q R)(P Q R) 合取

32、范式为： (P QR)P,范式不唯一性,例 求公式的范式 (PQ)(RQ)P),解1： 原式=(PQ)(PR) 析取范式 = P(QR) 合取范式解2: 析取范式为: (PQR)(P Q R)(P Q R) 合取范式为： (P QR)P,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.3 范式及其应用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的应用,(一) 主析取范式,定义1 对于n个命题变元P1，P2，Pn，公式 Q1Q2Qn 称为极小项，其中Qi=Pi或Pi(i=1，n)。,例 由两个命题变元P，Q组成的极小项有四个，它们分别为：PQ PQPQ PQ,三个命题

33、变元P、Q和R可构造8个极小项,把命题变元的否定形式看成0，肯定形式看成1，则每个极小项对应一个二进制数，也对应一个十进制数。它们对应如下： PQR 与000 或0对应，简记为 m0 PQR 与001 或1对应，简记为 m1 PQR 与010 或2对应，简记为 m2 PQR 与011 或3对应，简记为 m3 PQR 与100 或4对应，简记为 m4 PQR 与101 或5对应，简记为 m5 PQR 与110 或6对应，简记为 m6 PQR 与111 或7对应，简记为 m7,n个命题变元组成的极小项有2n个,公式的每一个完全成真解释对应一个极小项公式的所有完全成真解释对应极小项的析取,主析取范式

34、,定义2 仅有极小项构成的析取范式称为主析取范式。定理1 任何一个合式公式，均有惟一的一个主析取范式与该合式公式等价。,主析取范式就是公式的所有完全成真解释对应极小项的析取。,求主析取范式的两种方法,(1)解释法: 根据公式的所有完全成真解释，求出与这些成真解释对应的合取式，所有合取式的析取就为公式的主析取范式。(2)等价变换法: 将析取范式中的每一个合取式用AA填满命题变元，然后用等价公式进行变换，消去相同部分，即得公式的主析取范式。,例 求公式的主析取范式 (PQ)(RQ)P),解：原式=(PQ)(RQ)P) =(PQ)(RQ)P) =(PQ)(PR)(PQ) =(PQ)(PR) 析取范式

35、 =(PQ(R R)(P (QQ)R) = (PQR) (PQ R)(P QR) =101100110=456,解：P=T时, 原式=(TQ)(RQ)T) =QR P=F时, 原式=(FQ)(RQ)F) =F 所以有: 成真解释为：(P,Q,R)=(T,F,T), (T,F,F), (T,T,F),例 求公式的主析取范式 (PQ)(RQ)P),于是主析取范式为: (PQR)(P Q R)(P Q R) =101100110=456,(二) 主合取范式,定义3 对于n个命变元P1，P2，Pn，公式 Q1Q2Qn 称为极大项，其中Qi=Pi或Pi(i=1，n)。,例 由两个命题变元P，Q组成的极大

36、项有四个，它们分别为： PQ PQ PQ PQ,三个命题变元P、Q和R可构造8个极大项,把命题变元的否定形式看成1，肯定形式看成0，则每个极大项对应一个二进制数，也对应一个十进制数。它们对应如下： PQR 与000 或0对应，简记为 M0 PQR 与001 或1对应，简记为 M1 PQR 与010 或2对应，简记为 M2 PQR 与011 或3对应，简记为 M3 PQR 与100 或4对应，简记为 M4 PQR 与101 或5对应，简记为 M5 PQR 与110 或6对应，简记为 M6 PQR与111 或7对应，简记为 M7,n个命题变元组成的极大项有2n个,公式的每一个完全成假解释对应一个极

37、大项公式的所有完全成假解释对应极大项的合取,主合取范式,定义4 仅有极大项构成的合取范式称为主合取范式。 定理2 任何一个合式公式，均有惟一的一个主合取范式与该合式公式等价。,主合取范式就是公式的所有完全成假解释对应的极大项的合取。,求主合取范式的两种方法,(1)解释法 根据公式的所有完全成假解释，求出与这些成假解释对应的析取式，所有析取式的合取就为公式的主合取范式。(2)等价变换法 将合取范式中的每一个析取式用AA填满命题变元，然后用等价公式进行变换，消去相同部份，即得公式的主合取范式。,例 求公式的主合取范式 (PQ)(RQ)P),解：原式=(PQ)(RQ)P) =(PQ)(RQ)P) =

38、(PQ)(PR)(PQ) =(PQ)(PR) 析取范式 = P(QR) 合取范式 =(P(QQ)(RR)(QR) (PP) =(PQR)(PQR) (PQR) (PQR) (PQR) =000001010011111=01237,解：P=T时, 原式=(TQ)(RQ)T) =QR P=F时, 原式=(FQ)(RQ)F) =F 所以有: 成假解释为：(P,Q,R)=(T,T,T), (F, ),例 求公式的主合取范式 (PQ)(RQ)P),于是主合取范式= (PQR) (PQR) (PQR) (PQR)(PQR) =111011010001000=01237,(F,TT),(F,T,F),(F,

39、F,T),(F,F,F),例 试求 =(PR)(P (Q R) 的主析取范式和主合取范式,解: =(PR) (P(QR)(P(QR)（去蕴涵词、等价词） =(PR) (PQR) (PQ) (PR)（化简） =(PR) (PQR) (PQ) (PR)（去蕴涵词） = (PR) (PQR)(PQ) =(110 100) 001 (111 110)=(1,4,6,7),解(续): 已经得到主析取范式如下: = (PQR)(PQ)(PR),=(PP)(PQ)(QP) (QQ)(PR)(QR)(PR) =(PQ)(QP)(PR)(QR) (PR) =(T(PQR) (QP)(PQR) )(PR) T)

40、(PQR) T) =101 (010 011) (010 000) 000 =(0,2,3,5),例 试求 =(PR)(P (Q R) 的主析取范式和主合取范式,主合取范式和主析取范式的关系,(1)紧密相关性： 一个公式的主合取范式和主析取范式是紧密相关的。 如例： = (PR)(P (Q R) = = (PR)(P (Q R) =(2) 惟一性: 任何一个命题演算公式，具有惟一的主合取范式和主析取范式，因此如果两个公式具有相同的主析取范式或主合取范式，则称两公式逻辑等价。,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.3 范式及其应用 1.3.1 范式 1.3.2 主范式

41、1.3.3 范式的应用,苹果考题：宝藏在哪里?,你面前有两扇门，其中一扇门内藏着宝藏，但如果你不小心闯入另一扇门，只能痛苦地慢慢死掉在这两扇门前面，有两个人，这两个人都知道哪扇门后有宝藏，哪扇门擅闯者死，而这两个人呢，一个人只说真话，一个人只说假话。游戏规则是，你只能问这两个人每人一个问题。,问其中一个人：“如果我问另一个人，他会跟我说甲乙两扇中哪扇门后是宝藏？”,令 P：被问人说真话； Q：被问人回答是“甲”； R：另一人回答是“甲” ； S：甲门内藏着宝藏。根据题意可得真值表如图所示。根据真值表知析取范式为： S=(PQ)(PQ) =(PP)Q =Q因此被问人回答是“甲”时，此门不是藏着宝

42、藏。,T T T (谎) F,T F F (谎) T,F T F (真) F,F F T (真) T,结论: 否定被问人的回答!,趣味离散数学一、巧猜围棋子,甲手里有一个围棋子，要乙来猜棋子的颜色是白的还是黑的。条件是：只允许乙问一个只能回答“是”或“否”的问题，但甲可以说真话，也可以说假话，问乙可以向甲提出一个什么问题，然后从甲回答“是”或“否”中就能够判断出甲手中棋子的颜色？,？,例 从A,B,C三人中挑选12人去完成一个任务。选派时要满足以下条件： （）若A去，则C同去。 （）若B去，则C不能去。 （）若C不去，则A或B可以去。 问应如何选派他们去？,解: 选派条件可以表述为: (AC)(B C)( C(AB) = (AC)(B C)(ABC) = (AB) (AC) (BC)(ABC) = (ABC) (ABC) (ABC) 可知，选派方案有3种：（1）C去，而A,B都不去。 （2）B去，而A,C都不去。 （3）A,C去，而B不去。,第一章 命题演算基础,1.1 命题和联结词 1.2 真假性 1.3 范式及其应用 1.3.1 范式 1.3.2 主范式 1.3.3 范式的应用 第二章 命题演算的推理理论,