第二章 谓词逻辑习题与解答⒈ 将下列命题符号化：⑴ 所有的火车都比某些汽车快。

⑵ 任何金属都可以溶解在某种液体中。

⑶ 至少有一种金属可以溶解在所有液体中。

⑷ 每个人都有自己喜欢的职业。

⑸ 有些职业是所有的人都喜欢的。

解 ⑴ 取论域为所有交通工具的集合。

令x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。

“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧∃→∀。

⑵ 取论域为所有物质的集合。

令x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。

“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧∃→∀。

⑶ 论域与谓词与(2)同。

“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →∀∧∃。

⑷ 取论域为所有事物的集合。

令x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。

“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧∃→∀⑸论域与谓词与(4)同。

“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →∀∧∃。

⒉ 取论域为正整数集，用函数+（加法），∙（乘法）和谓词<，=将下列命题符号化：⑴ 没有既是奇数，又是偶数的正整数。

⑵ 任何两个正整数都有最小公倍数。

⑶ 没有最大的素数。

⑷ 并非所有的素数都不是偶数。

解 先引进一些谓词如下：x y x D :),(能被y 整除，),(y x D 可表示为)(y x v v =∙∃。

x x J :)(是奇数，)(x J 可表示为)2(x v v =∙⌝∃。

x x E :)(是偶数，)(x E 可表示为)2(x v v =∙∃。

x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=↔=∙∃∀∧=⌝。

⑴ “没有既是奇数，又是偶数的正整数”可表示为))()((x E x J x ∧⌝∃，并可进一步符号化为))2()2((x v v x v v x =∙∃∧=∙⌝∃⌝∃。

⑵ “任何两个正整数都有最小公倍数”可表示为))),(),((),(),((u z u z y u D x u D u y z D x z D z y x =∨<→∧∀∧∧∃∀∀，并可进一步符号化为)))()(()()((u z u z u y v v u x v v u z y v v z x v v z y x =∨<→=∙∃∧=∙∃∀∧=∙∃∧=∙∃∃∀∀⑶ “没有最大的素数”可表示为)))(()((x y x y y P y x P x =∨<→∀∧⌝∃，并可进一步符号化为)1)(()1(()1)(()1((y y u u y u v v u y y x u u x u v v u x x <→=∨=↔=∙∃∀∧=⌝∀∧=∨=↔=∙∃∀∧=⌝⌝∃⑷ “并非所有的素数都不是偶数”可表示为))()((x E x P x ⌝→⌝∀，并可进一步符号化为))2()(()1((x v v x u v v u x x =∙⌝∃→=∙∃∀∧=⌝⌝∀⒊ 取论域为实数集合，用函数+，－（减法）和谓词<，=将下列命题符号化：⑴ 没有最大的实数。

⑵ 任何两不同的实数之间必有另一实数。

⑶ 函数)(x f 在点a 处连续。

⑷ 函数)(x f 恰有一个根。

⑸ 函数)(x f 是严格单调递增函数。

解 ⑴ “没有最大的实数”符号化为)(x y x y y x =∨<∀⌝∃。

⑵ “任何两不同的实数之间必有另一实数”符号化为))((y z z x z y x y x <∧<∃→<∀∀。

⑶“函数)(x f 在点a 处连续”的定义是：任给0>ε，总可以找到0>δ，使得只要δ<-||a x 就有ε<-|)()(|a f x f 。

“函数)(x f 在点a 处连续”符号化为))))()()()((0(0(εεδδδδεε+<∧<-→+<∧<-∀∧<∃→<∀a f x f x f a f a x x a x⑷ “函数)(x f 恰有一个根”符号化为))0)((0)((x y y f y x f x =→=∀∧=∃。

⑸ “函数)(x f 是严格单调递增函数”符号化为))()((y f x f y x y x <→<∀∀。

⒋ 指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。

(1) )),(),((a x P x y P x →∀(2) ),()(y x zQ x xP ∀→∀(3) )()())()((x Q x xP x R x P x ∧∀→∧∀(4) ))),(,()),,(((y x g z xP x y x f P y ∀→∀(5) )())()()((x R x xR x Q x P x ∧∃∧→∀5. 归纳证明：若t ，t '是项，则x t t '也是项。

证明 ① 若t 是x ，则x t t '是t '，x t t '是项。

② 若t 是不同于x 的变元y ，则x t t '仍是y ，x t t '是项。

③若t 是常元a ，则x t t '仍是a ，x t t '是项。

④若t 是),,(1n t t f ，则x t t '是))(,,)((1x t n x t t t f '' ，由归纳假设知x t n x t t t '')(,,)(1 都是项，所以x t t '是项。

6. 归纳证明：若t 是项，A 是公式，则x t A 也是公式。

证明 ①若A 是),,(1n t t P ，则x t A 是))(,,)((1x t n x t t t P ，由上题知x t n x t t t )(,,)(1 都是项，所以x t A 是公式。

②若A 是B ⌝，则x t A 是x t B ⌝，由归纳假设知x t B 是公式，所以x t A 是公式。

③若A 是C B →，则x t A 是x t x t C B →，由归纳假设知x t B 和x t C 都是公式，所以x t A 是公式。

④若A 是xB ∀，则x t A 仍是A ，x t A 是公式。

⑤若A 是yB ∀，其中y 是不同于x 的变元，则x t A 是x t yB ∀，由归纳假设知x t B 是公式，所以x t A 是公式。

7. 给定解释I 和I 中赋值v 如下：}2,1{=I D ，1=I a ，2=I b ，2)1(=I f ，1)2(=I f1)2,1()1,1(==I I P P ，0)2,2()1,2(==I I P P ，1)(=x v ，1)(=y v计算下列公式在解释I ，赋值v 下的真值。

(1) )),(())(,())(,(x y f P b f x P x f a P ∧∧(2) ),(x y yP x ∃∀(3) )))(),((),((y f x f P y x P y x →∀∀解 (1))))(),(())(,())(,((v x y f P b f x P x f a P I ∧∧))()),((())(),(()))((,(x v y v f P b f x v P x v f a P I I I I I I I I ∧∧=)1),1(())2(,1())1(,1(I I I I I I f P f P f P ∧∧=0011)1,2()1,1()2,1(=∧∧=∧∧=I I I P P P (2))))(,((v x y yP x I ∃∀])2/[))(,((])1/[))(,((x v x y yP I x v x y yP I ∃∧∃=]))2/][1/[))(,((])1/][1/[))(,(((y x v x y P I y x v x y P I ∨=]))2/][2/[))(,((])1/][2/[))(,(((y x v x y P I y x v x y P I ∨∧))2,2()2,1(())1,2()1,1((I I I I P P P P ∨∧∨= 1)01()01(=∨∧∨=(3) )))))((),((),(((v y f x f P y x P y x I →∀∀)))2(,)1(()2,1(()))1(,)1(()1,1((I I I I I I I I f f P P f f P P →∧→=)))2(,)2(()2,2(()))1(,)2(()1,2((I I I I I I I I f f P P f f P P →∧→∧))1,1()2,2(())2,1()1,2(())1,2()2,1(())2,2()1,1((I I I I I I I I P P P P P P P P →∧→∧→∧→=01100)10()10()01()01(=∧∧∧=→∧→∧→∧→=7. 给定解释I 如下：},{b a D I =， 1),(),(==b b P a a P I I ， 0),(),(==a b P b a P I I判断I 是不是以下语句的模型。

(1) ),(y x yP x ∃∀(2) ),(y x yP x ∀∀(3) ),(y x yP x ∀∃(4) ),(y x P y x ⌝∃∃(5) )),(),((x y P y x P y x →∀∀(6)),(x x xP ∀解 (1) )),((y x yP x I ∃∀1)10()01()),(),(()),(),((=∨∧∨=∨∧∨=b b P a b P b a P a a P I I I I(2) )),((y x yP x I ∀∀01001),(),(),(),(=∧∧∧=∧∧∧=b b P a b P b a P a a P I I I I(3) )),((y x yP x I ∀∃0)10()01()),(),(()),(),((=∧∨∧=∧∨∧=b b P a b P b a P a a P I I I I(4) )),((y x P y x I ⌝∃∃10110),(),(),(),(=∨∨∨=⌝∨⌝∨⌝∨⌝=b b P a b P b a P a a P I I I I(5) ))),(),(((x y P y x P y x I →∀∀)),(),(()),(),((a b P b a P a a P a a P I I I I →∧→=)),(),(()),(),((b b P b b P b a P a b P I I I I →∧→∧1)11()00()00()11(=→∧→∧→∧→=(6) 111),(),()),((=∧=∧=∀b b P a a P x x xP I I I9.写出一个语句A ，使得A 有模型，并且A 的每个模型的论域至少有三个元素。