《离散数学教案》PPT课件.ppt

《《离散数学教案》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《离散数学教案》PPT课件.ppt（646页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学课程学时：课程学时：5656讲讲 授：康珺授：康珺1课程性质离散数学离散数学（又称计算机数学计算机数学）是现代数学的重要分支，是计算机专业核心基础课程之一。2课程目标离散数学离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。3与其他课程的关系离散数学离散数学与计算机科学的其他课程,如：数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、容错技术、人工智能等有密切的联系。它是这些课程的先导和基础课程。4n离散数学q上海科学技术文献出版社，1982n左孝凌

2、等编著n离散数学q高等教育出版社n耿素云、屈婉玲著耿素云、屈婉玲著教材与参考书5课程内容 本课程根据大纲的内容和相关独立性，可分为四大部分 第一部分 数理逻辑数理逻辑 包括命题逻辑;谓词逻辑 第二部分 集合论集合论 包括集合与关系;函数 6课程内容第三部分 代数系统代数系统 包括代数结构;格与布尔代数第四部分 图论图论 7学习方法定义、定理多。本课内容定义定义定理定理例题例题为了学好这门课，要求：（）弄懂定义、定理，弄懂例题，加深对定义、定理的理解；（）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。（3）做好课堂笔记。8第一篇 数理逻辑 逻辑学逻辑学:研究思维形式及思维规律的科学

3、。逻辑学分为二类：n辩证逻辑辩证逻辑:是研究事物发展的客观规律。n形式逻辑形式逻辑:对思维的形式结构和规律进行研究。数理逻辑数理逻辑：是用数学的方法研究概念、判断和推理的科学，属于形式逻辑。9第一篇 数理逻辑在数理逻辑中，用数学的方法是指引进一套符号体系的方法来研究概念、判断和推理。即对符号进行判断和推理。数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支的共同基础古典数理逻辑(命题逻辑和谓词逻辑)。10第一章 命题逻辑1.1 命题1.2 命题联结词1.3 命题公式1.4 等价式1.5 永真蕴含式1.6 其他命题联结词1.7 范 式 1.8 推论理论11第一

4、章 命题逻辑 教学目的及要求：教学目的及要求：深刻理解和掌握命题逻辑中基本概念和基本方法。教学内容：教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、对偶与范式、推理理论。教学重点：教学重点：命题逻辑中的基本概念和基本推理方法。教学难点：教学难点：推理理论。121.1 命题定义：定义：具有确定真假值的陈述句叫命题。讨论定义：（1）命题可以是真的，或者是假的，但不能 同时为真又为假。（2）命题分类：)原子命题原子命题（基本命题、本原命题）：不能分解成为更简单的命题。例：我是一位学生。131.1 命题 )分子命题分子命题（复合命题）：若干个原子 命题使用适当的联结词所

5、组成的新命题 例：我是一位学生和他是一位工人（3）命题所用符号：常用大写个英文字母 表示命题。用、表示。（4）命题中所有的“真”用“”表示，命题中所有的“假”用“”表示。141.1 命题例例：判断下列语句是否为命题。陈述句一般为命题（1）十是整数。（）（2）上海是一个村庄。（）（3）今天下雨。（4）加拿大是一个国家。（）（5）是偶数而是奇数。（T）（6）她不是护士。（7）（8）今天是星期天。151.1 命题命令句，感叹句，疑问句均不是命题。（1）把门关上！（2）你到哪里去？语句既为真，同时又包含假的不是命题，这样的句子称为“悖论悖论”。（3）他正在说谎。（在命题逻辑中不讨论这类问题）161.2

6、 命题联结词在命题演算中也有类似的日常生活中的联结词称做：“命题联结词”,下面先介绍五个常用的命题联结词。否定词：否定词：（否定运算、非运算）（）符号 ,读作“非”，“否定”设命题为，则在的前面加否定词 ，变成，读做“的否定”或“非”171.2 命题联结词（）定义 P的真值表：（）举例：每一种生物均是动物。F ：有一些生物不是动物。T 这里 不能讲成“每一种生物都不是动物”。对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。TFFT PP181.2 命题联结词合取词合取词（“合取”、“积”、“与”运算）(1)符号“”设，为两个命题，则称与的合 取，读作：“与”、“与的合取”、“并

