离散证明题集锦

离散证明题集锦离散证明题集锦离散证明题集锦资料仅供参考文件编号：2022年4月离散证明题集锦版本号：A修改号：1页次：1.0审核：批准:发布日期：离散证明题集锦一．命题逻辑例：给出┐(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是两个命题公式，AB当且仅当A↔B是一个重言式。（前面已证）证明：若AB，则对于A、B所包含的分量的任意指派，A、B均取相同的真值，即A↔B是一个重言式；若A↔B是一个重言式，即对于分量的任意指派，A、B均取相同的真值，即AB定理1：设A1是命题公式A的子公式，若A1B1，则若将A中的A1用B1来替换，得到公式B，则B与A等价，即AB.(替换规则)。证明：因为对变元的任一组指派，A1与B1真值相同，故以B1取代A1后，公式B与公式A相对于变元的任一指派的真值也必相同，所以AB。证明下列命题公式(可以利用基本等价式)Q→(P∨(P∧Q))Q→P(P∧Q)∨(P∧┐Q)P(P→Q)→(Q∨R)P∨Q∨RP∧┐Q∨QP∨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∧PP3.原式┐（┐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为任意两个命题公式，PQ的充分必要条件是PQ且QP。证明：若PQ，则P↔Q为重言式，即P→Q和Q→P是重言式；若有PQ且QP，则P→Q和Q→P是重言式，即P↔Q为重言式例已知A是B的充分条件,B是C的必要条件，C是D的必要条件,D是B的必要条件,问：(1)A是D的什么条件(2)B是D的什么条件解已知AB,CB,DC,BD,故有(1)AB,BD,所以AD,即A是D的充分条件(2)DC,CB,所以DB,又因为BD,所以BD,即B是D的充要条件。定理：如果AB，则A*B*。证明：设P1,P2,…,Pn是出现在命题公式A、B中的原子变元，因为AB，即：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)→Q1.③主析取范式法((P→Q)∧P)→Qm0∨m1∨m2∨m3由②,③同样能判断推理正确.(2)P：我上街;Q：我去新华书店.前提：P→Q,P.结论：Q.推理的形式结构为((P→Q)∧P)→Q.(**)((P→Q)∧P)→Qm0∨m2∨m3可见(**)不是重言式,所以推理不正确.还可用其他方法判断之.例证明下列前提是不相容的。1.若A因病缺了许多课,那么他中学考试失败。2.若A中学考试失败,则他没有知识。3.若A读了许多书,则他有知识。4.A因病缺了许多课,而且读了许多书。证明符号化题目: P:因病缺了许多课, Q:中学考试失败, R:有知识, S:读了许多书。 问题要证明前提 PQ,QR,SR,P∧S是不相容的。下面我们用另外一种形式的格式证明（即后面讲的“构造证明”的格式）：编号 公式 依据 (1) P∧S P (2) P (1);I1 (3) S (1);I2 (4) PQ P (5) Q (2),(4);I8 (6) SR P (7) R (3),(6);I8 (8) QR P (9) R (5),(8);I9 (10) R∧R (7),(9)例张三说李四在说谎,李四说王五在说谎,王五说张三、李四都在说谎。问谁说真话,谁说假话解设A:张三说真话;B:李四说真话;C:王五说真话 依题意有AB,BC,CA∧B。 (AB)∧(BC)∧(CA∧B)(AB)∧(BA)∧(BC)∧(CB)∧(C(A∧B))∧((A∧B)C)(A∧B∧C)∧((A∨B)∧C))∧((A∧B∧C)∨(A∧C)∨(B∧C))A∧B∧C即:李四说真话,张三和王五说假话。例：求证：S是前提W，W→┐Q,┐Q→R和R→S的有效结论。证明：{1} (1) W→┐Q P{2} (2) ┐Q→R P{1,2} (3) W→R T,(1)(2)I11{3} (4) W P{1,2,3} (5) R T,(3)(4)I8{4} (6) R→S P{1,2,3,4} (7) S T,(5)(6)I8（这部分的T，I8等是另外一本书的内容，所以不用管，只要会推就行）例前提:如果马会飞或羊吃草,则母鸡就会是飞鸟;如果母鸡是飞鸟,那么烤熟的鸭子还会跑;烤熟的鸭子不会跑。结论:羊不吃草。解符号化上述语句,P:马会飞,Q:羊吃草,R:母鸡是飞鸟,S:烤熟的鸭子还会跑,S:烤熟的鸭子不会跑,Q:羊不吃草。 前提集合{P∨QR,RS,S},结论C:Q。 (1) S P (2) RS P (3) R (1),(2),I9 (4) P∨QR P (5) (P∨Q) (3),(4),I9 (6) P∧Q (5),E5 (7) Q (6),I2例如果我的考试通过,那么我很快乐。如果我快乐,那么阳光很好。现在是凌晨一点,天很暖和。试给出结论。解设P:我的考试通过,Q:我很快乐,R:阳光很好,S:天很暖和。把“凌晨一点”理解为阳光不好。 前提为: PQ,QR,R∧S。 编号 公式 依据 (1) PQ P (2) QR P (3) PR (1),(2)；I11 (4) R∧S P (5) R (4)；I1 (6) P (3),(5)；I9 结论:P,我的考试没通过。例前提:P∨Q,PR,RS; 结论:SQ。证明(1) S CP(2) RS P(3) SR (2),E(4) R (1),(3),I(5) PR P(6) RP (5),E(7) P (4),(6),I(8) P∨Q P(9) PQ (8),E(10) Q (7),(9),I(11) SQ (1),(10),CP（CP规则这部分因为好像多了一个条件，所以用起来可能会比较简单）例：证明R→S可从前提P→(Q→S)，┐R∨P和Q推出。证明：(CP规则，因为结论R→S为条件式){1} (1) ┐R∨P P{2} (2) R P(附加前提){1,2} (3) P T,(1)(2)I10{3} (4) P→(Q→S) P{1,2,3} (5) Q→S T,(3,4)I8{4} (6) Q P{1,2,3,4} (7) S T,(5)(6)I8{1,3,4} (8) R→S CP,(2)(7)例：证明从前提P→Q，┐(Q∨R)可演绎出┐P.证明：(反证法){1} (1) P P（附加前提）{2} (2) P→Q P{1,2} (3) Q T,(1)(2)I8{3} (4) ┐(Q∨R) P{3} (5) ┐Q∧┐R T,(4)E5{3} (6) ┐Q T，(5)I1{1,2,3} (7) Q∧┐Q T,(3)(6)例“如果春暖花开,燕子就会飞回北方。如果燕子飞回北方,则冰雪融化。所以,如果冰雪没有融化,则没有春暖花开。”证明这些语句构成一个正确的推理。证:令P:春暖花开。Q:燕子飞回北方。R:冰雪融化。则上述问题转化成证明:PQ,QRRP利用CP规则,将R作为附加前提,推导P,从而推导出RP。编号公式依据(1)QRP(2)RP(附加前提)(3)Q(1),(2);I9(4)PQ前提(5)P(3),(4);I9课堂练习：1.用基本等价公式的转换方法验证下列推断是否有效。(1)PQ，R∧S，QR∧S；(2)PQ，QR，RPP∨Q∨R；(3)P，QR，R∨SQS；(4)Q∧R，R∧P，QP∨Q。2.用推理规则证明下述论断的正确性。(1)P，P(Q(R∧S))QS；(2)P(QR)，R(QS)P(QS)；(3)P(QR)(Q(RS))(P(QS))；(4)(PQ)(R∨S)，(QP)∨R，RPQ。3.A,B,C,D四人中要派两个人出差，按下述三个条件有几种派法如何派(1)若A去，则C和D中要去一人。(2)B和C不能都去。(3)C去则D要留下。4.A,B,C,D四人参加考试后，有人问它们，谁的成绩最好。A说“不是我”，B说“是D”，C说“是B”，D说“不是我”。四人的回答只有一人符合实际，问是谁的成绩最好只有一人成绩最好的是谁5.判断下列推理是否正确：(1)如果我是小孩，我会喜欢熊猫。我不是小孩，所以我不喜欢熊猫。(2)如果太阳从西边出来，那么地球停止转动。太阳从西边出来了，所以地球停止了转动。二．谓词逻辑例试用量词、谓词表示下列命题：①所有大学生都热爱祖国；②每个自然数都是实数；③一些大学生有远大理想；④有的自然数是素数。解①令S(x)：x是大学生，L(x)：x热爱祖国，则所有大学生都热爱祖国(x)(S(x)→L(x))②令N(x)：x是自然数，R(x)：x是实数，则每个自然数都是实数(x)(N(x)→R(x))全称量词(x)后跟条件式。③令S(x)：x是大学生，I(x)：x有远大理想，则一些大学生有远大理想(x)(S(x)∧I(x))④令N(x)：x是自然数，P(x)：x是素数。则有的自然数是素数(x)(N(x)∧P(x))存在量词(x)后跟合取式。例令f(x):x小于88，g(x):x是奇数，(x)(f(x)∧g(x))。个体变元x是约束变元。这已经不是一个命题函数,而是一个命题。它相当于说“存在有小于88的奇数”,这是一个真命题例令f(y):y是辣椒，g(y):y是红的，(y)(f(y)→g(y))。个体变元y是约束变元。 这也不是一个命题函数,而是一个命题。对于其中的个体变元不需要再作代入,它的含义是确定的,它断定“一切辣椒都是红的”,这当然是一个假命题。例：将公式(x)(P(x)→Q(x,y))∧R(x,y)中的约束变元改名。下面哪个正确（注意到此公式中，约束变元只有x）,1）(y)(P(y)→Q(y,y))∧R(x,y)2）(z)(P(z)→Q(x,y))∧R(x,y)3）(z)(P(z)→Q(z,y))∧R(x,y)例：将公式(x)(P(y)→Q(x,y))∧R(x,y)中的自由变元代入。（注意到此公式中y为自由变元，x既是约束出现，也是自由出现。）我们以y为例，试判断下面哪个正确1）(x)(P(z)→Q(x,z))∧R(x,y)2）(x)(P(x)→Q(x,z))∧R(x,x)3）(x)(P(z)→Q(x,z))∧R(x,z)例在公式(x)(Q(x)→R(x,y))∨(z)P(x,z)中，x既为约束出现，又为自由出现，下面用两种方法，使变元x在公式中只呈一种形式出现解用约束变元的改名规则得: (u)(Q(u)→R(u,y))∨(z)P(x,z);或用自由变元得代入规则得: (x)(Q(x)→R(x,y))∨(z)P(u,z)。（重做前一例题，将自由出现的x进行代入）重做例：将公式(x)(P(y)→Q(x,y))∧R(x,y)中的自由变元代入。注意到此公式中y为自由变元，x既是约束出现，也是自由出现。这次，我们将自由出现的x代入，得：(x)(P(y)→Q(x,y))∧R(z,y)例试证明下面苏格拉底论证：所有人都是要死的，苏格拉底是人，因此，苏格拉底是要死的。证明：令M(x):x是人，D(x):x是要死的，s:苏格拉底，原题可符号化为：(x)(M(x)→D(x))，M(s)┣D(s)推证如下：{1} (1)(x)(M(x)→D(x))P{1} (2)M(s)→D(s)UI,(1){3} (3)M(s)P{1,3}(4)D(s)T,(2),(3),I例证明(x)A(x)(x)B(x)(x)(A(x)B(x))证明：反证法(1) (x)(A(x)B(x)) P(附加前提)(2) (x)(A(x)B(x)) T,(1),E(3) (A(a)B(a)) T,(2),ES(4) A(a)∧B(a) T,(3),I(5) A(a) T,(4),I(6) B(a) T,(4),I(7) (x)A(x) T,(5),EG(8) (x)A(x)(x)B(x) P前提(9) (x)B(x) T,(7)(8),I(10) B(a) T(11) B(a)∧B(a) (6)(10)矛盾三．集合例在一个住着一些人家的僻静孤岛上,岛上只有一个理发师a,a给且只给岛上所有不能自己理发的人理发。问谁给a理发解:设S={x|x是不能自己理发的人}。(1)若aS,则a给自己a理发。又由题意知,a只给不能自己理发的人理发,所以a是不能自己理发的人,即aS,矛盾。(2)若aS,则a是不能自己理发的人。又由题意知,a只给集合S中的人理发,所以a要给a理发,即aS,矛盾。无论如何,都有aS和aS同时成立。这是著名的罗素悖论paradox。例令A={{1,2},{3},4},B={4,{5},{5,6}},则∪A={1,2}∪{3}={1,2,3},∪B={5}∪{5,6}={5,6},∩A={1,2}∩{3}=,∩B={5}∩{5,6}={5}四．关系例设A={1,3,5},B={2,4,6,8},定义A到B的二元关系R:‹a,b›R当且仅当a‹b,则称R为A到B的“小于”关系。R={‹1,2›,‹1,4›,‹1,6›,‹1,8›,‹3,4›,‹3,6›,‹3,8›,‹5,6›,‹5,8›}是A到B的一个关系,显然RA×B。而‹3,2›R,‹5,2›R,‹5,4›R。例设A={1,2,3,4,5,6},B={a,b,c,d},关系R={‹2,a›,‹2,b›,‹3,b›,‹4,d›,‹6,d›},则dm(R)={2,3,4,6},rn(R)={a,b,d},fl(R)={2,3,4,6,a,b,d}。例设A={1,2,3},B={1,2,3,4},从A到B上的关系R={‹1,1›,‹2,2›,‹3,3›},S={‹1,1›,‹1,2›,‹1,3›,‹1,4›}，则R∪S={‹1,1›,‹2,2›,‹3,3›,‹1,2›,‹1,3›,‹1,4›}R∩S={‹1,1›}R-S={‹2,2›,‹3,3›}S-R={‹1,2›,‹1,3›,‹1,4›}R'={‹1,2›,‹1,3›,‹1,4›,‹2,1›,‹2,3›,‹2,4›,‹3,1›,‹3,2›,‹3,4›}要注意的是,作为关系,补运算是对全域关系而言的,并不是对全集U而言的。例设A和B分别是学校的所有学生和所有课程的集合。假设R由所有有序对‹a,b›组成，其中a是选修课程b的学生。S由所有有序对‹a,b›构成，其中课程b是a的必修课。什么是关系R∪S，R∩S，RS，R-S和S-R解：关系R∪S由所有的有序对‹a,b›组成，其中a是一个学生，他或者选修了课程b，或者课程b是他的必修课。R∩S是所有有序对‹a,b›的集合，其中a是一个学生，他选修了课程b并且课程b也是a的必修课。RS由所有有序对‹a,b›组成，其中学生a已经选修了课程b，但课程b不是a的必修课，或者课程b是a的必修课，但a没有选修它。R-S是所有有序对‹a,b›的集合，其中a已经选修了课程b但课程b不是a的必修课。S-R是所有有序对‹a,b›的集合，其中课程b是a的必修课，但a没有选它。例设A={a,b,c,d},A上的关系 R={‹a,a›,‹a,b›,‹b,d›}, S={‹a,d›,‹b,c›,‹b,d›,‹c,b›}。求R*S和S*R。解:R*S={‹a,d›,‹a,c›}；S*R={‹c,d›}。显然R*S≠S*R从本例可知复合关系不满足交换律。兄弟关系和父子关系的复合是——叔侄关系例设A={a,b,c,d,e,f}, R={‹a,b›,‹b,c›,‹c,d›,‹d,e›,‹e,f›}。 求Rn(n=1,2,3,4,…)。解：R1=R；R2=R*R={‹a,c›,‹b,d›,‹c,e›,‹d,f›}；R3=R2*R={‹a,d›,‹b,e›,‹c,f›}；R4=R3*R={‹a,e›,‹b,f›}；R5=R4*R={‹a,f›}；R6=R5*R=；R7=； … Rn=(n＞5)。例设A={a,b,c,d,1,2,3,4},A上的关系R={‹a,2›,‹b,2›,‹b,3›,‹d,4›},则R–1={‹2,a›,‹2,b›,‹3,b›,‹4,d›}。例设A={a,b,c},B={0,1},有A到B的关系R={‹a,0›,‹b,0›,‹c,1›},S={‹a,1›,‹b,1›,‹c,1›}则R–1={‹0,a›,‹0,b›,‹1,c›},S–1={‹1,a›,‹1,b›,‹1,c›} R∪S={‹a,0›,‹b,0›,‹c,1›,‹a,1›,‹b,1›}； (R∪S)–1=R–1∪S–1 ={‹0,a›,‹0,b›,‹1,c›,‹1,a›,‹1,b›}； R∩S={‹c,1›}; (R∩S)–1=R–1∩S–1={‹1,c›}; R–S={‹a,0›,‹b,0›}； (R–S)–1=R–1–S–1={‹0,a›,‹0,b›}； dmR–1=rnR={0,1}； rn(S–1)=dm(S)={a,b,c}例设A={2,3,4},B={2,3,4,5,6},定义A到B的二元关系R: aRb当且仅当a整除b。 R={‹2,2›,‹2,4›,‹2,6›,‹3,3›,‹3,6›,‹4,4›} 23456 210101 MR=301001 400100例S={a,b,c},S上的关系R1={‹a,a›,‹b,b›,‹c,c›,‹b,c›}R2={‹a,b›,‹b,a›}R3={‹b,b›,‹c,c›}R1是自反的,R2不是自反的,R3也不是自反的。R1不是非自反的,R2是非自反的,R3也不是非自反的。例设A＝{2,3,5,7}，R＝{‹x,y›|(x-y)/2是整数}，验证R在A上是自反和对称的。证：因为对于任意x∈A，(x-x)/2＝0,即‹x,y›∈R，故R是自反的。又设x,y∈A，如果‹x,y›∈R，即(x-y)/2是整数，则(y-x)/2是整数，即‹y,x›∈R，故R是对称的。事实上，关系R＝{‹2,2›,‹3,3›,‹5,5›,‹7,7›,‹3,5›,‹5,3›,‹3,7›,‹7,3›,‹5,7›,‹7,5›}例设X＝{1,2,3}，R1＝{‹1,2›,‹2,2›}，R2＝{‹1,2›}，R3＝{‹1,2›,‹2,3›,‹1,3›,‹2,1›}，R1,R2,R3都是传递关系吗证：根据传递的定义，R1和R2是传递的。但对于R3,因为‹1,2›∈R3，‹2,1›∈R3，但‹1,1›R3,，故R3不是传递的。注意：R2是传递的。例在集合S={a,b,c,d}上的关系 R＝{‹b,c›,‹c,c›,‹c,d›,‹d,c›},判断R的性质。解R不是自反的；‹c,c›R，所以R不是非自反的；‹b,c›R,但‹c,b›R,所以R不是对称的；‹c,c›R，所以R不是非对称的； cd,但‹c,d›R且‹d,c›R,所以R不是反对称的； ‹b,c›R,‹c,d›R,但‹b,d›R,所以R不是可传递的。例A={1,2,3,4,5,6,7},R是A上的模3同余关系。显然R是A上的等价关系,A中各元素关于R的等价类分别是: [1]R={1,4,7}, [4]R={1,4,7},[7]R={1,4,7} [2]R={2,5}, [5]R={2,5}, [3]R={3,6}, [6]R={3,6},可以看出,彼此等价的元素其等价类是相同的,所以不同的等价类仅有3个,它们是[1]R,[2]R和[3]R。例若A={2,3,4,6,8},偏序关系是整除关系, 则2和3是A的极小元,6和8是A的极大元。我们先看极小元,从最大的数8开始,因为4≤8(即4整除8),故8不是极小元，那么4是不是极小元呢因为2≤4,所以4也不是极小元，那么2是不是极小元呢由于A中没有任何其它元素x,满足x≤2,故2是A的极小元。同理，3也是A的极小元。4不是，因为2≤4。对于极大元，我们从最小的数2开始,因为2≤4(即2整除4),故2不是极大元，那么4是不是极大元呢因为4≤8,所以4也不是极大元，那么8是不是极大元呢由于A中没有任何其它元素x,满足8≤x,故8是A的极大元。同理，6也是A的极大元。4不是，因为4≤8。从本例可知,极小元和极大元不是唯一的。例若A={2,3,4,6,8},偏序关系是整除关系，则A中既没有最小元,也没有最大元。因为2不能整除A中所有元素(如2不能整除3),所以2不是A的最小元，显然其余元素也不是。同理，8也不能被A中所有元素所整除，所以8不是A的最大元。实际上，A中所有元素的(最大)公约数和(最小)公倍数均不属于A,所以A中既没有最小元,也没有最大元。又如B={2,4,6,8},偏序关系是整除关系,则B的最小元是2,没有最大元。