离散数学-第七章二元关系课后练习习题及答案

第一篇：离散数学-第七章二元关系课后练习习题及答案

第七章作业 评分要求：

1.合计100分

2.给出每小题得分(注意: 写出扣分理由).3.总得分在采分点1处正确设置.设R={|x,y∈N且x+3y=12}.【本题合计10分】(1)求R的集合表达式(列元素法);(2)求domR, ranR;(3)求R◦R;(4)求R↾{2,3,4,6};(5)求R[{3}];解

(1)R={<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}【2分】(2)domR={0,3,6,9,12}, ranR={0,1,2,3,4}【2分】(3)R◦R={<3,3>, <0,4>}【2分】(4)R↾{2,3,4,6}={<3,3>, <6,2>}【2分】(5)R[{3}]={3}【2分】 设R,F,G为A上的二元关系.证明:(1)R◦(F∪G)=R◦F∪R◦G(2)R◦(F∩G)⊆R◦F∩R◦G(3)R◦(F◦G)=(R◦F)◦G.【本题合计18分：每小题6分，证明格式正确得3分，错一步扣1分】 证明

(1)∀, ∈R◦(F∪G)⇔ ∃t(xRt∧t(F∪G)y)复合定义 ⇔ ∃t(xRt∧(tFy∨tGy)∪定义

⇔ ∃t((xRt∧tFy)∨(xRt∧tGy))∧对∨分配律 ⇔ ∃t(xRt∧tFy)∨∃t(xRt∧tGy)∃对∨分配律 ⇔ x(R◦F)y∨x(R◦G)y 复合定义 ⇔ x(R◦F∪R◦G)y ∪定义 得证

(2)∀, x(R◦(F∩G))y ⇔ ∃t(xRt∧t(F∩G)y)复合定义 ⇔ ∃t(xRt∧(tFy∧tGy))∩定义

⇔ ∃t((xRt∧tFy)∧(xRt∧tGy))∧幂等律, ∧交换律, ∧结合律 ⇒ ∃t(xRt∧tFy)∧∃t(xRt∧tGy)补充的量词推理定律 ⇔ x(R◦F)y∧x(R◦G)y 复合定义 ⇔ x(R◦F∪R◦G)y ∪定义 得证

(3)∀, ∈R◦(F◦G)⇔ ∃s(∈R∧∈(F◦G))◦定义 ⇔ ∃s(∈R∧∃t(∈F∧∈G)))◦定义 ⇔ ∃s∃t(∈R∧∈F∧∈G)辖域扩张公式 ⇔ ∃t∃s((∈R∧∈F)∧∈G)存在量词交换 ⇔ ∃t(∃s(∈R∧∈F)∧∈G)辖域收缩公式 ⇔ ∃t(∈(R◦F)∧∈G)复合定义 ⇔ ∈(R◦F)◦G 复合定义 得证 设F={|x－y+2>0∧x－y－2<0}是实数集R上的二元关系, 问F具有什么性质并说明理由.【本题合计10分：每种性质2分----答对得1分，正确说明理由得1分】 解 F={|x－y+2>0∧x－y－2<0}={|－2∈F显然.对称性: ∀, ∈F⇔－2∈F.不具有反自反性: 反例 <2,2>∈F 不具有反对称性: 反例 <2,3>,<3,2>∈F, 显然2≠3 不具有传递性: 反例 <2,3.5>,<3.5,5>∈F, 但<2,5>不属于F.设A={a,b,c}, R={,},(1)给出R的关系矩阵;(2)说明R具有的性质(用关系矩阵的判定方法说明理由)【本题合计12分：第（1）小题2分；第（2）小题10分----答对性质得1分，说明理由得1分】 解

(1)R的关系矩阵M(R)为

0 1 1 0 0 0 0 0 0(2)不具有自反性: M(R)的主对角线不是全为1 是反自反的: M(R)的主对角线全为0 不具有对称性: M(R)不是对称的

是反对称的: M(R)对称的位置至多有一个1 是传递的: M(R2)如下

0 0 0 0 0 0 0 0 0 显然满足: 如果M(R2)任意位置为1, 则M(R)对应位置也为1 5 设A≠ø, R⊆A×A, 证明(1)r(R)=R∪IA(2)s(R)=R∪R-1

【本题合计12分，每小题6分----证明格式正确得2分，过程错误一步扣1分】 证明

(1)只要证明r(R)⊆R∪IA和R∪IA⊆r(R)即可 先证r(R)⊆R∪IA:

IA⊆R∪IA

⇒ R∪IA自反(自反性的充要条件)⇒ r(R)⊆R∪IA(自反闭包的最小性)再证R∪IA⊆r(R): R⊆r(R)∧IA⊆r(R)(自反闭包的性质及自反性的充要条件)⇒ R∪IA⊆r(R)得证

(2)只要证明s(R)⊆R∪R-1及R∪R-1⊆s(R)即可 先证s(R)⊆R∪R-1:(R∪R-1)-1=R∪R-1(理由如下: ∀, ∈(R∪R-1)-1

⇔ ∈R∪R-1(逆运算定义)⇔ ∈R∨∈R-1(∪定义)⇔ ∈R-1∨∈R(逆运算定义)⇔ ∈R∪R-1(∪定义, ∪交换律)所以(R∪R-1)-1=R∪R-1)⇔ R∪R-1是对称的(对称性的充要条件)⇒ s(R)⊆R∪R-1(对称闭包的最小性)再证R∪R-1⊆s(R): R⊆s(R)(闭包定义)∧ R-1⊆s(R)(后者理由如下: ∀, ∈R-1

⇔ ∈R(逆运算定义)

⇒ ∈s(R)

⇒ ∈s(R)(s(R)是对称的)

所以 R-1⊆s(R))⇒ R∪R-1⊆s(R)得证 设A={a,b,c,d}, R={,,,,,}, 用Warshall算法求t(R).【本题合计8分】

解 依次求出W0,W1,W2,W3,W4=t(R)【2分】 W0=M(R)=

【1分】 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 W1=

【1分】 W2=

【1分】 W3=

【1分】 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 W4= 1 0 1 1

0 1 1

0 1 1

0 1 1 【1分】

即t(R)={,,,,,,,,,,,}.【1分】 设R为A上的自反和传递的关系, 证明R∩R-1是A上的等价关系.【本题合计10分】 证明

自反性: ∀x∈A，xRx∧xR-1x⇒ x(R∩R-1)x【3分】 对称性: ∀x,y∈A，x(R∩R-1)y⇔ xRy∧xR-1y⇔ yR-1x∧yRx⇒ y(R∩R-1)x【3分】 传递性: ∀x,y,z∈A，x(R∩R-1)y∧y(R∩R-1)z⇔ xRy∧xR-1y∧yRz∧yR-1z ⇔(xRy∧yRz)∧(xR-1y∧yR-1z)⇒ xRz∧xR-1z⇔ x(R∩R-1)z【4分】 得证.设A={1,2,3,4}, 在A×A上定义二元关系R, ∀,∈A×A, R⇔u+y=v+x(1)证明R是A×A上的等价关系;(2)确定由R引起的对A×A的划分.【本题合计10分】 解

(1)自反性: ∀∈A×A, R显然成立.【2分】 对称性: ∀,∈A×A, R⇔x+v=y+u⇔u+y=v+x⇔R【2分】 传递性: ∀,,∈A×A, R∧R⇔x+v=y+u∧u+t=v+s⇒x+t=y+s⇔R【2分】 因此R是A×A上的等价关系.(2)根据R的定义, R⇔x+v=y+u⇔x－y=u－v, 因此 []R={|∈A×A∧u－v=x－y},【2分】 所以R引起的划分如下: { { <1,1>,<2,2>,<3,3>,<4,4>}, {<1,2>,<2,3>,<3,4>}, {<2,1>,<3,2>,<4,3>}, {<1,3>,<2,4>}, {<3,1>,<4,2>}, {<1, 4>}, {<4,1>} }【2分】 设R, S是A={1,2,3,4}上的等价关系, 其关系矩阵分别为 【本题合计5分】

11MR00110000100100MS001, 0011001100001.求包含R与S的最小的等价关系.分析: 设包含R与S的最小等价关系为T，则RT, ST, 所以RS T.而T是等价关系，根据等价关系的定义，T应该具有自反性、对称性和传递性。由于R与S是等价关系，具有上述三个性质，由第四节关系运算与关系性质的关系知，RS具有自反性、对称性，但不一定有传递性。为此，需要使RS有传递性。又题目要求T是包含RS的最小等价关系，所以，T应是包含RS且具有传递性的最小关系，从而由传递闭包的定义，T应是RS的传递闭包，即T=t(RS)。如此，只需求出MT=Mt(RS)即可。

11求解过程：MR00110000100100，MS001***100110011000，01所以MRS11MRMS00111000（指对应元素逻辑或），【2分】 0100。【3分】 01故由Warshall算法，MTMt(RS)设R是集合A上的等价关系, |A|=n, |R|=r, |A/R|=t, 证明: rt≥n2.【本题合计5分】 证 设A/R={B1,B2,…,Bt}, |B1|=x1, |B2|=x2,…, |Bt|=xt, 显然有1 xin, xi∈N, 1it.由于A/R是A的划分, 因此 x1+x2+…+xt = n,(1).【1分】

根据Bi是等价类, 对任意s,t∈Bi, 有∈R, 从而

x12+x22+…+xt2 = r,(2)【2分】 根据算术-均方根均值不等式有

x1x2xtt2x12x2xt2

t代入(1)(2)可得 rt  n2 , 得证.【2分】

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

离散数学考试试题（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。

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

第一章部分课后习题参考答案 设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.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)

