院系：專業(yè)班級：姓名院系：專業(yè)班級：姓名：學號：裝訂線專業(yè)：考試日期：時間：總分：分閉卷一大題：選擇題（共10小題，每小題2分，共20分）1．下列是兩個命題變元P，Q的小項是（

）A．P∧┐P∧Q

B．┐P∨QC．┐P∧Q

D．┐P∨P∨Q2．令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（

）A．P→┐Q

B．P∨┐QC．P∧Q

D．P∧┐Q3．下列等值式不正確的是（

）A．┐(x)A(x)┐AB．(x)(B→A(x))B→(x)A(x)C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)4．設(shè)R為實數(shù)集，函數(shù)f：R→R，f(x)=2x，則f是（

）A．滿射函數(shù)

B．入射函數(shù)

C．雙射函數(shù)

D．非入射非滿射5．設(shè)A={a,b,c,d}，A上的等價關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則對應于R的A的劃分是（

）A．{{a},{b,c},0o00u6k}

B．{{a,b},{c},60qmoym}

C．{{a},,{c},0uuqeiw}

D．{{a,b},{c,d}}6．設(shè)X，Y，Z是集合，“-”是集合相對補運算，下列等式不正確的是（

）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)7．設(shè)*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，則（

）A．對所有x屬于A，有x*Z=Z*x=ZB．Z屬于A，且對所有x屬于A，有x*Z=Z*x=ZC．Z屬于A，且對所有x屬于A，有x*Z=Z*x=xD．Z屬于A，且存在x屬于A，有x*Z=Z*x=Z8．在自然數(shù)集N上，下列定義的運算“*”中不可結(jié)合的只有（

）A．a(chǎn)*b=min(a,b)B．a(chǎn)*b=a+bC．a(chǎn)*b=D．a(chǎn)*b=a/b9．下列說法正確的是（

）A．整環(huán)必為域

B.交換環(huán)必為整環(huán)C．整環(huán)必為交換環(huán)

D.交換環(huán)必為含幺環(huán)10．下列各圖是歐拉圖的是（

）A.B.C.D.二大題：填空題（共10空，每空2分，共20分）1．“如果雪是黑的，太陽從西邊出”是命題。2．集合A={1,2,3}上的二元關(guān)系R具有對稱性，反對稱性，自反性，則R=。3．設(shè)R是實數(shù)集，在R上定義二元運算*為a*b=a+b+a·b，其中+和·是數(shù)的加法和乘法，則代數(shù)系統(tǒng)<R,*>的幺元是，3的逆元是。4．對稱關(guān)系具有性和性。5．無向圖G具有一條歐拉回路，當且僅當G是，并且所有結(jié)點的度數(shù)都是。6．在下圖中，度數(shù)為3的結(jié)點有個，出度為2的結(jié)點有個。三大題：計算證明題（共8小題，共60分）1．（8分）如果論域是集合{a,b,c}，試消去給定公式中的量詞：(y)(x)(x+y=0)。2．（10分）設(shè)A={a,b,c

}，P(A)是A的冪集，是集合對稱差運算。已知<P(A),>是群。在群<P(A),>中，①找出其幺元。②找出任一元素的逆元。③求元素x使?jié)M足{a}x=3．（8分）求公式┐(P→Q)(P→┐Q)的主合取范式。4．（8分）在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除關(guān)系，求Z的極大元，極小元，最大元，最小元，并求集合D={2,3,4,6}的最小上界和最大下界。5．（8分）證明((Q∧S)→R)∧(S→(P∨R))(S∧(P→Q))→R6．（8分）證明:下列兩個圖同構(gòu)。7．（10分）在謂詞邏輯中構(gòu)造下面推理的證明：每個人在學校讀書的就能獲得知識。所以如果沒有人獲得知識就沒有人在學校讀書。（個體域：所有人的集合）

院系：專業(yè)班級：姓名：院系：專業(yè)班級：姓名：學號：裝訂線專業(yè)：考試日期：時間：總分：分閉卷一大題：選擇題（共10小題，每小題2分，共20分）1．下列是兩個命題變元P，Q的小項是（

C

）A．P∧┐P∧Q

B．┐P∨QC．┐P∧Q

D．┐P∨P∨Q2．令P：今天下雪了，Q：路滑，則命題“雖然今天下雪了，但是路不滑”可符號化為（

D

）A．P→┐Q

B．P∨┐QC．P∧Q

D．P∧┐Q3．下列等值式不正確的是（

C

）A．┐(x)A(x)┐AB．(x)(B→A(x))B→(x)A(x)C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)4．設(shè)R為實數(shù)集，函數(shù)f：R→R，f(x)=2x，則f是（

C

）A．滿射函數(shù)

B．入射函數(shù)

C．雙射函數(shù)

