离散数学(chapter2).pptVIP

离散数学 离散数学 注1：y 在A (y)中自由出现，且y 取任何值时A为真； 注2：取代 y 的x不能在A (y)中约束出现。 二、谓词逻辑推理遵循的推理规则（续） 全称量词消去规则(UI规则) (1) ? xA (x) ? A (y)，y不在A (x)中约束出现。 (2) ? xA (x) ? A (c) ，c为个体域中任意个体常项。 注：x在A (x)中必须是自由出现个体变项。 全称量词引入规则(UG规则) A (y) ? ? xA (x) 离散数学 注1：c 是使A为真的特定个体常项；注2：c 不曾 在A(x)中出现过；注3：A (x)中有异于x 的自由出现 的个体变项时，此规则不可用。 二、谓词逻辑推理遵循的推理规则（续） 存在量词引入规则(EG规则)： A (c) ? ? xA (x) 存在量词消去规则(EI规则)： ? xA (x) ? A (c) 注1：c 是特定的个体常项； 注2：取代 c 的x不能已在A (c)中出现过。 离散数学 例7：证明苏格拉底三段论“ 凡人都是要死的，苏格 拉底是人，所以苏格拉底是要死的”。 三、推理证明 解题步骤: (1) 将命题符号化； (2) 写出前提、结论； (3) 用推理规则进行 推理(构造证明)。 解：F (x)：x是人，G (x)：x是要死的，a：苏格拉底 前提： ? x(F (x) ? G (x))，F (a) 结论： G (a) 证明： ① ? x(F (x) ? G (x)) ② F (a) ? G (a) ③ F (a) ④ G (a) 前提引入 ①UI 前提引入 ②③假言推理 离散数学 例8：证明“ 每个学术会的成员都是工人并且是专家， 有些成员是青年人，所以有的成员是青年专家”。 三、推理证明（续） 解：F (x)： x是学术会的成员，G (x)：x是工人， H (x)：x是专家， R (x)：x是青年人， 前提：? x(F (x) ? (G (x) ? H (x))), ? x(F (x) ? R (x)) 结论： ? x(F (x) ? R (x) ? H (x)) 离散数学 三、推理证明（续） 证明： ① ? x(F (x) ? R (x)) ② F (c) ? R (c) ③ ? x(F (x) ? (G (x) ? H (x))) ④ F (c) ? (G (c) ? H (c)) 前提引入 ①EI 前提引入 ②化简 ⑤ F (c) ⑥ G (c) ? H (c) ⑦ H (c) ⑧ F (c) ? R (c) ? H (c) ⑨ ? x(F (x) ? R (x) ? H (x)) ③UI ④⑤假言推理 ⑥化简 ②⑦合取 ⑧EG 离散数学 三、推理证明（续） 在前提中，若既有存在量词，又有全称量词，应先引入存在量词。 离散数学 例9：构造下列推理的证明 (1) 前提：? ? x(F (x) ? H (x))，? x(G (x) ? H (x)) 结论：? x(G (x) ? ? F (x)) (2) 前提： ? xF (x) ? ? xG (x) 结论： ? x(F (x) ? G (x)) 三、推理证明（续） 离散数学 (1) 前提： ? ? x(F (x) ? H (x))，? x(G (x) ? H (x)) 结论： ? x(G (x) ? ? F (x)) 三、推理证明（续） 证明： ① ? ? x(F (x) ? H (x)) ② ? x (? F (x) ? ? H (x))) ③ ? F (y) ? ? H (y) ④ ? x(G (x) ? H (x)) 前提引入 ①置换 ②UI ④UI ⑤ G (y) ? H (y) ⑥ H (y) ? ? F (y) ⑦ G (y) ? ? F (y) ⑧ ? x(G (x) ? ? F (x)) 前提引入 ③置换 ⑤⑥假言三段论 ⑦UG 离散数学 (2) 前提：? xF(x) ? ? xG(x) 结论：? x(F(x) ? G(x)) 三、推理证明（续） 证明： ① ? ? x(F (x) ? G (x)) ② ? x(F (x) ? ? G (x)) ③ F (c) ? ? G (c) ④ F (c) 否定结论引入 ①置换 ②EI ④EG ⑤ ? xF (x) ⑥ ? xF (x) ? ? xG (x) ⑦ ? xG (x) ⑧ G (c) ③化简 前提引入 ⑤⑥假言推理 ⑦UI ③化简 ⑨ ? G (c) ⑧⑨合取 ⑩ G (