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

1、广东工业大学计算机学院广东工业大学计算机学院离散数学离散数学离离 散散 数数 学学离离 散散 数数 学学蔡瑞初蔡瑞初2第二篇第二篇 数理逻辑数理逻辑先看著名物理学家爱因斯坦出过的一道题：先看著名物理学家爱因斯坦出过的一道题：一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶

2、帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来的呢？3第二篇第二篇 数理逻辑数理逻辑要回答这样的问题，实际上就是看由一些诸如要回答这样的问题，实际上就是看由一些诸如“商商人戴的是红帽子人戴的是红帽子”这样的前提能否推出这样的前提能否推出“猜出答案猜出答案的应试者戴的是黑帽子的应试者戴的是黑帽子”这样的结论来。这又需要这样的结论来。这又需要经历如下过程：经历如下过程：(1) (1) 什么是前提？有哪些前提？什么是前提？有哪些前提？(2) (2) 结论是什么？结

3、论是什么？(3) (3) 根据什么进行推理？根据什么进行推理？(4) (4) 怎么进行推理？怎么进行推理？42022-3-112022-3-11数理逻辑（数理逻辑（Mathematical LogicMathematical Logic） 是研究演绎推理的一门学科，用是研究演绎推理的一门学科，用数学的数学的方法方法来研究来研究推理的规律推理的规律统称为数理逻辑。统称为数理逻辑。第二篇第二篇 数理逻辑数理逻辑52022-3-112022-3-11主要研究内容：主要研究内容：推理推理 着重于着重于推理过程是否正确推理过程是否正确 着重于着重于语句之间的关系语句之间的关系主要研究方法：主要研究方法：

4、数学的方法数学的方法 就是引进一套符号体系的方法，所以数就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（理逻辑又叫符号逻辑（Symbolic LogicSymbolic Logic）。）。 第二篇第二篇 数理逻辑数理逻辑62022-3-112022-3-11什么是数理逻辑什么是数理逻辑 ？用数学的方法来研究推理的规律统称为数理逻辑。用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？为什么要研究数理逻辑？程序算法数据程序算法数据算法逻辑控制算法逻辑控制总结总结72022-3-112022-3-11第二篇第二篇 数理逻辑数理逻辑命题逻辑命题逻辑 命题的基本概念命题的基本概念命

5、题联结词命题联结词命题公式命题公式命题的范式命题的范式 主要研主要研 究内容究内容谓词逻辑谓词逻辑谓词的基本概念谓词的基本概念谓词公式谓词公式公式的标准型公式的标准型推理与证明技术推理与证明技术命题逻辑推理理论命题逻辑推理理论谓词逻辑推理理论谓词逻辑推理理论数学归纳法数学归纳法按定义证明法按定义证明法82022-3-112022-3-11第三章第三章 命题逻辑命题逻辑 命题逻辑也称命题演算，或语句逻辑。命题逻辑也称命题演算，或语句逻辑。 研究内容：研究内容： （1 1）研究以）研究以命题为基本单位命题为基本单位构成的构成的前提和结论前提和结论之间的可推导关系之间的可推导关系 （2 2）研究）研

6、究什么是命题什么是命题？ （3 3）研究）研究如何表示命题如何表示命题？ （4 4）研究）研究如何由一组前提推导一些结论如何由一组前提推导一些结论？92022-3-112022-3-11第三章第三章 命题逻辑命题逻辑 命题逻辑的命题逻辑的特征：特征： 在研究逻辑的形式时，我们在研究逻辑的形式时，我们把一个命题只把一个命题只分析到其中所含的命题成份为止，不再分析下分析到其中所含的命题成份为止，不再分析下去去。不把一个简单命题再分析为非命题的集合，。不把一个简单命题再分析为非命题的集合，不把不把谓词谓词和和量词量词等非命题成份分析出来。等非命题成份分析出来。 102022-3-112022-3-1

7、1第三章第三章 命题逻辑命题逻辑集合的表示方法集合的表示方法2命题公式命题公式3命题范式命题范式4命题基本概念命题基本概念1命题联结词命题联结词2112022-3-112022-3-113.1 3.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1、五种基本、五种基本联结词联结词2 2、2424个个基本基本的等价公式的等价公式3 3 掌握求命题掌握求命题范式的方法范式的方法3联结词完备集联结词完备集的理解和学习的理解和学习2公式的代入规公式的代入规则和替换规则则和替换规则122022-3-112022-3-113.2.1 3.2.1 命题命题定义定义3.2.13.2.

