离散件1-命题逻辑(离散数学课件).ppt

《离散件1-命题逻辑(离散数学课件).ppt》由会员分享，可在线阅读，更多相关《离散件1-命题逻辑(离散数学课件).ppt（72页珍藏版）》请在三一办公上搜索。

1、离散数学DISCRETE MATHEMATICS,离散数学,性质计算机科学主要的专业基础课之一，为计算机软件和应用各专业提供认识、分析和解决问题所需的离散数学基本理论、工具和方法。特点离散数学以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。,增强数学逻辑思维能力，培养和提高分析问题解决问题的能力，为学习计算机科学与应用的后续课程及进一步深造奠定坚实基础。,学习目的,离散数学教程（吴子华 四川大学出版社）或者：离散数学（冯伟森等编）参 考 书：1.方士昌，离散数学（第二版），西安电子科技大学出版社2.李盘林等，离散数学，高等教育出版社3.耿素云等，离散数学（第三

2、版），清华大学出版社4.Bernard Kolman等，离散数学结构（英文影印第四版），高等教育出版社5.Kenneth A.Ross 等，离散数学（第五版），清华大学出版社使用参考书注意事项：1。参考而非代替2。某些术语的差异问题,教 材：,离散数学的基本内容,逻辑命题逻辑谓词逻辑集合与关系集合与运算二元关系函数与映射图论代数系统群与环格与布尔代数,与离散数学关联的主要后续课程,数据结构与算法设计 数据库系统原理 编译原理 人工智能,学习方法和要求,如何学好离散数学：决心+专心+不缺课+适当笔记+基本作业+温故知新考核要求全部学习内容纳入考核，期末成绩占70%，课堂考勤占10%，平时成绩（课

3、后作业课堂练习期中考试）占20%。,第一节 命题及其表示一、定义：能确定其真或假的断言称为命题。1)命题的值有“真”和“假”之分，统称为 命题的真值。2)命题的要素：判断句+有确定的真假值,第一章 命题逻辑,例:下列各判断句都满足命题的定义。1)中国是最大的发展中国家。2)孔子是中国古代最伟大的教育家和思想家。3)银行利率上升，股价随之下降。4)两个三角形相似的充分必要条件是对应角相等并且对应边成比例。5）在定义域上可导的一元函数一定是连续函数。6)微软是世界上最大的软件厂商.7)2020年前人类将登上火星。注：命题的值遵循时效原则。,例：下列各个语句都不是命题。1)明天过来吧!2)1+1=1

4、0。3)我们要不畏艰难，勇于攀登。4)3x+4y 10。5)本断言不是命题。（悖论）,1。原子命题及其值1）定义：不能分解出更小命题单位的命题称为原子命题。2）例,(不是原子命题),(是原子命题),中国是最大的发展中国家。,大熊猫不是猫。,(是原子命题),中国是历史悠久、地大物博、人口众多的发展中国家。,2。复合命题与逻辑联结词1）复合命题：由若干原子命题经联结词联结而成的命题。例：孔子是中国古代最伟大的教育家和思想家。在定义域上可导的一元函数是连续函数。两个三角形相似的充分必要条件是对应角相等并且对应边成比例。无论是学习离散数学，还是学习C语言，都得下功夫；否则，就很难取得好的成绩。,常用的

5、几个逻辑联结词否定联结词：“不是”、“非”、英文“not”，用于表达对另一判断的否定。例如：不是人人都能成为艺术家的。合取联结词：“和”、“与”、“并且”、“既.又”、英文“and”，用于表达两个判断的同时性。例如：他既长于数学又精通音律。析取联结词：“或”、“要么.要么”、“不是.就是”、英文“or”，用于表达对两个判断的选择。注：本联结词有“可兼或”与“不可兼或”之分。如“小马或者小李成绩最好”是可兼或；而“小马在睡觉或在跳舞”则不是。,常用的几个逻辑联结词 条件联结词：“如果.就”、“除非.否则”英文“if.then.”，用于表达在指定的前提下将产生何种结果的判断。前提部分称为条件联结词

