的离散数学第3章命题逻辑

1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院20222022年年3 3月月11 11日星期五日星期五电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程22022-3-112022-3-11数理逻辑（数理逻辑（Mathematical LogicMathematical Logic） 是研究演绎推理的一门学科，用是研究演绎推理的一门学科，

2、用数学的方法数学的方法来研究来研究推理的规律推理的规律统称为数理逻统称为数理逻辑。辑。第二篇第二篇 数理逻辑数理逻辑电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程32022-3-112022-3-11主要研究内容：主要研究内容：推理推理 着重于着重于推理过程是否正确推理过程是否正确 着重于着重于语句之间的关系语句之间的关系 主要研究方法：主要研究方法：数学的方法数学的方法 即引进一套符号体系的方法，即引进一套符号体系的方法， 所以数理逻辑又叫所以数理逻辑又叫符号逻辑符号逻辑（Symbolic Symbolic LogicLogic）。）。 第二篇第二篇 数理逻辑数

3、理逻辑电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程42022-3-112022-3-11什么是数理逻辑什么是数理逻辑 ？ 用数学的方法来研究推理的规律统称为用数学的方法来研究推理的规律统称为数理逻辑。数理逻辑。为什么要研究数理逻辑？为什么要研究数理逻辑？ 程序程序 算法算法 数据数据 算法算法 逻辑逻辑 控制控制总结总结电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程52022-3-112022-3-11第二篇第二篇 数理逻辑数理逻辑命题逻辑命题逻辑 命题的基本概念命题的基本概念命题联结词命题联结词命题公式命题公式命题的范式命题的范式

4、 主要研主要研 究内容究内容谓词逻辑谓词逻辑谓词的基本概念谓词的基本概念谓词公式谓词公式公式的标准型公式的标准型推理与证明技术推理与证明技术命题逻辑推理理论命题逻辑推理理论谓词逻辑推理理论谓词逻辑推理理论数学归纳法数学归纳法按定义证明法按定义证明法电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程62022-3-112022-3-11第三章第三章 命题逻辑命题逻辑 命题逻辑也称命题演算，或语句逻辑。命题逻辑也称命题演算，或语句逻辑。 研究内容：研究内容： （1 1）研究以）研究以命题命题为基本单位为基本单位构成的构成的前提和前提和结论之间的可推导关系结论之间的可推导关

5、系 （2 2）研究）研究什么是什么是命题命题？ （3 3）研究）研究如何表示如何表示命题命题？ （4 4）研究）研究如何由一组前提如何由一组前提推导推导一些结论一些结论？电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程72022-3-112022-3-11第三章第三章 命题逻辑命题逻辑 命题逻辑的命题逻辑的特征：特征： 在研究逻辑的形式时，我们在研究逻辑的形式时，我们把一个命把一个命题只分析到其中所含的命题成份为止，不题只分析到其中所含的命题成份为止，不再分析下去再分析下去。 即：不把一个简单命题再分析为非命即：不把一个简单命题再分析为非命题的集合，也不把题的集合，

6、也不把谓词谓词和和量词量词等非命题成等非命题成份分析出来。份分析出来。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82022-3-112022-3-11第三章第三章 命题逻辑命题逻辑集合的表示方法集合的表示方法2命题公式命题公式3命题范式命题范式4命题基本概念命题基本概念1命题联结词命题联结词2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程92022-3-112022-3-113.1 3.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1、五种基本、五种基本联结词联结词2 2、2424个个基本基本的等价公

7、式的等价公式3 3 掌握求命题掌握求命题范式的方法范式的方法3联结词完备集联结词完备集的理解和学习的理解和学习2公式的代入规公式的代入规则和替换规则则和替换规则电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程102022-3-112022-3-113.2.1 3.2.1 命题命题定义定义3.2.1 3.2.1 具有具有确切真值确切真值的陈述句称为的陈述句称为命命题题, , 该命题可以取一个该命题可以取一个“值值”，称为，称为真真值值。 真值只有真值只有“真真”和和“假假”两种，两种， 分别用分别用“”( (或或“”) )和和“”( (或或“”) )表示。表示。3.2

8、 3.2 命题与命题联结词命题与命题联结词电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程112022-3-112022-3-11（1 1）太阳是圆的；）太阳是圆的； （2 2）北京是中国的首都；）北京是中国的首都；（3 3）1 11 11010；（4 4）+y+y；（5 5）我喜欢踢足球；）我喜欢踢足球；（6 6）3 3能被能被2 2整除；整除；（7 7）地球外的星球上也有人；）地球外的星球上也有人；（8 8）中国是世界上人口最多的国家；）中国是世界上人口最多的国家；例例3.2.13.2.1TF非命题非命题T/FFT/FTT电子科技大学离散数学课程组电子科技大学离

