13年数理逻辑总复习.ppt

* * * * * * * 数理逻辑总复习 * 第一章 主要内容 命题、真值、简单命题与复合命题、命题符号化 联结词?, ?, ?, ?, ?及复合命题符号化 命题公式及层次 公式的类型 真值表及应用 * 第一章 基本要求 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 会求复合命题的真值 深刻理解合式公式及重言式、矛盾式、可满足式等概念 熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型 * 第二章 主要内容 等值式与等值演算 基本等值式（16组，24个公式） 主析取范式与主合取范式 联结词完备集 消解法 * 第二章 基本要求 深刻理解等值式的概念 牢记基本等值式的名称及它们的内容 熟练地应用基本等值式及置换规则进行等值演算 理解文字、简单析取式、简单合取式、析取范式、合取范式的概念 深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系 * 第二章 基本要求 熟练掌握求主范式的方法（等值演算、真值表等） 会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值 会将公式等值地化成指定联结词完备集中的公式 会用命题逻辑的概念及运算解决简单的应用问题 掌握消解规则及其性质 会用消解算法判断公式的可满足性 * 第三章 主要内容 推理的形式结构 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系统P 构造推理证明的方法 直接证明法 附加前提证明法 归谬法(反证法) * 第三章 基本要求 理解并记住推理形式结构的两种形式： 1. (A1?A2?…?Ak)?B 2. 前提：A1, A2, … , Ak 结论：B 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等） 牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬法 会解决实际中的简单推理问题 * 第四章 主要内容 个体词、谓词、量词 一阶逻辑命题符号化 一阶语言L：项、原子公式、合式公式 公式的解释 量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释 公式的类型 永真式(逻辑有效式)、矛盾式(永假式)、可满足式 * 第四章 基本要求 准确地将给定命题符号化 理解一阶语言的概念 深刻理解一阶语言的解释 熟练地给出公式的解释 记住闭式的性质并能应用它 深刻理解永真式、矛盾式、可满足式的概念, 会判断简单公式的类型 * 第五章 主要内容 一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则 前束范式 推理的形式结构 自然推理系统NL 推理定律、推理规则 * 第五章 基本要求 深刻理解并牢记一阶逻辑中的重要等值式, 并能准确而熟练地应用它们． 熟练正确地使用置换规则、换名规则、代替规则． 熟练地求出给定公式的前束范式． 深刻理解自然推理系统NL 的定义，牢记NL 中的各条推理规则，特别是注意使用??、?+、?+、?? 4条推理规则的条件． 能正确地给出有效推理的证明． * of 8 练习1：符号化练习（红色为p，蓝色为q） 这个工作要求有C++或Java的开发经验。 本饭店午餐免费赠送汤或沙拉。 考试想要得高分，把这本习题集做完就够了。 必须走500米才能登上香山山顶。 只有你购买的手机没有超过一年，你的包修单才有效。 在电脑上登陆必须有一个有效的口令。 如果你经常玩电子游戏，你的视力会衰退，反之亦然。 p ? q (?p ? q) ? (p ? ?q) q ? p q ? p q ? p p ? q q ? p * of 8 练习1（续） a) 假如上午不下雨，我去看电影；否则就在家里读书或看报。 p:上午下雨。 q: 我去看电影。 r:我在家读书。 r: 我在家看报。 b)我今天去打球，除非下雨。 p:我今天去打球。 q: 今天下雨。 c)仅当你走，我将留下。 p:你走。 q: 我留下。 (?p?q)?(p?(r?s)) ?q?p q?p * 练习1（续） 符号化下列命题 1）每一个人的外祖父都是他母亲的父亲. P(x):x是人，O(x,y):x是y的外祖父 F(x,y):x是y的父亲，M(x,y):x是y的母亲 2）不管白猫黑猫，抓住老鼠就是好猫. C(x):x是猫，W(x):x是白色的，B(x):x是黑色的 G(x):x是好的，M(x):x是老鼠，K(x,y):x抓住y ?x?y (P(x) ? O(y,x)??z(M(z,x) ? F(y,z))) ?x?y(C(x)?(W(x)?B(x))?M(y)?K(x,y)?G(x)) * 练习1（续） 3）在实数集中，任給一正实数，都存在大于该实数的实数。 R(x)