离散证明题集锦.docx
《离散证明题集锦.docx》由会员分享，可在线阅读，更多相关《离散证明题集锦.docx（21页珍藏版）》请在冰点文库上搜索。
离散证明题集锦
离散证明题集锦
一．命题逻辑
例：
给出┐（P∧Q）↔（┐P∨┐Q）的真值表
P
Q
┐（P∧Q）↔（┐P∨┐Q）
0
0
101111
0
1
101110
1
0
101011
1
1
011000
步骤
②①③①②①
解：
一般说来，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∨R
P∧┐Q∨QP∨Q
解：
1.原式Q→（P∨P）∧（P∨Q）Q→P∧（P∨Q）Q→P
2.原式（（P∧Q）∨P）∧（（P∧Q）∨┐Q）（P∨P）∧（P∨Q）∧（P∨┐Q）∧（Q∨┐Q）P∧（P∨Q）∧（P∨┐Q）P∧PP
3.原式┐（┐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）→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:
读了许多书。
问题要证明前提
PQ,QR,SR,P∧S是不相容的。
下面我们用另外一种形式的格式证明
（即后面讲的“构造证明”的格式）：
编号公式依据
（1）P∧SP
（2）P
（1）;I1
（3）S
（1）;I2
（4）PQP
（5）Q
（2）,（4）;I8
（6）SRP
（7）R（3）,（6）;I8
（8）QRP
（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
即:
李四说真话,张三和王五说假话。
例1.9.3：
求证：
S是前提W，W→┐Q,┐Q→R和R→S的有效结论。
证明：
{1}
（1）W→┐QP
{2}
（2）┐Q→RP
{1,2}（3）W→RT,
（1）
（2）I11
{3}（4）WP
{1,2,3}（5）RT,（3）（4）I8
{4}（6）R→SP
{1,2,3,4}（7）ST,（5）（6）I8
（这部分的T，I8等是另外一本书的内容，所以不用管，只要会推就行）
例前提:
如果马会飞或羊吃草,则母鸡就会是飞鸟;如果母鸡是飞鸟,那么烤熟的鸭子还会跑;烤熟的鸭子不会跑。
结论:
羊不吃草。
解符号化上述语句,P:
马会飞,Q:
羊吃草,R:
母鸡是飞鸟,S:
烤熟的鸭子还会跑,S:
烤熟的鸭子不会跑,Q:
羊不吃草。
前提集合{P∨QR,RS,S},结论C:
Q。
（1）SP
（2）RSP
（3）R
（1）,
（2）,I9
（4）P∨QRP
（5）（P∨Q）（3）,（4）,I9
（6）P∧Q（5）,E5
（7）Q（6）,I2
例如果我的考试通过,那么我很快乐。
如果我快乐,那么阳光很好。
现在是凌晨一点,天很暖和。
试给出结论。
解设P:
我的考试通过,Q:
我很快乐,R:
阳光很好,S:
天很暖和。
把“凌晨一点”理解为阳光不好。
前提为:
PQ,QR,R∧S。
编号公式依据
（1）PQP
（2）QRP
（3）PR
（1）,
（2）；I11
（4）R∧SP
（5）R（4）；I1
（6）P（3）,（5）；I9
结论:
P,我的考试没通过。
例前提:
P∨Q,PR,RS;结论:
SQ。
证明
（1）SCP
（2）RSP
（3）SR
（2）,E
（4）R
（1）,（3）,I
（5）PRP
（6）RP（5）,E
（7）P（4）,（6）,I
（8）P∨QP
（9）PQ（8）,E
（10）Q（7）,（9）,I
（11）SQ
（1）,（10）,CP
（CP规则这部分因为好像多了一个条件，所以用起来可能会比较简单）
例1.9.5：
证明R→S可从前提P→（Q→S），┐R∨P和Q推出。
证明：
（CP规则，因为结论R→S为条件式）
{1}
（1）┐R∨PP
{2}
（2）RP（附加前提）
{1,2}（3）PT,
（1）
（2）I10
{3}（4）P→（Q→S）P
{1,2,3}（5）Q→ST,（3,4）I8
{4}（6）QP
{1,2,3,4}（7）ST,（5）（6）I8
{1,3,4}（8）R→SCP,
（2）（7）
例1.9.4：
证明从前提P→Q，┐（Q∨R）可演绎出┐P.
证明：
（反证法）
{1}
（1）PP（附加前提）
{2}
（2）P→QP
{1,2}（3）QT,
（1）
（2）I8
{3}（4）┐（Q∨R）P
{3}（5）┐Q∧┐RT,（4）E5
{3}（6）┐QT，（5）I1
{1,2,3}（7）Q∧┐QT,（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,US
（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›}
升级会员 