精品文档离散数学课外习题集
编者：金鹏
时间：2008-5-6
目录：
第一章
一、选择题
1.由n个命题变元组成不等值的命题公式的个数为（）
A.2n
B.2n
C.n2
D.2n2
2.设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化
为（）
A.P→Q
B.Q→P
C.P ?Q
D.?Q∨?P
3.下列各组公式中，哪组是互为对偶的？（）
A.P,P
B.P, ?P
C.A,(A*)*
D.A,A
（其中P为单独的命题变元，A为含有联结词的命题变元）
4.设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑步”符号化为（）
A. ?p∧?Q
B. ?P∨?Q
C. ?(P?Q)
D.P??Q
5.下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）
A. 2是偶数或-3不是负数 C. 2是奇数或-3不是负数
C．2不是偶数且-3不是负数 D. 2是奇数且-3不是负数
6.设P：张三可以作这件事，Q：李四可以作这件事。命题“张三或李四可以做这件
事”符号化为（）
A.P∨Q
B.P∨?Q
C.P?Q
D. ?(?P∨?Q)
7.下列语句中哪个是真命题？（）
A.我正在说谎。
B.严禁吸烟。
C.如果1+2=3，那么雪是黑的。
D.如果1+2=5，那么雪是黑的。
8.下面哪个联结词运算不可交换？（）
A.∧
B.→
C.∨
D.?
9.命题公式(P∧ (P→Q)) →Q是（）。
A.矛盾式
B.蕴含式
C.重言式
D.等值式
10.下面哪个命题公式是重言式？（）
A.(P→Q)∧(Q→ P)
B.(P∧Q)→P
C.(?P∨Q)∧?(?P∧?Q)
D.?(P∨Q)
11.下列哪一组命题公式是等值的？（）
A. ?P∧?Q,P∨Q
B.A→(B→A),?A→(A→?B)
C.Q→(P∨Q),?Q∧ (P∨Q)
D.?A∨ (A∧B),B
12.P→Q的逆反式是（）
A.Q→?P
B. P →? Q
C. ?Q→P
D. ?Q→?P
13.?P→Q的逆反式是（）
A.Q→?P
B. P →? Q
C. Q→?P
D.P →? Q
14.下列命题联结词集合中，哪一个是最小联结词组？（）
A.{?,?}
B.{?,∨,∧}
C.{↑}
D.{∧,→}
15.下列联结词集合中，哪一个不是最小联结词组？（）
A.{?,∧}
B.{?,→}
C.{?,∧,∨}
D.{↑}
16.已知A是B的充分条件，B是C的必要条件，D是B的必要条件，则A是D的（）
A.充分条件
B.必要条件
C.充要条件
D.A、B、C都不对
17.?P → Q的反换式是（）
A.Q→?P
B.?P→?Q
C.?Q→?P
D.P→?Q
18.下面哪一个命题公式是重言式？（）
A.P→(Q∨R)
B.(P∨R)∧(P→Q)
C.(P∨Q) ? (Q∨R)
D.(P→(Q→R)) →((P→Q) →(P→R))
19.下列哪个命题公式不是重言式？（）
A.Q→(P∨Q)
B.(P∧Q)→P
C.?(P∧?Q) ∧(?P∨Q)
D.(P→Q)?(?P∨Q)
20.重言式的否定式是（）
A.重言式
B.矛盾式
C.可满足式
D.蕴含式
21. 下面哪一个命题是假命题？（）
A.如果2是偶数，那么一个公式的析取范式惟一
B.如果2是偶数，那么一个公式的析取范式不惟一
C.如果2是奇数，那么一个公式的析取范式惟一
D.如果2是奇数，那么一个公式的析取范式不惟一
22. 下面哪一组命题公式不是等值的？（）
A.?(A→B),A∧?B
B.?(A?B),(A∧?B)∨(?A∧B)
C.A→(B∨C),?A∧(B∨C)
D. A→(B∨C),(A∧?B)→C
23.命题公式P→Q∧R的对偶式为（）
A.P→(Q∨R)
B. P∨ (Q∨R)
C.?P∨ (Q∧R)
D.?P∧ (Q∨R)
24.命题公式P→(Q↓R)是（）
A.重言式
B.可满足式
C.矛盾式
D.等值式
25.P??Q?（）
A.?P→ (P→?Q)
B.(?P∨Q)∨ (?Q∨P)
C.(?P∨?Q)∧(?Q∨P)
D.(?P∨?Q)∧(Q∨P)
26.命题公式?(P∧Q)→R的主析取范式中含极小项的个数为（）
A.8
B.3
C.5
D.0
27.命题公式?(P∧Q)→R的主析取范式中含极大项的个数为（）
A.0
B.3
C.5
D.8
28.命题公式?(P∧Q)→R的成真赋值为（）
A.000,001,110
B.001,011,101,110,111
C.全体赋值
D.无
29.如果A?B成立，则以下各种蕴含关系哪一个成立？（）
A.B?A
B.?A??B
C.?B??A
D.?A?B
二、填空题
1.下列句子中，是命题的有
(1).我是教师。
(2).禁止吸烟！
(3).蚊子是鸟类动物。
(4).上课去！
(5).月亮比地球大。
2.设P：我生病，Q：我去学校
(1).命题“我虽然生病但我仍去学校”符号化为。
(2).命题“只有在生病的时候，我才不去学校”符号化为。
(3).命题“如果我生病，那么我不去学校”符号化为。
3.设P：我有钱，Q：我去看电影。
(1).命题“如果我有钱，那么我就去看电影”符号化为。
(2).命题“虽然我有钱，但我不去看电影”符号化为。
(3).命题“当且仅当我有钱时，我才去看电影”符号化为。
4. 对于下列各式，是永真式的有。
(1).(P∧(P→Q))→Q
(2).P→(P∨Q)
(3).Q→(P∧Q)
(4).(?P∧(P∨Q))→Q
(5).(P→Q) →Q
5. (P∧(P∨Q)) →R?。
6. P→(P→Q) 。
7.对于下列各式
(1).(?P∧Q)∨(?P∧?Q)可化简为。
(2).Q→(P∨(P∧Q)) 可化简为。
(3).(?P∨Q)?(?Q→?P)∧P可化简为。
8. 命题公式P∨(Q∧?R)的成真赋值为，成假赋值为。
9. 若且则称X是公式A的子公式。
10.写出表中各列所定义的命题联结词。
P Q P ①Q P ②Q
1 1 1 0
1 0 0 1
0 1 0 1
0 0 0 1
11. 由n个命题变元可组成个不等值的命题公式。
12. 用两种形式写出P↑Q的对偶式①，②。
13. 两个重言式的析取是①，一个重言式与一个矛盾式的析取是②。
14. A、B为两个命题公式，A?B当且仅当①，A?B当且仅当②。
15. 设P、Q为两个命题公式，德●摩根律可表示为①，吸收率可表示为②。
16. 设命题公式A中仅含有联结词?，∧，∨，若得到公式A*，则A*称为A 的对偶式。
17. 公式(P∨Q) →R的只含联结词?，∧，∨的等值式为①，它的对偶式为
②。
18. 命题公式A?(P∧Q∧R)↑0，则其对偶式A*?。
19. 在命题演算中，一个蕴含式与它的①式是等值的，它的②式与它的③是不等值的。
20. 公式?P→Q的反换式为①，逆反式为②。
21. 任意两个不同极小项的合取为①式，全体极小项的析取式必为
②。
22. 命题公式?(P→Q)的主析取范式为①，主合取范式的编码表示为
②。
23. 已知公式A(P,Q,R)的主合取范式为M0∧M3∧M5，它的主析取范式为（写成编码形式）。
24. 命题公式?(P?Q)的主析取范式为①，其编码表示为②，主合取范式的编码表示为③。
25. 对于前提：S→?Q，S∨R，?R, ?P?Q，其有效结论为。
26. 对于前提：(P∧Q) →R，?R∨S, ?S，其有效结论为。
三、判断题
1.“王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。（）
2.凡陈述句都是命题。（）
3.语句3x+5y=0是一个命题。（）
4.命题“两个角相等当且仅当它们是对顶角“的值为1。（）
5.语句“x+y=4”是个命题。（）
6.命题“十减四等于五”是一个原子命题。（）
7.命题“如果1+2=3，那么雪是黑的”是真命题。（）
8.(P→(Q∧R))是一个命题演算的命题公式，其中P、Q、R是命题变元。（）
9.(P→(Q∧R→?Q))是一个命题公式，其中P、Q、R是命题变元。（）
10.若A：张明和李红都是三好学生，则?A：张明和李红都不是三好学生。（）
11.若A：张明和李红都是运动员，则?A：张明和李红不都是运动员。（）
12.若P：每一个自然数都是偶数，则?P：每一个自然数都不是偶数。（）
13.若P：每个自然数都是偶数，则?P：每个自然数不都是偶数。（）
14.如果A?B，则A∧C?B∧C，A∨C?B∨C。（）
15.如果A∧C?B∧C，则A?B。（）
16.联结词“↓”是可结合的。（）
17.联结词“↑”是可结合的。（）
18.联结词“↓”是可交换的。（）
19.联结词“↑”是可交换的。（）
20.联结词“→”是满足交换律。（）
21.“学习有如逆水行舟，不进则退”。设P：学习如逆水行舟，Q：学习进步，R：学
习退步。则命题符号化为P∧(?Q→R)。（）
22.P、Q、R定义同上，则“学习有如逆水行舟，不进则退”形式化为：P→ (?Q→R)。
（）
23.设P、Q是两个命题，当且仅当P、Q的真值均为1时，P?Q的值为1。（）
24.命题公式(P∧(P→Q))→Q是矛盾式。（）
25.命题公式(P∧(P→Q))→Q是重言式。（）
26.联结词∧与∨不是相互可分配的。（）
27.在命题的演算中，每个最小联结词组至少有两个联结词。（）
28.命题联结词集{?,?}是最小联结词集。（）
29.命题联结词集{?,∧,∨}是最小联结词集。（）
30.命题联结词集{∧,→}是最小联结词集。（）
31.命题联结词集{↑}和{↓}是最小联结词集。（）
32.A是命题公式，A与(A*)*互为对偶式。（）
33.A是命题公式，A?(A*)*。（）
34.P是命题变元，P与P互为对偶式。（）
35.任一命题公式的主析取范式和它的主合取范式互为对偶式。（）
36.任一命题公式都可以表示成与其等值的若干极小项的析取式。（）
四、综合题
1.使用命题：
P：这个材料有趣。
Q：这些习题很难。
R：这门课程让人喜欢。
将下列句子用符号形式写出：
(1). 这个材料有趣，并且这些习题很难。
(2). 这个材料无趣，习题也不难，而且这门课程也不让人喜欢。
(3). 如果这个材料无趣，习题也不难，那么这门课程就不会让人喜欢。
(4). 这个材料有趣，意味着这些习题很难，并且反之亦然。
(5). 或者这个材料有趣，或者这些习题很难，并且两者恰具其一。
2.用符号形式写出下列命题：
(1).假如上午不下雨，我去看电影，否则就在家里读书或者看报；
(2).我今天进城，除非下雨；
(3).仅当你走，我将留下；
(4).一个数是素数当且仅当它只能被1和它自身整除。
3.判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。
(1).是无理数。
(2).5能被2整除。
(3).现在开会吗？
(4).x+5>0。
(5).这朵花真好看呀！
(6).2是素数当且仅当三角形有三条边。
(7).雪是黑色的当且仅当太阳从东方升起。
(8).2000年10月1日天气晴好。
(9).太阳系以外的星球上有生物。
(10).小李在宿舍。
(11).全体起立！
(12).4是2的倍数或是3的倍数。
(13).4是偶数且是奇数。
(14).李明与王华是同学。
(15).蓝色和黄色可以调配成绿色。
4.确定下列命题的真值：
(1).“如果太阳从西边出来，那么地球自转”；
(2).“如果太阳从东边出来，那么地球自转停止”；
(3).“如果8+9>30，那么三角形有三条边”；
(4).“如果疑问句是命题，那么地球将停止转动”。
5.判断下面语句是否是命题，若是，确定其真值：
(1).喜马拉雅山比华山高；
(2).如果时间静止不动，你就可以长生不老；
(3).如果时间流失不止，你就可以长生不老；
(4).伦敦是英国首都；
(5).这盆茉莉花好香阿！
6.给命题变元P、Q、R、S分别指派真值为1、1、0、0，求下列命题公式的真值：
(1).(?(P∧Q)∨?R)∨(((?P∧Q)∨?R)∧S)
(2).(P∨(Q→(R∧?P)))?(Q∨?S)
7.设A*、B*分别是命题公式A和B的对偶式，判断下列各式是否成立，若不成立，
请举例说明：
(1).A*?A
(2).A?B则A*?B*
(3).A?B则A*?B*
(4).(A*)*?A
8.命题联结词“↓”定义为P↓Q??(P∨Q)
(1).构造P↓Q的真值表；
(2).证明∨、∧、?可以用仅含联结词↓的等值公式表示。
9.化简下列命题公式：
(1).A∨(?A∨(B∧?B))
(2).(A∧B∧C)∨(?A∧B∧C)
(3).((P→Q)?(?Q→?P))∧R
(4).((A→B)?(?B→?A)∨C
10.如果有A∧C?B∧C，是否一定有A?B?
11.如果有A∨C?B∨C，是否一定有A?B?
12.如果?A??B是否有A?B？
13.用真值表判断下列各式是否为重言式：
(1).((?P∨Q)∧(Q→R))→?(P∧?R)
(2).(P∧Q→R)→(P∧?R∧Q)
14.设命题公式A的真值表如表所示，试求出A的主析取范式和主合取范式（用编码
1 1 1
1 0 1
0 1 0
15.
16.证明下列命题的等值关系：
(1).(P→Q)∧(R→Q)?(P∨R)→Q
(2).(P∧Q∧A→C)∧(A→P∨Q∨C)?(A∧(P?Q))→C
(3).P→(Q→P)?Q→(P→R)
(4).(P→Q)∧(P→R)?P→(Q∧R)
(5).(P∨Q)∧?(P∧Q)??(P?Q)
17.求证下面命题的蕴含关系：
(1).P∧Q?P→Q
(2).(P→(Q→R))?(P→Q)→(P→R)
18.求下面各式的主析取范式与主合取范式，并写出相应的为真赋值。
(1).?(P→Q)?(P→?Q)
(2).(?R∨(Q→P))→(P→Q∨R))
(3).((P→Q)→Q)→((Q→P)→P)
(4).(P→(Q→R))?(R→(Q→P))
(5).?((P→Q)∧(R→P))∨?((R→?Q)→?P
19.联结词f1，f2由表所示真值表定义，证明{ f1，f2}是最小联结词组。
P Q f1P P f1Q
1 1 0 1
1 0 0 1
0 1 1 0
0 0 1 1
20. 设计一种简单的表决器，表决者每人座位旁边有一按钮，若同意则按下按钮，否则不按按钮，当表决结果超过半数时，会场电铃就会响，否则铃不响。试以表决人数为3人的情况设计表决器电路的逻辑关系。
21.证明{↑}时最小联结词组。
22.设计一加法器，实现两自然数相加的功能。
23.某勘探队有3名队员。有一天取得一块矿样，3人的判断如下：
甲说：这不是铁，也不是铜；
乙说：这不是铁，是锡；
丙说：这不是锡，时铁。
经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个全错了。根据以上情况判断矿样的种类。
24.观察下列推理过程，是否正确，结论是否有效，说明理由。
(1).①P∧Q→R P
(2).②P→R T①I
(3).③P P
(4).④R T②③I
所以P∧Q→R，P?R。
25.下列证明过程是否正确，若正确补足每一步推理依据，否则指出错误。
(1).①?D∨A
(2).②D
(3).③A
(4).④A→(C→B)
(5).⑤C→B
(6).⑥C
(7).⑦B
(8).⑧D→B
26.证明A→(B→C)，B→(C→D)?A→(B→D)。
27. 用CP规则证明?P∨(?Q∨R)，Q→(R→S)，P?Q→S。
28.用推理规则说明A→B,?(B∨C)，A∧C是否能同时为真。
29.用推理规则说明(P∨Q)→R，?S∨U，?R∨S，U→W，?W??P∧?Q。
30.用推理规则证明下列推理的正确性：如果A努力工作，那么B或C感到愉快；如
果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。
31.用等值演算法证明?P∧?(P→Q)是矛盾式。
32.用CP规则证明A→(B∧C)，(E→?F)→?C，B→(A∧?S)?B→E。
33.用反证法证明(A→B)∧(C→D)，(B→E)∧(D→F)，?(E∧F)，A→C??A。
34.用反证法证明A→B，(?B∨C)∧?C，?(?A∧D)??D。
第二章
一、选择题
1.谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的作用域是（）
A. ?x(P(x)∨?yR(y))
B.P(x)
C. (P(x)∨?yR(y))
D.P(x)，Q(x)
2.谓词公式?x(P(x)∨?yR(y))→Q(x)中变元x是（）
A.自由变量
B.约束变量
C.既不是自由变量也不是约束变量
D.既是自由变量也是约束变量
3.若个体域为整体域，下列公式中哪个值为真？（）
A.?x?y(x+y=0)
B.?y?x(x+y=0)
C.?x?y(x+y=0)
D.??x?y(x+y=0)
4.设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∧Q(x))在下面哪个论域
中是可满足的？（）
A.自然数集
B.整数集
C.实数集
D.以上均不成立
5.设C(x)：x是运动员，G(x)：x是强壮的。命题“没有一个运动员不是强壮的”可
符号化为（）
A.??x(C(x)∧?G(x))
B.??x(C(x)→?G(x))
C.??x(C(x)∧?G(x))
D.??x(C(x)→?G(x))
6.设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为（）
A.?x(A(x)∧B(x))
B.??x(A(x)→?B(x))
C.??x(A(x)∧B(x))
D.??x(A(x)∧?B(x))
7.设Z(x)：x是整数，N(x)：x是负数，S(x,y)：y是x的平方，则“任何整数的平方
非负”可表示为下述谓词公式（）
A.?x?y(Z(x)∧S(x,y)→?N(y))
B.?x?y(Z(x)∧S(x,y)→?N(y))
C.?x?y(Z(x)→S(x,y)∧?N(y))
D.?x(Z(x)∧S(x,y)→?N(y))
8.令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快。则语句“某些汽车比所有
的火车慢”可表示为（）
A.?y(G(y)→?x(F(x)∧H(x,y)))
B.?y(G(y)∧?x(F(x)→H(x,y)))
C.?x?y(G(y)→(F(x)∧H(x,y)))
D.?y(G(y)→?x(F(x)→H(x,y)))
9.设个体域A={a,b}，公式?xP(x)∧?xS(x)在A中消去量词后应为（）
A.P(x)∧S(x)
B.P(a)∧P(b)∧(S(a)∨S(b))
C.P(a)∧S(b)
D.P(a)∧P(b)∧S(a)∧S(b)
10.在谓词演算中，下列各式哪个是正确的？（）
A.?x?yA(x,y)??y?xA(x,y)
B.?x?yA(x,y)??y?xA(x,y)
C.?x?yA(x,y)??x?yA(x,y)
D.?x?yA(x,y)??y?xA(x,y)
11.下列各式哪个不正确？（）
A.?x(P(x)∨Q(x))??xP(x)∨?xQ(x)
B.?x(P(x)∧Q(x))??xP(x)∧?xQ(x)
C.?x(P(x)∨Q(x))??xP(x)∨?xQ(x)
D.?xP(x)∧Q)??xP(x)∧Q
12.下面谓词公式哪个是前束范式？（）
A.?x?y?z(B(x,y)→A(z))
B.??x?yB(x,y)
C.?x?y?x(A(x,y)∧B(x,y))
D.?x(A(x,y)→?yB(y))
13.在谓词演算中：P(a)是?xP(x)的有效结论，其理论根据是（）
A.全称规定规则(US)
B.全称推广规则(UG)
C.存在规定规则(ES)
D.存在推广规则(EG)
二、填空题
1.令R(x)：x是实数，Q(x)：x是有理数。
(1)命题“并非每个实数都是有理数”。其符号化为①。
(2)命题“虽然有些实数是有理数，但并非一切实数都是有理数”。则其符号化可
表示为②。
2. 设G(x)：x是金子，F(x)：x是闪光的，则命题“金子是闪光的，但闪光的不一定
是金子”符号化为。
3. 设C(x)：x是计算机，P(x,y)：x能做y，I(x)：x是智能工作，则命题“并非所有
智能工作都能由计算机来做”符号化为。
4.设Q(x)：x是偶数，P(x)：x是素数，则命题“存在惟一一个偶素数”可符号化为
①，“至多存在一个偶素数”可符号化为②。
5. 设Q(x)：x是奇数，Z(x)：x是整数，则语句“不是所有整数都是奇数”所对应的
谓词公式为。
6. 设个体域为自然数集，P(x)：x是奇数，Q(x)：x是偶数，则命题“不存在既是奇
数又是偶数的自然数”可符号化为。
7. 设个体域为全总个体域，R(x)：x是实数，Q(x)：x是有理数，Z(x)：x是整数，则
命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数担不是整数”
符号化分别为①，②，③。
8. ?x?y(P(x,y)∧Q(y,z))∧?xP(x,y)中?x的作用域为①，?y的作用域为
②，?x的作用域为③。
9.公式?x(P(x)→Q(x,y)∨?R(y,z))→S(x)中自由变量为①，约束变量为
②。
10.取个体域为整数集，给定下列公式：
(1).?x?y(x·y=0) (2).?x?y(x·y=1)
(3)?x?y(x·y=2) (4)?x?y?z(x-y=z)
(5).x-y=-y+x (5).?x?y(x·y=y)
(7)?x(x·y=x) (8).?x?y(x+y=2y)
上面公式中，真命题的有①，假命题的有②。
*11. 下列谓词公式
(1).?(?xA(x))与?x?A(x)
(2).?x(A(x)∨B(x))与?xA(x)∨?xB(x)
(3).?x(A(x)∧B(x))与?xA(x)∧?xB(x)
(4).?x?yD(x,y)与?y?xD(x,y)
中是等值的。
12.对公式?x(P(x)∨Q(x))，其中P(x):x=1，Q(x):x=2，当论域为{1,2}时，其真值为
①，当论域为{0,1,2}时，其真值为②。
13. 设个体域为A={a,b,c}，消去公式?xP(x)∧?xQ(x)中的量词，可得。
14.下列各式
(1).?x(P(x)∨Q(x))→(?xP(x)∨?xQ(x))
(2).(?x(A(x)→B(x))∧A(c))→A(c)
(3).(?x(?A(x)→B(x))∧?x?B(x))→?xA(x)
(4).(?x(P(x)∧Q(x)))→?xP(x)→?Q(x))
其中是永真式。
15.下列各式
(1).?y?xA(x,y) (2).?x?yA(x,y)
(3).?x?y A(x,y) (4).?x?yA(x,y)
它们之间存在着的推理关系。
可供选择的项有：
A.(1)?(2)；(2) ?(3)
B.(2) ?(1)；(3) ?(4)
C.(1) ?(3)；(4) ?(3)
D.(4) ?(1)；(1) ?(3)
E.(1) ?(3)；(2) ?(4)
16. 填上联结词：?xP(x)∨?xQ(x) ?x(P(x)∨Q(x))
*17. 只用联结词?，?，→，表示以下的公式。
(1).?x(P(x)∧Q(x))= ①；
(2).?x(P(x)??yQ(y))= ②；
(3).?y(?xP(x)∨?Q(y))= ③。
18.给定下面谓词公式：
(1).?x(?F(x)→?F(x))
(2).?xF(x)→?xF(x)
(3).?(F(x)→(?yG(x,y)→F(x)))
(4).?x?yF(x,y)→?x?yF(x,y)
(5).??xF(x)??x?F(x)
(6).?x(F(x)∧G(x))→(?xF(x)∨?xG(x))
(7).?x?yF(x,y)→?x?yF(x,y)
(8).?x(F(x)∨G(x))→(?xF(x)∨?xG(x))
(9).(?xF(x)∨?xG(x))→?x(F(x)∨G(x))
(10).?x?yF(x,y)??y?xF(x,y)
(11).?(?xF(x)→?yG(y))∧?yG(y)
上面11个公式中，为重言式的有①，为矛盾式的有②。
19.给定下列各公式：
(1).(??xF(x)∨?yG(y))∧(F(u)→?zH(z))
(2).?xF(y,x)→?yG(y)
(3).?x(F(x,y)→?yG(x,y))
则①是(1)的前束范式，②是(2)的前束范式，③是(3)的前束范式。
供选择的答案有
①?x?y?z((?F(x)∨G(y))∧(F(u)→H(z)))
②?x?y?z((?F(x)∨G(y))∧(F(u)→H(z)))
③?x?y(F(y,x)→G(y))
④?x?y(F(z,x)→G(y))
⑤?x?y(?F(z,x)∨G(y))
⑥?x?y(F(x,z)→G(x,y))
⑦?x?y(F(x,z)→G(x,y))
⑧?y?x(F(x,z)→G(x,y))
⑨?y?x(?F(x,z)?G(y))
20. 谓词公式?xP(x)→?xQ(x)∨?yR(y)的前束范式为。
21. 谓词公式?x(P(x)→Q(x,y)∨?zR(y,z))→S(x)的前束范式为。
*22. 谓词公式??x(??yG(y,b)→H(x))的前束范式为。
23.在谓词逻辑中给出四个推理：
(1).前提：?x(F(x)→G(x))，?yF(y)；结论：?yG(y)
(2).前提：?x(F(x)∧G(x))；结论：?yF(y)
(3).前提：?xF(x)，?xG(x)；结论：?y(F(y)∧G(y))
(4).前提：?x(F(x)→H(x))，?H(y)；结论：?x(?F(x))
以上四个推理中正确的有。
24.在谓词逻辑中构造下面推理的证明：
每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。
命题符号化：F(x)：x喜欢步行；G(x)：x喜欢坐汽车；H(x)：x喜欢骑自行车。
前提：?x(F(x)→?G(x))，?x(G(x)∨H(x))，?x(?H(x))；
结论：?x(?F(x))。
三、判断题
1. 在谓词公式中，一个变量只能是自由变量或约束变量中的一种。（）
2. 公式?x(P(x)→Q(x))∨R(y)中?x的作用域为P(x)。（）
3. 同一谓词公式，指定不同的论域，其真值不一定相同。（）
4. 谓词公式?xP(x)∧?y(?P(y))是矛盾式。（）
*5. ?x(P(x)→Q(x))→(?xP(x)→?xQ(x))为真。（）
6. 对公式?z(P(z)∧Q(x,z)∧M(z,y))∨R(z)中自由变量代入后，有
?z(P(z)∧Q(a,z)∧M(z,b))∨R(z)（）
7. ?x?y(P(x)→Q(y))??xP(x)→?yQ(y)（）
*8. P(x)，Q(x)表示谓词，P表示命题，有?x(P(x)→P)??xP(x)→P（）
*9. ?x(A(x)∧B(x))??xA(x)∧?xB(x)（）
*10. ?x(A(x)→B(x))??xA(x)∧?xB(x)（）
11. 任意一个谓词公式都与一个前束范式等价。（）
12. 公式?xP(x)→?yQ(x,y)前束范式?x?y(P(x)→Q(x,y))为（）
13. 公式?x(??yP(x,y)→(?zQ(z)→R(x)))的前束范式为?x?y?z(P(x,y)∨?Q(z)∨R(x))（）
14.下面的推理：
条件：?x(P(x)∨Q(x))，根据全称规定（US）有：P(a)∨Q(b)是正确的。（）
15.对公式?z(P(z)∧Q(x,z)∧M(z,y))∨R(z)中约束变量z改名后，得到的等价公式为：
?t(P9t)∧Q(x,t)∧M(t,y))∨R(t)（）
四、综合题
1.用谓词和量词将下列命题符号化：
(1).没有不犯错误的人；
(2).尽管有人聪明，但未必一切人都很聪明；
(3).每个计算机系的学生都学离散数学；
(4).所有的人都学习和工作；
(5).并非一切推理都能用计算机完成；
(6).任何自然数都有惟一的一个后继数。
*2. 令S(x,y,z)表示“x+y=z”，G(x,y)表示“x=y”，L(x,y)表示“x (1).没有x<0，且若x>0当且仅当有这样的y，使得x≥y。 (2).并非对一切x，都存在y，使得x≤y。 (3).对任意的x，若x+y=x，当且仅当y=0。 3. 用谓词公式表示命题“lim() x a f x A → = ”，并写出该命题的否定命题。 *4. 设P(x)：x是外语学的好的学生，Q(x)：x是三好学生，对下述自然语言用谓词符号化： (1).并不是外语学的好的都是三好学生。 (2).有这样的学生，外语学的好而不是三好学生，但外语学不好的学生一定不是三好学生。 5.指出下列公式中量词每次出现的作用域，并指出个体变量是约束变量还是自由变 量。 (1).?x?y(R(x,y)∨L(y,z))∧?xH(x,y) (2).?x(P(x)∧?xQ(x))∨(?xP(x)→Q(x)) 6.设f,g,h是二元运算符号，E，L是二元谓词符号，考查的个体域为有理数集。给出 解释如下： f(x,y)=x·y；g(x,y)=x+y；h(x,y)=x2-y2；a=0；b=1； E(x,y):x=y；L(x,y):x 根据上面的解释，以下公式中哪些为真，哪些为假？ (1).E(f(x,y),g(x,y)) (2).E(f(x,x),h(x,a)) (3).L(x,y)→L(y,x) (4).?xE(f(x,y),b) (5).?E(x,a)∧E(g(y,x),y) 7.在谓词逻辑中将命题(1)(2)(3)符号化，并指出各命题的真值。对应的个体域分别为 ①②③： ①非负整数集N； ②实数集R； ③整数集Z。 (1).对于任意的x，均有(x+1)2=x2+2x+1 (2).存在x，使得x+1=0 (3).存在x，使得5x=1 *8. 假设论域为自然数集N={1,2,3,……}，a为2，P为命题“2>1”；A(x)表示“x>1”；B(x)表示“x是某个自然数的平方”。请在此基础上，求下面公式的真值：?x(A(x)→(A(a)→B(x))→((P→?xA(x))→B(a)) 9.下列各式翻译成自然语言，然后在不同的个体域中确定它们的真值： (1).?x?y(x·y=0) (2).?x?y(x·y=0) (3).?x?y(x·y=1) (4).?x?y(x·y=1) (5).?x?y(x·y=x) (6).?x?y(x·y=x) (7).?x?y?z(x-y=z) 个体域分别为：①实数集②整数集③正整数集④非负实数集 10.设解释T如下：个体域为实数集R，元素a=0，函数f(x,y)=x-y，特定谓词F(x,y)为 x (1).?xF(f(a,x),a) (2).?x?y(?F(f(x,y),x)) (3).?x?y?z(F(x,y)→F(f(x,z),f(y,z))) (4).?x?yF(x,f(f(x,y),y)) 11.求下面谓词公式 ?x(X(x)∧?y(X(y)→((Y(x,z)∧Y(y,z)∧p)→?t(X(t)→(Y(x,t)→Y(y,t)))))) 在赋值(z;p;X(x);Y(x,y))=(2;1;x是自然数;x 12.设解释T为：个体域为D＝{-2,3,6}，谓词F(x)：x≤3，G(x)：x>5，R(x)：x≤7。 根据解释T，求下列各式的真值： (1).?x(F(x)∧G(x)) (2).?x(R(x)→F(x))∨G(5) (3).?x(F(x)∨G(x)) 13.设A(x)是一个含有个体变量x的谓词公式，证明下面等值式成立： ??xA(x)??x(?A(x)) 14.设A(x)，B(x)均为含有自由变量x的任意谓词公式，证明： ?x(A(x)→B(x))??xA(x)→?xB(x) 15. 证明：?x?y(G(x)?H(y))??xG(x)??xH(x)。 16. 设G(x)，H(x)分别是谓词公式，试证明?xG(x)→?xH(x)??x(G(x)→H(x)) 17. 下列公式是否成立，成立则证明，不成立，则举例说明之。 (1).?x?yA(x,y)??x?yA(x,y) (2).?xA(x)∧?xB(x)??x(A(x)∧B(x)) 18. 下面公式是否是永真式？说明理由。 (1).(A→?xB(x))??x(A→B(x)) (2).?x(A(x)→B(x))?(?xA(x)→?xB(x)) 19. 下面的公式是否是永真式？是则证明之，不是，请举出反例： (1).?x?yA(x,y)??y?xA(x,y) (2).(?xA(x)→?xB(x))→?x(A(x)→B(x)) 20. 下面公式是否有效，对有效的公式加以证明，对无效的公式加以反驳。 (1).?x(P(x)∨Q(x))→(?xP(x)∨?xQ(x)) (2).(?xP(x)∨?xQ(x))→?x(P(x)∨Q(x)) 21. 航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明：这个人一定不是航海家。 22．指出下列推理中的错误： (1). ①?xF(x)→G(x) 前提引入 ②F(y)→G(y) ①US (2). ①?x(F(x)∨G(x)) 前提引入 ②F(a)∨G(b) ①US (3). ①F(x)→G(x) 前提引入 ②?y(F(y)→G(y)) ①EG (4). ①F(x)→G(c) 前提引入 ②?x(F(x)→G(x)) ①EG (5). ①F(a)→G(b) 前提引入 ②?x(F(x)→G(x)) ①EG (6). ①?x(F(x)∧G(x)) 前提引入 ②?y(H(y)∧R(y)) 前提引入 ③F(c)∧G(c) ①ES ④F(c) ③化简 ⑤H(c)∧R(c) ②ES ⑥H(c) ⑤化简 ⑦F(c)∧H(c) ④⑥合取 ⑧?x(F(x)∧H(x)) ⑦EG 23. 试找出下列推理过程中的错误，写出正确的推导过程，说明理由： ①?x(P(x)→Q(x)) 条件 ②P(y)→Q(y) 全称规定(US) ③?xP(x) 条件 ④P(y) 存在规定(ES) ⑤Q(y) 由条件②④ ⑥?xQ(x) 存在推广(EG) 24. 下面推理是否是一个有效的推理，为什么？ ①?x?yQ(x,y) 条件 ②?yQ(a,y) 全称规定(US) ③Q(a,b) 存在规定(ES) ④?xQ(x,b) 全称推广(UG) ⑤?y?xQ(x,y) 存在推广(EG) 25. 下面推广是否正确，若有错，请指出： ?x(A(x)→B(x)) ??x(?A(x)∨B(x)) ① ??X?(A(x)∧?B(x)) ② ???x(A(x)∧?B(x)) ③ ??(?xA(x)∧?x?B(x)) ④ ???xA(x)∨??x(?B(x)) ⑤ ???xA(x)∨?xB(x) ⑥ ??xA(x)→?xB(x) ⑦ 26. 用谓词演算推理规则证明： ?x(P(x)→(Q(y)∧R(x)))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 27．改正下面证明中的错误： 前提：?x(?y(S(x,y)∧M(y))→?z(P(z)∧R(x,z)))； 结论：??zP(z)→?x?y(S(x,y)→?M(y))。 证明过程： ①?x(?y(S(x,y)∧M(y))→?z(P(z)∧R(x,z)))；P ②?y(S(b,y)∧M(y))→?z(P(z)∧R(b,z)) ①US ③??zP(z) P(附加前提) ④?z(?P(z)) ③T,E ⑤?P(a) ④US ⑥?P(a)∨?R(b,a) T,⑤I ⑦?z(?P(z)∨?R(b,z)) ⑥UG ⑧??z(P(z)∧R(b,z)) ⑦T,E ⑨??y(S(b,y)∧M(y)) ②,⑧T,L ⑩?y(?S(b,y)∨?M(y)) ⑨T,E ⑾?y(S(b,y)→?M(y)) ⑩T,E ⑿?x?y(S(x,y)→?M(y)) ⑾UG ⒀??zP(z)→?x?y(S(x,y)→?M(y)) CP 第三章 一、选择题 1.对任意集合A、B、C，下述论断正确的是（） A.若A∈B，B?C，则A∈C B.若A∈B，B?C，则A?C C.若A?B，B∈C，则A∈C D.若A?B，B∈C，则A?C 2.设A-B=?，则有（） A.B=? B.B≠? C.A?B D.A?B 3.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x}，则下列选项正确的是（） A.P?Q B.P?Q C.Q?P D.Q=P 4.设A={{1,2,3},{4,5},{6,7,8}}，下列选项正确的是（） A.1∈A B.{1,2,3}∈A C.{{4,5}}∈A D.?∈A 5.下列个选项错误的是（） A.??? B.?∈? C.??{?} D.?∈{?} 6.设A={x|x3-x=0}，B={x|x2-4<0,x∈Z}，C={x|y=2x-1}，D={x|x+y=5,xy=6}，则有（） A.A=B B.A=C C.C=D D.C=A 7. 在0 ?之间填上正确的符号。 A.= B.∈ C.? D.? 8.设M={x|f1(x)=0}，N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（） A.M∩N B.M∪N C.M⊕N D.M-N 9.设A={a,{a}}，下列选项错误的是（） A.{a}∈P(A) B.{a}?P(A) C.{{a}}∈P(A) D.{{a}}?P(A) 10.设A={?}，B=P(P(A))，下列选项错误的是（） A.?∈B B.{?}∈B C.{{?}}∈B D.{?,{?}}∈P(A) 11.幂集P(P(P(?)))为（） A.{{?},{?,{?}}} B.{?,{?,{?}},{?}} C.{?,{?,{?}},{{?}},{?}} D.{?,{?,{?}}} *12.空集?的幂集P(?)的基数是（） A.0 B.1 C.3 D.4 13. 集合A={1,2,…,10}上的关系R={ A.自反的 B.对称的 C.传递的，对称的 D.反自反的，传递的 14.设A={a,b,c}上的关系如下，有传递性的有（） A.ρ1={ B.ρ2={ C.ρ3={ D.ρ4={ 15.设R和S是集合A上的任意关系，则下列命题为真的是（） A.若R和S是自反的，则R?S也是自反的 B.若R和S是反自反的，则R?S也是反自反的 C.若R和S是对称的，则R?S也是对称的 D.若R和S是传递的，则R?S也是传递的 16.若R和S是集合A上的两个关系，则下述结论正确的是（） A.若R和S是自反的，则R∩S也是自反的 B.若R和S是对称的，则R?S也是对称的 C.若R和S是反对称的，则R?S也是反对称的 D.若R和S是传递的，则R∪S也是传递的 17.设A={1,2,3,4,5}，ρ={ 的性质是（） A.对称的 B.自反的 C.反对称的 D.反自反、反对称、传递的 18.设集合A={a,b,c}，R是A上的二元关系，R={ A.反自反的 B.反对称的 C.可传递的 D.不可传递的 19.设R和S是集合A上的等价关系，则R∪S的对称性（） A.一定成立 B.一定不成立 C.不一定成立 D.不可能成立 20.设R和S是非空集合A上的等价关系，下述各式是等价关系的为（） A.(A×A)-R B.R2 C.R-S D.r(R-S) 21.集合A上的关系R是相容关系的必要条件是（） A.自反、反对称的 B.反自反、对称的 C.传递、自反的 D.自反、对称的 22.设R是集合A上的偏序关系， °R是R的逆关系，则R∪°R是（） A.偏序关系 B.等价关系 C.相容关系 D.都不是 23.设集合A中有4个元素，则A上的不同的等价关系的个数为（） A.11个 B.14个 C.15个 D.17个 二、填空题 1. 设M={1≤x≤12，x被2整除，x∈Z}，N={x|1≤x≤12，x被3整除，x∈Z}，则 M∪N=①，M∩N ②。 2.设全集U={1,2,…,7}的子集为A={偶数}，B={奇数}，C={3的倍数}，则A∩B= ①，A∩C=②，A C U=③,B∩C=④。 3.设集合<3，x∈Z}，B={x|x=2k，k∈Z}，C={1,2,3,4,5}。 (1).A⊕C= ① (2).(A⊕B)∩C=② (3).B⊕B= ③ (4).A⊕(C-B)= ④ 4.设I为整数集合，A={x|x2<30，x∈I}，B={x|x是素数，x<20}，C={1,3,5}。 (1).(A∩B)∪C=① (2).(B-A)∪C=② (3).(C-A)∩(B-A)= ③ (4).(B∩C)-A= ④ 5.设全集U={1,2,3,…,20}，A、B、C是其子集，且<4}，B={x|x2-6x-7=0}， C={x|x2<100}。 (1).(A-B)∩C=① (2).A∩B∩C=② (3).(A∩B)-C= ③ 6.设A、B是集合，求A与B之间的关系。 (1).如果A={1}，B={1,{1,2}}，则① (2).如果A=?，B={?}，则② (3).如果A={a}，B={?,a,{?}}，则③ (4).如果A={?}，B={?,{?}}，则④ 供选择项： A.A∈B且A?B B.A∈B且A?B C. A?B但A?B D.A?B且A?B 7. 设A={{x,y},?,x,y}，求下列各式的结果： A-{x,y}= ①；A-{?}= ②；{{x,y}}-A= ③； ?-A= ④；A的幂集P(A)= ⑤。 8. 集合A={?,{a}}的幂集P(A)= 。 9. 集合A={{1,2},{3}},B={{1},{2},{3}}，试写出 A∪B=①，A∩B=②，P(A)=③。 10. 设A={x|100 11. 若集合A的基数|A|=10，则其幂集的基数|P(A)|= 。 12.确定以下各式： (!).?∩{?}= ① (2).{?,{?}}-?= ② (3).{?,{?}}-{?}= ③ 13. 某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是。 14. 某学校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，且其中只有3人同时参加3种球队，那么仅仅参加两种球队得队员人数是。 15. 设A={a,b,c}，则集合S1={{a,b},{b,c}}，S2={{a},{a,b},{a,c}}，S3={{a},{b,c}}，S4={{a,b,c}}，S5={{a},{b},{c}}和S6={{a},{a,c}}中是A的完全覆盖的有①，是A的划分的有②。 16. 设D为同一平面上直线的集合，并且∥表示两直线间的平行关系，⊥表示两直线间的垂直关系，则∥2= ①，⊥2= ②，⊥3= ③。 17. 关系R是反自反的，当且仅当在关系矩阵中①，在关系图上②。 18. 关系R是对称的，当且仅当关系矩阵是①，在关系图上②。 19. 关系R是反对称的，当且仅当关系矩阵是①，在关系图上②。 20. 设A={1,2,3}上的关系R={<1,1>,<1,2>,<1,3>,<3,3>}，则关系R具备①性，不具备②性。 21. 设A={1,2,3,4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则r(R)= ①，s(R)= ②。 22.设集合A仅含有3个元素，那么 (1).在A上可定义. 种不同的二元关系。 (2).在A上可定义种不同的自反关系。 (3).在A上可定义种不同的反自反关系。 (4).在A上可定义种不同的对称关系。 (5).在A上可定义种不同的反对称关系。 23.如果R1和R2是A上的对称关系，有下列观点： (1).R1∪R2是对称的 (2).R1∩R2是对称的 (3).R1?R2是对称的 其中是正确的。 24.如果R1和R2是A上的反对称关系，有下列观点： (1).R1∪R2是反对称的 (2).R1∩R2是反对称的 (3).R1?R2是反对称的 其中是正确的。 25.如果R1和R2是A上的传递关系，有下列观点： (1).R1∪R2是传递关系 (2).R1∩R2是传递关系 (3).R1?R2是传递关系 (4).R12是传递关系 其中是正确的。 26.R是A的二元关系，那么有下列观点： (1).当R是自反关系时，R的传递闭包也是自反关系 (2). 当R是反自反关系时，R的传递闭包也是反自反关系 其中是正确的。 27.R是A的二元关系，那么有下列观点： (1).当R是对称关系时，R的传递闭包也是对称关系 (2). 当R是反对称关系时，R的传递闭包也是反对称关系 其中是正确的。 28. 集合A={a,b,c,d,e,f,g}，A上的一个划分π={{a,b},{c,d,e},{f,g}}，那么π所对应的 等价关系R应有个有序对。 29. 设R是集合{1,2,…,10}上的模7同余关系，则[2]R= 。 30. 设R1和R2是A的相容关系，那么对于下列观点： (1).R1∪R2是相容关系 (2).R1∩R2是相容关系 (3).R1?R2是相容关系 其中是正确的。 *31. 整数集上的小于关系“<”具有①，②和③关系。 32. 设A={a,b,c}上偏序关系(P(A),?)，则P(A)的子集B={?,{a},{b},{a,b},{b,c}}的极大 元是①，最大元是②，上界是③，下确界是④。 33. A={2,3,4,5,6,8,10,12,24}，R是A上的整除关系。那么A的极大元是①， 极小元是②。 34. A={1,2,3,4,5,6,7,8,9,10,11,12}，R是A上的整除关系。子集B={2,4,6}，那么B的 最大元是①，B的最小元是②，B的上界是③，B的下界是④。 35. A={1,2,3,4,5,6,8,10,24,36}，R是A上的整除关系。子集B={1,2,3,4}，那么B的上 界是①，B的下界是②，B的上确界是③，B的下确界是④。 三、判断题 1. 若A⊕B=A⊕C，则B=C。（） 2. 若P∪Q=Q，P∩Q=?，则P=?。（） 3. {?}∈{?,{?}}且{?}?{?,{?}}。（） 4. 设A={?}，B=P(P(A))，则有{?}∈B，且{?}?B。（） 5. A，B是集合，则命题A?B和A∈B可能同时成立。（） 6. 设A，B为任意集合，则P(A-B)=P(A)-P(B)。（） 7. 若A-B?B，则B?A。（） 8. 对每个集合A，有{A}?P(A)。（） 9. 设A与B是任意两个集合，若{A∩B,B-A}是A∪B的一个划分，则有A-B=?。（） 10. 若{A-B,B-A}是集合A∪B的一个划分，则有A∩B=?，其中A≠?，B≠?。（） 11. 设A，B是两个任意的集合，若{A∩B,A-B,B-A}是A∪B的一个划分，则有A∩B=?， A-B=?，B-A=?。（） 12. 若{A∩B}是A∪B的一个划分，则有A-B=B-A=?。（） 13. 若R是集合A上的传递关系，则R2也是集合A上的传递关系。（） °R也是对称的。（） 14. 若集合A上的关系R是对称的，则 15. 一个不是自反的关系，一定是反自反的。（） 16. 集合A={1,2,3}的任何关系R都不可能既是对称的，又是反对称的。（） 17. 集合A={a,b,c}上的关系R={ 18. 若R和S是集合A上的任意两个自反关系，则R?S也是自反的。（） 19. 若R和S是集合A上的任意两个反自反关系，则R?S也是反自反的。（） 20. 若R和S是集合A上的任意两个对称关系，则R?S也是对称的。（） 21. 若R和S是集合A上的任意两个传递关系，则R?S也是传递的。（） 第二次在线作业 1.（ 2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 ?正确 ?错误 我的答案：正确此题得分：2.5分 2.（2.5分）设< L*1*2> 是代数系统，其中是*1*2二元运算符，如果*1*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L*1*2> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 ?正确 ?错误 我的答案：正确此题得分：2.5分 4.（2.5分）零元是不可逆的 ?正确 ?错误 我的答案：正确此题得分：2.5分 5.（2.5分）群中每个元素的逆元都是惟一的 ?正确 ?错误 我的答案：正确此题得分：2.5分 6.（2.5分）设abc是阿贝尔群< G+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) ?正确 ?错误 我的答案：正确此题得分：2.5分 7.（2.5分） < {01234}MAXMIN> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 ?正确 ?错误 我的答案：正确此题得分：2.5分 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 ?正确 ?错误 我的答案：正确此题得分：2.5分 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 ?正确 ?错误 我的答案：正确此题得分：2.5分 11.（2.5分）不含回路的连通图是树 ?正确 ?错误 我的答案：正确此题得分：2.5分 12.（2.5分）简单图邻接矩阵主对角线上的元素全为0 ?正确 ?错误 我的答案：正确此题得分：2.5分 13.（2.5分）树一定是连通图 ?正确 ?错误 我的答案：正确此题得分：2.5分 14.（2.5分）无向图的邻接矩阵是对称阵 ?正确 ?错误 我的答案：正确此题得分：2.5分 15.（2.5分）不与任何结点相邻接的结点称为孤立结点 ?正确 ?错误 我的答案：正确此题得分：2.5分 离散数学（第五版）清华大学出版社第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令F(x):x是鸟 G(x):x会飞翔. 命题符号化为 ?x(F(x)→G(x)). (2)令F(x):x为人. G(x):x爱吃糖 命题符号化为 ??x(F(x)→G(x)) 或者 ?x(F(x)∧?G(x)) (3)令F(x):x为人. G(x):x爱看小说. 命题符号化为 ?x(F(x)∧G(x)). (4) F(x):x为人. G(x):x爱看电视. 命题符号化为 ??x(F(x)∧?G(x)). 分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的F(x)都是特性谓词。 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 27 ?x(F(x)∧G(x)) 即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 ?xF(x) 其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。 （2）在(a),(b),(c)中均符号化为 ?xG(x) 其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在(a),(b),(c)中均符号化为 ?xH(x) 其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。 分析1°命题的真值与个体域有关。 2°有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 ?xF(x) 这里，F(x):x呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ?x(F(x)→G(x)) 这里，F(x):x为人，且F(x)为特性谓词。G(x):x呼吸。 28 2．3 因题目中未给出个体域，因而应采用全总个体域。 （1）令：F(x):x是大学生，G(x):x是文科生，H(x):x是理科生，命题符号化为?x(F(x)→(G(x)∨H(x)) （2）令F(x):x是人，G(y):y是化，H(x):x喜欢，命题符号化为 ?x(F(x)∧?y(G(y)→H(x,y))) （3）令F(x):x是人，G(x):x犯错误，命题符号化为 ??x(F(x)∧?G(x)), 或另一种等值的形式为 ?x(F(x)→G(x) 集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作 不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取 一、填空题 1. 设A = {1, 2}, B = {2, 3}, 则A - A =________, A – B =________, B – A =________. 2. 设N 是自然数集合, f 和g 是N 到N 的函数, 且f (n ) = 2n +1，g (n ) = n 2, 那么复合函数(f f ) (n )=________ , (f g ) (n )=________ , (g f ) (n ) =________. 3. 设|X | = n , P (X )为集合X 的幂集, 则| P (X )| = ________. 在代数结构(P (X ), ∪)中，则P (X ) 对∪运算的单位元是________, 零元是________ . 4. 在下图中， _______________________________是其Euler 路 . 5. 设有向图G = (V , E )，V = {v 1，v 2，v 3，v 4}，若G 的邻接矩阵A =???? ??????1001001111011010, 则v 1的出度deg +(v 1) =________, v 1的入度deg -(v 1) =________, 从v 2到v 4长度为2的路有________条. 二、单选题 1. 设A = {{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是( ) (A) 1∈A (B) {1, 2, 3}?A (C) {{4, 5}}?A (D) ?∈A . 2．集合A = {1, 2, …, 10}上的关系R ={(x , y )|x + y = 10, x , y ∈A }, 则R 的性质是 ( ) (A) 自反的 (B) 对称的 (C) 传递的、对称的 (D) 反自反的、传递的. 3．若R 和S 是集合A 上的两个关系，则下述结论正确的是( ) (A) 若R 和S 是自反的, 则R ∩S 是自反的 (B) 若R 和S 是对称的, 则R S 是对称的 (C) 若R 和S 是反对称的, 则R S 是反对称的 (D) 若R 和S 是传递的, 则R ∪S 是传递的. 4．集合A = {1, 2, 3, 4}上的关系 R = {(1, 4), (2, 3), (3, 1), (4, 3)}, 则下列不是．．t (R )中元素的是( ) (A) (1, 1) (B) (1, 2) (C) (1, 3) (D) (1, 4). 5．设p ：我们划船，q ：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( ) (A) ? p ∧? q (B) ? p ∨? q 《离散数学》模拟试题3 一、填空题（每小题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. 已知命题公式R Q P G→ ∧ ? =) (，则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分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0 离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】 一、填空题 1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________; (A)-(B)＝__________________________. 2.设有限集合A,|A|=n,则|(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是 _______________________________________,其中双射的是 __________________________. 4.已知命题公式G＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则 2013年4月考试离散数学第二次作业 一、单项选择题（本大题共50分，共 25 小题，每小题 2 分） 1. 下列语句中为命题的是（） A. 暮春三月，江南草长. B. 这是多么可爱的风景啊！ C. 大家想做什么，就做什么，行吗？ D. 请勿践踏草地！ 2. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（） A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 3. 集合|A|=3，|B|=2，则A B上不同的函数个数为（）。 A. 3+2个 B. 32个 C. 2*3个 D. 23个 4. 设A-B=φ，则以下正确的是（）。 A. A＝B B. A?B C. B?A D. 以上都不对 5. 设R为实数集，函数f：R→R，f(x)=2x，则f是（） A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射 6. 设B={a,b,c},C={1,2,3,4}，以下哪个关系是从B到C的单射函数？（） A. f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B. f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C. f={<1,7>,<2,7>,<4,9>,<3,8>} D. f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} E. f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>} 7. 下述*运算为实数集上的运算，其中可交换且可结合的运算是（）。 A. a*b=a+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b| 8. 在下列命题中，为真的命题是（） A. 汉密顿图一定是欧拉图 B. 无向完全图都是欧拉图 C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出 D. 有割点的连通图是汉密顿图 9. 设p:小李努力学习，q:小李取得好成绩，命题“只有小李努力学习，他才能取得好成绩”的符号化形式为（）。 A. B. C. 常熟理工学院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.（2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 正确 错误 正确答案： 2.（2.5分）设< L,*1,*2> 是代数系统，其中是*1,*2二元运算符，如果*1,*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L,*1,*2> 是格 正确 错误 正确答案： 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 正确 错误 正确答案： 4.（2.5分）零元是不可逆的 正确 错误 正确答案： 5.（2.5分）群中每个元素的逆元都是惟一的 正确 错误 正确答案： 6.（2.5分）设a,b,c是阿贝尔群< G,+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) 正确 错误 正确答案： 7.（2.5分） < {0,1,2,3,4},MAX,MIN> 是格 正确 错误 正确答案： 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 正确 错误 正确答案： 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 正确 错误 正确答案： 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 正确 错误 正确答案： 11.（2.5分）不含回路的连通图是树 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。 离散数学作业布置 第1次作业（P15） 1.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 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，所以这一段的论述为真。 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 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111 离散数学（第五版）清华大学出版社第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们 都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来 的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许 多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结 的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→ｑ。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→ｑ为假命题。 （7）p→ｑ，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→ｑ为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G= 第6章 函数 一、选择题（每题3分） 1、设{,,},{1,2,3}A a b c B ==，则下列关系中能构成A 到B 函数的是（ C ） A 、1{,1,,2,,3}f a a a =<><><> B 、2{,1,,1,,2}f a b b =<><><> C 、4{,1,,1,,1}f a b c =<><><> D 、1{,1,,2,,2,,3}f a a b c =<><><><> 2、设R Z N 、、分别为实数集、整数集，自然数集，则下列关系中能构成函数的是（ B ） A 、)}10(),(|,{<+∧∈> 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P 全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ? ?????001110101 B ．???? ? ?????101110001 离散数学 1.在自然推理系统P 中构造下面推理的证明： 前提：,,p q r q r s ?∨∨?→ 结论：p s →. 3设一阶逻辑公式 ((,)(()()))G x yP x y zQ z R x =???→?→ 试将G 化成与其等价的前束范式。 4.判断下面推理是否正确，并证明你的结论。 如果小王今天家里有事，则他不会来开会。 如果小张今天看到小王，则小王今天来开会了。 小张今天看到小王。所以小王今天家里没事。 5、构造下面推理的证明 前提： ))()(()),()()((x R x F x x H x G x F x ∧?∧→? 结论: ))()()((x G x R x F x ∧∧? 6用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ??→∧→=的类型。 7分别用真值表法和公式法求(P →(Q ∨R ))∧(?P ∨(Q ?R ))的主析取范式 ，并写出其相应的成真赋值和成假赋值。 8用逻辑推理证明： 所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。 9、设A ＝{?，1，{1}}，B ＝{0，{0}}，求P (A )、P (B )－{0}、P (B )⊕B 。 10、设X ＝{1，2，3，4}，R 是X 上的二元关系，R ＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)画出R 的关系图。 (2)写出R 的关系矩阵。 (3)说明R 是否是自反、反自反、对称、传递的。 11、集合X={<1,2>, <3,4>, <5,6>,… }，R={<离散数学第二次在线作业
离散数学(第五版)清华大学出版社第2章习题解答
离散数学第四章二元关系和函数知识点总结
《离散数学》第2次作业
离散数学第五版 模拟试题 及答案
离散数学试题及答案精选版
2013年4月考试离散数学第二次作业
离散数学题库
中石油北京19春《离散数学》第二次在线作业
离散数学题库及答案
离散数学作业 (2)
离散数学(第五版)清华大学出版社第1章习题解答
电大离散数学作业答案作业答案
离散数学函数复习题答案
山东大学离散数学题库及答案
离散数学及答案
离散数学题库
相关主题
文本预览