厦门大学离散数学期末试卷2007年(数学学院)

《厦门大学离散数学期末试卷2007年(数学学院)》由会员分享，可在线阅读，更多相关《厦门大学离散数学期末试卷2007年(数学学院)（5页珍藏版）》请在金锄头文库上搜索。

1、From: LockLoveHsw 1 / 5 一、一、 选择选择题题（共（共 1 15 5 题，每题题，每题 2 2 分，共分，共 3 30 0 分）分） 1下列语句不是命题的有（ ）。 Ax=13。 B离散数学是计算机系的一门必修课。 C鸡有三只脚。 D太阳系以外的星球上有生物。 2设 p：天下大雨，q：小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上 班”的符号化形式为（ ）。 Apq Bqp Cp q D pq 3谓词公式)()()(xQyyRxPx中的x( )。 A只是约束变元。 B只是自由变元。 C既非约束变元又非自由变元。 D既是约束变元又是自由变元。 4. 下面式子中

2、，（ ）是不正确的。 A.)()()()(xxBxxAxBxAx B.)()()()(xxBxxAxBxAx C.BxxABxAx)()( D.)()(xxBAxBAx 5设个体域为整数集合，则下列公式中真值为 1 的是( )。 Axy(x + y = 1)。 Bxy(x + y = 1)。 Cxy(x + y = 1)。 D xy(x + y = 1)。 6下列命题为假的是( )。 厦门大学厦门大学离散数学离散数学课程试卷课程试卷 数学科学数学科学学院学院 2007 年级年级 主考教师：主考教师：金贤安金贤安 试卷类型： （试卷类型： （A A 卷）卷） From: LockLoveHsw

3、2 / 5 A P() B P() C P() DP() P() 7下列关于集合的势的叙述中，（ ）是错误的。 A. 实数集比自然数集优势。 B. 任一无限集合都存在与自己等势的真子集。 C. 集合类上的优势关系是偏序关系。 D. 有理数集比整数集优势。 8设CBA,是集合，F是关系，则下列式子中不正确的是（ ）。 ABBABA B. CBCABA)()( C. BFAFBAF D. )()(CBACBA 9设 A=1,2,3,100，R 是 A 上相等关系“=” ，由 R 产生等价类有（ ） 。 A10 个 B50 个 C100 个 D1 个 10集合 A=1，2，3，4上的偏序关系 R 的

4、关系图为 则它的哈斯图为（ ） 。 11下列关系中能构成函数的是（ ） 。 A)10(),( |,yxNyxyx B)(),( |,2xyRyxyx C)(),( |,2xyRyxyx D)3mod(),( |,yxZyxyx 12N是自然数集，定义3mod )()( ,:xxfNNf（即x除以 3 的余数） ，则f是（ ） 。 From: LockLoveHsw 3 / 5 A满射不是单射 B单射不是满射 C双射 D不是单射也不是满射 13设 R 为实数集，定义*运算如下：a*b=|a+b+ab|，则*运算满足（ ）。 A结合律 B交换律 C有幺元 D幂等律 14. 数的乘法在下列集合中不封

5、闭的有（ ）。 A1 , 0 B为素数xx C.,2Zbaba D1xCxx且 15下图所示的哈斯图所表示的偏序集中不是格的是（ ） 。 二二、填空填空题题（共（共 1010 空空，每，每空空 2 2 分，共分，共 2 20 0 分）分） 1命题 a a,3,4,1 的真值 = _。 2已知集合 A=,1,2，则 A 的幂集 P(A) =_。 3含 n 个命题变项的重言式的主合取范式为_。 4设集合 A=a,b,c,d ，则 A 上的不同的等价关系共有_个，A 上有_个不同的 双射函数。 5设 B 为布尔代数，a,b,cB，则(ab)(ac)a 的化简式为_。 6. 设 F(x):x 是人，H

6、(x,y):x 与 y 一样高，在一阶逻辑中，命题“人都不一样高”的符号化 形式为_。 7 公式)(),(),()(xSzyRzyxQxPx的自由变元是 ， 约束变元是 。 8设A=, , B=,则BA= 。 三、三、计算题计算题（每题每题 5 5 分分，共共 1515 分）分） 1 （5 分）求命题公式)()(qprpp的主析取范式。 2 （5 分）设集合 A=a，b，c，d，A 上的关系 R=, 求： （1）画出 R 的关系图。(1 分) （2）R 的自反闭包、对称闭包和传递闭包的关系图。 （1 分，1 分和 2 分） 3.（5 分）设为一偏序集，其中 A=1，2，3，4，6，8，12，2

7、4，R 是 A 上的整除关系。 （1）画出偏序集的哈斯图。（3 分） From: LockLoveHsw 4 / 5 （2）求 A 的极大元和极小元。（1 分） （3）求 B=2,3,6的最小上界和最大下界。（1 分） 四四、简答、简答题题（共共 1010 分）分） 1 （4 分）设解释 R 如下：DR是实数集，DR中特定元素 a=0，DR中特定函数yxyxf),(，特定谓词yxyxF: ),(， 问公式),(),(),(zyfzxfFyxFzyxA的涵义如何？ （2分）真值如何？（2 分） 2 （6 分）判断下列公式是否是永真式？并说明理由。 (1) (xA(x)xB(x)x(A(x)B(x

8、)。 （3 分） (2) (xA(x)xB(x)x(A(x)B(x)。 （3 分） 五五、证明证明题题（共（共 2525 分）分） 1 （10 分） （1） （5 分）在命题逻辑的自然推理系统中构造下面推理的证明。 前提：(PQ)，QR，R 结论：P （2） （5 分）在谓词逻辑的自然推理系统中构造下面推理的证明。 前提：x（A（x）B（x） ） ，x B（x） 结论：x A（x） 2 （5 分）叙述并证明容斥原理。 （2 分和 3 分） 3 （5 分）设 R 是集合 A 上的一个具有传递和自反性质的关系，T 是 A 上的关系，使得 TR且R，证明 T 是一个等价关系。 4 （5 分）设1 ,

9、 0 ,B是布尔代数，a,bB，试证0)()(bababa当且仅当。 六六 应用题应用题（该题为该题为附加题附加题，8 分）分） 甲、乙、丙、丁 4 个人有且仅有 2 个人参加围棋优胜比赛。关于谁参加竞赛，下列 4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 From: LockLoveHsw 5 / 5 答案： 四：2 解 (1)(xA(x)xB(x)x(A(x)B(x) (xA(x)xB(x)x(A(x)B(x) (xA(x)xB(x)x(A(x)B(x) (xA(x)

10、xB(x)xA(x)xB(x) (xA(x)xA(x)xB(x)(xB(x)xA(x)xB(x) x(A(x)A(x)xB(x) T 所以，(xA(x)xB(x)x(A(x)B(x)为永真式。 (2)设论域为1，2，令 A(1)T；A(2)F；B(1)F；B(2)T。 则xA(x)为假，xB(x)也为假，从而xA(x)xB(x)为真；而由于 A(1)B(1)为假，所以x(A(x)B(x)也为假，因此公式(xA(x)xB(x)x(A(x)B(x)为假。该公式不是永真式。 五：3 证明 因 R 自反，任意 aA，有R，由 T 的定义，有T，故 T 自反。 若T，即R 且R，也就是R 且R，从而T，故 T对称。 若T，T，即R 且R，R 且R，因 R 传递，由R 和R 可得R，由R 和R 可得R，由R 和R 可得T，故 T 传递。 所以，T 是 A 上的等价关系。