8、1具有具有确切真值确切真值的陈述句称为的陈述句称为命题命题, , 该命题可以取一个该命题可以取一个“值值”，称为，称为真值真值。真值只有真值只有“真真”和和“假假”两种，两种，分别用分别用“”( (或或“”) )和和“”( (或或“”) )表示。表示。3.2 3.2 命题与命题联结词命题与命题联结词132022-3-112022-3-11（1 1）太阳是圆的；）太阳是圆的； （2 2）成都是一个旅游城市；）成都是一个旅游城市；（3 3）北京是中国的首都；）北京是中国的首都；（4 4）这个语句是假的；）这个语句是假的；（5 5）1 11 11010；（6 6）+y+y；（7 7）我喜欢踢足球；）

9、我喜欢踢足球；（8 8）3 3能被能被2 2整除；整除；（9 9）地球外的星球上也有人；）地球外的星球上也有人；（1010）中国是世界上人口最多的国家；）中国是世界上人口最多的国家；（1111）今天是晴天；）今天是晴天；例例3.2.13.2.1TTT/F非命题非命题T/FFT/FTTT非命题非命题142022-3-112022-3-11例例3.2.13.2.1（续）（续）（1212）把门关上；）把门关上；（1313）滚出去！）滚出去！（1414）你要出去吗？）你要出去吗？（1515）今天天气真好啊！）今天天气真好啊！非命题非命题非命题非命题非命题非命题非命题非命题注意：注意：一切没有判断内容的

10、句子都不能作为命题一切没有判断内容的句子都不能作为命题，如命令，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。句、感叹句、疑问句、祈使句、二义性的陈述句等。 152022-3-112022-3-11命题一定是陈述句，但并非一切陈述句都是命题。命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠命题的真值有时可明确给出，有时还需要依靠环境、环境、条件、实际情况时间条件、实际情况时间才能确定其真值。才能确定其真值。结论：结论：在数理逻辑中像在数理逻辑中像字母字母“x x”、“y y”、“z z”等字母总等字母总是表示是表示变量。变量。约定：约定：162022-

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

12、解为更为简单命题为更为简单命题的命题。的命题。复合命题复合命题：可以：可以分解分解为更为简单命题的命题。而且为更为简单命题的命题。而且这些简单命题之间是通过如这些简单命题之间是通过如“或者或者”、“并并且且”、“不不”、“如果如果.则则.”、“当且仅当且仅当当”等这样的关联词和标点符号复合而构成一等这样的关联词和标点符号复合而构成一个复合命题。个复合命题。命题的分类命题的分类182022-3-112022-3-11今天天气很冷。今天天气很冷。今天天气很冷并且刮风。今天天气很冷并且刮风。今天天气很冷并且刮风，但室内暖和。今天天气很冷并且刮风，但室内暖和。例例3.2.33.2.3 通常用通常用大写

13、的带或不带下标的英文字母大写的带或不带下标的英文字母、.P.P、Q Q、R R、. . A Ai i、B Bi i 、C Ci i、.P.Pi i、Q Qi i、R Ri i、.等表示命题等表示命题192022-3-112022-3-113.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.

14、合取合取 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 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：北京是中国的首都：北京是中国的首都202022-3-112022-3-

15、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 1212022-3-112022-3-11说明说明1 1、联结词是句子与句子之间的联结，而非单纯的联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；名词、形容词、数词等地联结；2 2、联结词是两个句子真值之间的联结，而非句子联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何的具体含义的联结，两个句子之间可以无任何地内在

16、联系；地内在联系；222022-3-112022-3-11说明说明3 3、联结词与自然语言之间的对应联结词与自然语言之间的对应并非一一对应并非一一对应；联结词联结词自然语言自然语言既既又又、不仅、不仅而且而且、虽然、虽然但但是是、并且、和、与，等等；、并且、和、与，等等；如如P P则则Q Q、只要、只要P P就就Q Q、P P仅当仅当Q Q、只有、只有Q Q才才P P、除非除非Q Q否则否则 P P，等等，等等等价、当且仅当、充分必要、等等；等价、当且仅当、充分必要、等等； 相容（可兼）的或相容（可兼）的或232022-3-112022-3-11符号化下列命题符号化下列命题（1 1）四川）四川

