PAGEPAGE2吉林大學(xué)軟件學(xué)院2002級本科《離散數(shù)學(xué)I》試題（A）參考答案及評分標(biāo)準吉林大學(xué)計算機科學(xué)與技術(shù)學(xué)院2005級本科《離散數(shù)學(xué)I》試題（A）

參考答案簡答題（本大題共20小題，每小題2分，共40分）4最大元是PQ最小元是PQIA，EA不滿足反自反，滿足反對稱不存在不是，解釋{P，Q}可弄假該公式PQR一定，一定0個一定成立D={a，b}

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

1001

或者

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

0110

不是，不一定一定、一定【1分對完全剩余系為{0,1,2,3,4,5,6,7,8}、簡化剩余系為{1,2,4,5,7,8}不是，例如0或1不對不對，例如：24≡0mod41其閉合圖如右圖所示，共有60條二、解答題【本大題共5小題，共60分】1、解：

【3分】

主析取范式

（或用真值表法，如下：）PQPQ001011100111主析取范式為2、解：原式 =xG(x,y)yH(y) =(xG(x,y))yH(y) =xG(x,y)yH(y) =xG(x,y)uH(u)改名 =xu(G(x,y)H(u))對應(yīng)的Skolem范式為：xu(G(x,y)H(u))3、證：S 規(guī)則1QS 規(guī)則1Q 規(guī)則2;根據(jù)(1)、(2)PQ 規(guī)則1P 規(guī)則2;根據(jù)(3)、(4)PR 規(guī)則1;R 規(guī)則2;根據(jù)(5)、(6)4、證明：只需證明R滿足自反、對稱、傳遞性。 （1）對xA，因為有x+x=2x為偶數(shù)，所以有xRx；因此R具有自反性。 （2）對x,yA，若xRy，則有x+y是偶數(shù)，那么y+x也是偶數(shù)，所以有yRx，故R具有對稱性； （3）對x,y,zA，如果xRy，yRz，則x+y是偶數(shù)，y+z是偶數(shù)，所以有x+y+y+z=x+2y+z是偶數(shù)，那么x+z+2y-2y=x+z是偶數(shù)，所以有xRz，股R具有傳遞性。 綜上（1）、（2）、（3）可知，R為A上的等價關(guān)系。證畢！ A/R={{1,3,5,…,97,99},{2,4,6,…,98,100}}5、解：設(shè)l1≡1(mod5) l2≡0(mod5) l3≡0(mod5)

l1≡0(mod6) l2≡1(mod6) l3≡0(mod6)

l1≡0(mod7) l2≡0(mod7) l3≡1(mod7)

得l1=42c1，l2=35c2，l3=30c3，

分別解合同式42c1≡1(mod5)，35c2≡1(mod6)，30c3≡1(mod7)，

得c1≡3(mod5)，c2≡5(mod6)，c3≡4(mod7)，

故l1=126，l2=175，于是x=2′126+5′175+4′120=252+875+480=1607≡137(mod140)。6、解：（1）A點到其它各點的最短路及長度，如下表所示：BCDEFAAB，