7、 且”等。(2)定义（由真值表给出）：191.2 命题联结词TTTTFFFTFFTFFFFFQPP QQP的真值表：201.2 命题联结词当且仅当和的真值均为“”，则（）的真值为“”。否则，其真值为“”。注意注意：和是互为独立的；地位是平等的，和的位置可以交换而不会影响的结果。211.2 命题联结词(3)举例：(a)P：王华的成绩很好 Q：王华的品德很好。则：王华的成绩很好并且品德很好。(b)P：我们去种树 Q：房间里有一台电视机 则：我们去种树与房间里有一台电视机。221.2 命题联结词 (c)P：今天下大雨 Q：3+3=6 则：今天下大雨和3+3=6由例(b)(c)可见，在日常生活中，合取

8、词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。231.2 命题联结词 (d)P:王大和王二是亲兄弟。Q:他打开箱子然后拿出一件衣服来。该语句不是合取联结词组成的命题。241.2 命题联结词析取词析取词（或运算）（）符号“”设、为二个命题，则（）称作与的“析取”，读作：“或”。（）定义（由真值表给出）：251.2 命题联结词当且仅当、均为“”时，（）为“”。否则，其真值为“”TTTTFTTTFFFFP QQP的真值表：261.2 命题联结词区分“可兼或”与“不可兼或（异或，排斥或）”“可兼或”即P或Q为“T”时（PQ）为“T”，是析取。例如：灯泡有故障或开关有

9、故障。今晚写字或看书。今天下雨或打雷。以上例句均为“可兼或”。271.2 命题联结词“不可兼或”即P和Q的真值不同时，PQ为T。（异或用“”表示）不是析取。FTTTFTTTFFFFPQQPPQ的真值表：281.2 命题联结词例：他通过电视看杂技或或到剧场看杂技。他乘火车去北京或或乘飞机去北京。以上两句均为“不可兼或”。291.2 命题联结词单条件联结词：单条件联结词：（）符号“”，读作：“如果则”、为二个命题，（）为新的命题，读作：“如果则”。（）定义（由真值表给出）301.2 命题联结词的真值表：TTTFFTTTFTFFPQQP311.2 命题联结词 当为“”，为“”时，则（）为“”，否则（

10、）均为“”。：称为前件、条件、前提、假设 ：称为后件、结论。（）举例：P：我拿起一本书 Q：我一口气读完了这本书 321.2 命题联结词 PQ：如果我拿起一本书，则我一口气读完 了这本书。(b)P：月亮出来了 Q：33=9 PQ：如果月亮出来了，则33=9。通常称：(a)为形式条件命题前提和结果有某种形式 和内容上的联系。331.2 命题联结词 (b)为实质条件命题前提和结果可以有联 系，也可以没有联系，只要满足单条件命 题的定义。所以,是形式条件命题一定是实质条件命题,反 之不一定。“”是实质条件命题。例：我买到了鱼；:我吃鱼。：如果我买到了鱼，则我吃鱼。但“如果我没买到鱼，则我吃鱼”，在日

11、常生活中不可能，但在单条件命题的定义中是允许的。341.2 命题联结词可以证明：Q P P 原命题 逆反命题 逆命题 反命题351.2 命题联结词列出真值表,由真值表得：原命题逆反命题；逆命题反命题。TTTTTTTTFFFTFFTTTFTTTTFFP QP PQQP36n5双条件联结词（双条件联结词（等价联结词）：）：（）符号“”，读作：“当且仅当”、为二个命题，（）为新的命题，读作：“当且仅当”。（）定义（由真值表给出）371.2 命题联结词P Q的真值表:每当和的真值相同时，则（）的真值为“”，否则（）的真值为“”。TTTFFTFTFTFFP QQP381.2 命题联结词（）举例：（a）设

12、 ：ABC是等腰三角形 ：ABC有两只角相等 ：ABC是等腰三角形当且仅当 有两只角相等。391.2 命题联结词（b）下面均为等价联结词：春天来了当且仅当燕子飞回来了。平面上二直线平行，当且仅当二直线不相交。当且仅当雪是白色的。401.2 命题联结词（）,中，、的地位是平等的，、交换位置不会改变真值表中的值。（）当且仅当 仅当 当且411.2 命题联结词命题联结词在使用中的优先级命题联结词在使用中的优先级（）先括号内，后括号外（）运算时联结词的优先次序为：（由高到低）（）联结词按从左到右的次序进行运算（）最外层的括号一律均可省去 （）可写成421.2 命题联结词例（）可省去括号 因为“”运算是

