离散数学 第二章练习题答案 VIP免费

一、选择题1．下列四个公式正确的是①)()())()((xxBxxAxBxAx②)()())()((xxBxxAxBxAx③)()())()((xxBxxAxBxAx④))()(()()(xBxAxxxBxxAA.①③B.①④C.③④D.②④2.谓词公式)())()((xQyyRxPx中量词x的辖域是()(A)))()((yyRxPx(B)P(x)(C))()(yyRxP(D))(xQ3.谓词公式))()(()(xxQxQxxxP的类型是（）(A)永真式(B)矛盾式(C)非永真式的可满足式(D)蕴涵式4.设个体域为整数集，下列公式中其真值为1的是()(A))0(yxyx(B))0(yxxy(C))0(yxyx(D))0(yxyx5.设个体域{,}Aab，公式()()xPxxSx在中消去量词后应为()(A)()()PxSx(B)()()(()())PaPbSaSb(C)()()PaSb(D)()()()()PaPbSaSb6.在谓词演算中，下列各式正确的是()(A)(,)(,)xyAxyyxAxy(B)(,)(,)xyAxyyxAxy(C)(,)(,)xyAxyxyAxy(D)(,)(,)xyAxyyxAxy7.下列各式不正确的是()(A)(()())()()xPxQxxPxxQx(B)(()())()()xPxQxxPxxQx(C)(()())()()xPxQxxPxxQx(D)(())()xPxQxPxQ8.设I是如下一个解释：D＝{a,b},0101b)P(b,a)P(b,b)P(a,),(aaP则在解释I下取真值为1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).9.设个体变元zyx,,的论域都为自然数集合，(,,):,Pxyzxyz(,,),(,):QxyzxyzRxyxy：，则以下命题中（）是假命题.A．),0,(xxxPB．),,(yyxyPxC．),,(xxyyQxD．)0,(xxR10.下面不是命题的是（）A．()xPxB．()()xPxC．()()()xPxPyD．()()(()())xyPxRy11公式()()()()xPxxQx的前束范式为（）A．()()(()())xyPxQyB．()()(()())xyPxQyC．()()(()())xyPxQyD．()()(()())xyPxQy12.公式()(())xPxQ（）A．(()())(()())xPxQQxPxB．(()())(()())xPxQQxPxC(()())(()())xPxQQxPxD．(()())(()())xPxQQxPx13.()()(,)xyPxy的否定是（）A．()()(,)xyPxyB．()()(,)xyPxyC．()()(,)xyPxyD．()()(,)xyPxy14.下列谓词公式与()(()())xAxBx等价的是（）A．()()()()xAxxBxB．()()()()xAxxBxC．()()()()xAxxBxD．()()()()xAxxBx15.在谓词演算中，()Pa是()xPx的有效结论，其理论依据是（）A．USB．UGC．ESD．EG16.设个体域是整数集合，P代表xy((xy)(xyx))，下面4个命题中为真的是()(A)P是真命题(B)P是假命题(C)P是一阶逻辑公式，但不是命题(D)P不是一阶逻辑公式二、填空题1.设全体域D是正整数集合，确定下列命题的真值：(1)()xyxyy(0)(2)()+xyxyy(0)(3)()+xyxyx(0)(4)(2)xyyx(1)2.谓词公式()((,)())()((,)()())xPxyQzyRxyzQz中量词x的辖域是3.公式()(()(,)()(,))()xPxQxyzRyzSx中量的自由变量为x,y约束变量为x,z4.设个体域D＝{1,2},那么谓词公式)()(yyBxxA消去量词后的等值式为.A(1)A(2)(B(1)B(2)).5.设个体域D＝{a,b},公式)),()((yxyHxGx消去量词化为.(G(a)(H(a,a)H(a,b)))(G(b)(H(b,a)H(b,b)))6.设N(x)：x是自然数，Z(y)；y是整数，则命题“每个自然数都是整数，而有些整数不是自然数”符号化为(()())(()())xNxZxxZxNx7.谓词公式xFxGxyFyGy)的类型是永假式．8.设个体域{1,2},谓词P(1)=1,P(2)=0，Q(1)=0，Q(2)=1，则x(P(x)Q(x))的真值是19.只用联结词,,表示以下公式()(()())xPxQx()(()())xPxQx()(()()())xPxyQy()((()()())(()()()))xPxyQyyQyPx()(()()())yxPxQy()(()()())yQyxPx三、计算及证明1.求谓词公式))(())((afRxQPx的真值．其中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）．解：))(())((afRxQPx=))5(())5(())1(())3((fRQPQPQP=...