湘潭大学 任任版 离散数学课后习题答案 习题15.doc

《湘潭大学 任任版 离散数学课后习题答案 习题15.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题十五1、设下面所有谓词的论域D={a、b、c}。试将下面命题中的量词消除，写成与之等值的命题公式。分析：本题主要是考察对全称量词、存在量词的理解，然后通过合取词、析取词把全称量词和存在量词消去。（1）解：（2）解：（3）解：2、指出下列命题的真值：分析：本题主要是考察合式公式的解释的定义，已经判定给定解释下合式公式的真值。（1）其中，＞2＞5，论域D={-2，3，6}解：假。（x为-2时不成立）（2）其中，＞3，论域D={2}。解：真。3、在一阶逻辑中，将下列命题符号化：分析：本题主要是考察存在量词、全称量词已经基本的连接词的运用。（1）凡有理数均可表示为分数。解

2、：令：：x是有理数；Q（x）:x可表示为分数。（2）有些实数是有理数。解：P（x）：:x是实数,Q(x)：x是有理数。（3）并非所有实数都是有理数。解：P（x）：:x是实数,Q(x)：x是有理数。（4）如果明天天气好，有一些学生将去公园。解：P（x）:x去公园S（x）:x是学生W：明天天气好（5）对任意的正实数，都存在大于该实数的实数。解：P（x）:x是实数；G（x,y）：:x大于y。（6）对任意给＞0，，都在存在N，使当n＞N时，有＜解：G（x，y）:x＞y,4、指出下列公式中的自由变元和约束变元，并指出各量词的作用域。分析：本题主要是考察自由边缘、约束变元的定义，

3、以及量词的作用域的概念。（1）解；自由变元z,约束变元x,第一个的作用域是，第二个是。（2）解：自由变元z，约束为元：x，y。第一个的作用域为第二个的作用域为第二个；的作用域为。（3）解：自由变元：，约束变元：x和y；，的作用域为（4）解：无自由变元约束变元x，y；的作用域：，的作用域：（5）解：自由变元：y与G(x，y)中的x，约束变元：F(x)中的x；的作用域：F(x)（6）解：自由变元：Z与H(x，y)中的y；约束变元：,和的作用范围：，的作用范围：5．设谓词公式。判定以下改名是否正确：分析：本题主要是考察改名规则的定义，以及它的适用范围。有兴趣的同学可以顺便了

4、解一下代替规则情形。（1）解：错误（2）解：正确（3）解：错误（4）解：错误（5）解：错误6．设I是如下一个解释：，，，，。试确定下列公式在I下的真值：分析：本题主要考察合式公式在特定解释下的真值。（1）解：真（2）解：假（3）解：真（4）解：真7．判断下列公式的恒真性和恒假性分析：本题主要是根据已知的命题公式、合式公式的基本等值式来进行推导，看该合式公式是与1等值还是与0等值。（1）解：恒真（2）解：恒真（3）解：恒真（4）解：恒假8．设G（x）是恰含自由变元x的谓词公式，H是不含变元x的谓词公式，证明：（1）（2）分析：本题根据量词作用域的扩张进行证明。证明（1）

5、证明（2）9．设G（x，y）是任意一个含x，y自由出现的谓词公式，证明：（1）分析：本题主要是根据两个合式公式等值的定义进行证明。证：设D是论域，I是G（x，y）的一个解释。（a）若在I下的为真，则在I下，对任意的,即是真命题，反之亦然。（b）若在I下为假，则在I下必存在或，使得G（x0,y）或G（x,y0）为假，于是，此xo或yo亦弄假，反之亦然。（2）分析：本题主要是根据两个合式公式等值的定义进行证明。证：设D是论域，I是G（x,y）的一个解释。（a）若在I下为真，则在I下存在使G（x0,y0）为真命题，于是，也是真命题，反之亦然。（b）若在I下为假，则对任意，G

6、（x,y）均为假，故亦为假，反之亦然。10．将下列公式化成等价的前束范式：分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式。（1）解：（2）解：（3）解：（4）解：11．给出下面公式的skolem范式：分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式，然后根据前束范式写出对应的skolem范式。（1）解：∴所求为:（2）解:原式即为所求（3）解：即为所求。12．假设是公式G的前束范式，其中M（x,y）是仅仅包含变量x，y的母式，设f是不出

7、现在M（x,y）中的函数符号。证明：G恒真当且仅当恒真。分析：本题主要是用反证法，根据解释的定义来证明结论成立。证：设恒真。若不真，则存在一个解释I,使得对任意的（论域），为假。于是，在I下也为假。此为矛盾。反之，设恒真。若不是恒真，则存在一个解释I’，使得对任意，存在，使为假。由于是不出现在中的函数符号，故可定义函数，使得。于是，在I’下为假。矛盾。故结论成立。13．证明分析：本题是根据基本的等值式、蕴含式、以及US、UG、ES、EG规则证明结论成立。证：（1）前提引入(2)化简（1）（3）US规则，根据（2）（4）化简（1）（5）US规则，根据（