1、离散数学考试题(后附详细答案)一、 命题符号化（共6小题，每小题3分，共计18分）1. 用命题逻辑把下列命题符号化a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS)b) 我今天进城，除非下雨。设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：QP或PQc) 仅当你走，我将留下。设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： QP2. 用谓词逻辑把下列命题符号化a) 有些实数不是有理数设R(x)表示“x是实数”，Q(x)表示“x是
2、有理数”，命题符号化为：$x(R(x) Q(x) 或 x(R(x) Q(x)b) 对于所有非零实数x，总存在y使得xy=1。设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) $y(R(y) E(f(x,y),1)c) f 是从A到B的函数当且仅当对于每个aA存在唯一的bB，使得f(a)=b.设F(f)表示“f是从A到B的函数”, A(x)表示“xA”, B(x)表示“xB”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)$b(B(b) E(f(a),b) c(S(c) E(f(a),c) E(a,b)二、
3、 简答题（共6道题，共32分）1. 求命题公式(P(QR)(R(QP)的主析取范式、主合取范式，并写出所有成真赋值。（5分）(P(QR)(R(QP)（PQR）(PQR) (（PQR）(PQR) (PQR) （PQR）).(（PQR） (PQR) (PQR) （PQR）)(PQR) (PQR) 这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（PQR)（PQR)（PQR)（PQR)（PQR)（PQR)2. 设个体域为1,2,3，求下列命题的真值（4分）a) x$y(x+y=4)b) $yx (x+y=4)a) T b) F3. 求x(F(x)G(x
4、)($xF(x)$xG(x)的前束范式。（4分）x(F(x)G(x)($xF(x)$xG(x) x(F(x)G(x)($yF(y)$zG(z) x(F(x)G(x)y$z(F(y)G(z) $xy$z(F(x)G(x) (F(y)G(z)4. 判断下面命题的真假，并说明原因。（每小题2分，共4分）a) （AB）C=(A-B) (A-C)b) 若f是从集合A到集合B的入射函数，则|A|B|a) 真命题。因为（AB）C=（AB）C=（AC）（BC）=（A-C）（B-C）b) 真命题。因为如果f是从集合A到集合B的入射函数，则|ranf|=|A|，且ranfB,故命题成立。5. 设A是有穷集，|A|
5、=5，问（每小题2分，共4分）a) A上有多少种不同的等价关系？b) 从A到A的不同双射函数有多少个？a) 52 b) 5!=1206. 设有偏序集，其哈斯图如图1，求子集B=b,d,e的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g d e b ca图1B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是g、下界集合是a,b、上确界是g、下确界是b.7. 已知有限集S=a1,a2,an,N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,Nn;P(N);R,RR,o,1N（写出即可）(6分)KS=n; KP(S)=; KN=0,KN
6、n=0, KP(N)=; KR=, K=RR= ,K0,1N= 三、 证明题（共3小题，共计40分）1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10分）a) A(BC),(EF)C, B(AS)BEb) x(P(x)Q(x), x(Q(x)R(x)，$xR(x) $xP(x)a) 证 （1）B P(附加条件) （2）B(AS) P (3) AS T(1)(2) I (4) A T(3) I (5) A(BC) P (6) BC T(4)(5) I (7) C T(6) I (8) (EF)C P (9) (EF) T(7)(8) I (10) EF T(9) E (11) E
7、T(10) I (12) BE CPb) 证 (1) $xR(x) P (2) R(c) ES(1) (3) x(Q(x)R(x) P (4) Q(c)R(c) US(3) (5) Q(c) T(2)(4) I (6) x(P(x)Q(x) P (7) P(c)Q(c) US(6) (8) P(c) T(5)(7) I (9) $xP(x) EG(8)2. 设R1是A上的等价关系，R2是B上的等价关系，A且B，关系R满足：,R，当且仅当R1且R2。试证明：R是AB上的等价关系。（10分）证 任取,ABxA yBR1R2,R，故R是自反的任取,RR1R2R1R2,R.故R是对称的。任取,R,RR
8、1R2R1R2(R1R1)(R2R2) R1R2,R, 故R是传递的。综上所述R是AB上的等价关系。3. 用伯恩斯坦定理证明（0,1和(a,b)等势。（10分）证 构造函数f：（0,1(a,b)，f(x)=,显然f是入射函数 构造函数g: (a,b)（0,1，,显然g是入射函数， 故（0,1和(a,b)等势。由于，所以4. 设R是集合A上的等价关系，A的元素个数为n，R作为集合有s个元素，若A关于R的商集A/R有r个元素，证明：rsn2。（10分）证 设商集A/R的r个等价类的元素个数分别为m1,m2,mr，由于一个划分对应一个等价关系，m1+m2+mr=n， 由于（r个数的平方的平均值大于等
9、于这r个数的平均值的平方），所以，即四、 应用题（10分）在一个道路上连接有8个城市，分别标记为a,b,c,d,e,f,g,h。城市之间的直接连接的道路是单向的，有ab, ac, bg, gb, cf, fe, bd, df.对每一个城市求出从它出发所能够到达的所有其他城市。解 把8个城市作为集合A的元素，即A=a,b,c,d,e,f,g,h，在A上定义二元关系R，R当且仅当从x到y有直接连接的道路，即R=,那么该问题即变为求R的传递闭包。利用Warshal算法，求得t(R)=那么从城市x出发能到达的城市为，故有离散数学 考试题答案一、 命题符号化（共6小题，每小题3分，共计18分）1. 用命
10、题逻辑把下列命题符号化a) 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS)b) 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：QP或PQc) 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： QP2. 用谓词逻辑把下列命题符号化a) 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：$x(R(x) Q(x) 或 x(R(x) Q(x)b) 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0)
11、$y(R(y) E(f(x,y),1)c) 设F(f)表示“f是从A到B的函数”, A(x)表示“xA”, B(x)表示“xB”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)$b(B(b) E(f(a),b) c(S(c) E(f(a),c) E(a,b)二、 简答题（共6道题，共32分）1. (P(QR)(R(QP)（PQR）(PQR) (（PQR）(PQR) (PQR) （PQR）).(（PQR） (PQR) (PQR) （PQR）)(PQR) (PQR) 这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（PQR)（PQR
12、)（PQR)（PQR)（PQR)（PQR)2. a) T b) F3. x(F(x)G(x)($xF(x)$xG(x) x(F(x)G(x)($yF(y)$zG(z) x(F(x)G(x)y$z(F(y)G(z) $xy$z(F(x)G(x) (F(y)G(z)4. a) 真命题。因为（AB）C=（AB）C=（AC）（BC）=（A-C）（B-C）b) 真命题。因为如果f是从集合A到集合B的入射函数，则|ranf|=|A|，且ranfB,故命题成立。5. a) 52 b) 5!=1206. B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是g、下界集合是a,b、上确界是g、下确界是
13、b.7. KS=n; KP(S)=; KN=0,KNn=0, KP(N)=; KR=, K=RR= ,K0,1N= 三、 证明题（共3小题，共计40分）1. a) 证 （1）B P(附加条件) （2）B(AS) P (3) AS T(1)(2) I (4) A T(3) I (5) A(BC) P (6) BC T(4)(5) I (7) C T(6) I (8) (EF)C P (9) (EF) T(7)(8) I (10) EF T(9) E (11) E T(10) I (12) BE CPb) 证 (1) $xR(x) P (2) R(c) ES(1) (3) x(Q(x)R(x) P
14、 (4) Q(c)R(c) US(3) (5) Q(c) T(2)(4) I (6) x(P(x)Q(x) P (7) P(c)Q(c) US(6) (8) P(c) T(5)(7) I (9) $xP(x) EG(8)2. 证 任取,ABxA yBR1R2,R，故R是自反的任取,RR1R2R1R2,R.故R是对称的。任取,R,RR1R2R1R2(R1R1)(R2R2) R1R2,R, 故R是传递的。综上所述R是AB上的等价关系。3. 证 构造函数f：（0,1(a,b)，f(x)=,显然f是入射函数 构造函数g: (a,b)（0,1，,显然g是入射函数， 故（0,1和(a,b)等势。由于，所以
15、4. 证 设商集A/R的r个等价类的元素个数分别为m1,m2,mr，由于一个划分对应一个等价关系，m1+m2+mr=n， 由于（r个数的平方的平均值大于等于这r个数的平均值的平方），所以，即四、 应用题（10分）解 把8个城市作为集合A的元素，即A=a,b,c,d,e,f,g,h，在A上定义二元关系R，R当且仅当从x到y有直接连接的道路，即R=,那么该问题即变为求R的传递闭包。利用Warshal算法，求得t(R)=那么从城市x出发能到达的城市为，故有离散数学试题带答案一、填空 20% （每小题2分）1设 （N：自然数集，E+ 正偶数） 则 。2A，B，C表示三个集合，文图中阴影部分的集合表达式
16、为 A B C 。3设P，Q 的真值为0，R，S的真值为1，则的真值= 。4公式的主合取范式为 。5若解释I的论域D仅包含一个元素，则 在I下真值为 。6设A=1，2，3，4，A上关系图为则 R2 = 。7设A=a，b，c，d，其上偏序关系R的哈斯图为则 R= 。8图的补图为 。9设A=a，b，c，d ，A上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。10下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分）1、下列是真命题的有（）A ； B；C ； D 。2、下列集合
17、中相等的有（ ） A4，3；B，3，4；C4，3，3；D 3，4。3、设A=1，2，3，则A上的二元关系有（ ）个。 A 23 ； B 32 ； C ； D 。4、设R，S是集合A上的关系，则下列说法正确的是（ ） A若R，S 是自反的， 则是自反的； B若R，S 是反自反的， 则是反自反的； C若R，S 是对称的， 则是对称的； D若R，S 是传递的， 则是传递的。5、设A=1，2，3，4，P（A）（A的幂集）上规定二元系如下则P（A）/ R=（ ）AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、设A=，1，1，3，1，2，3则A上包含关系“
18、”的哈斯图为（ ）7、下列函数是双射的为（ ）Af : IE , f (x) = 2x ； Bf : NNN, f (n) = ；Cf : RI , f (x) = x ； Df :IN, f (x) = | x | 。（注：I整数集，E偶数集， N自然数集，R实数集）8、图 中 从v1到v3长度为3 的通路有（ ）条。A 0；B 1；C 2；D 3。9、下图中既不是Eular图，也不是Hamilton图的图是（ ）10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。A1；B2；C3；D4 。三、证明 26%、 R是集合X上的一个自反关系，求证：R是对称和传递的
19、，当且仅当 和在R中有在R中。（8分）、 f和g都是群到的同态映射，证明是的一个子群。其中C= (8分)、 G= (|V| = v，|E|=e ) 是每一个面至少由k（k3）条边围成的连通平面图，则， 由此证明彼得森图（Peterson）图是非平面图。（11分）四、逻辑推演 16%用CP规则证明下题（每小题 8分）1、2、五、计算 18%1、设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。 （9分）2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（分）试卷一答案：一、
20、填空 20% （每小题2分）1、0，1，2，3，4，6； 2、；3、1； 4、； 5、1；6、, , , ；7、, IA ；8、9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% （每小题 2分）题目12345678910答案C DB、CCADCADBA三、证明 26%1、 证：“” 若由R对称性知，由R传递性得 “” 若，有 任意 ，因若 所以R是对称的。若， 则 即R是传递的。2、 证，有 ，又 是 的子群。3、 证：设G有r个面，则，即 。而 故即得 。（8分）彼得森图为，这样不成立，所以彼得森图非平面图。（3分） 二、 逻辑推演 16%1、