D．非入射非滿射5．設(shè)A={a,b,c,d}，A上的等價關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>}∪IA，則對應于R的A的劃分是（

D

）A．{{a},{b,c},06umek6}

B．{{a,b},{c},m66u6c6}

C．{{a},,{c},uswe6am}

D．{{a,b},{c,d}}6．設(shè)X，Y，Z是集合，“-”是集合相對補運算，下列等式不正確的是（

A

）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)7．設(shè)*是集合A上的二元運算，稱Z是A上關(guān)于運算*的零元，則（

B

）A．對所有x屬于A，有x*Z=Z*x=ZB．Z屬于A，且對所有x屬于A，有x*Z=Z*x=ZC．Z屬于A，且對所有x屬于A，有x*Z=Z*x=xD．Z屬于A，且存在x屬于A，有x*Z=Z*x=Z8．在自然數(shù)集N上，下列定義的運算“*”中不可結(jié)合的只有（

D

）A．a(chǎn)*b=min(a,b)B．a(chǎn)*b=a+bC．a(chǎn)*b=D．a(chǎn)*b=a/b9．下列說法正確的是（

C

）A．整環(huán)必為域

B.交換環(huán)必為整環(huán)C．整環(huán)必為交換環(huán)

D.交換環(huán)必為含幺環(huán)10．下列各圖是歐拉圖的是（

D

）A.B.C.D.二大題：填空題（共10空，每空2分，共20分）1．“如果雪是黑的，太陽從西邊出”是真命題。2．集合A={1,2,3}上的二元關(guān)系R具有對稱性，反對稱性，自反性，則R={<1,1>,<2,2>,<3,3>}。3．設(shè)R是實數(shù)集，在R上定義二元運算*為a*b=a+b+a·b，其中+和·是數(shù)的加法和乘法，則代數(shù)系統(tǒng)<R,*>的幺元是0，3的逆元是-3/4。4．對稱關(guān)系具有自反性和對稱性。5．無向圖G具有一條歐拉回路，當且僅當G是連通圖，并且所有結(jié)點的度數(shù)都是偶數(shù)。6．在下圖中，度數(shù)為3的結(jié)點有2個，出度為2的結(jié)點有1個。三大題：計算證明題（共8小題，共60分）1．（8分）如果論域是集合{a,b,c}，試消去給定公式中的量詞：(y)(x)(x+y=0)。2．（10分）設(shè)A={a,b,c

}，P(A)是A的冪集，是集合對稱差運算。已知<P(A),>是群。在群<P(A),>中，①找出其幺元。②找出任一元素的逆元。③求元素x使?jié)M足{a}x=解:①因為,且對任意,,所以為幺元.(3分)②對任意,因為,所以.(3分)③因為,所以x={a,b}.并且由題可知x的取法唯一.所以x有唯一解:x={a,b}.(4分)3．（8分）求公式┐(P→Q)(P→┐Q)的主合取范式。4．（8分）在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除關(guān)系，求Z的極大元，極小元，最大元，最小元，并求集合D={2,3,4,6}的最小上界和最大下界。

解:此偏序關(guān)系的哈斯圖如下.極大元:8,12,14,(3分)極小元:1.(1分)最大元:無.最小元:1.(2分)D的最小上界:12.最大下界：１.(2分)5．（8分）證明((Q∧S)→R)∧(S→(P∨R))(S∧(P→Q))→R證明:原式左邊6．（8分）證明:下列兩個圖同構(gòu)。證明:圖中結(jié)點如上標示.建立映射:f:i.(3分)易見f為雙射.(1分)又因左圖的邊為(1,2),(2,3),(2,4)(3,5),(4,5),(5,6).一一對應于右圖的邊:(1＇,2＇),(2＇,3＇),(2＇,5＇)(3＇,4＇),(4＇,5＇),(4＇,6＇)．所以兩個圖等價．(2分)7．（10分）在謂詞邏輯中構(gòu)造下面推理的證明：每個人在學校讀書的就能獲得知識。所以如果沒有人獲得知識就沒有人在學校讀書。（個體域：所有人的集合）譯:P(x):x在學校讀書;Q(x):x能獲得知識.(3分)(5分,每少做一步扣一分)

