离散数学谓词逻辑-1.ppt

谓词逻辑习题课 第九周 2014.11 命题符号化 讨论在给定解释下谓词公式的真值 判断公式是不是永真式，并加以说明 转换前束合取范式 推理证明 1.将下列命题符号化 (1)没有不犯错误的人 (2) 发光的不都是金子 (3) 一切人都不一样高 (4) 并不是所有的汽车都比火车快 (5)不管黑猫白猫，抓住老鼠就是好猫 (6)有唯一的偶素数 (7)对平面上任意两点，有且仅有一条直线通过这 两点 (1) 没有不犯错误的人 ① 存在不犯错误的人是不可能的。 ② 只要是人，必然犯错误。 设 M(x): x是人，F(x):x犯错误 命题符号化为① ┐(?x)(M(x)∧┐F(x)) ② (?x)(M(x)→F(x)) (2) 发光的不都是金子 ① 不是发光的东西都是金子。 ② 存在着发光的东西不是金子。 设 L(x)：x是发光的东西，G(x)：x是金子。 命题符号化为 ① ┐(?x)(L(x)→G(x)) ② (?x)(L(x)∧﹁G(x))  (3) 一切人都不一样高 设 F(x):x是人, H(x,y), x与y相同, L(x,y): x与y一样高， 命题符号化为 (?x)(F(x)??y(F(y)??H(x,y)??L(x,y))) 或 (?x)?y(F(x)?F(y)??H(x,y)??L(x,y)) (4) 并不是所有的汽车都比火车快 设 F(x):x是汽车, G(y):y是火车, H(x,y):x比y快， 命题符号化为 ?(?x)?y(F(x)?G(y)?H(x,y)) 或 (?x)?y(F(x)?G(y)??H(x,y)) （5）不管黑猫白猫，抓住老鼠就是好猫 需要考虑问题： ①只是限制黑猫白猫，还是包含其它颜色的猫？ ②是指至少抓住一只就可以，还是抓住所有的？ 设 C(x):x是猫,W(x):x是白的,B(x):x是黑的 G(x):x是好的,M(x):x是老鼠, K(x):x抓住y 命题符号化为 (?x)?y(C(x)∧M(y)∧(B(x)∨W(x))∧K(x,y))→G(x)) (6)有唯一的偶素数 设：Q(x):x是偶数,P(x):x是素数, E(x,y):x＝y 命题符号化为： (?x)(Q(x)?P(x)???y(Q(y)?P(y)??E(x,y))) (7)对平面上任意两点，有且仅有一条直线通过这 两点 设 P(x):x是一个点, L(x):x是一条直线 R(x,y,z):z通过x,y, E(x,y):x等于y 命题符号化为 (?x)?y(P(x)∧P(y)∧﹁E(x,y)) →?z(L(z)∧R(x,y,z)∧?u((L(u)∧R(x,y,u))→E(u,z))) 2.讨论在给定解释下谓词公式的真值 （1）?x(P→Q(x))∨R(a) D={-2,3,6} , P:21,Q(x):x≤3, R(x):x5,a:5 （2）?x?y(P(x)∧Q(x,y)) D= {1,2}， P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F （1）?x(P→Q(x))∨R(a) D={-2,3,6} , P:21,Q(x):x≤3, R(x):x5,a:5 ?x(P→Q(x))∨R(a)?(P→?xQ(x))∨R(a) ?(P→(Q(-2)∧Q(3)∧Q(6)))∨R(5) ?(T→(T ∧T ∧F ))∨F?(T→F)∨F?F∨F ?F （2）?x?y(P(x)∧Q(x,y)) D= {1,2}， P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F 真值为F 3.判断下列公式是不是永真式，并加以说明 （1）(?xP(x) →?xQ(x)) ? ?x(P(x) →Q(x)) 解：不是永真式，取解释如下 D= {1,2} P(1) P(2) Q(1) Q(2) F T F T 在该解释下?