离散数学同步练习册a.docx
- 文档编号:13036653
- 上传时间:2023-06-10
- 格式:DOCX
- 页数:33
- 大小:150.42KB
离散数学同步练习册a.docx
《离散数学同步练习册a.docx》由会员分享,可在线阅读,更多相关《离散数学同步练习册a.docx(33页珍藏版)》请在冰点文库上搜索。
离散数学同步练习册a
第一章命题逻辑
一、填空题
(1)设:
p:
派小王去开会。
q:
派小李去开会。
则命题:
“派小王或小李中的一人去开会”可符号化
为:
(⌝p∧q)∨(p∧⌝q)。
(2)设A,B都是命题公式,A⇒B,则A→B的真值是1或T。
(3)设:
p:
刘平聪明。
q:
刘平用功。
在命题逻辑中,命题:
“刘平不但不聪明,而且不用功”可符号化为:
⌝p∧⌝q。
(4)设A,B代表任意的命题公式,则蕴涵等值式为
A→B⇔⌝B→⌝A。
(5)设,p:
径一事;q:
长一智。
在命题逻辑中,命题:
“不径一事,不长一智。
”可符号化为:
⌝p→⌝q。
(6)设A,B代表任意的命题公式,则德∙摩根律为
⌝(A∧B)⇔⌝A∨⌝B 。
(7)设,p:
选小王当班长;q:
选小李当班长。
则命题:
“选小王或小李中的一人当班长。
”可符号化为:
(⌝p∧q)∨(p∧⌝q)。
(8)设,P:
他聪明;Q:
他用功。
在命题逻辑中,命题:
“他既聪明又用功。
”可符号化为:
p∧q。
(9)对于命题公式A,B,当且仅当A→B是重言式时,称“A蕴含B”,并记为A⇒B
。
(10)设:
P:
我们划船。
Q:
我们跑步。
在命题逻辑中,命题:
“我们不能既划船又跑步。
”可符号化为:
⌝(P∧Q)。
(11)设P,Q是命题公式,德·摩根律为:
⌝(P∨Q)⇔⌝P∧⌝Q。
(12)设P:
你努力。
Q:
你失败。
在命题逻辑中,命题:
“除非你努力,否则你将失败。
”可符号化为:
⌝p→q。
(13)设p:
小王是100米赛跑冠军。
q:
小王是400米赛跑冠军。
在命题逻辑中,命题:
“小王是100米或400米赛跑冠军。
”可符号化为:
p∨q。
(4)设A,C为两个命题公式,当且仅当A→C为一重言式时,称C可由A逻辑地推出
。
二.判断题(判断下列命题的对错。
正确的在括号内填√,错误的在括号内填×)
1.设A,B是命题公式,则蕴涵等值式为A→B⇔⌝A∧B。
(×)
2.命题公式⌝p∧q∧⌝r是析取范式。
(√)
3.陈述句“x+y>5”是命题。
(×)
4.110(p=1,q=1,r=0)是命题公式((⌝(p∧q))→r)∨q的成真赋值。
(√)
5.命题公式p→(⌝p∧q)是重言式。
(×)
6.设A,B都是合式公式,则A∧B→⌝B也是合式公式。
(√)
7.A∨(B∧C)⇔(A∨B)∨(A∨C)。
(×)
8.陈述句“我学英语,或者我学法语”是命题。
(√)
9.命题“如果雪是黑的,那么太阳从西方出”是假命题。
(×)
10.“请不要随地吐痰!
”是命题。
(×)
11.P→Q⇔⌝P∧Q。
(×)
12.陈述句“如果天下雨,那么我在家看电视”是命题。
(√)
13.命题公式(P∧Q)∨(⌝R→T)是析取范式。
(×)
14.命题公式(P∧⌝Q)∨R∨(⌝P∧Q)是析取范式。
(√)
三、选择题:
在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的内。
1.设:
P:
天下雪。
Q:
他走路上班。
则命题“只有天下雪,他才走路上班。
”可符号化为
(2)。
(1)P→Q
(2)Q→P
(3)⌝Q→⌝P
(4)Q∨⌝P
2.
(1)明年国庆节是晴天。
(2)在实数范围内,x+y〈3。
(3)请回答这个问题!
(4)明天下午有课吗?
在上面句子中,是命题的只有
(1)。
3.命题公式A与B是等值的,是指(4)。
(1)A与B有相同的命题变元
(2)A↔B是可满足式
(3)A→B为重言式
(4)A↔B为重言式
4.
(1)雪是黑色的。
(2)这朵花多好看呀!
。
(3)请回答这个问题!
(4)明天下午有会吗?
在上面句子中,是命题的是
(1)。
5.设:
P:
天下大雨。
Q:
他乘公共汽车上班。
则命题“只要天下大雨,他就乘公共汽车上班。
”
可符号化为
(1)(因为天下雨,他可能不上班,不是充分条件)。
(1)Q→P
(2)P→Q
(3)⌝Q→⌝P
(4)Q∨⌝P
6.设:
P:
你努力;Q:
你失败。
则命题“除非你努力,否则你将失败。
”
在命题逻辑中可符号化为(3)。
(1)Q→P
(2)P→Q
(3)⌝P→Q(4)Q∨⌝P
7.
(1)现在开会吗?
(2)在实数范围内,x+y>5。
(3)这朵花多好看呀!
(4)离散数学是计算机科学专业的一门必修课。
在上面语句中,是命题的只有(4)。
8.设:
P:
天气好。
Q:
他去郊游。
则命题“如果天气好,他就去郊游。
”
可符号化为
(2)(理解为他去郊游,一定是在天气好的时候;但天气好的时候很多,不可能都在郊游)
(1)P→Q
(2)Q→P
(3)⌝Q→⌝P(4)Q∨⌝P
9.下列式子是合式公式的是
(2)。
(1)(P∨→Q)
(2)⌝(P→(Q∨R))
(3)(P⌝Q)(4)∧Q→R
10.
(1)1+101=110
(2)中国人民是伟大的。
(3)全体起立!
(4)计算机机房有空位吗?
在上面句子中,是命题的是
(2)。
11.设:
P:
他聪明;Q:
他用功。
则命题“他虽聪明但不用功。
”
在命题逻辑中可符号化为(4)。
(1)P∧Q
(2)P→Q
(3)P∨⌝Q(4)P∧⌝Q
12.
(1)如果天气好,那么我去散步。
(2)天气多好呀!
(3)x=3。
(4)明天下午有会吗?
在上面句子中
(1)是命题。
13.设:
P:
王强身体很好;Q:
王强成绩很好。
命题“王强身体很好,成绩也很好。
”在命题逻辑中可符号化为(4)。
(1)P∨Q
(2)P→Q
(3)P∧⌝Q(4)P∧Q
四、解答题
1.设命题公式为(⌝p→q)→(q→⌝p)。
(1)求此命题公式的真值表;
(2)给出它的析取范式;
(3)判断该公式的类型。
解
(1)真值表如下
p
q
⌝p
⌝p→q
q→⌝p
(⌝p→q)→(q→⌝p)
0
0
1
0
1
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
0
1
0
0
(2)(⌝p→q)→(q→⌝p)
⌝(p∨q)∨(⌝q∨⌝p)
(⌝p∧⌝q)∨⌝q∨⌝p(析取范式)
(⌝p∧⌝q)∨(p∧⌝q)∨(⌝p∧q)(主析取范式)
(3)该公式为可满足式
2.设命题公式为(p→q)∧(p∨r)。
(1)求此命题公式的真值表;
(2)给出它的析取范式;
(3)判断该公式的类型。
解
(1)真值表如下
p
q
r
p→q
p∨r
(p→q)∧(p∨r)
0
0
0
1
0
0
0
0
1
1
1
1
0
1
0
1
0
0
0
1
1
1
1
1
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
1
1
1
(2)(p→q)∧(p∨r)
(⌝p∨q)∧(p∨r)
(⌝p∧(p∨r))
∨(q∧(p∨r))
(⌝p∧r)∨(q∧r)∨(q∧p)(析取范式)
(⌝p∧r∧(q∨⌝q))∨(q∧r∧(p∨⌝p))∨(q∧p∧(r∨⌝r))
(⌝p∧q∧r)∨(⌝p∧⌝q∧r)∨(p∧q∧r)∨(⌝p∧q∧r)∨(p∧q∧r)∨(p∧q∧⌝r)
(⌝p∧⌝q∧r)∨(⌝p∧q∧r)∨(p∧q∧⌝r)∨(p∧q∧r)(主析取范式)
(3)该公式为可满足式
3.设命题公式为⌝Q∧(P→Q)→⌝P。
(1)求此命题公式的真值表;
(2)求此命题公式的析取范式;
(3)判断该命题公式的类型。
解
(1)真值表如下
P
Q
⌝Q
P→Q
⌝Q∧(P→Q)
⌝P
⌝Q∧(P→Q)→⌝P
0
0
1
1
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
1
0
0
1
(2)⌝Q∧(P→Q)→⌝P
⌝(⌝Q∧(⌝P∨Q))∨⌝P
(Q∨⌝(⌝P∨Q))∨⌝P
⌝(⌝P∨Q)∨(Q∨⌝P)
1(析取范式)
(⌝P∧⌝Q)∨(⌝P∧Q)∨(P∧⌝Q)∨(P∧Q)(主析取范式)
(3)该公式为重言式
4.完成下列问题
(1)求此命题公式(P∧(Q→R))→S的真值表;
(2)求命题公式(P∧(Q→R))→S的析取范式。
解
(1)真值表如下
P
Q
R
S
Q→R
P∧(Q→R))
(P∧(Q→R))→S
0
0
0
0
1
0
1
0
0
0
1
1
0
1
0
0
1
0
1
0
1
0
0
1
1
1
0
1
0
1
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
0
0
1
1
0
1
0
0
1
1
1
1
1
0
1
0
1
1
0
1
0
1
1
1
1
1
1
1
0
0
0
0
1
1
1
0
1
0
0
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
(2)(P∧(Q→R))→S
⌝(P∧(⌝Q∨R))∨S
(⌝P∨⌝(⌝Q∨R))∨S
⌝P∨(Q∧⌝R)∨S(析取范式)
5.设命题公式为(P∧(P→Q))→Q。
(1)求此命题公式的真值表;
(2)判断该公式的类型。
解
(1)真值表如下
P
Q
P→Q
P∧(P→Q)
(P∧(P→Q))→Q
0
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
1
(2)该公式为重言式
6.设命题公式为((P∨Q)∧⌝P)→Q。
(1)求此命题公式的真值表;
(2)给出它的析取范式;
(3)判断该公式的类型。
解
(1)真值表如下
P
Q
⌝P
P∨Q
(P∨Q)∧⌝P
((P∨Q)∧⌝P)→Q
0
0
1
0
0
1
0
1
1
1
1
1
1
0
0
1
0
1
1
1
0
1
0
1
(2)((P∨Q)∧⌝P)→Q
⌝((P∨Q)∧⌝P)∨Q
(⌝(P∨Q)∨P)∨Q
⌝(P∨Q)∨(Q∨P)
1(析取范式)
(⌝P∧⌝Q)∨(⌝P∧Q)∨(P∧⌝Q)∨(P∧Q)(主析取范式)
(3)该公式为重言式
7.用直接证法证明
前提:
P∨Q,P→R,Q→S
结论:
S∨R
证
(1)P∨QP
(2)⌝P→QT
(1)E
(3)Q→SP
(4)⌝P→ST(2,3)I
(5)⌝S→PT(4)E
(6)P→RP
(7)⌝S→RT(5,6)I
(8)S∨RT(7)E
8.用直接证法证明
前提:
P→(Q∨R),S→⌝Q,P,S。
结论:
R
证
(1)PP
(2)P→(Q∨R)P
(3)Q∨RT(1,2)I
(4)SP
(5)S→⌝QP
(6)⌝QT(4,5)I
(7)RT(3,6)I
第二章谓词逻辑
一填空题
(1)若个体域是含三个元素的有限域{a,b,c},则
∃xA(x)⇔A(a)∨A(b)∨A(c)
(2)取全总个体域,令F(x):
x为人,G(x):
x爱看电影。
则命题“没有不爱看电影的人。
”可符号化为___⌝∃x(F(x)∧⌝G(x))___。
(3)若个体域是含三个元素的有限域{a,b,c},则
∀xA(x)⇔A(a)∧A(b)∧A(c)。
(4)取全总个体域,令M(x):
x是人,G(y):
y是花,H(x,y):
x喜欢y。
则命题“有些人喜欢所有的花。
”可符号化为_∃x(M(x)∧∀y(G(y)→H(x,y)))。
(5)取个体域为全体人的集合。
令F(x):
x在广州工作,G(x):
x是广州人。
在一阶逻辑中,命题“在广州工作的人未必都是广州人。
”可符号化为__∃x(F(x)∧⌝G(x))___。
(6)P(x):
x是学生,Q(x):
x要参加考试。
在谓词逻辑中,命题:
“每个学生都要参加考试”可符号化为:
(∀x)(P(x)→Q(x))。
(7)M(x):
x是人,B(x):
x勇敢。
则命题“有人勇敢,但不是所有的人都勇敢”谓词符号化为(∃x)(M(x)∧B(x))∧⌝(∀x)(M(x)→B(x))。
(8)P(x):
x是人,M(x):
x聪明。
则命题“尽管有人聪明,但不是一切人都聪明”谓词符号化为__(∃x)(P(x)∧M(x))∧⌝(∀x)(P(x)→M(x))_。
(9)I(x):
x是实数,R(x):
x是正数,N(x):
x是负数。
在谓词逻辑中,命题:
“任何实数或是正的或是负的”可符号化为:
(∀x)(I(x)→(⌝R(x)∧N(x))∨(R(x)∧⌝N(x)))。
(10)P(x):
x是学生,Q(x):
x要参加考试。
在谓词逻辑中,命题:
“有些学生可以免考”可符号化为:
(∃x)(P(x)∧⌝Q(x))。
(11)令M(x):
x是大学生,P(y):
y是运动员,H(x,y):
x钦佩y。
则命题“有些大学生不钦佩所有运动员。
”可符号化为__∃x(M(x)∧∀y(P(y)→⌝H(x,y)))__。
二.判断题(判断下列命题的对错。
正确的在括号内填√,错误的在括号内填×)
1.设A,B都是谓词公式,则∀xA↔⌝B也是谓词公式。
(√)
2.设c是个体域中某个元素,A是谓词公式,则A(c)⇒∀xA(x)。
(×)
3.∀x∀yA(x,y)⇔∀y∀xA(x,y)。
(√)
4.∀x∃yA(x,y)⇔∃y∀xA(x,y)。
(×)
5.取个体域为整数集,则谓词公式∀x∀y(x⨯y=y)是假命题。
(√)
6.(∀x)(P(x)→Q(x))⇔(∀x)(⌝P(x)∨Q(x))。
(√)
7.命题公式(P∧⌝Q∨R)∨(⌝P∧Q)是析取范式。
(×)
8.谓词公式(∀x)(A(x)→B(x,y))∧R(x)的自由变元为x,y。
(√)
9.((∀x)A(x)→B)⇔(∃x)(A(x)→B)。
(√)
10.R(x):
“x是大学生。
”是命题。
(×)
三、选择题:
在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的内。
1.设F(x):
x是火车,G(x):
x是汽车,H(x,y):
x比y快。
命题“某些汽车比所有火车慢”的符号化公式是
(2)。
(1)∃y(G(y)→∀x(F(x)∧H(x,y)))
(2)∃y(G(y)∧∀x(F(x)→H(x,y)))
(3)∀x∃y(G(y)→(F(x)∧H(x,y)))
(4)∃y(G(y)→∀x(F(x)→H(x,y)))
2.设个体域为整数集,下列真值为真的公式是(3)。
(1)∃y∀x(x–y=2)
(2)∀x∀y(x–y=2)
(3)∀x∃y(x–y=2)
(4)∃x∀y(x–y=2)
3.设F(x):
x是人,G(x):
x早晨吃面包。
命题“有些人早晨吃面包”在谓词逻辑中的符号化公式是(4)。
(1)(∀x)(F(x)→G(x))
(2)(∀x)(F(x)∧G(x))
(3)(∃x)(F(x)→G(x))
(4)(∃x)(F(x)∧G(x))
4.下列式子中正确的是(4)。
(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)
5.下面谓词公式是永真式的是
(2) 。
(1)P(x)→Q(x)
(2)(∀x)P(x)→(∃x)P(x)
(3)P(a)→(∀x)P(x)
(4)⌝P(a)→(∃x)P(x)
6.设S(x):
x是运动员,J(y):
y是教练员,L(x,y):
x钦佩y。
命题“所有运动员都钦佩一些教练员”的符号化公式是(3)。
(1)∀x(S(x)∧∀y(J(y)∧L(x,y)))
(2)∀x∃y(S(x)→(J(y)→L(x,y)))
(3)∀x(S(x)→∃y(J(y)∧L(x,y)))
(4)∃y∀x(S(x)→(J(y)∧L(x,y)))
7.下列式子是合式公式的是
(2)。
(1)(P∨→Q)
(2)⌝(P∧(Q∨R))
(3)(P⌝Q)(4)∧Q→∧R
8.下列式子中正确的是同4题。
(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)
四、解答题
1.构造下面推理的证明:
前提:
∃xF(x)→∀y((F(y)∨G(y))→R(y)),
∃xF(x)。
结论:
∃xR(x)。
证
(1)∃xF(x)P
(2)F(c)ES
(1)
(3)∃xF(x)→∀y((F(y)∨G(y))→R(y))P
(4)(∀x)(F(x)→∀y((F(y)∨G(y))→R(y)))T(3)E
(5)F(c)→((F(c)∨G(c))→R(c))US(4)
(6)(F(c)∨G(c))→R(c))T(2,5)I
(7)F(c)∨G(c)T
(2)I
(8)R(c)T(6,7)I
(9)(∃x)R(x)EG(8)
2.在一阶逻辑中构造下面推理的证明
每个喜欢步行的人都不喜欢坐汽车。
每个人或者喜欢坐汽车或者喜欢骑自行车。
有的人不喜欢骑自行车。
因而有的人不喜欢步行。
令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)∃x⌝H(x)P
(2)⌝H(c)ES
(1)
(3)∀x(G(x)∨H(x))P
(4)G(c)∨H(c)US(3)
(5)G(c)T(4)I
(6)∀x(F(x)→⌝G(x))P
(7)F(c)→⌝G(c)US(6)
(8)⌝F(c)T(5,7)I
(9)(∃x)⌝F(x)EG(8)
3.在命题逻辑中构造下面推理的证明:
如果他是理科学生,他必须学好数学。
如果他不是文科学生,他必是理科学生。
他没学好数学,所以他是文科学生。
解A:
他是理科学生,B:
他学好了数学,C:
他是文科学生
前提:
A→B,A∨C,⌝B结论:
C
证
(1)A→BP
(2)⌝BP
(3)⌝AT(1,2)I
(4)A∨CP
(5)CT(3,4)I
4.用直接证法证明:
前提:
(∀x)(C(x)→W(x)∧R(x)),(∃x)(C(x)∧Q(x))
结论:
(∃x)(Q(x)∧R(x))。
证
(1)(∃x)(C(x)∧Q(x))P
(2)C(c)∧Q(c)ES
(1)
(3)(∀x)(C(x)→W(x)∧R(x))P
(4)C(c)→W(c)∧R(c)US(3)
(5)C(c)T
(2)I
(6)W(c)∧R(c)T(4,5)I
(7)R(c)T(6)I
(8)Q(c)T
(2)I
(9)Q(c)∧R(c)T(7,8)I
(10)(∃x)(Q(x)∧R(x))EG(9)
第三章集合与关系
一、填空题
(1)如果|A|=n,那么|A×A|=
。
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,2>,<2,2>,<2,3>}。
(4)如果|A|=n,那么|P(A)|=
。
(5)设集合A上的关系R和S,R={<1,2>,<2,1>,<3,4>,<4,3>},S={<1,3>,<3,1>,<2,4>,<4,2>},则R◦S={<1,4>,<2,3>,<3,2>,<4,1>}。
(6)设集合E={a,b,c},E的幂集P(E)={Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。
(7)设R是定义在集合X上的二元关系,如果对于每个x,y∈X,
_每当xRy,就有yRx_,则称集合X上的关系R是对称的。
(8)设关系R和S为,R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>},则R◦S=__{<1,5>,<3,2>,<2,5>}__。
(9)设R是定义在集合X上的二元关系,如果对于每个x∈X,有xRx,则称集合X上的关系R是自反的。
二.判断题(正确的在括号内填√,错误的在括号内填×)
1.设A、B、C为任意的三个集合,则A×(B×C)=(A×B)×C。
(×)
2.设S,T是任意集合,如果S-T=∅,则S=T。
(×)
3.集合A={1,2,3,4}上的关系{<1,2>,<2,3>,<2,4>,<3,4>}是一个函数。
(×)
4.集合A={1,2,3,4}上的整除关系是等价关系。
(×)
5.集合A的幂集P(A)上的包含关系是偏序关系。
(√)
6.设A={a,b,c},R∈A×A且R={,},则R是传递的。
(√)
6.设A,B是任意集合,如果B≠∅,则A–B≠A。
(×)
7.集合A={1,2,3}上的关系{<1,1>,<2,2>,<3,3>,<1,2>}是传递的。
(√)
8.集合A={1,2,3,4}上的小于关系是等价关系。
(×)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 同步 练习