资源描述：
《离散数学(刘任任版)第14章答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学习题解答1、2、指出下列命题的真值：3、在一阶逻辑中，将下列命题符号化：（1）凡有理数均可表示为分数。解：P(x)：x是有理数；Q（x）:x可表示为分数。在谓词逻辑中基本语句的形式化（1）“D中所有x都有性质F”（2）“D中有的x具有性质F”（3）“D中所有x而言，如果x有性质F，则x就有性质G”（4）“D中有的x具有性质F，又有性质G”设D是论域：（5）“对于D中的所有x和y而言，若x有性质F,y有性质G，则x与y有关系H”（6）“对于D中的所有x而言，若x有性质F,就存在y有性质G，并且x与y有关系H”（7）“存在D中的x有性质F，并且对D中所有y而言，
2、如果y有性质G，则x与y就有关系H”（8）“D中存在着x与y，x有性质F，y有性质G，并且x与y有关系H”解：自由变元z，约束为元：x，y。第一个的作用域为(2)第二个的作用域为第二个P(x)；第二个的作用域的作用域为Q(y)(3)解：自由变元z，约束为元：x，y。的作用域为R(y)解：无自由变元，约束为元：x，y。(4)的作用域为：的作用域为：H(x,y)(5)解：自由变元:y与G(x,y)中的x,约束变元:F(x)中的x解：自由变元:Z与H(x,y)中的y;约束变元:x,y。的作用域：F(x)(6)和的作用域：的作用域：5．设谓词公式。判定以下改名是否正确：(1
3、)(2)(3)(4)(5)错误正确错误错误错误6．(1)解：真(2)解：假(3)解：真(4)解：真7.判断下列公式的恒真性和恒假性(1)解：恒真(2)解：恒真(3)解：恒真(4)解：恒假(5)解：满足8．(1)(2)证明（1）证明（2）9．证：设D是论域，I是G（x，y）的一个解释。（a）若（1）在I下的为真，则在I下，对任意的,即是真命题。（b）若在I下的为假,则在I下,必存在使得G（x0,y）或G（x,y0）为假，于是，此xo或yo亦弄假证：设D是论域，I是G（x,y）的一个解释。（2）（a)若也是真命题，反之亦然。在I下的为真，则在I下,有使G（x0,y0）为
4、真命题，于是，(3)解：(4)解：11．给出下面公式的skolem范式：(1)∴所求为:解:原式:(2)即为所求(3)解：12．假设是公式G的前束范式，其中M（x,y）是仅仅包含变量x，y的母式，设f是不出现在M（x,y）中的函数符号。证明：G恒真当且仅当恒真。证：设恒真。若不真，则存在一个解释I,使得对任意的（论域），为假。于是，G在I下也为假。此为矛盾。反之，设恒真。若不是恒真，则存在一个解释I’，使得对任意，存在，使为假。由于f是不出现在中的函数符号，故可定义函数，使得。于是，在I’下为假。矛盾。故结论成立。证明:（1）（2）（3）（4）（5）（6）前提引入1
5、3．证明假言推理(2)(4)UG，（5）US，（1）前提引入US，（3）前提:结论:证明:（1）（2）等值替换（1）（3）（4）（5）（6）前提引入14．构造下面推理的证明US，（5）假言推理(2)(4)等值替换（2）US，（3）解：（4）错误。F(y)中的变元y与（2）中的变元重名。15．指出下面两个推理的错误。（1）（6）（5）G(y)假言推理,(2),(4)（3）（2）UG，(5)前提引入US，（1）前提引入（4）F(y)ES,(3)解：（3）错误。在（2）中还有自由变元y。（1）（5）（3）（2）EG，(4)前提引入US，（1）（4）ES，（2）US，（3）
6、在推理过程中,指出下面各证明序列中的错误②F(c)→G(c)（1）①F(x)→（2）①F(y)→G(y)②F(c)→G(c)（3）①②前提引入EG规则①前提引入ES规则①前提引入ES规则①（4）①F(c)∧G(b)（5）①F(c)→G(c)②②前提引入前提引入UG规则①EG规则①16.每个学术会的成员都是知识分子并且是专家，有些成员是青年人。证明：有的成员是青年专家。解：P（x）：x是学术会的成员；E（x）：x是专家；G（x）：x是知识分子；Y（x）：x是青年人。前提：结论：前提:结论:（1）前提引入（2）US，（1）（3）（4）（5）P(c)（6）（7）E(c)（
7、8）Y(c)（9）（10）前提引入ES，（3）化简(4)假言推理(2)(5)化简(6)化简(4)合并(7)(8)EG，（9）
