离散数学 章节练习 2 KEY

离散数学章节练习 2范围：谓词逻辑班级：________________ 学号：________________ 姓名： ________________一、单项选择题1. 下列那个公式是永真式：( )A (p∧r)∨(p∧s) ； B. (p∧⌝p)→qC ⌝∃xB(x)⇔∃x⌝B(x) D. (p∨⌝p)→q2. 下列公式中正确的等价式是( )A. ⌝∃xA(x)⇔∃x⌝A(x)B. ⌝∀xA(x)⇔∃x⌝A(x)C. ∀x∀yA(x,y)⇔∃y∀xA(x,y)D.∀x(A(x)∨B(x))⇔∀xA(x)∨∀xB(x)3. “人总是要死的”谓词公式表示为 ( )（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。

A、M(x) →Mortal(x)B、M(x) ∧Mortal(x)C、∀x (M(x) →Mortal(x))D、∃x (M(x) →Mortal(x))4.谓词公式∀x(P(x)∨(∃y)R(y))→Q(x)中的x ( )A.只是约束变元。

B. 既是约束变元又是自由变元。

C.既非约束变元又非自由变元。

D. 只是自由变元。

5.当个体域 D={a, b}时，下列与∀xP(x)等值的式子是 ( )A.P(a)∨P(b)B. p(a)∧P(b)C.P(a)→P(b)D. ⌝P(a)→P(b)6. 设个体域是正整数集，则下列公式中真值为真的公式是( )A. (∀x)(∃y)(x·y=0)B. (∀x)(∃y)(x·y=1)C. (∃ x)(∃y)(x·y=2)D. (∀x)(∀y)(∃z)(x-y=z)7.下列公式中正确的等价式是 ( )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)8.命题逻辑中一组公式H 1，H 2， ···,H n .，C ，存在关系H 1∧H 2∧···∧H n ⇒C 当且仅当H 1∧H 2∧···∧H n →C 是 ( )A. 矛盾式。

B. 永假式。

C. 可满足式。

D. 永真式。

9.下列公式中正确的等价式是 ( )A. ⌝∃xA(x)⇔∃x ⌝A(x)B. ⌝∀xA(x)⇔∃x ⌝A(x)C. ∀x ∀yA(x,y)⇔∃y ∀xA(x,y)D.∀x(A(x)∨B(x))⇔∀xA(x)∨∀xB(x)10. 命题公式((p →q) →(⌝q →⌝p)) ∨r 的类型是 ( )A. 永真式。

B.永假式。

C. 非永真式可满足式。

D. 重言式11.下列公式中那个为永真式 ( )A ．∀x(F(x) →G(x))B. ∃x(F(x)∧G(x))C ．∀xF(x) → ∃xF(x)D. ∀x ∀y(F(x)∧G(y)→H(x,y))12. “所有的狗都是会飞”谓词公式表示为 ( )（论域为全总个体域）M(x)：x 是狗；Mortal(x)：x 是会飞的。

A 、)()(x Mortal x M →；B 、)()(x Mortal x M ∧C 、))()((x Mortal x M x →∀；D 、))()((x Mortal x M x ∧∃13. 公式))()((x Q x P x A →∃=的解释I 为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A 的真值为 ( )A 、1；B 、0；C 、可满足式；D 、无法判定。

14.下列公式中正确的等价式是 ( )A. ⌝∃xA(x)⇔∃x ⌝A(x)B. ⌝∀xA(x)⇔∃x⌝A(x)C. ∀x∀yA(x,y)⇔∃y∀xA(x,y)D.∀x(A(x)∨B(x))⇔∀xA(x)∨∀xB(x)15. 谓词公式∀xP(x,y)∃→yQ(x,y)的前束范式是 ( )A、∀xP(x,y)∃→yQ(x,y) ；B、⌝∀rP(r,y)∃∨sQ(x,s)；C、∃r∃s(⌝P(r,y)∨Q(x,s))D 、∃⇔r∃s⌝P(r,y)∨Q(x,s)16.下列公式中正确的等价式是 ( )A. ⌝∃xA(x)⇔∃x⌝A(x)B. ⌝∀xA(x)⇔∃x⌝A(x)C. ∀x∀yA(x,y)⇔∃y∀xA(x,y)D.∀x(A(x)∨B(x))⇔∀xA(x)∨∀xB(x)17.下列公式中，不是p→(q→p)的代换实例的是 ( )A. F(x,y)→(G(x,y)→F(x,y))B. F(x,y)→G(x,y)→F(x,y)C. F(y,x)→(G(x,y)→F(x,y))D. F(x,y)→(G(x,y)→F(y,x))18. 下列公式中等价的是（）A、∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)B、∀x(A(x)∧B(x))⇔∀xA(x) ∨∀xB(x)C、∀x(A(x) ∨B(x))⇔∀xA(x)∧∀xB(x)D、∀x(A(x)∧B(x))⇔∀x⌝A(x)∧∀x⌝B(x)19. 对公式∀x(F(x)→G(y)) →∃y(H(x)∧L(x,y,z))的变元分析正确的是( )A. x是约束变元B. y是约束变元。

C. z是约束变元。

D. x既是约束变元，又是自由变元。

20. 对公式∀x∀y(P(x,y)∧Q(y,z)) ∧∃xP(x,y)中量词的作用域分析不正确的是（）A ∀x的作用域是P(x,y)B ∀y的作用域是P(x,y)∧Q(y,z)C ∃x 的作用域是P(x,y)D ∀x 的作用域是P(x,y)∧Q(y,z)二、判断题1、∃x ∀y(P(x,y)∧Q(a,y))∃→x ∀y(P(x,y)∧Q(x,y))（其中a 是个体常元）是永真式。

( )2、谓词逻辑中，量词（quantifiers ）是表示个体常项或个体变项之间数量关系的词。

( )3、谓词W(x),M(z)中只有1个个体变元，则称为1元谓词公式。

( )4、F(y)∧⌝G(x,y)是合法的公式 ( )5、∀s(P(s)∃∧rQ(r,z)∃→tR(s,t))不是闭公式 ( )6、一个谓词公式，如果量词均在全式的开头，则该公式称为前束范式( )7、量词指导变元是指∀xA 和∃xA 中的x ( )8、全称量词∀x 是指个体域中所有对象具有某性质或具有某相互关系( )三、填空题1．公式∀xP(x)→∃x Q(x)的前束范式是， 。

2．∀x(P(x)∨(∃y)R(y))→Q(x)中∀x 的辖域是 。

3. 谓词公式(∀x)(∃y)(P(x,y)∨R(y))→Q(y)，则其自由变元是________。

4．∀xP(x) →∀yQ(y)) 的前束范式为 。