第五篇：离散数学课后习题答案第三章

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

5.确定下列命题是否为真：

（1）

真

（2）

假（3）{}

真

（4）{}

真（5）｛a,b｝｛a,b,c,｛a,b,c｝｝

真（6）｛a,b｝｛a,b,c,｛a,b｝｝

真（7）｛a,b｝｛a,b,｛｛a,b｝｝｝

真（8）｛a,b｝｛a,b,｛｛a,b｝｝｝

假

6．设a,b,c各不相同，判断下述等式中哪个等式为真:（1）｛｛a,b｝，c,｝ =｛｛a,b｝,c｝

假（2）｛a ,b,a｝=｛a,b｝

真（3）｛｛a｝，{b}｝=｛｛a,b｝｝

假（4）｛，｛｝，a,b｝=｛｛,｛｝｝,a,b｝

假 8．求下列集合的幂集：

（1）｛a,b,c｝ P(A)={ ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}（2）｛1，｛2，3｝｝ P(A)={ , {1}, {{2,3}}, {1，{2，3}} }（3）｛｝ P(A)={ , ｛｝ }

（4）｛，｛｝｝ P(A)={ , {1}, {{2,3}}, {1，{2，3}} } 14．化简下列集合表达式：（1）（AB）B）-（AB）（2）（（ABC）-（BC））A 解:(1)（AB）B）-（AB）=（AB）B）～（AB）