9、散数学课程组国家精品课程国家精品课程122022-3-112022-3-11例例3.2.13.2.1（续）（续）（1 1）把门关上；）把门关上；（2 2）一起来，更精彩！）一起来，更精彩！（3 3）你要出去吗？）你要出去吗？（4 4）今天天气真好啊！）今天天气真好啊！ (5) (5) 我正在说假话我正在说假话. .非命题非命题非命题非命题非命题非命题非命题非命题注意：注意：一切没有判断内容的句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令，如命令句、感叹句、疑问句、祈使句、二义性的陈述句句、感叹句、疑问句、祈使句、二义性的陈述句( (悖论悖论) )等。等。 非命题非命题电子科技大

10、学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程132022-3-112022-3-11n命题一定是陈述句，但并非一切陈述句都是命题。命题一定是陈述句，但并非一切陈述句都是命题。n命题的真值有时可明确给出，有时还需要依靠命题的真值有时可明确给出，有时还需要依靠环境、环境、条件、实际情况时间条件、实际情况时间才能确定其真值。才能确定其真值。结论：结论：在数理逻辑中像在数理逻辑中像字母字母“x x”、“y y”、“z z”等字母总等字母总是表示是表示变量。变量。约定：约定：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程142022-3-112022-

11、3-11下列语句是否是命题？下列语句是否是命题？并判断其真值结果？并判断其真值结果？（1 1）四川）四川不不是一个国家；是一个国家；（2 2）3 3既既是素数是素数又又是奇数；是奇数；（3 3）张谦是大学生）张谦是大学生或是或是运动员；运动员；（4 4）如果如果周末天气晴朗，周末天气晴朗，则则我们将到郊外旅游；我们将到郊外旅游；（5 5）2 + 2 = 42 + 2 = 4当且仅当当且仅当雪是白的。雪是白的。例例3.2.23.2.2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程152022-3-112022-3-11一般来说，命题可分两种类型：一般来说，命题可分两

12、种类型：1)1) 原子命题原子命题( (简单命题简单命题) )：不能再：不能再分解分解为更为简单为更为简单命题的命题。命题的命题。2)2) 复合命题复合命题：可以：可以分解分解为更为简单命题的命题。为更为简单命题的命题。而且这些简单命题之间是通过如而且这些简单命题之间是通过如“或者或者”、“并且并且”、“不不”、“如果如果.则则.”、“当当且仅当且仅当”等这样的关联词和标点符号复合而构等这样的关联词和标点符号复合而构成一个复合命题。成一个复合命题。命题的分类命题的分类电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程162022-3-112022-3-111)1) 今

13、天天气很冷。今天天气很冷。2)2) 今天天气很冷并且刮风。今天天气很冷并且刮风。3)3) 今天天气很冷并且刮风，但室内暖和。今天天气很冷并且刮风，但室内暖和。例例3.2.33.2.3 通常用通常用大写的带或不带下标的英文字母大写的带或不带下标的英文字母、.P.P、Q Q、R R、. . A Ai i、B Bi i 、C Ci i、.P.Pi i、Q Qi i、R Ri i、.等表示命题等表示命题电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程172022-3-112022-3-113.2.2 3.2.2 命题联结词命题联结词设命题设命题P,QP,Q表示任意两个命题表

14、示任意两个命题, ,则则最常见的命题联结词有：最常见的命题联结词有：联接词联接词记号记号 复合命题复合命题读法读法 记法记法真值结果真值结果 3.3.析取析取 P P或者或者Q QP P与与Q Q的析取的析取P P Q QP PQ=1Q=1P=1P=1或或Q=1Q=12.2.合取合取 P P并且并且Q QP P与与Q Q的合取的合取PQPQPQPQ=1=1P=1P=1且且Q=1Q=11.1.否定否定 非非P PP P的否定的否定P PP=1P=1 P=0P=04.4.蕴涵蕴涵若若P,P,则则Q QP P蕴涵蕴涵Q QP PQQP PQ=0Q=0 P=1,Q=0P=1,Q=05.5.等价等价 P

15、 P当且仅当当且仅当Q QP P等价于等价于Q QP PQ QP PQ=1Q=1P P=1=1, ,Q=1Q=1或或P P=0=0, ,Q=0Q=0例如：例如：命题命题P P：2 2是素数；是素数；Q Q：北京是中国的首都：北京是中国的首都电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程182022-3-112022-3-11总结总结P QP QP PPQPQPQPQPQPQP PQ Q0 00 01 10 00 01 11 10 10 11 10 01 11 10 01 01 00 00 01 10 00 01 11 10 01 11 11 11 1电子科技大学离

