资源描述：
《离散证明题集锦》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、离散证明题集锦一．命题逻辑例：给出┐(P∧Q)↔(┐P∨┐Q)的真值表PQ┐(P∧Q)↔(┐P∨┐Q)00101111011011101010101111011000步骤②①③①②①解：一般说来，n个命题变元组成的命题公式共有2n种真值指派。l定理1：任何两个重言式的合取或析取，仍然是重言式。证明：设A、B为两个重言式，则A∧B和A∨B的真值分别等于T∧T和T∨T。l定理2：对一个重言式的同一分量都用任何一个命题公式置换，所得命题公式仍为一个重言式。（即代入规则）证明：由于重言式的真值与分量的真值指派无关，故对同一分量
2、以任何一个命题公式置换后，重言式的真值不变。l定理3：设A、B是两个命题公式，AÛB当且仅当A↔B是一个重言式。（前面已证）证明：若AÛB，则对于A、B所包含的分量的任意指派，A、B均取相同的真值，即A↔B是一个重言式；若A↔B是一个重言式，即对于分量的任意指派，A、B均取相同的真值，即AÛBl定理1：设A1是命题公式A的子公式，若A1ÛB1，则若将A中的A1用B1来替换，得到公式B，则B与A等价，即AÛB.(替换规则)。证明：因为对变元的任一组指派，A1与B1真值相同，故以B1取代A1后，公式B与公式A相对于变元的任
3、一指派的真值也必相同，所以AÛB。l证明下列命题公式(可以利用基本等价式)Q→(P∨(P∧Q))ÛQ→P(P∧Q)∨(P∧┐Q)ÛP(P→Q)→(Q∨R)ÛP∨Q∨RP∧┐Q∨QÛP∨Q解：1.原式ÛQ→(P∨P)∧(P∨Q)ÛQ→P∧(P∨Q)ÛQ→P2.原式Û(（P∧Q）∨P)∧((P∧Q)∨┐Q)Û(P∨P)∧(P∨Q)∧(P∨┐Q)∧(Q∨┐Q)ÛP∧(P∨Q)∧(P∨┐Q)ÛP∧PÛP3.原式Û┐（┐P∨Q）∨(Q∨R)Û(P∧┐Q)∨(Q∨R)Û(P∨Q∨R)∧(Q∨┐Q∨R)ÛP∨Q∨R（零率）4.原式Û
4、（P∧┐Q）∨QÛ（P∨Q）∧(┐Q∨Q)ÛP∨Q（运算次序优先级：┐，∧，∨，→，↔）例:求证:(P→Q)∨┐(P→Q)为永真式。解：原式Û（┐P∨Q）∨（P∧┐Q）Û(┐P∨Q∨P)∧（┐P∨Q∨┐Q）ÛT例：求证┐Q∧(P→Q)Þ┐P证法1：前件真推导后件真证法2：后件假推导前件假证法3：定义定理：设P、Q为任意两个命题公式，PÛQ的充分必要条件是PÞQ且QÞP。证明：若PÛQ，则P↔Q为重言式，即P→Q和Q→P是重言式；若有PÞQ且QÞP，则P→Q和Q→P是重言式，即P↔Q为重言式例已知A是B的充分条件,B是C
5、的必要条件，C是D的必要条件,D是B的必要条件,问：(1)A是D的什么条件?(2)B是D的什么条件?解已知AÞB,CÞB,DÞC,BÞD,故有(1)AÞB,BÞD,所以AÞD,即A是D的充分条件(2)DÞC,CÞB,所以DÞB,又因为BÞD,所以BÛD,即B是D的充要条件。定理：如果AÛB，则A*ÛB*。证明：设P1,P2,…,Pn是出现在命题公式A、B中的原子变元，因为AÛB，即：A(P1,P2,…,Pn)↔B(P1,P2,…,Pn)是一个重言式。故有：A(┐P1,┐P2,…,┐Pn)↔B(┐P1,┐P2,…,┐Pn
6、)是一个重言式。即A(┐P1,┐P2,…,┐Pn)ÛB(┐P1,┐P2,…,┐Pn)┐A*Û┐B*，即A*ÛB*例判断下面各推理是否正确.(1)如果天气凉快,小王就不去游泳.天气凉快,所以小王没去游泳.(2)如果我上街,我一定去新华书店.我没上街.所以我没去新华书店.解:解上述类型的推理问题,应先将命题符号化,然后写出前提、结论和推理的形式结构,最后进行判断.(1)P：天气凉快;Q：小王去游泳.前提：P→ØQ,P.结论：ØQ.推理的形式结构为((P→ØQ)∧P)→ØQ.(*)判断(*)是否为重言式.①真值表法真值表的最
7、后一列全为1,因而(*)是重言式.所以推理正确.②等价演算法(P→ØQ)∧P)→ØQÛ1.③主析取范式法((P→ØQ)∧P)→ØQÛm0∨m1∨m2∨m3由②,③同样能判断推理正确.(2)P：我上街;Q：我去新华书店.前提：P→Q,ØP.结论：ØQ.推理的形式结构为((P→Q)∧ØP)→ØQ.(**)((P→Q)∧ØP)→ØQÛm0∨m2∨m3可见(**)不是重言式,所以推理不正确.还可用其他方法判断之.例证明下列前提是不相容的。1.若A因病缺了许多课,那么他中学考试失败。2.若A中学考试失败,则他没有知识。3.若A读
8、了许多书,则他有知识。4.A因病缺了许多课,而且读了许多书。证明符号化题目:P:因病缺了许多课,Q:中学考试失败,R:有知识,S:读了许多书。问题要证明前提P®Q,QØ®R,S®R,P∧S是不相容的。下面我们用另外一种形式的格式证明（即后面讲的“构造证明”的格式）：编号公式依据(1)P∧SP(2)P(1);I1(3)S(1);I2
