第二章 谓词逻辑习题与解答1. 将下列命题符号化：(1) 所有的火车都比某些汽车快2) 任何金属都可以溶解在某种液体中3) 至少有一种金属可以溶解在所有液体中4) 每个人都有自己喜欢的职业5) 有些职业是所有的人都喜欢的解 (1) 取论域为所有交通工具的集合令是火车， 是汽车， 比y跑得快所有的火车都比某些汽车快”可以符号化为2) 取论域为所有物质的集合令是金属， 是液体， 可以溶解在y中任何金属都可以溶解在某种液体中” 可以符号化为3) 论域和谓词与(2)同至少有一种金属可以溶解在所有液体中” 可以符号化为4) 取论域为所有事物的集合令是人， 是职业， 喜欢y每个人都有自己喜欢的职业” 可以符号化为(5)论域和谓词与(4)同有些职业是所有的人都喜欢的”可以符号化为2. 取论域为正整数集，用函数（加法），（乘法）和谓词，将下列命题符号化：(1) 没有既是奇数，又是偶数的正整数2) 任何两个正整数都有最小公倍数3) 没有最大的素数4) 并非所有的素数都不是偶数解 先引进一些谓词如下：能被y整除，可表示为是奇数，可表示为是偶数，可表示为是素数，可表示为1) “没有既是奇数，又是偶数的正整数”可表示为，并可进一步符号化为。
2) “任何两个正整数都有最小公倍数”可表示为，并可进一步符号化为(3) “没有最大的素数”可表示为，并可进一步符号化为(4) “并非所有的素数都不是偶数”可表示为，并可进一步符号化为3. 取论域为实数集合，用函数，－（减法）和谓词，将下列命题符号化：(1) 没有最大的实数2) 任何两个不同的实数之间必有另一实数3) 函数在点a处连续4) 函数恰有一个根5) 函数是严格单调递增函数解 (1) “没有最大的实数”符号化为2) “任何两个不同的实数之间必有另一实数”符号化为3) “函数在点a处连续”的定义是：任给，总可以找到，使得只要就有函数在点a处连续”符号化为(4) “函数恰有一个根”符号化为5) “函数是严格单调递增函数”符号化为4. 指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域1) (2) (3) (4) (5) 解 (1) 变元 x 在中三次出现都是约束出现，"x 的唯一出现的辖域是 P(y, x) ® P(x, a)2) 变元 x 在中的头两次出现是约束出现，第三次出现是自由出现变元 y 在中的唯一出现是自由出现变元 z 在中的唯一出现是约束出现"x 的唯一出现的辖域是 P(x)，"z 的唯一出现的辖域是Q(x, y)。
3) 变元 x 在中的头五次出现是约束出现，第六次出现是自由出现"x 的第一次出现的辖域是P(x) Ù R(x)，第二次出现的辖域是P(x)4) 变元 x 在中的头两次出现是自由出现，后两次出现是约束出现"x 的唯一出现的辖域是 P(z, g(x, y))， "y 的唯一出现的辖域是P(f(x, y), x) ® "xP(z, g(x, y))5) 变元 x 在中的头五次出现是约束出现，第六次出现是自由出现"x 的唯一出现的辖域是P(x) ® Q(x) Ù $xR(x)，$x 的唯一出现的辖域是R(x)5. 归纳证明：若t，是项，则也是项证明 ① 若t是x，则是，是项② 若t是不同于x的变元y，则仍是y，是项③ 若t是常元a，则仍是a，是项④若t是，则是，由归纳假设知都是项，所以是项6. 归纳证明：若t是项，A是公式，则也是公式证明 ① 若A是，则是，由上题知都是项，所以是公式② 若A是，则是，由归纳假设知是公式，所以是公式③ 若A是，则是，由归纳假设知和都是公式，所以是公式④ 若A是，则仍是A，是公式⑤ 若A是，其中y是不同于x的变元，则是，由归纳假设知是公式，所以是公式7. 给定解释I和I中赋值v如下：，，，，，，，计算下列公式在解释I和赋值I中v下的真值。
1) (2) (3) 解 (1) (2) (3) 7. 给定解释I如下：， ， 判断I是不是以下语句的模型1) (2) (3) (4) (5) (6) 解 (1) (2) (3) (4) (5) (6) 9. 写出一个语句A，使得A有模型，并且A的每个模型的论域至少有三个元素解 语句A为给定解释如下为自然数集合， 当且仅当， ，，则是A的模型，A有模型任取满足语句A的解释I，则，又因为，所以，，是论域中三个不同元素，论域中至少有三个元素10. 写出一个语句A，使得A有模型，并且A的每个模型的论域有无穷多个元素解 语句A为给定解释如下为自然数集合， 当且仅当 则是A的模型，A有模型任取满足语句A的解释I，取，因为，所以有使得，又因为，故因为，所以有使得，又因为，故因为，所以，故因此，，，是论域中的三个不同元素这个过程可以不断进行下去，得到因此，论域 DI 中必然有无穷多个元素11. 判断以下公式是不是永真式、永假式、可满足式，并说明理由1) (2) (3) (4) (5) (6) (7) 解 (1) 是永真式若解释I使得，则或① 若，则存在使得，② 若，则存在使得，。
因此，2) 是非永真的可满足式给定解释I如下 ， 则给定解释如下3) 是非永真的可满足式给定解释I如下 ， 则给定解释如下4) 是非永真的可满足式给定解释I如下给定解释如下5) 是非永真的可满足式给定解释I如下 ， 则给定解释如下6) 是永真式若解释I使得，则存在使得，因此且，且，7) 是永真式若解释I使得，则且存在使得，又因为，所以，12.设A,B是任意公式，证明以下公式是永真式1) ,其中项t对于A中的x是可代入的2) (3) (4) (5) (6) ，其中x不是A的自由变元解 (1) 任取解释I和I中赋值v，若,则，所以这表明是永真式2) 任取解释I和I中赋值v， 当且仅当 当且仅当 存在使得 当且仅当 存在使得 当且仅当 这表明是永真式3) 任取解释I和I中赋值v， 当且仅当 当且仅当 存在使得 当且仅当 存在使得 当且仅当 这表明是永真式4) 任取解释I和I中赋值v，若，则存在使得，，且，这表明是永真式5) 任取解释I和I中赋值v，若，则存在使得，，这表明是永真式6) 任取解释I和I中赋值v，若，则对于每个，，因为x不是A的自由变元，所以，因此，。
这表明是永真式13.设是公式A的闭包，是，其中证明：(1) A是永真式当且仅当是永真式；(2) A是可满足式当且仅当是可满足式证明 (1) （）首先证明：若A是永真式，则是永真式设A是永真式任取解释I和I中赋值v，任取，因为也是I中赋值，所以，是永真式若A是永真式，则是永真式，… ，是永真式因为是永真式，所以若是永真式，则A是永真式2) （）因为是永真式，所以若解释I和I中赋值v满足A，则I和v满足若解释I和I中赋值v满足，则有使得，I和I中赋值满足A14.判断以下等值式是否成立，并说明理由1) (2) (3) (4) (5) (6) 解 (1) 不成立取解释I如下 ， ， ， 则且2) 不成立取解释I如下 ， ， ， 则且3) 不成立取解释I和I中赋值v下 ， ， 则且4) 成立任取解释I和I中赋值v，因为x不是中的自由变元，所以对于每个， 当且仅当对于每个， 当且仅当(5) 不成立取解释I如下 ， ， ， 则且6) 不成立取解释I如下 ， ， 则且15.设A,B是任意公式，证明以下等值式1) ，其中y在A中不出现2) (3) ，其中x不是B的自由变元，y不是A的自由变元。
4) ，其中x不是B的自由变元，y不是A的自由变元5) ，其中x不是B的自由变元，y不是A的自由变元6) 证明 (1) (2) (3) (4) (5) (6) 任取解释I和I中赋值v， 当且仅当有使得 当且仅当有使得 当且仅当有使得 当且仅当有使得 当且仅当16.判断以下逻辑推论关系是否成立，并说明理由1) (2) (3) (4) (5) (6) 解 (1) 不成立取解释I如下 ， ， ， 则且2) 不成立取解释I如下 ， ， ， 则且3) 不成立取解释I如下 ， ， 则且4) 若解释I使得，则有使得，且，，5) 不成立取解释I如下 ， ， 则且，这表明6) 不成立取解释I如下 ， 则，但17.设A,B是任意公式，证明以下结论1) (2) (3) ，其中x对于A中的y是可代入的4) 证明 (1) 若解释I和I中赋值v使得，则有使得，，且，2) 若解释I和I中赋值v使得，则对于每个，，，3) 若解释I和I中赋值v使得，则有使得，因为，所以，，4) 若解释I和I中赋值v使得，则对于每个，，且，因此且，18.设变元x既不是公式B中的自由变元，也不是公式集中任何公式的自由变元，A是公式。
若，则证明 设解释I和I中赋值v满足，则，有使得因为x不是公式集中任何公式的自由变元，所以I和也满足，I和满足又因为，所以，因为x不是B中的自由变元，因此19. 设是公式集合，A是公式，则当且仅当不可满足证明 设可满足，解释I和I中赋值v满足，则I和v满足且，所以设，则有解释I和I中赋值v满足且，所以I和v满足因此，可满足20.判断以下公式集合是否可满足，并说明理由1) (2) 解 (1) 可满足取解释I和I中赋值v如下 ， ，对每个常元a，；对每个n元函数符号f，；对每个变元x，可归纳证明：对每个项t，I和v满足2) 可满足取解释I和I中赋值v如下为自然数集， 当且仅当 则I和v满足。