一．选择题
1、设A={a,{b}}，p(A)是A的幂集，则 ( )。
A. p(A)={∅,a,b,{b}}
C.p(A)={∅,{a},b,{b}}
B. p(A)={∅,{a},{{b}},{a,{b}}}
D. p(A)={∅,a,{b},{{b}}}
2、设A={b,{1}}，p(A)是A的幂集，则 ( )。
A. p(A)={∅,b,1,{1}} B.p(A)={∅,b,{1},{{1}}} C.p(A)={∅,{b},1,{1}}
D.p(A)={∅,{b},{{1}},{b,{1}}}
3、设A={a,{1}}，p(A)是A的幂集，则 ( )。
A. p(A)={∅,a,1,{1}} B.p(A)={∅,a,{1},{{1}}} C.p(A)={∅,{a},1,{1}}
D.p(A)={∅,{a},{{1}},{a,{1}}}
4、设A={a,{0}}，p(A)是A的幂集，则 ( )。
A. p(A)={∅,a,0,{0}} B. p(A)={∅,{a},0,{0}}
C. p(A)={∅,{a},{{0}},{a,{0}}} D. p(A)={∅,a,{0},{{0}}} 5、集合B={{Φ}}的幂集为（ ）。 A、{{Φ},{{Φ},Φ},Φ}； B、{Φ,{{Φ}}}； C、{Φ,{Φ},{{Φ}}}； D、{{Φ,{Φ}}}
6、设A={a,{1}}，p(A)是A的幂集，则 ( )。
A. p(A)={∅,a,1,{1}} B.p(A)={∅,a,{1},{{1}}} C.p(A)={∅,{a},1,{1}}
D.p(A)={∅,{a},{{1}},{a,{1}}}
7、集合B={1,{1}}的幂集为（ ）。
A、 B、C、 D、{Φ,{1},{{1}},{1,{1}}}；{1,{1},{{1}}}；{Φ,1,{1},{{1}},{1,{1}}}；{{1,{1}}} 8、设A={a,{0}}，p(A)是A的幂集，则 ( )。
A. p(A)={∅,a,0,{0}} B. p(A)={∅,{a},0,{0}}
C. p(A)={∅,{a},{{0}},{a,{0}}} D. p(A)={∅,a,{0},{{0}}} 9、设A={a,{b}}，p(A)是A的幂集，则 ( )。
A. p(A)={∅,a,b,{b}}
C. p(A)={∅,{a},b,{b}}
B. p(A)={∅,{a},{{b}},{a,{b}}}
D. p(A)={∅,a,{b},{{b}}}
10.集合B={Φ,{Φ}}的幂集为（ ）。 A、{{Φ},{{Φ},Φ},Φ}； B、{Φ,{Φ},{{Φ}}}；
C、{Φ,{Φ},{{Φ}},{Φ,{Φ}}}； D、{{Φ,{Φ}}}
C、{xx是正整数且x≤25} D、{xx是正有理数且x≤25} 11、设A={1，2，3}，下面（ ）集合等于A 。
A、{xx是正整数且x≤3} B、{xx是整数且x≤9} C、{1，2，3，4} D、{xx是正有理数且x≤3} 12、设A={1，2，3，4，5}，下面（ ）集合等于A 。 A、{1，2，3，4，5，6} B、{xx是正整数且x≤25} 13、设A={1，2，3}，下面（ ）集合等于A 。 A、{xx是整数且x≤3} B、{xx是正整数且x≤9} C、{1，2，3，4} D、{xx是正有理数且x≤3} 14、设A={1，2，3，4，5}，下面（ ）集合等于A 。 A、{1，2，3，4，5，6} B、{xx是整数且x≤25} C、{xx是整数且x≤5} D、{xx是正有理数且x≤5} 15、设A={1，2，3}，下面（ ）集合等于A 。 A、{xx是整数且x≤3} B、{xx是正整数且x≤9} C、{1，2，3，4} D、{xx是正有理数且x≤3}
222
2
2
2
2
16、设A={1，2，3}，下面（ ）集合等于A 。 A、{xx是正整数且x≤3} B、{xx是整数且x≤9} C、{1，2，3，4} D、{xx是正有理数且x≤3} 17、设A={1，2，3，4}，下面（ ）集合等于A 。 A、{1，2，3} B、{xx是整数且x≤4}
C、{xx是正整数且x≤16} D、{xx是正有理数且x≤4} 18、设A={1，2，3，4}，下面（ ）集合等于A 。 A、{1，2，3} B、{xx是正整数且x≤4} C、{xx是整数且x≤16} D、{xx是正有理数且x≤4} 19、设A={1，2，3，4}，下面（ ）集合等于A 。 A、{1，2，3} B、{xx是正整数且x≤4} C、{xx是整数且x≤16} D、{xx是正有理数且x≤4} 20、设A={1，2，3，4，5}，下面（ ）集合等于A 。 A、{1，2，3，4，5，6} B、{xx是整数且x≤25} C、{xx是正整数且x≤5} D、{xx是正有理数且x≤5}
21、设A={{1，2，3}，{4，5，6}，{6，7，8}}，下列各式中（ ）是正确的。 A、Φ⊄A； B、{6，7，8}∈A；C、{4，5，6}⊂A； D、{1，2}⊂A 22、设A=Ø，B=P(A)，以下正确的式子是（ ） A．∅∈B B．{{Ø}}∈B C．{Ø}∉B D． {Ø,{Ø}}∈B 23、设A={Ø}，B=P(A)，以下正确的式子是（ ） A．A∈B C．{∅}∈B
B、 {{∅}}∈B
2
22
2
2
D．A∈B
24、设S={Φ,{1},{1,2}}，则有（ ）⊆S。
A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。
25、设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。 A、Φ⊆A； B、{6，7，8}∈A；C、{{4，5}}⊂A； D、{1，2，3}⊂A 26、设A=Ø，B=P(A)，以下正确的式子是（ ） A．∅∈B B．{{Ø}}∈B C．{Ø}∉B D． {Ø,{Ø}}∈B 27、下列各选项中错误的是（ ）
A) Ф∈Ф B) Ф⊆ Ф C) Ф⊆ {Ф} D) Ф∈{Ф}
28、设A={{1，2，3}，{4，5，6}，{6，7，8}}，下列各式中（ ）是正确的。 A、Φ⊄A； B、{4，5，6}⊂A；C、{6，7，8}∈A； D、{1，2}⊂A 29、设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。 A、Φ⊆A； B、{6，7，8}∈A；C、{{4，5}}⊂A； D、{1，2，3}⊂A 30、在0 Φ之间应填入（ ）符号。 A、= B、⊂ C、∈ D、∉ 31、设A=Φ,
。 B={Φ,{Φ}}，则A⊕B是（ ）
A、{Φ,{Φ}} B、{Φ} C、{{Φ}} D、Φ 32、设A=Φ,
。 B={Φ,{Φ}}，则A—B是（ ）
A、{{Φ}} B、{Φ} C、{Φ,{Φ}} D、Φ 33、设A=Φ,
。 B={Φ,{Φ}}，则A∪B是（ ）
A、{{Φ}} B、{Φ} C、{Φ,{Φ}} D、Φ 34、A是素数集合，B是奇数集合，则A-B=（ ）
A 素数集合；B、 奇数集合； C、 Φ； D、{2}。 35、设A=Φ,
。 B={Φ,{Φ}}，则B－A是（ ）
A、{{Φ}} B、{Φ} C、{Φ,{Φ}} D、Φ 36、设A=Φ,
。 B={Φ,{Φ}}，则A—B是（ ）
A、{{Φ}} B、{Φ} C、Φ D、{Φ,{Φ}} 37、设A=Φ,
。 B={Φ,{Φ}}，则A∩B是（ ）
A、{{Φ}} B、Φ C、{Φ,{Φ}} D、{Φ} 38、设A=Φ,
。 B={Φ,{Φ}}，则B－A是（ ）
A、{{Φ}} B、{Φ} C、{Φ,{Φ}} D、Φ 39、A是素数集合，B是奇数集合，则A-B=（ ）
A 素数集合；B、 奇数集合； C、 Φ； D、{2}。 40、设A=Φ,
。 B={Φ,{Φ}}，则A∪B是（ ）
A、{{Φ}} B、{Φ} C、{Φ,{Φ}} D、Φ
41、设A={xx是整数且x<16}，下面哪个命题为真（ ）。 A、{0,1,2,4}⊆A ； B、{−4，−3,−2,−1}⊆A ； C、Φ⊄A ； D、{xx是整数且x<4}⊆A。
A、2是素数 B、x+5 > 6 C、你今年多大了？ D、这朵花多好看呀！。 42、下列各命题中真值为假的命题是（ ）。
A、2+2=4当且仅当3是奇数； B、如果2+2=4，那么3是奇数； C、2+2≠4当且仅当3不是奇数； D、2+2≠4当且仅当3是偶数； 43、下列语句中不是命题的是（ ）
A、9+5≤12。 B、2+3=5。 C、我用的计算机CPU主频是1G吗？ D、我努力学习。 44、设A={xx是整数且x<16}，下面哪个命题为假（ ）。 A、{0,1,2,4}⊆A ； B、{−3,−2,−1}⊆A ； C、Φ⊆A ； D、{xx是整数且x<4}⊆A。 45、下列语句不是命题的是（ ）。
A、你打算考硕士研究生吗？ B、离散数学是计算机系的一门必修课。 C、鸡有三只脚。 D、太阳系以外的星球上有生物。 46、 下列句子为命题的是( )
A.全体起立! B.x=0 C.我在说谎 D.张三生于1886年的春天 47、下列语句是命题的是（ ）。
A、明年中秋节的晚上是晴天。 B、x+y>0。 C、请关门！ D、我正在说谎 48、下列语句不是命题的是( )。 A.2015年7月1日是晴天。
B. 他是不是计算机专家呢?要是他考上了，我就赌输了。 C. 要是他考上了，我就赌输了。 D.他不是一个真正的科学家。
49、下列语句不是命题的是( )。 A. 要是他考上了，我就赌输了。 B. 他是不是计算机专家呢? C. 1915年6月14日是晴天。 D.他不是一个真正的科学家。
50. 下列语句不是命题的是( )。 A. 你在干什么？
B. 他不是计算机专家。
C. 1915年6月14日不是晴天。 D.雪是白的。 51、令我听课为P，我看小说为Q，命题“我或者听课，或者看小说”的符号化为（ ） A、 P→¬Q B、 ¬P→Q； C、 D、¬(P∧Q) （Q∧¬P）∨（P∧¬Q）
2
2
52、令我带伞为P，天下雨为Q，命题“只有天下雨，我才带伞”的符号化为（ ） A、 P→¬Q B、 Q→¬P； C、 P→Q D、¬(P∧Q)
53、令我听课为P，我看小说为Q，命题“我不能一边听课，一边看小说”的符号化为（ ）
A、 P→¬Q B、 ¬P→Q； C、 ¬Q∧¬P D、¬(P∧Q)
54、令我带伞为P，天下雨为Q，命题“如果天不下雨，则我不带伞”的符号化为（ ） A、 P→¬Q B、 ¬Q→¬P； C、 ¬Q∧¬P D、¬(P∧Q)
55.设 P：我将去学校，Q：我有自行车。命题“我将去学校，当且仅当我有自行车时”符号化为 （ ）
A. P → Q B. Q → P C. P↔Q D. ¬P∨¬Q
56、令我带伞为P，天下雨为Q，命题“如果天不下雨，则我不带伞”的符号化为（ ） A、 P→¬Q B、 ¬Q→¬P； C、 ¬Q∧¬P D、¬(P∧Q)
57、令我听课为P，我看小说为Q，命题“我只能听课，而不能看小说”的符号化为（ ） A、 P→¬Q B、¬Q∧P ； C、P∧Q D、¬P→Q
58、设 P：张三可以做这件事，Q：李四可以做这件事。命题“张三或李四可以做这件事”符号化的结果为（ ）
A． P∨Q B. P∨┐Q C．P∧Q D. ┐(┐P∨┐Q)
59、令我带伞为P，天下雨为Q，命题“只有天下雨，我才带伞”的符号化为（ ） A、 P→¬Q B、 Q→¬P； C、 P→Q D、¬(P∧Q)
60、令我带伞为P，天下雨为Q，命题“除非天下雨，否则我不带伞”的符号化为（ ） A、 P→¬Q B、 Q→¬P； C、 P→Q D、（Q∧¬P）∨（P∧¬Q）61、命题“任何人都犯错误”符号化为（ ）。 设M(x)：x是人，P(x)：x犯错误。
A、∀x(M(x)→P(x))； B、∀x(M(x)→¬P(x))； C、∀x(¬M(x)→P(x))； D、∃x(M(x)∧¬P(x))。 62、“人总是要死的”谓词公式表示为（ ）。
（论域为全总个体域）M(x)：x是人；D(x)：x是要死的。
B、M(x)∧D(x) C、∀x(M(x)→D(x))；D、∃x(M(x)∧D(x)) A、M(x)→D(x)；
63、命题“任何人都犯错误”符号化为（ ）。 设M(x)：x是人，P(x)：x犯错误。
A、∀x(M(x)→P(x))； B、∀x(M(x)→¬P(x))；
C、∀x(¬M(x)→P(x))； D、∃x(M(x)∧¬P(x))。
64、命题“说存在不犯错误的人是错误的”符号化为（ ）。 设M(x)：x是人，P(x)：x犯错误。
A、¬(∃x(M(x)∧¬P(x)))； B、¬(∃x(M(x)→¬P(x)))； C、¬(∃x(M(x)∧P(x)))； D、∀x(M(x)∧P(x))。 65、“认为存在不死的人是错误的”谓词公式表示为（ ）。 （论域为全总个体域）M(x)：x是人；D(x)：x是要死的。 A、∃x(M(x)∧¬D(x))； B、¬∃x(M(x)∧¬D(x)) C、∀x(M(x)∧D(x))； D、¬∃x(M(x)∧D(x))
66、“认为存在不死的人是错误的”谓词公式表示为（ ）。 （论域为全总个体域）M(x)：x是人；D(x)：x是要死的。 A、∃x(M(x)∧¬D(x))； B、¬∃x(M(x)∧¬D(x)) C、∀x(M(x)∧D(x))； D、¬∃x(M(x)∧D(x)) 67、“人总是要死的”谓词公式表示为（ ）。 （论域为全总个体域）M(x)：x是人；D(x)：x是要死的。
B、M(x)∧D(x) C、∀x(M(x)→D(x))；D、∃x(M(x)∧D(x)) A、M(x)→D(x)；
68、命题“没有不犯错误的人”符号化为（ ）。 设M(x)：x是人，P(x)：x犯错误。
A、∀x(M(x)∧P(x))； B、¬(∃x(M(x)→¬P(x)))； C、¬(∃x(M(x)∧P(x)))； D、¬(∃x(M(x)∧¬P(x)))。 69、“没有不死的人”谓词公式表示为（ ）。
（论域为全总个体域）M(x)：x是人；D(x)：x是要死的。 A、∃x(M(x)∧¬D(x))； B、∀x(M(x)∧D(x)) C、M(x)∧D(x)； D、¬∃x(M(x)∧¬D(x))
70、命题“说存在不犯错误的人是错误的”符号化为（ ）。 设M(x)：x是人，P(x)：x犯错误。
A、¬(∃x(M(x)∧¬P(x)))； B、¬(∃x(M(x)→¬P(x)))； C、¬(∃x(M(x)∧P(x)))； D、∀x(M(x)∧P(x))。
71、已知命题G=¬P∨(¬Q∧¬R) ，则所有使G取真值为1的赋值是 ( )。 (A)(1, 1, 0), (1, 1, 1), (1, 0, 1); (B) (1, 1, 0), (1, 0, 1), (1, 0, 0); (C) (1, 0, 0), (0, 0, 1), (1, 1, 0); (D) (1, 0, 0), (1, 0, 1), (0, 1, 1).
72、已知命题G=P∧(¬Q∨R) ，则所有使G取真值为1的赋值是 ( )。 A.(0, 0, 0), (1, 0, 1), (1, 0, 0); B. (0, 1, 0), (1, 0, 1), (1, 1, 0); C.(1, 0, 0), (1, 0, 1), (1, 1, 1); D. (1, 1, 0), (1, 0, 1), (1, 1, 1).
73、已知命题G=P∧(Q∨¬R) ，则所有使G取真值为1的赋值是 ( )。 A.(1, 0, 0), (0, 0, 1), (1, 0, 0); B. (0, 1, 0), (1, 0, 1), (1, 1, 0); C.(1, 0, 0), (1, 0, 1), (1, 1, 0); D. (1, 1, 0), (1, 0, 0), (1, 1, 1).
74、已知命题G=¬P∨(Q∧¬R) ，则所有使G取真值为1的赋值是 ( )。 (A)(1, 0, 0), (1, 0, 1), (1, 1, 0); (B) (1, 0, 0), (1, 0, 1), (1, 1, 1); (C) (1, 0, 0), (0, 0, 1), (1, 1, 0); (D) (0, 0, 0), (1, 0, 1), (1, 1, 1).
75、已知命题G=P∧(¬Q∨¬R) ，则所有使G取真值为1的赋值是 ( )。 A.(0, 0, 0), (0, 0, 1), (1, 0, 0); B. (0, 1, 0), (1, 0, 1), (1, 1, 0); C.(1, 0, 0), (1, 0, 1), (1, 1, 0); D. (1, 1, 0), (1, 0, 1), (1, 1, 1).
76、已知命题G=P∧(Q∨¬R) ，则所有使G取真值为1的赋值是 ( )。 A.(1, 0, 0), (0, 0, 1), (1, 0, 0); B. (0, 1, 0), (1, 0, 1), (1, 1, 0); C.(1, 0, 0), (1, 0, 1), (1, 1, 0); D. (1, 1, 0), (1, 0, 0), (1, 1, 1).
77、已知命题G=P∧(Q∨¬R) ，则所有使G取真值为1的赋值是 ( )。 A.(1, 0, 0), (0, 0, 1), (1, 0, 0); B. (0, 1, 0), (1, 0, 1), (1, 1, 0); C.(1, 0, 0), (1, 0, 1), (1, 1, 0); D. (1, 1, 0), (1, 0, 0), (1, 1, 1).
78、已知命题G=P∧(¬Q∨R) ，则所有使G取真值为1的赋值是 ( )。 A.(0, 0, 0), (1, 0, 1), (1, 0, 0); B. (0, 1, 0), (1, 0, 1), (1, 1, 0); C.(1, 0, 0), (1, 0, 1), (1, 1, 1); D. (1, 1, 0), (1, 0, 1), (1, 1, 1).
79、已知命题G=¬P∨(¬Q∧¬R) ，则所有使G取真值为1的赋值是 ( )。 (A)(1, 1, 0), (1, 1, 1), (1, 0, 1); (B) (1, 1, 0), (1, 0, 1), (1, 0, 0); (C) (1, 0, 0), (0, 0, 1), (1, 1, 0); (D) (1, 0, 0), (1, 0, 1), (0, 1, 1).
80、已知命题G=¬P∨(Q∧¬R) ，则所有使G取真值为0的赋值是 ( )。 A.(1, 0, 0), (1, 0, 1), (1, 1, 1); B. (1, 0, 0), (1, 1, 0), (1, 1, 1); C.(1, 0, 0), (0, 0, 1), (1, 1, 0); D. (1, 1, 0), (1, 0, 1), (0, 1, 1). 81、给定下列序列，（ ）可以构成无向简单图的结点度数列。 A、（1，1，2，2，3）； B、（1，1，2，2，2）； C、（0，1，3，3，3）； D、（1，3，4，4，5）。 82、下列图中是欧拉图的有( )。
83、下面四组数能构成无向简单图的度数列的是（ ）。 A、（2，3，2，5，2）； B、（1，5，2，8，3）； C、（1，5，3，2，2）； D、（1，6，8，3，3）。
84、下面四组数能构成无向简单图的度数列的是（ ） A、（6，3，1，3，2）； B、（7，5，2，2，3）； C、（8，1，3，2，2）； D、（0，3，8，3，3）。 85、在如下各图中（ ）是欧拉图。
86、下面四组数能构成无向简单图的度数列的是（ ）。 A、（2，2，2，2，2）； B、（1，1，2，2，3）； C、（1，1，1，2，2）； D、（0，1，2，3，3）。 87、下面四组数能构成无向简单图的度数列的是（ ）。 A、（2，2，5，2，2）； B、（1，1，2，2，3）； C、（1，1，6，2，2）； D、（0，1，2，3，3）。 88、在如下各图中（ ）是二部图。
89、下面那一个图可一笔画出（ ）。
90、下图中既不是欧拉图，也不是哈密顿图的图是（ ）
91、下列图中不是是哈密顿图的有( )。
92、一棵树有2个2度顶点，2 个3度顶点，1个4度顶点，其余均为树叶，则树叶为（ ）片。
A 、6 B、 4 C、8 D 、无法确定 93、连通图 G 是一棵树当且仅当 G 中（ ）
A.有些边不是割边 B.每条边都是割边 C.无割边集 D.每条边都不是割边
94、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。
A．1； B．2； C．3； D．4 。
95、一棵无向树T有8个顶点，4度、3度、2度的分支点各1个，其余顶点均为树叶，则T中有（ ）片树叶。
A、3； B、4； C、5； D、6 96、一棵树有5个2度顶点，2个3度顶点，1个4度顶点，其余均为树叶，则树叶为（ ）片。
A 、2 B、 4 C、6 D 、8
97、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。
A．1； B．2； C．3； D．4 。 98、一棵树有2个2度顶点，2 个3度顶点，1个4度顶点，其余均为树叶，则树叶为（ ）片。
A 、6 B、 4 C、8 D 、无法确定 99、一棵树有3个2度顶点，3个3度顶点，2个4度顶点，其余均为树叶，则树叶为（ ）片。
A 、11 B、 7 C、无法确定 D 、9 100、一棵树有4个2度顶点，1 个3度顶点，3个4度顶点，其余均为树叶，则树叶为（ ）片。
A 、5 B、 7 C、9 D 、无法确定 101、一棵树有4个2度顶点，1 个3度顶点，3个4度顶点，其余均为树叶，则树叶为（ ）片。
A 、5 B、 7 C、9 D 、无法确定
二．填空题
1.设A={x，{2}}，B={2，{2}}，则A∩ B=________，A-B=________。 2、设A={a，{c}}，B={ Ø，c}，则A∩ B=________，B -A =________。
3、设A={ Ø ，{c}}，B={ {∅}，c}，则A∩ B=________，A-B=________。 4、设A={ Ø ，c}，B={ {∅}，c}，则A∩ B=________，A-B=________。 5. 设A={x，{2}}，B={3，2}，则A∩ B=________，A-B=________。 6、设A={a，{c}}，B={ Ø，c}，则A∩ B=________，B -A =________。 7、设A={c，{c}}，B={ Ø，c}，则A∩ B=________， A-B =________。 8、设A={c，{a}}，B={ Ø，c}，则A∩ B=________， A-B =________。 9. 设A={x，{2}}，B={3，2}，则A∩ B=________，A-B=________。 10. 设A={x，{2}}，B={2，{2}}，则A∩ B=________，A-B=________。
11. 两个重言式的等价是________式，一个重言式与一个矛盾式的蕴涵是________式。 12. 两个矛盾式的蕴涵是________式，一个重言式与一个重言式的析取是________式。 13. 两个矛盾式的蕴涵是________式，一个重言式与一个重言式的析取是________式。 14. 两个重言式的蕴涵是________式，一个重言式与一个矛盾式的合取是________式。 15. 两个矛盾式的等价是________式，一个重言式与一个矛盾式的蕴涵是________式。 16. 两个重言式的蕴涵是________式，一个矛盾式与一个矛盾式的合取是________式。 17. 两个矛盾式的蕴涵是________式，一个矛盾式与一个矛盾式的析取是________式。 18. 两个重言式的蕴涵是________式，一个重言式与一个矛盾式的合取是________式。 19. 两个矛盾式的蕴涵是________式，一个重言式与一个重言式的析取是________式。 20. 两个重言式的蕴涵是________式，一个矛盾式与一个矛盾式的合取是________式。 21、若公式¬(P→Q)∧(¬P→Q)的主析取范式为m2则它的主合取范式为 。
22、若公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式为m0∨m1∨m2∨m7则它的主合取范式为 。
23、若公式¬(P→Q)∧(¬P→Q)的主合取范式为M0∧M1∧M3则它的主合取范式为 。
24、若公式(P∧Q)∨(¬P∧R)的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为 。
25、若公式(P∧Q)∨(¬P∧R)的主合取范式M000∧M010∧M100∧M101为则它的主析取范式为 。
26、若公式(P∨(Q∧R))→(P∧Q∧R)的主合取范式为M3∨M4∨M5∨M6m0∨m1∨m2∨m7则它的主合取范式为 。
27、若公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式为m0∨m1∨m2∨m7则它的主合取范式为 。
28、若公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式为m0∨m1∨m2∨m7则它的主合取范式为 。
29、若公式¬(P→Q)∧(¬P→Q)的主合取范式为M0∧M1∧M3则它的主合取范式为 。
30、若公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式为m0∨m1∨m2∨m7则它的主合取范式为 。
31、完全二部图K4,4具有____________个点和____________条边。
32、完全二部图K4,5具有____________个点和____________条边。 33、完全二部图K3,4具有____________个点和____________条边。 34、完全二部图K4,5具有____________个点和____________条边。 35、完全二部图K3,5具有____________个点和____________条边。 36、完全二部图K5,5具有____________个点和____________条边。
37、设K7 是有7个点的完全图，则K7有____________条边,n阶完全图结点v的度数d(v) = 。
38、完全二部图K5,5具有____________个点和____________条边。 39、完全二部图K5,6具有____________个点和____________条边。 40、完全二部图K4,4具有____________个点和____________条边。 41、已知(x+2,4)=(5,2x+y)则(x,y)为____________
42、设图 G有 5 个结点，若各结点的度数分别为：3 ,4, 6, 2, 3, 则 G有____________条边.
43、已知(x−4,8)=(5,2x+y)则(x,y)为____________ 44、已知(x+4,8)=(5,2x+y)则(x,y)为____________ 45、已知(x+2,4)=(5,2x+y)则(x,y)为____________ 46、已知(x−4,6)=(5,2x+y)则(x,y)为____________
47、设图 G有 5 个结点，若各结点的度数分别为：3 ,4, 6, 2, 3, 则 G有____________条边.
48、设图 G有 5 个结点，若各结点的度数分别为：3 ,4, 6, 2, 7, 则 G有____________条边.
49、设图 G有 5 个结点，若各结点的度数分别为：3 ,8, 6, 2, 3, 则 G有____________条边.
50、设图 G有 5 个结点，若各结点的度数分别为：3 ,2, 6, 2, 3, 则 G有____________条边.
51. 无向图G= Δ (G)=_____________ ， G 的 最 小 度 δ (G)=_____________ 。 52. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 53. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 54. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 55. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 56. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 57. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 58. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 59. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 60. 无向图G= Δ(G)=_____________，G的最小度δ(G)=_____________。 三．计算题 1、 构造命题公式(P→(¬P∧Q))∨R的真值表。 PQR ¬P (¬P∧Q) P→(¬P∨Q) 1 1 1 1 0 (P→(¬P∧Q))∨R 1 1 1 1 0 000 1 0 001 1 0 010 1 1 011 1 1 100 0 0 101 0 0 110 0 0 111 0 0 0 0 0 1 0 1 2构造命题公式(P→(¬P∨Q))∧R的真值表。 3构造命题公式(¬P→(P∧Q))∨R的真值表。 4构造命题公式(¬P→(P∨Q))∧R的真值表。 5构造命题公式(¬P→(P∧Q))∨R的真值表。 6构造命题公式((P∨Q)→P)∨¬R的真值表。 7构造命题公式((P∧Q)→¬P)∨R的真值表。 8构造命题公式(¬P→(P∧Q))∨R的真值表。 9构造命题公式((¬P∨Q)→P)∧R的真值表。 10构造命题公式(P→(¬P∨Q))∧R的真值表。 11、求公式(P→Q)∨(¬P∧Q)的主合取范式和主析取范式。 (P→Q)∨(¬P∧Q)⇔(¬P∨Q)∨(¬P∧Q) ⇔(¬P∧Q)∨(¬P∧¬Q)∨(P∧Q)∨(¬P∧Q)∨(¬P∧Q) ⇔m1∨m0∨m3∨m1∨m1⇔∑(0,1,3) (P→Q)∨(¬P∧Q)⇔(¬P∨Q)∨(¬P∧Q)⇔(¬P∨Q)∧(¬P∨Q)⇔¬P∨Q⇔M2⇔∏(2) 12、求公式(P→¬Q)∧(¬P∨Q)的主合取范式和主析取范式。 13、求公式(P→¬Q)∨(¬P∧Q)的主合取范式和主析取范式。 14、求公式(Q→P)∨(¬P∧Q)的主合取范式和主析取范式。 15、求公式(P→Q)∨(¬P∧Q)的主合取范式和主析取范式。 16、求公式(Q→P)∧(¬P∨Q)的主合取范式和主析取范式。 17、把p∧¬q分别化为与之等值的只包含“↑”和“↓”的公式。 p∧¬q ⇔¬¬(p∧¬q)⇔¬(p↑¬q)⇔¬(p↑(q↑q)) ⇔(p↑(q↑q))↑(p↑(q↑q)) p∧¬q ⇔¬¬(p∧¬q)⇔¬(¬p∨q) ⇔¬p↓q⇔(p↓p)↓q 18、把¬p∧q分别化为与之等值的只包含“↑”和“↓”的公式。 19、把¬p→¬q分别化为与之等值的只包含“↑”和“↓”的公式。 20、求公式(P→Q)∧(¬P∨Q)的主合取范式和主析取范式。 21、设A＝｛2， 4,6， 8｝，R为A上整除关系，试画 无，2,8、6,2 22、设A＝｛2，3， 4,6， 8｝，R为A上整除关系，试画 27、设A＝｛2，3， 4,6， 8｝，R为A上整除关系，试画 31、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. （3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 0 0 0 M=1 1 1 1 01 具有不自反也不反自反，不对称，反对称，传递性质 32、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. （3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 33、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. （3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 34、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. （3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 35、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. （3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 36、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. （3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 37、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. （3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 38、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. (3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 39、设集合A＝{a,b,c}，A上的关系R＝{ （1）画出R的关系图； （2）写出R的关系矩阵. （3）问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 40、设集合A＝{a,b,c}，A上的关系R＝{ (1) 画出R的关系图； (2) 写出R的关系矩阵. 问R具有关系的哪几种性质(自反，反自反，对称，反对称，传递)? 41、下图给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v1到v2长度分别为1，2，3，4的通路有多少条？（2’） （4）求通路长度小于等于2的回路有多少条？(2’) （5）求长度等于3的通路（包括回路）有多少条?(2’) (1) 0 1 1 1 A= 1 0 1 0 0 1 0 1 1 0 0 0 (2) 2 1 1 1 A2= 0 2 1 2 2 0 1 0 0 1 1 1 2 3 3 3 A3=4 1 2 1 0 3 2 3 2 1 1 1 6 5 5 5 A4=2 6 5 6 6 2 3 2 2 3 3 3 1 1 1 1 P= 1 1 1 1 1 1 1 1 1 1 1 1 （2）1，1，3，5 (3)6 (4)11+8+8+5=32 42、下图给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v3到v2长度分别为1，2，3，4的通路有多少条？（2’） （4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度等于3的通路（包括回路）有多少条?(2’) 43、下图给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v4到v2长度分别为1，2，3，4的通路有多少条？（（4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度等于2的通路（包括回路）有多少条?(2’) 44、下图给出了一个有向图。 2’） （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v3到v2长度分别为1，2，3，4的通路有多少条？（2’） （4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度小于等于4的通路（包括回路）有多少条?(2’) 45、下图给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v2到v3长度分别为1，2，3，4的通路有多少条？（（4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度等于3的通路（包括回路）有多少条?(2’) 2’） 46、下图给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v3到v2长度分别为1，2，3，4的通路有多少条？（（4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度等于3的通路（包括回路）有多少条?(2’) 47.给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v3到v1长度分别为1，2，3，4的通路有多少条？（（4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度等于4的通路（包括回路）有多少条?(2’) 2’）2’） 48、下图给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v1到v2长度分别为1，2，3，4的通路有多少条？（（4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度等于4的通路（包括回路）有多少条?(2’) 49、下图给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v3到v2长度分别为1，2，3，4的通路有多少条？（（4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度小于等于2的通路（包括回路）有多少条?(2’) 2’）2’） 50、下图给出了一个有向图。 （1）求出它的邻接矩阵A；（2’） （2）求出A2，A3，A4及可达矩阵P。(4’) （3）求v4到v3长度分别为1，2，3，4的通路有多少条？（（4）求通路长度小于等于3的回路有多少条？(2’) （5）求长度等于4的通路（包括回路）有多少条?(2’) 四、证明题 1、用推理规则证明以下推理 前提：¬( S→Q)→¬P，R∨P,¬R，S 结论：Q 2、用推理规则证明以下推理 前提：¬(Q→S)→¬P，R∨P,¬R，¬S 结论：¬Q 3、用推理规则证明以下推理 前提：¬(Q→S)→¬P，R∨P,¬R，Q 2’） 结论： S 4、用推理规则证明以下推理 前提：P→(Q→S)，R∨P，¬R，Q 结论： S 1.R∨P2.¬R 3.P 4.P→(Q→S) 5.Q→S6.Q7.S 5、用推理规则证明以下推理 前提：P→(Q→S)，R∨P，¬R，¬S 结论：¬Q 6、证明公式(¬p→q)→(¬q→p)为重言式 7、用推理规则证明以下推理 前提：¬( S→Q)→¬P，R∨P,¬R，¬Q 结论：¬S 8、证明公式(p→¬q)→(q→¬p)为重言式 9、证明集合相等：(A−B)∪B=A∪B (A−B)∪B=(A∩B)∪B=(A∪B)∩(B∪B)=(A∪B)∩E=A∪B 10、证明公式(¬p→q)→(¬q→p)为重言式 (p→q)→(¬q→¬p) ⇔(¬ p∨ q) →( q∨¬p) ⇔¬(¬ p∨ q) ∨( q∨¬p) ⇔( p∧¬ q) ∨( q∨¬p) ⇔(p∨ q) ∧(¬ q∨ q) ∨¬p ⇔(p∨ q) ∨¬p ⇔ p∨¬p∨ q ⇔1 五．应用题 1、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 用库斯克（Kruskal）算法求产生的最优树。结果如图： （3分） 树权C(T)=1+7+5+18+16+19=66即为总造价。（1分） 2、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 3、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 4、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生 成树），并求最小总造价。 5、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 6、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 7、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 8、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 9.如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 10、如下图所示的赋权图表示某七个城市v1,v2,\",v7及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小（即求最小生成树），并求最小总造价。 11、在计算机通信中,设八进制数字出现的频率如下: 0: 2%, 1: 3%, 2: 8%, 3: 12%, 4: 20%, 5: 32%， 6: 13%, 7: 10% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 解：１、按照哈弗曼算法得到最优二元树如下：（4分） 2、按照最优二元树以左枝为0，右枝为1，规则编码（不唯一），得到 编码分别为： 0:00000 1:00001 2:0001 3:101 4:11 5:10 6:001 7:100（4分） 3．100 个按比例传输的数字需要的二进制位即为树权， 5*5+4*8+3*35+2*52=104+105+32+25=57+209=266。（1分）4、等长码每个数字需3位二进制编码，故300个二进制数字（1分）。 12、在计算机通信中,设八进制数字出现的频率如下: 0: 5%, 1: 7%, 2: 8%, 3: 22%, 4: 10%, 5: 12%， 6: 13%, 7: 23% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述 比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 13、在计算机通信中,设八进制数字出现的频率如下: 0: 5%, 1: 6%, 2: 9%, 3: 22%, 4: 13%, 5: 20%， 6: 10%, 7: 15% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 14、在计算机通信中,设八进制数字出现的频率如下: 0: 1%, 1: 4%, 2: 5%, 3: 10%, 4: 12%, 5: 23%， 6: 21%, 7: 24% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 15、在计算机通信中,设八进制数字出现的频率如下: 0: 1%, 1: 3%, 2: 4%, 3: 7%, 4: 10%, 5: 12%， 6: 13%, 7: 50% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 16、在计算机通信中,设八进制数字出现的频率如下: 0: 1%, 1: 3%, 2: 4%, 3: 7%, 4: 10%, 5: 12%， 6: 13%, 7: 50% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 17、在计算机通信中,设八进制数字出现的频率如下: 0: 5%, 1: 7%, 2: 8%, 3: 22%, 4: 10%, 5: 12%， 6: 13%, 7: 23% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 18、在计算机通信中,设八进制数字出现的频率如下: 0: 1%, 1: 4%, 2: 5%, 3: 10%, 4: 12%, 5: 23%， 6: 21%, 7: 24% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 19、在计算机通信中,设八进制数字出现的频率如下: 0: 2%, 1: 3%, 2: 8%, 3: 12%, 4: 20%, 5: 32%， 6: 13%, 7: 10% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 20、在计算机通信中,设八进制数字出现的频率如下: 0: 4%, 1: 6%, 2: 7%, 3: 12%, 4: 15%, 5: 20%， 6: 19%, 7: 17% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前缀码), 并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字? 因篇幅问题不能全部显示，请点此查看更多更全内容