=（AB）～（AB）)B=B=

（2）（（ABC）-（BC））A=（（ABC）～（BC））A =（A～（BC））（（BC）～（BC））A =（A～（BC））A=（A～（BC））A=A 18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网 球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打 |A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|=2, 如图所示。

25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5人

21.设集合A＝{{1，2}，{2，3}，{1，3},{}},计算下列表达式：（1）A（2）A（3）A（4）A 解:（1）A={1，2}{2，3}{1，3}{}={1，2，3,}

（2）A={1，2}{2，3}{1，3}{}=

（3）A=123=

（4）A=

27、设A,B,C是任意集合，证明(1)(A-B)-C=A-BC(2)(A-B)-C=(A-C)-(B-C)证明

(1)(A-B)-C=(A～B)～C= A(～B～C)= A～(BC)=A-BC(2)(A-C)-(B-C)=(A～C)～(B ～C)=(A～C)(～BC)=(A～C～B)(A～CC)=(A～C～B) = A～(BC)=A-BC 由（1）得证。

网球的人} |C|=6,CAB

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

7.列出集合A={2,3,4}上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA.解：IA ={<2，2>,<3,3>,<4,4>} EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>} LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,4>} 13.设A={<1,2>,<2,4>,<3,3>}

B={<1,3>,<2,4>,<4,2>} 求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB), fld(A-B).解：AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} AB={<2,4>} domA={1,2,3} domB={1,2,4} dom(A∨B)={1,2,3,4} ranA={2,3,4} ranB={2,3,4} ran(AB)={4} A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求RR, R-1, R{0,1,}, R[{1,2}] 解：RR={<0,2>,<0,3>,<1,3>} R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3}

