qhgAAA第二章习题解答.doc

《qhgAAA第二章习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词逻辑习题与解答⒈将下列命题符号化：⑴所有的火车都比某些汽车快。⑵任何金属都可以溶解在某种液体中。⑶至少有一种金属可以溶解在所有液体中。⑷每个人都有自己喜欢的职业。⑸有些职业是所有的人都喜欢的。解⑴取论域为所有交通工具的集合。令是火车，是汽车，比y跑得快。“所有的火车都比某些汽车快”可以符号化为。⑵取论域为所有物质的集合。令是金属，是液体，可以溶解在y中。“任何金属都可以溶解在某种液体中”可以符号化为。⑶论域与谓词与(2)同。“至少有一种金属可以溶解在所有液体中”可以符号化为。⑷取论域为所有事物的集合。令是

2、人，是职业，喜欢y。“每个人都有自己喜欢的职业”可以符号化为⑸论域与谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为。⒉取论域为正整数集，用函数（加法），（乘法）和谓词，将下列命题符号化：⑴没有既是奇数，又是偶数的正整数。⑵任何两个正整数都有最小公倍数。⑶没有最大的素数。⑷并非所有的素数都不是偶数。解先引进一些谓词如下：能被y整除，可表示为。是奇数，可表示为。是偶数，可表示为。是素数，可表示为。⑴“没有既是奇数，又是偶数的正整数”可表示为，并可进一步符号化为。⑵“任何两个正整数都有最小公倍数”可表示为，并

3、可进一步符号化为⑶“没有最大的素数”可表示为，并可进一步符号化为⑷“并非所有的素数都不是偶数”可表示为，并可进一步符号化为⒊取论域为实数集合，用函数，－（减法）和谓词，将下列命题符号化：⑴没有最大的实数。⑵任何两不同的实数之间必有另一实数。⑶函数在点a处连续。⑷函数恰有一个根。⑸函数是严格单调递增函数。解⑴“没有最大的实数”符号化为。⑵“任何两不同的实数之间必有另一实数”符号化为。⑶“函数在点a处连续”的定义是：任给，总可以找到，使得只要就有。“函数在点a处连续”符号化为⑷“函数恰有一个根”符号化为。⑸“函数是严格

4、单调递增函数”符号化为。⒋指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。(1)(2)(3)(4)(5)5.归纳证明：若t，是项，则也是项。证明①若t是x，则是，是项。②若t是不同于x的变元y，则仍是y，是项。③若t是常元a，则仍是a，是项。④若t是，则是，由归纳假设知都是项，所以是项。6.归纳证明：若t是项，A是公式，则也是公式。证明①若A是，则是，由上题知都是项，所以是公式。②若A是，则是，由归纳假设知是公式，所以是公式。③若A是，则是，由归纳假设知和都是公式，所以是公式。④若A是，则仍是

5、A，是公式。⑤若A是，其中y是不同于x的变元，则是，由归纳假设知是公式，所以是公式。7.给定解释I和I中赋值v如下：，，，，，，，计算下列公式在解释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，则，又因为，所

6、以，，是论域中三个不同元素，论域中至少有三个元素。10.写出一个语句A，使得A有模型，并且A的每个模型的论域有无穷多个元素。解语句A为。给定解释如下。为自然数集合，当且仅当则是A的模型，A有模型。任取满足语句A的解释I，取，因为，所以有使得，又因为，故。因为，所以有使得，又因为，故。因为，所以，故。因此，，，是论域中的三个不同元素。这个过程可以永远进行下去，得到因此，论域中必然有无穷多个元素。11.判断以下公式是不是永真式、永假式、可满足式，并说明理由。(1)(2)(3)(4)(5)(6)(7)解(1)是永真式。若

7、解释I使得，则或。①若，则存在使得，。②若，则存在使得，。因此，。(2)是非永真的可满足式。给定解释I如下。，，则。给定解释如下。，，，，则。(3)是非永真的可满足式。给定解释I如下。，，则。给定解释如下。，，，，则。(4)是非永真的可满足式。给定解释I如下。，则。给定解释如下。，，则。(5)是非永真的可满足式。给定解释I如下。，，则。给定解释如下。，，，，则。(6)是永真式。若解释I使得，则存在使得，因此且，且，。(7)是永真式。若解释I使得，则且。存在使得，又因为，所以，。因此，。12.设A,B是任意公式，证明

8、以下公式是永真式。(1),其中项t对于A中的x是可代入的。(2)(3)(4)(5)(6)，其中x不是A的自由变元。解(1)任取解释I和I中赋值v，若,则，所以。这表明是永真式。(2)任取解释I和I中赋值v，当且仅当当且仅当存在使得当且仅当存在使得当且仅当这表明是永真式。(3)任取解释I和I中赋值v，当且仅当当且仅当存在使得当且仅当存在使得当且仅当这表明是永真