离散数学答案第二章习题解答

第二章 谓词逻辑

习题与解答

1. 将下列命题符号化：

(1) 所有的火车都比某些汽车快。

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

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

(4) 每个人都有自己喜欢的职业。

(5) 有些职业是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。令

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

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

(2) 取论域为所有物质的集合。令

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

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

(3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。

(4) 取论域为所有事物的集合。令

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

“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→?

(5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。

2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化：

(1) 没有既是奇数，又是偶数的正整数。

(2) 任何两个正整数都有最小公倍数。

(3) 没有最大的素数。

(4) 并非所有的素数都不是偶数。

解 先引进一些谓词如下：

x y x D :),(能被y 整除，),(y x D 可表示为)(x y 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 =∨=?=???∧=?。

(1) “没有既是奇数，又是偶数的正整数”可表示为))()((x E x J x ∧??，

并可进一步符号化为))2()2((x v v x v v x =??∧=?????。

(2) “任何两个正整数都有最小公倍数”可表示为

))),(),((),(),((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 =∨<→=??∧=???∧=??∧=?????(3) “没有最大的素数”可表示为)))(()((x y x y y P y x P x =∨<→?∧??， 并可进一步符号化为

))

)1)(()1(()1)(()1((x y x y y u u y u v v u y y x u u x u v v u x x =∨<→=∨=?=???∧=??∧=∨=?=???∧=??? (4) “并非所有的素数都不是偶数”可表示为))()((x E x P x ?→??，并可进一步符号化

为))2()1)(()1((x v v x u u x u v v u x x =???→=∨=?=???∧=???

3. 取论域为实数集合，用函数+，－（减法）和谓词<，=将下列命题符号化：

(1) 没有最大的实数。

(2) 任何两个不同的实数之间必有另一实数。

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

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

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

解 (1) “没有最大的实数”符号化为)(x y x y y x =∨

(2) “任何两个不同的实数之间必有另一实数”符号化为))((y z z x z y x y x <∧

(3) “函数)(x f 在点a 处连续”的定义是：

任给0>ε，总可以找到0>δ，使得只要δ<-||a x 就有ε<-|)()(|a f x f 。 “函数)(x f 在点a 处连续”符号化为

))))()()()((0(0(εεδδδδεε+<∧<-→+<∧<-?∧

(4) “函数)(x f 恰有一个根”符号化为))0)((0)((x y y f y x f x =→=?∧=?。

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

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

(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 ∧?∧→?

解 (1) 变元 x 在)),(),((a x P x y P x →?中三次出现都是约束出现，?x 的唯一出现的辖域是 P (y , x ) → P (x , a )。

(2) 变元 x 在),()(y x zQ x xP ?→?中的头两次出现是约束出现，第三次出现是自由出现。变元 y 在),()(y x zQ x xP ?→?中的唯一出现是自由出现。变元 z 在),()(y x zQ x xP ?→?中的唯一出现是约束出现。?x 的唯一出现的辖域是 P (x )，?z 的唯一出现的辖域是Q (x , y )。

(3) 变元 x 在)()())()((x Q x xP x R x P x ∧?→∧?中的头五次出现是约束出现，第六次出现是自由出现。?x 的第一次出现的辖域是P (x ) ∧ R (x )，第二次出现的辖域是P (x )。

(4) 变元 x 在))),(,()),,(((y x g z xP x y x f P y ?→?中的头两次出现是自由出现，后两次出现是约束出现。?x 的唯一出现的辖域是 P (z , g (x , y ))， ?y 的唯一出现的辖域是 P (f (x , y ), x ) → ?xP (z , g (x , y ))。

(5) 变元 x 在)())()()((x R x xR x Q x P x ∧?∧→?中的头五次出现是约束出现，第六次出现是自由出现。?x 的唯一出现的辖域是P (x ) → Q (x ) ∧ ?xR (x )，?x 的唯一出现的辖域是R (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 f

1)2,1()1,1(==I I P P ，0)2,2()1,2(==I I P P ，1)(=x v ，1)(=y v

计算下列公式在解释I 和赋值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 I

9. 写出一个语句A ，使得A 有模型，并且A 的每个模型的论域至少有三个元素。 解 语句A 为),(),(),(),(a c P c b P b a P x x P x ∧∧∧??。给定解释I '如下。

I D '为自然数集合， 1),(='y x P I 当且仅当y x ≠， 1='I a ，2='I b ，3='I c 则I '是A 的模型，A 有模型。

任取满足语句A 的解释I ，则1),(),(),(===I I I I I I I I I a c P c b P b a P ，又因为1)),((=??x x P x I ，所以I a ，I b ，I c 是论域I D 中三个不同元素，论域I D 中至少有三个元素。

10. 写出一个语句A ，使得A 有模型，并且A 的每个模型的论域有无穷多个元素。

解 语句A 为),()),(),(),((),(y x yP x z x P z y P y x P y x x x P x ??∧→∧??∧??。给定解释I '如下。

I D '为自然数集合， 1),(='y x P I 当且仅当y x <

则I '是A 的模型，A 有模型。

任取满足语句A 的解释I ，取I D d ∈1，因为1)),((=??y x yP x I ，所以有I D d ∈2使得1),(21=d d P I ，又因为1)),((=??x x P x I ，故21d d ≠。因为1)),((=??y x yP x I ，所以有I D d ∈3使得1),(32=d d P I ，又因为1)),((=??x x P x I ，故23d d ≠。因为1))),(),(),(((=→∧??z x P z y P y x P y x I ，所以1),(31=d d P I ，故13d d ≠。因此，

1d ，2d ，3d 是论域中的三个不同元素。这个过程可以不断进行下去，得到 ,,,321d d d 因此，论域 D I 中必然有无穷多个元素。

11. 判断以下公式是不是永真式、永假式、可满足式，并说明理由。

(1) ))()(()()(x Q x P x x xQ x xP ∨?→?∨?

(2) ))()(()()(x Q x P x x xQ x xP ∧?→?∧?

(3) )()())()((x xQ x xP x Q x P x ?∨?→∨?

(4) ),(),(y x yP x x x xP ??→?

(5) ))()(())()((x Q x P x x xQ x xP →?→?→?

(6) ))()(())()((x Q x P x x xQ x xP →?→?→?

(7) ))()(())()((x xQ x xP x Q x P x ?→?→→?

解 (1) ))()(()()(x Q x P x x xQ x xP ∨?→?∨?是永真式。若解释I 使得1))()((=?∨?x xQ x xP I ，则1))((=?x xP I 或1))((=?x xQ I 。

① 若1))((=?x xP I ，则存在I D d ∈使得1)(=d P I ，1)()(=∨d Q d P I I 。 ② 若1))((=?x xQ I ，则存在I D d ∈使得1)(=d Q I ，1)()(=∨d Q d P I I 。 因此，1)))()(((=∨?x Q x P x I 。

(2) ))()(()()(x Q x P x x xQ x xP ∧?→?∧?是非永真的可满足式。给定解释I 如下。

}{d D I =， 1)(=d P I ， 1)(=d Q I

则1)))()(()()((=∧?→?∧?x Q x P x x xQ x xP I 。

给定解释I '如下。

},{b a D I ='，1)(='a P I ，0)(='b P I ，0)(='a Q I ，1)(='b Q I

则0)))()(()()((=∧?→?∧?'x Q x P x x xQ x xP I 。

(3) )()())()((x xQ x xP x Q x P x ?∨?→∨?是非永真的可满足式。给定解释I 如下。

}{d D I =， 1)(=d P I ， 1)(=d Q I

则1))()())()(((=?∨?→∨?x xQ x xP x Q x P x I 。

给定解释I '如下。

},{b a D I ='，1)(='a P I ，0)(='b P I ，0)(='a Q I ，1)(='b Q I

则0))()())()(((=?∨?→∨?'x xQ x xP x Q x P x I 。

(4) ),(),(y x yP x x x xP ??→?是非永真的可满足式。给定解释I 如下。

}{d D I =， 1),(=d d P I

则1)),(),((=??→?y x yP x x x xP I 。

给定解释I '如下。

},{b a D I ='，1),(),(==''b b P a a P I I ，0),(),(==''a b P b a P I I

则0)),(),((=??→?'y x yP x x x xP I 。

(5) ))()(())()((x Q x P x x xQ x xP →?→?→?是非永真的可满足式。给定解释I 如下。

}{d D I =， 1)(=d P I ， 1)(=d Q I

则1)))()(())()(((=→?→?→?x Q x P x x xQ x xP I 。

给定解释I '如下。

},{b a D I ='，1)(='a P I ，0)(='b P I ，0)(='a Q I ，1)(='b Q I

则0)))()(())()(((=→?→?→?'x Q x P x x xQ x xP I 。

(6) ))()(())()((x Q x P x x xQ x xP →?→?→?是永真式。若解释I 使得0)))()(((=→?x Q x P x I ，则存在I D d ∈使得0)()(=→d Q d P I I ，因此1)(=d P I 且0)(=d Q I ，1))((=?x xP I 且0))((=?x xQ I ，0)))()(((=?→?x xQ x xP I 。

(7) ))()(())()((x xQ x xP x Q x P x ?→?→→?是永真式。若解释I 使得0)))()(((=?→?x xQ x xP I ，则1))((=?x xP I 且0))((=?x xQ I 。存在I D d ∈使得1)(=d P I ，又因为0))((=?x xQ I ，所以0)(=d Q I ，0)()(=→d Q d P I I 。因此，0)))()(((=→?x Q x P x I 。

12.设A ,B 是任意公式，证明以下公式是永真式。

(1) xA A x t ?→,其中项t 对于A 中的x 是可代入的。

(2) A x xA ?????

(3) A x xA ?????

(4) xB xA B A x ?∧?→∧?)(

(5) )(B A x xB xA ∨?→?∨?

(6) )()(xB A B A x ?→→→?，其中x 不是A 的自由变元。

解 (1) 任取解释I 和I 中赋值v ，若1))((=v A I x t ,则1))])((/[)(())((==v t I x v A I v A I x t ，所以1))((=?v xA I 。这表明xA A x t ?→是永真式。

(2) 任取解释I 和I 中赋值v ，

1))((=??v xA I

当且仅当 0))((=?v xA I

当且仅当 存在I D d ∈使得0])/[)((=d x v A I

当且仅当 存在I D d ∈使得1])/[)((=?d x v A I 当且仅当 1))((=??v A x I

这表明A x xA ?????是永真式。

(3) 任取解释I 和I 中赋值v ，

0))((=??v xA I

当且仅当 1))((=?v xA I

当且仅当 存在I D d ∈使得1])/[)((=d x v A I

当且仅当 存在I D d ∈使得0])/[)((=?d x v A I 当且仅当 0))((=??v A x I

这表明A x xA ?????是永真式。

(4) 任取解释I 和I 中赋值v ，若1)))(((=∧?v B A x I ，则存在I D d ∈使得

1)]/[)((=∧d x v B A I ，1)]/[)(()]/[)((==d x v B I d x v A I ，1))((=?v xA I 且1))((=?v xB I ，1))((=?∧?v xB xA I 。这表明xB xA B A x ?∧?→∧?)(是永真式。

(5) 任取解释I 和I 中赋值v ，若0)))(((=∨?v B A x I ，则存在I D d ∈使得0)]/[)((=∨d x v B A I ，0)]/[)(()]/[)((==d x v B I d x v A I ，0))((=?∨?v xB xA I 。这表明)(B A x xB xA ∨?→?∨?是永真式。

(6) 任取解释I 和I 中赋值v ，若1))(()))(((==→?v A I v B A x I ，则对于每个I D d ∈，1)]/[)((=→d x v B A I ，因为x 不是A 的自由变元，所以1))(()]/[)((==v A I d x v A I ，因此1)]/[)((=d x v B I ，1))((=?v xB I 。这表明)()(xB A B A x ?→→→?是永真式。

13.设1A 是公式A 的闭包，2A 是A x x n ?? 1，其中},,{)(V ar 1n x x A =。证明：

(1) A 是永真式当且仅当1A 是永真式；

(2) A 是可满足式当且仅当2A 是可满足式。

证明 (1) （?）首先证明：若A 是永真式，则xA ?是永真式。设A 是永真式。任取解释I 和I 中赋值v ，任取I D d ∈，因为]/[d x v 也是I 中赋值，所以1)]/[)((=d x v A I ，1))((=?v xA I 。xA ?是永真式。若A 是永真式，则A x n ?是永真式，… ，A x x n ?? 1是永真式。

（?）因为A A x x n →?? 1是永真式，所以若A x x n ?? 1是永真式，则A 是永真式。

(2) （?）因为A x x A n ??→ 1是永真式，所以若解释I 和I 中赋值v 满足A ，则I 和v 满足A x x n ?? 1。

（?）若解释I 和I 中赋值v 满足A x x n ?? 1，则有I n D d d ∈,,1 使得1])/,,/[)((11=n n d x d x v A I ，I 和I 中赋值]/,,/[11n n d x d x v 满足A 。

14.判断以下等值式是否成立，并说明理由。

(1) )()())()((x xQ x xP x Q x P x ??????

(2) )()())()((x xQ x xP x Q x P x ?→??→?

(3) )()(x P x xP ??

(4) )()(x xP x xP x ????

(5) )()())()((y yQ x xP y yQ x P x ???????

(6) )()())()((y yQ x xP y yQ x P x ???????

解 (1) 不成立。取解释I 如下。

},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I

则0)))()(((=??x Q x P x I 且1))()((=???x xQ x xP I 。

(2) 不成立。取解释I 如下。

},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I

则0)))()(((=→?x Q x P x I 且1))()((=?→?x xQ x xP I 。

(3) 不成立。取解释I 和I 中赋值v 下。

},{b a D I =， 0)(=a P I ， 1)(=b P I ， b x v =)(

则0)))(((=?v x xP I 且1)))(((=v x P I 。

(4) 成立。任取解释I 和I 中赋值v ，因为x 不是)(x xP ?中的自由变元，所以对于每个I D d ∈，)))(((])/[))(((v x xP I d x v x xP I ?=?。

1)))(((=??v x xP x I

当且仅当对于每个I D d ∈，1])/[))(((=?d x v x xP I 当且仅当1)))(((=?v x xP I

(5) 不成立。取解释I 如下。

},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I

则0)))()(((=???y yQ x P x I 且1))()((=???y yQ x xP I 。

(6) 不成立。取解释I 如下。

},{b a D I =， 1)(=a P I ， 0)(=b P I ， 1)()(==b Q a Q I I

则0)))()(((=???y yQ x P x I 且1))()((=???y yQ x xP I 。

15.设A ,B 是任意公式，证明以下等值式。

(1) x y A y A x ???，其中y 在A 中不出现。

(2) B x A x B A x ?→??→?)(

(3) B y A x B A y x ?∨??∨??)(，其中x 不是B 的自由变元，y 不是A 的自由变元。

(4) B y A x B A y x ?∧??∧??)(，其中x 不是B 的自由变元，y 不是A 的自由变元。

(5) B y A x B A y x ?→??→??)(，其中x 不是B 的自由变元，y 不是A 的自由变元。

(6) A x y A y x ?????

证明 (1) x y x y A y A y A x A x ???????????

(2) B x A x B x A x B x A x B A x B A x ?→???∨????∨???∨???→?)()(

(3) B y A x B y A x B A y x ?∨???∨??∨??)()(

(4) B y A x yB A x B A y x ?∧???∧??∧??)()(

(5) B y A x yB A x B A y x ?→???→??→??)()(

(6) 任取解释I 和I 中赋值v ，

0))((=??v yA x I

当且仅当有I D d ∈使得0])/[)((=?d x v yA I

当且仅当有I D c d ∈,使得0])/][/[)((=c y d x v A I

当且仅当有I D c d ∈,使得0])/][/[)((=d x c y v A I

当且仅当有I D c ∈使得0])/[)((=?c y v xA I 当且仅当0))((=??v xA y I

16.判断以下逻辑推论关系是否成立，并说明理由。

(1) )()(|))()((x xQ x xP x Q x P x ?∨?=∨?

(2) ))()((|)()(x Q x P x x xQ x xP ∧?=?∧?

(3) ))()((|))()((x Q x P x x xQ x P x ??=???

(4) ))()((|))()((x Q x P x x xQ x P x →?=?→?

(5) )(|)(,))()((x xQ x xP x Q x P x ?=?→?

(6) ),(|),(x x xP y x yP x ?=??

解 (1) 不成立。取解释I 如下。

},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I

则1)))()(((=∨?x Q x P x I 且0))()((=?∨?x xQ x xP I 。这表明)()(/|))()((x xQ x xP x Q x P x ?∨?=∨?。

(2) 不成立。取解释I 如下。

},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I

则1))()((=?∧?x xQ x xP I 且0)))()(((=∧?x Q x P x I 。这表明))()((/|)()(x Q x P x x xQ x xP ∧?=?∧?。

(3) 不成立。取解释I 如下。

},{b a D I =， 0)()(==b P a P I I ， 1)(=a Q I ， 0)(=b Q I

则1)))()(((=???x xQ x P x I 且0)))()(((=??x Q x P x I 。这表明))()((/|))()((x Q x P x x xQ x P x ??=???。

(4) 若解释I 使得0)))()(((=→?x Q x P x I ，则有I D d ∈使得0)()(=→d Q d P I I ，1)(=d P I 且0)(=d Q I ，0))((=?x xQ I ，0)))()(((=?→?x xQ x P x I 。这表明))()((|))()((x Q x P x x xQ x P x →?=?→?。

(5) 不成立。取解释I 如下。

},{b a D I =， 1)(=a P I ， 0)(=b P I ， 0)()(==b Q a Q I I

则1))(()))()(((=?=→?x xP I x Q x P x I 且0))((=?x xQ I ，这表明)(/|)(,))()((x xQ x xP x Q x P x ?=?→?。

(6) 不成立。取解释I 如下。

},{b a D I =， 1),(=b a P I ， 0),(),(),(===b b P a b P a a P I I I

则1)),((=??y x yP x I ，但0)),((=?x x xP I 。所以),(/|),(x x xP y x yP x ?=??。

17.设A ,B 是任意公式，证明以下结论。

(1) xB xA B A x ?∧?=∧?|)(

(2) xB xA B A x ?=?→?|,)(

(3) A y x A x y x ??=?|，其中x 对于A 中的y 是可代入的。

(4) )(|B A x B x A x →?=?→?

证明 (1) 若解释I 和I 中赋值v 使得1)))(((=∧?v B A x I ，则有I D d ∈使得1])/[)((=∧d x v B A I ，1])/[)((])/[)((==d x v B I d x v A I ，1))((=?v xA I 且1))((=?v xB I ，1))((=?∧?v xB xA I 。这表明xB xA B A x ?∧?=∧?|)(。

(2) 若解释I 和I 中赋值v 使得1))(()))(((=?=→?v xA I v B A x I ，则对于每个I D d ∈，1])/[)((])/[)((==→d x v A I d x v B A I ，1])/[)((=d x v B I ，1))((=?v xB I 。这表明xB xA B A x ?=?→?|,)(。

(3) 若解释I 和I 中赋值v 使得1))((=?v A x I y x ，则有I D d ∈使得1])/[)((=y x v A I y x ，

因为])/][/[)((])])/[)((/][/[)((])/[)((d y d x v A I d x v x I y d x v A I d x v A I y x ==，所以1])/][/[)((=d y d x v A I ，1])/[)((=?d x v yA I ，1))((=??v yA x I 。这表明

A y x A x y x ??=?|。

(4) 若解释I 和I 中赋值v 使得0)))(((=→?v B A x I ，则对于每个I D d ∈，0])/[)((=→d x v B A I ，1])/[)((=d x v A I 且0])/[)((=d x v B I ，因此1))((=?v xA I 且0))((=?v xB I ，0))((=?→?v xB xA I 。所以)(|B A x B x A x →?=?→?。

18.设变元x 既不是公式B 中的自由变元，也不是公式集Γ中任何公式的自由变元，A 是公式。若B A =?Γ|}{，则B A x =??Γ|}{。

证明 设解释I 和I 中赋值v 满足}{A x ??Γ，则1))((=?v xA I ，有I D d ∈使得1])/[)((=d x v A I 。因为x 不是公式集Γ中任何公式的自由变元，所以I 和]/[d x v 也满足Γ，I 和]/[d x v 满足}{A ?Γ。又因为B A =?Γ|}{，所以1])/[)((=d x v B I ，因为x 不是B 中的自由变元，因此1))((=v B I 。这表明B A x =??Γ|}{。

19. 设Γ是公式集合，A 是公式，则A =Γ|当且仅当}{A ??Γ不可满足。

证明 设}{A ??Γ可满足，解释I 和I 中赋值v 满足}{A ??Γ，则I 和v 满足Γ且0))((=v A I ，所以A /|=Γ。

设A /|=Γ，则有解释I 和I 中赋值v 满足Γ且0))((=v A I ，所以I 和v 满足}{A ??Γ。因此，}{A ??Γ可满足。

20.判断以下公式集合是否可满足，并说明理由。

(1) )}({}|)({x xP t t P ???是项

(2) )},(,)),(),(),((,),({y x yP x z x P z y P y x P z y x x x P x ??→∧?????

解 (1) 可满足。取解释I 和I 中赋值v 如下。

}2,1{=I D ， 0)1(=I P ， 1)2(=I P ，

对每个常元a ，1=I

a ；

对每个n 元函数符号f ，1),,(1=n I x x f ；

对每个变元x ，1)(=x v 。

可归纳证明：对每个项t ，1))((=v t I 。 I 和v 满足)}({}|)({x xP t t P ???是项。

(2) 可满足。取解释I 和I 中赋值v 如下。

I D 为自然数集， 1),(=y x P I 当且仅当 y x <

则I 和v 满足)},(,)),(),(),((,),({y x yP x z x P z y P y x P z y x x x P x ??→∧?????。