17、不不是人口最多的省份；是人口最多的省份；（2 2）王超是一个）王超是一个德智体德智体全面发展的好学生；全面发展的好学生；（3 3）教室的灯不亮可能是灯管坏了）教室的灯不亮可能是灯管坏了或者或者是停电了；是停电了；（4 4）如果如果周末天气晴朗，周末天气晴朗，那么那么学院将组织我们到学院将组织我们到石像湖春游；石像湖春游；（5 5）两个三角形全等）两个三角形全等当且仅当当且仅当三角形的三条边全三角形的三条边全部相等。部相等。例例3.23.2. .4 4242022-3-112022-3-11例例3.23.2. .4 4 解解（1 1）设：四川是人口最多的省份。）设：四川是人口最多的省份。 则命题

18、（则命题（1 1）可表示为）可表示为。（2 2）设：王超是一个思想品德好的学生；）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生；：王超是一个学习成绩好的学生； R R：王超是一个体育成绩好的学生。：王超是一个体育成绩好的学生。 则命题（则命题（2 2）可表示为）可表示为R R。（3 3）设：教室的灯不亮可能是灯管坏了）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了：教室的灯不亮可能是停电了 则命题（则命题（3 3）可表示为）可表示为。252022-3-112022-3-11（4 4）设：周末天气晴朗；）设：周末天气晴朗； ：学院将组织我们到石像湖春游。：学院将组织

19、我们到石像湖春游。 则命题（则命题（4 4）可表示为）可表示为。（5 5）设：两个三角形全等；）设：两个三角形全等； ：三角形的三条边全部相等。：三角形的三条边全部相等。 则命题（则命题（5 5）可表示为）可表示为。例例3.23.2. .4 4 解解( (续续) )262022-3-112022-3-11 为了不使句子产生混淆，作如下约定为了不使句子产生混淆，作如下约定，命题联结命题联结词之优先级词之优先级如下：如下：1.1. 否定否定合取合取析取析取蕴涵蕴涵等价等价2.2. 同级的联结词，按其出现的先后次序同级的联结词，按其出现的先后次序( (从左从左到右到右) )3.3. 若运算要求与优先

20、次序不一致时，可使用若运算要求与优先次序不一致时，可使用括号括号；同级符号相邻时，也可使用括号。；同级符号相邻时，也可使用括号。括号中的运算为最优先级括号中的运算为最优先级。约约 定定272022-3-112022-3-11设命题设命题P P：明天上午七点下雨；：明天上午七点下雨； Q Q：明天上午七点下雪；：明天上午七点下雪； R R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句：如果如果明天上午七点明天上午七点不不是雨是雨夹夹雪，雪，则则我将去学校我将去学校如果如果明天上午七点明天上午七点不不下雨下雨并且并且不不下雪，下雪，则则我将去学我将去学校校如果如果明天上午七点下雨明天上

21、午七点下雨或或下雪，下雪，则则我将我将不不去学校去学校明天上午我将明天上午我将雨雪无阻雨雪无阻一定去学校一定去学校可符号化为：可符号化为：(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)RPQ)R。可符号化为可符号化为:(PQ)R:(PQ)R。282022-3-112022-3-11例例3.23.2. .6 6设命题设命题P P：你陪伴我；：你陪伴我； Q Q：你代我叫车子；

22、：你代我叫车子； R R：我将出去。：我将出去。 符号化下述语句：符号化下述语句： 除非除非你陪伴我或代我叫车子，你陪伴我或代我叫车子，否则否则我将我将不不出去出去 如果如果你陪伴我你陪伴我并且并且代我叫辆车子，代我叫辆车子，则则我将出去我将出去 如果如果你你不不陪伴我陪伴我或或不不代我叫辆车子，我将代我叫辆车子，我将不不出去出去R(PQ) R(PQ) 或或 (PQ)RPQ)R( (PQ)RPQ)R(PQ)RPQ)R292022-3-112022-3-11例例设设P:P:雪是白色的雪是白色的;Q:2+2=4;Q:2+2=4。将下列命题符号化：。将下列命题符号化：（1 1）因为雪是白色的，所以）

23、因为雪是白色的，所以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 Q302022-3-1120

24、22-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：输入端为高电位：输入端为高电位, ,则则 “与门与门”对应于对应于PQPQ； “或门或门”对应于对应于PQPQ； “非门非门”对应于对应于P P。312022-3-112022-3-113.3 3.3 命题公式、解释与真值表命题公式、解释与真值表定义定义3.3.13.3.1 一个特定的命题是一个一个特定的命