院系：專業(yè)班級：姓名：院系：專業(yè)班級：姓名：學號：裝訂線.專業(yè):考試日期：所需時間：120分鐘總分：100分閉卷選擇題（每小題3分，總共30分）1、設(shè)P：我們劃船，Q：我們跑步。命題“我們不能既劃船又跑步”符號化為（）A、B、C、D、2、下列語句中哪個是真命題？（）A、我正在說謊。B、嚴禁吸煙C、如果1+2=3，那么雪是黑的。D、如果1+2=5，那么雪是黑的。3、命題公式是（）A、矛盾式B、蘊含式C、重言式D、等值式4、謂詞公式中變元x是（）A、自由變量B、約束變量C、既不是自由變量也不是約束變量D、既是自由變量也是約束變量5、若個體域為整數(shù)域，下列公式中哪個值為真？（）A、B、C、D、6、設(shè)個體域A={a,b},公式在A中消去量詞應為（）A、B、C、D、8、設(shè)A={{1，2，3}，{4，5}，{6，7，8}}，下列正確的是（）A、1AB、{1，2，3}AC、{{4，5}}AD、A9、冪集P（P（P（）））為（）A、{{}，{，{}}}B、{，{}，{，{}}}C、{，{}，{，{}}，{{}}}D、{，{，{}}}10、任意一個具有多個等冪元的半群，它（）A、不能構(gòu)成群B、不一定能構(gòu)成群C、能構(gòu)成群D、不能構(gòu)成交換群二、填空題（每小題2分，總共16分）1、對于前提：S，SR，，，其有效結(jié)論為2、謂詞公式的前束范式為3、設(shè)集合A={x|<3,xZ},B={x|x=2k,kZ}C={1,2,3,4,5},則A（C-B）=4、某校有足球隊員38人，籃球隊員15人，排球隊員20人，三隊隊員總數(shù)為58人，其中只有3人同時參加3種球隊，則僅僅參加兩種球隊的隊員為人。5、設(shè)A={1，2，3}上的關(guān)系R={<1,1>,<1,2>,<1,3>,<3,3>},則R具有性6、設(shè)A={1，2，3，4}上的關(guān)系R={<2,4>,<1,2>,<1,3>,<3,3>},則r(R)=7、A={1，2，3，4，5，6，8，10，24，36}，R是A上的整除關(guān)系。子集B={1，2，3，4}，那么B的上界是，下界是，B的上確界是，B的下確界是。8、設(shè)A為非空有限集，代數(shù)系統(tǒng)（P（A），）中，P（A）對運算的幺元是，零元是三、用符號形式寫出下列命題：（每小題2分，總共8分）1、如果上午不下雨，我去看電影，否則就在家讀書或看報。2、僅當你走，我將留下。3、沒有不犯錯誤的人。4、盡管有人聰明，但未必一切人都聰明。六、（9分）每個喜歡步行的人都不喜歡坐汽車，每個人或者喜歡坐汽車或者喜歡騎自行車。證明：有的人不喜歡騎自行車，因而有的人不喜歡步行。七、（9分）求的主析取范式和主合取范式，并判斷公式類型。八、（8分）令A={1，2，3}，B={a，b，c}，C={x，y，z}。R：，S：，且R={〈1，b〉〈2，a〉，〈2，c〉}，S={〈a，y〉，〈b，x〉，〈c，y〉，〈c，z〉}1、求復合關(guān)系2、求R、S、的矩陣。九（6分）設(shè)R是A上的一個具有傳遞和自反性質(zhì)的關(guān)系，T是A上的關(guān)系，使得〈a,b>,證明T是一個等價關(guān)系。十、（8分）有理數(shù)集Q中的*定義為：a*b=a+b-ab1、（Q，*）是半群嗎？是可交換的嗎？2、求幺元3、Q中是否有可逆元？若有，求出其逆元。十一、（6分）1、設(shè)（G，*）是一群，對，令H={y|y*a=a*y,yG},證明（H，*）是（G，*）的子群。