6、的前件，结果部分称为条件联结词的后件。例如：“如果下雨，就停止比赛”。“没有共产党，就没有新中国。”,常用的几个逻辑联结词 双条件联结词：“充要条件是.”、“当且仅当”、“等价于”、英文“if and only if”等，用于表达两个判断的某种相同性问题。例如：正整数 p是素数当且仅当 p 1并且p只有 1 和自身两个正因子。,二、命题的形式化 1。命题标识符 用大写字母或字母数字串表示命题。例如：令P：孔子是中国古代伟大的教育家。Q：孔子是中国古代伟大的思想家。2。逻辑值的符号表示用 1（或 T）表示逻辑值真用 0（或 F）表示逻辑值假 注：本课程中主要用 0、1 表示逻辑值。,3。常见逻辑

7、联结词的形式化否定联结词：（或）如 P 合取联结词：如 P Q 析取联结词：如 P Q 条件联结词：如 P Q 双条件联结词：如 P Q,4。命题形式化（翻译）的例子中国是最大的发展中国家。这是一个原子命题，可形式化表示为 P。孔子是中国古代伟大的教育家和思想家。令P：孔子是教育家，Q：孔子是思想家；形式化为 P Q。在定义域上可导的一元函数一定是连续函数。令P：这是可导函数，Q：这是连续函数；形式化为 P Q。这件事不是小王做的，就是小李做的。令P：这是小王做的，Q：这是小李做的。形式化为 P Q。两个三角形相似的充分必要条件是对应角相等并且对应边成比例。令P：两三角形相似，Q：对应角相等，

8、R：对应边成比例。形式化为 P（Q R）。,三、从形式化到具体化1。不同的命题可能形式化为相同的命题标识符。2。每个命题标识符可以具体化为不同的实际命题，称为对标识符的解释。例如：PQ 既可解释为“这件事不是小王做的，就是小李做的”，也可以解释为“要么在成都停留，要么在北京停留”。,四、逻辑联结词的功能定义,四、逻辑联结词的功能定义,否定 析取 合取 条件 双条件 P Q P PQ PQ PQ PQ 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1,四、逻辑联结词的功能定义,否定 析取 合取 条件 双条件 P Q P PQ PQ P

9、Q PQ 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1,四、逻辑联结词的功能定义,否定 析取 合取 条件 双条件 P Q P PQ PQ PQ PQ 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1,四、逻辑联结词的功能定义,否定 析取 合取 条件 双条件 P Q P PQ PQ PQ PQ 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1,四、逻辑联结词的功能定义,否定 析取 合取 条件 双条件 P Q

10、P PQ PQ PQ PQ 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1,四、逻辑联结词的功能定义,否定 析取 合取 条件 双条件 P Q P PQ PQ PQ PQ 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1,四、逻辑联结词的功能定义,否定 析取 合取 条件 双条件 P Q P PQ PQ PQ PQ 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1,作业,习题1.1 1,2（吴子华）or 习题1.

11、1 1,2（冯伟森）,第二节 命题合适公式与真值表,一、命题合适公式定义(形成规则)原子命题标识符是合适公式。(基础)如果P、Q都是合适公式，则 P、Q、（P Q）、（P Q）、（P Q）、（P Q）也都是合适公式。(归纳)只有按照1 和 2 产生的公式是合适公式。(界限)约定：1）以后我们用WFF表示术语“合适公式”。2）简称合适公式为公式。3）合适公式的外层括号可以去掉。例如（P Q）（P Q）可以写成（P Q）（P Q）。,二、子合适公式,定义：设G是WFF，A是G的一部分，且A也是WFF，则称 A是G的子合适公式。简称A 是G的子公式。例如：P、Q、（P Q）、（P Q）都是（P Q）

