离散数学(一)[数理逻辑与集合论]试题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/(x3+8),x≠-2
D.f(x)=x3+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是传递的当且仅当R2R,其中R2表示RR。(9分)
19.证明下面关于集合A和B的命题是相互等价的。(9分)
(a) AB (b) A∪B=B (c) A∩B=A
20.所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。请用谓词逻辑中的推理理论证明上述推理。(个体域:所有人的集合)(10分)