16、散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程192022-3-112022-3-11说明说明1 1、联结词是句子与句子之间的联结，而非单纯的联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；名词、形容词、数词等地联结；2 2、联结词是两个句子真值之间的联结，而非句子联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何的具体含义的联结，两个句子之间可以无任何地内在联系；地内在联系；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程202022-3-112022-3-11说明说明3 3、联结词与自然语言之间的

17、对应联结词与自然语言之间的对应并非一一对应并非一一对应；联结词联结词自然语言自然语言既既又又、不仅、不仅而且而且、虽然、虽然但但是是、并且、和、与，等等；、并且、和、与，等等；如如P P则则Q Q、只要、只要P P就就Q Q、P P仅当仅当Q Q、只有、只有Q Q才才P P、除非除非Q Q否则否则 P P，等等，等等等价、当且仅当、充分必要、等等；等价、当且仅当、充分必要、等等； 相容（可兼）的或相容（可兼）的或电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程212022-3-112022-3-11符号化下列命题符号化下列命题（1 1）四川）四川不不是人口最多的省份

18、；是人口最多的省份；（2 2）王超是一个）王超是一个德智体德智体全面发展的好学生；全面发展的好学生；解：解：（1 1）设：四川是人口最多的省份。）设：四川是人口最多的省份。 则命题（则命题（1 1）可表示为）可表示为。（2 2）设：王超是一个思想品德好的学生；）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生；：王超是一个学习成绩好的学生； R R：王超是一个体育成绩好的学生。：王超是一个体育成绩好的学生。 R R例例3.23.2. .4 4电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程222022-3-112022-3-11符号化下列命题符号化下列

19、命题（3 3）教室的灯不亮可能是灯管坏了）教室的灯不亮可能是灯管坏了或者或者是停电了；是停电了；（4 4）如果如果周末天气晴朗，周末天气晴朗，那么那么学院将组织我们到石像湖春学院将组织我们到石像湖春游；游；解：解：（3 3）设：教室的灯亮）设：教室的灯亮 ：灯管坏：灯管坏 R R：教室的灯不亮可能是停电了：教室的灯不亮可能是停电了 则命题（则命题（3 3）可表示为）可表示为() ) ( ( R) R) 。（4 4）设：周末天气晴朗；）设：周末天气晴朗； ：学院将组织我们到石像湖春游。：学院将组织我们到石像湖春游。 则命题（则命题（4 4）可表示为）可表示为。例例3.23.2. .4 4（续）（

20、续）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程232022-3-112022-3-11符号化下列命题符号化下列命题（5 5）两个三角形全等）两个三角形全等当且仅当当且仅当三角形的三条边全三角形的三条边全部相等。部相等。解：解：（5 5）设：两个三角形全等；）设：两个三角形全等； ：三角形的三条边全部相等。：三角形的三条边全部相等。 则命题（则命题（5 5）可表示为）可表示为。例例3.23.2. .4 4电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程242022-3-112022-3-11 为了不使句子产生混淆，作如下约定为了不使句

21、子产生混淆，作如下约定，命题联结命题联结词之优先级词之优先级如下：如下：1.1. 否定否定 合取合取, , 析取析取 蕴涵蕴涵 等价等价2.2. 同级的联结词同级的联结词 合取合取, , 析取析取 ，按其出现的先按其出现的先后次序后次序( (从左到右从左到右) )确定确定运算顺序运算顺序3.3. 若运算要求与优先次序不一致时，可使用若运算要求与优先次序不一致时，可使用括括号号；同级符号相邻时，也可使用括号。；同级符号相邻时，也可使用括号。括号括号中的运算为最优先级中的运算为最优先级。约约 定定电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程252022-3-1120

22、22-3-11设命题设命题P P：明天上午七点下雨；：明天上午七点下雨；Q Q：明天上午七点下雪；：明天上午七点下雪；R R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句：1)1) 如果如果明天上午七点明天上午七点不不是雨是雨夹夹雪，雪，则则我将去学校我将去学校2)2) 如果如果明天上午七点明天上午七点不不下雨下雨并且并且不不下雪，下雪，则则我将去学校我将去学校例例3.23.2. .5 5可符号化为：可符号化为：(PQ)R(PQ)R。可符号化为可符号化为:(:(PQ)RPQ)R。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程262022-3-11202

