第一章数理逻辑-谓词演算.ppt

习题课 主要内容 个体词①个体常项②个体变项③个体域④全总个体域? 谓词①谓词常项②谓词变项③n(n≥1)元谓词④特性谓词? 量词①全称量词②存在量词? 一阶逻辑中命题符号化? 一阶逻辑公式①原子公式②合式公式（或公式）③闭式解释 一阶逻辑公式的分类①逻辑有效式（或永真式）②矛盾式（或永假式）③可满足式 等值式与基本的等值式①在有限个体域中消去量词等值式②量词否定等值式③量词辖域收缩与扩张等值式④量词分配等值式? 基本规则①置换规则②换名规则③代替规则? 前束范式? 推理理论①推理的形式结构②推理正确③构造证明④新的推理规则全称指定规则，记为US存在指定规则，记为ES 全称推广规则，记为UG存在推广规则，记为EG? 典型习题 一、在谓词逻辑中将下列命题符号化：??? 1.没有一个自然数大于等于任何自然数。??? ??? 解：设N(x)：x是自然数，???????? G(x，y)：x≥y，??????? 则命题可符号化为：?????? ??x(N(x)??y(N(y)?G(x，y)) 2.有唯一的偶素数。???? 解： 设Q(x)：x是偶数，????????? P(x)：x是素数，????????? E(x，y)：x=y，???????? 则命题可符号化为：???????? ?!x(Q(x)?P(x)) ??或 ?x(Q(x)?P(x)???y(?E(x,y)?Q(y)?P(y))  3.每个人都有自己喜欢的职业。???? 解：设M(x)：x是人，?????????? P(y)：y是职业，?????????? L(x，y)：x喜欢y，????????? 则命题可符号化为：????????? ?x(M(x)??y(P(y)?L(x，y))) 4.只有总经理才有秘书。 二、证明下列等值式? ??? ?x(F(x)→G(x)) ? ?x(F(x)∧ ?G(x))? ? ?x(F(x)→G(x)) ? ?x?(F(x)→G(x)) （量词否定等值式） ? ? x ?(? F(x)∨G(x)) （蕴涵等值式） ? ? x(F(x)∧?G(x)) （德.摩根律） 三、构造下面推理的证明 前提： ? x(F(x)→(G(a)∧R(x)), ?xF(x)??????? 结论： ?x(F(x)∧R(x)) 证明： ① ?xF(x) 前提引入 ② F(c) ①ES ③ ?x(F(x)→(G(a)∧R(x)) 前提引入 ④ F(c)→(G(a)∧R(c)) ③US ⑤ G(a)∧R(c) ②④假言推理 ⑥ R(c) ⑤化简 ⑦ F(c)∧R(c) ②⑥合取 ⑧ ? x(F(x)∧R(x)) ⑦EG 注意：在此证明中，要先消去存在量词。 四、在一阶逻辑自然推理系统F中构造下面推理的证明? ??1、所有的人或者是吃素的或者是吃荤的，吃素的常吃豆制品，因而不吃豆制品的人是吃荤的。（个体域为人的集合）。 分析：由于个体域为人类集合，所以不用引入特性谓词， 令F(x)：x是吃素的，G(x)：x是吃荤的， H(x)：x吃豆制品。 前提： ?x(F(x)∨G(x))， ?x(F(x)→H(x)) 结论： ?x(┐H(x)→G(x)) 证明： ① ?x(F(x)∨G(x)) 前提引入 ② F(y)∨G(y) ①US ③ ┐F(y)→G(y) ②置换 ④ ?x(F(x)→H(x)) 前提引入 ⑤ F(y)→H(y) ④US ⑥ ┐F(y)∨H(y) ⑤置换 ⑦ ┐H(y)→┐F(y) ⑥置换