资源预览内容
第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
第9页 / 共29页
第10页 / 共29页
亲,该文档总共29页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
离散证明题集锦一命题逻辑例:给出(PAQ)(n PVq Q)的真值表PQn (PAQ)(-n PViQ)00101111011011101010101111011000步骤一般说来,n个命题变元组成的命题公式共有2n种真值指派。定理1:任何两个重言式的合取或析取,仍然是重言式。证明:设A、B为两个重言式,则AAB和AVB的真值分别等于 TAT 和 TVT。 定理 2:对一个重言式的同一分量都用任何一个命题公式置换, 所得命题公式仍为一个重言式。(即代入规则)证明:由于重言式的真值与分量的真值指派无关,故对同一分量以 任何一个命题公式置换后,重言式的真值不变。定理3:设A、B是两个命题公式,AoB当且仅当AB是一个重言式。(前面已证)证明:若AoB,则对于A、B所包含的分量的任意指派,A、B 均取相同的真值,即AB是一个重言式;若AoB是一个重言式, 即对于分量的任意指派, A、 B 均取相同的真值,即 AoB定理1:设A1是命题公式A的子公式,若A1oB1,则若将A 中的A1用B1来替换,得到公式B,则B与A等价,即AoB(替 换规则)。证明:因为对变元的任一组指派,A1与B1真值相同,故以B1 取代 A1 后,公式 B 与公式 A 相对于变元的任一指派的真值也必相 同,所以 AoB。 证明下列命题公式(可以利用基本等价式)Qf(PV(PAQ)oQfP(PAQ)V(PAn Q)oP(PQ)(QVR)oPVQVRPA-i QVQoPVQ解:1原式 oQf(PVP) A(PVQ) oQfPA(PVQ) oQP2原式 o (PAQ) VP) A(PAQ) V- Q) o (PVP) A(PVQ) A (PV- Q) A(QV- Q)oPA(PVQ) A(PV- Q) oPAPoP3原式PVQ)V(QVR) (PAn Q) V(QVR) (PVQVR) A(QVn QVR) oPVQVR (零率)4原式 o ( PAn Q)VQo (PVQ)A(i QVQ) oPVQ (运算次 序优先级:n,A,V,f, o)例:求证:(P -Q) V n (P -Q)为永真式。解:原式 o (n PVQ)V(PAn Q)o(n PVQVP) A(n PVQ Vn Q) oT例:求证n QA(P-QQn P证法 1:前件真推导后件真证法 2:后件假推导前件假证法 3:定义定理:设P、Q为任意两个命题公式,PoQ的充分必要条件是PnQ 且 QnP。证明:若PoQ,则PoQ为重言式,即P-Q和Q-P是重言式; 若有PnQ且QnP,则P-Q和Q-P是重言式,即PoQ为重言 式例 已知A是B的充分条件,B是C的必要条件,C是D的必要条件, D是B的必要条件,问:(1) A是D的什么条件?(2) B是D的什么条件?解 已知 AnB, CnB, DnC, BnD,故有(1) AnB, BnD,所以AnD,即A是D的充分条件DnC, CnB,所以DnB,又因为BnD,所以BoD,即B是D 的充要条件。定理:如果AoB,则A* o B*。证明:设P1,P2,Pn是出现在命公式A、B中的原子变元,因为AoB, 即: A(P1,P2,Pn)B(P1,P2,丹)是一个重言式。故有:A(n P1门P2,门Pn)oB(P1门P2,门Pn)是一个重言式。即A(n P1门 P2,门 Pn)oB(q P1门 P2,门 Pn)n A* o q B*,即 A* o B*例 判断下面各推理是否正确.(1) 如果天气凉快,小王就不去游泳.天气凉快,所以小王没去游泳.(2) 如果我上街,我一定去新华书店.我没上街.所以我没去新华书店. 解: 解上述类型的推理问题,应先将命题符号化,然后写出前提、结论 和推理的形式结构,最后进行判断.(1)P:天气凉快;Q:小王去游泳.前提: P-Q, P.结论:Q推理的形式结构为(P-Q)AP)-Q.(*)判断(*)是否为重言式. 真值表法真值表的最后一列全为 1,因而(*)是重言式.所以推理正确. 等价演算法(P-Q)AP)fQ o1 主析取范式法(P- Q)AP)- Qo m0Vm1Vm2Vm3由,同样能判断推理正确.(2)P: 我上街;Q:我去新华书店.前提: P-Q,P.结论: Q.推理的形式结构为(P-Q)A P) - Q.(*)(P-Q)A P)- Qom0V m2V m3可见(*)不是重言式,所以推理不正确.还可用其他方法判断之.例 证明下列前提是不相容的。1. 若A因病缺了许多课,那么他中学考试失败。2. 若A中学考试失败,则他没有知识。3. 若A读了许多书,则他有知识。4. A因病缺了许多课,而且读了许多书。证明 符号化题目:P: 因病缺了许多课,Q: 中学考试失败,R: 有知识,S: 读了许多书。问题要证明前提PtQ, QtR, StR, PAS 是不相容的。下面我们用另外一种形式的格式证明(即后面讲的 构造证明 的格式):编号公式依据(1)PASP(2)P(1); I1(3)S(1); I2(4)PtQP(5)Q(2),(4); I8(6)StRP(7)R(3),(6); I8(8)QtR(9) R (5),(8); I9(10) R 心R(7),(9)例 张三说李四在说谎, 李四说王五在说谎, 王五说张三、李四都在说 谎。问谁说真话, 谁说假话?解 设A:张三说真话;B:李四说真话;C:王五说真话 依题 AB, BoC, CiA / B。(A 分 iB)/(B iC)/(C 分 iA/iB)o (AitB)/(iBtA)/(BitC)/(iCt B) /(CtGA/iB)/ (A / iB)tC)o (iA/B/iC)/(AVB)/C) A(iAAiBAiC)V(AAiC)V (B/ C)o AA BA C即: 李四说真话, 张三和王五说假话。例193:求证:S是前提W, W-n Q门Q-R和R-S的有 效结论。 证明:1(1) W -iQP2 iQ-R P1,2(3) W-RT,(1)(2)I113 (4) WP1,2,3 (5) RT,(3)(4)I84 R - SP1,2,3,4 (7) ST,(5)(6)I8(这部分的 T,I8 等是另外一本书的内容,所以不用管,只要会推 就行)例 前提: 如果马会飞或羊吃草 , 则母鸡就会是飞鸟; 如果母鸡是飞 鸟, 那么烤熟的鸭子还会跑; 烤熟的鸭子不会跑。结论: 羊不吃草。 解 符号化上述语句, P: 马会飞, Q: 羊吃草, R: 母鸡是飞鸟, S: 烤熟 的鸭子还会跑,S:烤熟的鸭子不会跑,Q:羊不吃草。前提集合PV QtR, RtS,S,结论 C :Q。(1)SP(2)RtSP(3)R(1), (2), I9(4)PVQtRP(5)(PVQ)(3), (4), I9(6)(5), E5(7)Q(6), I 2例 如果我的考试通过, 那么我很快乐。如果我快乐, 那么阳光很好。 现在是凌晨一点, 天很暖和。试给出结论。解 设 P: 我的考试通过, Q: 我很快乐, R: 阳光很好, S: 天很暖和。 把 凌晨一点 理解为阳光不好。前提为:PtQ,(QR, R ASo编号公式依据(1)PtQP(2)QtRP(3)PtR(1), (2);I11(4)rasP(5)-r(4);I1(6)p(3), (5);I9结论:P,我的考试没通过。例前提:PVQ,PtR, RtS;结论:StQ。证明 (1)SCP(2)R-tSP(3)S-tR(2), E(4)-R(1), (3), I(5)-PtRP(6)-RtP(5), E(7)P(4), (6), IP(9) pQ,E(10) -Q(7), (9), I(11) S-tQ(1), (10), CP(CP 规则这部分因为好像多了一个条件,所以用起来可能会比较简 单)例195:证明Rf S可从前提Pf (Qf S),RVP和Q推出。证明:(CP规则,因为结论RfS为条件式)1(1) 1 RVP P2RP(附加前提)1,2(3) P T,(1)(2)I103(4) Pf(QfS)P1,2,3 (5) QfST, (3,4)I84(6) Q P1,2,3,4 (7) ST,(5)(6)I81,3,4(8) RfSCP,(2)(7)例194:证明从前提PQ,n (QVR)可演绎出P证明: (反证法)1(1) P P (附加前提)2 P-QP1,2(3) QT,(1)(2)I83 1 (QVR) P3 i QAnRT, (4)E53(6) 1 QT, (5)I1 1,2,3 (7) QA1 Q T,(3)(6)例 如果春暖花开, 燕子就会飞回北方。如果燕子飞回北方, 则冰雪 融化。所以, 如果冰雪没有融化, 则没有春暖花开。 证明这些语句 构成一个正确的推理。证:令P:春暖花开。Q:燕子飞回北方。R: 冰雪融化。则上述问题转化成证明:PQ, QR-iRIP利用CP规则,将iR作为附加前提,推导iP,从而推导出iRiP。编号公式依据(1)QtRP(2)iRP(附加前提)(3)iQ(1),(2); I9(4)PtQ前提(5)iP(3),(4); I9课堂练习:1. 用基本等价公式的转换方法验证下列推断是否有效。(1) P t Q, RAS, -Q n RAS;(2) -P t Q, Q t R, R t P n PVQVR;(3) P, Q t R, RVS n Q t S;(4) -QAR, RAP, Qn PV-Q。2. 用推理规则证明下述论断的正确性。(1) P, Pt (Qt (RAS)n Qt S;(2) Pt (Qt R), Rt (Qt S)n Pt (Qt S);(3) Pt (Qt R)n (Qt (Rt S)t (Pt (Qt S);(4) -(P t Q) t -(RVS), (Qt P)V-R, R n P分 Q。3. A, B, C, D四人中要派两个人出差,按下述三个条件有几种派法?如何派?若A去,则C和D中要去一人。(2)B和
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号