23、2-3-11 设命题设命题P P：明天上午七点下雨；：明天上午七点下雨；Q Q：明天上午七点下雪；：明天上午七点下雪；R R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句：1)1) 如果如果明天上午七点下雨明天上午七点下雨或或下雪，下雪，则则我将我将不不去学校去学校2)2) 明天上午我将明天上午我将雨雪无阻雨雪无阻一定去学校一定去学校解：解： 1) 1)可符号化为可符号化为:(PQ)R:(PQ)R 2)2)可符号化为：可符号化为：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) 或或 (PQ)(PQ)(PQ)(PQ)R(PQ)(PQ)(PQ)(PQ)

24、R例例3.23.2. .5 5（续）（续）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程272022-3-112022-3-11例例3.23.2. .6 6设命题设命题P P：你陪伴我；：你陪伴我； Q Q：你代我叫车子；：你代我叫车子； R R：我将出去。：我将出去。 符号化下述语句：符号化下述语句： 除非除非你陪伴我或代我叫车子，你陪伴我或代我叫车子，否则否则我将我将不不出去出去 如果如果你陪伴我你陪伴我并且并且代我叫辆车子，代我叫辆车子，则则我将出去我将出去 如果如果你你不不陪伴我陪伴我或或不不代我叫辆车子，我将代我叫辆车子，我将不不出去出去R(PQ) R(

25、PQ) 或或 (PQ)RPQ)R( (PQ)RPQ)R(PQ)RPQ)R电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程282022-3-112022-3-11例例:(:(粗略阅读）粗略阅读）设设P:P:雪是白色的雪是白色的;Q:2+2=4;Q:2+2=4。将下列命题符号化：。将下列命题符号化：（1 1）因为雪是白色的，所以）因为雪是白色的，所以2+2=42+2=4； PQ PQ （2 2）如果）如果2+2=42+2=4，则雪是白色的；，则雪是白色的； QPQP（3 3）只有雪是白色的，才有）只有雪是白色的，才有2+2=42+2=4； QPQP（4 4）只有）只有2

26、+2=42+2=4，雪才是白色的；，雪才是白色的； PQPQ（5 5）只要雪不是白色的，就有）只要雪不是白色的，就有2+2=42+2=4； PQPQ（6 6）除非雪是白色的，否则）除非雪是白色的，否则2+242+24； PP Q Q或或QPQP（7 7）雪是白色的当且仅当）雪是白色的当且仅当2+2=42+2=4； P P Q Q电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程292022-3-112022-3-113.2.4 3.2.4 命题联结词的应用命题联结词的应用例例 3.2.7 3.2.7 用复合命题表示如下图所示的开关用复合命题表示如下图所示的开关电路电路

27、： 图图3.3.2.12.1 图图3 3. .2 2.2 .2 图图3 3. .2 2.3.3PQPPQABABABABA A设：设： ：开关闭合；：开关闭合。：开关闭合；：开关闭合。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程302022-3-112022-3-11用复合命题表示如下图所示的逻辑电路用复合命题表示如下图所示的逻辑电路：例例 3.2.8 3.2.8图图3.2.43.2.4 图图3.2.53.2.5 图图3.2.63.2.6QPP P Q QQPP PQ QPP P解解: :设设P P：输入端为高电位：输入端为高电位,Q,Q：输入端为高电位：输入

28、端为高电位, ,则则 “与门与门”对应于对应于PQPQ； “或门或门”对应于对应于PQPQ； “非门非门”对应于对应于P P。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程312022-3-112022-3-113.3 3.3 命题公式、解释与真值表命题公式、解释与真值表定义定义3.3.13.3.1 一个特定的命题是一个一个特定的命题是一个常值命题常值命题，它不是它不是具有值具有值“T T”( (“1 1”) )，就是具有值，就是具有值“F F”( (“0 0”) )。 一个任意的没有赋予具体内容的原子命题是一个一个任意的没有赋予具体内容的原子命题是一个变量命题，

29、常称它为变量命题，常称它为命题变量命题变量( (或或命题变元命题变元) )。 该命题变量无具体的真值，该命题变量无具体的真值，其其变域是集合变域是集合 T T，F F 注意注意(1)(1)复合命题为命题变元的复合命题为命题变元的“函数函数”, ,其其函数值仍为函数值仍为 真真 或或“假假”值值。(2)(2)真值函数或命题公式真值函数或命题公式，没有确没有确切切真值真值。真值函数真值函数电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程322022-3-112022-3-113.3.1 3.3.1 命题公式命题公式定义定义3.3.2 3.3.2 命题公式命题公式( (递

30、归定义递归定义) )1.1. 命题变元本身是一个公式；命题变元本身是一个公式；2.2. 如如G G是公式，则是公式，则(G)(G)也是公式；也是公式；3.3. 如如G G，H H是公式，则是公式，则(GH)(GH)、(GH)(GH)、(GH)(GH)、(G(GH H) )也是公式；也是公式；4.4. 仅由有限步使用规则仅由有限步使用规则1-31-3后产生的结果。后产生的结果。该公式常用符号该公式常用符号G G、H H、等表示。等表示。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程332022-3-112022-3-11符号串：符号串：(P(QRP(QR)( (QQ

31、( (SRSR) ( (PQPQ) ) ( (PP( ( (PQPQ) (PQPQ) )( (RQRQ)( (PRPR) 等都是命题公式。等都是命题公式。例例3 3. .3.13.1例例3.3.23.3.2 符号串：符号串：( (PQPQ) )QQ) ) ( (PQPQ；( (PQPQ( (R R PQPQ 等都不是合法的命题公式。等都不是合法的命题公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程342022-3-112022-3-11例例3.3.33.3.3试用符号形式写出下列命题：试用符号形式写出下列命题：（1 1）虽然今天天气晴朗，老陈还是不来；）虽然今

32、天天气晴朗，老陈还是不来；（2 2）除非你陪伴我或代我叫的士，否则我将不出去；）除非你陪伴我或代我叫的士，否则我将不出去；（3 3）停机的原因在于语法错误或者程序错误；）停机的原因在于语法错误或者程序错误；解：解：（1 1）P P：今天天气晴朗：今天天气晴朗,Q,Q：老陈要来：老陈要来, ,则有：则有：PPQ Q；（2 2）P P：你陪伴我；：你陪伴我； Q Q：你代我叫的士；：你代我叫的士；R R：我出去。：我出去。则有：则有：RPQRPQ或或PQRPQR；（3 3）P P：停机的原因在于语法错误，：停机的原因在于语法错误，Q Q：停机的原因在：停机的原因在于程序错误，于程序错误，则有：则有

33、：PQPQ；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程352022-3-112022-3-11例例3.3.3(3.3.3(续续) )试用符号形式写出下列命题：试用符号形式写出下列命题：（4 4）若）若a a和和b b是偶数，则是偶数，则a + ba + b是偶数；是偶数；（5 5）我们要做到身体好、学习好、工作好，为祖国四）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。化建设而奋斗。 解：解：（4 4）P P：a a是偶数；是偶数；Q Q：b b是偶数，是偶数，R R：a+ba+b是偶数，是偶数，则有：则有：PQRPQR；（5 5）P P：我们要做到

34、身体好：我们要做到身体好,Q,Q：我们要做到学习好：我们要做到学习好, R, R：我们要做到工作好，我们要做到工作好，S S：我们要为祖国四化建设而奋斗，：我们要为祖国四化建设而奋斗，则有：则有：PQRPQR S S。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程362022-3-112022-3-11公式公式( (PP( (QRQR)( (QQ( (SRSR)可表示可表示如下：如下：(P(QR)(Q(SR)(P(QR)(Q(SR)P(QR)P(QR) Q(S Q(SR R) )P P QR QR Q Q SR SRQ Q R R S R S RS S例例3.3.

35、43.3.4电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程372022-3-112022-3-113.3.2 3.3.2 公式的解释与真值表公式的解释与真值表定义定义3.3.3 3.3.3 设设P P1 1、P P2 2、P Pn n是出现在公式是出现在公式G G中的所中的所有命题变元有命题变元，指定指定P P1 1、P P2 2、P Pn n一组真值，则这组一组真值，则这组真值称为真值称为G G的一个的一个解释解释, ,常记为常记为。 一般来说，若有个命题变元，则应有一般来说，若有个命题变元，则应有2 2n n个不个不同的解释。同的解释。 如果公式如果公式G G

36、在解释下是真的，则称在解释下是真的，则称满足满足G G；如；如果果G G在解释下是假的，则称在解释下是假的，则称弄假弄假G G。定义定义3.3.43.3.4 将将公式公式G G在其所有可能解释下在其所有可能解释下的的真值情况真值情况列成列成的表，称为的表，称为G G的的真值表真值表。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程382022-3-112022-3-11例例3 3. .3.53.5求下面公式的真值表：求下面公式的真值表： (P(P( P PQ)R)QQ)R)Q 其中，、是的所有命题变元。其中，、是的所有命题变元。P Q R P PQ( PQ)RP(

37、PQ)R)G0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1011100000111100000101001111010011110111电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程392022-3-112022-3-11例例3 3. .3.53.5（续）（续）P Q R(P( PQ)R)Q0 0 010 0 110 1 010 1 111 0 001 0 111 1 011 1 1 1进一步化简为：进一步化简为：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程402022-3-112

38、022-3-11例例3.3.63.3.6 P Q () () ( ) (Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面这组公式的真值表：求下面这组公式的真值表： 1 1 ( ()； 2 2( ()； 3 3 ( ( ) ) ( (Q)Q)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程412022-3-112022-3-11从这三个真值表可以看到一个非常有趣的事实：从这三个真值表可以看到一个非常有趣的事实： 公式公式G G1 1对所有可能的解释具有对所有可能的解释具有“真真”值值 公式公式G G3 3对所有可能的解释均具有对所有可能

39、的解释均具有“假假”值值 公式公式G G2 2则具有则具有“真真”和和“假假”值值结论结论 P Q () () ( ) (Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程422022-3-112022-3-11定义定义3.3.53.3.51.1. 公式公式G G称为称为永真公式永真公式( (重言式重言式) )，如果在它的所有，如果在它的所有解释之下都为解释之下都为“真真”。2.2. 公式公式G G称为称为永假公式永假公式( (矛盾式矛盾式),),如果在它的所有如果在它的所有解释之下都为解释之下都

40、为“假假”。3.3. 公式公式G G称为称为可满足式可满足式，如果它不是永假的。，如果它不是永假的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程432022-3-112022-3-11从上述定义可知三种特殊公式之间的关系：从上述定义可知三种特殊公式之间的关系：1)1) 永真式永真式G G的否定的否定 G G是是矛盾式矛盾式；矛盾式矛盾式G G的否定的否定 G G是是永真式永真式。2)2) 永真式永真式一定是一定是可满足式可满足式, ,可满足式可满足式不一定是不一定是永真式永真式3)3) 可满足式可满足式的否定不一定为的否定不一定为矛盾式矛盾式结论结论电子科技大学

41、离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程442022-3-112022-3-11例例3.3.73.3.7写出下列公式的真值表，并验证其公式是重言式、写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。矛盾式、可满足公式。（1 1）G G1 1=(=() )( ( ) )；（2 2）G G2 2=(=(Q)Q)( ( ( (Q)Q) (Q(Q)；（3 3）G G3 3=(P=(P Q)Q) Q Q。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程452022-3-112022-3-11例例3.3.7 3.3.7 解解P Q() (

42、)( Q) (Q) (Q) (PQ) Q0 0 0 1 1 0 1 1 永真式永真式永假式永假式可满足式可满足式三个公式的真值表如下：三个公式的真值表如下：101110001110电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程462022-3-112022-3-11设存在设存在G G和和H H两个公式，例如令：两个公式，例如令： ， 。若若是一个永真公式，即这两个公式对任何是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为解释都必同为真假，此时，说和相等，记为。为此可定义：。为此可定义：分析公式（分析公式（1 1）定义定义3 3. .3.63

43、.6 设设G G、H H是是公式，公式，如果在任意解释如果在任意解释下，下，G G与与H H的的真值相同，则称公式真值相同，则称公式G G、H H是是等价的等价的，记作记作G GH H。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程472022-3-112022-3-11公式公式G G、H H等价等价的充分必要条件是公式的充分必要条件是公式G GH H是永真公式是永真公式证明证明: :“”假定假定G G，H H等价，则等价，则G G，H H在其任意解释在其任意解释下或同为真或同为假下或同为真或同为假。 于是由于是由“”的意义知，的意义知，G GH H在其任何的解释

44、在其任何的解释下，其真值为下，其真值为“真真”，即，即G GH H为永真公式。为永真公式。“”假定公式假定公式G GH H是永真公式，是它的任意解释，是永真公式，是它的任意解释，在下，在下，G GH H为真，因此，为真，因此，G G、H H或同为真，或同为假，或同为真，或同为假，由于的任意性，故有由于的任意性，故有G GH H。定理定理3 3. .3.13.1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程482022-3-112022-3-11 （1 1）“”是一种逻辑联结词，公式是一种逻辑联结词，公式G GH H是命题是命题公式，其中公式，其中“”是一种逻辑运算

45、，是一种逻辑运算，G GH H的结果仍是的结果仍是一个命题公式一个命题公式。而逻辑等价而逻辑等价“”则是描述了两个公式则是描述了两个公式G G与与H H之间的一之间的一种逻辑等价关系，种逻辑等价关系，G GH H表示表示“命题公式命题公式G G等等价价于命题于命题公式公式H H”，G GH H 的结果的结果不是命题公式不是命题公式。 （2 2）如果要求用计算机判断命题公式如果要求用计算机判断命题公式G G、H H是否是否逻辑等价，即逻辑等价，即G GH H那是办不到的那是办不到的然而计算机却可然而计算机却可“计算计算”公式公式G GH H是否是否为为永真公式。永真公式。 “” ” 与与“”的区

46、别的区别电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程492022-3-112022-3-11“=”=”的性质的性质由于由于“= =”不是一个联结词，而是一种关系，不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：为此，这种关系具有如下三个性质：（1 1）自反性）自反性 G = GG = G；（2 2）对称性）对称性 若若G = HG = H，则，则H = GH = G；（3 3）传递性）传递性 若若G = HG = H，H = SH = S，则，则G = SG = S。这三条性质体现了这三条性质体现了“= =”的实质含义。的实质含义。 电子科技大学离

47、散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程502022-3-112022-3-113.3.4 3.3.4 命题公式的基本等价关系命题公式的基本等价关系例例3.3.83.3.8 证明公式证明公式G G1 1( () )与公式与公式G G2 2(PQ)(QP)(PQ)(QP)之间是逻辑等价的。之间是逻辑等价的。 解：解：根据定理根据定理3.3.13.3.1，只需判定公式，只需判定公式G G3 3( () ) (PQ)(QP)(PQ)(QP)为永真公式。为永真公式。P Q G3() (Q)(Q)0 0 1 1 1 1 10 1 0 1 1 0 0 1 0 0 1 0 0 11 1

48、 1 1 1 1 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程512022-3-112022-3-11设设G G，H H，S S是任何的公式，则：是任何的公式，则：基本等价公式基本等价公式1) 1) 1 1：GGGGG G ( (幂等律幂等律) ) 2 2：GGGGG G2) 2) 3 3：GHGHHG HG ( (交换律交换律) ) 4 4：GHGHHGHG3) 3) 5 5：G(HS)G(HS)(GH)S(GH)S( (结合律结合律) ) 6 6: : G(HS) G(HS)(GH)S(GH)S4)4) 7 7：G(GH)G(GH) G G ( (吸收律吸

49、收律) ) 8 8：G(GH)G(GH) G G电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程522022-3-112022-3-115)5) 9 9：G(HS)G(HS)(GH)(GS)(GH)(GS)( (分配律）分配律） 1010：G(HS)G(HS)(GH)(GS)(GH)(GS)6) 6) 1111：GGG G( (同一律同一律) ) 1212：GGG G 7) 7) 1313：GG( (零律）零律） 1414：GG8) 8) 1515：GGGG1 1( (排中律排中律) )9) 9) 1616：GGGG ( (矛盾律矛盾律) )基本等价公式（续）基本等

50、价公式（续）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程532022-3-112022-3-11基本等价公式（续）基本等价公式（续）10) 10) 1717：(G)(G)G G ( (双重否定律双重否定律) )11) 11) 1818：(GH)(GH)GH GH (De MoRGan(De MoRGan定律定律) ) 1919：(GH)(GH)GHGH。12) 12) 2020: : (G(GH)H)( (GH)(HGGH)(HG) )( (等价等价) )13) 13) 2121：(GH)(GH)(GH)(GH) ( (蕴涵蕴涵) )14) 14) E E222

51、2：G G G G。 ( (假言易位假言易位) )15)15) E E2323：G G G G。 ( (等价否定等等价否定等式式) )16)16) E E2424：(G(G ) (G) (G ) ) G G ( (归谬论归谬论) )如何推导？如何推导？电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程542022-3-112022-3-11将将G G，H H理解为某总体论域上的子集合，规定：理解为某总体论域上的子集合，规定：GHGH为两集合的公共部分为两集合的公共部分（交集合）（交集合）GHGH为两集合的全部为两集合的全部（并集合）（并集合）G G为总体论域（如矩形域

