2003级本科《离散数学I》试题（A）答案学习资料

2003级本科《离散数学I》试题（A）答案简答题（本大题共20小题，每小题2分，共40分）((A))＝{{,{},{{}},{,{}}}设(A,≤)是一个部分序集，A中元素a说是一个极大元，如果除a之外，A中没有元素x，使得a≤x。

设(A,≤)是一个部分序集，如果A中有一个元素a，对于所有的xA，都有x≤a，则称a为集合A的最大元。有向图G称为有向树，如果G中有一点r，并且满足：

（1）G中每一点v(vr)都恰是一条弧e的起点；

（2）r不是任一条弧的起点；

（3）r是根。【答出（1）～（3）任一个给1分，两个或两个以上给2分】设G=（P，L）是有限图，（v1,…,vn）是G中一条路，如果G中每点，除v1外，恰在此路中出现一次，而v1=vn，则此路称为Hamilton回路。

Hamilton回路一定是简单路从模m的每个剩余类中取出一个数作为代表，这样便可得到m个数r1,…,rm，这m个数便构成模m的一个完全剩余系。从modm的一个完全剩余系中取出与m互质的那些数就得到modm的一个简化剩余系。设σ是A到B内的映射，如果对任意aA，bA且，ab，都有σ(a)σ(b)，就称σ是A到B的单射。

不是，只有双射（1－1映射）才有逆映射。TI(G)＝0。一定成立。一定是平衡的，不一定是连通的。（a,m）=d且d|b（或者a和m互质，或（a,m）=d1且d|b）C/S={{},{{},{a}},{{1,2},{d,e}},{{1,2,3}},{N,Z,Q},{R}}是恒真公式G与H不等价，设解释I：D={a,b},

P(a)P(b)Q(a)Q(b)

1001则G在I下为假，而H在I下为真。一定是，可能。一定存在，能整除。RC＝IA∪{(a,c),(a,h),(c,a),(c,h),(h,a),(h,c),(d,f),(f,d),(e,g),(g,e)}含有7个极小项。G在I下的真值为0。(1323)＝1323×(1-1/3)×(1-1/7)＝75647二、解答题（本大题共6小题，每小题10分，共60分）集合A={1,2,3}，R是(A)上的二元关系，R＝{(a,b)|a∩b}，则R满足下列哪些性质？满足，给出证明，不满足，说明为什么？

(1)自反性；（2）反自反性；（3）对称性；（4）反对称性；（5）传递性。解答：（1）R不满足自反性，因为(A)，但∩＝，所以(,)R；（2）R不满足反自反性，因为{1}(A)且{1}∩{1}＝{1}，所以({1},{1})R；（3）R满足对称性，证明：对于任意的(a,b)R，则a∩b，则b∩a，所以

(b,a)R，所以R满足对称性。（4）R不满足反对称性，令a＝{1,2}，b={1,3}，则a,b(A)，而a∩b=b∩a＝{1}，由R的定义知，(a,b)R且(b,a)R，但ab，所以R不满足反对称性。（5）R不满足传递性，令a＝{1}，b={1,2}，c={2}，则a,b,c(A)，则有a∩b={1}且b∩c＝{2}，由R的定义知(a,b)R且(b,c)R，但a∩c=，故(a,c)R，所以R不满足传递性。设A＝{1,2,3,4,5,6,8,10,12,24}，R是整除关系，则(A,R)是一个部分序集，试画出(A,R)的Hasse图，并指出极大、极小元和最大、最小元。解答：(A,R)的Hasse图如下：33152641210824极大元为24、10极小元为1无最大元最小元为1求谓词公式xP(x,y)yQ(y)的Skolem范式。解答：用a代替x用f(z)代替u得该公式的Skolem范式为：【评分说明：1～3步等价变换给6分，变量改名1分，前束范式1分，前束合取范式1分，Skolem范式1分】用形式演绎法证明{(PQ)(RS),(QT)(SM),(TM),PR}共同蕴涵P。证明：（1）(PQ)(RS) 规则1（2）PQ 规则2，根据（1）（3）RS 规则2，根据（1）（4）(QT)(SM) 规则1（5）QT 规则2，根据（4）（6）SM 规则2，根据（4）（7）PT 规则2，根据（2）（5）（8）RM 规则2，根据（3）（6）（9）(TM) 规则1（10）TM 规则2，根据（9）（11）TP 规则2，根据（7）（12）MR 规则2，根据（8）（13）PR 规则1（14）RP 规则2，根据（13）（15）MP 规则2，根据（12）（14）（16）P 规则2，根据（10）（11）（15）解合同式67x29（mod294）。解答：令a＝67，m＝294，用辗转相除法求a和m的最高公因数，并表示成其倍数和。k01234567qk4211213rk2615114310Sk012351318T和m的最高公因数为1，表为这两个数的倍数和为

1＝(-1)6-1×18×294＋(-1)6×79×67＝(-18)×294＋79×67所以该合同式的解为x=79×29＝2291233下图是A,B,C,D,E,F六个城市间的公路路线图，边上的权值表示两个城市间的公路长度