院系：專業(yè)班級：姓名：學號：裝訂線院系：專業(yè)班級：姓名：學號：裝訂線.專業(yè):考試日期：所需時間：120分鐘總分：100分閉卷選擇題（每小題3分，總共30分）1、設(shè)P：我們劃船，Q：我們跑步。命題“我們不能既劃船又跑步”符號化為（B）A、B、C、D、2、下列語句中哪個是真命題？（D）A、我正在說謊。B、嚴禁吸煙C、如果1+2=3，那么雪是黑的。D、如果1+2=5，那么雪是黑的。3、命題公式是（C）A、矛盾式B、蘊含式C、重言式D、等值式4、謂詞公式中變元x是（D）A、自由變量B、約束變量C、既不是自由變量也不是約束變量D、既是自由變量也是約束變量5、若個體域為整數(shù)域，下列公式中哪個值為真？（A）A、B、C、D、6、設(shè)個體域A={a,b},公式在A中消去量詞應為（B）A、B、C、D、8、設(shè)A={{1，2，3}，{4，5}，{6，7，8}}，下列正確的是（C）A、19、冪集P（P（P（）））為（C）A、{{}，{，{}}}B、{，{}，{，{}}}C、{，{}，{，{}}，{{}}}D、{，{，{}}}10、任意一個具有多個等冪元的半群，它（A）A、不能構(gòu)成群B、不一定能構(gòu)成群C、能構(gòu)成群D、不能構(gòu)成交換群二、填空題（每小題2分，總共16分）1、對于前提：S，SR，，，其有效結(jié)論為P2、謂詞公式的前束范式為3、設(shè)集合A={x|<3,xZ},B={x|x=2k,kZ}C={1,2,3,4,5},則A（C-B）={0，2，4，6，7，8}4、某校有足球隊員38人，籃球隊員15人，排球隊員20人，三隊隊員總數(shù)為58人，其中只有3人同時參加3種球隊，那么僅僅參加兩種球隊的隊員為9人。5、設(shè)A={1，2，3}上的關(guān)系R={<1,1>,<1,2>,<1,3>,<3,3>},則R具有反對稱、傳遞性6、設(shè)A={1，2，3，4}上的關(guān)系R={<2,4>,<1,2>,<1,3>,<3,3>},則r(R)={〈1，1〉，〈2，2〉，〈3，3〉，〈4，4〉，〈2，4〉，〈1，2〉，〈1，3〉s(R)={〈1，2〉，〈2，1〉，〈1，3〉，〈3，1〉，〈2，4〉，〈4，2〉，〈3，3〉}。7、A={1，2，3，4，5，6，8，10，24，36}，R是A上的整除關(guān)系。子集B={1，2，3，4}，那么B的上界是24，36，下界是1，B的上確界是不存在，B的下確界是1。8、設(shè)A為非空有限集，代數(shù)系統(tǒng)（P（A），）中，P（A）對運算的幺元是，零元是A。三、用符號形式寫出下列命題：（每小題2分，總共8分）1、如果上午不下雨，我去看電影，否則就在家讀書或看報。解：P:上午不下雨Q:我去看電影R:我在家讀書T:我在家看報2、僅當你走，我將留下。解P:你走Q:我將留下3、沒有不犯錯誤的人。解M(x):x是人F(x):x會犯錯誤4、盡管有人聰明，但未必一切人都聰明。解M(x):x是人T(x):x是聰明的六、（9分）每個喜歡步行的人都不喜歡坐汽車，每個人或者喜歡坐汽車或者喜歡騎自行車。證明：有的人不喜歡騎自行車，因而有的人不喜歡步行。解：設(shè)個體域為人P(x):x喜歡步行Q(x):x喜歡乘汽車R(x):x喜歡騎自行車前提：，，結(jié)論：1、P7、US62、ES18、T57I3、P9、TEG84、Q(a)R(a)US35、Q(a)T24I6、P七、（9分）求的主析取范式和主合取范式，并判斷公式類型。解主析取范式主合取范式可滿足式PQPQP(PQ)P(PQ)Q11111100010111100110八、（8分）令A={1，2，3}，B={a，b，c}，C={x，y，z}。R：，S：，且R={〈1，b〉〈2，a〉，〈2，c〉}，S={〈a，y〉，〈b，x〉，〈c，y〉，〈c，z〉}1、求復合關(guān)系2、求R、S、的矩陣。解={〈1，x〉〈2，y〉，〈2，z〉}九（6分）設(shè)R是A上的一個具有傳遞和自反性質(zhì)的關(guān)系，T是A上的關(guān)系，使得〈a,b>,證明T是一個等價關(guān)系。證：<a,a>R所以<a,a>T<a,b>所以<b,a>T<a,b>T,<b,c>T所以<a,b>R且<b,a>R<b,c>R且〈c,b>RR是A上的一個具有傳遞的關(guān)系所以<a,c>R,<c,a>R所以<a,c>T所以T是一個等價關(guān)系十、（8分）有理數(shù)集Q中的*定義為：a*b=a+b-ab1、（Q，*）是半群嗎？是可交換的嗎？2、求幺元3、Q中是否有可逆元？若有，求出其逆元。解：1、Q，a*bQQ（a*b）*c=a*(b*c)=a+b+c-ab-ac-bc+abc是半群a*b=b*a是可交換的2、Qa*e=a+e-ae=a所以e=03、Qa*a-1=0a-1=1/(1-a)a十一、（6分）1、設(shè)（G，*）是一群，對，令H={y|y*a=a*y,yG},證明（H，*）是（G，*）的子群。證：eH,Hx*a=a*x,y*a=a*y(x*y)*a=x*(y*a)=(x*a)*y=a*(x*y)x*a=a*xa=x-1*a*xa*x-1=x-1*a所以x-1H所以（H，*）是（G，*）的子群。

2020-2021《離散數(shù)學》期末課程考試試卷B一、選擇題（在下列各題的括號處選擇一最恰當?shù)拇鸢?，?小題，每小題3分，共15分）1．設(shè)S表示二年級大學生的集合,R表示計算機科學系學生的集合,T表示選修離散數(shù)學的學生的集合,G表示星期一晚上參加音樂會的學生的集合，則命題“聽離散數(shù)學課的學生都沒有參加星期一晚上的音樂會。”可表示為 （）。A、TG B、T∩G=φ C、GT D、(R∩T)G2．下列推理錯誤的是（）（1）如果今天是1號，則明天是5號。今天是1號，所以明天是5號。（2）如果今天是1號，則明天是5號。明天是5號，所以今天是1號。（3）如果今天是1號，則明天是5號。明天不是5號，所以今天不是1號。（4）如果今天是1號，則明天是5號，今天不是1號，所以明天不是5號。A、（3）B、（1）（2）（4）C、（2）（4）D、（2）（3）3．n階無向完全圖Kn的邊數(shù)m是多少？（）A、nB、n2C、n(n-1)D、4．設(shè)有序?qū)?lt;2x+3,8>=<9,2x+y>則x與y分別是 （）。A、3，2 B、-3，2 C、-3，-2 D、3，-25．已知n階無向簡單圖G有m條邊，則G的補圖有()條邊。A、 B、n(n-1) C、 D、m二、在命題邏輯中將下列命題符號化（共2小題，每小題3分，共6分）只有6能被2整除，6才能被4整除。除非你努力，否則你將失敗。三、在一階邏輯中將下列命題符號化（共2小題，每小題5分，共10分）沒有不能表示成分數(shù)的有理數(shù)。在北京賣菜的人不全是外地人。四、設(shè)A={a，b，c，d}，R={<a，b>，<b，a>，<b，c>，<c，d>}，求R4。 （12分）五、設(shè)A={1，2，3，4}，R為A×A上的等價關(guān)系，其定義為：，。求商集(A×A)/R。 （12分）六、對60個人的調(diào)查表明有25人閱讀《每周新聞》雜志，26人閱讀《時代》雜志，26人閱讀《財富》雜志，9人閱讀《每周新聞》和《財富》雜志，11人閱讀《每周新聞》和《時代》雜志，8人閱讀《財富》和《時代》雜志，還有8人什么雜志也不讀。問： （15分）有多少人閱讀全部三種雜志？分別求只閱讀《每周新聞》、《時代》和《財富》雜志的人數(shù)。七、求命題公式的主析取范式。 （15分）八、在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：（15分）只要A曾到過受害者房間并且11點以前沒有離開，A就犯了謀殺罪。A曾到過受害者房間。如果A在11點以前離開，看門人會看見他?？撮T人沒有看見他。所以A犯了謀殺罪。注意：試題答案一律寫在答題紙上，寫在試卷上視為無效。