25、题是一个常值命题常值命题，它不是它不是具有值具有值“T T”( (“1 1”) )，就是具有值，就是具有值“F F”( (“0 0”) )。而一个任意的没有赋予具体内容的原子命题是一个变而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为量命题，常称它为命题变量命题变量( (或或命题变元命题变元) )，该命题变该命题变量无具体的真值，它的变域是集合量无具体的真值，它的变域是集合 T T，F F ( (或或00，11) )注意注意(1)(1)复合命题为命题变元的复合命题为命题变元的“函数函数”, ,其其函数值仍为函数值仍为 真真 或或“假假”值值。(2)(2)真值函数或命题公式真值函数

26、或命题公式，没有确没有确切切真值真值。真值函数真值函数322022-3-112022-3-113.3.13.3.1命题公式命题公式定义定义3.3.2 (3.3.2 (命题公式命题公式) )命题变元本身是一个公式；命题变元本身是一个公式；如如G G是公式，则是公式，则(G)(G)也是公式；也是公式；如如G G，H H是公式，则是公式，则(GH)(GH)、(GH)(GH)、(GH)(GH)、(G(GH H) )也是公式；也是公式；仅由有限步使用规则仅由有限步使用规则1-31-3后产生的结果。该公式常后产生的结果。该公式常用符号用符号G G、H H、等表示。等表示。332022-3-112022-3