13、可结合的。而（）中的括号不能省去，因“”不满足结合律。431.2 命题联结词 命题联结词小结：命题联结词小结：（1）五个联结词的含义与日常生活中的联结词 的含义大致相同。（2）“或”可分为可兼或（）和异或（）（不可兼或）（3）“”为一元运算，其余四个均为二元运算。441.2 命题联结词(4)“”分为形式条件和实质条件命题，当前件为“”时，不论后件怎样，则单条件命题的真值均为“”。(5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。451.2 命题联结词以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻

14、辑演算，为此，首先要把推理所涉及到的各命题符号化。步骤如下：找出各简单命题，分别符号化。找出各联结词，把简单命题逐个联结起来。461.2 命题联结词例.将下列命题符号化：（1）李明是计算机系的学生，他住在312室或 313室。（2）张三和李四是朋友。（3）虽然交通堵塞，但是老王还是准时到达了 车站。（4）只有一个角是直角的三角形才是直角三角 形。（5）老王或小李中有一个去上海出差。471.2 命题联结词解：（1）首先用字母表示简单命题。P：李明是计算机系的学生。Q：李明住在312室。R：李明住在313室。该命题符号化为：P（QR）（2）张三和李四是朋友。是一个简单句 该命题符号化为：P481.

15、2 命题联结词（3）首先用字母表示简单命题。P：交通堵塞。Q：老王准时到达了车站。该命题符号化为：PQ（4）首先用字母表示简单命题。P：三角形的一个角是直角。Q：三角形是直角三角形。该命题符号化为：P Q491.2 命题联结词（5）首先用字母表示简单命题。P：老王去上海出差。Q：小李去上海出差。该命题符号化为：P Q 也可符号化为：（PQ）（PQ）或者（P Q）（PQ）501.3 命题公式约定：约定：（）我们只注意命题的真假值，而不再去注意命题的汉语意义。（）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。511.3 命题公式命题公式命题公式命题常元：命题常元：表示确定的命题

16、T，F。命题变元：命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母表示。命题公式命题公式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。521.3 命题公式定义定义命题公式(wff)可按下述法则来生成：）单个的命题变元是一个命题公式。）若是命题公式，也为命题公式。）若、是命题公式，则（）、（）、（）、（）均为命题公式。）当且仅当有限次使用（）（）（）所得到的包含有命题变元和命题常元，联结词，括号的符号串才是命题公式。531.3 命题公式例如：(PQ)，(P(QR)，(PQ)R)，P都是命题公式。而(P)，(P)都不是命题公式命题公式的真值表命题公式的真值表

17、:命题变元用特定的命题来取代，这一过程称为对该命题变元进行真值指派。指派。命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。写成(x)541.3 命题公式 例如：公式 P(Q R)定义三元函数 Y(P，Q，R)P(Q R)定义定义命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表。551.3 命题公式构造真值表的步骤如下：1)找出给定命题公式中所有的命题变元，列 出所有可能的赋值。2)按照从低到高顺序写出命题公式的各层次。3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。561.3 命题公式FTTTTFTTFTTFTTFTFFFF（）（）P QQ

18、P例构造命题公式（）的真值表：571.3 命题公式 例写出命题公式（）的真值表 T TTT T FTT T TFT T FFT T TTF F FTF F TFF F FFF（)RQP581.3 命题公式由上二例可见，个命题变元有组真值指派；个命题变元有23 组真值指派，个则有个2n个真值指派。591.3 命题公式 命题公式的永真式、永假式和可满足式命题公式的永真式、永假式和可满足式定义定义设公式中有n个不同的原子变元 p1,pn,(n为正整数)。该变元组的任意一组确定的值（u1,un）称为关于p1,pn的一个完全指派完全指派，其中ui或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以

19、确定的值，则这样的一组值称为公式的关于该变元组的部分指派部分指派。定义定义使公式取真的指派称为成真指派成真指派。601.3 命题公式定义如果一个命题公式的所有完全指派均为成真指派，则该公式称为永真式永真式。如果一个命题公式的所有完全指派均为成假指派，则该公式称为永假式永假式。既不是永真式，又不是永假式，则称此命题公式是可满足式。可满足式。讨论：（）永真式的否定为永假式（）；永假式的否定为永真式（）。（）二个永真式的析取、合取、蕴含、等价 均为永真式。611.4 等价式等价式等价式定义定义如果对两个公式，不论作何种指派，它们真值均相同，则称，是逻辑等价的，亦说（）等价于（）,并记作：621.4