52、）中为总体论域（如矩形域）中G G的的补集补集将命题中的真值将命题中的真值“1 1”理解为集合中的总体论域理解为集合中的总体论域（全集），将命题中的真值（全集），将命题中的真值“0 0”理解为集合中的理解为集合中的空集空集 GH GH GGH GH GUABUABUA命题与集合之间的关系命题与集合之间的关系电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程55 “” “” 对对“”与与“”“”对对“”的对比的对比等幂律等幂律; ; GGGGG GGG GGG G交换律交换律= = = GHGHHGHG GH GHHGHG结合律结合律A(BC)=(AB)CA(BC)=(

53、AB)CA(BC)=(AB)CA(BC)=(AB)CG(HS)=(GH)SG(HS)=(GH)SG(HS)=(GH)SG(HS)=(GH)S恒等律恒等律；GG GG零律零律；GG GG吸收律吸收律 A(AB)=A A(AB)=A A(AB)=A A(AB)=A G(GH)=G G(GH)=GG(GH)=G G(GH)=G否定律否定律 (G)(G)G G分配律分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)G(HS)=(GH)(GS)G(HS)=(GH)(GS)G(HS)=(GH)(GS)G(HS)=(GH)(GS)AA 电子

54、科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程562022-3-112022-3-11设设G G( (P P1 1, ,P P2 2, , ,P Pn n) )是一个命题公式是一个命题公式，其中其中： P P1 1, , P P2 2, , , , P Pn n是命题变元是命题变元，G G1 1(P(P1 1, ,P P2 2, , ,P Pn n) ), , G G2 2( (P P1 1, ,P P2 2, , ,P Pn n) ), , ., , G Gn n( (P P1 1, ,P P2 2, , ,P Pn n) )为任意的命题为任意的命题公式公式， 分别