27、-11符号串：符号串： (QR(QR) ), ,( (P(QRP(QR) SS, , ( (SRSR) ), , ( (QQ( (SRSR) (P(QRP(QR)( (QQ( (SRSR)；等都是命题公式。等都是命题公式。例例3 3. .3.13.1例例3.3.23.3.2符号串：符号串：( (PQPQ) )QQ) )； ( (PQPQ；( (PQPQ( (R R； PQPQ。等都不是合法的命题公式。等都不是合法的命题公式。342022-3-112022-3-113.3.2 3.3.2 公式的解释与真值表公式的解释与真值表定义定义3.3.3 3.3.3 设设P P1 1、P P2 2、P Pn

28、 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在其所有可能解释下在其所有可能解释下的的真值情况真值情况列成列成的表，称为的表，称为

29、G G的的真值表真值表。352022-3-112022-3-11例例3 3. .3.53.5求下面公式的真值表：求下面公式的真值表： (P(P( P PQ)R)QQ)R)Q 其中，、是的所有命题变元。其中，、是的所有命题变元。P Q R P PQ( PQ)RP( PQ)R)G0 0 0 10 0 110 0 1 10 0 110 1 0 1 1 0 1 10 1 1 1 1 1 111 0 0 0 1 0 001 0 1 0 1 1 111 1 0 0 0 0 011 1 1 0 0 0 01362022-3-112022-3-11例例3 3. .3.53.5（续）（续）P Q R(P( PQ

30、)R)Q0 0 0 1 1 0 0 1 1 1 0 0 10 0 1 1 1 0 0 1 1 1 0 0 10 1 0 1 1 1 0 1 1 1 1 0 10 1 1 1 1 1 1 1 1 1 1 1 11 0 0 0 0 1 0 0 0 0 1 0 01 0 1 1 0 1 1 1 1 0 1 1 11 1 0 0 0 0 0 1 0 0 0 0 11 1 1 0 0 0 0 1 0 0 0 0 1化简表示：化简表示：372022-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

31、 0 111 1 011 1 1 1进一步化简为：进一步化简为：382022-3-112022-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)。392022-3-112022-3-11从这三个真值表可以看到一个非常有趣的事实：从这三个真值表可以看到一个非常有趣的事实： 公式公式G G1 1对所有可能的解释具有对所有可能的解释具有“真真”值值 公式公式G G3 3对所有可能的解释均具

32、有对所有可能的解释均具有“假假”值值 公式公式G G2 2则具有则具有“真真”和和“假假”值值结论结论402022-3-112022-3-11定义定义3.3.53.3.5公式公式G G称为称为永真公式永真公式( (重言式重言式) )，如果在它的所有解，如果在它的所有解释之下都为释之下都为“真真”。公式公式G G称为称为永假公式永假公式( (矛盾式矛盾式),),如果在它的所有解释如果在它的所有解释之下都为之下都为“假假”。公式公式G G称为称为可满足的可满足的，如果它不是永假的。，如果它不是永假的。412022-3-112022-3-11从上述定义可知三种特殊公式之间的关系：从上述定义可知三种特

33、殊公式之间的关系：1)1) 永真式永真式G G的否定的否定 G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定 G G是是永真式。永真式。2)2) 永真式一定是可满足式永真式一定是可满足式, ,可满足式不一定是永真式可满足式不一定是永真式3)3) 可满足式的否定不一定为不可满足式可满足式的否定不一定为不可满足式( (即为矛盾式即为矛盾式) )结论结论422022-3-112022-3-11例例3.3.73.3.7写出下列公式的真值表，并验证其公式是重言式、写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。矛盾式、可满足公式。（1 1）G G1 1=(=() )( ( ) )

34、；（2 2）G G2 2=(=(Q)Q)( ( ( (Q)Q) (Q(Q)；（3 3）G G3 3=(P=(P Q)Q) Q Q。432022-3-112022-3-11例例3.3.7 3.3.7 解解P Q() ( )( Q) (Q) (Q) (PQ) Q0 01 0 10 11 0 11 0 1 0 11 11 0 0永真公式永真公式永假公式永假公式可满足公式可满足公式三个公式的真值表如下：三个公式的真值表如下：442022-3-112022-3-11若将其看成两个公式，分别令：若将其看成两个公式，分别令： ， 。则则是一个永真公式，即这两个公式对任何是一个永真公式，即这两个公式对任何解释

35、都必同为真假，此时，说和相等，记为解释都必同为真假，此时，说和相等，记为。为此可定义：。为此可定义：分析公式（分析公式（1 1）定义定义3 3. .3.63.6 设设G G、H H是是公式，公式，如果在任意解释如果在任意解释下，下，G G与与H H的的真值相同，则称公式真值相同，则称公式G G、H H是是等价的等价的，记作记作G GH H。452022-3-112022-3-11公式公式G G、H H等价等价的充分必要条件是公式的充分必要条件是公式G GH H是永真公式是永真公式证明证明: :“”假定假定G G，H H等价，则等价，则G G，H H在其任意解释在其任意解释下或同为真或同为假，于

36、是由下或同为真或同为假，于是由“”的意义知，的意义知，G GH H在其任何的解释下，其真值为在其任何的解释下，其真值为“真真”，即，即G GH H为永真公式。为永真公式。“”假定公式假定公式G GH H是永真公式，是它的任意解释，是永真公式，是它的任意解释，在下，在下，G GH H为真，因此，为真，因此，G G、H H或同为真，或同为假，或同为真，或同为假，由于的任意性，故有由于的任意性，故有G GH H。定理定理3 3. .3.13.1462022-3-112022-3-11 首先，双条件词首先，双条件词“”是一种逻辑联结词，公式是一种逻辑联结词，公式G GH H是命题公式，其中是命题公式，

37、其中“”是一种逻辑运算，是一种逻辑运算，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是否是永真公式。是否是永真

38、公式。 “” 与与“”的区别的区别472022-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。这三条性质体现了这三条性质体现了“= =”的实质含义。的实质含义。 482022-3-112022-3-113.3.4 3.3.4 命题公式的基本等价关系命题公式的基本等价关系例例

39、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 1 1 1 1 1492022-3-112022-3-11设设G G，H H，S S是任何的公式，则：是任何的公式，则：基本等价公式基本等价公式1) 1) 1 1：GGGG

40、G 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 G502022-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)

41、6) 1111：GGG G( (同一律同一律) ) 1212：GGG G 7) 7) 1313：GG( (零律）零律） 1414：GG8) 8) 1515：GGGG1 1( (排中律排中律) )9) 9) 1616：GGGG0 0( (矛盾律矛盾律) )基本等价公式（续）基本等价公式（续）512022-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) 1

42、2) 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 ( (归谬论归谬论) )522022-3-112022-3-11这种图是将这种图是将G G，H H理解为某总体论域上的子集合，而理解为某总体论域上的子集合，而规定规定GHGH为两集合的公

43、共部分为两集合的公共部分（交集合），（交集合），GHGH为为两集合的全部两集合的全部（并集合），（并集合），G G为总体论域（如矩为总体论域（如矩形域）中形域）中G G的的补集，补集，将命题中的真值将命题中的真值“1 1”理解为集理解为集合中的总体论域（全集），将命题中的真值合中的总体论域（全集），将命题中的真值“0 0”理解为集合中的空集，则有：理解为集合中的空集，则有： GH GH GUABUABUA命题与集合之间的关系命题与集合之间的关系53 “” 对对“”与与“”对对“”的对比的对比等幂律等幂律; ; GGGGG GGG GGG G交换律交换律= = = GHGHHGHG GH GHH

