离散数学(上)

　　　　　　　　　　　离散数学(一)[数理逻辑与集合论]试题1

一、选择（每题3分，共27分）
1. 前提p∨q，┌q∨r，┌r的结论是（）
A．q
B．┌p
C．p∨q
D．┌p→r
2. 下列语句中为命题的是（）
A．暮春三月，江南草长
B．这是多么可爱的风景啊！
C．大家想做什么，就做什么，行吗？
D．请勿践踏草地！
3. 设F（x）表示x是火车，G（x）表示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）））
4. 利用谓词的约束变元改名规则和自由变元代入规则，可将如下公式：（

x）（P（x）→Q（x，y））∧R（x，y）改写成（）
A．（

x）（P（y）→Q（x，y））∧R（z，s）
B．（

z）（P（z）→Q（z，s））∧R（x，s）
C．（

x）（P（s）→Q（x，s））∧R（x，y）
D．（

x）（P（s）→Q（z，s））∧R（z，s）
5. 下列公式中正确的等价式是（）
A．┌（

x）A（x）（

x）┌A（x）
B．┌（

x）A（x）（

x）┌A（x）
C．（

x）（

y）A（x，y）（

y）（

x）A（x，y）
D．（

x）（A（x）∧B（x））（

x）A（x）∨（

x）B（x）
6. 设A＝{Φ}，B＝P（P（A）），以下不正确的式子是（）
A．{{Φ}，Φ}∈B
B．{{Φ}}∈B
C．{{Φ}}包含于B
D．{{{{Φ}}，Φ}}包含于B
7. 设f是实数集R到R的函数，则f（x）为双射函数的是（）
A．

B．f（x）＝lnx，x>0
C．f（x）＝1/（x³＋8），x≠－2
D．f（x）＝x³＋8
8. 设集合A＝{1，2，3}，下列关系R中不是等价关系的是（）
A．R＝{<1，1>，<2，2>，<3，3>}
B．R＝{<1，1>，<2，2>，<3，3>，<3，2>，<2，3>}
C．R＝{<1，1>，<2，2>，<3，3>，<1，4>}
D．R＝{<1，1>，<2，2>，<1，2>，<2，1>，<1，3>，<3，1>，<3，3>，<2，3>， <3，2>}
9. 设A＝{a，b，c}，B＝{a，b}，则下列命题不正确的是（）
A．A∪B＝{a，b}
B．BA
C．A－B＝{c}
D．B－A＝Φ
　　　　

二、填空（每空2分，共20分）
10．设p：1＋1＝5，q：明天是阴天，则命题“只要1＋1＝5，那么明天是阴天”可符号化为_____________，其真值是________。
11．在公式（

A）（P（z）→Q（x，z））∧（

z）R（x，z）中，

A的辖域是___________________，

z的辖域是__________________。
12．设R为非空集合A上的二元关系，如果R具有自反性、___________、__________则称R为A上的一个偏序关系。
13．设x＝{1，3，5，9，15，45}，R是x上的整除关系，则R是x上的偏序，其最大元是___________，极小元是_________。
14．给定命题公式（P∨Q）→R，该公式在联接词集合{┌,→}中的形式为__________，在联接词集合{┌,∧}中的形式为__________ 。
　　

三、计算和证明
15．设个体域D＝{2，3，6}，F（x）：x≤3，G（x）：x>5，消去公式

x（F（x）∧

yG（y））中的量词，并讨论其真值。（8分）
16．用等值演算法求公式┌（p→q）→（p→q）的主合取范式。（8分）
17．设A＝{a，b，c}，求A上所有等价关系。（9分）
18．设R是A上的二元关系，试证：R是传递的当且仅当R²R，其中R²表示RR。（9分）
19．证明下面关于集合A和B的命题是相互等价的。（9分）
(a) AB (b) A∪B＝B (c) A∩B＝A
20．所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。请用谓词逻辑中的推理理论证明上述推理。（个体域：所有人的集合）（10分）
　　