离散数学习题

第一篇：离散数学习题

集合论

1.A={,1}，B={{a}}求A的幂集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x

4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b关于R的等价类。

5.R是A上的等价关系，A/R={{1,2}，{3}},求A，R。6.请分别判断以下结论是否一定成立，如果一定成立请证明，否则请举出反例。

①如果A∪BC，则AC或者BC。②如果A×B=A×C且A，则B=C。

27.如果R是A上的等价关系，R,r(R)是否一定是A上的等价关系？证明或举例。

8.已知A∩CB∩C,A-CB-C,证明：AB。9.证明：AX(B∩C)=(AXB)∩(AXC)10.证明：P(A)∪P(B)P(A∪B)-111.证明：R[sym] iff R=R

-1212.证明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.证明：s(R∪S)=s(R)∪s(S)14.R是A上的关系，证明：如果R是对称的，则r(R)也是对称的。

15.I是整数集，R={(x,y)|x-y是3的倍数}，证明：R是I上的等价关系。

16.如果R是A上的等价关系，则A/R一定是A的划分。17.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。18.I是正整数集合，R是I×I上的二元关系，R={<,>|xv=yu},证明：R是等价关系。

19.f:AB，R是B上的等价关系，令S={|xA且yA且R}，证明：S是A上的等价关系。

20.R是集合A上的自反关系，S是A上的自反和对称关系，证明t(R∪S)是A上的等价关系。

21.P和Q都是集合A上的划分，请问P∪Q，P-Q是否是A上的划分，22.RAXA,R[irref]且R[tra],证明：r(R)是A上的偏序关系。

23.画出{1,2,3,4,6}上整除关系的哈斯图，求{2,3,6}的4种元素。

24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),画出S的哈斯图并求{b,c,d,f}的极大元等8种元素。

25.f:A→B,g:B→C都是单（满）射，证明：复合映射gof一定是单（满）射。

26.f:A→B,g:B→C，gof是单射，请问f和g是否一定是单射？请证明或举出反例。27.R是实数集，f:R×RR×R,f()=,请问f是否为单射？是否为满射？分别证明或举反例。28.已知B∩C=,令f：P(B∪C)P(B)×P(C)，对XP(B∪C),令f(X)=(B∩X,C∩X),证明：f是双射。

代数系统

1.是模8加群，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的单位元、每个元素的逆元、所有的生成元和所有的子群。

2.求的单位元，零元，每个元素的逆元，每个元素的阶，它是循环群吗？求出它所有的子群。

3.R是实数集，在R上定义运算*为x*y=x+y+xy,问：是代数系统吗？有单位元吗？每个元素都有逆元吗？ ***4.R是非零实数集合，是代数系统，对于R中元素*x,y，令xoy=2x+2y-2。请问中是否存在单位元、零元、哪些元素有逆元？运算o是否满足交换律和结合律。分别说明理由。

5.R是实数集，R上的6运算定义如下：对R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|x-y|。问：哪些满足交换律、结合律、有单位元、有零元？说明理由。

6.是一个群，证明：G是交换群当且仅当对任意G中222元素x,y,都有等式(xy)=xy成立。

7.证明：如果群G中每个元素的逆元素都是它自已，则G是交换群。

8.循环群一定是交换群。

9.证明：阶为素数的群一定是循环群。

-110.是一个群，uG,定义运算*：x*y=xouoy, 证明：是一个群。

11.整数集Z上定义运算*：对任意整数x和y,x*y=x+y-4,其中+，-为普通加减法。证明：是一个群。

12.证明：如果群G中至少有两个元素，则群中没有零元。13.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分

14.是一个群,aG,n是a的阶(周期)，证明：k<{a|k=0,2,…,n-1},o>是的一个子群。

15.H，K都是群G的子群，请问H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的两个子群，aG, 试证：aHaK当且仅当HK。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，请问(G,*)是否构成群？

n18.是群，e是单位元，aG,a的阶为k,证明：a=e当且仅当 n是k的倍数。

19.S是G的子群，证明：{x|x是S的左陪集}是G的一个划分