12、（P Q）的子公式。,三、命题公式的解释,1。对公式G中的每个原子代以具体的命题称为对G的解释。2。对原子代以真命题可以用对原子赋值 1来表达，对原子代以假命题可以用对原子赋值 0来表达。3。公式在每种解释下取得唯一的值。,例：下面是对公式G=（R Q）（P Q）的一个解释：P Q R 0 1 0 在这个解释下，公式G的值是(0 0）（0 1）=1。,四、公式的真值表,1。真值表：由公式的全部解释构成的表。2。真值表类似于联结词功能表，公式的原子 列于最前几列，表中每行对应一种解释。3。如果公式中有n个原子，则表中有 2 n 个不 同的解释行。,例：构造公式G=（R Q）（P Q）的真值表。解

13、：公式中含 3 个原子，故有 8 种可能的解释，见下表。P Q R|R Q P Q|（R Q）（P Q）0 0 0|0 0 1|0 1 0|0 1 1|1 0 0|1 0 1|1 1 0|1 1 1|,例：构造公式G=（R Q）（P Q）的真值表。解：公式中含 3 个原子，故有 8 种可能的解释，见下表。P Q R|R Q P Q|（R Q）（P Q）0 0 0|0|0 0 1|1|0 1 0|0|0 1 1|0|1 0 0|0|1 0 1|1|1 1 0|0|1 1 1|0|,例：构造公式G=（R Q）（P Q）的真值表。解：公式中含 3 个原子，故有 8 种可能的解释，见下表。P Q R|

14、R Q P Q|（R Q）（P Q）0 0 0|0 1|0 0 1|1 1|0 1 0|0 1|0 1 1|0 1|1 0 0|0 0|1 0 1|1 0|1 1 0|0 1|1 1 1|0 1|,例：构造公式G=（R Q）（P Q）的真值表。解：公式中含 3 个原子，故有 8 种可能的解释，见下表。P Q R|R Q P Q|（R Q）（P Q）0 0 0|0 1|10 0 1|1 1|10 1 0|0 1|10 1 1|0 1|11 0 0|0 0|01 0 1|1 0|11 1 0|0 1|11 1 1|0 1|1,例：构造公式G1=P（P Q）和 G2=P(P Q)的真值表。解：下面把

15、两个公式的真值表放在一起。P Q|P（P Q）|P（P Q）0 0|1|00 1|1|01 0|1|01 1|1|0,五、公式的分类,1。永真式：在任何解释下都取真值 1 的公式。也叫做重言式，如P（P Q）。永真式通常用符号T表示。2。永假式：在任何解释下都取真值 0的公式。也叫做矛盾式，如 P（P Q）。永假式通常用符号F表示。3。可满足式：至少在一种解释下取真值 1的公式。如 P Q等。显然，永真式是可满足公式，而矛盾式是不可满足公式。,作业:习题1.2 1,2(3)(7)（吴子华）or 习题1.2 1,2(3)(7)（冯伟森）,一、定义：设A是 B两个WFF，如果在任何解释下A和B都取

16、相同的值，则说公式A和B是等价的。1。A和 B等价记为 A B。2。定理：A B当且仅当A B是永真式。证明要点：当A B时，任何解释下A和 B同值，因此 A B 是永真式。反之，当A B是永真式时，在任何解释下A和B必须同值，因此 A B。,第三节 命题公式的等价,例：验证 P Q P Q解：列出真值表如下：P Q|P Q|P Q 0 0|1|10 1|1|11 0|0|01 1|1|1从值表可以看出，等价式成立。,例：验证（P Q）P Q解：列出真值表如下：P Q|（P Q）|P Q 0 0|1|10 1|0|01 0|0|01 1|0|0从真值表可以看出，等价式成立。,二、基本等价式,在

17、教材中列出了常用的 14个等价式，可以利用真值表加以验证。它们表达了逻辑联结词满足的运算定律，具有普遍意义，必须记住。1。（P）P（双重否定律）2。P P P，P P P（幂等律）3。P Q Q P，P Q Q P（交换律）,4。P（Q R）（PQ）R（P Q R）P（Q R）（P Q）R（P Q R）（结合律）根据结合律，只含 或只含 的公式，可以去掉括号。,5。P（Q R）（P Q）（P R）P（Q R）（P Q）（P R）（分配律）6。P（P R）P（吸收律）P（P R）P7。（P Q）P Q（德。摩根律）（P Q）P Q,8。P F P，P T P（同一律）9。P T T，P F F（

18、零律）10。P P T，P P F（矛盾律）11。P Q P Q(条件词转化)12。P Q（P Q）(P Q）(双条件词转化),三、公式等价的性质,1。A A（自反性）2。如果A B，则 B A（对称性）3。如果A B，B C 则A C（传递性）4。设A是公式 X 的一个子公式，且A B。又设用 B取代X中的子公式A后得到的新公式为Y，则 X Y。证明要点：因为A B，因而在任何解释下，A和B取相同的值，因而X和 Y的取值也都相同。利用上面的性质和基本等价式，就可以使用等价变换的方法去证明公式的等价问题，下面是两个例子。,例1：证明 P Q Q P证明：P Q P Q（Q）P Q P,例2：证

19、明(P Q)(P R)P(Q R)证明：（P Q）（P R)(P Q)(P R)P(Q R)P(Q R),四、对偶式,1。定义：设G是不含 和的WFF。把G中联结词 换成，把 换成、T换成F、F换成T后得到的公式记为G*，称之为G的对偶式。例如：G=P(Q R)，则G*=P（Q R）A(P,Q,R)=(P Q)(P R)Q TA*(P,Q,R)=(P Q)(P R)Q F求一般WFF的对偶式，必须用基本等价式先化去 和，变成只含否定、析取、合取之类联结词的等价公式后再作。,2。定理：设A、B都是WFF。如果A B,则A*B*。证明要点：设A和B分别表示 A(P1,P2,Pn)和B(P1,P2,

20、Pn),根据德.莫根定律 A(P1,P2,Pn)A*(P1,P2,Pn)B(P1,P2,Pn)B*(P1,P2,Pn)由A B 得出：A*B*。,例如：设A=P(Q R)B=（P Q）（P R)显然，A B。它们的对偶式分别是 A*=P(Q R)B*=（P Q）（P R)同样容易看出：A*B*。,作业:习题1.3 1(3)(4),2（吴子华）or 习题1.3 1(3)(4),2（冯伟森）,第四节 命题公式的范式表示,一、定义 1。原子公式及其否定都称为句节。例如 P、Q称为正句节，Q、P 称为负句节。2。有限个句节组成的析取式称为子句。例如 P Q R就是一个子句。3。有限个句节组成的合取式称