2020-2021《離散數(shù)學》期末課程考試試卷B答案一大題：選擇題（在下列各題的括號處選擇一最恰當?shù)拇鸢福?小題，每小題3分，共15分）1．B 2．C 3．D 4．A 5．C二大題：在命題邏輯中將下列命題符號化（共2小題，每小題3分，共6分）1．p：6能被2整除。q：6能被4整除。 （1分） （2分）2．p：你努力。q：你失敗。 （1分） 或 （2分）三大題：在一階邏輯中將下列命題符號化（共2小題，每小題5分，共10分）1．R(x)：x是有理數(shù)。F(x)：x能表示成分數(shù)。 （2分） 或 （3分）2．M(x)：x是人。F(x)：x是外地人。G(x)：x在北京賣菜。 （2分） 或 （3分）四大題（12分）：R2={<a，a>，<a，c>，<b，b>，<b，d>} （4分）R3={<a，b>，<b，a>，<b，c>，<a，d>} （4分）R4={<a，a>，<a，c>，<b，b>，<b，d>} （4分）或，，（4分），，(4分)所以 R4={<a，a>，<a，c>，<b，b>，<b，d>} （4分）五大題（12分）：根據(jù)命題得到R={略} （4分）所以 (A×A)/R={{<1，1>}，{<1，2>，<2，1>}，{<1，3>，<2，2>，<3，1>}，{<1，4>，<2，3>，<3，2>，<4，1>}，{<2，4>，<3，3>，<4，2>}，{<3，4>，<4，3>}，{<4，4>}} （8分）或 根據(jù)命題得到A×A中各元素關(guān)于該等價關(guān)系的等價類分別對應A中元素可能的和：2,3,4,5,6,7,8，即等價類分別是：{<1，1>}，{<1，2>，<2，1>}，{<1，3>，<2，2>，<3，1>}，{<1，4>，<2，3>，<3，2>，<4，1>}，{<2，4>，<3，3>，<4，2>}，{<3，4>，<4，3>}，{<4，4>}。（6分）所以 (A×A)/R={{<1，1>}，{<1，2>，<2，1>}，{<1，3>，<2，2>，<3，1>}，{<1，4>，<2，3>，<3，2>，<4，1>}，{<2，4>，<3，3>，<4，2>}，{<3，4>，<4，3>}，{<4，4>}} （6分）六大題（15分）：方法一：設(shè)A，B，C，S分別表示閱讀了《每周新聞》、《時代》和《財富》雜志及全體參與調(diào)查的人員的集合。由題意得到|A|=25，|B|=26，|C|=26，|A∩B|=11，|A∩C|=9，|B∩C|=8，|S|=60 （5分）根據(jù)集合的包含排斥原理有|S|-|A|-|B|-|C|+|A∩B|+|A∩C|+|B∩C|-|A∩B∩C| （2分）所以 |A∩B∩C|=60-25-26-26+11+9+8-8=3 （2分）只閱讀《每周新聞》雜志的人數(shù)為|A-(B∪C)|=|A-(A∩(B∪C))|=|A|-|A∩(B∪C)|=|A|-|(A∩B)∪(A∩C)|=|A|-(|A∩B|+|A∩C|-|A∩B∩C|)=25-(11+9-3)=8 （2分）同理，只閱讀《時代》雜志的人數(shù)為|B-(A∪C)|=|B-(B∩(A∪C))|=26-(11+8-3)=10 （2分）只閱讀《財富》雜志的人數(shù)為|C-(A∪B)|=|C-(C∩(A∪B))|=26-(9+8-3)=12 （2分）方法二：設(shè)閱讀全部三種雜志的人數(shù)為x，只閱讀《每周新聞》、《時代》和《財富》雜志的人數(shù)分別為y1，y2，y3，由題意得 （2分） （9分）解上述方程組得到X=3，y1=8，y2=10，y3=12 （4分）七大題（15分）： （3分） （3分） （4分）所以 （5分）八大題（15分）：設(shè)p：A曾到過受害者房間。q：A在11點以前離開了。r：A犯了謀殺罪。s：看門人看見A。 （3分）于是 前面推理可寫成前提：，p，， （1分）結(jié)論：r （1分）證明如下：=1\*GB3① 前提引入 （1分）=2\*GB3② 前提引入 （1分）=3\*GB3③ =1\*GB3①=2\*GB3②拒取 (2分)=4\*GB3④p 前提引入 （1分）=5\*GB3⑤ =3\*GB3③=4\*GB3④合取引入 （2分）=6\*GB3⑥ 前提引入 （1分）=7\*GB3⑦r =5\*GB3⑤=6\*GB3⑥假言推理 （2分）所以上面推理是正確的。