20.G是群，证明：S={aG|xG(ax=xa)},则S是G的子群。21.是偶数阶群，则G中必存在2阶元素。22.证明：6个元素的群在同构意义下只有两个。

++23.R为实数集，R为正实数集，与是否同构？ 24.是有限群，证明：G不可能表示成两个真子群的并。25.图论

1.如何判断二部图？完全图、完全二部图的边数。2.如何求E回路？

3.Petersen图是否为E图或H图。

4.哪些完全图是H图？哪些完全图是E图？ 5.n为何值时轮图为H图？ 6.如何求最小生成树。

7.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。8.证明：如果G是欧拉图，则其边图L(G)也是欧拉图。9.证明：奇数个顶点的二部图（两步图）不是哈密尔顿图。10.G是平面图，G有m条边，n个顶点，证明：m3n-6。并由此证明K5不是平面图。

11.证明：有6个顶点的简单无向图G和它的补图中至少有一个三角形。

12.证明：在至少有两个顶点的无向树中，至少有2个一度顶点。

13.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？

14.证明：简单无向图G和它的补图中至少有一个是连通图。15.证明：无向图中奇度点（度数为奇数的点）有偶数个。16.证明：n个顶点的无向连通图至少有n-1条边。17.G是H图，V是G的顶点集，证明：对任意顶点集S，SV，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分图数目。18.一棵无向树有3个3次点，1个顶点次数为2，其余顶点次数为1，问它有几个次数为1的顶点？写出求解过程。19.证明：每个简单平面图都包含一个次至多为5的顶点。20.连通平面图G有n个顶点，m条边和f个面，证明：n-m+f=2。21.如果图G的最大顶点次数≤ρ，证明：G是ρ+1可点着色的。

22.G是无向简单连通图，G有n个顶点，则G最少有几条边，最多有几条边？

23.如果一个简单图G和它的补图同构，则称G是自补图，求所有4个顶点自补图。

24.G是平面图，G有m条边，n个顶点，证明：m3n-6。如果G中无三角形，则m2n-4。数理逻辑

1.如果今天是星期一，则要进行英语或数理逻辑考试。

没有不犯错误的人。整数都是有理数。有的有理数不是整数。

不存在最大的整数。有且只有一个偶数是素数。2.求真值表及范式：P(┓QR)、(┓QR)(PR)3.推理：

p(qr)，┓s∨p，q ├ sr pr，qs，p∨q ├ r∨s p∨q，p┓r，st，┓sr，┓t ├ q p(┓(r∧s)┓q),p,┓s ├ ┓q 4.如果小王是理科学生，他一定会学好数学。如果小王不是文科学生，他一定是理科学生。小王没学好数学。所以小王是文科学生。

5.判断各公式在给定解释时的真假值，并且改变论域使该公式在新的解释下取值相反。论域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①x(F(x)∨G(x))②yyR(x,y)

第二篇：离散数学习题及答案

离散数学考试试题（A卷及答案）

一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

(1)若A去，则C和D中要去1个人；

(2)B和C不能都去；

(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此

(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧ D)∨(C∧D)

T

故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：

x(S(x)∧W(x))，xY(x)x(S(x)∧Y(x))

下面给出证明：

(1)xY(x)P

(2)Y(c)T(1)，ES

(3)x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)x(S(x)∧Y(x))T(6)，EG

三、（10分）设A、B和C是三个集合，则AB(BA)。

证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)

x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)

(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))

(BA)。

四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i14232－

15>}。

五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。

证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。

下证对任意正整数n，R对称。

因R对称，则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx，所以R对称。若Rn对称，则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x，所以Rn1对称。因此，对任意正整数n，Rn对称。对任意的x、y∈A，若xt(R)y，则存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是对称的。

六、（10分）若f：A→B是双射，则f：B→A是双射。

证明因为f：A→B是双射，则f是B到A的函数。下证f是双射。

对任意x∈A，必存在y∈B使f(x)＝y，从而f(y)＝x，所以f是满射。