21、为短语。例如 P Q R S 是短语。4。有限个子句组成的合取式称为合取范式。例如(P Q)(S R)Q是合取范式。5。有限个短语组成的析取式称为析取范式。例如(P Q)(S R)是析取范式。,定理：每个WFF都可以化成等价的合取 范式或析取范式。证明要点：利用基本等价式进行转化。主要包括化去条件联结词和双条件联结词、使用德。摩根律、幂等律、交换律、结合律、分配律等。,例：求公式（P Q）（P R)的合取范式和析取范式。解：（P Q）（P R）（P Q）（P R）（P Q）（P R）(析取范式）P（P Q）（P R）（Q R）（合取范式）P（Q R）（合取范式）,二、主合取范式和主析取范式,从

22、上面例子可以看出，一个WFF可以有多个析取范式或合取范式，不易发现规律。下面先引入极小项和极大项的概念。1。设G是含 n个原子的WFF，由 n个无互反性的句节组成的子句称为G的一个极大项；由 n个无互反性的句节组成的短语称为G的一个极小项。例：对公式 G=（P Q）（P R)而言，P Q R，P Q R 等子句是极大项，而 短语 P Q R，P Q R是极小项。,2。极大项的性质 先以含2个原子P、Q的公式为例，列表考 察极大项的性质。P Q|P Q|P Q|P Q|P Q 0 0|0|1|1|10 1|1|0|1|11 0|1|1|0|11 1|1|1|1|0,从真值表中可以看出：1）每个极

