[论文]离散证明题集锦

《[论文]离散证明题集锦》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散证明题集锦一.命题逻辑例：给出1(PAQW-iPV-iQ)的真值表PQ-1(PAQ)^>(-1PV-1Q)00101111011011101010101111011000骤步②①③①②①般说来，11个命题变元组成的命题公式共有2n种真值指派。•定理1：任何两个重言式的合取或析取，仍然是重言式。证明：设A、B为两个重言式，则AAB和AVB的真值分别等于TAT^ITVTo•定理2：对一个重言式的同一分量都用任何一个命题公式置换,所得命题公式仍为一个重言式。(即代入规则)证明：由于重言式的真值与分量的真值指派无关，故对同一分量以任何一个命题公式置换后，重言式的真值不变。•定理3：设A、

2、B是两个命题公式，AoB当且仅当A・B是一个重言式。（前面已证）证明：若AoB,贝IJ对于A、B所包含的分量的任意指派，A、B均取相同的真值，即A-B是一个重言式；若A-B是一个重言式，即对于分量的任意指派，A、B均取相同的真值，即AoB•定理1：设A1是命题公式A的子公式，若AloBl,则若将A中的Al用Bl来替换,得到公式B，则B与A等价,即AoB.（替换规则）。证明：因为对变元的任一组指派，A1与B1真值相同，故以B1取代Al后，公式〕B与公式A相对于变元的任一指派的真值也必相同，所以AoB。•证明下列命题公式(可以利用基本等价式)Q->(PV(P/Q))oQ->P(PAQ)

3、V(PAnQ)oP(PfQ)f(QVR)oPVQVRPA-iQVQ^PVQ解：1•原式<=>Q->(PVP)A(PVQ)<=>Q->PA(PVQ)oQ-P2•原式0((P/Q)VP)A((PAQ)ViQ)o(PVP)A(PVQ)A(PVnQ)A(QVnQ)oPA(PVQ)A(PVqQ)oP/PoP3•原式or(-]PVQ)V(QVR)o(PAiQ)V(QVR)<=>(PVQVR)A(QVnQVR)<^PVQVR(零率)4•原式o(PA-iQ)VQo(PVQ)A(-iQVQ)<=>PVQ(运算次序优先级：-i,A,V,-,・)例：求证:(PfQ)Vn(PfQ)为永真式。解：原式o(

4、-1PVQ)V(PAnQ)0(=PVQVP)A(qPVQViQ)oT例：求证iQA(P->Q)=>nP证法1:前件真推导后件真证法2：后件假推导前件假证法3：定义定理：设P.Q为任意两个命题公式，PoQ的充分必要条件是P=>Q且Q=>Po证明：若PoQ,则PoQ为重言式，即PfQ和Q->P是重言式；若有PnQ且QnP,则P-Q和Q-P是重言式，即PoQ为重言式例已知A是B的充分条件，B是C的必要条件，C是D的必要条件，D是B的必要条件，问：(1)A是D的什么条件?⑵B是D的什么条件?解已知A=>B,C=>B,DdC，B=>D,故有(1)A=>B，B=>D，所以A=>D,即A是D的充分

5、条件(2)D=>C,C=>B,所以D=>B,又因为B=>D，所以BoD，即B是D的充要条件。定理：如果AoB,则A*oB*。证明：设P1,P2,…,Pn是出现在命题公式A、B中的原子变元，因为AoB,即：A(Pl，P2，・・・,Pn)・B(Pl,P2"・・,Pn)是一个重言式。故有:A(-1PinP2,…,1Pn)oB(-iPinP2,…,1Pn)是一个重言式。即A(nPinP2,...,nPn)oB(-

6、PinP2,…门Pn)1A*oiB*,艮卩A*oB*例判断下面各推理是否正确.(D如果天气凉快，小王就不去游泳•天气凉快，所以小王没去游泳.(2)如果我上街，我一定去新华书店•我没

7、上街•所以我没去新华书店.解：解上述类型的推理问题，应先将命题符号化，然后写出前提、结论和推理的形式结构，最后进行判断.(1)P：天气凉快；Q：小王去游泳.前提：P—-1Q，P.结论：—iQ.推理的形式结构为((PrQ)AP)f「Q・(*)判断(*)是否为重言式.①真值表法真值表的最后一列全为因而(*)是重言式•所以推理正确.①等价演算法(P->-.Q)AP)->-iQol.②主析取范式法((P-iQ)AP)--iQomOVmlVm2Vm3由②，③同样能判断推理正确.(1)P：我上街；Q：我去新华书店.前提：PfQ，「P・结论：-iQ.推理的形式结构为((P-Q)A-iP)-「Q・(

8、杯)((P-Q)A「PL「Q<=>m0Vm2Vm3可见(**)不是重言式，所以推理不正确.还可用其他方法判断之.例证明下列前提是不相容的。1.若A因病缺了许多课，那么他中学考试失败。2.若A中学考试失败，则他没有知识。3.若A读了许多书，则他有知识。1.A因病缺了许多课，而且读了许多书。证明符号化题目：P：因病缺了许多课，Q：中学考试失败，R：有知识，S:读了许多书。问题要证明前提P—Q,Q「tR,StR,PAS是不相容的。下面我们用另外一种形式的格式证明