对任意的y1、y2∈B，若f(y1)＝f(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f是单射。

综上可得，f：B→A是双射。

七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。

证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因为S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，则bj＝bp*bj。所以对q≥i，有bq＝bp*bq。

因为p≥1，所以总可找到k≥1，使得kp≥i。对于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，则a∈S且a*a＝a。

八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：

m≤

rl(n－2)。l2l证明设G有r个面，则2m＝

2)。d(f)≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤l2(n－ii

1（2）设平面图G＝是自对偶图，则| E|＝2(|V|－1)。

证明设G＝是连通平面图G＝的对偶图，则G G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

离散数学考试试题（B卷及答案）

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。

(1)R附加前提

(2)PRP

(3)PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)QSP

(7)ST(5)(6)，I

(8)RSCP

(9)S∨RT(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。

(1)x(P(x)Q(x))P

(2)x(P(x)∨Q(x))T(1)，E

(3)x(P(x)∧Q(x))T(2)，E

(4)P(a)∧Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)Q(a)T(4)，I

(7)x(P(x)(A(x)∨B(x))P

(8)P(a)(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)x(A(x)Q(x))P

(11)A(a)Q(a)T(10)，US

(12)A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和

i1

3A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，i13即有a∈si，于是Usi。又显然有siU，所以U＝si。

i1i1i1i1rrrr

任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。

假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：

(1)fg是A到C的函数；

(2)对任意的x∈A，有fg(x)＝f(g(x))。

证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，fg是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，则R是G中的－

一个等价关系，且[a]R＝aH。

证明对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，则a1*b∈H，b1*c∈H。因为H是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

综上可得，R是G中的一个等价关系。

对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R－

＝aH。

第三篇：离散数学习题五

习题五

1.设个体域D={a,b,c}，在D中消去公式x(F(x)yG(y))的量词。甲乙用了不同的演算过程：

甲的演算过程如下： x(F(x)yG(y))x(F(x)(G(a)G(b)G(c)))(F(a)(G(a)G(b)G(c)))

(F(b)(G(a)G(b)G(c)))(F(c)(G(a)G(b)G(c)))(F(a)F(b)F(c))(G(a)G(b)G(c))乙的演算过程如下：

x(F(x)yG(y))xF(x)yG(y)(F(a)F(b)F(c))(G(a)G(b)G(c))

显然，乙的演算过程简单，试指出乙在演算过程中的关键步骤。

解：乙在演算中的关键步骤是，在演算开始就利用量词辖域收缩与扩张等值式，将量词的辖域缩小，因而演算简单。

2.设个体域D={a,b,c}，消去下列各式的量词：

(1)xy(F(x)G(y))(2)xy(F(x)G(y))(3)xF(x)yG(y)(4)（xF(x,y)yG(y))

解：

（1）(F(a)F(b)F(c))(G(a)G(b)G(c))（2）(F(a)F(b)F(c))(G(a)G(b)G(c))（3）(F(a)F(b)F(c))(G(a)G(b)G(c))（4）(F(a,y)F(b,y)F(c,y))(G(a)G(b)G(c))在（1）（2）（4）中均将量词的辖域缩小，所以演算结果都比较简单

3.设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。（1）x(F(x)G(x))（2）x(F(x)G(x))解：

解释I1为：个体为实数集合R，F(x)：x为自然数，G(x)：x为整数。在I1下，（1）为自然数都是整数，（2）为存在整数为自然数。他们都是真命题

解释I2为：个体域仍为实数集R，F(x)：x是无理数，G(x)：x能表示成分数，在I2下，（1）为无理数都能表示成分数，（2）为存在能表示成分数的无理数，他们都是假命题

4.给定公式AxF(x)xF(x)

（1）在解释I1中，个体域D1={a}，证明公式A在I1下的真值为1.（2）在解释I2中，个体域D2={a1,a2,,an}，n2,A在I2下的真值还一定是1吗？为什么？ 解：

（1）在I1下，xF(x)xF(x)F(a)F(a)F(a)F(a)1（2）在I2下

xF(x)xF(x)(F(a1)F(a2)F(an))(F(a1)F(a2)F(an))