23、大项在全部的 4 种不同解释中，只有一次取值 0；2）在每个解释中只有一个极大项取值 0；3）每个极大项取值为 0 当且仅当对原子解释为0时极大项中原子以自身出现，对原子解释为1时极大项中原子以其否定出现；4）没有两个极大项是等价的；5）不同极大项的析取式是永真式；6）全部极大项的合取式是矛盾式。,2。极小项的性质仍以有2个原子P、Q的公式为例，列表考 察极小项的性质。P Q|P Q|P Q|P Q|P Q 0 0|0|0|0|10 1|0|0|1|01 0|0|1|0|01 1|1|0|0|0,从真值表中可以看出：1）每个极小项在全部的 4 种不同解释中，只有一次取值 1；2）在每个解释中只

24、有一个极小项取值 1；3）每个极小项取值为 1当且仅当对原子解释为1时极小项中原子以自身出现，对原子解释为0时极小项中原子以其否定出现；4）没有两个极小项是等价的；5）不同极小项的合取式是矛盾式；6）全部极小项的析取式是永真式。,3。主合取范式,1）定义：如果一个公式的合取范式是由极大项构成的，则称这个范式为主合取范式。2）求一个公式的主合取范式的方法 真值表法：根据极大项的性质 3），在公式的真值表中找出对应于公式值为 0的全部解释，构造相应的极大项，由这些极大项构成主合取范式。例：利用真值表法求公式（P Q）（P R）的主合取范式。解：构造真值表如下：,P Q R|（P Q）（P R）0

25、0 0|0 0 0 1|0 0 1 0|0 0 1 1|0 1 0 0|1 1 0 1|0 1 1 0|1 1 1|1 从表中可知，有 5种解释使公式取值0，它们分别是 0 0 0，0 0 1，0 1 0，0 1 1，1 0 1 根据极大项性质 3），可以得到相应的 5个极大项：P Q R，P Q R，P Q R，P Q R，P Q R因而，公式（P Q）（P R）的主合取范式为：（PQR）（PQR）（PQR）（PQ R）（PQ R）,等价变换法：先把公式化成等价的合取范式，如果某个子式中不含原子 X 及其否定 X，则在这个子式中增加一个永假式（X X），并按分配律展开，最后按幂等律合并相同极

26、大项即可。,例：采用等价变换法求公式（P Q）（P R)的主合取范式。解：（P Q）（P R）（P Q）（P R）（P Q）（P R）P（Q R）（合取范式）（P（Q Q）（R R）（P P）Q R）（PQ R）（PQ R）（P Q R）（P Q R）（PQR）可见，这个结果与采用真值表法完全相同。,3。主析取范式1）定义：如果一个公式的析取范式是由极小项构成的，则称这个范式为主析取范式。2）求一个公式的主析取范式的方法 真值表法：根据极小项的性质 3），在公式的真值表中找出对应于公式值为 1的全部解释，构造相应的极小项，由这些极小项构成主析取范式。,例：利用真值表法求公式（P Q）（P R）

27、的主析取范式。解：构造真值表如下：,P Q R|（P Q）（P R）0 0 0|0 0 0 1|0 0 1 0|0 0 1 1|0 1 0 0|1 1 0 1|0 1 1 0|1 1 1|1 从表中可知，有3种解释使公式取值1，分别是 1 0 0，1 1 0，1 1 1,根据极小项性质3），可得到相应的极小项是：P Q R，P Q R，P Q R因而，公式（P Q）（P R）的主析取范式为（P Q R）（PQ R）（P Q R）,等价变换法：先把公式化成等价的析取范式，如果某个短语中不含原子 X 及其否定 X，则在这个短语中增加一个永真式（X X），并按分配律展开，最后按幂等律合并相同极 小项即可。例：求公式（P Q）（P R)的主析取范式。,解：（P Q）（P R）（P Q）（P R）（P Q）（P R）(析取范式）(P Q(R R)(P(Q Q)R)(P Q R)(P Q R)(P QR）这个结果与采用真值表法完全相同。,从上面的讨论中，可以得到如下定理：定理：每个可满足公式都存在唯一的主析取范式。每个非永真公式都存在唯一的主合取范式。作业:习题1.4 1(3)(4),3（吴子华）or习题1.5 1(3)(4),3（冯伟森）,