20、等价式例：TTT TTTT FTTF TTTF F Q QPPP Q 631.4 等价式例：判断公式A：(PQ)(PQ)与 B：(PR)(PR)是否等价。解：列该公式的真值表：641.4 等价式FFFTTFTTFFFFFTFFFTTTFFFFFTTTFFFTFFFTFFTFFTTFTTTTTTTTFFTTTTTFTTTTFTTTTTTTTFFTTTTTTFTTFTTTBAPRPRRPQPQQRQP651.4 等价式定理定理 命题公式的充要条件是为永真式。说明：“”为等价关系符，表示和有等价关系。不为命题公式 “”为等价联结词（运算符），、为命题公式，则（）也为一命题公式。661.4 等价式证明

21、：（）充分性：为永真式，即、有相同的真值，所以。（）必要性：，即、有相同的真值表，所以 为永真式。例：证明；671.4 等价式T T TT T T TTF T F T T T FTT T TF T F TFT T TF T FFFPQ PQP PQP由定理可知：若，则 若，C，则681.4 等价式下面列出组等价公式（1）双重否定律双重否定律 （2）同等律同等律；（3）交换律交换律 ；（4）结合律结合律 （）（）；（）（）；（）（）691.4 等价式（5）分配律分配律 （）（）（）；（）（）（）（6）摩根律摩根律 （）；（）（7）吸收律吸收律 （）；（）701.4 等价式（8）蕴含律蕴含律 （9

22、）等价律等价律 （）（）（10）零律零律；（11）同一律同一律；（12）互补律互补律；（13）输出律输出律 （）711.4 等价式（14）归缪律归缪律 （）（）（15）逆反律逆反律 说明：（）证明上述组等价公式的方法可用真值表法，把改为所得的命题公式为永真式，则成立。721.4 等价式（2）、均满足结合律，则在单一用、联结词组成的命题公式中，括号可以省去。（3）每个等价模式实际给出了无穷多个同类型的具体的命题公式。例如：(PQ)(P Q)，(PQ)(RS)(P Q)(R S)，(PQ)R)(P Q)R)731.4 等价式置换规则置换规则定义给定一命题公式，其中P1、P2Pn 是中的原子命题变元

23、，若（1）用某些命题公式代换中的一些原子命题变元Pi （2）用命题公式i代换Pi，则必须用i代换中的所有Pi由此而得到的新的命题公式称为命题公式的代代换实例换实例741.4 等价式讨论定义：讨论定义：（）用命题公式只能代换原子命题变元，而不 能去代换分子命题公式。（）要用命题公式同时代换同一个原子命题变 元。（）永真式的代换实例仍为永真式；反之代换实 例为永真式时，则不能断定原公式也一定是 永真式。751.4 等价式例：为一永真式，若用任何命题公式代换，则仍为永真式为一个可满足的命题公式，若用代换，则得（）为永真式，但（）并不是永真式。（）一个命题公式的代换实例有许多个，但不一定都等价于原来的

24、命题公式 761.4 等价式例设：（Q）若用（）代换中的，得：（）（Q（）是的代换实例，而：（）（Q）不是B的代换实例。例的代换实例有：（），（），（）等所以，一个命题公式的代换实例有无限个。771.4 等价式下面讨论取代过程（置换规则）：定义给定一命题公式，是的任何部分，若也是一命题公式，则称是的子命题子命题公式公式。例：（）（）的子命题公式有：、（）、（）、（）、（）（）等。781.4 等价式定理给定一命题公式，是的子公式。设B是一命题公式，若 B，并用B取代中的，从而生成一新的命题公式B，则B。从定理可见：一个命题公式A，经多次取代，所得到的新公式与原公式等价。例：证明：（）（）791.

25、4 等价式（）（）例：证明：（）（）（）（）为一永真式801.4 等价式证明：原式：（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）它是它是（永真式）的代换实例，永真式的代（永真式）的代换实例，永真式的代换实例仍为永真式！换实例仍为永真式！811.4 等价式对偶原理（对偶定律）对偶原理（对偶定律）定义定义给定二个命题公式和A*，若用代换，用代换，用代换，用代换，其中一个命题公式由另一个命题公式得来，则称和A*是互为对偶的，而联结词和也是互为对偶的例：写出下列命题公式的对偶式：（）（）对偶式 A*821.4 等价式讨论定义：（）若命题公式中有联结词，则必须把化成由联结词，组成

