中央广播电视大学 试卷习题 数理逻辑部分综合练习_离散数学

离散数学数理逻辑部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习， 这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己 检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是数理逻辑部分的 综合练习。 一、单项选择题 1.设P我将去市里，我有时间.命题“我将去市里，仅当我有时间时”符号化为 0 A.Q→PB.P→QC.PQD.PV-Q 2.设命题公式G一P→(QAR),则使公式G取真值为1的P,Q,R赋值分别是O A.0,0,0B.0,0,1C.0,1,0D.1,0,0 3.下列公式0为重言式. A.PA→VB.(Q→(PV0)→((V0)） C.(P→(Q→PD)→(P→(P→0)D.(-v(PA0)→Q 4.下列等价公式成立的为(). A.PA=RvB.P→(Q→乃台P→(P→0 C.Q((RD.R(PA 5.命题公式一(P→Q)的主析取范式是0. A.PA-OB.POC.-PVOD.PVO 6.命题公式(PVQ)→R的析取范式是() A.(PVQ)VRB.(PAQ)VR C.(PVQ)VRD.(PA-Q)VR 7.设C(x):x是国家级运动员，G(x):x是健壮的，则命题“没有一个国家级运动员不 是健壮的”可符号化为0. A.一x(C(x)AG(x)B.x(C(x)→G(x) C.x(C(x)>G(x))D.x(C(x)G(x)) 8.设A(x):x是人，B(x):x是学生，则命题“不是所有人都是学生”可符号化 为(). A.(廿x)(A(x)∧B(x))B.(3x)(A(x)∧B(x)) C.7(付x)(A(x)→B(x)D.7(3x)(A(x)∧7B(x)) 9.表达式x(P(x,y)VQ(z)∧3y(R(x,y)→zQ(z)中x的辖域是0. A.P(x,y)B.P(x,y)vQ(z)C.R(x,y)D.P(x,y)AR(x,y)

1 离散数学数理逻辑部分综合练习 本课程综合练习共分 3 次，分别是集合论部分、图论部分、数理逻辑部分的综合练习， 这 3 次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己 检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是数理逻辑部分的 综合练习。 一、单项选择题 1．设 P：我将去市里，Q：我有时间．命题“我将去市里，仅当我有时间时”符号化为 () A．Q → P B． P → Q C． P  Q D．P  Q 2．设命题公式 G： P →(Q  R) ,则使公式 G 取真值为 1 的 P，Q，R 赋值分别是() A．0,0,0B．0,0,1C．0,1,0D．1,0,0 3．下列公式()为重言式． A．PQPQB．(Q→(PQ))(Q(PQ)) C．(P→(Q→P))(P→(P→Q))D．(P(PQ))Q 4．下列等价公式成立的为()． A．PQPQB．P→(Q→P)P→(P→Q) C．Q→(PQ)Q(PQ)D．P(PQ)Q 5．命题公式 (P → Q) 的主析取范式是()． A． P  Q B． P  Q C．P  Q D． P  Q 6．命题公式（P∨Q）→R 的析取范式是() A．（P∨Q）∨RB．（P∧Q）∨R C．（P∨Q）∨RD．（P∧Q）∨R 7．设 C(x):x 是国家级运动员，G(x):x 是健壮的，则命题“没有一个国家级运动员不 是健壮的”可符号化为()． A． x(C(x)  G(x)) B． x(C(x) → G(x)) C． x(C(x) → G(x)) D． x(C(x)  G(x)) 8．设 A（x）：x 是人，B（x）：x 是学生，则命题“不是所有人都是学生”可符号化 为（）． A．(  x)(A(x)∧B(x))B．┐(  x)(A(x)∧B(x)) C．┐(x)(A(x)→B(x))D．┐(  x)(A(x)∧┐B(x)) 9．表达式 x(P(x, y)  Q(z))  y(R(x, y) → zQ(z)) 中 x 的辖域是()． A．P(x,y)B．P(x,y)Q(z)C．R(x,y)D．P(x,y)R(x,y)

二、填空题 1.命题公式P→(QyP)的真值是. 2.设P他生病了，Q他出差了.R我同意他不参加学习.则命题“如果他生病或出 差了，我就同意他不参加学习”符号化的结果为， 3.含有三个命题变项P,Q,R的命题公式P入Q的主析取范式是， 4.设F(x):x是鸟，G(x):x会飞翔.则命题“鸟会飞”符号化为 5.设个体域上{1,2}，那么谓词公式3x4(x)VyBy)消去量词后的等值式为. 6.设个体域D={a,b,c,则谓词公式（付x)A(x)消去量词后的等值式为 7.设个体域D={a,b},则谓词公式（付x)A(x)∧（臼x)B(x)消去量词后的等值式为 A(a)∧A(b))∧(B(a)VB(b 8.设个体域D={1,2},则谓词公式3x4(x)消去量词后的等值式为， A(1)VA(2) 9.谓词命题公式（付x)(P(x)→Q(x)V(x,))中的约束变元为， 10.(付x)(P(x)→Q(x)V(x,))中的自由变元为. 三、公式翻译题 1.请将语句“今天不是天晴”翻译成命题公式。 2.将语句“今天没有下雨.”翻译成命题公式. 3.将语句“今天没有人来.”翻译成命题公式 4.将语句“他不去学校.”翻译成命题公式。 5.将语句“尽管他接受了这个任务，但他没有完成好.”翻译成命题公式. 6.将语句“小王去旅游，小李也去旅游.”翻译成命题公式 7.将语句“他去旅游，仅当他有时间.”翻译成命题公式 8.请将语句“我去书店，仅当天不下雨”翻译成命题公式， 9.将语句“如果所有人今天都去参加活动，则明天的会议取消.”翻译成命题公式， 10.将语句“如果你去了，那么他就不去.”翻译成命题公式： 11.请将语句“有人不去工作”翻译成谓词公式， 12.将语句“有人去上课.”翻译成谓词公式. 13.请将语句“所有人都努力工作.”翻译成谓词公式。 14.将语句“所有人都去工作.”翻译成谓词公式 15.将语句“所有的人都学习努力.”翻译成命题公式。 四、判断说明题（判断下列各题，并说明理由.） 1.命题公式(Q→P)ΛP为永假式 2.命题公式7P∧(PQ)VP为永真式 3.下面的推理是否正确，试予以说明

2 二、填空题 1．命题公式 P Q P →  ( ) 的真值是． 2．设 P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出 差了，我就同意他不参加学习”符号化的结果为． 3．含有三个命题变项 P，Q，R 的命题公式 PQ 的主析取范式是． 4．设 F(x)：x 是鸟，G(x)：x 会飞翔．则命题“鸟会飞”符号化为． 5．设个体域 D={1,2},那么谓词公式 xA(x)  yB(y) 消去量词后的等值式为． 6．设个体域 D＝{a,b,c}，则谓词公式(x)A(x)消去量词后的等值式为． 7．设个体域 D＝{a,b}，则谓词公式(x)A(x)∧（x）B（x）消去量词后的等值式为． A(a)∧A(b))∧(B（a）∨B（b） 8．设个体域 D＝{1,2}，则谓词公式 xA(x) 消去量词后的等值式为． A(1)A(2) 9．谓词命题公式(x)(P(x)→Q(x)∨R(x，y))中的约束变元为． 10．(x)(P(x)→Q(x)∨R(x，y))中的自由变元为． 三、公式翻译题 1．请将语句“今天不是天晴”翻译成命题公式． 2．将语句“今天没有下雨．”翻译成命题公式． 3．将语句“今天没有人来．”翻译成命题公式． 4．将语句“他不去学校．”翻译成命题公式． 5．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式． 6．将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 7．将语句“他去旅游，仅当他有时间．”翻译成命题公式． 8．请将语句“我去书店，仅当天不下雨”翻译成命题公式． 9．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式． 10．将语句“如果你去了，那么他就不去．”翻译成命题公式． 11．请将语句“有人不去工作”翻译成谓词公式． 12．将语句“有人去上课．”翻译成谓词公式． 13．请将语句“所有人都努力工作．”翻译成谓词公式． 14．将语句“所有人都去工作．”翻译成谓词公式． 15．将语句“所有的人都学习努力．”翻译成命题公式． 四、判断说明题（判断下列各题，并说明理由．） 1．命题公式 (Q → P)  P 为永假式． 2．命题公式┐P∧（P→┐Q）∨P 为永真式． 3．下面的推理是否正确，试予以说明．

(1)(x)F(x)→G(x)前提引入 (2)F(y)→G(y)US(1). 五.计算题 1.(1)求命题公式一(P→Q)A(P→一Q)的主析取范式、主合取范式： (2)求该命题公式的成假赋值 2.求公式(PAQ)→R的析取、合取、主析取、主合取范式。 3.求P→wR的析取范式，合取范式、主析取范式，主合取范式 4.试求出(PVQ)→R的析取范式，合取范式，主合取范式. 5.求(PVQ)→(VQ)的合取范式 6.设谓词公式3x(P(x,y)→Q(y,x,)∧yR(y,z)←→F(y).试 (1)写出量词的辖域： (2)指出该公式的自由变元和约束变元. 六、证明题 1.试证明命题公式(P→(w0)APQ与(RvQ)等价 2.试证明（臼x)(P(x)∧R(x))三（臼x)P(x)∧(3x)R(x). 参考解答 一、单项选择题 1.B2.D3.C4.B5.A6.D7.D 8.C9.B 二、填空题 1.T(或1) 2.(0→R 3.(PAOAR(PAO-R) 4.(x)(F(x)→G(x)) 5.(A(1)vA(2)v(B(1)AB(2) 6.A(a)∧A(b)∧A(c) 7.A(a)∧A(b)∧(B(a)VB(b) 8.A(1)VA(2) 9.x 10.R(x,月中的y 三、公式翻译题 1.解：设P今天是天晴： 则P. 2.解：设P今天下雨， 3

3 (1)（x）F（x）→G（x）前提引入 (2)F（y）→G（y）US（1）． 五．计算题 1．（1）求命题公式 (P → Q)  (P → Q) 的主析取范式、主合取范式； （2）求该命题公式的成假赋值． 2．求公式 (P  Q) → R 的析取、合取、主析取、主合取范式． 3．求 P→QR 的析取范式，合取范式、主析取范式，主合取范式． 4．试求出（P∨Q）→R 的析取范式，合取范式，主合取范式． 5．求（P∨Q）→（R∨Q）的合取范式． 6．设谓词公式 x(P(x, y) → zQ( y, x,z))  yR( y,z)  F( y) ．试 （1）写出量词的辖域； （2）指出该公式的自由变元和约束变元． 六、证明题 1．试证明命题公式(P→(QR))PQ 与（PQ）等价． 2．试证明（x）（P（x）∧R（x））（x）P（x）∧（x）R（x）． 参考解答 一、单项选择题 1．B2．D3．C4．B5．A6．D7．D 8．C9．B 二、填空题 1．T（或 1） 2．(PQ)→R 3．(PQR)(PQR) 4．(x)(F(x)→G(x)) 5．(A(1)A(2))(B(1)B(2)) 6．A(a)∧A(b)∧A（c） 7．A(a)∧A(b))∧(B（a）∨B（b） 8．A(1)A(2) 9．x 10．R(x，y)中的 y 三、公式翻译题 1．解：设 P：今天是天晴； 则P． 2．解：设 P：今天下雨

则-P 3.解：设P今天有人来， 则-P. 4.解：设P他去学校， 则P 5.解：设P他接受了这个任务，他完成好了这个任务， 则P%aQ. 6.解：设P小王去旅游，Q小李去旅游， 则PAQ 7.解：设P他去旅游，Q他有时间， 则P→Q. 8.解：设P:我去书店，Q:天不下雨， 则P→Q. 9.解：设P:所有人今天都去参加活动，Q明天的会议取消， 则P→Q. 10.解：设P你去，他去， 则P→Q. 11.解：设P(x):x是人，Q():x去工作， 则（自x)(P(xA7Q(x) 12.解：设P(x):x是人，Q(x):x去上课， 则（白）(P(xAQ(x)) 13.解：设P(x):x是人，Q(x):x努力工作， 则（付x)(P(x)→Q(x)) 14.解：设P(x):x是人，Q():x去工作， 则（付x)(P(x)→Q(x)) 15.解：设P(x):x是人，Q():x学习努力， 则(Hx)(P(x)→(x)). 四、判断说明题（判断下列各题，并说明理由.） 1.解：正确 因为，由真值表 (Q> (Q→乃A 乃 0 0 0

4 则P． 3．解：设 P：今天有人来， 则P． 4．解：设 P：他去学校， 则P． 5．解：设 P：他接受了这个任务，Q：他完成好了这个任务， 则 PQ． 6．解：设 P：小王去旅游，Q：小李去旅游， 则 PQ． 7．解：设 P：他去旅游，Q：他有时间， 则 P→Q． 8．解：设 P：我去书店，Q：天不下雨， 则 P→Q． 9．解：设 P：所有人今天都去参加活动，Q：明天的会议取消， 则 P→Q． 10．解：设 P：你去，Q：他去， 则 P→Q． 11．解：设 P(x)：x 是人，Q(x)：x 去工作， 则(x)(P(x)┐Q(x))． 12．解：设 P(x)：x 是人，Q(x)：x 去上课， 则(x)(P(x)Q(x))． 13．解：设 P(x)：x 是人，Q(x)：x 努力工作． 则(x)(P(x)→Q(x))． 14．解：设 P(x)：x 是人，Q(x)：x 去工作， 则(x)(P(x)→Q(x))． 15．解：设 P(x)：x 是人，Q(x)：x 学习努力， 则（x）(P(x)→Q(x))． 四、判断说明题（判断下列各题，并说明理由．） 1．解：正确 因为，由真值表 P Q Q →P (Q→ P) (Q→P) P 0 0 1 0 0

0 1 0 0 0 0 0 0 可知，该命题公式为永假式 2.解：正确 P∧(PQ)VP是由PA(PQ)与P组成的析取式， 如果P的值为真，则7PA(PQ)VP为真， 如果P的值为假，则P与PQ为真，即7PΛ(PQ)为真， 也即ㄣP入(PQ)VP为真， 所以P∧(PQ)VP是永真式， 另种说明： 7P∧(PQ)VP是由7P∧(P)与P组成的析取式， 只要其中一项为真，则整个公式为真. 可以看到，不论P的值为真或为假，一PA(P7Q)与P总有一个为真， 所以PA(PQ)VP是永真式 或用等价演算P∧(PQ)VP=T 3.解：错误. (2)应为F(y)→G(x),换名时，约束变元与自由变元不能混淆. 五.计算题 1.解：(1)(P→Q)Λ(P→Q)台(PVQ)A(PV-Q) 台(PΛ-Q)A(-PV-Q)台(PΛQΛ-P)V(PA-QA-Q) 一(PA一Q)(主析取范式) (Pv(-O))((P-P)V-O) 台(PVQ)A(PVQ)A(PVQ)∧(PV-Q) 台(PVQ)A(PV一Q)A(PV一Q)(主合取范式) (2)因为命题公式的成真赋值是(1,0)， 所以它的成假赋值是(0,0)，(0,1)，(1,1). 2.解：(PAQ)→R台(PAQ)VR 台(PVQ)VR 台一PV一QVR(析取、合取、主合取范式) =(PA(QN0∧(Vǜ)V(PVPAON(RVB)V(PV) ∧(V0Λ0 台（ㄣPA7Q∧7BV(PA7QA)V(ㄣPΛQA7BV(PAQA)

5 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 可知，该命题公式为永假式． 2．解：正确． ┐P∧（P→┐Q）∨P 是由┐P∧（P→┐Q）与 P 组成的析取式， 如果 P 的值为真，则┐P∧（P→┐Q）∨P 为真， 如果 P 的值为假，则┐P 与 P→┐Q 为真，即┐P∧（P→┐Q）为真， 也即┐P∧（P→┐Q）∨P 为真， 所以┐P∧（P→┐Q）∨P 是永真式． 另种说明： ┐P∧（P→┐Q）∨P 是由┐P∧（P→┐Q）与 P 组成的析取式， 只要其中一项为真，则整个公式为真． 可以看到，不论 P 的值为真或为假，┐P∧（P→┐Q）与 P 总有一个为真， 所以┐P∧（P→┐Q）∨P 是永真式． 或用等价演算┐P∧（P→┐Q）∨PT 3．解：错误． （2）应为 F（y）→G（x），换名时，约束变元与自由变元不能混淆． 五．计算题 1．解：（1） (P →Q)  (P → Q)  (P  Q)  (P  Q)  (P  Q)  (P  Q)  (P  Q  P) (P  Q  Q)  (P  Q) (主析取范式)  (P  (Q  Q))  ((P  P) Q)  (P  Q)  (P  Q)  (P  Q)  (P  Q)  (P  Q)  (P  Q)  (P  Q) (主合取范式) （2）因为命题公式的成真赋值是(1,0)， 所以它的成假赋值是(0,0)，(0,1)，(1,1)． 2．解： (P  Q) → R  (P  Q)  R  (P  Q)  R  P  Q  R （析取、合取、主合取范式） (┐P∧(┐Q∨Q)∧(┐R∨R))∨((┐P∨P)∧┐Q∧(┐R∨R))∨((┐P∨P) ∧(┐Q∨Q)∧R) (┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)

V(PA7Q∧7V(P∧ュQ∧BV(P∧Q∧)（主析取范式） 3.解：P(VQ) 台nPV(V0 台PVVR(析取、合取、主合取范式) 台(PA ON7 RV(PA7QAAV(PAΛAV PAQN RV(PA OARV(PAON7 R V(PAQ∧0（主析取范式） 4.解：(PVQ)→(PV0V=(PA7④VR(析取范式) 一(PV用∧（ㄣV)(合取范式） 台(PVBV(QA0)∧(VBV(PA)) 台(PVV0∧（ㄣPVV0∧(NVPA ∧(VV) 台(PVQNǜ∧（ㄣPVVǜ∧(PVV0 (主合取范式) 5.解：(PVQ)→(RVQ) 台(PVQ)V(VQ) 台(PA0V(VQ) 台(PVV0∧(VRV) 一(PVV)合取范式 6.解：(1)3x量词的辖域为(P(x,y)→zQy,x,z), Vz量词的辖域为Q(y,x,), y量词的辖域为R(y,z). (2)自由变元为(P(x,y)→Q(y,x,)与Fy)中的，以及R(y,)中的2 约束变元为(P(x,y)→Qy,x,z)》中的x与Qy,x,)中的2，以及R(y,)中的. 六、证明题 1.证明：(P,(wa0)AaPn=(-v(w0)AP%Q 台(RO-RAF%Q 台(PAPA0V(PA)V(RPA⑩ 台(PA0V(-PA0v(-PAǜ 台P%Q(吸收律) 台(Rvㄣ)（摩根律） 2.证明：(1)(3x)(P(x)ΛR(x))P (2)P(a)∧R(a)Es(1) 6

6 ∨(P∧┐Q∧┐R)∨(P∧┐Q∧R)∨(P∧Q∧R)（主析取范式） 3．解：P→（R∨Q） ┐P∨(R∨Q) ┐P∨Q∨R（析取、合取、主合取范式） (┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨ (┐P∧Q∧┐R)∨(P∧┐Q∧R)∨(P∧Q∧┐R) ∨(P∧Q∧R)（主析取范式） 4．解：（P∨Q）→R┐(P∨Q)∨R(┐P∧┐Q)∨R（析取范式） (┐P∨R)∧(┐Q∨R)（合取范式） ((┐P∨R)∨(Q∧┐Q))∧((┐Q∨R)∨(P∧┐P)) (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧(┐Q∨R∨P) ∧(┐Q∨R∨┐P) (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧(P∨┐Q∨R) （主合取范式） 5．解：（P∨Q）→（R∨Q） （P∨Q）∨（R∨Q） (P∧Q)∨（R∨Q） (P∨R∨Q)∧(Q∨R∨Q) (P∨R∨Q)合取范式 6．解：（1）x 量词的辖域为 (P(x, y) → zQ( y, x,z)) ， z 量词的辖域为 Q( y, x,z) , y 量词的辖域为 R( y,z) ． （2）自由变元为 (P(x, y) → zQ( y, x,z)) 与 F( y) 中的 y，以及 R( y,z) 中的 z 约束变元为 (P(x, y) → zQ( y, x,z)) 中的 x 与 Q( y, x,z) 中的 z，以及 R( y,z) 中的 y． 六、证明题 1．证明：(P→(QR))PQ(P(QR))PQ (PQR)PQ (PPQ)(QPQ)(RPQ) (PQ)(PQ)(PQR) PQ（吸收律） (PQ)（摩根律） 2．证明：（1）（x）（P（x）∧R（x））P （2）P（a）∧R（a）ES(1)

(3)P(a)(2)I (4)(3x)P(x)EG(3) (5)R(a)T(2)I (6)(3x)R(x)EG(5) (7)(3x)P(x)Λ(3x)R(x)T(5)(6)I >

7 （3）P（a）T(2)I （4）（x）P（x）EG(3) （5）R（a）T(2)I （6）（x）R（x）EG(5) （7）（x）P（x）∧（x）R（x）T(5)(6)I