离散数学谓词逻辑技术总结.ppt

谓词逻辑习题课第九周 II. 讨论在给定解释下谓词公式的真值 III. 判断公式是不是永真式,并加以说明 IV. 转换前束合取范式 (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))) (1)?x(P→Q(x ))∨R(a)D ={-2,3,6} , P :2>1, Q(x ):x≤3, R(x ):x >5, 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 :2>1, Q(x ):x≤3, R(x ):x >5, 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 ,并加以说明(1)(?xP (x ) →?xQ (x )) ??x(P(x ) →Q(x)) 解:不是永真式,取解释如下 D = {1,2} P (1) P (2) Q (1) Q (2) FTFT 在该解释下?xP (x ) 为T,?xQ (x)为F,所以?xP (x ) →?xQ (x)为F;而(P (1) →Q (1)) 为T,(P (2) →Q (2)) 为T, 所以?x(P(x ) →Q(x))为T;综上该公式不是永真式