2020-2021《離散數(shù)學》期末課程考試試卷A一、填空題（每空3分，共15分）1．命題公式的類型是。2．設(shè)p：我將去鎮(zhèn)上。q：我有時間。則命題“我將去鎮(zhèn)上，僅當我有時間。”的符號化形式為。3．化簡下面集合表達式：=。4．已知一有向圖的D的度序列為（2,3,2,3），出度序列為（1,2,1,1），則D的入度序列為。5．5個頂點的非同構(gòu)的無向樹共有棵。二、選擇題（單項選擇題，每題3分，共30分）1．設(shè)命題公式，記作A，則使A的真值指派為1的p，q的取值是（）。A、00 B、01 C、10 D、112．設(shè)p：你努力。q：你將失敗。則命題“除非你努力，否則你將失敗?！狈柣癁椋ǎ?。A、pq B、qp C、┐pq D、┐qp3．下列公式中不與等值的是（）。A、 B、C、 D、4．下面公式正確的是（）。A、 B、C、 D、5．下列命題錯誤的是（）。A、 B、C、 D、6．設(shè)R={<x,y>|x,y∈R，x-y+2>0且x-y-2<0}，則R具有的性質(zhì)是（）。A、自反性 B、對稱性C、自反性和對稱性 D、自反性、對稱性和傳遞性7．設(shè)A＝B＝R×R，f是A→B的函數(shù)，且任意<x,y>∈A，f(<x,y>)=<y-1,x-1>，則f是（）。A、單射 B、滿射 C、雙射 D、既非單射，也非滿射8．彼得松（Peterson）圖既不是歐拉圖，也不是哈密頓圖，至少加（）條新邊才能使它成為歐拉圖。A、1B、2C、5D、69．設(shè)G是n（n≥2）階無向簡單圖，是G的補圖，已知，，則和分別是（）。A、k1，k2 B、k2，k1 C、n-1-k1，n-1-k2 D、n-1-k2，n-1-k110．無向樹T有7片葉子，其余頂點都是3度頂點，則T的頂點數(shù)為（）。A、5 B、6 C、12 D、13三、在一階邏輯中符號化下列命題。（每題4分，共12分）1．林曉莉非常聰明并且能干。2．每一個人都愛他自己的孩子。3．并非所有的人都用右手寫字。四、計算題（每題8分，共32分）1．設(shè)集合A＝{1，2，3，4}，B＝{2，3，4}，C={1，2，3}，A到B上關(guān)系R1＝{<2,4>，<3,3>，<4,2>}，B到C上關(guān)系R2＝{<2.1>，<3,2>，<4,3>}，求。2．某班有25個學生，其中14人會打籃球，12人會打排球，6人會打網(wǎng)球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人三種球都會打。已知會打網(wǎng)球的人都會打籃球或排球。求不會打球的人數(shù)。3．設(shè)無向圖G=<V,E>，其中V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}，其關(guān)聯(lián)矩陣如下試在同構(gòu)意義下畫出G的圖形。4．判斷下圖是否是歐拉圖，如果是，找出其歐拉回路。五、在自然推理系統(tǒng)P中證明下面推理。（11分）前提：，，結(jié)論：

