第3章-命题逻辑-电子科大离散数学内部教学课件

电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院09 09 七月七月 2024 2024电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程22024/7/92024/7/9数理逻辑（数理逻辑（Mathematical LogicMathematical Logic）是研究演绎推理的一门学科，用是研究演绎推理的一门学科，用数学的数学的方法方法来研究来研究推理的规律推理的规律统称为数理逻辑。统称为数理逻辑。第二篇第二篇 数理逻辑数理逻辑电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程32024/7/92024/7/9主要研究内容：主要研究内容：推理推理 着重于着重于推理过程是否正确推理过程是否正确 着重于着重于语句之间的关系语句之间的关系 主要研究方法：主要研究方法：数学的方法数学的方法 就是引进一套符号体系的方法，所以数就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（理逻辑又叫符号逻辑（Symbolic LogicSymbolic Logic）。）。第二篇第二篇 数理逻辑数理逻辑电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程42024/7/92024/7/9什么是数理逻辑什么是数理逻辑？用数学的方法来研究推理的规律统称为数理逻辑。用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？为什么要研究数理逻辑？程序算法数据程序算法数据 算法逻辑控制算法逻辑控制总结总结电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程52024/7/92024/7/9第二篇第二篇 数理逻辑数理逻辑命题逻辑命题逻辑 命题的基本概念命题的基本概念命题联结词命题联结词命题公式命题公式命题的范式命题的范式主要研主要研究内容究内容谓词逻辑谓词逻辑谓词的基本概念谓词的基本概念谓词公式谓词公式公式的标准型公式的标准型推理与证明技术推理与证明技术命题逻辑推理理论命题逻辑推理理论谓词逻辑推理理论谓词逻辑推理理论数学归纳法数学归纳法按定义证明法按定义证明法电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程62024/7/92024/7/9第三章第三章 命题逻辑命题逻辑 命题逻辑也称命题演算，或语句逻辑。命题逻辑也称命题演算，或语句逻辑。研究内容：以研究内容：以命题为基本单位命题为基本单位构成的构成的前提和结前提和结论之间的可推导关系。论之间的可推导关系。（1 1）研究）研究什么是命题什么是命题？（2 2）研究）研究如何表示命题如何表示命题？（3 3）研究）研究如何由一组前提推导一些结论如何由一组前提推导一些结论？电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程72024/7/92024/7/9第三章第三章 命题逻辑命题逻辑 命题逻辑的命题逻辑的特征：特征：在研究逻辑的形式时，我们在研究逻辑的形式时，我们把一个命题只把一个命题只分析到其中所含的命题成份为止，不再分析下分析到其中所含的命题成份为止，不再分析下去去。不把一个简单命题再分析为非命题的集合，。不把一个简单命题再分析为非命题的集合，不把不把谓词谓词和和量词量词等非命题成份分析出来。等非命题成份分析出来。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程82024/7/92024/7/9第三章第三章 命题逻辑命题逻辑集合的表示方法集合的表示方法2命题公式命题公式3命题范式命题范式4命题基本概念命题基本概念1命题联结词命题联结词2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程92024/7/92024/7/93.1 3.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1、五种基本、五种基本联结词联结词2 2、2424个个基本基本的等价公式的等价公式3 3 掌握求命题掌握求命题范式的方法范式的方法3联结词完备集联结词完备集的理解和学习的理解和学习2公式的代入规公式的代入规则和替换规则则和替换规则电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程102024/7/92024/7/93.2.1 3.2.1 命题命题定义定义3.2.13.2.1具有具有确切真值确切真值的陈述句称为的陈述句称为命题命题,该命题可以取一个该命题可以取一个“值值”，称为，称为真值真值。真值只有真值只有“真真”和和“假假”两种，两种，分别用分别用“”(或或“”)和和“”(或或“”)表示。表示。3.2 3.2 命题与命题联结词命题与命题联结词电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程112024/7/92024/7/9（1 1）太阳是圆的；）太阳是圆的；（2 2）成都是一个旅游城市；）成都是一个旅游城市；（3 3）北京是中国的首都；）北京是中国的首都；（4 4）这个语句是假的；）这个语句是假的；（5 5）1 11 11010；（6 6）+y+y；（7 7）我喜欢踢足球；）我喜欢踢足球；（8 8）3 3能被能被2 2整除；整除；（9 9）地球外的星球上也有人；）地球外的星球上也有人；（1010）中国是世界上人口最多的国家；）中国是世界上人口最多的国家；（1111）今天是晴天；）今天是晴天；例例3.2.13.2.1TTT/F非命题非命题T/FFT/FTTT非命题非命题电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程122024/7/92024/7/9例例3.2.13.2.1（续）（续）（1212）把门关上；）把门关上；（1313）滚出去！）滚出去！（1414）你要出去吗？）你要出去吗？（1515）今天天气真好啊！）今天天气真好啊！非命题非命题非命题非命题非命题非命题非命题非命题注意：注意：一切没有判断内容的句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。句、感叹句、疑问句、祈使句、二义性的陈述句等。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程132024/7/92024/7/9n命题一定是陈述句，但并非一切陈述句都是命题。命题一定是陈述句，但并非一切陈述句都是命题。n命题的真值有时可明确给出，有时还需要依靠命题的真值有时可明确给出，有时还需要依靠环境、环境、条件、实际情况时间条件、实际情况时间才能确定其真值。才能确定其真值。结论：结论：在在数数理理逻逻辑辑中中像像字字母母“x x”、“y y”、“z z”等等字字母总是表示母总是表示变量。变量。约定：约定：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程142024/7/92024/7/9下列语句是否是命题？下列语句是否是命题？并判断其真值结果？并判断其真值结果？（1 1）四川）四川不不是一个国家；是一个国家；（2 2）3 3既既是素数是素数又又是奇数；是奇数；（3 3）张谦是大学生）张谦是大学生或是或是运动员；运动员；（4 4）如果如果周末天气晴朗，周末天气晴朗，则则我们将到郊外旅游；我们将到郊外旅游；（5 5）2+2=42+2=4当且仅当当且仅当雪是白的。雪是白的。例例3.2.23.2.2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程152024/7/92024/7/9一般来说，命题可分两种类型：一般来说，命题可分两种类型：1)1)原子命题原子命题(简单命题简单命题)：不能再：不能再分解分解为更为简单为更为简单命题的命题。命题的命题。2)2)复合命题复合命题：可以：可以分解分解为更为简单命题的命题。为更为简单命题的命题。而且这些简单命题之间是通过如而且这些简单命题之间是通过如“或者或者”、“并且并且”、“不不”、“如果如果.则则.”、“当且当且仅当仅当”等这样的关联词和标点符号复合而构成等这样的关联词和标点符号复合而构成一个复合命题。一个复合命题。命题的分类命题的分类电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程162024/7/92024/7/91)1)今天天气很冷。今天天气很冷。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、.等表示命题等表示命题电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程172024/7/92024/7/93.2.2 3.2.2 命题联结词命题联结词设命题设命题P,QP,Q表示任意两个命题表示任意两个命题,则则最常见的命题联结词有：最常见的命题联结词有：联接词联接词记号记号 复合命题复合命题读法读法 记法记法真值结果真值结果 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 P P=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 P当且仅当当且仅当Q QP P等价于等价于Q QP PQ QP PQ=1Q=1P P=1=1,Q=1Q=1或或P P=0=0,Q=0Q=0电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程18否定否定联结联结词词联结词联结词“”是自然语言中的是自然语言中的“非非”、“不不”和和“没有没有”等的逻辑抽象；等的逻辑抽象；例：例：P:2P:2是素数是素数 P:2P:2不是素数不是素数P PP P0 01 11 10 0电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程19析取析取联结联结词词联结词联结词“”是自然语言中的是自然语言中的“或或”、“或者或者”等逻辑抽象等逻辑抽象；例：例：P:P:王红学过英语；王红学过英语；Q：王红学过法语；：王红学过法语；则则PQ:王红学过英语或法语王红学过英语或法语；P PQ QPQPQ0 00 00 00 01 11 11 10 01 11 11 11 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程20n析取联结词表示的析取联结词表示的“或或”有有“可兼可兼或或”、“不可兼或不可兼或”两种。两种。例如：例如：张红生于张红生于1982年或年或1983年。年。若若P：张红生于：张红生于1982年年Q：张红生于：张红生于1983年年P与与Q不能同时为真，即为不能同时为真，即为“不可兼或不可兼或”。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程21合取合取联结联结词词“”是自然语言中的是自然语言中的“并且并且”、“既既又又”、“但但”、“和和”、“与与”、“不仅不仅而且而且”、“虽然虽然但是但是”、“一面一面,一面一面”等的逻辑等的逻辑抽象；抽象；例：例：P:3是素数；是素数；Q：3是奇数是奇数；则则PQ:3既是素数又是奇数；既是素数又是奇数；P PQ QP QP Q0 00 00 00 01 10 01 10 00 01 11 11 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程22n不是所有的不是所有的“和和”，“与与”都要使都要使用合取联结词表示。用合取联结词表示。例如：例如：1）2和和3的最小公倍数是的最小公倍数是6。2）点）点a位于点位于点b与点与点c之间之间这两个命题都是简单命题，不能再进行划分。这两个命题都是简单命题，不能再进行划分。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程23蕴涵蕴涵联结联结词词“”是自然语言中的是自然语言中的“如果如果，则，则”，“若若，才能，才能”、“除非除非，否则，否则”、“只要只要，就，就”、“仅当仅当”、“只有只有才才”等的逻等的逻辑抽象；辑抽象；例：例：P:角角A和角和角B是对顶角；（是对顶角；（前件前件）Q：角：角A等于角等于角B；（；（后件后件）则则P Q:如果角如果角A和角和角B是对顶角，则角是对顶角，则角A等于角等于角B；P PQ QP QP Q0 00 01 10 01 11 11 10 00 01 11 11 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程24n在自然语言中，前件为假，不管结论真假，在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但对于整个语句的意义，往往无法判断。但对于数理逻辑中的蕴涵联结词来说，当前件数理逻辑中的蕴涵联结词来说，当前件P P为假时，不管为假时，不管Q Q的真假如何，则的真假如何，则PQPQ都为都为真。此时称为真。此时称为“善意推定善意推定”；例如：例如：如果如果2是偶数，则天上就可以掉馅饼。是偶数，则天上就可以掉馅饼。两个简单命题无任何关系，但此命题合法。两个简单命题无任何关系，但此命题合法。n在自然语言中，条件式中前提和结论间必在自然语言中，条件式中前提和结论间必含有某种因果关系，但在数理逻辑中可以含有某种因果关系，但在数理逻辑中可以允许允许两者无必然因果关系两者无必然因果关系，也就是说，也就是说并不并不要求前件和后件有什么联系要求前件和后件有什么联系；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程25n下面几个命题是等价的。下面几个命题是等价的。n1 1）如果如果约翰学习微积分，约翰学习微积分，则则他是大学一年级学他是大学一年级学生。生。n2 2）约翰学习微积分）约翰学习微积分仅当仅当他是大学一年级学生。他是大学一年级学生。n3 3）只有只有约翰是大学一年级学生，他约翰是大学一年级学生，他才才能学习微能学习微积分。积分。n4 4）除非除非约翰是大学一年级学生，约翰是大学一年级学生，否则否则他不学习他不学习微积分。微积分。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程26等价等价联结联结词词“”是自然语言中的是自然语言中的“等价等价”、“充分必要充分必要条件条件”、“当且仅当当且仅当”等的逻辑抽象；（双条等的逻辑抽象；（双条件联结词）件联结词）例：例：P:成都是四川的省会；成都是四川的省会；Q：鸟会飞；：鸟会飞；则则P Q:成都是四川的省会当且仅当鸟会飞。成都是四川的省会当且仅当鸟会飞。P PQ QP P Q Q0 00 01 10 01 10 01 10 00 01 11 11 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程272024/7/92024/7/9总结总结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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程282024/7/92024/7/9说明说明1 1、联结词是句子与句子之间的联结，而非单纯的联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；名词、形容词、数词等地联结；2 2、联结词是两个句子真值之间的联结，而非句子联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何的具体含义的联结，两个句子之间可以无任何地内在联系；地内在联系；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程292024/7/92024/7/9说明说明3 3、联结词与自然语言之间的对应联结词与自然语言之间的对应并非一一对应并非一一对应；联结词联结词自然语言自然语言既既又又、不仅、不仅而且而且、虽然、虽然但是但是、并且、和、与，等等；、并且、和、与，等等；如如P P则则Q Q、只要、只要P P就就Q Q、P P仅当仅当Q Q、只有、只有Q Q才才P P、除非、除非Q Q否则否则 P P，等等，等等等价、当且仅当、充分必要、等等；等价、当且仅当、充分必要、等等；相容（可兼）的或相容（可兼）的或电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程302024/7/92024/7/9符号化下列命题符号化下列命题（1 1）四川）四川不不是人口最多的省份；是人口最多的省份；（2 2）王超是一个）王超是一个德智体德智体全面发展的好学生；全面发展的好学生；（3 3）教室的灯不亮可能是灯管坏了）教室的灯不亮可能是灯管坏了或者或者是停电了；是停电了；（4 4）如果如果周末天气晴朗，周末天气晴朗，那么那么学院将组织我们到石学院将组织我们到石像湖春游；像湖春游；（5 5）两个三角形全等）两个三角形全等当且仅当当且仅当三角形的三条边全部三角形的三条边全部相等。相等。例例3.23.2.4 4电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程312024/7/92024/7/9例例3.23.2.4 4 解解（1 1）设：四川是人口最多的省份。）设：四川是人口最多的省份。则命题（则命题（1 1）可表示为）可表示为。（2 2）设：王超是一个思想品德好的学生；）设：王超是一个思想品德好的学生；：王超是一个学习成绩好的学生；：王超是一个学习成绩好的学生；R R：王超是一个体育成绩好的学生。：王超是一个体育成绩好的学生。则命题（则命题（2 2）可表示为）可表示为R R。（3 3）设：教室的灯不亮可能是灯管坏了）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了：教室的灯不亮可能是停电了 则命题（则命题（3 3）可表示为）可表示为。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程322024/7/92024/7/9（4 4）设：周末天气晴朗；）设：周末天气晴朗；：学院将组织我们到石像湖春游。：学院将组织我们到石像湖春游。则命题（则命题（4 4）可表示为）可表示为。（5 5）设：两个三角形全等；）设：两个三角形全等；：三角形的三条边全部相等。：三角形的三条边全部相等。则命题（则命题（5 5）可表示为）可表示为。例例3.23.2.4 4 解解(续续)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程332024/7/92024/7/9 为了不使句子产生混淆，作如下约定为了不使句子产生混淆，作如下约定，命题联结命题联结词之优先级词之优先级如下：如下：1.1.否定否定合取合取析取析取蕴涵蕴涵等价等价2.2.同同级级的的联联结结词词，按按其其出出现现的的先先后后次次序序(从从左左到右到右)3.3.若若运运算算要要求求与与优优先先次次序序不不一一致致时时，可可使使用用括括号号；同同级级符符号号相相邻邻时时，也也可可使使用用括括号号。括括号号中的运算为最优先级中的运算为最优先级。约约 定定电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程342024/7/92024/7/9设命题设命题P P：明天上午七点下雨；：明天上午七点下雨；Q Q：明天上午七点下雪；：明天上午七点下雪；R R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句：1)1)如果如果明天上午七点明天上午七点不不是雨是雨夹夹雪，雪，则则我将去学校我将去学校2)2)如果如果明天上午七点明天上午七点不不下雨下雨并且并且不不下雪，下雪，则则我将去我将去学校学校3)3)如果如果明天上午七点下雨明天上午七点下雨或或下雪，下雪，则则我将我将不不去学校去学校4)4)明天上午我将明天上午我将雨雪无阻雨雪无阻一定去学校一定去学校可符号化为：可符号化为：(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)。或或(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)R(PQ)R。例例3.23.2.5 5可符号化为：可符号化为：(PQ)R(PQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程352024/7/92024/7/9例例3.23.2.6 6设命题设命题P P：你陪伴我；：你陪伴我；Q Q：你代我叫车子；：你代我叫车子；R R：我将出去。：我将出去。符号化下述语句：符号化下述语句：除非除非你陪伴我或代我叫车子，你陪伴我或代我叫车子，否则否则我将我将不不出去出去 如果如果你陪伴我你陪伴我并且并且代我叫辆车子，代我叫辆车子，则则我将出去我将出去 如果如果你你不不陪伴我陪伴我或或不不代我叫辆车子，我将代我叫辆车子，我将不不出去出去R(PQ)R(PQ)或或 (PQ)RPQ)R(PQ)RPQ)R(PQ)RPQ)R电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程362024/7/92024/7/9例例设设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+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电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程372024/7/92024/7/93.2.4 3.2.4 命题联结词的应用命题联结词的应用例例 3.2.7 3.2.7 用复合命题表示如下图所示的开关用复合命题表示如下图所示的开关电路电路：图图3.3.2.12.1 图图3 3.2 2.2 .2 图图3 3.2 2.3.3ABABABABA A设：设：开关闭合；：开关闭合。：开关闭合；：开关闭合。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程382024/7/92024/7/9用复合命题表示如下图所示的逻辑电路用复合命题表示如下图所示的逻辑电路：例例 3.2.8 3.2.8图图3.2.43.2.4 图图3.2.53.2.5 图图3.2.63.2.6P P Q QP PQ QP P解解:设设P P：输入端为高电位：输入端为高电位,Q,Q：输入端为高电位：输入端为高电位,则则 “与门与门”对应于对应于PQPQ；“或门或门”对应于对应于PQPQ；“非门非门”对应于对应于P P。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程392024/7/92024/7/93.3 3.3 命题公式、解释与真值表命题公式、解释与真值表定义定义3.3.13.3.1 一个特定的命题是一个一个特定的命题是一个常值命题常值命题，它不是它不是具有值具有值“T T”(“1 1”)，就是具有值，就是具有值“F F”(“0 0”)。而一个任意的没有赋予具体内容的原子命题是一个变而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为量命题，常称它为命题变量命题变量(或或命题变元命题变元)，该命题变该命题变量无具体的真值，它的变域是集合量无具体的真值，它的变域是集合 T T，F F(或或00，11)注意注意(1)(1)复合命题为命题变元的复合命题为命题变元的“函数函数”,其其函数值仍为函数值仍为 真真 或或“假假”值值。(2)(2)真值函数或命题公式真值函数或命题公式，没有确没有确切切真值真值。真值函数真值函数电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程402024/7/92024/7/93.3.13.3.1命题公式命题公式定义定义3.3.2(3.3.2(命题公式命题公式)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、等表示。等表示。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程412024/7/92024/7/9符号串：符号串：(P(QRP(QR)(QQ(SRSR)；(PQPQ)；(PP(PQPQ)；(PQPQ)(RQRQ)(PRPR)。等都是命题公式。等都是命题公式。例例3 3.3.13.1例例3.3.23.3.2符号串：符号串：(PQPQ)QQ)；(PQPQ；(PQPQ(R R；PQPQ。等都不是合法的命题公式。等都不是合法的命题公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程422024/7/92024/7/9例例3.3.33.3.3试用符号形式写出下列命题：试用符号形式写出下列命题：（1 1）虽然今天天气晴朗，老陈还是不来；）虽然今天天气晴朗，老陈还是不来；（2 2）除非你陪伴我或代我叫车子，否则我将不出去；）除非你陪伴我或代我叫车子，否则我将不出去；（3 3）停机的原因在于语法错误或者程序错误；）停机的原因在于语法错误或者程序错误；（4 4）若）若a a和和b b是偶数，则是偶数，则a+ba+b是偶数；是偶数；（5 5）我们要做到身体好、学习好、工作好，为祖国四）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。化建设而奋斗。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程432024/7/92024/7/9例例3.3.3 3.3.3 解解（1 1）P P：今天天气晴朗：今天天气晴朗,Q,Q：老陈要来：老陈要来,则有：则有：PQPQ；（2 2）P P：你陪伴我；：你陪伴我；Q Q：你代我叫车子；：你代我叫车子；R R：我出去。：我出去。则有：则有：RPQRPQ或或PQRPQR；（3 3）P P：停机的原因在于语法错误，：停机的原因在于语法错误，Q Q：停机的原因在：停机的原因在于程序错误，于程序错误，则有：则有：PQPQ；（4 4）P P：a a是偶数；是偶数；Q Q：b b是偶数，是偶数，R R：a+ba+b是偶数，是偶数，则有：则有：PQRPQR；（5 5）P P：我们要做到身体好：我们要做到身体好,Q,Q：我们要做到学习好：我们要做到学习好,R,R：我们要做到工作好，：我们要做到工作好，S S：我们要为祖国四化建设而奋：我们要为祖国四化建设而奋斗，斗，则有：则有：PQRPQR S S。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程442024/7/92024/7/9公式公式(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.43.3.4电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程452024/7/92024/7/93.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在解释下是真的，则称在解释下是真的，则称满足满足G G；如；如果果G G在解释下是假的，则称在解释下是假的，则称弄假弄假G G。定义定义3.3.43.3.4 将将公式公式G G在其所有可能解释下在其所有可能解释下的的真值情况真值情况列成列成的表，称为的表，称为G G的的真值表真值表。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程462024/7/92024/7/9例例3 3.3.53.5求下面公式的真值表：求下面公式的真值表：(P(P(P PQ)R)QQ)R)Q 其中，、是的所有命题变元。其中，、是的所有命题变元。PQR P PQ(PQ)RP(PQ)R)G0001001100110011010110110111111110001000101011111100000111100001电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程472024/7/92024/7/9例例3 3.3.53.5（续）（续）PQR(P(PQ)R)Q00010011010101111000101111011111进一步化简为：进一步化简为：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程482024/7/92024/7/9例例3.3.63.3.6PQ()()()(Q)00100011001010011110求下面这组公式的真值表：求下面这组公式的真值表：1 1 ()；2 2()；3 3 ()(Q)Q)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程492024/7/92024/7/9从这三个真值表可以看到一个非常有趣的事实：从这三个真值表可以看到一个非常有趣的事实：公式公式G G1 1对所有可能的解释具有对所有可能的解释具有“真真”值值公式公式G G3 3对所有可能的解释均具有对所有可能的解释均具有“假假”值值公式公式G G2 2则具有则具有“真真”和和“假假”值值结论结论电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程502024/7/92024/7/9定义定义3.3.53.3.51.1.公式公式G G称为称为永真公式永真公式(重言式重言式)，如果在它的所有，如果在它的所有解释之下都为解释之下都为“真真”。2.2.公式公式G G称为称为永假公式永假公式(矛盾式矛盾式),),如果在它的所有如果在它的所有解释之下都为解释之下都为“假假”。3.3.公式公式G G称为称为可满足的可满足的，如果它不是永假的。，如果它不是永假的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程512024/7/92024/7/9从上述定义可知三种特殊公式之间的关系：从上述定义可知三种特殊公式之间的关系：1)1)永真式永真式G G的否定的否定 G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定 G G是是永真式。永真式。2)2)永真式一定是可满足式永真式一定是可满足式,可满足式不一定是永真式可满足式不一定是永真式3)3)可满足式的否定不一定为不可满足式可满足式的否定不一定为不可满足式(即为矛盾式即为矛盾式)结论结论电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程522024/7/92024/7/9例例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。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程532024/7/92024/7/9例例3.3.7 3.3.7 解解PQ()()(Q)(Q)(Q)(PQ)Q00101011011010111100永真公式永真公式永假公式永假公式可满足公式可满足公式三个公式的真值表如下：三个公式的真值表如下：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程542024/7/92024/7/9若将其看成两个公式，分别令：若将其看成两个公式，分别令：，。则则是一个永真公式，即这两个公式对任何是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为解释都必同为真假，此时，说和相等，记为。为此可定义：。为此可定义：分析公式（分析公式（1 1）定义定义3 3.3.63.6 设设G G、H H是是公式，公式，如果在任意解释下，如果在任意解释下，G G与与H H的的真值相同，则称公式真值相同，则称公式G G、H H是是等价的等价的，记作记作G GH H。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程552024/7/92024/7/9公式公式G G、H H等价等价的充分必要条件是公式的充分必要条件是公式G GH H是永真公式是永真公式证明证明:“”假定假定G G，H H等价，则等价，则G G，H H在其任意解释在其任意解释下或同为真或同为假，于是由下或同为真或同为假，于是由“”的意义知，的意义知，G GH H在其任何的解释下，其真值为在其任何的解释下，其真值为“真真”，即，即G GH H为永为永真公式。真公式。“”假定公式假定公式G GH H是永真公式，是它的任意解释，是永真公式，是它的任意解释，在下，在下，G GH H为真，因此，为真，因此，G G、H H或同为真，或同为假，或同为真，或同为假，由于的任意性，故有由于的任意性，故有G GH H。定理定理3 3.3.13.1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程562024/7/92024/7/9 首先，双条件词首先，双条件词“”是一种逻辑联结词，公式是一种逻辑联结词，公式G GH H是命题公式，其中是命题公式，其中“”是一种逻辑运算，是一种逻辑运算，G GH H的结果仍是一个命题公式的结果仍是一个命题公式。而逻辑等价而逻辑等价“”则是描则是描述了两个公式述了两个公式G G与与H H之间的一种逻辑等价关系，之间的一种逻辑等价关系，G GH H表表示示“命题公式命题公式G G等等价价于命题公式于命题公式H H”，G GH H 的结果的结果不不是命题公式是命题公式。其次，如果要求用计算机来判断命题公式其次，如果要求用计算机来判断命题公式G G、H H是是否逻辑等价，即否逻辑等价，即G GH H那是办不到的那是办不到的，然而计算机却可然而计算机却可“计算计算”公式公式G GH H是否是永真公式。是否是永真公式。“”与与“”的区别的区别电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程572024/7/92024/7/9“=”=”的性质的性质由于由于“=”不是一个联结词，而是一种关系，为此，不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：这种关系具有如下三个性质：（1 1）自反性）自反性 G=GG=G；（2 2）对称性）对称性 若若G=HG=H，则，则H=GH=G；（3 3）传递性）传递性 若若G=HG=H，H=SH=S，则，则G=SG=S。这三条性质体现了这三条性质体现了“=”的实质含义。的实质含义。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程582024/7/92024/7/93.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)为永真公式。为永真公式。PQG3()(Q)(Q)0011111010110010010011111111电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程592024/7/92024/7/9设设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 (吸收律吸收律)8 8：G(GH)G(GH)G G电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程602024/7/92024/7/95)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：GGGG0 0(矛盾律矛盾律)基本等价公式（续）基本等价公式（续）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程612024/7/92024/7/9基本等价公式（续）基本等价公式（续）10)10)1717：(G)(G)G G (双重否定律双重否定律)11)11)1818：(GH)(GH)GH GH (De(De MoRGanMoRGan定律定律)1919：(GH)(GH)GHGH。12)12)2020:(G(GH)H)(GH)(HGGH)(HG)(等价等价)13)13)2121：(GH)(GH)(GH)(GH)(蕴涵蕴涵)14)14)E E2222：G G G G。(假言易位假言易位)15)15)E E2323：G G G G。(等价否定等式等价否定等式)16)16)E E2424：(G(G )(G)(G)G G (归谬论归谬论)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程622024/7/92024/7/9这种图是将这种图是将G G，H H理解为某总体论域上的子集合，而理解为某总体论域上的子集合，而规定规定GHGH为两集合的公共部分为两集合的公共部分（交集合），（交集合），GHGH为为两集合的全部两集合的全部（并集合），（并集合），G G为总体论域（如矩为总体论域（如矩形域）中形域）中G G的的补集，补集，将命题中的真值将命题中的真值“1 1”理解为集理解为集合中的总体论域（全集），将命题中的真值合中的总体论域（全集），将命题中的真值“0 0”理解为集合中的空集，则有：理解为集合中的空集，则有：GH GH GGH GH GUABUABUA命题与集合之间的关系命题与集合之间的关系电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程63“”“”对对“”与与“”“”对对“”的对比的对比等幂律等幂律;GGGGG GGG GGG G交换律交换律=GHGHHGHG GH GHHGHG结合律结合律A(BC)=(AB)CA(BC)=(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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程642024/7/92024/7/9设设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)为任意的命为任意的命题公式，题公式，分别分别用用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(代入定理代入定理)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程652024/7/92024/7/9例例3.3.93.3.9设设(,)()，证明公式，证明公式G G是一个永真公式。另有两个任意公式：是一个永真公式。另有两个任意公式：(,)()；(,)()。进一步验证代入定理的正确性。进一步验证代入定理的正确性。解解 建立公式建立公式G G的真值表如的真值表如右所示。可见右所示。可见为永真公式。为永真公式。PQ()001011101111电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程662024/7/92024/7/9例例3.3.93.3.9（续）（续）将，代入到中分别取代将，代入到中分别取代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)的真值表。的真值表。PQ()()()()00111111110010000010101011011001011101101111电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程672024/7/92024/7/9定理定理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 1H H1 1，则则G GH H。利用利用2424个基本等价公式及代入定理和替换定个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。理，可完成公式的转化和等价判定。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程682024/7/92024/7/9例例3.3.103.3.10利用基本的等价关系，完成如下工作：利用基本的等价关系，完成如下工作：（1 1）判断公式的类型：）判断公式的类型：证明证明 ()()()()()()是一个永真公式。是一个永真公式。（2 2）证明公式之间的等价关系：）证明公式之间的等价关系：证明证明()=()=()（3 3）化简公式：）化简公式：证明证明(P(P(R)(R)(R)(PR)=R R)(PR)=R 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程692024/7/92024/7/9例例3.3.10 3.3.10 证明证明（1 1）()()()()()=(=()()()()()()=(=()()()()()()()()=(=()()()()()()()()=(=()()()()()()=T)=T 即即:()()()()()()为永真公式；为永真公式；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程702024/7/92024/7/9例例3.3.10 3.3.10 证明（续）证明（续）（2 2）P P(Q(QR)=R)=P P(Q(QR)=R)=P P(Q QR)R)=(=(P P Q)R=Q)R=(P(PQ)R=(PQ)R=(PQ)RQ)R 即有即有:P P(Q(QR)=(PR)=(PQ)RQ)R；（3 3）(P(P(QR)(QR)(PR)QR)(QR)(PR)=(=(PP Q)R)(QP)R)Q)R)(QP)R)=(=(PQ)R)(QP)R)(PQ)R)(QP)R)=(=(PQ)(QP)R(PQ)(QP)R =TR=R =TR=R 即有即有:(P(P(QR)(QR)(PR)=RQR)(QR)(PR)=R。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程712024/7/92024/7/93.3.6 3.3.6 命题公式的应用命题公式的应用例例3.3.113.3.11 利用基本的等价关系，化简下列电路图利用基本的等价关系，化简下列电路图&11&TSRQPRPSQPSPQRP解：解：上述电路图可描述为：上述电路图可描述为：（1 1）(PQR)(PQS)(PR)(PS)(PQR)(PQS)(PR)(PS)（2 2）(PQR)(PQS)(PST)(PQR)(PQS)(PST)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程722024/7/92024/7/9例例3.3.113.3.11（续）（续）利用利用2424个基本等价关系，化简公式个基本等价关系，化简公式(1)(1)、(2)(2)可得：可得：（1 1）(PQR)(PQS)(PR)(PS)(PQR)(PQS)(PR)(PS)=(PQ(RS)(P(RS)=(PQ(RS)(P(RS)=PQ(RS)=PQ(RS)；（2 2）(PQR)(PQS)(PST)(PQR)(PQS)(PST)=(PQS)(PST)=PST =(PQS)(PST)=PST。SRQPPSQ&电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程732024/7/92024/7/9例例3.3.123.3.12将下面程序语言进行化简。将下面程序语言进行化简。If A then if B then X else Y else if B then X else YIf A then if B then X else Y else if B then X else Y TFFTFTStartStartAXYEndBB 解：解：执行执行X X的条件为：的条件为：()()()执行执行Y Y的条件为：的条件为：()()()电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程742024/7/92024/7/9例例3.3.12(3.3.