44、GHG结合律结合律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)=

45、(GH)(GS)G(HS)=(GH)(GS)AA 542022-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) )为任意的为任意的命题公式，命题公式，分别分别用用G G1 1、G G2 2、G Gn n取代取代G G中的中

46、的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(代入定理代入定理) )552022-3-112022-3-11例例3.3.93.3.9设设( (, , ) )( ( ()，证明公，证明公式式G G是一个永真公式。另有两个任意公式：是一个永真公式。另有两个任意公式： (

47、(, , ) )( ( ) )； ( (, , ) )( () )。 进一步验证代入定理的正确性。进一步验证代入定理的正确性。 解解 建立公式建立公式G G的真值表如的真值表如右所示。可见右所示。可见为永真公式。为永真公式。P Q()0 010 111 011 11562022-3-112022-3-11例例3.3.93.3.9（续）（续） 将，代入到中分别取代G中的命题变元P、Q，所得到的公式为： (P, Q) = G(H, S) = (H(HS)S = ()()()() 建立新公式(P, Q)的真值表。P Q( )( )()()0 0 1 1 1 1 1 1 1 1 00 1 0 0 0

48、0 0 1 0 1 01 0 1 1 0 1 1 0 0 1 01 1 1 0 1 1 0 1 1 1 1572022-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 1H H1 1，则则G GH H。利用利用2424个基本等价公式及代入定理和替换定个基本等价公式及代入定理和替换

49、定理，可完成公式的转化和等价判定。理，可完成公式的转化和等价判定。582022-3-112022-3-11例例3.3.103.3.10利用基本的等价关系，完成如下工作：利用基本的等价关系，完成如下工作：（1 1）证明公式之间的等价关系：）证明公式之间的等价关系：证明证明( () = () = ()（2 2）化简公式：）化简公式：证明证明( ( P(P( R)(R)(R)(PR) = R R)(PR) = R 592022-3-112022-3-11例例3.3.10 3.3.10 解答解答（1 1） P P(Q(QR)=R)= P P(Q(QR)=R)= P P( ( Q QR)R) =( =(

50、 P P Q)R=Q)R= (P(PQ)R=(PQ)R=(PQ)RQ)R 即有即有: : P P(Q(QR)=(PR)=(PQ)RQ)R； （2 2） ( ( 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。 602022-3-112022-3-113.3.6 3.3.6

51、命题公式的应用命题公式的应用例例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)612022-3-112022-3-113.3.6 3.3.6 命题公式的应用命题公式的应用将下面程序语言进行化简。将下面程序语言进行化简。If A then if B then X else Y else if B

52、then X else YIf A then if B then X else Y else if B then X else Y TFFTFTStartStartAXYEndBB 解：解：执行执行X X的条件为：的条件为： ( ()()( ) ) 执行执行Y Y的条件为：的条件为： ( ( )()( ) )622022-3-112022-3-11例例3.3.12(3.3.12(续）续） 执行执行X X的条件可化简为：的条件可化简为：( ()()( ) )( ( ) )执行执行Y Y的条件可化简为：的条件可化简为：( ( )()( ) ) ( ( ) ) TXYEndStartStartAF程

53、序可简化为：程序可简化为：If B then X else YIf B then X else Y 632022-3-112022-3-113.5 3.5 公式的标准型公式的标准型范式范式3.5.1 3.5.1 析取范式和合取范式析取范式和合取范式定义定义3.5.13.5.1 （1 1）命题变元或命题变元的否定称为）命题变元或命题变元的否定称为文字文字（2 2）有限个文字的析取称为）有限个文字的析取称为析取式析取式( (也称为也称为子句）子句）（3 3）有限个文字的合取称为）有限个文字的合取称为合取式合取式( (也称为也称为短语）短语）（4 4）P P与与 P P称为称为互补对互补对。6420

54、22-3-112022-3-11例子例子（1 1）、）、 是文字；是文字；（2 2）是子句；是子句； （3 3）是短语。是短语。 P P是一个子句，这种说法正确么？是一个子句，这种说法正确么？一个命题变元或者其否定既可以是简单一个命题变元或者其否定既可以是简单的子句，也可以是简单的短语。的子句，也可以是简单的短语。因此，因此， 不但是文字，也是子句、短语不但是文字，也是子句、短语 652022-3-112022-3-11定义定义3.5.23.5.2（1 1）有限个短语的析取式称为）有限个短语的析取式称为析取范式析取范式（2 2）有限个子句的合取式称为）有限个子句的合取式称为合取范式合取范式一个

55、不含最外层括号的短语（子句）也一个不含最外层括号的短语（子句）也可以是析取范式（合取范式）。可以是析取范式（合取范式）。662022-3-112022-3-11例子例子（1 1）、）、 是析取范式、合取范式；是析取范式、合取范式；（2 2） 是子句、析取范式、合取范式，是子句、析取范式、合取范式， ( ( ) )仅是子句、合取范式；仅是子句、合取范式；（3 3） 是短语、析取范式、合取范式，是短语、析取范式、合取范式， ( () )仅是短语、析取范式；仅是短语、析取范式；（4 4）( ()()( ) )是析取范式；是析取范式；（5 5）( ()()( ) )是合取范式；是合取范式；（6 6）句

56、子）句子( ( ) )、 ( () )既不是析取范既不是析取范式也不是合取范式式也不是合取范式672022-3-112022-3-11总结总结（1 1）单个单个的的文字文字是是子句、短语、析取范式，合取范式子句、短语、析取范式，合取范式（2 2）单个单个的的子句子句是是析取范式析取范式；（3 3）单个单个的的短语短语是是合取范式合取范式；（4 4）若）若单个单个的的子句（短语）子句（短语）无最外层括号，则是无最外层括号，则是合取合取范式（析取范式）；范式（析取范式）；（5 5）析取范式、合取范式析取范式、合取范式仅含联结词集仅含联结词集 ， （6 6） “ ”联结词仅出现在联结词仅出现在命题变

57、元前命题变元前。682022-3-112022-3-11范式的求解方法范式的求解方法定理定理3.5.13.5.1 对于任意命题公式，都存在与其等价对于任意命题公式，都存在与其等价的析取范式和合取范式。的析取范式和合取范式。转换方法：转换方法：（1 1）利用等价公式中的等价式和蕴涵式将公式中）利用等价公式中的等价式和蕴涵式将公式中的的、用联结词用联结词 、来取代，这可利用来取代，这可利用如下等价关系：如下等价关系：( () = () = ( ) )；( () = () = ()()() ) = ( = ( )()( ) )。692022-3-112022-3-11范式的求解方法范式的求解方法(

58、(续续) )（2 2）重复使用德）重复使用德 摩根定律将否定号移到各个命题摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号，这可利用如下变元的前端，并消去多余的否定号，这可利用如下等价关系：等价关系： ( ( ) =) =； ( () = ) = ； ( () = ) = 。（3 3）重复利用分配律，可将公式化成一些合取式的）重复利用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取，这可利用如下等析取，或化成一些析取式的合取，这可利用如下等价关系：价关系：( () = () = ()()() )； ( () = () = ()()() )。702022-3-112022-

59、3-11例例3.5.13.5.1求公式：求公式：( ( )()(R)R)的析取范式和合取范式的析取范式和合取范式解解 ( ( )()(R) R) = (= ( )()( R)(R)( RP)RP)= (= ( R)(R)( RPRP）= (= ( )()( R)R)( )()( RP) RP) = (= ( R)R)合取范式合取范式= = R R析取范式析取范式 712022-3-112022-3-11范式的不惟一性范式的不惟一性 考虑公式：考虑公式： ( ()()() )， 其与之等价的析取范式：其与之等价的析取范式： ( () )； ( ()()() )； ( ( )()() )； ( (

60、)()() )。这种不惟一的表达形式给研究问题带来了不便。这种不惟一的表达形式给研究问题带来了不便。722022-3-112022-3-113.5.2 3.5.2 主析取范式和主合取范式主析取范式和主合取范式1 1 极小项和极大项极小项和极大项定义定义 3.5.33.5.3 在含有在含有n n个个命题变元命题变元P P1 1、P P2 2、P P3 3、P Pn n的短语或子句中，若每个命题变元与其否定不同的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现时存在，但二者之一恰好出现一次且仅一次，一次且仅一次，则称则称此短语或子句为此短语或子句为关于关于P P1 1、P P2 2、P P3 3