数理逻辑-命题逻辑.ppt.ppt

数理逻辑 南京师范大学泰州学院哲学系 绪论 数理逻辑数理逻辑的产生与发展数理逻辑的研究内容预备知识 集合的基本知识 序偶与笛卡儿积 映射等 数理逻辑是思维科学的一个分支 也是数学的一个分支 由于具有强有力的形式表达和形式分析的功能 数理逻辑在哲学 语言学 经济学 计算机科学 人工智能 决策学等多领域的现代发展中 得到了广泛的实质性的运用 熟悉和掌握数理逻辑基础 已成为当代人文 社会科学工作者应当具备的一种知识结构和素养 它是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科 它起源于公元十七世纪 十九世纪英国的德 摩根和乔治 布尔发展了逻辑代数 二十世纪三十年代数理逻辑进入了成熟时期 基本内容 命题逻辑和谓词逻辑 有了明确的理论基础 成为数学的一个重要分支 同时也是电子元件设计和性质分析的工具 冯 诺意曼 图灵 克林 等人研究了逻辑与计算的关系 基于理论研究和实践 随着1946年第一台通用电子数字计算机的诞生和近代科学的发展 计算技术中提出了大量的逻辑问题 逻辑程序设计语言的研制 更促进了数理逻辑的发展 除古典二值 真 假 逻辑外 还研究了多值逻辑 模态逻辑 概率逻辑 模糊逻辑 非单调逻辑等 不仅有演绎逻辑 也还有归纳逻辑 计算机科学中还专门研究计算逻辑 程序逻辑 时序逻辑等 现代数理逻辑分为四论 证明论 递归论 模型论 公理化集合论 第一节 数理逻辑的定义 发展 研究内容1 数理逻辑的定义 数理逻辑又称符号逻辑 它是数学的一个分支 是用数学方法研究逻辑或形式逻辑的学科 其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统 数理逻辑是数学基础的一个不可缺少的组成部分 简言之 用数学的方法研究关于推理 证明等问题的学科就叫做数理逻辑 广义理解 用数学方法研究演绎规律的学科 狭义理解 用数学方法研究数学中演绎规律和数学基础的学科 2 数理逻辑的产生和发展 1 利用计算的方法来代替人们思维中的逻辑推理过程 这种想法早在十七世纪就有人提出过 莱布尼茨就曾经设想过能不能创造一种 通用的科学语言 可以把推理过程象数学一样利用公式来进行计算 从而得出正确的结论 由于当时的社会条件 他的想法并没有实现 但是它的思想却是现代数理逻辑部分内容的萌芽 从这个意义上讲 莱布尼茨可以说是数理逻辑的先驱 2 1847年 英国数学家布尔发表了 逻辑的数学分析 建立了 布尔代数 并创造一套符号系统 利用符号来表示逻辑中的各种概念 布尔建立了一系列的运算法则 利用代数的方法研究逻辑问题 初步奠定了数理逻辑的基础 3 十九世纪末二十世纪初 数理逻辑有了比较大的发展 1884年 德国数学家弗雷格出版了 数论的基础 一书 在书中引入量词的符号 使得数理逻辑的符号系统更加完备 对建立这门学科做出贡献的 还有美国人皮尔斯 他也在著作中引入了逻辑符号 从而使现代数理逻辑最基本的理论基础逐步形成 成为一门独立的学科 1910到1913年出版的罗素 怀特海合著的 数学原理 是这门学科兴起的标志 4 随着数理逻辑的发展 到20世纪30年代 数理逻辑已完全成熟 数理逻辑的分支得到了迅速的发展 如 集合论 证明论 递归论 模型论 等 数理逻辑之所以发展这么迅速 主要原因是这门学科对于数学其它分支如集合论 数论 代数 拓扑学等的发展有重大的影响 特别是对新近形成的计算机科学的发展起了推动作用 反过来 其他学科的发展也推动了数理逻辑的发展 3 数理逻辑研究的主要内容 数理逻辑最基本的也是最重要的组成部分 就是 命题演算 和 谓词演算 1 命题演算是研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法 2 谓词演算也叫做命题涵项演算 在谓词演算里 把命题的内部结构分析成具有主词和谓词的逻辑形式 由命题涵项 逻辑连接词和量词构成命题 然后研究这样的命题之间的逻辑推理关系 4 数理逻辑与传统逻辑的区别 第一 传统逻辑与现代逻辑的研究对象不完全相同 有些内容如类比与假说 是传统逻辑的研究内容 但现代逻辑尚未展开这些方面的全面研究 现代逻辑研究的许多内容则是传统逻辑没有研究甚至也没有能力去研究的 比如 一个公理系统的完全性与无矛盾性 第二 传统逻辑与现代逻辑在人们的实践中所起的认识作用有些区别 传统逻辑是一般思维中的便利工具 它对实际思维中常见的思维形式类型 主要是推理 加以分析 研究 这种研究的理论成果 在规范 导引人们进行符合逻辑的思维方面发挥着重要作用 而现代逻辑是数学研究中的有用工具 它运用一些数学方法对思维形式类型进行研究 这种研究的成果对数学 计算机科学 人工智能等科学的发展有重要意义 第三 传统逻辑和现代逻辑所使用的工具语言不同 传统逻辑的研究主要运用自然语言 因为自然语言本身具有模糊 歧义性等特点 使得传统逻辑在理论上有某些缺陷 比如不能准确地处理关系命题 必须预设命题的主项和谓项所指称的对象存在等等 但自然语言同我们的日常经验比较接近 因此 传统逻辑在日常生活的应用上较之现代逻辑更为广泛 现代逻辑则主要运用人工语言 通过建立形式系统以实现对思维形式的研究 人工语言和数学方法的运用使得现代逻辑较之传统逻辑更为精确 研究的内容也更为深刻 当然 这也使得现代逻辑更为抽象而远离人们的日常经验 5 数理逻辑的主要特点 1 使用一整套符号语言 从而简化了推理形式 数理逻辑使用一套专门的符号来处理各种思维形式 完全消除了自然语言的含混性 摆脱了自然语言的局限 2 数理逻辑借助人工符号语言 使整个推理形式化 3 数理逻辑同逻辑学其他分支相比较 它的主要特点是系统性 它通过符号把把思维的各种逻辑形式联系起来 组成一个完整的系统 它研究各种系统的逻辑发展过程 也研究系统之间的相互关联 第二节 预备知识 一 集合概念及其表示1 集合的基本概念所谓集合 就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体 组成集合的各个对象 称为这个集合的元素或成员 例1指出以下叙述中哪些是集合 哪些不是集合 1 中国人的集合 2 百货商店里好看的花布的集合 3 1000以内的素数的集合 4 26个英文字母组成的集合 5 这个班里高个子学生的集合 6 直线y 2x 5上的点的集合 解 1 3 4 6 是集合 2 不是集合 因为对每一种布 没有确定的标准说它是 好看 还是 不好看 5 也不是集合 因为在 高个子 与 不是高个子 之间没有明确的界限 但是 如果我们给出一个完全确定的标准 如身高大于1 80米 合乎这个标准的算是 高个子 否则不算 那么对于这个班里的每一个学生 总可以明确地断定是否合乎这个标准 这时 这个班里高个子学生 就构成一个集合 集合及其表示 通常 用大写字母a b c 表示集合 用小写字母a b c 表示元素 用如下的字母表示常用的集合 n 自然数的集合 包含0 nm 小于m的自然数集合 即 0 1 m 1 i 整数的集合 i 正整数的集合 i 负整数的集合 r 实数的集合 r 正实数的集合 r 负实数的集合 q 有理数的集合 c 复数的集合 设a为任一个对象 a为任意一个集合 则在a和a之间有且仅有以下两种情况中的一个出现 a为a的元素 记作 a a 并称为 a属于a 或 a含有a a不为a的元素 记作 a a 并称 a不属于a 当a1 a a2 a an a时 常简写为a1 a2 an a 2 集合的表示方法1 列举法这种方法是将集合中的元素一一列举出来 或者列出足够多的元素以反映集合中成员的特征 并用花括号将元素括起来 其表示形如a a1 a2 an 或a a1 a2 a3 例如 a a b c d x y z b 0 1 2 3 4 5 6 7 8 9 就是用列举法表示的集合 2 描述法这种方法是用一个条件来描述集合中元素具有的共同性质 这个条件可以是一句话或一个或多个表达方式 其表示形式如a x p x 或a x p x 其中p x 表示 x满足性质p 或 x具有性质p 例如 前面列出的常用集合n和nm 可以用列举法分别表示为n n n是自然数 nm n n n且0 n m 例2设全集合是整数集i 试用列举法表示集合a x x 10 x 24 0且 5 x 6 解a 1 0 1 2 3 4 5 6 二 特殊的集合1 空集定义3 1 3 不含任何元素的集合称为空集 记作 x p x p x 例如 x x x2 1 0 x r 是空集 注意 空集是任意集合的子集 2 全集定义3 1 4 在一定范围内 如果所有集合均是某一集合的子集 则称该集合为全集 记作e e x p x p x 3 幂集定义 给定集合a 由a的所有子集为元素组成的集合称为a的幂集 记作 a 或2a从定义中可看出 集合a的幂集实际上是以a的所有子集为元素组成的集合 例4 5求下列集合的幂集 1 a 2 b 3 c 4 d a b c 解 1 p a 2 p b 3 p c 4 p d a b c a b a c b c a b c 三 集合的关系相等 外延性公理 两个集合是相等的 当且仅当它们有相同的成员 两个集合a和b相等 记作a b 两个集合不相等 记作a b 0 1 x x x2 2x 1 0 x i 0 1 1 2 两个集合a和b相等当且仅当它们具有相同的元素 即对任意集合a b a b x x a x b 外延公理 子集的定义 设a b是任意两个集合 如果a的每一个元素都是b的元素 则称集合a是集合b的子集合 或子集 subsets 或称a包含在b内 记为a b 或称b包含a 记为b a 即a b x x a x b 设a b c为任意集合 根据定义 显然有 包含关系具有自反性 a a包含关系具有传递性 若a b且b c 则a c 注 可能a b或b a 也可能两者均不成立 不是两者必居其一 定理设a b和c为任意三个集合 则有 1 a 2 a a 3 若a b且b c 则a c 4 若a b且b c 则a c 例如设a a b c b a b c d c a b 则a b c a c b a c b a b c d e f g h i j 练习设a a b c a a b 试指出下列论断是否正确 1 a a 8 b a 2 a a 9 a b a 3 a a 10 a b a 4 a 11 c a 5 a 12 c a 6 b a 13 c a 7 b a 14 a b c a 例4 3列出集合a 1 2 的全部子集 解因为 是任何集合的子集 所以 是a的子集 由a中任意一个元素所组成的集合是a的子集 所以 1 和 2 是a的子集 由a中任意两个元素所组成的集合是a的子集 所以 1 2 是a的子集 因为a中只有两个元素 故a再没有其他的子集 由上可知 a有四个子集 1 2 1 2 例4 4设有集合a b c和d 下述论断是否正确 说明理由 1 若a b b c 则a c解正确 因为b c 所以集合b的每一个元素也是集合c的元素 由a b知a是b的一个元素 因此a也是c的一个元素 故a c 2 若a b b c 则a c解错误 举反例如下 设a a b a b c a b c 显然a b b c 但a不是c的子集 因为a a 但a c 四 集合的运算及其性质 要求 1 掌握如下概念 交集 并集 补集等概念 2 熟练掌握集合运算定律 会使用运算定律证明两个集合相等 一 集合的运算1 交集 定义 设任意两个集合a和b 由a和b的所有共同元素组成的集合 称为a和b的交集 记为a b a b x x a x b 文氏图 例1 a 0 2 4 6 8 10 12 b 1 2 3 4 5 6 a b 2 4 6 例2 设a是平面上所有矩形的集合 b是平面上所有菱形的集合 a b是所有正方形的集合 例3 设a是所有能被k整除的整数的集合 b是所有能被l整除的整数的集合 a b是所有能被k与l最小公倍数整除的整数的集合 性质 a a a ab a c a e ad a b b ae a b c a b c f a b a a b b 例题4 设a b 求证a c b c 证明 对任一x a c 则x a且x c 因为有若x a 则x b 所以x b且x c 故x b c 因此a c b c 2 并集定义3 2 2 设任意两个集合a和b 所有属于a或属于b的元素组成的集合 称为a和b的并集 记作a b a b x x a x b 文氏图 例1 a 1 2 3 4 b 2 4 5 a b 1 2 3 4 5 例2 设a是奇数集合 b是偶数集合 a b是整数集合 a b 性质 a a a ab a e ec a ad a b b ae a b c a b c f a a b b a b 例题3 设a b c d 求证a c b d 证明 对任一x a c 则x a或x c 若x a 则x b 故x b d 若x c 则x d 故x b d 因此a c b d 定理3 2 1设a b c为三个集合 则下列分配律成立 a a b c a b a c b a b c a b a c 证明 a 设s a b c t a b a c 若x s 则x a且x b c 即x a且x b或x a且x c x a b或x a c即x t 所以s t 反之 若x t 则x a b或x a c x a且x b或x a且x c 即x a且x b c 于是x s 所以t s 因此 s t b 证明完全与a 类似 定理3 2 2设a b为任意两个集合 则下列吸收律成立 a a a b ab a a b a 证明 a a a b a e a b a e b a e ab a a b a a a b a a b a 定理3 2 3a b 当且仅当a b b或a b a 证明 若a b 对任意x a必有x b 对任意x a b 则x a或x b 即x b 所以a b b 又b a b 因此得到a b b 反之 若a b b 因为a a b 所以a b 同理可证得a b a 3 差集 补集定义3 2 3 设a b是任意两个集合 所有属于a而不属于b的元素组成的集合称为b对a的补集 或相对补 或a和b差集 记作a b a b x x a x b 文氏图 定义3 2 4 设e为全集 任一集合a关于e的补 称为a的绝对补 记作 a a e a x x e x a 文氏图 性质 a a ab e c ed a a ee a a 定理3 2 4设a b为任意两个集合 则下列关系式成立 a a b a bb a b a b定理3 2 5设a b为任意两个集合 则下列关系式成立 a a b a bb a b a a b 定理3 2 6设a b c为三个集合 则a b c a b a c 定理3 2 7设a b为任意两个集合 若a b 则a b ab b a a b 五 序偶与笛卡尔积 要求 了解有序n元组 笛卡尔积 一 有序n元组1 序偶 有序2元组 两个具有固定次序的客体组成一个序偶 有序2元组 记作 其中x是它的第一元素 y是它的第二元素 例 平面直角坐标系中的一个点的坐标就构成为一个有序序偶 我们可用表示 注 序偶是讲究次序的 例和是表示平面上两个不同的点 这与集合不同 1 3 和 3 1 是两个相等的集合 2 定义3 4 1 两个序偶相等 当且仅当x u且y v 3 有序 元组 是一个序偶 其第一元素本身也是一个序偶 表示为 z 或 4 有序n元组 有序n元组也是一个序偶 其第一元素是一个n 1元组 xn 通常简记为 其中xi称作它的第i坐标 i 1 2 n 的充要条件是xi yi i 1 2 n 序偶其元素可以分别属于不同的集合 因此任给两个集合a和b 我们可以定义一种序偶的集合 二 笛卡尔积1 定义3 4 2 设a和b是任意两个集合 由a中元素作第一元素 b中元素作第二元素构成序偶 所有这样序偶的集合称集合a和b的笛卡尔积或直积 记作a b 即a b x a y b 例题若a b 1 2 3 求a b b a a a b b以及 a b b a 解 a b b a a a b b a b b a 若a b均是有限集 a m b n 则 a b m n 2 n个集合的笛卡尔积 集合a1 a2 an 则特别地 约定 若a 或b 则a b b a 4 映射 在数学及相关的领域经常等同于函数 设a和b是两个集合 如果按照某种对应关系f 对于集合a中的任何一个元素 在集合b中都存在唯一的一个元素与之对应 那么 这样的对应 包括集合a b 以及集合a到集合b的对应关系f 叫做集合a到集合b的映射 mapping 记作f a b 单射 指将不同的变量映像到不同的值的函数 也就是说 对于任意x1 x2 a 并且x1 x2 则f x1 f x2 满射 指集合b等于值域的函数 即 对集合b中任意元素 都存在至少一个定义域中的元素与之对应 也就是说 ran f b 双射 也称一一对应 既是单射又是满射的函数 直观地说 一个双射函数形成一个对应 并且每一个输入值都有正好一个输出值以及每一个输出值都有正好一个输入值 雙射 單射與滿射 單射但非滿射滿射但非單射非滿射非單射 5 等势 如果存在a到b的双射 则a和b是等势的 基数 所有等势的集合所确定的数 称为基数 记为 a 有穷集和无穷集 如果存在自然数n 使得 a n 就称为有穷集 否则就称为无穷集 自然数集是我们遇到的第一个无穷集 它的基数我们用w0表示 如果a为有穷集或 a w0 则称a为可数集 否则a为不可数集 二 能行方法 这一方法是由有穷多条有穷长的指令组成 每一步做什么取决于这些指令或者再加上一步操作所得的结果 并且按此方法能在有穷步内结束求解过程 并给出确定的答案 能行可判定 如果一个问题存在上述这样一种能行方法去求解 则称该问题是能行可判定的 参考书目 1 莫绍揆 数理逻辑初步 上海 上海人民出版社 1980年版 2 王宪钧 数理逻辑引论 北京 北京大学出版社1982年版3 胡世华等 数理逻辑基础 北京 科学出版社1982年版 4 a g 汉密尔顿 数理逻辑 汉译本 朱水林译 上海 华东师范大学出版社1986年版 5 美 i m 科庇 符号逻辑 宋文坚等译 北京 北京大学出版社1988年版 6 张家龙 数理逻辑发展史 从莱布尼茨到哥德尔 北京 社会科学文献出版社1993年版 7 陈慕泽 数理逻辑教程 上海 上海人民出版社2001年版8 毕富生 数理逻辑 北京 高等教育出版社2004年版9 李小五 现代逻辑讲义 广州 中山大学出版社2005年版 10 邢滔滔 数理逻辑 北京 北京大学出版社2008年版11 徐明 符号逻辑讲义 武汉 武汉大学出版社2008年版 12刘壮虎 素朴集合论 北京 北京大学出版社2001年版 第一章 命题逻辑 第一节 原子命题与复合命题一 命题及其真值 1 命题逻辑 propositionlogic 它是以命题为基本逻辑形式的逻辑学的基础组成部分 与 词项逻辑 相对 也就是说 在考查和研究命题时 只把一个命题分析到其中所含命题成分为止 即把简单命题作为整体来考察 不把一个简单命题再分析为非命题成分的结合 不把个体词 谓词和量词等非命题成分分析出来 可以更进一步地说 由简单命题 原子命题 出发 通过使用命题联结词构成复合命题 然后研究复合命题的逻辑形式以及符合命题之间的推理关系 比如 p q p q 2 命题逻辑的发展历史 1 古希腊 亚里士多德 在他的逻辑研究体系中 已涉及到一些命题逻辑的基本内容 如命题的概念 命题的真假 命题联结词 命题之间的关系等 斯多亚学派 他们对命题逻辑作了深入的研究 比较系统地建立起了命题逻辑理论 对构成命题的算子 联结词 作了非常准确的分析 也有了正确的真值表观念 特别对蕴涵的意义进行了极其复杂的讨论 他们的命题逻辑的某些方面是公理化的 并且还对规律和元定理作出了区分 2 中世纪 中世纪的逻辑学家对命题逻辑作出了杰出的贡献 如西班牙的彼得 逻辑大全 威廉 奥康等都对逻辑的发展作出了重要贡献 他们构造两套命题逻辑系统 简单蕴涵系统和当下蕴涵系统 把斯多亚学派的命题逻辑推进了一步 3 十九世纪中叶 1879年 弗雷格才第一个建立了初步自足的命题逻辑公理系统 即命题演算 在这个系统中 他用了否定和蕴涵两个初始联结词 并且它有六条公理 如果我们用p q r来表示命题变元 就可以写成 p q p p q r p q p r p q r q p r p q q p p p p p其中第三个公理可以从第一 第二个公理推导出 最后三个公理可以用 p q p q 代替 因此 简化后的公理系统只有三条公理 这个公理系统为许多现代逻辑学家所采用 3 1 命题的涵义 简单来说 就是有真假的语句 即通过肯定或否定对事物作出某种陈述的语句 如 水银是液体 和 水银不是液体 这两个语句就是真假的 它们分别直接表达了两个相应的判断 因而都是命题 凡不表达判断的语句 都不是命题 2 命题的真值 就是指命题的真或假 4 原子命题和复合命题 1 原子命题 是数理逻辑中的基本概念 是在指在结构上不能分解出其他命题的命题 如 所有的牛都是动物 有的罪犯不是杀人犯 注意 原子命题是由词项结合而成 它包括个体词和谓词两个部分 即由指称个体的词和表示一个个体的性质或表示两个及两个以上个体之间关系的词所构成 2 复合命题 就是指在自身中包含了其他命题的命题 亦即以其他命题作为其构成要素的命题 它是由逻辑联结词和支命题所组成 逻辑联结词 就是在复合命题中联结各支命题 表明支命题之间逻辑关系的词项 它决定了复合命题的逻辑性质 复合命题的真假 决定于它的支命题之间的联系是否符合逻辑联结词的涵义所规定的联系 支命题 就是复合命题中所包含的命题 一般说来 支命题是简单命题 但是并不都是简单命题 也可以是复合命题 如 革命或迟或早总将发生 并将必然取得胜利 第二节 真值联结词与真值形式 一 真值联结词 1 真值联结词 在复合命题中联结各支命题 表明支命题之间逻辑关系的词项 它刻画的是原子命题和由其构成的复合命题之间的真假关系 如 合取 选取 等 2 常用真值联结词的逻辑特征 1 否定词 否定运算 非运算 符号 读作 非 否定 设命题为 则在 的前面加否定词 变成 读做 的否定 或 非 定义 严格由真值表定义 举例 北京是一座城市 北京不是一座城市 每一种生物均是动物 f 有一些生物不是动物 t这里 不能讲成 每一种生物都不是动物 为假命题了 对量化命题的否定 除对动词进行否定外 同时对量化词也要加以否定 2 合取词 合取 积 与 运算 符号 设 为两个命题 则 称 与 的合取 读作 与 与 的合取 并且 等 定义 由真值表给出 真值表如下 当且仅当 和 的真值均为 则 的真值为 否则 其真值为 注意 和 是互为独立的 地位是平等的 和 的位置可以交换而不会影响 的结果 举例 a p 王华的成绩很好q 王华的品德很好 则 王华的成绩很好并且品德很好 b p 我们去种树q 房间里有一台电视机则 我们去种树与房间里有一台电视机 c p 今天下大雨q 3 3 6则 今天下大雨和3 3 6由例 b c 可见 在日常生活中 合取词应用在二个有关系的命题之间 而在逻辑学中 合取词可以用在二个毫不相干的命题之间 d 下列语句不是合取联结词组成的命题 p 王大和王二是亲兄弟 q 他打开箱子然后 而后 拿出一件衣服来 3 析取词 或运算 符号 设 为二个命题 则 称作 与 的 析取 读作 或 定义 由真值表给出 当且仅当 均为 时 为 否则 其真值为 如右图 区分 可兼或 与 不可兼或 异或 排斥或 析取词为可兼或即 p和q均为 t 时 p q 为 t 例如 灯泡有故障或开关有故障 今晚写字或看书 今天下雨或打雷 以上例句均为可兼或 不可兼或 中当p和q均为 t 时 则p异或q为 f 异或用 不相容 表示 例 他通过电视看杂技或到剧场看杂技 他乘火车去北京或乘飞机去北京 以上两句均为不 可兼或 4 蕴涵 符号 读作 如果 则 蕴含 为二个命题 为新的命题 读作 如果 则 蕴含 仅当 当且 是 的充分条件 定义 由真值表定义 当 为 为 时 则 为 否则 均为 称为前件 条件 前提 假设 称为后件 结论 举例 a p 我拿起一本书q 我一口气读完了这本书p q 如果我拿起一本书 则我一口气读完了这本书 b p 月亮出来了q 3 3 9p q 如果月亮出来了 则3 3 9 通常称 a 为形式条件命题 前提和结果有某种形式和内容上的联系 b 为实质条件命题 前提和结果可以有联系 也可以没有联系 只要满足单条件命题的定义 所以 是形式条件命题一定是实质条件命题 反之不一定 是实质条件命题 例 我买到了鱼 我吃鱼 如果我买到了鱼 则我吃鱼 但 如果我没买到鱼 则我吃鱼 这在日常生活中是不可能的 但在单条件命题的定义中是允许的 可以证明 q p原命题逆反命题 逆命题反命题列出真值表 由真值表得 原命题 逆反命题 逆命题 反命题 5 等值 符号 设 为二个命题 则 读作 当且仅当 等价 是 的充分必要条件 定义 见真值表 每当 和 的真值相同时 则 的真值为 否则 的真值为 举例 a 设 abc是等腰三角形 abc有两只角相等 abc是等腰三角形当且仅当 abc中有两只角相等 b 下面均为等价联结词 春天来了当且仅当燕子飞回来了 平面上二直线平行 当且仅当这二直线不相交 当且仅当雪是白色的 中 的地位是平等的 交换位置不会改变真值表中的值 当且仅当 仅当 当且 3 命题联结词在使用中的优先级 先括号内 后括号外 运算时联结词的优先次序为 由高到低 联结词按从左到右的次序进行运算例 可省去括号因为 运算是可结合的 可省去括号因为符合上述规定而 中的括号不能省去 因为 不满足结 最外层的括号一律均可省去 可写成 4 命题联结词小结 五个联结词的含义与日常生活中的联结词的含义大致相同 或 可分为可兼或 和异或 不可兼或 3 除 为一元运算外 其余四个均为二元运算 4 分为形式条件和实质条件命题 当前件为 时 不论后件怎样 则单条件命题的真值均为 5 命题联结词是命题或命题之间的联结词 而不是名词之间 数字之间和动词之间的联结词 二 真值形式 约定 我们只注意命题的真假值 而不再去注意命题的汉语意义 对命题联结词 我们只注意真值表的定义 而不注意它日常生活中的含义 1 真值形式 又称之为 命题公式 命题常元 表示确定的命题 t f 命题变元 以真假为其变域之变元 或没有指定真值的命题 常用大写英文字母 表示 真值形式 由命题变元 常元 联结词 括号 以规定的格式联结起来的字符串 定义 命题公式可按下述法则来生成 孤立的命题变元是一个命题公式 若 是命题公式 也为命题公式 若 是命题公式 则 均为命题公式 2 复合命题的真值形式 数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算 为此 首先要把推理所涉及到的各命题符号化 把用自然语言表达的复合命题翻译成相应真值形式的步骤 第一 确定复合命题所包含的所有不同的原子命题 第二 用同一命题变项表示所有相同的原子命题 用不同的命题变项分别表示所有不同的原子命题 一般用小写字母p q r s s 来表示 第三 确定复合命题所断定支命题之间的逻辑关系 并用相应的真值联结词加以表达 第四 依据确定的层次 写出整个复合命题真值形式 如 如果天气晴朗 那么我们去逛动物园 首先 我们用p来表示天气晴朗 用q来表示我们去逛动物园这个原子命题 然后 用假言这个真值联结词把这两个原子命题联结起来 因此 这个假言命题的真值形式是 p q 例 写出下列复合命题的真值形式 1 李明是计算机系的学生 他住在312室或313室 2 虽然交通堵塞 但是老王还是准时到达了车站 3 只有一个角是直角的三角形才是直角三角形 4 老王或小李中有一个去上海出差 解 1 首先用字母表示简单命题 p 李明是计算机系的学生 q 李明住在312室 r 李明住在313室 该命题符号化为 p q r 2 首先用字母表示简单命题 p 交通堵塞 q 老王准时到达了车站 该命题符号化为 p q 3 首先用字母表示简单命题 p 三角形的一个角是直角 q 三角形是直角三角形 该命题符号化为 p q 4 首先用字母表示简单命题 p 老王去上海出差 q 小李去上海出差 该命题符号化为 p q也可符号化为 p q p q 或者 p q p q 2 命题推理及其真值形式 1 命题推理 简单地说就是根据某些规则从一个命题或几个命题得出一个或几个命题的思维过程和思维活动 比如 如果某人是杀人犯 那么他一定去过犯罪现场 这个人没去过犯罪现场那么这个人不是杀人犯2 写出命题推理的真值形式的步骤 第一 分别写出各个前提和结论的真值形式 第二 用合取号把各个前提的真值形式联结起来 所得的合取式 就是前提的真值形式 第三 用蕴涵号把前提和结论的真值形式联结起来 所得的蕴涵式 就是整个命题推理的真值形式 举例 如果上帝不能创造出一块他自己都不能搬动的石头 则他不是万能的 如果上帝能创造出一块他自己都搬不动的石头 则他同样不是万能的 上帝或者能创造出一块自己都不能搬动的石头 或者不能 二者必居其一 因此 上帝不是万能的 我们用p表示上帝能创造出一块他自己都不能搬动的石头 用q表示上帝是万能的 则推理的形式表示如下 p qp qp p q因此这个命题推理的真值形式就可表示为 p q p q p p q 3 真值函数 truthfunction 也叫做 真值函项 所谓真值函数就是指定义域和值域都为真值的函数 也就是说 如果对于一个变元的任意一个允许值 另一变元总有一个确定的值与之对应 那么后者 因变元 就是前者 自变元 的函数 注意 1 任何真值形式都表示一个真值函数 真值形式是真值函数的表现形式 2 真值函数的个数是真值函数中所含的不同命题变元的个数确定 n个命题变元可以有的真假情况是2n个 对于每一个真假情况 又都可以有两种断定 肯定和否定 因此 对于2n中情况 肯定和否定的组合22n个 其中每一个组合是一个真值函数的内容 注意 关于计算当命题变项的数目为n 自然数 时 真值函项种类有多少种 第一 当命题的变项的数目为1时 设命题变项为p 这时p的真值共有两种 真和假 在p的每一种取值下 真值函项的取值各有两种 因此产生不同真值函项的数目有且只有2 2 4 种 第二 当命题变项的数目为2时 设命题变项为p和q 那么p与q组成的所有不同的真值组合共有2 2 22 4 种 即真真 真假 假真 假假四种组合 对于两个变项的每一种真值组合 真值函项的取值又各有两种 因此 当命题变项的数目为2时 所构成不同的真值函项有且只有2 2 2 2 24 222 16 种 第三 当命题变项的数目为3时 设命题变项为p q r 那么p q r所有不同的真值组合共有2 2 2 23 8 种 对于三个变项的每一种真值组合 真值函项的取值又各有两种可能 即 真或假 因此 当命题变项的数目为时 能构成不同的真值函项有且只有2 2 2 2 2 2 2 2 28 223 256 种 第四 依次类推 当命题变项的数目为n时 其中每一个命题变项的取值有且只有两种可能 即真或者假 因此 n个命题变项的不同取值的真值组合为 2 2 2 2 2n 种 对于其中每一种命题变项的真值组合 真值函项的取值又各有两种 由此可推 含有n个命题变项的不同的真值组合函项共有 2 2 2 2 22n 从上述就可以看出 当命题变项的数目确定之后 不同真值函项的个数是完全确定的 有限的 它的真值形式的个数是无限的 一个真值函项可以由不同的真值形式来表示 4 真值联结词的完全性与独立性 真值联结词的完全性 又称真值联结词的完备集 设 是一些命题联结词构成的集合 称 是联结词的完备集 如果对于任意的n元 n 1 真值函数f都可使用只含 中联结词的公式a表达 即a至多含n个命题变元p1p2 pn 且a在任意真值函数t var 0 1 下真值t a 等于f t p1 t p2 t pn 简单地来说 一组真值联结词是完全的 当且仅当由它能定义任一n元真值联结词 真值联结词的独立性 在一组真值联结词中 某个联结词如果不能由该组中其他联结词定义 则称为是独立的 一组真值联结词满足独立性 当且仅当其中每个联结词都是独立的 如 就是满足独立性的一组联结词 5 真值形式的类型 1 一个真值形式是重言式 当且仅当它在其命题变项的任意一组赋值下都真 如p p就是重言式 无论p取任何值 它的值都是真的 另外如p p等都是重言式 在命题逻辑中 重言式是数理专家最感兴趣的 因为它们中的一部分是命题逻辑中的逻辑规律 因此 从思维和形式结构上来讲 我们又可以把重言式分为以下三类 第一类 有些重言式表示了命题逻辑的逻辑规律 例如 p p是命题逻辑中的排中律 p p 表示的是命题逻辑中的不矛盾律 第二类 有一些重言式还可以表示命题逻辑中正确的推理形式 如像这样一种推理形式 p q q p 第三类 还有一些重言式是以等值式出现的 它们又叫做重言等值式 这些等值式也表现了命题逻辑的规律 其中一些对逻辑演算是很重要的 借助这些规律可以形成一些重要的逻辑方法 例如求否定 及范式等 除了以上三类以外 还有一些重言式是和我们的实际思维关系不大的 或者说在我们的思维中一般不会出现以这类重言式为形式的命题和推理 但这些重言式在逻辑中有具有非常重要的作用 如 一些命题演算的公理 定理及在求证定理过程中得到的公式等 2 一真值形式是矛盾式 永假式 当且仅当它在其命题变项的任意一组赋值下都就是假的 比如p p p p 等这些真值形式就是一个矛盾式 从形式上看 如果否定整个重言式 得到的公式就是一个矛盾式 矛盾式是逻辑矛盾的表现形式 3 一个真值形式是满足式 又称之为可真式 当且仅当它在其命题变项的至少一组赋值下为真 如p q p q p q等是可满足式 因此 从上述就可以看出 真值形式可以分为矛盾式和满足式 而满足式又可以分为重言式和非重言式 根据上述的分类 我们可以得出以下结论 第一 一个真值形式a是重言式 当且仅当它的否定 a是矛盾式 第二 一个真值形式a是满足式 当且仅当它的否定 a不是重言式 第三 一个真值形式是不是重言式当且仅当至少在它所含命题变项的一种取值下 其值为假 第四 一个真值形式是不可满足的 当且仅当它的否定是重言式 第五 重言式一定是可满足的 反之不然 第六 不可满足式一定不是重言式 反之不然 第三节 真值形式的判定方法根据上面情况可以得知 重言式是真值形式中最重要的一种 它是逻辑真理的表现形式 各种逻辑规律以及正确的逻辑推理形式等逻辑真理均可表现为重言式 因此 命题逻辑理论的主要内容就是研究重言式的判定和证明方法 数理逻辑的特点在于从有限的公理出发 根据少许的规则 可以推出许多重言式 即正确的推理形式 因此 如何推出重言式 如何判定重言式等问题就成了数理逻辑的重要问题 为此下面就简单介绍一些判定真值形式 也可以说重言式 的方法 这里主要介绍真值表方法 归谬赋值法 范式方法 真值树方法等几种方法 一 重言式的定义 第一种 用真值表验证的真值形式 如果最后一列的每一表值都是真的 那么该真值形式就是重言式 第二种 一个真值形式是重言式 当且仅当用别的命题去替换构成命题的任一原子命题 其结构总是真的 第三种 一个真值形式是重言式 当且仅当对该真值形式中的原子命题赋以任何真值 其结果总是真的 总之 不论所含的命题变项取什么真值 函项的值总是真的真值函项就是重言式 二 真值表方法 1 真值表法 真值表是能显示任何复合判断在它的肢判断的各种真值组合下所取的真值情况的一种数理逻辑图表 真值表方法就是运用真值表来计算和显示复合判断的真值 定义复合判断的逻辑联结词 确定复合判断间的真值关系和判定复合判断的推理形式是否为有效式的一种方法 1 各类真值形式在真值表中的判定方法 在一个公式a的真值表中 由最后一列的值而定 如果一个真值形式是重言式 当且仅当它在其真值表各行中的取值都为真 如果一个真值形式是矛盾式 当且仅当它在其真值表各行中的取值都为假 如果一个真值形式是可真式 当且仅当它在其真值表各行中至少有一行的取值为真 2 构造一个真值形式的真值表的步骤 第一 确定真值形式中有多少个不同的命题变项 第二 列出命题变项的所有不同的取值情况 在这里我们需计算一下n个命题变项所有不同取值情况 2n 第三 相应于命题变项的各组取值 计算出真值形式的真值 第四 作出完整的真值表 第五 判定出真值形式的类型 2 举例 1 用真值表的方法来判断这个真值形式 p q q p 2 用真值表的方法来判定下列命题推理 或者逻辑学难学 或者没有多少学生喜欢它 如果数学容易学 那么逻辑学不难学 因此 如果许多学生喜欢逻辑学 那么数学并不太容易 第一步 写出命题推理的真值形式 设p 逻辑学难学 q 没有多少学生喜欢逻辑 r 数学容易学命题推理的真值形式 p q r p q r 第二步 作出这个命题推理的真值形式的完整的真值表 3 真值表方法的优缺点 优点 它可以能行地判定一个真值形式是重言式 矛盾式 还是协调式 一个真值形式无论多么复杂 我们都可以用真值表方法 判断它是不是一个重言式 真值表的几种作用如下 1 利用真值表判定两个复合判断是否等值 2 利用真值表判定两个复合判断是否为矛盾判断 3 利用真值表判定复合判断推理是否有效 缺点 当真值形式的构造比较复杂 或者所含命题变项的个数比较多时 构造它的真值表就会比较麻烦或者说是不太够简便 因此 当一个真值形式中的命题变项比较多时 就需要找到一种比较简便的判定方法 一般地有两种 一种是简化真值表的方法 也就是我们常说的归谬赋值法 另一种是真值树法 它们都是在真值表方法的基础上发展起来的 三 归谬赋值法 1 归谬赋值法的基本思想 为了判定一真值形式是否为重言式 先假设它不是重言式 即一组赋值使得该真值形式为假 依据这个假设给每个命题变项赋值 如果在赋值过程中 必须给同一命题变项既赋真又赋假 即出现矛盾 这说明假设不成立 即所要判定的真值形式不可能为假 因而是重言式 如果在赋值的过程中没有出现矛盾 也就是说找到一组赋值使该真值形式为假 则该真值形式就不是重言式 2 归谬赋值法的一般步骤为 第一 假设被判定的蕴涵式为假 即 只有蕴涵式的前件真而后件假 蕴涵式才假 第二 从这一假设出发 根据有关真值联结词的真值表 依次对公式中的每一变项进行赋值 第三 检查所有变项的真值 如果其中至少有一个变项的赋值既有真又有假 即出现p p之类的逻辑矛盾 那么根据归谬原则 可以断定该假设不成立 从而证明原公式不可能假 只能为真 因而原公式为重言式 如果变项的赋值没有出现逻辑矛盾 那么就说明该假设成立 因而原公式不是重言式 3 举例 1 用归谬辅值方法判定 p p p是否为重言式 第一步 假设整个蕴涵式为假 第二步 根据假设和充分条件式的逻辑特征可得出 前件为真 后件为假 第三步 后件为假 即p p为假 根据析取命题的逻辑特征可得出 p为假 第四步 前件的p为真 后件的p为假 因而产生矛盾 假设不成立 因此 p p p为重言式 p p pf 假设 tf 由 和 定义 ff 由 和 定义 由 得p真 由 得p假 产生矛盾 所以 p p p为假不成立 因此 p p p为重言式 2 判定此公式是否为重言式 p q r q p r q p q r q p r q f t f t t t f fffftf 上表中 第 行是假设整个公式为假 f 因为整个公式是蕴涵式 因此在 下赋值 f 第 行是在断定 只要前件真 t 而后件假 f 该蕴涵式必假 第 行是在断定后件怎样才能假 f 前件怎样才能真 t 因后件又是个蕴涵式 所以这个蕴涵式的前件真 t 而后件假 f 该蕴涵式必假 又因整个蕴涵式的前件是个合取式 所以合取两端的公式必须都真 t 该合取式才真 t 从第 行可以看出 变项p既真 t 又假 f 整个蕴涵式中至少有一逻辑矛盾 所以该公式为重言式 3 我们再对一等值式是否为重言式进行判定 对等值式的判定比较麻烦 我们可根据真值联结词 的逻辑性质 等值式 p q 可表述为 p q p q 把等值式分解为两个蕴涵式 然后再分别用归谬赋值法进行判定 如果这两个蕴涵式都是重言式 那么这一等值式为重言式 如果两个蕴涵式中有一个不是重言式 那么 这一等值式就不是重言式 如下例 证明 p q r p q r 我们先将此公式分解为两个蕴涵式 再分别判定 p q r p q r tttfttffftfftftf表中变项q既真 t 又假 f 出现矛盾 所以该蕴涵式为重言式 p q r p q r ttftffftffftttfttf表中变项r既真 t 又假 f 出现矛盾 所以该蕴涵式为重言式 由于蕴涵式 和 都是重言式 所以 原等值式为重言式 4 常用重言式 1 重言蕴涵式 p p 同一律 p p 排中律 p p 不矛盾律 p q q p 否定后件律 p q p q mp规则 即分离规则 p q p q p q q p否定肯定律 p q p p q q合取分解律 p q q r p r 假言三段论 又叫连锁蕴涵律 p r r p 归谬律 基本含义为 如果从一个命题可以推出矛盾 那么这个命题就是假的 p p q 析取添加律 2 重言等价式 双重否定律 同等律 交换律 结合律 分配律 摩根律 吸收律 蕴含律 等价律 零律 又称加元律 同一律 互补律 输出律 归缪律 逆反律 简化律 p p 四 范式 1 范式的涵义 在数学中通常称之为 通式 把命题公式化归为一种标准的形式 称此标准形式为范式 它是一种形式上有一定规律的公式 因而它具有一些形式方面的特征 凭借这种特征 我们就能确定一个真值形式是不是重言式 简单地说就是一个真值形式如果命题逻辑公式只包含联结词 合取 析取 及 否定 并且其中否定符号只属于一个变项 那么就是范式 如 p q r s p q 就是范式 而 p q q r s就不是范式 因为其中的 属于 q r 的整体 不合范式的涵义 2 判定的涵义 以有限次步骤来决定命题公式是否为永真式 永假式 还是可满足的 或者判定二个命题公式是否等价等这一类的问题 统称为判定问题 3 范式中的几个主要概念 1 简单析取 由命题变项或命题变项的否定用析取词联结而成的析取式 p r p q p q等 因此 一个简单析取是重言式 当且仅当它至少含有一对这样的析取支 其中一个是某变项 而另一个是它的否定 如简单析取p p q就是一个重言式 2 简单合取 由命题变项或命题变项的否定用合取连接词而成的合取式 如p q p q r等 一个简单合取是不可满足 矛盾式 的当且仅当有一个命题变项 它和它的否定都在该简单合取中出现 如p p r就是一个矛盾式 4 析取范式 a是析取范式是指它是形如a1 a2 a3 an n n且n 1 的真值形式 其中每个ai 1 i n 都是简单合取式 称ai为析取范式的成员 例如 p q p p q p q 就是析取范式 注意 析取范式的优点就在于它易于显示矛盾 一个析取范式是否为矛盾的 可以用极简易的方法在有穷步骤内判断 这是因为每一个析取范式都由几个简单合取组成 5 合取范式 a是合取范式是指它是形如a1 a2 a3 an n n且n 1 的真值形式 其中每个其中每个ai 1 i