第1章 命题逻辑课程性质 Discrete Math. 离散数学 研究离散对象及其相互间关系的一门数学学科。 研究离散结构的数学分支。（辞海）计算机科学、信息科学、数字化科学的数学基础 第1章 命题逻辑离散数学主要内容 命题逻辑 谓词逻辑 集 合 二元关系 函 数 代数系统 群、环和域 格与布尔代数 图 论 数理逻辑(Mathematics Logic)集合论(Sets)代数结构（或代数系统） (Algebra Structure)图论(Graph Theory)第1章 命题逻辑哥尼斯堡七桥问题哈密尔顿周游世界问题四色定理第1章 命题逻辑离散数学课程设置：计算机系核心课程信息类专业必修课程其它类专业的重要选修课程第1章 命题逻辑 离散数学的后继课程： 数据结构、编译技术、 算法分析与设计、人工智能与机器人、 数据库、网络和计算机图形学第1章 命题逻辑教材及参考书左孝凌等，离散数学，上海科学技术文 献出版社，1982同济大学应用数学系离散数学编写组， 离散数学，统计大学出版社，2003第1章 命题逻辑 第1章 命题逻辑逻辑学：研究思维形式及思维规律的科学。逻辑学 辩证逻辑：以辩证法的世界观为基础的逻辑学。 形式逻辑：对思维的形式结构和规律进行研究 的类似于语法的一门工具性学科。 思维的形式结构 概念：思维的基本单位。 判断：通过概念对事物是否具有某种属 性进行肯定或否定的回答。 推理：由一个或几个判断推出另一判断 的思维形式。 数理逻辑：用数学方法来研究推理的规律。 第1章 命题逻辑数理逻辑包括逻辑演算、证明论、公理集合论、模型 论和递归论。本课程只介绍逻辑演算中的命题逻辑和谓词 逻辑。17世纪中叶：德国数学家莱布尼茨(G.W.Leibnitz)创立。 英国数学家布尔(G.Boole)：布尔代数 德国数学家弗雷格(F.L.G.Frege)：量词与约束变元 美国数学家歌德尔(K.Godel)：完全性定理意大利数学家皮亚诺(G.Peano) 英国数学家德摩根(A.DeMorgen)、罗素(B.A.Russell)。所谓的数学方法，就是引进一套符号体系的方法，所以数 理逻辑又称为符号逻辑。 第1章 命题逻辑第1章 命题逻辑1.1命题及联结词1.1.1 命题的基本概念 在数理逻辑中把能判断真假的陈述句称为命题。一般 用小写英文字母或小写英文字母带下标表示。 命题的概念包含了以下3个要素：只有陈述句才有可能成为命题，而其它的语句，如：感 叹句、祈使句、疑问句等都不是命题。 一个语句虽是陈述句,但不能判断真假不是命题。 虽然要求命题能判断真假，但不要求现在就能确定真 假，将来可以确定真假也可以。第1章 命题逻辑一个命题表达的判断结果称为命题的真 值。命题的真值有“真”和“假”两种，分别用 True、T、1(真)和False、F、0(假)来表示。 真值为真的命题称为真命题，真值为假的命 题称为假命题。任何命题的真值是唯一的。在命题逻辑中对命题不再细分，因而命 题是命题逻辑中最基本的也是最小的研究单 位。第1章 命题逻辑【例1.1】判断以下语句是否为命题。若是命题 ，确定其真值。上海是个小村庄。存在外星人。禁止吸烟！北京是中国的首都。4是素数或6是素数。今天你吃了吗？11+1=100我正在说谎。命题(F) 命题(待定) 不是命题(祈使句) 命题(T) 命题(F) 不是命题(疑问句) 命题(由上下文确定) 不是命题(悖论)第1章 命题逻辑表示命题的小写英文字母或带下标的小写英文字母常称 为命题标识符。如果命题标识符表示一个具体、确定的命题 ，称为命题常元。如果命题标识符表示任意一个命题，称为 命题变元。命题变元无确定的真值。命题是能判断真假的陈述句。而命题变元代表任意的命 题，其真值是不确定的。因而不是命题。如果一个命题不能再分解成更简单的命题，则称该命题 为原子命题。如果一个命题不是原子命题，称该命题为复合 命题。如果命题变元表示原子命题时，该命题变元称为原子 变元。在自然语言中，可以通过“如果，那么”，“不但 ，而且”这样的连词将简单的陈述句联结成复合语句，同 样在命题逻辑当中，也可以通过命题联结词将原子变元联 结起来表示复合命题。第1章 命题逻辑1.1.2 命题联结词常用的逻辑联结词有五种：否定联结 词、合取联结词、析取联结词、条件联结 词和双条件联结词。 表1.1 p p0 11 0p和p的关系如表1.1所示，表1.1叫做否定联结词“” 的真值表(下同)。联结词“”也可以看作逻辑运算，它是一元运算。 【例1.2】否定下列命题。p：王强是一名大学生。p：王强不是一名大学生。1. 否定联结词定义1.1.1 设p为命题，则p的否定是一 个复合命题，记作：p，读作“非p”或“p的 否定”。定义为：若P为T，则p为F；若p 为F，则p的真值为T。第1章 命题逻辑2. 合取联结词 定义1.1.2设p和q均为命题，则p 和q的合取是一个复合命题，记作 pq，读作“p与q”或“p合取q”。定义 为：当且仅当p和q均为T时，pq的 才为T。联结词“”的真值表如表1.2所 示。联结词“”也可以看成逻辑运算 ，它是二元逻辑运算。 表1.2 pqpq0 00010100111【例1.3】设 p：2008年北京举办了奥运会。q：中国是世界四大文明古国之一。 则pq：2008年北京举办了奥运会并且中国是世界四 大文明古国之一。第1章 命题逻辑3. 析取联结词定义1.1.3 设p和q均为命题， 则p和q的析取是一个复合命题， 记作pq，读作“p或q”或者“p析取 q”。定义为：当且仅当p和q均为F 时，pq才为F。联结词“”的真值表如表1.3 所示。联结词“”也可以看成逻辑运 算，它是二元逻辑运算。表1.3pqpq000011101111“”与汉语中的“或”相似，但又不相同。汉语中的或有可 兼或与不可兼或(排斥或)的区分。 【例1.4】我今天在电视上看这场杂技或在剧场里看这场杂技 。灯泡有故障或开关有故障。第1章 命题逻辑4. 条件联结词定义1.1.4 设p和q均为命题，其条 件命题是个复合命题，记为：pq。读 作“如果p，那么q”或“若p，则q”。定义 为：当且仅当p为T，q为F时，pq才 为F。p称为条件命题pq的前件，q称 为条件命题pq的后件。 联结词“”真值表如表1.4所示。联结词“”也可以看成逻辑运算， 它是二元逻辑运算。 表1.4 pqpq001011100111【例1.5】 p：小王努力学习。q：小王学习成绩优秀。 pq：如果小王努力学习，那么他的学习成绩就优秀。 联结词“”与汉语中的“如果，那么”或“若，则 ”相似，但又是不相同的。(“”可不顾及前因后果)第1章 命题逻辑5. 双条件联结词定义1.1.5设p和q均为命题，其复 合命题pq称为双条件命题，读作：“p 双条件q”或者“p当且仅当q”。定义为： 当且仅当p和q的真值相同时，pq为T 。联结词“”的真值表如表1.5所示。 联结词“”也可以理解成逻辑运算， 它是二元逻辑运算。 表1.5 pqpq001010100111双条件联结词表示的是一个充分必 要关系，与前面所述相同，也可以不必顾及其前因后果， 而只根据联结词的定义来确定其真值。【例1.6】设p：张华是三好学生。q：张华德、智、体全优秀。 pq：张华是三好学生当且仅当德、智、体全优秀。第1章 命题逻辑1.2 命题公式与翻译把命题常量，命题变量按照一定的逻辑顺序用命题联结 词连接起来就构成了命题演算的合式公式，也叫命题公式。 当使用联结词集，时，合式公式定义如下 ： 定义1.2.1按下列规则构成的符号串称为命题演算的合式 公式，也称为命题公式，简称公式。 单个命题变元和常元是合式公式。 如果A是合式公式，那么A是合式公式。 如果A和B是合式公式，那么(AB)、(AB)、 (AB)和(AB)是合式公式。 当且仅当有限次地应用了、所得到的符号 串是合式公式。命题公式一般的用大写的英文字母A，B，C，表 示。 依照这个定义，下列符号串是合式公式：第1章 命题逻辑(pq)，(pq)，(p(pq)，(pq)(qr)(st) 下列符号串不是合式公式：(pq)(q)，(pq，(pq)q) 定义1.2.1给出合式公式定义的方法称为归纳定义，它 包括三部分：基础，归纳和界限。定义1.2.1中的是基础 ，和是归纳，是界限。下文中还将多次出现这种形 式的定义。 为方便起见，对命题公式约定如下：最外层括号可以省略。规定联结词的优先级由高到低依次为， ，。按此优先级别，如果去掉括号，不改变原公式运算 次序，也可以省掉这些括号。 一般地说，命题公式中包含命题变元，因而无法计算 其真值，所以不是命题。命题公式中的命题变元，也叫命题公式的分量。第1章 命题逻辑有了命题公式的概念，就可以用命题公式表示复合命 题，常将这个过程称为命题的符号化。命题的符号化可按 如下步骤进行： 找出复合命题中的原子命题。 用小写的英文字母或带下标的小写的英文字母表示这些 原子命题。 使用命题联结词将这些小写的英文字母或带下标的小写 的英文字母连接起来。 【例1.7】将下列命题符号化：他今天上午或者骑自行车去学校，或者乘公共汽车去学校 。 解：令 p：他今天上午骑自行车去学校。q：他今天上午乘公共汽车去学校。 此命题中的或是不可兼或，所以不能符号化为：pq 。而要符号化为：(pq)或(pq)(pq)。第1章 命题逻辑1.3真值表和等价公式1.3.1命题公式的真值表定义1.3.1 设pl，p2，pn是出现在公式A中的全部命题 变元，给pl，p2，pn各指定一个真值，称为对公式A的一 个赋值或解释。若指定的赋值使A的真值为T，则称这个赋值 为A的成真赋值，若使A的真值为F，则称这个赋值为A的成假 赋值。例如，给公式(pqr)赋值011是指p=0，q=1，r=1， 它是该公式的成真赋值；赋值110是指p=1，q=1，r=0，它 是该公式的成假赋值。 定义1.3.2 在命题公式A中，对A的每一个赋值，就确定 了A的一个真值，把它们汇列成表，称该表为命题公式A的 真值表。 第1章 命题逻辑【例1.8】构造命题公式pq的真值表，并求成真赋 值和成假赋值。表1.6pqppq0011011110001101第1章 命题逻辑表1.7 pqpqpqpq(pq)(pq)0001111010100010001001110001【例1.9】构造命题公式(pq)(pq)的真值表，并 求成真赋值和成假赋值。 解：命题公式(pq)(pq)的真值表如表1.7所示。00， 11是成真赋值，01，10是成假赋值。第1章 命题逻辑1.3.2命题公式的等价定义1.3.3 设A和B是两个命题公式，对A和B的任一赋值 ，A和B的真值都相同，则称A和B是等价的或逻辑相等的， 记为AB 可以证明，命题公式等价有下面的三条性质： 自反性，即对任意命题公式A， AA 对称性，即对任意命题公式A和B，