离散数学练习题答案.doc

《离散数学练习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题1．下列四个公式正确的是①②③④A.①③B.①④C.③④D.②④2.谓词公式中量词"x的辖域是()(A)(B)P(x)(C)(D)3.谓词公式的类型是（）(A)永真式(B)矛盾式(C)非永真式的可满足式(D)蕴涵式4.设个体域为整数集，下列公式中其真值为1的是()(A)(B)(C)(D)5.设个体域，公式在中消去量词后应为()(A)(B)(C)(D)6.在谓词演算中，下列各式正确的是()(A)(B)(C)(D)7.下列各式不正确的是()(A)(B)(C)(D)8.设I是如下一个解释：D＝{a,b},则在解释I下取真值为1的公式是().(A)$x"yP(x,y)(B)"x"yP(x,

2、y)(C)"xP(x,x)(D)"x$yP(x,y).9.设个体变元的论域都为自然数集合，，则以下命题中（）是假命题.A．B．C．D．10.下面不是命题的是（）A．B．C．D．11公式的前束范式为（）A．B．C．D．12.公式（）A．B．CD．13.的否定是（）A．B．C．D．14.下列谓词公式与等价的是（）A．B．C．D．15.在谓词演算中，是的有效结论，其理论依据是（）A．B．C．D．16.设个体域是整数集合，P代表"x"y((x

3、体域D是正整数集合，确定下列命题的真值：(1)　(　0　)　　(2)　(　0　)(3)(　0　)　　(4)(　1　)2.谓词公式中量词"x的辖域是3.公式中量的自由变量为x,y约束变量为x,z4.设个体域D＝{1,2},那么谓词公式消去量词后的等值式为.A(1)ÚA(2)Ú(B(1)ÙB(2)).5.设个体域D＝{a,b},公式消去量词化为.(G(a)®(H(a,a)ÚH(a,b)))Ù(G(b)®(H(b,a)ÚH(b,b)))6.设N(x)：x是自然数，Z(y)；y是整数，则命题“每个自然数都是整数，而有些整数不是自然数”符号化为7.谓词公式"x(F(x)®G(x))ÙØ"y(F(y)®

4、G(y))的类型是永假式．8.设个体域{1,2},谓词P(1)=1,P(2)=0，Q(1)=0，Q(2)=1，则"x(P(x)ÚQ(x))的真值是19.只用联结词表示以下公式三、计算及证明1.求谓词公式的真值．其中P：4>3，Q（x）：x>1，R（x）：x£2．f（-3）=1，f（1）=5，f（5）=-3．a：5．个体域D=（-3，1，5）．解：==2.说明公式是逻辑有效式(永真式)．解：因为是的代换实例，可知是逻辑有效式．或3.通过等值演算说明下列等值式成立：证：4.求谓词公式的前束范式解：(或)5.前提：$xF(x),"x(F(x)®G(x)ÙH(x))结论：$x(F(x)ÙH(x))6

5、.构造推理证明．（提示：.)证　①　　　　　　前提引入②　　　　　　T①,蕴含等值式③　　T②,量词否定　　　　　④　⑤　　　　　　T④,蕴含等值式法2：（反证法）　①　　　　　　前提引入②　　　　　　TE①,③　　ES②,　　　　　④　T③　,　⑤　　　　　　T③,⑥　　　　　　EG⑤　⑦P⑧T⑦⑨UG⑧⑩T④