离散数学同步练习
a)x(S(x)y(J(y)L(x,y)))
b)xy(S(x)(J(y)L(x,y)))
c)x(S(x)y(J(y)L(x,y)))
d)yx(S(x)(J(y)L(x,y)))
6.下列式子是合式公式的是。
(1)(PQ)(2)(P(QR))
(3)(PQ)(4)QR
7.下列式子中正确的是。
(1)(x)P(x)(x)P(x)
(7)M(x):x是人,B(x):x勇敢。则命题“有人勇敢,但不是所有的人都勇敢”谓词符号化为___________________________________________。
(8)P(x):x是人,M(x):x聪明。则命题“尽管有人聪明,但不是一切人都聪明”谓词符号化为__________________________________________。
令F(x):x喜欢步行。G(x):x喜欢坐汽车。H(x):x喜欢骑自行车。
3.在命题逻辑中构造下面推理的证明:
如果他是理科学生,他必须学好数学。如果他不是文科学生,他必是理科学生。他没学好数学,所以他是文科学生。
4.用直接证法证明:
前提:(x)(C(x)→W(x)∧R(x)),(x)(C(x)∧Q(x))
(7)设R是定义在集合X上的二元关系,如果对于任意x,yX,
______________________,则称集合X上的关系R是对称的。
(8)设关系R和S为,R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>},则R◦S=__________________________。
(4)如果|A|=n,那么|P(A)|=2n。
(5)设集合A上的关系R和S,R={<1,2>,<2,1>,<3,4>,<4,3>},S={<1,3>,<3,1>,<2,4>,<4,2>},则R◦S=。
(6)设集合E={a,b,c},E的幂集P(E)=___________________________。
(9)I(x):x是实数,R(x):x是正数,N(x):x是负数。在谓词逻辑中,命题:
“任何实数或是正的或是负的”可符号化为:。
(10)令M(x):x是大学生,P(y):y是运动员,H(x,y):x钦佩y。则命题“有些大学生不钦佩所有运动员。”可符号化为_______________________。
xA(x)
(2)取全总个体域,令F(x):x为人,G(x):x爱看电影。则命题“没有不爱看电影的人。”可符号化为_____________________________________。
(3)若个体域是含三个元素的有限域{a,b,c},则
xA(x)。
(4)取全总个体域,令M(x):x是人,G(y):y是花, H(x,y):x喜欢y。则命题“有些人喜欢所有的花。”可符号化为_________________________。
3.集合A={1,2,3,4}上的整除关系是等价关系。()
4.集合A的幂集P(A)上的包含关系是偏序关系。()
5.设A={a,b,c}, RA×A且R={< a,b>,< a,c>},则R是传递的。()
6.设A,B是任意集合,如果B,则A–BA。()
。
二.判断题
1.设A,B是命题公式,则等价式ABAB。()
2.命题公式pqr是析取范式。()
3.陈述句“x + y >5”是命题。()
4.110 (p=1,q=1, r=0)是命题公式(((pq))r)q的成真赋值。()
5.命题公式p(pq)是重言式。()
6.设A,B都是合式公式,则ABB也是合式公式。()
(8)设,P:他聪明;Q:他用功。在命题逻辑中,命题:
“他既聪明又用功。”可符号化为:。
(9)对于命题公式A,B,当且仅当是重言式时,称“A蕴含B”,并记为AB
。
(10)设:P:我们划船。Q:我们跑步。在命题逻辑中,命题:
“我们不能既划船又跑步。”可符号化为:。
(11)设P,Q是命题公式,德·摩根律为:
5.下列式子中正确的是。
(1)(x)P(x)(x)P(x)
(2)(x)P(x)(x)P(x)
(3)(x)P(x)(x)P(x)
(4)(x)P(x)(x)P(x)
6.下面谓词公式是永真式的是。
a)P(x)Q(x)
b)(x)P(x)(x)P(x)
c)P(a)(x)P(x)
d)P(a)(x)P(x)
5.设S(x):x是运动员,J(y):y是教练员,L(x,y):x钦佩y。命题“所有运动员都钦佩一些教练员”的符号化公式是。
14.命题公式(PQ)R(PQ)是析取范式。()
三、选择题:在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的内。
1.设:P:天下雪。Q:他走路上班。则命题“只有天下雪,他才走路上班。”可符号化为。
(1)PQ
(2)QP
(3)QP
(4)QP
2.(1)明年国庆节是晴天。
(2 )在实数范围内,x+y〈3。
(3 )请回答这个问题!
(4 )明天下午有课吗?
在上面句子中,是命题的只有。
3.命题公式A与B是等值的,是指。
(1)A与B有相同的命题变元
(2)AB是可满足式
(3)AB为重言式
(4)AB为重言式
4.(1)雪是黑色的。
(2 )这朵花多好看呀!。
(3 )请回答这个问题!
(4 )明天下午有会吗?
在上面句子中,是命题的是。
(2)(x)P(x)(x)P(x)
(3)(x)P(x)(x)P(x)
(4)(x)P(x)(x)P(x)
四、解答题
1.构造下面推理的证明:
前提:xF(x)y((F(y)G(y))R(y)),
xF(x)。
结论:xR(x)。
2.在一阶逻辑中构造下面推理的证明
每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。
2.设命题公式为(pq)(pr)。
(1)求此命题公式的真值表;
(2)给出它的析取范式;
3.设命题公式为Q(PQ)P。
(1)求此命题公式的真值表;
(2)求此命题公式的析取范式;
4.完成下列问题
(1)求此命题公式Q(PQ)P的真值表;
(2)求命题公式(P∧(Q→R))→S的析取范式。
5.设命题公式为(P(PQ))Q。
(9)设R是定义在集合X上的二元关系,如果对于每个xX,
______________________,则称集合X上的关系R是自反的。
二.判断题
1.设S,T是任意集合,如果ST =,则S = T。()
2.集合A={1,2,3,4}上的关系{<1,2>,<2,3>,<2,4>,<3,4>}是一个函数。()
(1)yx(x–y=2)
(2)xy(x–y=2)
(3)xy(x–y=2)
(4)xy(x–y=2)
3.设F(x):x是人,G(x):x早晨吃面包。命题“有些人早晨吃面包”在谓词逻辑中的符号化公式是。
(1)(x)(F(x)G(x))
(2)(x)(F(x)G(x))
(3)(x)(F(x)G(x))
(4)(x)(F(x)G(x))
5.设:P:天下大雨。Q:他乘公共汽车上班。则命题“只要天下大雨,他就乘公共汽车上班。”
可符号化为。
(1)QP
(2)PQ
(3)QP
(4)QP
6.设:P:你努力;Q:你失败。则命题“除非你努力,否则你将失败。”
在命题逻辑中可符号化为。
(1)QP(2)PQ
(3)PQ(4)QP
7.(1)现在开会吗?
(2 )在实数范围内,x+y5。
(4)设A , B代表任意的命题公式,则等价式
AB。
(5)设,p:径一事;q:长一智。在命题逻辑中,命题:
“不径一事,不长一智。”可符号化为:。
(6)设A , B代表任意的命题公式,则德摩根律为
(AB)。
(7)设,p:选小王当班长;q:选小李当班长。则命题:“选小王或小李中的一人当班长。”可符号化为:。
7.A(BC)( AB)(AC)。()
8.陈述句“我学英语,或者我学法语”是命题。()
9.命题“如果雪是黑的,那么太阳从西方出”是假命题。()
10.“请不要随地吐痰!”是命题。()
11.PQPQ。()
12.陈述句“如果天下雨,那么我在家看电视”是命题。()
13.命题公式(PQ)(RT)是析取范式。()
1.设F(x):x是火车,G(x):x是汽车,H(x,y):x比y快。命题“某些汽车比所有火车慢”的符号化公式是。
(1)y(G(y)x(F(x)H(x,y)))
(2)y(G(y)x(F(x)H(x,y)))
(3)xy(G(y)(F(x)H(x,y)))
(4)y(G(y)x(F(x)H(x,y)))
2.设个体域为整数集,下列真值为真的公式是。
结论:(x)(Q(x)∧R(x))。
第三章集合与关系
一填空题
(1)如果|A|=n,那么|A×A|=n2。A上的二元关系有_________个。
(2)集合A上关系R的自反闭包r(R)=___________________。
(3)设集合A上的关系R和S,R={(1,2),(1,3),(3,2)},S={(1, 3),(2,1),(3,2)},则S◦R=。
二.判断题
1.设A,B都是谓词公式,则xAB也是谓词公式。()