5.命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数，y x y x L >:),(则命题的逻辑谓词公式为6.谓词合式公式)()(x xQ x xP ∃→∀的前束范式为 。

7.将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。

8.设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A(x)关于y 是自由的，则 被称为存在量词消去规则，记为ES 。

9．公式∀xP(x)→∃x Q(x)的前束范式是， 。

10．表示个体词的性质或个体词之间关系的词称为。

11．公式∃xP(x)→∀x Q(x)的前束范式是，12．一个析取范式中，如果所有简单合取式均为极小项，则称为。

13．设A、B是两个合法的谓词公式,如果在任何解释下两个公式的真值都相等，则称A与B 。

四、计算题1．将∀xP(x,y)→∃yQ(x,y)转换为前束范式解：∀xP(x,y)→∃yQ(x,y)⇔∀rP(r,y)→∃sQ(x,s) 约束变元改名 2分⇔⌝∀rP(r,y)∨∃sQ(x,s) 转换条件式2分⇔∃r⌝P(r,y)∨∃sQ(x,s) 德摩律2分⇔∃r∃s(⌝P(r,y)∨Q(x,s)) 量词辖域的扩张2分2. 求谓词公式∀x(P(x)∨(∃y)R(y))→Q(x)的前束范式。

∀x(P(x)∨∃yR(y))→Q(x)= ∀z(P(z)∨(∃y)R(y))→ Q(x) 1分= ∀z∃y(P(z)∨ R(y))→Q(x) 1分=⌝∀z∃y(P(z)∨ R(y))∨Q(x) 1分=∃z∀y⌝(P(z)∨ R(y))∨Q(x) 1分=∃z∀y(⌝P(z) ∧⌝R(y))∨Q(x) 1分=∃z∀y(⌝P(z) ∧⌝R(y)∨ Q(x)) 3分3. 求谓词公式∀x(P(x)∨(∃y)Q(y))→R(x)的前束范式。

解∀x(P(x)∨∃yQ(y))→R(x)= ∀z(P(z)∨(∃y)Q(y))→ R(x) 1分= ∀z∃y(P(z)∨ Q(y))→R(x) 1分=⌝∀z∃y(P(z)∨ Q(y))∨R(x) 1分=∃z∀y⌝(P(z)∨ Q(y))∨R(x) 1分=∃z∀y(⌝P(z) ∧⌝Q(y))∨R(x) 1分=∃z∀y(⌝P(z) ∧⌝Q(y)∨ R(x)) 3分4．将命题 “并不是所有的汽车都比火车快”符号化。

设 F(x):x 是汽车,G(y):y 是火车,H(x,y):x 比y 快，命题符号化为⌝∀x ∀y(F(x)∧G(y)→H(x,y))或∃x ∃y(F(x)∧G(y)∧⌝H(x,y))5．给定解释Ｉ如下, 试求下公式),(y x yF x ∃∀在Ｉ下的真值. (a)个体域D={3,4}; (b))(x f 为3)4(,4)3(==f f(c)1)3,4()4,3(,0)4,4()3,3(),(====F F F F y x F 为.解: ))4,()3,((),(x F x F x y x yF x ∨∀⇔∃∀⇔))4,4()3,4(())4,3()3,3((F F F F ∨∧∨⇔1)01()10(⇔∨∧∨6．在一阶逻辑将下列命题符号化:(1) 火车都比轮船快.(2) 不存在比所有火车都快的汽车.解:(1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快命题符号化为: )),())()(((y x H y G x F y x →∧∀∀(2) (1)F(x): x 是火车; G(x): x 是汽车; H(x,y): x 比y 快命题符号化为: ))),()(()((y x H x F x y G y →∀∧⌝∃7．在一阶逻辑中将下列命题符号化:(1) 没有不能表示成分数的有理数.(2) 在北京卖菜的人不全是外地人.解:(1)F(x): x 能表示成分数H(x): x 是有理数命题符号化为: ))()((x H x F x ∧⌝⌝∃(2)F(x): x 是北京卖菜的人H(x): x 是外地人命题符号化为: ))()((x H x F x →⌝∀8．判断yF(x,y)的类型:解:取解释I 个体域为全体实数F(x,y)：x+y=5所以,前件为任意实数x 存在实数y 使x+y=5，前件真；后件为存在实数x 对任意实数y 都有x+y=5，后件假，]此时为假命题再取解释I 个体域为自然数N ，F(x,y)：:x+y=5所以,前件为任意自然数x 存在自然数y 使x+y=5，前件假。