[理学]第1章 命题逻辑11-12.ppt

* 合式公式 定义 合式公式 (命题公式, 公式) ： (1) 单个命题常项或变项 p,q,r,…, pi ,qi ,ri ,…,0,1是合式公式 (2) 若A是合式公式，则 (?A)也是合式公式 (3) 若A, B是合式公式，则(A?B), (A?B), (A?B), (A?B)也是合式公式 (4) 只有有限次地应用(1)~(3)形成的符号串才是合式公式 * 合式公式的层次 (1) 若公式A是单个的命题变项, 则称A为0层公式. (2) 称A是n+1(n≥0)层公式是指下面情况之一： (a) A=?B, B是n层公式； (b) A=B?C, 其中B,C分别为i层和j层公式，且 n=max(i, j)； (c) A=B?C, 其中B,C的层次及n同(b)； (d) A=B?C, 其中B,C的层次及n同(b)； (e) A=B?C, 其中B,C的层次及n同(b). * 合式公式的层次 (续) 例如 公式 p 0层 ?p 1层 ?p?q 2层 ?(p?q)?r 3层 ((?p?q) ?r)?(?r?s) 4层 * 公式的赋值 定义: 给公式A中命题变项 p1, p2, … , pn指定一组真值称为对A的一个赋值或解释 成真赋值: 使公式为真的赋值 成假赋值: 使公式为假的赋值 * 公式的赋值(续) 赋值?=?1?2…?n之间不加标点符号，?i=0或1. A中仅出现 p1, p2, …, pn，给A赋值?1?2…?n是指 p1=?1, p2=?2, …, pn=?n 例：A=(p?q) ?r 110、111、011、010 含n个变项的公式有2n个赋值. * 真值表 真值表: 公式A在所有赋值下的取值情况列成的表 例 A= (q?p) ?q?p 的真值表 p q q?p (q?p) ?q (q?p) ?q?p 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 * 例 B = ? (?p?q) ?q 的真值表 p q ?p ?p?q ? (?p?q) ? (?p?q) ?q 0 0 0 1 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 真值表例子 * 例 C = (p?q) ??r 的真值表 p q r p?q ?r (p?q)??r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 真值表例子 * 公式的类型 定义 设A为一个命题公式 (1) 若A无成假赋值，则称A为重言式(也称永真式) (2) 若A无成真赋值，则称A为矛盾式(也称永假式) (3) 若A不是矛盾式，则称A为可满足式 注意：重言式是可满足式，但反之不真. A为重言式， A= (q?p)?q?p B为矛盾式， B =?(?p?q)?q C为可满足式 C= (p?q)??r 余力理工配楼303A buaayuli@ruc.edu.cn * 定位 程序 = 算法 + 数据结构 算法 = 逻辑 + 控制 逻辑是所有学科的基础 离散数学是数学哲学 * 学习方法 听课 做练习 阅读文献 实践研究 * 主要内容 数理逻辑 集合论 代数结构 图论（不讲） 组合分析初步 形式语言和自动机初步 * 教材与教学参考书 教材： 耿素云、屈婉玲、张立昂，离散数学（第四版），清华大学出版社, 2008. 教学参考书： 屈婉玲、耿素云、张立昂，离散数学题解（修订版），清华大学出版社，2004. * 数理逻辑部分 第1章 命题逻辑 第2章 一阶逻辑 * 第1章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 联结词全功能集 1.5 对偶与