《离散证明题集锦》由会员分享，可在线阅读，更多相关《离散证明题集锦（29页珍藏版）》请在金锄头文库上搜索。
1、离散证明题集锦一命题逻辑例：给出(PAQ)(n PVq Q)的真值表PQn (PAQ)(-n PViQ)00101111011011101010101111011000步骤一般说来，n个命题变元组成的命题公式共有2n种真值指派。定理1：任何两个重言式的合取或析取，仍然是重言式。证明：设A、B为两个重言式，则AAB和AVB的真值分别等于 TAT 和 TVT。 定理 2：对一个重言式的同一分量都用任何一个命题公式置换， 所得命题公式仍为一个重言式。(即代入规则)证明：由于重言式的真值与分量的真值指派无关，故对同一分量以 任何一个命题公式置换后，重言式的真值不变。定理3：设A、B是两个命题公式，Ao
2、B当且仅当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
3、(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
4、(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,
5、所以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) 如果我上街,我一定去新华书店.我没上
6、街.所以我没去新华书店. 解: 解上述类型的推理问题,应先将命题符号化,然后写出前提、结论 和推理的形式结构,最后进行判断.(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)- Qo
7、m0V 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); I
8、8(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即: 李四说
9、真话, 张三和王五说假话。例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: 烤熟
10、的鸭子还会跑,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)
11、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 P2R
12、P(附加前提)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)例 如果春暖花开, 燕子就会飞回北方。如果燕子飞回北方, 则冰雪 融化。所以, 如果冰雪
13、没有融化, 则没有春暖花开。 证明这些语句 构成一个正确的推理。证:令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和