2020-2021《離散數(shù)學》期末課程考試試卷A答案一、填空題（每小題3分，共5小題，共15分）1、永真式（重言式）2、3、B4、（1,1,1,2）5、3二、選擇題（在下列各題的括號處選擇一最恰當?shù)拇鸢?，?0小題，每小題3分，共30分）1——5：CDABD 6——10：CCCDC三、在一階邏輯中將下列命題符號化（共3小題，每小題4分，共12分）1．a(chǎn)：林曉莉。F(x)：x非常聰明。 G(x)：x能干。 （2分） （2分）2．M(x)：x是人。F(x)：x愛自己的孩子。3、M(x)：x是人。G(x)：x用右手寫字。 或 四、計算題（每題8分，共32分）1、R1R2={<2,3>，<3,2>，<4,1>}2、設(shè)A、B、C分別表示會打籃球、排球和網(wǎng)球的人的集合，S為這25個學生的集合。則|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，，|S|=25 （5分）又由會打網(wǎng)球的人都會打籃球或排球知 從而 即 又 由此可求得 根據(jù)集合的包含排斥原理有|S|-|A|-|B|-|C|+|A∩B|+|A∩C|+|B∩C|-|A∩B∩C| （2分）所以 25-14-12-6+6+5+3-2=5 （2分）3、答案見下圖4、該圖是歐拉圖。其歐拉回路為 C=(abcdaedgfebgca)五（11分）、 證明如下：=1\*GB3① 前提引入 （1分）=2\*GB3② 前提引入 （1分）=3\*GB3③ =1\*GB3①=2\*GB3②析取三段論 （2分）=4\*GB3④ 前提引入 （1分）=5\*GB3⑤ t規(guī)則，=3\*GB3③=4\*GB3④拒取 （2分）=6\*GB3⑥ t規(guī)則，=5\*GB3⑤置換 （2分）=7\*GB3⑦ =5\*GB3⑤=6\*GB3⑥假言推理 （2分）所以上面推理是正確的。或使用附加前提證明法證明如下： =1\*GB3①p 附加前提引入 （1分）=2\*GB3② 前提引入 （1分）=3\*GB3③ 前提引入 （1分）=4\*GB3④ =2\*GB3②③析取三段論 （2分）=5\*GB3⑤ 前提引入 （1分）=6\*GB3⑥ t規(guī)則，=4\*GB3④=5\*GB3⑤拒取 （2分）=7\*GB3⑦ t規(guī)則，=6\*GB3⑥置換 （1分）⑧ t規(guī)則，①⑦析取三段論 （2分）故依附加前提證明法證明原理知原推理是有效的。 （1分）

院系：專業(yè)班級：院系：專業(yè)班級：姓名：序號：裝訂線適用專業(yè)：信息與計算科學考試日期：試卷類型：閉卷考試時間：120分鐘試卷總分：100分一、單項選擇題(本大題共6小題，每小題3分，共18分)1、下述哪一個不是命題？（D）

A、離散數(shù)學是計算機系的一門必修課

B、不存在最大偶數(shù)。

C、若我有空，我就看書。

D、請勿隨地葉痰！2.設(shè)<G,。>是群，且|G|>1,則下列命題不成立的是（B）A.G中有幺元B.G中有零元C.G中任一元素有逆元D.G中除幺元外無其它冪等元3、設(shè)A=,則下列是集合A的劃分的是（D）A.B.C.D.4.設(shè)集合A={a,}，下面四個命題為真的是(D)A.a包含于A

B.φ∈AC.包含于A