26、的等价的命题公式，然后求它的对偶式；例：求(PQ)(PR)的对偶式831.4 等价式（）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。例：（）对偶式写成 （），而不能写成841.4 等价式定理（摩根推广定理）设和A*为对偶式P1,P2Pn 是出现在和A*中的所有原子命题变元，于是有：（P1，P2Pn）A*（P1，P2Pn）（1）（P1，P2Pn）A*（P1，P2Pn）（）851.4 等价式证明：由摩根定理（）（）（）（）不难看出：一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。例：设（，）（），验证上述定理：861.4 等价

27、式证明：()（，）（，）A*（，）A*（，）（）（，）A*（，）（）有（，）A*（，）871.4 等价式定理若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若，则A*B*成立。证明：已知：、为任一命题公式，且，要证明A*B*设：P1、P2Pn 是出现在和中的原子命题变元，881.4 等价式由，即（P1，P2Pn）（P1，P2Pn）（P1，P2Pn）（P1，P2Pn）由摩根推广定理*（P1，P2Pn）*（P1，P2Pn）891.4 等价式*（P1，P2Pn）*（P1，P2Pn）为永真式前面讲过永真式的代换实例仍为永真式，所以用 Pi代换A*和B*中的Pi（1in)则得：*（P1，P2 Pn