55、分别用用G G1 1、G G2 2、G Gn n取代取代G G中的中的P P1 1、P P2 2、P Pn n后后得到新的命得到新的命题题公式公式： G(G(G G1 1, ,G G2 2, , ,G Gn n) ) G G( (P P1 1, ,P P2 2, , ,P Pn n) )若若G G是永真是永真( (或或永假永假) )式式，则则G G也是永真( (或或永假永假) )式。定理定理3.3.2(3.3.2(代入定理代入定理) )电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程572022-3-112022-3-11例例3.3.93.3.9设设( (, , )

56、 )( ( ()，证明公，证明公式式G G是一个永真公式。另有两个任意公式：是一个永真公式。另有两个任意公式： ( (, , ) )( ( ) )； ( (, , ) )( () )。 进一步验证代入定理的正确性。进一步验证代入定理的正确性。 解解 建立公式建立公式G G的真值表如的真值表如右所示。可见右所示。可见为永真公式。为永真公式。P Q()0 010 111 011 11电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程582022-3-112022-3-11例例3.3.93.3.9（续）（续）将将( (, , ) )( ( ) )；( (, , ) )( (

57、) ) 分别取代分别取代G G中的命题变元中的命题变元P P、Q Q，所得到的公式：，所得到的公式： (P, Q) = G(H, S) = (H(HS)S (P, Q) = G(H, S) = (H(HS)S = ( = ( )()( )()()()() ) 建立新公式建立新公式(P, Q)(P, Q)的真值表。的真值表。P Q( )( )()()0 0 0 1 1 0 1 1 ( (, , ) )( ( ()1 1 1 1 1 1 1 1 10 0 0 0 0 1 0 1 01 1 0 1 1 0 0 1 01 0 1 1 0 1 1 1 1电子科技大学离散数学课程组电子科技大学离散数学课程

58、组国家精品课程国家精品课程592022-3-112022-3-11定理定理3.33.3.3.3( (替换定理替换定理) )设设G G1 1是是G G的子公式的子公式( (即即 G G1 1是公式是公式G G的一部分的一部分) )，H H1 1是任意的命题公式，是任意的命题公式，在在G G中凡出现中凡出现G G1 1处都以处都以H H1 1替换替换，得到新的命题公式得到新的命题公式H H，若若G G1 1 H H1 1，则则G G H H。利用利用2424个基本等价公式及代入定理和替换定个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。理，可完成公式的转化和等价判定。电子科技大学离

59、散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程602022-3-112022-3-11例例3.3.103.3.10利用基本的等价关系，完成如下工作：利用基本的等价关系，完成如下工作：（1 1）判断公式的类型：）判断公式的类型： 证明证明 () ( ( ( ( )()( )()( ) )是一个永真公式。是一个永真公式。（2 2）证明公式之间的等价关系：）证明公式之间的等价关系：证明证明( () = () = ()（3 3）化简公式：）化简公式：证明证明( ( P(P( R)(R)(R)(PR) = R R)(PR) = R 电子科技大学离散数学课程组电子科技大学离散数学课程组国家

60、精品课程国家精品课程612022-3-112022-3-11例例3.3.10 3.3.10 证明证明（1 1）() ) ( ( ( ( )( )()( ) ) = ( = ()()( () ()()() = ( = ()()()()() ( ()()() = ( = ()()()()() ) ( ( ( ()()() = ( = ()()() ()()() = T) = T 即即: :() ( ( ( ( )()( )()( ) )为永真公式；为永真公式； 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程622022-3-112022-3-11例例3.3.10 3.3.10 证明（续）证