离散证明题集锦一．命题逻辑例：给出┐(P∧Q)↔(┐P∨┐Q)的真值表PQ┐(P∧Q)↔(┐P∨┐Q)00101111011011101010101111011000步骤②①③①②①解：一般说来，n个命题变元组成的命题公式共有2n种真值指派。定理1：任何两个重言式的合取或析取，仍然是重言式。证明：设A、B为两个重言式，则A∧B和A∨B的真值分别等于T∧T和T∨T。定理2：对一个重言式的同一分量都用任何一个命题公式置换，所得命题公式仍为一个重言式。（即代入规则）证明：由于重言式的真值与分量的真值指派无关，故对同一分量以任何一个命题公式置换后，重言式的真值不变。定理3：设A、B是两个命题公式，AB当且仅当A↔B是一个重言式。（前面已证）证明：若AB，则对于A、B所包含的分量的任意指派，A、B均取相同的真值，即A↔B是一个重言式；若A↔B是一个重言式，即对于分量的任意指派，A、B均取相同的真值，即AB定理1：设A1是命题公式A的子公式，若A1B1，则若将A中的A1用B1来替换，得到公式B，则B与A等价，即AB.(替换规则)。证明：因为对变元的任一组指派，A1与B1真值相同，故以B1取代A1后，公式B与公式A相对于变元的任一指派的真值也必相同，所以AB。证明下列命题公式(可以利用基本等价式)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.原式（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的必要条件，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)是一个重言式。即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.(*)判断(*)是否为重言式.①真值表法真值表的最后一列全为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读了许多书,则他有知识。4.A因病缺了许多课,而且读了许多书。证明符号化题目:P:因病缺了许多课,Q:中学考试失败,R:有知识,S:读了许多书