28、）*（P1，P2 Pn）即为：*（P1，P2Pn）*（P1，P2Pn）901.4 等价式例：证明：（）（）（）（）（）（）（）（）证明：（）左边(）（）（）（）（）（）（）911.4 等价式（）左边 （）（）（）（）（）结论：（）和（）是互为对偶的。921.5 永真蕴含式永真蕴含式定义命题公式称为永真蕴含命题公式，当且仅当 是一个永真式，记作：说明：“”读作“永真蕴含”，“蕴含”，“能推得”“”是关系符，不为命题公式。例：证明：；P（）列出真值表 证明：（）和（）为永真式931.5 永真蕴含式永真蕴含式（）可用等价公式证：（）（）T（）（）TT T TT T T T TF T TT T TF

29、TF T FF T TTFF T FF T FFF（）（）QP941.5 永真蕴含式永真蕴含式定理定理设、是二个命题公式的充分必要条件是 且。证明：若，则为一永真式由定律：（）（）（）（）且（）也为一永真式 即：且成立反之 且 则也成立此定理把“”和“”之间建立了相应的关系。951.5 永真蕴含式永真蕴含式下面给出常用的永真蕴含式 I1 （）I2 （）I3（）I4 （）I5 （）I6 （）（）（）I7 （）（）（）I8 （）（）（）I9 P 961.5 永真蕴含式永真蕴含式I10 I11 （）I12（）I13 （）（）（）证明上述永真蕴含式的方法有三种：（）把“”关系符改为“”联结词，证明它为

30、永真式。(a)真值表法 (b)命题演算法971.5 永真蕴含式永真蕴含式（）找出使单条件命题前件为“”的所有真值指派，试看能否导致后件均为“”，若为“”，则永真蕴含关系成立。TTTFFTTTFTFFPQQP981.5 永真蕴含式永真蕴含式例：（）前件为“”的所有指派为、（）均为“”，为“”，为“”，也应为“”，（）成立（）找出使单条件命题的后件均为“”的所有真值指派，试看前件的所有真值是否为“”，若是，则蕴含成立。991.5 永真蕴含式永真蕴含式例：（）后件为“”的所有条件是：为“”，代入前件得（）若为，则（）为“”；（）若为，则（）为“”；（）成立 若后件简单则可选用(3)；若前件简单则可选

31、用(2)。二种方法是互为独立的，只需使用一种证明就行。1001.5 永真蕴含式永真蕴含式讨论一下永真式 可得出三个结论：（）若一个命题公式等价于一个永真式，则该公式一定为永真式。（）若一个永真的命题公式永真蕴含一个命题公式，则此命题公式一定也为永真式。（）若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。1011.5 永真蕴含式永真蕴含式定理给定命题公式、，若，且，则。证明：，且，（）（）为永真式，由I6：（）（）（），（）也为永真式；即，成立1021.5 永真蕴含式永真蕴含式推论推论若B1、B1 B2Bm，则。定理定理给定一个命题公式、，若,，则（）证明：，（

32、）（）为永真式，由条件，若一定为“”，则、均为“”，（）也为“”，结论：（）为“”。1031.5 永真蕴含式永真蕴含式上述也可用等价公式证明它：（）（）（）（）（）（）也为永真式（）成立定义定义设H1,H2.Hm,均为命题公式，若（H1H2 Hm），则称 H1,H2.Hm,共同蕴含，并记作：H1,H2.Hm 。1041.5 永真蕴含式永真蕴含式 定理定理若（H1 H2Hm）,P ，则（H1 H2Hm）（）。证明：（H1 H2Hm P）（H1 H2Hm P）Q （H1 H2 Hm）（P Q）（H1 H2Hm）（P Q）H1 H2 .Hm（）也为永真式 （H1,H2 .Hm）（）成立 1051.6

33、 其他联结词联结词其他命题联结词：其他命题联结词：(1)不可兼或（异或，异）(a)符号:(),读作“异或”(b)定义:（由真值表）(c)异或的性质：（）（）（）（）（）()()FTTTFTTTFFFFP QQP1061.6 其他联结词联结词（）（）（）（对 可分配的）若，则有：，1071.6 其他联结词联结词()“与非”联结词：(a)符号,读作“与的否定”或“与非”(b)定义：（由真值表）（）（）FTTTFTTTFTFFP QQP1081.6 其他联结词联结词(c)性质：（）（）（）（）（）（）（）（）（）（）（）不可结合（）（）不可结合 ，1091.6 其他联结词联结词()“或非”联结词：(

34、a)符号：“”（）读作：“或的否定”或“或非”(b)定义（由真值表给出）：（）（）FTTFFTFTFTFFQP1101.6 其他联结词联结词(c)性质：（可交换的）（）（）（）（）（）（）不可结合（）（）不可结合；(d)由（）和（）中的性质可见，和是互为对偶的。1111.6 其他联结词联结词(4)“蕴含否定”联结词：(a)符号：(b)定义(由真值表给出）：P Q(PQ)“”cFFFFTFTFTFTTP QQPcc1121.6 其他联结词联结词()不同真值表的命题公式：按命题公式的生成规则，用联结词可组成无限个命题公式。下面讨论这些命题公式有多少种不同的真值表：(a)若命题变元只有一个，则用联结

35、词组成的命题公式由四种不同的真值表，即为：TFTFTTTFFF3210P1131.6 其他联结词联结词所有依赖于的命题公式均等价于这四个中的一个(b)若有二个命题变元、，则命题公式的不同真值表有：222=24=16种。推广到一般：若有个变元的命题公式，则可构成不同的真值表为22n（个）。1141.6 其他联结词联结词（）二元运算中的全部联结词总结：（）二元运算中的全部联结词总结：、是五个基本联结词。到此为止，一个符号系统已定义完毕，它们是：命题变元:、值:、运算符:、括号:（）关系符:、。C1151.6 其他联结词联结词全功能联结词集合：全功能联结词集合：定义一个联结词集合，用其中联结词构成的

36、式子足以把一切命题公式等价的表达出来，则称此联结词集合为全功能联结词集合全功能联结词集合。定义设有一联结词集合，若 （）用中的联结词的等价式能表达任何的一个命题公式；（）删除中的任一联结词，从而形成一个新的联结词集合，至少有一个命题公式不能用中的联结词的等价式来表示，则称A为最小的最小的全功能联结词集合全功能联结词集合。1161.6 其他联结词联结词我们可以证明：，；，；，；均为全功能联结词集合，且均是最小的全功能联结词集合。例：用上述最小全功能联结词集合中的联结词单一表达下述命题公式：1171.6 其他联结词联结词（），（）（），（），()，（）（）（）（）（）（）cc1181.7 范式范式

37、如何判定命题公式为永真式、永假式和可满足式或二个命题公式等价，归纳有三种方法：（1）真值表法：对于变元的所有真值指 派，看对应命题公式的真值。（2）命题演算方法：化简命题公式至最简式，看是否存在和（）、（）等价，若不则为可满足的。（3）范式方法：本节就介绍此法。1191.7 范式范式什么叫范式 把命题公式化归为一种标准的形式，称此标准形式为范式。什么叫判定 以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。讨论范式和主范式的目的就是为了进行判定。1201.7 范式范式析取范式和合取范式：析取范式和合取范式：设命题变元为：、

38、，则：（）的析取式称为“和”；（）的合取式称为“积”。定义定义命题公式的变元和变元的否定之积称为基本基本积积，而变元和变元的否定之和称为基本和基本和。1211.7 范式范式例：设、为二个命题变元，则：，称为基本和；，称为基本积。若“基本和”或“基本积”中的子公式”，称为此基本积 （和）的因子因子。例：的因子有：、1221.7 范式范式定理定理一个基本积必定是永假式，它的充分必要条件是，它至少包含一对因子,其中一个是另一个的否定。证明：（）充分条件：、为基本积中一对因子该 基本积一定为永假式。（）（）（）（）必要条件：基本积为永假式基本积中包含、这对因子。1231.7 范式范式反证法：假设基本积

39、中不包含、这样的因子，且为永假式。若给基本积中的命题变元指派“”，而命题变元的否定指派为“”，在基本积中不包含、这对因子，基本积得到的真值为“”，这和假设相矛盾；基本积中必然包含、这对因子才能使基本积为“”。1241.7 范式范式定理定理一个“基本和”必定为永真式，其充要条件（当且仅当）是，它至少包含一对因子，其中一个是另一个的否定。定义定义与给定命题公式等价的一个公式，如果是由基本积之和组成，则称它为命题公式的析取范式析取范式。并记为：PP1 P2 Pn（nI+）。其中P1，P2Pn均为基本积。方法可按下列三步（或四步）进行：1251.7 范式范式（）利用等价公式：化去“”、“”联结词，把命

40、题公式变为与其等价的用，表达的公式。例:，（）（）（）（）（）将“”深入到原子命题变元之前，并使变元之前最多只有一个“”词。例：（）1261.7 范式范式（）利用“”对“”的分配，将公式化为析取范式。（）除去永假项得最简析取范式。例：求（）（）的析取范式：解：原式 (（）（）)(（）（）)1271.7 范式范式(（）（）)(（）（）)-（1）化去化去词词（）（）（）-（2）将将“”深入到变元前面，并最多保留一深入到变元前面，并最多保留一个个（）（）（）（）（）-（3）“”对或对或“”的分配，化成为析取的分配，化成为析取范式范式（）（）-（4）最简析取范式）最简析取范式1281.7 范式范式讨论

41、定义：（）从上例看出，一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等价的。（）若一个命题公式的析取范式中每一个基本积均为永假式，则该公式也一定为永假式。即PP1P2Pn（P1，P2Pn均为基本积）则当P1P2 Pn F时，一定为永假式。(可用来判定是否为永假式)1291.7 范式范式例：（析取范式）（）（）永假式定义定义与给定命题公式等价的一个公式，如果它是由基本和之积所组成，则称它是给定命题公式的合取范式合取范式。并表示成：Q Q1 Q2 Qn，(nI+),其中Q!,Q2,Qn均为基本和。1301.7 范式范式求一个命题公式的合取范式的方法和求析取范式的方法类同：第（）、

42、（）步相同；第（）利用“”对“”的分配就行；第（）去掉永真的析取项。1311.7 范式范式例：求（）（）的合取范式原式 （）（）化去化去“”词词 （）（）“”深入到变元前，并最多保留一个深入到变元前，并最多保留一个（）（）（）“”对对“”的分配的分配（）（）（）（）（最简合取范式）1321.7 范式范式讨论定义：（）给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。（）若一个命题公式的合取范式中的各基本和的真值为“”，则该命题公式一定是永真式。(可用来判定是否为永真式)例:）（）（）1331.7 范式范式主析取范式。主析取范式。定义定义在个变元的基本积中，若每个变元及其

43、否定并不同时存在，且二者之一出现一次且仅出现一次，则称此基本积为极小项极小项。例:对二个命题变元讲,极小项有22=4个,即、对一个命题变元讲,极小项有21=2个,即:、1341.7 范式范式对三个命题变元讲，极小项有23=8个，即：、推广到一般：个命题变元构成的不同极小项有2n个（nI+）。使得每个极小项为真的赋值仅有一个。1351.7 范式范式定义定义对给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的主析取范式。主析取范式。定理定理在真值表中，一个公式的真值为的指派所对应的极小项的析取，即为此公式的主析取范式。1361.7 范式范式例：求出、（）、的主析取范式TFFTTTFT

44、TTFTTFTFTFTFTTFF（）1371.7 范式范式则可直接写出各命题公式的主析取范式：（）（）（）（）（）（）（）（）（）（）（）讨论此定理：1381.7 范式范式（1）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“”的行，对应写出极小项的析取式，且一定是唯一的。（2）若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2n个极小项。（3）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。（4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“”的个数。1391.7 范式范式下面介绍不用真值表，直接

45、求命题公式主析取范式的方法，分四步：（）将命题公式化归为与其等价的析取范式；（）除去永假项，合并基本积中相同项（例：），变为最简析取范式。（）利用添变元的方法，将所有基本积变为极小项。1401.7 范式范式例：二个变元、，利用“”对或“”的分配添项（）（）（）（）（）（）（）合并相同的极小项变为一项。例：求（）的主析取范式解：原式（）（）-（1）化为析取范式 1411.7 范式范式（）-（2）消去永假项，变为最简析取范式（）（）（）（）（）-（3）添项（）（）-（4）合并相同最小项1421.7 范式范式例：证明（）证明方法是写出二命题公式的主析范式，看其是否相同：（）（）（）（）（）而 （）（

46、）（）（）（）（）（）（）（）主析范式相同，有（）1431.7 范式范式主合取范式主合取范式定义在个变元的基本和中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，则称这种基本和为极大项。例：有二个变元,的极大项有22=4个，（）、（）、（）、（）有个变元，则有2n个极大项（nI+）。1441.7 范式范式定理在真值表中，一个公式的真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。在真值表中真值为“”的个数等于主合取范式中极大项的个数。例：求出（）、（）、（）、（）的主合取范式1451.7 范式范式（）TTFTTTFFTTFTTFTTTFTFTFFF直接写出其主合取

47、范式：（）（）（极大项）（）（）（）1461.7 范式范式（）（）（）（）（）（）（）（）（）（）（）（）（）（）1471.7 范式范式讨论（）与命题公式等价的主合范式中极大项的个数等于其真值表中真值为“”的个数。由真值表找极大项的方法为：将表中值为“”的对应真值指派中，把变元写成否定，把变元的否定写成变元。（）只要命题公式不是永真式，则一定可以写出对应与其等价的唯一的主合取范式。1481.7 范式范式（）若命题公式为含有个变元的永假式，则主合取范式包含了2n个极大项的合取式。（）可用主合取范式判定二个命题公式是否等价。（）已知一个命题公式的主析取范式，则一定可以直接写出与其等价的主合取范式来

48、。反之也行。例：（）（）（）主析取范式 （）主合取范式1491.7 范式范式（）对应于有个变元的命题公式，则一定有：主析范式极小项数主合范式极大项数主析范式极小项数主合范式极大项数2n下面介绍不用真值表求一命题公式主合取范式的方法：（1）化为与命题公式等价的合取范式；（2）除去真值为“T”的析取项和除去析取项中相同变元且只保留一个，变为最简合取式；（3）添项，使析取项均变为极大项；1501.7 范式范式 例如：、为二个变元，即：（）（）（）（4）合并相同的极大项，保留一项。例：求（）的主合取范式 解：原式 （）（）（）（）（）1511.7 范式范式主范式序（列）的唯一性主范式序（列）的唯一性（

49、）极小项极其编码为了确保主范式的唯一性，二个安排：（a）各命题变元的位置安排一固定次序；（b）对极小项、极大项安排一个次序。对于有个变元的命题公式，则最多可有2n个极 小项，用m0 m1 m2n-1来表示。下面列出三个变元，且、的位置已排定，则 152P Q R1117m(7)十P Q R1106m(6)十P Q R1015m(5)十P Q R1004m(4)十P Q R0113m(3)十 P Q R0102m(2)十 P Q R0011m(1)十P Q R0000m(0)十极小项表示二进制数十进制数m(i)十1.7 范式范式1531.7 范式范式例：设一命题公式有五个变元，P0,P1,P2,

50、P3,P4（次序已定），则必可写出25=32个极小项，下列出m(11)十和m(18)十的极小项表示：即，m(11)十 m(01011)二 （P0 P1 P2 P3 P4）m(18)十 m(10010)二 （P0 P1 P2 P3 P4）1541.7 范式范式通过上例归纳出一求极小项m(i)十的方法：(a)把(i)十变换成等价的(J0,J1Jn-1)二(b)由二进制写出其对应的极小项：例：求（）（）的编码表达式：（设、次序已定）解：原式（）（）（）（）1551.7 范式范式 m(001)二 m(010)二 m(100)二 m(101)二 m(1)十 m(3)十 m(7)十 m(6)十 m1,m3