为可满足式，设F(x)：x为奇数，aii,i1,2,n,n2，此时，蕴涵式前件为真，后件为假，故蕴含式为假，若令F(x)；x为整数，则蕴含式前后件均为真，所以（2）中公式在I2下为可满足式

5.给定解释I如下：（a）个体域D={3,4}；（b）f(x)为f(3)4,f(4)3;

（c）F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1.试求下列公式在I下的真值。

(1)xyF(x,y)(2)xyF(x,y)(3)xyF(x,y)F(f(x),f(y)))

解：

（1）

xyF(x,y)x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4))111（2）

x(F(x,3)F(x,4))(F(3,3)F(3,4))(F(4,3)F(4,4)0（3）

x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4))))(((F(3,3)F(f(3),f(3)))(F(3,4)F(f(3),f(4))))(((F(4,3)F(f(4),f(3)))(F(4,4)F(f(4),f(4))))1

6.甲使用量词辖域收缩与扩张等值式进行如下演算

x(F(x)G(x,y))xF(x)G(x,y)

乙说甲错了，乙说的对吗？为什么？

解：乙说的对，甲错了，全称量词的指导变元x，辖域为(F(x)G(x,y))，其中F(x)与G(x,y)都是x的约束变元，因而不能讲量词的辖域变小

7.请指出下面等值运算的两处错误

xy(F(x)(G(y)H(x,y))xy(F(x)(G(y)H(x,y))xy((F(x)G(y))H(x,y))

解：

演算的第一步，应用量词辖域收缩与扩张算值式时丢掉了否定连接词，演算的第二步，在原错的基础上又用错了等值式

(F(x)G(y)H(x,y))和(F(x)G(y)H(x,y))不等值

8.在一阶逻辑中将下列命题符号化，要求用两种不同的等值形式（1）没有小于负数的正数

（2）相等的两个角未必都是对顶角 解：

（1）x(F(x)G(x))x(G(x)F(x))

其中F(x)：x小于负数，G(x)：x是正数

（2）xy(F(x)F(y)H(x,y)L(x,y)xy(F(x)F(y)H(x,y)L(x,y))其中F(x)：x是角，H(x,y)：x=y，L(x,y)：x和y是对顶角

9.设个体域D为实数集合，命题“有的实数既是有理数又是无理数”，这显然是个假命题。可是某人却说这是真命题，其理由如下

设F(x)：x是有理数，G(x）：x是无理数。xF(x),xG(x)都是真命题，于是，xF(x)xG(x)x(F(x)G(x))由于xF(x)xG(x)是真命题，故x(F(x)G(x))也是真命题，即有的实数是有理数，也是无理数这个人的结论对吗？为什么？ 解：存在量词对无分配律

10.在求前束范式时有人说x(F(x)G(x,y))已是前束范式，理由是量词已在公式的前面，他说的对吗？为什么？

解：在前束范式中，否定联结词不能在量词前面出现 11.有人说无法求公式

x(F(x)G(x))xG(x,y)的前束范式，因为公式中的两个量词的指导变元相同。他的理由对吗？为什么？ 换名规则可以使两个指导变元不相同 12.求下列各式的前束范式：(1)xF(x)yG(x,y)(2)x(F(x,y)yG(x,y,z))(3)xF(x,y)xG(x,y)

(4)x1(F(x1)G(x1,x2))(x2H(x2)x3L(x2,x3))(5)x1F(x1,x2)(F(x1)x2G(x1,x2))解：

（1）xy(F(x)G(z,y))（2）xt(F(x,t)G(x,t,z))

（3）x1x2x3x4((F(x1,y)G(x2,y))(G(x3,y)F(x4,y)))（4）y1y2y3((F(y1)G(y1,x2))(H(y2)L(x2,y3)))（5）y1y2(F(y1,x2)(F(x1)G(x1,y2)))

13.将下列命题符号化，要求符号化的公式权威前束范式：（1）有点火车比有的汽车跑的快（2）有的火车比所有的汽车跑的快

（3）说有的火车比所有汽车跑得快是不对的（4）说有的飞机比有的汽车慢也是不对的 解：

（1）xy(F(x)G(y)H(x,y))其中F(x)：x是汽车 G(y):y是 火车 H(x,y)：x比y跑得快（2）xy(F(x)(G(y)H(x,y)))其中F(x)：x是火车 G(y):y是 汽车 H(x,y)：x比y跑得快

（3)xy(F(x)G(y)H(x,y))其中F(x)：x是火车 G(y):y是 汽车H(x,y)：x比y跑得快

（4）xy(F(x)G(y)H(x,y))其中F(x)：x是飞机 G(y):y是 汽车 H(x,y)：x比y跑得慢

14.在自然推理系统F中，指出下面各证明序列中的错误：（1）①F(x)xG(x)前提引入

②F(c)G(c)①EI规则（2）①xF(x)yG(y)前提引入

②F(a)F(b)①EI规则（3）①F(y)G(y)前提引入

②x(F(x)G(x))①EG规则（4）①F(a)F(b)前提引入

②x(F(x)G(x))①EG规则（5）①F(c)G(c)前提引入

②x(F(x)G(x))①UG规则

解：（1）对F(x)xG(x)不能使用EI规则，它不是前束范式，首先化成前束范式F(x)xG(x)x(F(y)G(x))，因为量词辖域(F(y)G(x)中，除了x还有自由出现的y所以不能用EI规则

（2）对xF(x)yG(y)也应该先化成前束范式才能消去量词，其前束范式为xy(F(x)G(y))，要消去量词，既要用UI规则，又要用EI规则（3）这里A(y)=F(y)G(y)满足要求

（4）这里，使F(a)为真的a不一定使G(a)为真，同样的，使G(b)为真的b不一定使F(b)为真

（5）这里，c为个体常项，不能对F(c)G(c)引入全称量词 15.在自然推理系统F中，构造下面推理的证明：（1）前提：xF(x)y((F(y)G(y))R(y)),xF(x)

结论：xR(x)

（2）前提：x(F(x)(G(a)R(x))),xF(x)

结论：x(F(x)R(x))（3）前提：x(F(x)G(x)),xG(x)

结论：xF(x)

（4）前提：x(F(x)G(x)),x(G(x)R(x)),xR(x)

结论：xF(x)

（1）证明：1 xF(x)

前提引入 xF(x)y((F(y)G(y))R(y))

前提引入

y((F(y)G(y))R(y)

2假言推理

F(c)EI(F(c)G(c))R(c)

UI F(c)G(c)

附加

R(c)6假言推理

xR(x)

7EG

（2）证明：1 xF(x)

前提引入

x(H(x)),xF(x)x(F(a)G(a))),G(a)I(y)H(a)x(F(x)(G(a)R(x)))

x(G(a)H(a)I(a))前提引入 F(c)EI F(c)(G(a)R(c))

UI G(a)R(c)4假言推理

R(c)

5化简

F(c)R(c)6合取

x(F(x)R(x))

7EG

（3）证明：1 xF(x)

前提引入xF(x)

1置换F(c)

2UI

x(F(x)G(x))

前提引入F(c)G(c)

4UI

6F(c)5析取三段论xF(x)

6EG(4)证明：1 x(F(x)G(x))

前提引入

F(y)G(y)UI x(G(x)R(X))

前提引入

G(y)R(y)

UI xR(x)

前提引入

R(y)

5UI G(y)

6析取三段论

8F(y)

27析取三段论

xF(x)

UG 16.找一个解释I，在I下，使得xF(x)xG(x)为真，而使得x(F(x)G(x))为假，从而说明xF(x)xG(x)x(F(x)G(x))。解：取个体域为自然数集合N，F(x):x为奇数，G(x):x 为偶数。显然在以上解释下xF(x)xG(x)为真而x(F(x)G(x))为假。

17.给定推理如下：

前提：x(F(x)G(x)),x(H(x)G(x))

结论：x(H(x)F(x))。

有些人给出的证明如下：

证明：

①xH(x)附加前提引入

②H(y)

③x(H(x)G(x))

④H(y)G(y)

⑤G(y)

⑥x(F(x)G(x))

⑦F(y)G(y)

⑧F(y)

⑨xF(x)

解：根据16题可知两公式并不等价。

①UI 前提引入 ③UI ②⑤假言推理 前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 并且说，由附加前提证明法可知，推理正确，请指出以上证明的错误。18.给出上题（17）推理的正确证明（注意，不能使用附加前提证明法）。

证明：1 x(F(x)G(x))

前提引入

x(H(x)G(x))

前提引入

F(y)G(y)UI H(y)G(y)

2UI G(y)F(y)

3置换H(y)F(y)5假言三段论x(H(x)F(x))UG

19.在自然推理系统F中，构造下列推理的证明：

前提：xF(x)xG(x)

结论：x(F(x)G(x))

证明：1xF(x)xG(x)

前提引入 yF(y)xG(x)

换名规则

yx(F(x)G(x))化简

x(F(x)G(x))EI

20.在自然推理系统F中，构造下列推理的证明（可以使用附加前提证明法）：（1）前提：x(F(x)G(x))

结论：xF(x)xG(x)（2）前提：x(F(x)G(x))

结论：xF(x)xG(x)

证明：（1）.1xF(x)

附加前提引入

F(y)UI x(F(x)G(x))

前提引入

F(y)G(y)

3UI G(y)3假言推理

xG(x)

（2）1 xF(x)

附加前提引入xF(x)

置换原则F(c)

2EI

x(F(x)G(x))

前提引入

F(c)G(c)

UI

G(c)

5析取三段论xG(x)

EG 21.在自然推理系统中，构造下面推理的证明：

没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。

设F(x):x是乌鸦，G(x)：x是北京鸭，H(x):x是白色的。前提 x(F(x)H(x)),x(G(x)H(x))结论 x(G(x)F(x))

证明：1 x(F(x)H(x))

前提引入 2 x(F(x)H(x))

置换原则 3 x(F(x)H(x))

置换原则 4 x(H(x)F(x))

H(y)F(y)

4UI 6 x(G(x)H(x))

前提引入 7 G(y)H(y)

5UI 8 G(y)F(y)

7假言三段论 9 x(G(x)F(x))

8UG 22.在自然推理系统F中，构造下面推理的证明：

(1)偶数都能被2整除。6是偶数。所以6能被2整除。

(2)凡大学生都是勤奋的。王晓山不勤奋，所以王晓山不是大学生。

（1）设F(x):x为偶数，G(x)：x能被2整除 前提 x(F(x)G(x)),F(6)结论 G(6)证明：1 x(F(x)G(x))

前提引入

F(6)G(6)

1UI F(6)

前提引入 G(6)

3假言推理

(2)设F(x):x是大学生，G(x)：x是勤奋的，a 王晓山 前提 x(F(x)G(x)),G(a)，结论 F(a)

证明：1 x(F(x)G(x))

前提引入

F(a)G(a)

1UI G(a)

前提引入

F(a)3 据取式

23.在自然推理系统F中，证明下面推理：

（1）每个有理数都是实数。有的有理数是整数。因此，有的实数是整数9（2）有理数，无理数都是实数。虚数不是实数。因此，虚数既不是有理数也不是无理数。

（1）设F(x):x是有理数，G(x)：x实数，H(x):x是整数

前提 x(F(x)G(x))，x(F(x)H(x))

结论 x(G(x)H(x))

(2)设F(x):x是有理数，G(x)：x是无理数，H(x):x是实数，I(x):x是虚数 前提 x((F(x)G(x))H(x)),x(I(x)H(x))结论 x(I(x)(F(x)G(x)))

证明：1 x(I(x)H(x))

前提引入

I(y)H(y)

UI x((F(x)G(x))H(x)), 前提引入

4(F(y)G(y))H(y)UI H(y)(F(y)G(y))

置换 I(y)(F(y)G(y))

5假言三段论

x(I(x)(F(x)G(x))

UG 24.在自然推理系统F中，构造下面推理的证明：

每个喜欢不行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者喜欢乘汽车。有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人类集合）

设F(x):x喜欢步行，G(x)：x喜欢骑自行车，H(x):x喜欢乘汽车 前提 x(F(x)G(x)，x(G(x)H(x)),xH(x)结论 xF(x)

证明：1 xH(x)

前提引入

H(c)

UI x(G(x)H(x))

前提引入

G(c)H(c)UI G(c)

4析取三段论

x(F(x)G(x))

前提引入

F(c)G(c)

UI

F(c)

57拒取式

xF(x)

8UG 25.在自然推理系统F中，构造下列推理的证明（个体域为人类集合）：

每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的，所以王大海在他的事业中将获得成功。

设F(x):x是科学工作者，G(x)：x是刻苦钻研的，H(x):x是聪明的，I(x):x在事业中获得成功

前提 x(F(x)G(x))，x(G(x)H(x)I(x))，a:王大海，F(a),H(a)结论 I(a)证明：1 F(a)

前提引入

x(F(x)G(x))

前提引入

F(a)G(a)

2UI G(a)3假言推论

H(a)

前提引入 x(G(x)H(x)I(x))

前提引入

G(a)H(a)I(a)

6UI G(a)H(a)5合取

I(a)8假言推论

第四篇：离散数学课后习题答案

第一章部分课后习题参考答案 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r) 0∨(0∧1)0（2）（p↔r）∧(﹁q∨s)（0↔1）∧(1∨1)0∧10.（3）（p∧q∧r）↔(p∧q∧﹁r)（1∧1∧1）↔(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→01 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外，只有6能被2整除，6才能被4整除。”

答：p: 是无理数

q: 3是无理数

0

r: 2是无理数

s: 6能被2整除t: 6能被4整除

0

命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型：（4）(p→q)→(q→p)（5）(p∧r)(p∧q)（6）((p→q)∧(q→r))→(p→r)答：

（4）

p

q

p→q

q

p

q→p

(p→q)→(q→p)

0

0

0

0

0

0

0

0

0

0

所以公式类型为永真式

（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）

第二章部分课后习题参考答案

3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.1(1)(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1

所以公式类型为永真式

(3)P

q

r

p∨q

p∧r

（p∨q）→(p∧r)0

0

0

0

0

0

0

0

0

0

0

0

0 0

0

0 1

0

0

0

0 1

0

1

0

0

0 1

所以公式类型为可满足式

4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)(p→(q∧r))(4)(p∧q)∨(p∧q)(p∨q)∧(p∧q)证明（2）(p→q)∧(p→r)(p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)（4）(p∧q)∨(p∧q)(p∨(p∧q))∧(q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值

(1)(p→q)→(q∨p)(2)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：

（1）主析取范式

(p→q)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)m0m2m3

∑(0,2,3)主合取范式：

(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq) M1

∏(1)(2)主合取范式为：

(p→q)qr(pq)qr (pq)qr0 所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为：

(p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))11 1 所以该式为永真式.永真式的主合取范式为 1 主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案

14.在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r 结论：p(4)前提：qp,qs,st,tr 结论：pq

证明：（2）

①(qr)前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p（3）⑤⑥拒取式

证明（4）：

①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入

⑤qt ③④等价三段论 ⑥（qt）(tq)⑤ 置换 ⑦（qt）⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取

15在自然推理系统P中用附加前提法证明下面各推理：

4(1)前提：p(qr),sp,q 结论：sr 证明

①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理

16在自然推理系统P中用归谬法证明下面各推理：

(1)前提：pq,rq,rs 结论：p 证明：

①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化简律 ⑥r￢s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取

由于最后一步r﹁r 是矛盾式,所以推理正确.

第五篇：《离散数学》图论部分习题

《离散数学》图论部分习题

1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图

2)是否存在具有6个顶点的自补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整 数，n=4k或n=4k+1，不存在6阶自补图。

6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现

7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。

8.图G如下图所示：

1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？

n为奇数时

10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数； 桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。

11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；

否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。

12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。

设有n个顶点，其中x片树叶

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1

n=9

15.给出全部互不同构的4阶简单无向图的平面图形。

16.如果G是平面图, 有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.