离散数学重修习题集
第一、二章
1）判断下列公式哪些是合式公式，哪些不是合式公式。
⑴(P∧Q→R)
⑵(P∧(Q→R)
⑶((?P→Q)?(R∨S))
⑷(P∧Q→RS)
⑸((P→(Q→R))→((Q→P)?Q∨R))。
解：⑴⑶⑸是合式公式；⑵⑷不是合式公式。
2）设P：天下雪。
Q：我将进城。
R：我有时间。
将下列命题符号化。
⑴天没有下雪，我也没有进城。
⑵如果我有时间，我将进城。
⑶如果天不下雪而我又有时间的话，我将进城。
解：⑴?P∧?Q
⑵ R→Q
⑶?P∧R→Q
3）用符号形式写出下列命题。
⑴假如上午不下雨，我去看电影，否则就在家里读书或看报。
⑵我今天进城，除非下雨。
⑶仅当你走，我将留下。
解：
⑴P：上午下雨；Q：我去看电影；R：我在家读书；S：我在家看报；原命题符号化为：（?P→Q）∧（P→R∨S）。
⑵P：我今天进城；Q：天下雨；原命题符号化为：?Q→P。
⑶P：你走；Q：我留下；原命题符号化为：Q→P。
4）用等价演算证明下列命题公式是否为重言式。
⑴(P∧(P→Q))→Q
??(P∧(?P∨Q))∨Q
?(?P∨(P∧?Q))∨Q
?((?P∨P)∧(?P∨?Q))∨Q
?(?P∨?Q)∨Q
?T
⑵(?Q∧(P→Q))→?P
?(?Q∧(?P∨Q))→?P
??(?Q∧(?P∨Q))∨?P
?(Q∨(P∧?Q))∨?P
?(?P∨Q)∨(P∧?Q)
??(P∧?Q)∨(P∧?Q)
?T
⑶(?P∧(P∨Q))→Q
?(?P∧Q)→Q
??(?P∧Q)∨Q
?P∨?Q∨Q
?T
⑷((P→Q)∧(Q→R))→(P→R)
??((?P∨Q)∧(?Q∨R))∨(?P∨R)
?(P∧?Q)∨(Q∧?R)∨(?P∨R)
?(P∧?Q)∨((?P∨Q∨R)∧(?P∨?R∨R))
?(P∧?Q)∨(?P∨Q∨R)
?(?P∨Q∨R∨P)∧(?P∨Q∨R∨?Q)
?T
5）写出下列命题公式的对偶式。
⑴?(?P∧?Q)∧R的对偶式是：?(?P∨?Q)∨R
⑵ (P∨?Q)∧(R∨P)对偶式是(P∧?Q)∨(R∧P)
⑶ P→((Q→R)∧(P∧?Q))
??P∨((?Q∨R)∧(P∧?Q))
?(?P∨?Q)∧(?P∨?Q∨R)
所以P→((Q→R)∧(P∧?Q))的对偶式是(?P∧?Q)∨(?P∧?Q∧R)
⑷ (P?Q)→R
??(P?Q)∨R
??(P→Q)∨?(Q→P)∨R
??(?P∨Q)∨?(?Q∨P)∨R
?(P∧?Q)∨(?P∧Q)∨R
所以(P?Q)→R的对偶式是(P∨?Q)∧(?P∨Q)∧R
6）写出下列命题公式的主析取范式和主合取范式
⑴ (P→Q)∧(Q→R)
?(?P∨Q)∧(?Q∨R)
?((?P∨Q)∧?Q)∨((?P∨Q)∧R)
?(?P∧?Q)∨(?P∧R)∨(Q∧R)
?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧?Q∧R)∨(?P∧Q∧R)∨(?P∧Q ∧R)∨(P∧Q∧R)
?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R)(主析取范式) ?∑0,1,3,7
?∏2,4,5,6
?(P∨?Q∨R)∧(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R)(主合取范式)
⑵?(?P∨?Q)∨R
?(P∧Q)∨R
?(P∧Q∧R)∨(P∧Q∧?R)∨(P∧R)∨(?P∧R)
?(P∧Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)∨(P∧?Q∧R)∨(?P∧Q∧R)∨(?P ∧?Q∧R)
?(P∧Q∧R)∨(P∧Q∧?R)∨(P∧?Q∧R)∨(?P∧Q∧R)∨(?P∧?Q∧R)(主析取范式)
?∑1,3,5,6,7
?∏0,2,4
?(P∨Q∨R)∧(P∨?Q∨R)∧(?P∨Q∨R)(主合取范式)
7）推理理论证明题：
⑴ P∧Q，(P?Q)→(T∨S)?(T∨S)
证明:
⑴P∧Q P
⑵P T⑴
⑶Q T⑴
⑷P→Q T⑶
⑸Q→P T⑵
⑹(P→Q)∧(Q→P) T⑷⑸
⑺P?Q T⑹
⑻(P?Q)→(T∨S) P
⑼T∨S T⑺⑻
⑵?(P→Q)→?(R∨S)，(Q→P)∨?R,R?P?Q
证明:
⑴R P
⑵(Q→P)∨?R P
⑶Q→P T⑴⑵析取三段论
⑷R∨S T⑴附加律
⑸?(P→Q)→?(R∨S) P
⑹P→Q T⑷⑸拒取式
⑺(P→Q)∧(Q→P) T⑶⑹合取引入
⑻P?Q T⑹双条件等价式
⑶?P∨?S，R→S??P∨?R
证明:
⑴?(?P∨?R) P(附加前提)
⑵P∧R T⑴条件等价式
⑶P T⑵化简律
⑷R T⑵化简律
⑸R→S P
⑹S T⑷⑸假言推理
⑺?P∨?S P
⑻?P T⑹⑺析取三段论
⑼?P∧P(矛盾) T⑶⑻合取引入
⑷ P→(Q∧R)，?Q∨S，(T→?U)→?S?Q→T
证明:
⑴Q P(附加前提)
⑵?Q∨S P
⑶S T⑴⑵析取三段论
⑷(T→?U)→?S P
⑸?(T→?U) T⑶⑷拒取式
⑹?(? T∨?U) T⑸条件等价式
⑺T∧U T⑹德·摩根律
⑻T T⑺化简律
⑼Q→T CP规则
⑸证明下面各命题推得的结论是有效的：如果今天是星期三，那么我有一次离散数学或数字逻辑测验。如果离散数学课老师有事，那么没有离散数学测验。今天是星期三且离散数学老师有事。所以，我有一次数字逻辑测验。
证明：设P：今天是星期三。
Q：我有一次离散数学测验。
R：我有一次数字逻辑测验。
S：离散数学课老师有事。
该推理就是要证明：P→(Q∨R)，S→?Q，P∧S?R
⑴P∧S P
⑵P T⑴化简律
⑶S T⑴化简律
⑷S→?Q P
⑸?Q T⑶⑷假言推理
⑹P→(Q∨R) P
⑺Q∨R T⑵⑹假言推理
⑻R T⑸⑺析取三段论
8）将下列命题符号化。并讨论它们的真值。
(1) 有些实数是有理数。
解：设R(x)：x是实数。Q(x)：x是有理数。
“有些实数是有理数。”符号化为：(?x)(R(x)∧Q(x))
它的真值为：真。
(2) 凡是人都要休息。
解：设R(x)：x是人。S(x)：x要休息。
“凡是人都要休息。”符号化为：(?x)(R(x)→S(x))
它的真值为：真。
(3) 每个自然数都有比它大的自然数。
解：设N(x)：x是自然数。G(x,y)：x比y大。
“每个自然数都有比它大的自然数。”符号化为：(?x)(N(x)→(?y)(N(y)∧G(y,x))) 它的真值为：真。
(4) 乌鸦都是黑的。
解：设A(x)：x是乌鸦。B(x)：是黑的。
“乌鸦都是黑的。”符号化为：(?x)(A(x)→B(x))
它的真值为：真。
(5) 不存在比所有火车都快的汽车。
解：设A(x)：x是汽车。B(x)：是火车。K(x,y)：x比y快。
“不存在比所有火车都快的汽车。”符号化为：?(?x)(A(x)∧(?y)(B(y)→K(x,y))) 它的真值为：真。
(6) 有些大学生不佩服运动员。
解：设S(x)：x是大学生。L(x)：是运动员。B(x,y)：x佩服y。
“有些大学生不佩服运动员。”符号化为：(?x)(S(x)∧L(y)∧?B(x,y))
它的真值为：真。
(7) 有些女同志既是教练员又是运动员。
解：设W(x)：x是女同志。J(x)：x是教练员。L(x)：x是运动员。
“有些女同志既是教练员又是运动员。”符号化为：(?x)(W(x)∧J(x)∧L(x))
它的真值为：真。
(8) 除2以外的所有质数都是奇数。
解：设A(x)：x是质数。B(x)：x是奇数。C(x,y)：x不等于y。
“除2以外的所有质数都是奇数。”符号化为：(?x)(A(x)∧C(x,2)→B(x))
它的真值为：真。
9）谓词推理理论
⑴(?x)(F(x)→(G(y)∧R(x)))，(?x)F(x)?(?x)(F(x)∧R(x))
证明：
⑴ (?x)F(x) P
⑵ F(c) ES⑴
⑶ (?x)(F(x)→(G(y)∧R(x))) P
⑷ F(c)→(G(y)∧R(c)) US⑶
⑸ G(y)∧R(c) T⑵⑷假言推理
⑹ R(c) T⑸化简律
⑺ F(c)∧R(c) T⑵⑹合取引入
⑻ (?x)(F(x)∧R(x)) EG⑺
⑵(?x)(F(x)→G(x))，(?x)(R(x)→?G(x))?(?x)(R(x)→? F(x))
证明：
⑴ (?x)(R(x)→?G(x)) P
⑵ R(c)→?G(c) US⑴
⑶ (?x)(F(x)→G(x))P
⑷ F(c)→G(c)US⑶
⑸?G(c)→?F(c) T⑷假言易位式
⑹ R(c)→?F(c) T⑵⑸假言三段论
⑺ (?x)(R(x)→?F(x)) UG⑹
⑶(?x)(F(x)∨G(x))，(?x)(G(x)→?R (x))，(?x)R(x)?(?x)F(x)
证明：
⑴ (?x)R(x) P
⑵ R(c) US⑴
⑶ (?x)(G(x)→?R(x)) P
⑷ G(c)→?R(c) US⑶
⑸?G(c) T⑵⑷拒取式
⑹ (?x)(F(x)∨G(x)) P
⑺ F(c)∨G(c) US⑹
⑻ F(c) T⑸⑺析取三段论
⑼ (?x)F(x) UG⑻
⑷(?x)(F(x)→R(x))?(?x)F(x)→(?x)R(x)
证明：
⑴ (?x)F(x) P(附加前提)
⑵ F(c) US⑴
⑶ (?x)(F(x)→R(x)) P
⑷ F(c)→R(c) US⑶
⑸ R(c) T⑵⑷假言推理
⑹ (?x)R(x) UG⑸
⑺ (?x)F(x)→(?x)R(x) CP
⑸ (?x)(F(x)∨G(x))，?(?x)(G(x)∧R(x))?(?x)R(x)→(?x)F(x)
证明：
⑴ (?x)R(x) P(附加前提)
⑵ R(c) US⑴
⑶?(?x)(G(x)∧R(x)) P
⑷ (?x)?(G(x)∧R(x)) T⑶量词否定等价式
⑸?(G(c)∧R(c)) US⑷
⑹?G(c)∨?R(c) T⑸德摩根律
⑺?G(c) T⑵⑹析取三段论
⑻ (?x)(F(x)∨G(x)) P
⑼ F(c)∨G(c) US⑻
⑽ F(c) T⑺⑼析取三段论
⑾ (?x)F(x) UG⑽
⑿ (?x)R(x)→(?x)F(x) CP
⑹ (?x)(F(x)∨G(x))?(?x)F(x)∨(?x)G (x)
证明：
⑴?((?x)F(x)∨(?x)G (x)) P(附加前提)
⑵?(?x)F(x)∧?(?x)G (x)) T⑴德摩根律
⑶ (?x)?F(x)∧(?x)?G (x)) T⑵量词否定等价式
⑷ (?x)?F(x) T⑶化简律
⑸?F(c) ES⑷
⑹ (?x)?G(x)) T⑶化简律
⑺?G(c) US⑹
⑻ (?x)(F(x)∨G(x)) P
⑼ F(c)∨G(c) US⑻
⑽ F(c) T⑺⑼析取三段论
⑾ F(c)∧?F(c)(矛盾) T⑸⑽合取引入
⑺(?x)(F(x)∨G(x))，(?x)(G(x)→?R (x))，(?x)R(x)?(?x)F(x)
证明：
⑴?(?x)F(x) P(附加前提)
⑵ (?x)?F(x) T⑴量词否定等价式
⑶?F(c) ES⑵
⑷ (?x)(F(x)∨G(x)) P
⑸ F(c)∨G(c) US⑷
⑹ G(c) T⑶⑸析取三段论
⑺ (?x)(G(x)→?R(x)) P
⑻ G(c)→?R(c) US⑺
⑼?R(c) T⑹⑻假言推理
⑽ (?x)R(x) P
⑾ R(c) US⑽
⑿ R(c)∧?R(c)(矛盾) T⑼⑾合取引入
⑻(?x)(F(x)→?G(x))，(?x)(G(x)∨R(x))，(?x)?R(x) ?(?x)?F(x)
证明：
⑴ (?x)?R(x) P
⑵?R(c) ES⑴
⑶?(?x)?F(x) P(附加前提)
⑷ (?x)F(x) T⑶量词否定等价式
⑸ F(c) US⑷
⑹ (?x)(F(x)→?G(x)) P
⑺ F(c)→?G(c) US⑹
⑻?G(c) T⑸⑺假言推理
⑼ (?x)(G(x)∨R(x)) P
⑽ G(c)∨R(c) US⑼
⑾ R(c) T⑻⑽析取三段论
⑿ R(c)∧?R(c)(矛盾) T⑵⑾合取引入
⑼证明下面推理。
每个有理数都是实数。有的有理数是整数。因此，有的实数是整数。
解：首先将命题符号化：
Q(x)：x是有理数。R(x)：x是实数。
Z(x)：x是整数。
本题要证明：(?x)(Q(x)→R(x)), (?x)(Q(x)∧Z(x))?(?x)(R(x)∧Z(x)) 证明：
⑴ (?x)(Q(x)∧Z(x)) P
⑵ Q(c)∧Z(c) ES⑴
⑶ Q(c) T⑵化简律
⑷ Z(c) T⑵化简律
⑸ (?x)(Q(x)→R(x)) P
⑹ Q(c)→R(c) US⑸
⑺ R(c) T⑶⑹假言推理
⑻ R(c)∧Z(c) T⑷⑺合取引入
⑼ (?x)(R(x)∧Z(x)) EG⑻
第三章
1）确定下列集合的幂集合。
⑴?a,b?
⑵??a,?b,c???
⑶??a,b?,?a,c??
⑷P( )
⑸P(P( ))
解：⑴? ,?a?,?b?,?a,b??
⑵? ,??a,?b,c????
⑶? ,??a,b??,??a,c??,??a,b?,?a,c???
⑷? ,? ??
⑸? ,? ?,?? ??,? ? ???
2）设全集E=?1,2,3,4,5,6?，A=?1,4?，B=?1,2,5?，C=?2,4?。求下列各集合。
⑴A∩~B
⑵ (A∩B)∪~C
⑶ ~ (A∩B)
⑷A⊕B
解：⑴A∩~B=?1,4?∩?3,4,6?=?4?
⑵(A∩B)∪~C=(?1,4?∩?1,2,5?)∪?1,3,5,6?=?1?∪?1,3,5,6?=?1,3,5,6?
⑶~ (A∩B)=~?1?=?2 3,4,5,6?
⑷A⊕B=(A∪B)－(A∩B)=?1,2,4,5?－?1?=?2,4,5?
3）设A,B,C,D是任意集合（*参考）
证明：
⑴A∪(B∩C)=(A∪B)∩(A∪C)
证明：x∈A∪(B∩C)? x∈A∨x∈B∩C
? x∈A∨(x∈B∧x∈C)
?(x∈A∨x∈B)∧(x∈A∨x∈C)
?(x∈A∨x∈B)∧(x∈A∨x∈C)
?x∈A∪B∧x∈A∪C
?x∈(A∪B)∩(A∪C)
所以A∪(B∩C)=(A∪B)∩(A∪C)
⑵A∩(B∪C)= (A∩B)∪(A∩C)
证明：x∈A∩(B∪C)? x∈A∧x∈B∪C
?x∈A∧(x∈B∨x∈C)
?(x∈A∧x∈B)∨(x∈A∧x∈C)
?x∈A∩B∨x∈A∩C
?x∈(A∩B)∪(A∩C)
所以A∩(B∪C)=(A∩B)∪(A∩C)
⑶ ~ (~A)=A
证明：x∈~ (~A)??(x∈~A)??(?x∈A)?x∈A
所以~ (~A)=A
⑷A∪E=E
证明：x∈A∪E?x∈A∨x∈E?x∈A∨T?T?x∈E
所以A∪E=E
⑸A∩~A=
证明：x∈A∩~A?x∈A∧x∈~A?x∈A∧?(x∈A)?F? x∈
所以A∩~A=
⑹A∪(A∩B)=A
证明：x∈A∪(A∩B)? x∈A∨x∈A∩B?x∈A∨(x∈A∧x∈B)?x∈A (吸收律) 所以A∪(A∩B)= A
⑺ ~(A∩B)=~A∪~B
证明：x∈~(A∩B)??(x∈A∩B)??(x∈A∧x∈B)??x∈A∨?x∈B
?x∈~A∨x∈~B?x∈~A∪~B
所以~ (A∩B)=~A∪~B
4）判断下列结论是否正确。
⑴若A∪B=A∪C，则B=C
解：不正确。反例，令A=?1,2,3?，B=?1,2?，C=?1?。A∪B=?1,2,3?=A∪C，但B≠C。
⑵若A∩B=A∩C，则B=C
解：不正确。反例，令A=?1?，B=?1,2?，C=?1,2,3?。A∩B=?1?=A∩C，但B≠C。5）设A=?a,b?，B=?1,2,3?，求：A×B，B×A，A×A，B×B和(A×B)∩( B×A)。
解：A×B=?
B×A=?<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>?
A×A=?
B×B=?<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>?
(A×B)∩(B×A)=
6）证明下列各题。
⑴如果A×A＝B×B，那么A＝B
证明：x∈A?x∈A∧x∈A?
⑵如果A×B＝A×C且A≠ ，那么B＝C
因为A≠ ，?x∈A，以下证明B＝C
y∈B?x∈A∧y∈B?
⑶ (A∩B)×(C∩D)＝(A×C)∩(B×D)
证明：
?x∈A∧x∈B∧y∈C∧y∈D
?x∈A∧y∈C∧x∈B∧y∈D
?
?
所以(A∩B)×(C∩D)＝(A×C)∩(B×D)
7）用列举法表示A到B的二元关系R，写出关系矩阵，画出关系图。
⑴A=?1,2,3,4,5?，B=?a,b,c?，R=?<1,a>,<1,b>,<2,b>,<3,a>?
⑵A=?a,b,c?，B=?1,2,3,4,5?，R=?
⑶ A =?0,1,2?，B =?0,2,4?，R =?| a ∈A ∧b ∈B ∧a ×b ∈A ∩B ?，其中×是普通乘法。
⑷ A =?1,2,3,4,5?，B =?1,2,3?，R =?| a ∈A ∧b ∈B ∧a =b 2?
解答：
⑴ M R =???????
? ??000
000001
010
011 R 关系图如图4.20所示。 ⑵
M R =????
? ??110000000000010
R 关系图如图4.21所示。
⑶ M R =??
?
?? ??001011111
R 关系图如图4.22所示。
⑷ M R =??
?????
?
??000
010********* R 关系图如图4.23所示。
8）设A =?1,2,3?，A 上二元关系定义为：
R =?<1,1>,<1,2>,<1,3>,<3,3>?
S =?<1,1>,<1,2>,<2,1>,<2,2>,<3,3>? T =?<1,1>,<1,2>,<2,2>,<2,3>? (空关系) A ×A (全域关系)
判断上述关系是否是⑴自反的，⑵对称的，⑶传递的，⑷反对称的。
解：各关系的自反性、对称性、传递性和对称性如表4.2所示。
9）设A =?1,2,3,4?，A 上二元关系R 定义为：
R =?<1,2>,<2,1>,<2,3>,<3,4>?
⑴ 求R 的自反闭包、对称闭包和传递闭包。
⑵ 用R 的关系矩阵和四阶单位阵求R 的自反闭包、对称闭包和传递闭包的关系矩阵。再由关系矩阵写出它们的集合表达式。
⑶ 根据R 的关系图，画出R 的自反闭包，对称闭包和传递闭包的关系图，再由关系图写出它们的集合表达式。 解答： ⑴
r(R )=?<1,2>,<2,1>,<2,3>,<3,4>,<1,1>,<2,2>,<3,3>,<4,4>? s(R )=?<1,2>,<2,1>,<2,3>,<3,4>,<3,2>,<4,3>? R 2=R R =?<1,1>,<1,3>,<2,2>,<2,4>? R 3=R 2 R =?<1,2>,<1,4>,<2,1>,<2,3>? R 4=R 2 R =?<1,1>,<1,3>,<2,2>,<2,4>?=R 2
t(R )=R ∪R 2∪R 3∪R 4= ?<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,4>? ⑵解：
M R =??
?
?
?
?
?
?
?00001000
01010010
M r(R )= M R ∨A I M =????
?
??
?
?00001000
0101
0010
∨???????
??1000010000100001=??
?
?
?
?
?
??1000
11000111
0011
r(R )=?<1,2>,<2,1>,<2,3>,<3,4>,<1,1>,<2,2>,<3,3>,<4,4>?
M s(R )= M R ∨T
R M =?????
??
?
?00001000
01010010∨???????
?
?010*********
0010=??
?
?
?
?
?
??0100
10100101
0010
s(R )= ?<1,2>,<2,1>,<2,3>,<3,4>,<3,2>,<4,3>?
=2
R M M R M R =??
?
??
?
?
?
?000010000101
0010
??????? ?
?0000100001010010=
??
?
?
?
??
??000000001010
0101
3R M =2
R M M R =??
?
??
??
??00000000
1010
0101
??????? ??00
001000010100
10
=??
????
?
??0000000001011010 4R M =3
R M M R =??
?
??
?
?
??00000000
0101
1010
??????? ??0000100001010010=
??
?
?
?
?
?
??000000001010
0101
M t(R )= M R ∨2R M ∨3R M ∨??
?
?
?
?
? ?
?=00001000111111114
R M
t(R )= ?<1,1>,<1,2>,<1,3>,<1,4>,<2,1>,<2,2>,<2,3>,<2,4>,<3,4>?
⑶R 的关系图如图4.30所示，R 的自反闭包、对称闭包和传递闭包的关系图如图4.31、图4.32和图4.33所示。
10）设R 是A 上的二元关系，证明：
⑴ R 是对称的当且仅当s(R )=R ⑵ R 是传递的当且仅当t(R )=R
证明：⑴?设R 是对称的，下证s(R )=
R
令R′=R
①R′=R是对称的。
②因为R?R=R′，所以R?R′。
③有任意对称二元关系R′′且R?R′′，下证R′?R′′
因为R′=R?R′′，所以R′?R′′
?设s(R)=R，下证R是对称的。
由对称闭包的定义，显然R是对称的。
⑵?设R是传递的，下证t(R)=R
令R′=R
①R′=R是传递的。
②因为R?R=R′，所以R?R′。
③有任意传递二元关系R′′且R?R′′，下证R′?R′′
因为R′=R?R′′，所以R′?R′′
?设t(R)=R，下证R是传递的。
由传递闭包的定义，显然R是传递的。
11）设R和S是A上的二元关系，R?S，证明：
⑴ r(R)?r(S)
⑵ s(R)?s(S)
⑶ t(R)?t(S)
证明：
⑴
r(R)=I A∪R? I A∪S=r(S)，即r(R)?r(S)。
⑵
先证R C?S C，
s(R)=R∪R C?S∪S C =s(S) ，所以s(R)?s(S)。
⑶
R?S?t(S)，t(S)是包含R的传递关系，而t(R) 是包含R的最小的传递关系。所以t(R)?t(S)
12）设R和S是A上的二元关系，证明：
⑴ r(R∪S)=r(R)∪r(S)
⑵ s(R∪S)=s(R)∪s(S)
证明：⑴r(R∪S)=R∪S∪I A=(R∪I A)∪(S∪I A)=r(R)∪r(S)
⑵s(R∪S)= (R∪S)∪(R∪S)C=(R∪R C)∪(S∪S C)=s(R)∪s(S)
13）设A=?1,2,3,4,5?，A上的等价关系R定义为：
R=?<1,2>,<2,1>,<3,4>,<4,3>?∪I A
画出关系图，找出所有等价类，总结等价类和关系图的关系。
解：R的关系图如图4.34所示。
[1]R=[2]R=?1,2?，[3]R=[4]R=?3,4?，[5]R=?5?
关系图每一个连通分支的结点构成的集合是一个等价类。或者说，每一个等价类导出了关系图的一个连通分支。
14）集合A是自然数集合的子集，A上的整除关系R是偏
序关系。定义为R=?
⑴A=?3,9,27,54?
⑵A=?1,2,3,4,6,8,12,24?
⑶A=?1,3,5,9,15,18,27,36,45,54?
⑷A=?1,2,3,4,5,6,7,8,9,10,11,12?
解：⑴R=?<3,9>,<3,27><3,54>,<9,27>,<9,54><27,54>?∪I A
集合A上的盖住关系COV A=?<3,9>,<9,27><27,54>?
哈斯图如图4.39所示。
R是全序关系。
⑵
R=?<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,
<2,6>,<2,8>,<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<
4,8>,
<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>?∪I
A
COV A=?<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,
<6,12>,<8,24>,<12,24>?
哈斯图如图4.40所示。
R不是全序关系。
⑶R=?<1,3>,<1,5>,<1,9>,<1,15>,<1,18>,<1,27>,<1,36>,<1,45>,<1,54>,
<3,9>,<3,15>,<3,18>,<3,27>,<3,36>,<3,45>,<3,54>,
<5,15>,<5,45>,<9,18>,<9,27>,<9,36>,<9,45>,<9,54>,
<15,45>,<18,36>,<18,54>,<27,54>?∪I A
COV
A=?<1,3>,<1,5>,<3,9>,<3,15>,<5,15>,<9,18>,<9,27>,<9,45>,<15,45>,<18,36>,
<18,54>,<27,54>?
哈斯图如图4.41所示。
不是全序关系。
⑷
R=?<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<1,9>,<1,10>,<1,11>,<1,12>,
<2,4>,<2,6>,<2,8>,<2,10>,<2,12>,<3,6>,<3,9>,<3,12>,<4,8>,<4,12>,
<5,10>,<6,12>?∪I A
COV A=?<1,2>,<1,3>,<1,5>,<1,7>,<1,11>,<2,4>,<2,6>,<3,6>,<3,9>,
<4,8>,<4,12>,<5,10>,<6,12>?
哈斯图如图4.42所示。
不是全序关系。
15）求出下列各偏序集
⑴A=?a,b,c,d,e?，?=?
B1=?b,c,d?，B2=?a,b,c,d?，B3=?b,c,d,e?
⑵A=?a,b,c,d,e?，?=?
B1=?a,b,c,d,e?，B2=?c,d?，B3=?c,d,e?
⑶A=P(?a,b,c?)，?=?
B1=? ,?a?,?b??，B2=??a?,?c??，B3=??a, c?,?a,b,c??
解：⑴COV A=?
哈斯图如图4.43所示。
A的子集B1、B2和B3的极大元、极小元、最大元、最
小元、上界、下界、上确界和下确界如表4.3所示。
⑵COV A=?
哈斯图如图4.44所示。
A的子集B1、B2和B3的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界如表4.4所示。
⑶A=P(?a,b,c?)=? ,?a?,?b?,?c?,?a, b?,?a, c?,?b, c?,?a,b,c??
?=?< ,?a?>,< ,?b?>,< ,?c?>,< ,?a,b?>,< ,?a,c?>,< ,?b,c?>,< ,?a,b,c?>,
,,,,,,
,,,,,
?∪I A
COV A=?< ,?a?>,< ,?b?>,< ,?c?>,,,, ,,,,,?
哈斯图如图4.45所示。
A的子集B1、B2和B3的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界如表4.5所示。
第五章
1）设代数系统
277
解：代数系统
和4互为逆元。
3）写出代数系统
解：代数系统
6）设
⑴a?b=|a+b|，⑵a?b=a b，⑶a?b=a+b?1，⑷a?b=a+2b
问：哪些运算在Z上是封闭的？哪些运算是可交换的？哪些运算是可结合的？
解：Z为整数集合，
⑴因为
①整数加法运算在Z上封闭，绝对值运算在Z上也封闭。
②?a,b∈Z，a?b=|a+b|=|b+a|=b?a
③当a＝1，b＝2，c＝-3时，(a?b)?c=||a+b|+c|=0，a?(b?c)=|a+|b+c||=2，(a?b)?c≠a?(b?c)。
所以，?运算在Z上封闭，可交换，但不可结合。
⑵因为
①当b＜0时，a?b= a b不一定是整数，例如a＝2，b＝-1，a?b=2-1?Z，
②?a,b∈Z，a?b=a b，b?a=b a，a?b不一定等于b?a，例如a＝2，b＝1时，a?b=a b=2，b?a=b a=1。a?b≠b?a。
③当a=2，b=1，c=2，(a?b)?c=(a b)?c=(21)?2=22=4，a?(b?c)=a?(b c)=2?(12)=2，(a?b)?c≠a?(b?c)。
所以?运算在Z上不封闭，不可交换，不可结合。
⑶因为
①整数加法和减法运算在Z上封闭，
②?a,b∈Z，a?b=a＋b-1= b＋a-1= b?a
③?a,b,c∈Z，(a?b)?c=(a＋b-1)＋c-1=a＋b＋c-2=a＋(b＋c-1)-1。
所以，?运算在Z上封闭，可交换，可结合。
⑷因为
①整数加法和乘法运算在Z上封闭。
②?a,b∈Z，a?b=a＋2b，b?a=b＋2a。a?b不一定等于b?a，如a＝1，b＝2时。a?b=a＋2b=5，b?a=b＋2a=4，a?b≠b?a。
③?a,b,c∈Z，(a?b)?c=(a＋2b)＋2c，a?(b?c)=a＋2(b＋2c)=a＋2b＋4c，当a ＝0，b＝0，c＝1时，(a?b)?c=2，a?(b?c)=4，(a?b)?c≠a?(b?c)。
所以，?运算在Z上封闭，不可交换，也不可结合。
7）设Z是整数集合，Z上的二元运算*定义为：a*b=ab+2(a+b+1)。证明代数系统
证明：由于任意两个整数经加、减、乘运算后，其结果仍然是整数。所以运算*对于是封闭的。
现证*是可结合运算。由于
(a*b)*c=(ab+2(a+b+1))*c
=(ab+2(a+b+1))c+2(ab+2(a+b+1)+c+1)
=abc+2ac+2bc+2c+2ab+4a+4b+2c+6
=abc+2(ab+bc+ca)+4(a+b+c)+6
a*(b*c)=a*(bc+2(b+c+1))
=a(bc+2(b+c+1))+2(a+bc+2(b+c+1)+1)
=abc+2ab+2ac+2a+2a+2bc+4b+4c+6
=abc+2(ab+bc+ca)+4(a+b+c)+6
所以(a*b)*c=a*(b*c)。由此证得*是可结合运算，
8）Z是由所有整数组成的集合，对于下列*运算，哪些代数系统
⑴a*b=a b
⑵a*b=a
⑶a*b=a+ab
⑷a*b=max(a,b)
解：⑴不是半群。因为运算*不满足结合律。
例如，(2*3)*2=23*2=(23)2=26，而2*(3*2)=2*32=29，所以(2*3)*2≠2*(3*2)。
⑵是半群。*的封闭性是显然的，由于(a*b)*c=a*c=a, a*(b*c)=a*b=a，所以*是可结合运算，
⑶不是半群，因为运算*不满足结合律。易见
(a*b)*c=(a+ab)*c=a+ab+(a+ab)c=a+ab+ac+abc
而
a*(b*c)=a*(b+bc)=a+a(b+bc)=a+ab+abc
所以(a*b)*c≠a*(b*c)，*不是可结合运算。
⑷是半群。*的封闭性是显然的，由于(a*b)*c=a*(b*c)=max(a, b, c)，所以*是可结合运算，
9）Z是整数集合，运算*定义为a*b=a+b+ab。证明
证明：*对于Z的封闭性是显然的。下面证明*是可结合运算，由于
(a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c =a+b+c+ab+ac+bc+abc
a*(b*c)=a*(b+c+bc)=a+b+c+bc +a(b+c+bc)=a+b+c+ab+ac+bc+abc
所以有(a*b)*c=a*(b*c)
由此可知*是可结合运算。又由于
0*a=a*0=0+a+a·0=a
所以0是幺元，
10）
证明：由题设可知，当a≠b时，必有a*b≠b*a，也即当a*b=b*a时，必有a=b。由于
离散数学期末试题及答案
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>}。
离散数学试题及解答
离散数学 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
离散数学 第2章 习题解答
第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x (是鸟 x F:) (会飞翔. G:) x x 命题符号化为 x F ?. G x→ ) ( )) ( (x (2)令x x (为人. F:) (爱吃糖 G:) x x 命题符号化为 x F x→ G ?? )) ( ) ( (x 或者 F x? x ∧ ? ) )) ( ( (x G (3)令x x (为人. F:) G:) (爱看小说. x x 命题符号化为 x F ?. G x∧ (x ( )) ( ) (4) x (为人. x F:) (爱看电视. G:) x x 命题符号化为 F x? ∧ ??. x G ( ) ( )) (x 分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的) F都是特性谓词。 (x 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 F x ? G x∧ ( )) ( ) (x
即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 )(x xF ? 其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。 （2） 在)(),(),(c b a 中均符号化为 )(x xG ? 其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。 （3）在)(),(),(c b a 中均符号化为 )(x xH ? 其中.15:)(=x x H 此命题在)(),(b a 中均为假命题，在(c)中为真命题。 分析 1°命题的真值与个体域有关。 2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 )(x xF ? 这里，x x F :)(呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ))()((x G x F x →? 这里，x x F :)(为人，且)(x F 为特性谓词。x x G :)(呼吸。 2．3 因题目中未给出个体域，因而应采用全总个体域。
离散数学习题集十五套
离散数学试题与答案试卷一 一、填空 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、命题符号化（共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 满足：<
离散数学课后习题答案_屈婉玲(高等教育出版社)
第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.
(1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p)
离散数学模拟试卷和答案
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 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个
离散数学 第2章 习题解答
习题 2.1 1．将下列命题符号化。 (1) 4不是奇数。 解：设A(x)：x是奇数。a：4。 “4不是奇数。”符号化为：?A(a) (2) 2是偶数且是质数。 解：设A(x)：x是偶数。B(x)：x是质数。a：2。 “2是偶数且是质数。”符号化为：A(a)∧B(a) (3) 老王是山东人或河北人。 解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。 “老王是山东人或河北人。”符号化为：A(a)∨B(a) (4) 2与3都是偶数。 解：设A(x)：x是偶数。a：2，b：3。 “2与3都是偶数。”符号化为：A(a)∧A(b) (5) 5大于3。 解：设G(x,y)：x大于y。a：5。b：3。 “5大于3。”符号化为：G(a,b) (6) 若m是奇数，则2m不是奇数。 解：设A(x)：x是奇数。a：m。b：2m。 “若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b) (7) 直线A平行于直线B当且仅当直线A不相交于直线B。 解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。 “直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b)??D(x,y) (8) 小王既聪明又用功，但身体不好。 解：设A(x)：x聪明。B(x)：x用功。C(x)：x身体好。a：小王。 “小王既聪明又用功，但身体不好。”符号化为：A(a)∧B(a)∧?C(a) (9) 秦岭隔开了渭水和汉水。 解：设A(x,y,z)：x隔开了y和z。a：秦岭。b：渭水。c：汉水。 “秦岭隔开了渭水和汉水。”符号化为：A(a,b,c) (10) 除非小李是东北人，否则她一定怕冷。 解：设A(x)：x是东北人。B(x)：x怕冷。a：小李。 “除非小李是东北人，否则她一定怕冷。”符号化为：B(a)→?A(a) 2．将下列命题符号化。并讨论它们的真值。 (1) 有些实数是有理数。 解：设R(x)：x是实数。Q(x)：x是有理数。 “有些实数是有理数。”符号化为：(?x)(R(x)∧Q(x))
离散数学复习题及答案
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 →∧??
离散数学模拟试题及答案
《离散数学》模拟试题 一、 填空题（每小题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) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。
大学离散数学试题集(非常完整试题)
第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. 给我一杯水吧！
离散数学答案(尹宝林版)第二章习题解答
第二章 谓词逻辑 习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。
离散数学试题与答案
试卷二试题与参考答案 一、填空 1、 P ：你努力，Q ：你失败。 2、 “除非你努力，否则你将失败”符号化为 ； “虽然你努力了，但还是失败了”符号化为 。 2、论域D={1，2}，指定谓词P 则公式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、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 6、4阶群必是 群或 群。 7、下面偏序格是分配格的是 。
8、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 二、选择 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 ．自反性 。
离散数学模拟题及答案
一、填空 1．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。2．一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是__________________，其主合取范式是_________________。 3．设A={a,b,c}，B={b,c,d,e}，C={b,c}，则( A ?B ) ⊕C＝____________。 4．幂集P(P(?)) ＝________________。 5．设A为任意集合，请填入适当运算符，使式子A________A=?；A________A’=?成立。6．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则D(R)=____________，R(R)=____________。 7．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，S n}，其中S i?A，S i≠?，i=1，2，…，n，且______ _____；进一步若_____ _______，则S是集合A的划分。8．两个重言式的析取是____ ____式，一个重言式和一个永假式的合取式是式。9．公式┐(P∨Q) ←→(P∧Q)的主析取范式是。 10. 已知Π={{a}{b,c}}是A={a,b,c}的一个划分，由Π决定的A上的一个等价关系 是。 二、证明及求解 1．求命题公式（P→Q）→（Q∨P）的主析取范式。 2．推理证明题 1）?P∨Q，?Q∨R，R→S?P→S。 2) (?x)(P(x)→Q(y)∧R(x))，(?x)P(x)?Q(y)∧(?x)(P(x)∧R(x)) x)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。3．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y= 2 试求R S R。 4．证明：R是传递的?R*R?R。 5．设R是A上的二元关系，S={
离散数学练习题及答案
离散数学试题 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就．在室内运动”可符合化为 （B） A. P∧Q B. P→Q C. Q→P D. P∨Q 2.设G=(V , E)为任意一图（无向或有向的），顶点个数为n，边的条数为m， 则各顶点的度数之和等于（ D ）。 A.n B. m C. 2n D. 2m 3.下列命题为假．命题的是（A） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式(?x(P(x)∨?yR(y))→Q(x) 中变元x是（D） A.自由变元 B.约束变元 C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 5.若个体域为整数域，下列公式中值为真的是（A） A.?x?y(x+y=0) B.?y?x(x+y=0) C.?x?y(x+y=0) D.??x?y(x+y=0) 6.下列命题中不．正确的是（D） A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C） A.P?Q B.P?Q C.Q?P D.Q=P 8.下列表达式中不．成立的是（A） A.A∪(B⊕C)=(A∪B) ⊕ (A∪C) B.A∩(B⊕C)=(A∩B) ⊕ (A∩C) C.(A⊕B)×C=(A×C) ⊕ (B×C) D.(A-B) ×C=(A×C)-(B×C) 9.半群、群及独异点的关系是（A） A.{群}?{独异点}?{半群} B.{独异点}?{半群}?{群}
离散数学模拟试题1
一、选择题（每小题只有一个正确答案，每题2分，共30分） 1、令A（x）:x是实数，B（x）:x是有理数，则命题：并非所有有理数都是实数。符号化为：（） A、x┐(A(x)∧B(x)) B、┐x(B(x)→A(x)) C、┐x(A(x)∧B(x)) D、┐x(B(x)∧┐A(x)) 2、设A={{1，2，3}，{4，5}，{6，7，8}}，则下列选项正确的是（） A、1∈A， B、φ∈A C、{1，2，3} A， D、{{4，5}} A 3、设A、B为集合，A-B=φ，则有（） A、B=φ B、B≠φ C、A B D、B A 4、一个连通有向图，如果它的每个结点的出度均等于入度，那么它有一条（）。 A、基本回路 B、欧拉回路 C、欧拉通路 D、简单回路 5、一棵树有2个结点度数为2，2个结点度数为3，3个结点度数为4，则它的树叶数为（） A、8 B、9 C、10 D、12 6、G是连通平面图，有5个顶点、6个面，则G的边数为（） A、6 B、5 C、11 D、9 7、设A={1，2，3}，B={1，2，3，4，5}，C={2，3}，则（A∪B）+C=（） A、{1，2} B、{2，3} C、{1，4，5} D、{1，2，3} 8、下列命题中为假的是（） A、{a，{b}}{{a，{b}}} B、φP(∪{φ,{φ}}) C、{a}XaX D、X∪Y=YX=φ 9、设解释T为：个体域为D={—2，3，6}，谓词A(x)：x 6，B(x)：x>5，则根据解释，公式x(A(x)∨B(x))的真值为（） A、0 B、1 C、没有确定真值 10、一个教室公用一个电源，如果想接34盏灯，则至少需要4个插线孔的接线板（）个。 A、10 B、11 C、12 D、34 11、下列说法错误的是（） A、n个结点m条边的有向树和无向树均满足：m=n－1. B、树都是二部图。 C、有向树都是单侧连通的 D、有桥的图不是欧拉图