離散數學試題與答案試卷一
一、填空 20% （每小題2分）
1〃設 }7|{)},5()(|{<∈=<∈=+
x E x x B x N x x A 且且（N ：自然數集，E ---+
正偶
數） 則 =?B A 。 2〃A ，B ，C 表示三個集合，文圖中陰影部分的集合運算式為 。
3〃設P ，Q 的真值為0，R ，S 的真值為1，則
)()))(((S R P R Q P ?∨→?∧→∨?的真值= 。
4〃公式P R S R P ?∨∧∨∧)()(的主合取範式為 。
5〃若解釋I 的論域D 僅包含一個元素，則 )()(x xP x xP ?→? 在I 下真值為 。
6〃設A={1，2，3，4}，A 上關係圖為
則 R 2 = 。
7〃設A={a ，b ，c ，d}，其上偏序關係R 的哈斯圖為
則 R= 。
8〃圖的補圖為 。
9〃設A={a ，b ，c ，d} ，A 上二元運算如下：
那麼代數系統的么元是 ，有逆元的元素為 ，它們的逆元分別為 。
10〃下圖所示的偏序集中，是格的為 。
二、選擇 20% （每小題 2分）
1、下列是真命題的有（ ） A 〃 }}{{}{a a ?；
B 〃}}{,{}}{{ΦΦ∈Φ；
C 〃 }},{{ΦΦ∈Φ；
D 〃 }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ）
A 〃{4，3}Φ?；
B 〃{Φ，3，4}；
C 〃{4，Φ，3，3}；
D 〃 {3，4}。 3、設A={1，2，3}，則A 上的二元關係有（ ）個。 A 〃 23 ； B
〃 32 ； C 〃 3
32
?； D 〃 2
23
?。
4、設R ，S 是集合A 上的關係，則下列說法正確的是（ ） A 〃若R ，S 是自反的， 則S R 是自反的； B 〃若R ，S 是反自反的， 則S R 是反自反的； C 〃若R ，S 是對稱的， 則S R 是對稱的； D 〃若R ，S 是傳遞的， 則S R 是傳遞的。
5、設A={1，2，3，4}，P （A ）（A 的冪集）上規定二元系如下
R=
t s
t s
p
∧
∈
=則P（A）/ R=（）
|}
>
A
<
)
(|
||
s
(
,
,
{t
|
A〃A ；B〃P(A) ；C〃{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；
D〃{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}}
6、設A={Φ，{1}，{1，3}，{1，2，3}}則A上包含關係“?”的哈斯圖為（）
7、下列函數是雙射的為（）
A〃f : I→E , f (x) = 2x ；B〃f : N→N?N, f (n) =
C〃f : R→I , f (x) = [x] ；D〃f :I→N, 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
度結點。
A〃1；B〃2；C〃3；D〃4 。
三、證明26%
１、R 是集合X 上的一個自反關係，求證：R 是對稱和傳遞的，當且僅當
< a, b> 和在R 中有<.b , c>在R 中。（8分）
２、f 和g 都是群
群。其中C=)}()(|{1x g x f G x x =∈且 (8分)
３、G=
圖，則2)
2(--≤
k v k e ， 由此證明彼得森圖（Peterson ）圖是非帄面圖。（11分）
四、邏輯推演 16%
用CP 規則證明下題（每小題 8分） 1、F A F E D D C B A →?→∨∧→∨, 2、)()())()((x xQ x xP x Q x P x ?→??→?
五、計算 18%
1、設集合A={a ，b ，c ，d}上的關係R={ ,< b , a > ,< b, c > , < c , d >}用矩陣運算求出R 的傳遞閉包t (R)。 （9分）
2、如下圖所示的賦權圖表示某七個城市721,,,v v v 及預先算出它們之間的一些直接通信線路造價，試給出一個設計方案，使得各城市之間能夠通信而且總造價最小。 （９分）
試卷一答案：
一、填空 20% （每小題2分）
1、{0，1，2，3，4，6}；
2、A C B -⊕)(；
3、1；
4、)()(R S P R S P ∨?∨?∧∨∨?；
5、1；
6、{<1,1>, <1,3>, <2,2>, <2,4> }；
7、{
8、
9、a ；a , b , c ,d ；a , d , c , d ；10、c;
二、選擇 20% （每小題 2分）
三、證明 26%
1、 證：
“?” X c b a ∈?,, 若R >c ,a <,>b ,a <∈由
R 對稱性知
R a ,c <,>a ,b <∈>，由R 傳遞性得 R >c ,b <∈
“?” 若R >b ,a <∈，R >c ,a <∈有 R >c ,b <∈ 任意 X b a ∈,，因
R >a ,a <∈若R >b ,a <∈R >a ,b < ∈∴ 所以R 是對稱的。
若R >b ,a <∈，R >c b,<∈ 則 R c b, R >a b,<>∈<∧∈ R >c ,a < ∈∴
即R 是傳遞的。 2、 證
C
b a ∈?,，有
)
()(),()(b g b f a g a f ==，又
)()(,)()(111
1b g b g b f b f ----==)()()()(111
1----===∴b g b g b f
b f
a f (∴★a g
b g a g b f a f b ()(*)()(*)()11
1===---★)1-b
a ∴★C
b ∈-1 ∴< C , ★> 是 < G 1 , ★>的子群。
3、 證：
①設G 有r 個面，則
rk
F d e r
i i ≥=∑=1
)(2，即
k e
r 2≤
。而 2=+-r e v 故
k e e v r e v 22+
-≤+-=即得 2)
2(--≤
k v k e 。（8分）
②彼得森圖為10,15,5===v e k ，這樣
2)
2(--≤
k v k e 不成立，
所以彼得森圖非帄面圖。（3分）
二、 邏輯推演 16% 1、 證明：
①A P （附加前提） ②B A ∨
T ①I ③D C B A ∧→∨ P ④D C ∧ T ②③I ⑤D T ④I ⑥E D ∨ T ⑤I ⑦F E D →∨ P ⑧F T ⑥⑦I ⑨F A → CP
2、證明 ①)(x xP ? P （附加前提） ②)(c P
US ① ③))()((x Q x P x →? P ④)()(c Q c P → US ③ ⑤)(c Q T ②④I ⑥)(x xQ ?
UG ⑤ ⑦)()(x xQ x xP ?→?
CP
三、 計算 18% 1、 解：
???????
?
?=0000100001010010
R M ， ???
????
??==0000000
0101
0010
12R R R M M M
??
?
??
??
??==000000000101
10102
3R R R M M M ，
??
?
??
?
?
?
?==000000001010
01013
4R R R M M M ??
?
??
??
?
?=+++=0000100011111111
4
32)(R R R R R t M M M M M
∴ t (R)={ , , < a , c> , , , < b ,b > , < b , c . > ,
< b , d > , < c , d > }
2、 解： 用庫斯克（Kruskal ）演算法求產生的最優樹。演算法略。結果如圖：
樹權C(T)=23+1+4+9+3+17=57即為總造價。
試卷二試題與答案
一、填空 20% （每小題2分）
1、 P ：你努力，Q ：你失敗。“除非你努力，否則你將失敗”的翻譯為
；“雖然你努力了，但還是失敗了”的翻譯為 。 2、論域D={1，2}，指定謂詞P
則公式x ??真值為 。 2、 設S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，則由B 31所表達的子集是 。
3、 設A={2，3，4，5，6}上的二元關係}|,{是质数
x y x y x R ∨<><=，則R=
（列舉法）。
R 的關係矩陣M R =
。
5、設A={1，2，3}，則A 上既不是對稱的又不是反對稱的關係
R= ；A 上既是對稱的又是反對稱的關係R= 。
6、設代數系統，其中A={a ，b ，c},
則么元是 ；是否有冪等 性 ；是否有對稱性 。
群或 群。 8、下面偏序格是分配格的是 。
9、n 個結點的無向完全圖K n 的邊數為 ，歐拉圖的充要條件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())((的根樹表示為
。
二、選擇 20% （每小題2分）
1、在下述公式中是重言式為（ ）
A 〃)()(Q P Q P ∨→∧；
B 〃))()(()(P Q Q P Q P →∧→??；
C 〃Q Q P ∧→?)(；
D 〃)(Q P P ∨→。
2、命題公式 )()(P Q Q P ∨?→→? 中極小項的個數為（ ），成真賦值的個數
為（ ）。
A 〃0；
B 〃1；
C 〃2；
D 〃3 。
3、設}}2,1{},1{,{Φ=S ，則 S
2 有（ ）個元素。
A 〃3；
B 〃6；
C 〃7；
D 〃8 。 4、 設} 3 ,2 ,1 {=S ，定義S S ?上的等價關係
},,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=則由 R 產 生
的S S ?上一個劃分共有（ ）個分塊。
A 〃4；
B 〃5；
C 〃6；
D 〃9 。 5、設} 3 ,2 ,1 {=S ，S 上關係R 的關係圖為
則R 具有（ ）性質。
A 〃自反性、對稱性、傳遞性；
B 〃反自反性、反對稱性；
C 〃反自反性、反對稱性、傳遞性；
D 〃自反性 。 6、設 ,+ 為普通加法和乘法，則（ ）>+< ,,S 是域。 A 〃},,3|{Q b a b a x x S ∈+== B 〃},,2|{Z b a n x x S ∈==
C 〃},
12|{Z n n x x S ∈+== D 〃}0|{≥∧∈=x Z x x S = N 。
7、下面偏序集（ ）能構成格。
8、在如下的有向圖中，從V 1到V 4長度為3 的道路有（ ）條。
A 〃1；
B 〃2；
C 〃3；
D 〃4 。
9、在如下各圖中（ ）歐拉圖。
10
、設R 是實數集合，“?”為普通乘法，則代數系統
A 〃群；
B 〃獨異點；
C 〃半群 。
三、證明 46%
1、 設R 是A 上一個二元關係，
)},,,(),(|,{R b c R c a A c A b a b a S >∈<>∈<∈∧∈><=且有对于某一个試證
明若R 是A 上一個等價關係，則S 也是A 上的一個等價關係。（9分）
2、 用邏輯推理證明：
所有的舞蹈者都很有風度，王華是個學生且是個舞蹈者。因此有些學生很有風度。（11分）
3、 若B A f →:是從A 到B 的函數，定義一個函數A
B g 2:→對任意B b ∈有
)})(()(|{)(b x f A x x b g =∧∈=，證明：若f 是A 到B 的滿射，則g 是從B 到 A 2
的單射。（10分）
4、 若無向圖G 中只有兩個奇數度結點，則這兩個結點一定連通。（8分）
5、 設G 是具有n 個結點的無向簡單圖，其邊數
2)2)(1(21
+--=
n n m ，則G 是
Hamilton 圖（8分）
四、計算 14%
1、 設
試求出
2、 權數1，4，9，16，25，36，49，64，81，100構造一棵最優二叉樹。（7分）
試卷二答案：
一、 填空 20%（每小題2分）
1、Q P →?；Q P ∧
2、T
3、},,,,{876540001111131a a a a a B B ==
4、
R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,
3>,<5,4>,<5,5>,<5,6>}；???
?
??
??
??00000
11111110001111111111 5、R={<1,2>,<1,3>,<2,1>}；
R={<1,1>,<2,2>,<3,3>} 6、a ；否；有 7、Klein 四元群；迴圈群 8、 B 9、
)1(21
-n n ；圖中無奇度結點且連通 10 、
二、
三、 證明 46%
1、（9分）
（1） S 自反的
A a ∈?，由R 自反，),(),(R a a R a a >∈<∧>∈<∴，S a a >∈∴<,
（2） S 對稱的
传递
对称定义R S
a b R R b c R c a S R b c R c a S b a A
b a >∈?<>∈<∧>∈∈<∧>∈∈<∈?,),(),()
,(),(,,
（3） S 傳遞的
定义
传递S S
c a R R c b R b a R c e R e b R b
d R d a S
c b S b a A
c b a >∈?<>∈<∧>∈∈<∧>∈<∧>∈<∧>∈∈<∧>∈<∈?,),(),(),(),(),(),(,,,,
由（1）、（2）、（3）得；S 是等價關係。 2、11分
證明：設P(x)：x 是個舞蹈者； Q(x) ：x 很有風度； S(x)：x 是個學生； a ：王華 上述句子符號化為：
前提：))()((x Q x P x →?、)()(a P a S ∧ 結論：))()((x Q x S x ∧? ……3分
①)()(a P a S ∧ P ②))()((x Q x P x →? P ③)()(a Q a P → US ② ④)(a P T ①I ⑤).(a Q T ③④I ⑥)(a S T ①I ⑦)()(a Q a S ∧ T ⑤⑥I ⑧)()((x Q x S x ∧? EG ⑦
……11分
３、１0分
證明 ：)(,,2121b b B b b ≠∈?A a a f ∈?∴21,满射
21212211,),()(,)(,)(a a f a f a f b a f b a f ≠∴≠==是函数由于且使 )
()()(),()(),()}
)(()(|{)()},)(()(|{)(21122122112211b g b g b g a b g a b g a b g a b x f A x x b g b x f A x x b g ≠∴??∈∈∴=∧∈==∧∈=但又
为单射任意性知由g b b ,,21。
4、8分
證明：設G 中兩奇數度結點分別為u 和v ，若 u ，v 不連通，則G 至少有兩個連通分支G 1、G 2 ，使得u 和v 分別屬於G 1和G 2，於是G 1和G 2中各含有1個奇數度結點，這與圖論基本定理矛盾，因而u ，v 一定連通。
5、8分
證明： 證G 中任何兩結點之和不小於n 。
反證法：若存在兩結點u ，v 不相鄰且1)()(-≤+n v d u d ,令},{1v u V =，則G-V 1
是具有n-2個結點的簡單圖，它的邊數
)1(2)2)(1(21
'--+--≥
n n n m ,可得
1)3)(2(21
'+--≥
n n m ，這與G 1=G-V 1為n-2個結點為簡單圖的題設矛盾，因而G
中任何兩個相鄰的結點度數和不少於n 。 所以G 為Hamilton 圖.
四、
計算 14%
1、 7分
解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z 6},+6> {[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]} {[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]} {[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]} Z 6的左陪集：Z 6 。
2、 7分
試卷三試題與答案
一、 填空 20% （每空 2分）
1、 設 f ，g 是自然數集N 上的函數x x g x x f N x 2)(,1)(,
=+=∈?，
則=)(x g f 。
2、 設A={a ，b ，c}，A 上二元關係R={< a, a > , < a, b >,< a, c >, < c, c>} ,
則s （R ）= 。
3、 A={1，2，3，4，5，6}，A 上二元關係}|,{是素数y x y x T ÷><=，則用列舉
法
T= ； T 的關係圖為
； T 具有 性質。 4、 集
合
}}
2{},2,{{Φ=A 的冪集
A 2= 。
5、 P ，Q 真值為0 ；R ，S 真值為1。則))()(())((S R Q P S R P wff ∧∧∨→∨∧的
真值為 。 6、 R
R Q P wff →∨∧?))((的
主
合
取
範
式
為 。
7、 設 P （x ）：x 是素數， E(x)：x 是偶數，O(x)：x 是奇數 N (x,y)：x 可以整數y 。
則謂詞))),()(()((x y N y O y x P x wff ∧?→?的自然語言是
。 8、 謂詞)),,()),(),(((u y x uQ z y P z x P z y x wff ?→∧???的前束範式為
。
二、 選擇 20% （每小題 2分）
1、 下述命題公式中，是重言式的為（ ）。
A 、)()(q p q p ∨→∧；
B 、))())(()(p q q p q p →∧→??；
C 、q q p ∧→?)(；
D 、q p p ??∧)(。 2、 r q p wff
→∧?)(的主析取範式中含極小項的個數為（ ）。
A 、2；
B 、 3；
C 、5；
D 、0；
E 、 8 。 3、 給定推理
①))()((x G x F x →? P ②)()(y G y F → US ① ③)(x xF ? P ④)(y F ES ③ ⑤)(y G T ②④I ⑥)(x xG ?
UG ⑤
)())()((x xG x G x F x ??→?∴
推理過程中錯在（ ）。
A 、①->②;
B 、②->③;
C 、③->④;
D 、④->⑤;
E 、⑤->⑥
4、 設S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}，
S 5={3，5}，在條件31S X S X ??且下X 與（ ）集合相等。 A 、 X=S 2或S 5 ； B 、X=S 4或S 5；
C 、X=S 1，S 2或S 4；
D 、X 與S 1，…，S 5中任何集合都不等。 5、 設
R
和
S
是
P
上的關係，P
是所有人的集合，
},|,{的父亲是y x P y x y x R ∧∈><=，}
,|,{的母亲是y x P y x y x S ∧∈><=則R S
1
-表示關係 （ ）。
A 、},|,{的丈夫是y x P y x y x ∧∈><；
B 、},|,{的孙子或孙女
是y x P y x y x ∧∈><； C 、 Φ； D 、},|,{的祖父或祖母
是y x P y x y x ∧∈><。 6、 下面函數（ ）是單射而非滿射。
A 、12)(,:2-+-=→x x x f R R f ；
B 、x x f R Z
f ln )(,
:=→+
；
C 、的最大整数表示不大于x x x x f Z R f ][],[)(,:=→；
D 、12)(,
:+=→x x f R R f 。
其中R 為實數集，Z 為整數集，R +，Z +分別表示正實數與正整數集。 7、 設S={1，2，3}，R 為S 上的關係，其關係圖為
則R 具有（ ）的性質。
A 、 自反、對稱、傳遞；
B 、什麼性質也沒有；
C 、反自反、反對稱、傳遞；
D 、自反、對稱、反對稱、傳遞。 8、 設}}2,1{},1{,{Φ=S ，則有（ ）S ?。
A 、{{1,2}} ；
B 、{1,2 } ；
C 、{1} ；
D 、{2} 。 9、 設A={1 ,2 ,3 }，則A 上有（ ）個二元關係。
A 、23
； B 、32
； C 、322； D 、2
32。 10、全體小項合取式為（ ）。
A 、可滿足式；
B 、矛盾式；
C 、永真式；
D 、A ，B ，C 都有可能。
三、 用CP 規則證明 16% （每小題 8分）
1、F A F E D D C B A →?→∨∧→∨,
2、)()())
()((x xQ x xP x Q x P x ?∨??∨?
四、（14%）
集合X={<1,2>, <3,4>, <5,6>,… }，R={<
五、（10%）
設集合A={ a ,b , c , d }上關係R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、寫出R 的關係矩陣和關係圖。（4分） 2、用矩陣運算求出R 的傳遞閉包。（6分）
六、（20%）
1、（10分）設f 和g 是函數，證明g f ?也是函數。
2、（10分）設函數S T f T S g →→::，證明 S T f →:有一左逆函數當且僅當f 是
入射函數。 答案：
五、 填空 20%（每空2分）
1、2(x+1)；
2、}a , c ,a , b ,c , c ,c , a ,b , a ,a , a {><><><><><><；
3、
>}<><><><><><3,6,2,6,2,4,5,1,3,1,2,1{；
4、
反對稱性、反自反性；4、}}}2{},2,{{}},2{{}},2,{{,{ΦΦΦ；5、1；
6、)()()(R Q P R Q P R Q P ∨∨∧∨∨?∧∨?∨；
7、任意x ，如果x 是素數則存在一個y ，y 是奇數且y 整除x ；
8、)),,(),(),((u y x Q z y P z x P u z y x ∨?∨?????。
六、 選擇 20%（每小題 2分）
七、 證明 16%(每小題8分) 1、 ①A P （附加前提） ②B A ∨
T ①I ③D C B A ∧→∨ P ④D C ∧ T ②③I ⑤D T ④I ⑥E D ∨
T ⑤I
⑦F E D →∨ P ⑧F T ⑥⑦I ⑨F A → CP
2、
)()(())()(()()()()()(x xQ x xP x Q x P x x xQ x P x x xQ x xP ?→???∨??→????∨?本题可证
① ))((x xP ?? P （附加前提） ②))((x P x ?? T ①E ③)(a P ?
ES ② ④))()((x Q x P x ∨? P ⑤)()(a Q a P ∨ US ④ ⑥)(a Q T ③⑤I ⑦)(x xQ ?
EG ⑥ ⑧)()((x xQ x xP ?→?? CP
八、 14% （1） 證明：
1、
自反性：y x y x X y x +=+>∈>∈<><<∴,,,
2、
對稱性：X y x X y x >∈∈
时当R y x y x >>∈<><<2211,,, 21121221y x y x y x y x +=++=+也即即
有对称性故R R y x y x >>∈<><<1122,,,
3、
傳遞性：X y x X
y x X y x >∈∈∈
时且当R y x y x R y x y x >>∈<><<>>∈<><<33222211,,,,,,
???+=++=+)2()1(23321221
y x y x y x y x 即
23123221)
2()1(y x y x y x y x +++=++++
即1331y x y x +=+
有传递性故R R y x y x >>∈<><<3311,,,
由（1）（2）（3）知：R 是X 上的先等價關係。
2、X/R=}]2,1{[R >< 九、 10%
1、??
?
??
??
??=0000100001010010
R M ； 關係圖
2、
??
?
??
??
??==000000001010
01012
R R R M M M
??
?
??
??
??==000000000101
10102
3R R R M M M
2
3
4000000001010
0101R R R R M M M M =??
?
?
?
??
?
?==
,,4635R R R R M M M M == ??
?
??
??
?
?=+++=0000100011111111
4
32)(R R R R R t M M M M M
∴ t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d
> }。
六、 20%
1、（1）
)}
()(|,{)}
()(|,{x g x f y domg domf x y x x g y x f y domg x domf x y x g f ==∧?∈><==∧=∧∈∧∈><=?
)}()(,|{x g x f domg domf x x domh g domf g
f h =?∈==?∴?=令
（2）)}()()(|,{x g x f x h y domg domf x y x h ===∧?∈><=
使得若有对21,y y domh x ∈ )()()(,
)()()(21x g x f x h y x g x f x h y ======
21,)(y y g f =有是函数或由于)(x h y y domh x =∈?使得有唯一即 也是函数g f ?∴。
2、證明：
t t f g T t g f =∈??)(,"" 则对有一左逆若
是入射所以是入射故f f g , 。 的左逆元
是故则且若或只有一个值则对令若此时令使入射由定义如下是入射f g t s g t f g s t f c t s g S s T c s g T f s t s g s t f T t f T f s S T f f ,)()()()(,)()(,)()(,|,),(:
:,
""===∈?∈=?==∈?∈?→?
左逆函数为使必能构造函数入射即若f g g f ,,。
試卷四試題與答案
一、 填空 10% （每小題 2分）
1、 若P ，Q ，為二命題，Q P →真值為0 當且僅當 。
2、 命題“對於任意給定的正實數，都存在比它大的實數”令F(x)：x 為實數，
y
x y x L >:),(則命題的邏輯謂詞公式
為 。 3、 謂
詞
合
式
公
式
)
()(x xQ x xP ?→?的前束範式
為 。
4、 將量詞轄域中出現的 和指導變元交換為另一變元符號，公式其餘
的部分不變，這種方法稱為換名規則。
5、 設x 是謂詞合式公式A 的一個客體變元，A 的論域為D ，A(x)關於y 是自由的，則
被稱為存在量詞消去規則，記為
ES 。
二、 選擇 25% （每小題 2.5分）
1、 下列語句是命題的有（ ）。
A 、 明年中秋節的晚上是晴天；
B 、0>+y x ；
C 、0>xy 當且僅當x 和y 都大於0；
D 、我正在說謊。
2、 下列各命題中真值為真的命題有（ ）。
A 、 2+2=4當且僅當3是奇數；
B 、2+2=4當且僅當3不是奇數；
C 、2+2≠4當且僅當3是奇數；
D 、2+2≠4當且僅當3不是奇數；
3、 下列符號串是合式公式的有（ ）
A 、Q P ?；
B 、Q P P ∨?；
C 、)()(Q P Q P ?∨∧∨?；
D 、)(Q P ??。 4、 下列等價式成立的有（ ）。
A 、P Q Q P ?→??→；
B 、R R P P ?∧∨)(；
C 、 Q Q P P ?→∧)(；
D 、R Q P R Q P →∧?→→)()(。 5、 若n A A A 21,和B 為wff ，且B A A A n ?∧∧∧ 21則（ ）。 A 、稱n A A A ∧∧∧ 21為B 的前件； B 、稱B 為n A A A 21,的有效結論 C 、當且僅當
F
B A A A n ?∧∧∧∧ 21；D 、當且僅當
F B A A A n ??∧∧∧∧ 21。
6、 A ，B 為二合式公式，且B A ?，則（ ）。
A 、
B A →為重言式； B 、*
*B A ?；
C 、B A ?；
D 、*
*B A ?； E 、B A ?為重言式。
7、 “人總是要死的”謂詞公式表示為（ ）。 （論域為全總個體域）M(x)：x 是人；Mortal(x)：x 是要死的。 A 、)()(x Mortal x M →； B 、)()(x Mortal x M ∧ C 、))()((x Mortal x M x →?；D 、))()((x Mortal x M x ∧?
8、 公式))()((x Q x P x A →?=的解釋I 為：個體域D={2}，P(x)：x>3, Q(x)：x=4則A
的真值為（ ）。
A 、1；
B 、0；
C 、可滿足式；
D 、無法判定。 9、 下列等價關係正確的是（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、Q x xP Q x P x →??→?)())((； D 、Q x xP Q x P x →??→?)())((。 10、 下列推理步驟錯在（ ）。 ①))()((x G x F x →? P ②)()(y G y F → US ① ③)(x xF ? P ④)(y F
ES ③
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).
离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (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 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分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())
下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（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∪I A＝{<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－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： 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的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,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→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（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)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(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))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分）
离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→?Q （B）P∨?Q （C）P∧Q （D）P∧?Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定 是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。
（A）永真式（B）永假式（C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ? （B）0 ? （C）0∈? （D）0?? 6、以下哪个不是集合A上的等价关系的性质？（） ）。 （A）2 （B）4 （C）3 （D）5 10．连通图G是一棵树，当且仅当G中（）。 （A）有些边不是割边（B）每条边都是割边 （C）无割边集（D）每条边都不是割边
二、填空题（2*10） 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D是正整数集合，则命题?x?y(xy=y)的真值是______。 3、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 4 5 6、设 7 8 (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下 五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：
《离散数学》模拟题（补） 一．单项选择题 1．下面四组数能构成无向图的度数列的有( )。 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。 2．图的邻接矩阵为( )。 A、； B、； C、； D、。 3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 4．下列图中是欧拉图的有( )。 5.下述命题公式中，是重言式的为（）。 A、； B、； C、； D、。 6.的主析取范式中含极小项的个数为（）。 A 、2； B、 3； C、5； D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) (
7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在（ ）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件 下X 与（ ）集合相等。 A 、X=S 2或S 5 ； B 、X=S 4或S 5； C 、X=S 1，S 2或S 4； D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合， ， 则表示关系 （ ） 。 A 、； B 、 ； C 、 ； D 、 。 10.下面函数（ ）是单射而非满射。 A 、 ； B 、 ； C 、 ； D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f
离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：
((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： * a b c d A B C
a b c d a b c d b c d a c d a b d a b c ，有逆元的元素为 ，它们的 逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A ． 23 ； B ． 32 ； C ． 332?； D ． 223?。 4、设R ，S 是集合A 上的关系，则下列说法正确的是（ ） A ．若R ，S 是自反的， 则S R ο是自反的； B ．若R ，S 是反自反的， 则S R ο是反自反的； C ．若R ，S 是对称的， 则S R ο是对称的； D ．若R ，S 是传递的， 则S R ο是传递的。 5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下 |}||(|)(,|,{t s A p t s t s R =∧∈><=则P （A ）/ R=（ ） A ．A ； B ．P(A) ； C ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D ．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“?”的哈斯图为（ ）
《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44
离散数学（上）模拟题 1、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化 a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 b) 我今天进城，除非下雨。 c) 仅当你走，我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 b) 对于所有非零实数x，总存在y使得xy=1。 c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得 f(a)=b. 2、简答题（共6道题，共32分） 1. 求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范 式，并写出所有成真赋值。（5分） 2. 设个体域为{1,2,3}，求下列命题的真值（4分） a) xy(x+y=4) b) yx (x+y=4) 3. 求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） 4. 判断下面命题的真假，并说明原因。（每小题2分，共4分） a) （AB）－C=(A-B) (A-C) b) 若f是从集合A到集合B的入射函数，则|A|≤|B| 5. 设A是有穷集，|A|=5，问（每小题2分，共4分） a) A上有多少种不同的等价关系？ b) 从A到A的不同双射函数有多少个？ 6. 设有偏序集
下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即 可）(6分) 3、证明题（共3小题，共计40分） 1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10 分） a) A→(B∧C),(E→F)→C, B→(A∧S)B→E b) x(P(x)→Q(x)), x(Q(x)∨R(x))，xR(x) xP(x) 2. 设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠，关系R 满足：<
常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={
1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨) ()(Q P Q P Q P ?∧?∨∧??Q) P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?
①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)(
第1章 一.填空题 1. 2. 公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。 3. 4. 5. 6. 7. 全体小项的析取式必为____________________式。 8. P,Q为两个命题，则德摩根律可表示为7. 全体小项的析取式必为_________式。 9. P,Q为两个命题，则吸收律可表示为____________________ 。 10. 设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为_____ _______________。 11. 设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为_________ ___________。 12. 13. 14. 15. 设P、Q为两个命题，交换律可表示为____________________。 16. 17. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为____________________ 。
18. 19. 20. 21. P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为_______________ _____。 22. 23. 24. 一个重言式和一个矛盾式的合取是____________________。 25. 全体小项的析取式为____________________ 。 26. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为____________________。 27. 28. 设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为____________________。 29. 30. 二.选择题 1. 2. 3. 在除﹁之外的四大联结词中，满足结合律的有几个( )。 A. 2 B.3 C. 4 D. 1 4. 判断下列语句哪个是命题( )。 A.你喜欢唱歌吗？ B.若7+8＞18，则三角形有4条边。 C.前进！ D. 给我一杯水吧！
02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={
5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集