《离散数学课件》谓词演算的推理理论.ppt

*/51 例 下面推理是否正确？ 设前提为?x?yF（x，y）， （1） ?x?yF（x，y） 前提引入 （2） ?yF（t，y） 全称量词消去 （3） F（t，c） 存在量词消去 （4） ?xF（x，c） 全称量词引入 （5） ?y?xF（x，y） 存在量词引入 解： 推理并不正确。 如果给定解释I：个体域为实数集，F(x,y)：x＞y。 则 ? x?yF（x，y）为真， 而?y ?xF（x，y）意为“存在着最小实数”， 是假命题，故知推理不正确。 之所以出现这样的错误，是在第（3）步中， ?yF（t，y ）非闭式（含有自由变元t)。 * 构造推理证明 例1 证明苏格拉底三段论: “人都是要死的, 苏格拉 底是人，所以苏格拉底是要死的.” 令 F(x): x是人, G(x): x是要死的, a: 苏格拉底 前提：?x(F(x)?G(x))，F(a) 结论：G(a) 证明：① F(a) 前提引入 ② ?x(F(x)?G(x)) 前提引入 ③ F(a)?G(a) ②UI ④ G(a) ①③假言推理 注意：使用UI时，用a取代x . * 构造推理证明(续) 例2 乌鸦都不是白色的. 北京鸭是白色的. 因此，北京鸭不是乌鸦. 令 F(x): x是乌鸦, G(x): x是北京鸭, H(x): x是白色的 前提：?x(F(x)??H(x))， ?x(G(x)?H(x)) 结论：?x(G(x)??F(x)) * 前提：?x(F(x)??H(x))，?x(G(x)?H(x))结 论：?x(G(x)??F(x)) 证明： ① ?x(F(x)??H(x)) 前提引入 ② F(y)??H(y) ①UI ③ ?x(G(x)?H(x)) 前提引入 ④ G(y)?H(y) ③UI ⑤ ?H(y)??G(y) ④置换 ⑥ F(y)??G(y) ②⑤假言三段论 ⑦ G(y)??F(y) ⑥置换 ⑧ ?x(G(x)??F(x)) ⑦UG * 构造推理证明(续) 例3 构造下述推理证明 前提：?x(F(x)?G(x))，?xF(x) 结论：?xG(x) 证明：① ?xF(x) 前提引入 ② ?x(F(x)?G(x)) 前提引入 ③ F(c) ①EI ④ F(c)?G(c) ②UI ⑤ G(c) ③④假言推理 ⑥ ?xG(x) ⑤EG 注意：必须先消存在量词 * 构造推理证明(续) 例4 构造下述推理证明 前提：?xF(x)??xG(x) 结论：?x(F(x)?G(x)) 证明：① ?xF(x)??xG(x) 前提引入 ② ?x?y(F(x)?G(y)) ①置换 ③ ?x(F(x)?G(z)) ②UI ④ F(z)?G(z) ③UI ⑤ ?x(F(x)?G(x)) ④UG */51 例 在自然推理系统中构造下面推理的证明  ??? 前提： ?xP(x)→?xQ(x)??????? 结论： ?x(P(x)→Q(x)) 证明: ? xP(x)→?xQ(x) 前提引入 ?xP(x)