16．设A={a,b,c,d}，R1，R2为A上的关系，其中

R1=a,a,a,b,b,d

R2a,d,b,c,b,d,c,b23求R1R2,R2R1,R1,R2。

解: R1R2={,,} R2R1={} R12=R1R1={,,} R22=R2R2={,,} R23=R2R22={,,}

36．设A={1，2，3，4}，在AA上定义二元关系R，,AA，〈u,v> R u + y = x + v.(1)证明R 是AA上的等价关系.(2)确定由R 引起的对AA的划分.（1）证明：∵R u+y=x-y ∴Ru-v=x-y AA ∵u-v=u-v ∴R ∴R是自反的

任意的,∈A×A 如果R，那么u-v=x-y ∴x-y=u-v ∴R ∴R是对称的

任意的,,∈A×A 若R,R 则u-v=x-y,x-y=a-b ∴u-v=a-b ∴R ∴R是传递的

∴R是A×A上的等价关系

(2)∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>}, {<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} }

41.设A={1，2，3，4}，R为AA上的二元关系, 〈a，b〉，〈c，d〉 AA ，〈a，b〉R〈c，d〉a + b = c + d(1)证明R为等价关系.(2)求R导出的划分.(1)证明：

a+b=a+b ∴R ∴R是自反的

任意的,∈A×A 设R，则a+b=c+d ∴c+d=a+b ∴R ∴R是对称的 任意的,,∈A×A 若R,R 则a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴R是传递的

∴R是 A×A上的等价关系

(2)∏={{<1,1>}, {<1,2>,<2,1>}，{<1,3>,<2,2>,<3,1>}，{<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}

43.对于下列集合与整除关系画出哈斯图:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12} 解: ***19511

42(1)(2)45.下图是两个偏序集的哈斯图.分别写出集合A和偏序关系R的集合表达式.debafc

gbcfdeag

(a)(b)解:(a)A={a,b,c,d,e,f,g} R={,,,,,,,,,}IA

(b)A={a,b,c,d,e,f,g} R={,,,,,,}IA 46.分别画出下列各偏序集的哈斯图,并找出A的极大元`极小元`最大元和最小元.(1)A={a,b,c,d,e} R={,,,,,,}IA.(2)A={a,b,c,d,e}, R={}IA.解:

edbcadeabc

(1)

(2)项目(1)(2)极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无

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

1．设f :NN,且

1，若x为奇数

f(x)=x

若x为偶数2，求f(0), f({0}), f(1), f({1}), f({0,2,4,6,…})，f({4,6,8}), f-1({3,5,7}).解：f(0)=0, f({0})={0}, f(1)=1, f({1})={1}, f({0,2,4,6,…})=N，f({4,6,8})={2,3,4}, f-1({3,5,7})={6,10,14}.4.判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的?(1)f:NN, f(x)=x2+2

不是满射，不是单射

(2)f:NN,f(x)=(x)mod 3,x除以3的余数

不是满射，不是单射

1，若x为奇数(3)f:NN,f(x)=

不是满射，不是单射

0，若x为偶数

0，若x为奇数(4)f:N{0,1},f(x)=

是满射，不是单射

1，若x为偶数(5)f:N-{0}R,f(x)=lgx

不是满射，是单射

(6)f:RR,f(x)=x2-2x-15

不是满射，不是单射

5.设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假:(1)f是从X到Y的二元关系,但不是从X到Y的函数;

对

(2)f是从X到Y的函数,但不是满射,也不是单射的;

错

(3)f是从X到Y的满射,但不是单射;

错

(4)f是从X到Y的双射.错