5离散数学第二章练习题答案.docVIP

选择题 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,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． C D． 13. 的否定是（ ） A． B． C． D． 14.下列谓词公式与等价的是（ ） A． B． C． D． 15.在谓词演算中，是的有效结论，其理论依据是（ ） A． B． C． D． 16. 设个体域是整数集合，P代表?x?y((x?y)?(x?y?x))，下面4个命题中为真的是( ) (A) P是真命题 (B) P是假命题 (C) P是一阶逻辑公式，但不是命题 (D) P不是一阶逻辑公式 二、填空题 1. 设全体域D是正整数集合，确定下列命题的真值： (1) 　(　　)　　 (2) 　(　　) (3) (　　)　　 (4) (　　) 2. 谓词公式中量词?x的辖域是 3. 公式中量的自由变量为 约束变量为 4. 设个体域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??G?y?)的类型是 永假式 ． 8. 设个体域{1,2},谓词P(1)=1,P(2)=0，Q(1)=0，Q(2)=1，则?x(P(x)?Q(x))的真值是 1 9.只用联结词表示以下公式 三、计算及证明 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.说明公式是逻辑有效式(永真式)． 解：因为是的代换实