D.φ包含于A5、下列是命題公式p(qr)的成真指派的是（A）A.110,111,100B.110,101,011C所有指派D.無6、設(shè)A和B都是命題，則AB的真值為假當且僅當（D）A、A為0，B為1B、A為0，B為0C、A為1，B為1D、A為1，B為0二、填空題（本大題共4小題，每題3分，共12分）１、設(shè)A={a,b,c}，F(xiàn)是A上的二元關(guān)系，F(xiàn)={<a,c>,<b,a>,<c,b>}，則其自反閉包為r(F)={<a,c>,<b,a>,<c,b>,<a,a>,<b,b>,<c,c>}。2、設(shè)B={0,1}，則B的冪集P(B)={φ,{0},{1},{0,1}}，3、R是集合A={1,2,3}上的二元關(guān)系，R={<1,1>,<2,1>,<2,2>,<1,3>,<3,2>,<3,3>}，則R具有的性質(zhì)是___自反性、反對稱性_______________。4、設(shè)A為非空有限集，代數(shù)系統(tǒng)(P（A），）中，P(A）對運算的幺元是A，零元是φ三、符號化下列各題(本大題共3小題，每小題3分，共9分)1、吳穎不僅用功而且聰明。解：p:吳穎用功;q:吳穎聰明2、如果太陽從西邊出來，我就不姓張。解：p:太陽從西邊出；q:我姓張；3、有的人登上過月球。解：M(x):x是人；A(x):x登上過月球四、（10分）求的主合取式和主析取式。解：（主合取范式）（主析取范式）五、（10分）（給定個體域{a,b},F(a,a)=1,F(a,b)=0,F(b,a)=0,F(b,b)=1,解：六、（12分）構(gòu)造下面推理的證明

前提：┐q→p，┐q∨r，┐r

結(jié)論：p∧┐r

證：（1）┐q→p前提引入（2）┐q∨r前提引入（3）┐r前提引入（4）由（2）置換規(guī)則（5）由（3）、（4）假言推理（6）p由（1）、（5）假言推理(7)p∧┐r合取引入規(guī)則七、（14分）.已知集合A={a,b,c,d}，B={c,d,e,f}

(1)求A-B

(2)求解：A-B

={a,b,}={a,b,e,f}八、（15分）符號化下列命題并推證其結(jié)論。如果小張守第一壘并且小李向B隊投球，則A隊取勝；或者A隊未取勝，或者A隊成為聯(lián)賽第一名；A隊沒有成為聯(lián)賽的第一名；小張守第一壘。因此，小李沒有向B隊投球。解：p:小張守第一壘；q:小李向B隊投球；r:A隊取勝；s:A隊成為聯(lián)賽第一名；前提：結(jié)論：證：（1）q否定式（2）前提引入（3）前提引入（4）(2),(3)析取三段論（5）前提引入（6）(4),(5)拒取式（7）置換（8）p前提引入(9)(7),(8)析取三段論（10）（1），（9）合取

院系：專業(yè)班級：院系：專業(yè)班級：姓名：學號：裝訂線.專業(yè)：考試日期：所需時間：120分鐘總分：100分閉卷一、選擇題（每小題2分，共20分）1．下列語句中是命題的只有（）A．1+8==30B．5x+6==30C．5y+1<30D．xmod20==3。2．設(shè)命題公式G：,則使公式G取真值為1的P，Q，R賦值分別是()3．設(shè)A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（）是錯的。A、；B、{6，7，8}A；C、{{4，5}}A；D、{1，2，3}A。4．給定下列序列，（）可以構(gòu)成無向簡單圖的結(jié)點度數(shù)序列。A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。5．給定無向圖，如下圖所示，下面哪個邊集不是其邊割集（）。A、{<V1,V2>,<V7,V8>}；B、{<V1,V4>,<V3,V4>}；C、{<V4,V7>,<V4,V8>}；D、{<V1,V4>,<V2,V3>}。6．設(shè)P表示“天下大雨”，Q表示“他在室內(nèi)運動”，則命題“除非天下大雨，否則他不在室內(nèi)運動”符號化為（）。A、；B、；C、；D、．7．集合A上的關(guān)系R為一個等價關(guān)系，當且僅當R具有（）。A、自反性、對稱性和傳遞性；B、自反性、反對稱性和傳遞性；C、反自反性、對稱性和傳遞性；D、反自反性、反對稱性和傳遞性8．設(shè)Q為有理數(shù)集，〈Q，〉（其中為普通乘法）不能構(gòu)成（）。A、半群；B、獨異點；C、群；D、交換半群．9．集合A={1,2,…,8}上的關(guān)系R={<x,y>|x+y=8,x,yA}，則R的性質(zhì)為（）。A、自反的B、對稱的C、傳遞的，對稱的D、傳遞的10．連通非平凡的無向圖G有一條歐拉回路當且僅當圖G()。A、只有一個奇度結(jié)點；B、只有兩個奇度結(jié)點；C、只有三個奇度結(jié)點；D、沒有奇度結(jié)點。二、填空題(每空2分，共20分)1．設(shè)，，請在下列每對集合中填入適當?shù)姆枺ǎ?。?）,(2)。2．n階完全無向圖Kn的邊數(shù)為。3．設(shè)圖G中結(jié)點的度數(shù)列為：1,4,4,3,5,5,則G中有條邊。4．令R(x):x是實數(shù)，Q(x):x是