离散数学第一章.ppt

1、1,第一章 命题逻辑,1.命题 2.命题联结词 3.命题变元与命题公式 4.等价式 5.永真蕴含式 6.命题联结词总结 7.范 式 和 判 定 8.推论规则和证明方法,2,1命题,定义： 具有唯一真值的陈述句叫命题。 讨论定义： （）命题可以是真的，或者是假的，但不能同时为真又为假。 （）命题分类： )原子命题（基本命题、本原命题）：一个命题，不能分解成为更简单的命题。 例：我是一位学生。,3,1命题,)分子命题（复合命题）：若干个原子命题使用适当的联结词所组成的新命题 例：我是一位学生和他是一位工人 (3)命题所用符号：常用大写个英文字母表示命题。用、表示。 (4)命题中所有的“真”用“”表

2、示， 命题中所有的“假”用“”表示。,4,1命题,例：判断下列语句是否为命题。 陈述句一般为命题 （1）十是整数。 （） （2）上海是一个村庄。（） （3）今天下雨。 （4）加拿大是一个国家。（） （5）是偶数而是奇数。 （6）她不是护士。 （7） （8）今天是星期天。,5,1命题,命令句，感叹句，疑问句均不是命题。 （1）把门关上！ （2）你到哪里去？ 语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。 （3）他正在说谎。 （在命题逻辑中不讨论这类问题）,6,2命题联结词,在命题演算中也有类似的日常生活中的联结词称做：“命题联结词”下面先介绍五个常用的命题联结词。 否定词：（否定运

3、算、非运算） （）符号 ,读作“非”，“否定” 设命题为，则在的前面加否定词 ，变成， 读做“的否定”或“非”,7,2命题联结词,（）定义：严格由真值表定义 （）举例： ：北京是一座城市。 ：北京不是一座城市。 ：每一种生物均是动物。F ：有一些生物不是动物。T 这里不能讲成“每一种生物都不是动物”为假命题了。 对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。,8,2命题联结词,合取词（“合取”、“积”、“与”运算） 符号“” 设，为两个命题，则称与的合取，读作：“与”、“与的合取”、“并且”等。 定义（由真值表给出）：,9,2命题联结词,真值表如下 ：,10,2命题联结词,当

4、且仅当和的真值均为“”，则（）的真值为“”。否则，其真值为“”。 注意：和是互为独立的；地位是平等的，和的位置可以交换而不会影响的结果。,11,2命题联结词,举例： (a) P：王华的成绩很好 Q：王华的品德很好。 则：王华的成绩很好并且品德很好。 (b) P：我们去种树 Q：房间里有一台电视机 则：我们去种树与房间里有一台电视机。,12,2命题联结词,(c) P：今天下大雨 Q：3+3=6 则：今天下大雨和3+3=6 由例(b)(c)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。,13,2命题联结词,(d) 下列语句不是合取联结词组

5、成的命题。 P: 王大和王二是亲兄弟。 Q: 他打开箱子然后（而后）拿出一件衣服来。,14,2命题联结词,析取词（或运算） （）符号“” 设、为二个命题，则（）称作与的“析取”，读作：“或”。 （）定义（由真值表给出）：,15,2命题联结词,当且仅当、均为“”时，（）为“”。否则，其真值为“”,真值表 如右：,16,2命题联结词,区分“可兼或”与“不可兼或（异或，排斥或）” 析取词为可兼或即:P和Q均为“T”时（PQ）为“T” 例如： 灯泡有故障或开关有故障。 今晚写字或看书。 今天下雨或打雷。 以上例句均为可兼或。,17,2命题联结词,“不可兼或”中当P和Q均为“T”时，则P异或Q为“F”。

6、 （异或用“”表示）,18,2命题联结词,例： 他通过电视看杂技或到剧场看杂技。 他乘火车去北京或乘飞机去北京。 以上两句均为不“可兼或”。,19,2命题联结词,单条件联结词：（“蕴含”联结词、蕴含词） （）符号“”，读作：“如果则”、“蕴含” 、为二个命题，（）为新的命题，读作：“如果则”，“蕴含”，“仅当”，“当且”，“是的充分条件”。 （）定义,20,2命题联结词,（由真值表定义）：,21,2命题联结词,当为“”，为“”时，则 （）为“”，否则（）均为“”。 ：称为前件、条件、前提、假设 ：称为后件、结论。 （）举例： P：我拿起一本书 Q：我一口气读完了这本书,22,2命题联结词,PQ

7、：如果我拿起一本书，则我一口气读完了这本书。 (b) P：月亮出来了 Q：33=9 PQ：如果月亮出来了，则 33=9。 通常称：(a)为形式条件命题。 前提和结果有某种形式和内容上的联系。,23,2命题联结词,(b)为实质条件命题。前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。 所以,是形式条件命题一定是实质条件命题,反之不一定。“”是实质条件命题。 例： ：我买到了鱼；:我吃鱼。,24,2命题联结词,：如果我买到了鱼，则我吃鱼。 但“如果我没买到鱼，则我吃鱼”，这在日常生活中是不可能的，但在单条件命题的定义中是允许的。,25,2命题联结词,可以证明： Q P 原命题 逆反

8、命题 逆命题 反命题,26,2命题联结词,列出真值表,由真值表得： 原命题逆反命题；逆命题反命题。,27,2命题联结词,双条件联结词（“等价”词、“同”联结词、“等同”词） （）符号“” 设、为二个命题，则读作：“当且仅当”，“等价”,“是的充分必要条件”。 （）定义（见真值表）：,28,2命题联结词,真值表: 每当和的真值相同时，则（）的真值为“”，否则（）的真值为“”。,29,2命题联结词,（）举例： （a）设 ：ABC是等腰三角形 ：ABC有两只角相等 ：ABC是等腰三角形当且仅当ABC中有两只角相等。,30,2命题联结词,（b）下面均为等价联结词： 春天来了当且仅当燕子飞回来了。 平面

9、上二直线平行，当且仅当这二直线不相交。 当且仅当雪是白色的。,31,2命题联结词,（）,中，、的地位是平等的，、交换位置不会改变真值表中的值。 （）当且仅当 仅当 当且,32,2命题联结词,命题联结词在使用中的优先级 （）先括号内，后括号外 （）运算时联结词的优先次序为： （由高到低）,33,2命题联结词,（）联结词按从左到右的次序进行运算 例 （）可省去括号 因为“”运算是可结合的。 （ ）可省去括号因为符合上述规定 而（）中的括号不能省去，因为“”不满足结合律。,34,2命题联结词,（）最外层的括号一律均可省去 （）可写成 命题联结词小结： （）五个联结词的含义与日常生活中的联结词的含义大

10、致相同。 （）“或”可分为可兼或（）和异或（ ）（不可兼或）,35,2命题联结词,(3) 除“”为一元运算外，其余四个均为二元运算。 (4) “”分为形式条件和实质条件命题，当前件为“”时，不论后件怎样，则单条件命题的真值均为“”。 (5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。,36,2命题联结词,以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。 步骤如下： 找出各简单命题，分别符号化。 找出各联结词，把简单命题逐个联结起来。,37,2命题联

11、结词,例. 将下列命题符号化： （1）李明是计算机系的学生，他住在312室或313室。 （2）张三和李四是朋友。 （3）虽然交通堵塞，但是老王还是准时到达了车站。 （4）只有一个角是直角的三角形才是直角三角形。 （5）老王或小李中有一个去上海出差。,38,2命题联结词,解： （1）首先用字母表示简单命题。 P：李明是计算机系的学生。 Q：李明住在312室。 R：李明住在313室。 该命题符号化为：P（QR） （2）张三和李四是朋友。是一个简单句 该命题符号化为：P,39,2命题联结词,（3）首先用字母表示简单命题。 P：交通堵塞。 Q：老王准时到达了车站。 该命题符号化为：PQ （4）首先用字

12、母表示简单命题。 P：三角形的一个角是直角。 Q：三角形是直角三角形。 该命题符号化为：P Q,40,2命题联结词,（5）首先用字母表示简单命题。 P：老王去上海出差。 Q：小李去上海出差。 该命题符号化为：P Q 也可符号化为： （PQ）（PQ）或者 （P Q） （PQ）,41,命题公式,约定： （）我们只注意命题的真假值，而不再去注意命题的汉语意义。 （）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。 命题公式 命题常元：表示确定的命题T，F。 命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母表示。,42,命题公式,命题公式：由命题变元、常元、联结

13、词、括号，以规定的格式联结起来的字符串。 定义：命题公式可按下述法则来生成： ）孤立的命题变元是一个命题公式。 ）若是命题公式，也为命题公式。 ）若、是命题公式，则（）、（）、（）、（）均为命题公式。,43,命题公式,）当且仅当有限次使用 （）（）（）所生成的公式才是命题公式。 例如：(P Q)，(P(Q R)，(PQ)R)，P都是命题公式。而(P)，(P)都不是命题公式 命题公式的真值表 : 命题变元用特定的命题来取代，这一过程称为对该命题变元进行指派。 命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。 写成(x),44,命题公式,例如：公式 P (Q R) 定义三元函数 Y

14、(P，Q，R) P (Q R) 定义：命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表。 构造真值表的步骤如下： 1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。 2)按照从低到高的顺序写出命题公式的各层次。 3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。,45,命题公式,例构造命题公式（）的真值表：,46,命题公式,例写出命题公式 （）的真值表,47,命题公式,由上二例可见，个命题变元有组真值指派；个命题变元有23 组真值指派， 个则有个2n个真值指派。 命题公式的永真式、永假式和可满足式 例：举最简单例子：,48,命题公式,定义：设公式中有

15、n个不同的原子变元p1,pn,(n为正整数)。该变元组的任意一组确定的值（ u1,un）称为关于p1,pn的一个完全指派，其中ui或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式的关于该变元组的部分指派。 定义：凡使公式取真的指派称为的成真指派。,49,命题公式,定义：如果一个命题公式的所有完全指派均为成真指派，则该公式称为永真式。如果一个命题公式的所有完全指派均为成假指派，则该公式称为永假式。既不是永真式，又不是永假式，则称此命题公式是可满足式。 讨论： （）永真式的否定为永假式（）；永假式的否定为永真式（）。 （）二个永真式的析取、合取、蕴含、等价

16、均为永真式。,50,4等价式,等价式 定义：如果对两个公式，不论作何种指派，它们真值均相同，则称，是逻辑等价的，亦说（）等价于（）。 并记作：,51,4等价式,例：,52,4等价式,例：判断公式A：(PQ)(PQ) 与B：(PR)(PR)是否等价。 解： 列该公式的真值表：,53,4等价式,54,4等价式,定理： 命题公式的充要条件是为永真式。 说明： “”为等价关系符，表示和有等价关系。 不为命题公式 “”为等价联结词（运算符），、为命题公式，则（）也为一命题公式。,55,4等价式,证明： （）充分性：为永真式，即、有相同的真值，所以。 （）必要性：，即、有相同的真值表，所以为永真式。 例：

17、证明 ； ,56,4等价式,由定理可知： 若，则 若，C，则,57,4等价式,下面列出组等价公式 （1）双重否定律 （2）同等律 ； （3）交换律 ； ； （4）结合律 （）（）； （）（）； （） （）,58,4等价式,（5）分配律 （）（）（）； （）（）（） （6）摩根律 （）； （） （7）吸收律 （） ； （） ,59,4等价式,（8）蕴含律 （9）等价律 （）（） （10）零律； （11）同一律； （12）互补律； （13）输出律 （）,60,4等价式,（14）归缪律 （）（） （15）逆反律 说明： （）证明上述组等价公式的方法可用真值表法，把改为所得的命题公式为永真式，则成立。

18、,61,4等价式,（2） 、 均满足结合律， 则在单一用、 联结词组成的命题公式中，括号可以省去。 （3）每个等价模式实际给出了无穷多个同类型的具体的命题公式。 例如：(PQ) (P Q)， (PQ) (RS) (P Q) (R S)， (PQ) R) (P Q) R),62,4等价式,置换规则 定义：给定一命题公式，其中P1、P2Pn 是中的原子命题变元， 若（1）用某些命题公式代换中的一些原子命题变元Pi （2）用命题公式i代换Pi，则必须用i代换中的所有Pi 由此而得到的新的命题公式称为命题公式的代换实例,63,4等价式,讨论定义： （）用命题公式只能代换原子命题变元，而不能去代换分子命

19、题公式 。 （）要用命题公式同时代换同一个原子命题变元 。 （）永真式的代换实例仍为永真式；反之代换实例为永真式时，则不能断定原公式也一定是永真式。,64,4等价式,例：为一永真式，若用任何命题公式代换，则仍为永真式 为一个可满足的命题公式，若用代换，则得（）为永真式，但（）并不是永真式。 （）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式,65,4等价式,例 设：（Q）若用（）代换中的， 得：（）（Q（）是的代换实例， 而：（）（Q）不是B的代换实例。 例的代换实例有：（），（），（）等 所以，一个命题公式的代换实例有无限个。,66,4等价式,下面讨论取代过程（置换规则）：

20、定义：给定一命题公式，是的任何部分，若也是一命题公式，则称是的子命题公式。 例：（）（） 的子命题公式有：、（）、 （）、（）、 （）（）等。,67,4等价式,定理：给定一命题公式，是的子公式。设B是一命题公式，若 B，并用B取代中的，从而生成一新的命题公式B，则B。 从定理可见：一个命题公式A，经多次取代，所得到的新公式与原公式等价。 例：证明：（）（） ,68,4等价式,（） （） 例：证明： （）（）（）（）为一永真式,69,4等价式,证明：原式： （）（）（）（） （）（）（）（） （）（）（）（）（） （）（）（）（） 它是（永真式）的代换实例，永真式的代换实例仍为永真式！,70,4

21、等价式,对偶原理（对偶定律） 定义：给定二个命题公式和A* ，若用代换，用代换，用代换，用代换，其中一个命题公式由另一个命题公式得来，则称和A*是互为对偶的，而联结词和也是互为对偶的 例：写出下列命题公式的对偶式： （） （） 对偶式 A* ,71,4等价式,讨论定义： （）若命题公式中有联结词，则必须把化成由联结词， ，组成的等价的命题公式，然后求它的对偶式； 例：求(PQ)(PR)的对偶式,72,4等价式,（）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。 例：（）对偶式写成 （），而不能写成,73,4等价式,定理：（摩根推广定理） 设和

22、A*为对偶式P1,P2Pn 是出现在和A*中的所有原子命题变元，于是有： （P1，P2Pn） A* （P1，P2Pn）（1） （P1，P2Pn） A*（P1，P2Pn）（）,74,4等价式,证明：由摩根定理 （）（） （）（） 不难看出：一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。 例：设（，） （），验证上述定理：,75,4等价式,证明： ()（，） （，） A*（，） A*（ ， ， ） （）（ ， ， ） A*（，） （ ） 有（ ， ， ） A*（，）,76,4等价式,定理：若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若，则A*B*成立。 证明：已知：、

23、为任一命题公式，且，要证明A*B* 设：P1、P2Pn 是出现在和中的原子命题变元，,77,4等价式,由， 即（P1，P2Pn） （P1，P2Pn） （P1，P2Pn） （P1，P2Pn） 由摩根推广定理 *（P1，P2Pn） *（P1，P2Pn）,78,4等价式,*（P1，P2Pn） *（P1，P2Pn）为永真式 前面讲过永真式的代换实例仍为永真式，所以用 Pi代换A*和B*中的Pi （1in) 则得： *（ P1， P2 Pn） *（ P1， P2 Pn） 即为：*（P1，P2Pn） *（P1，P2Pn）,79,4等价式,例：证明： （）（）（ ） （） （）（） （） （） 证明：（）左

24、边 （） （ ） （） （ ） （ ） （ ） （ ）,80,4等价式,（）左边 （） （） （） （） （） 结论：（）和（）是互为对偶的。,81,5永真蕴含式,定义：命题公式 称为永真蕴含命题公式，当且仅当是一个永真式， 记作： 说明：“ ”读作“永真蕴含”，“蕴含”，“能推得” “ ”是关系符， 不为命题公式。 例：证明： ； P （）列出真值表 证明：（）和（）为永真式,82,5永真蕴含式,（）可用等价公式证： （） （） T （） （） T,83,5永真蕴含式,定理：设、是二个命题公式 的充分必要条件是 且 。 证明：若，则为一永真式 由定律： （）（）（） （）且（）也为一永真式

25、即： 且成立 反之 且 则也成立 此定理把“”和“ ”之间建立了相应的关系。,84,5永真蕴含式,下面给出常用的永真蕴含式 I1 （） I2 （ ） I3（） I4 （） I5 （） I6 （）（） （） I7 （）（） （） I8 （）（） （） I9 P ,85,5永真蕴含式,I10 I11 （） I12（） I13 （）（）（） 证明上述永真蕴含式的方法有三种： （）把“ ”关系符改为“”联结词，证明它为永真式。 (a)真值表法 (b)命题演算法,86,5永真蕴含式,（）找出使单条件命题前件为“”的所有真值指派，试看能否导致后件均为“”，若为“”，则永真蕴含关系成立。,87,5永真蕴含式

26、,例：（） 前件为“”的所有指派为、（）均为“”， 为“”，为“”，也应为“”， （） 成立 （）找出使单条件命题的后件均为“”的所有真值指派，试看前件的所有真值是否为“”，若是，则蕴含成立。,88,5永真蕴含式,例：（） 后件为“”的所有条件是：为“”， 代入前件得 （）若为，则（）为“”； （）若为，则（）为“”； （） 成立 若后件简单则可选用(3)；若前件简单则可选用(2)。 二种方法是互为独立的，只需使用一种证明就行。,89,5永真蕴含式,讨论一下永真式 可得出三个结论： （）若一个命题公式等价于一个永真式，则该公式一定为永真式。 （）若一个永真的命题公式永真蕴含一个命题公式，则此命

27、题公式一定也为永真式。 （）若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。,90,5永真蕴含式,定理：给定命题公式、， 若，且，则。 证明：，且， （）（）为永真式， 由I6：（）（） （）， （）也为永真式；即，成立,91,5永真蕴含式,推论： 若B1、B1 B2Bm ，则。 定理：给定一个命题公式、，若,，则（） 证明：， （）（）为永真式， 由条件，若一定为“”，则、均为“”， （）也为“”， 结论：（）为“”。,92,5永真蕴含式,上述也可用等价公式证明它： （）（） （）（ ） （） （）也为永真式 （）成立 定义：设H1,H2.Hm,均为命题公式

28、，若 （H1 H2Hm ） ，则称： H1,H2.Hm,共同蕴含，并记作： H1,H2.Hm 。,93,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 ）（） 成立,94,6命题联结词总结,其他命题联结词： （）不可兼或（异或，异） (a)符号：“”（），读作“异或” (b)定义：（由真值表） (c)异或的性质： （）（ ） （）（ ） （） （可交换的）

29、（） （ ）（可结合的）,95,6命题联结词总结,（）（） （） （对 可分配的） 若 ，则有： ， ,96,6命题联结词总结,（）“与非”联结词： (a)符号“”，（）读作：“与的否定”或“与非” (b)定义：（由真值表） （）（）,97,6命题联结词总结,(c)性质： （）（） （） （）（）（） （）（）（） （）（）不可结合的 （）（）不可结合的 ，,98,6命题联结词总结,（）“或非”联结词： (a)符号：“” （）读作：“或的否定”或 “或非” (b)定义（由真值表给出）： （） （）,99,6命题联结词总结,(c)性质： （可交换的） （）（） （）（） （）（）不可结合的 （）

30、（） 不可结合的 ； (d)由（）和（）中的性质可见，和是互为对偶的。,100,6命题联结词总结,（4）“ 蕴含否定”联结词： (a)符号： (b)定义 （由真值表给出）： P Q (PQ),“”,c,c,c,101,6命题联结词总结,（）不同真值表的命题公式： 按命题公式的生成规则，用联结词可组成无限个命题公式。下面讨论这些命题公式有多少种不同的真值表： (a)若命题变元只有一个，则用联结词组成的命题公式由四种不同的真值表，即为：,102,6命题联结词总结,所有依赖于的命题公式均等价于这四个中的一个 (b)若有二个命题变元、，则命题公式的不同真值表有：222=24=16种。 推广到一般：若有

31、个变元的命题公式，则可构成不同的真值表为22n（个）。,103,6命题联结词总结,（）二元运算中的全部联结词总结： 、 是五个基本联结词。 到此为止，一个符号系统已定义完毕，它们是： 命题变元 :、 值 :、 运算符 : 、 、 括号 :（） 关系符 : 、,。,C,104,6命题联结词总结,全功能联结词集合： 定义：一个联结词集合，用其中联结词构成的式子足以把一切命题公式等价的表达出来，则称此联结词集合为全功能联结词集合。 定义：设有一联结词集合， 若（）用中的联结词的等价式能表达任何的一个命题公式；,105,6命题联结词总结,（）删除中的任一联结词，从而形成一个新的联结词集合，至少有一个命

32、题公式不能用中的联结词的等价式来表示，则称A为最小的全功能联结词集合。 我们可以证明：，；，；，；均为全功能联结词集合，且均是最小的全功能联结词集合。 例：用上述最小全功能联结词集合中的联结词单一表达下述命题公式：,106,6命题联结词总结,（） ， （） （ ） ， （） ， () ， （ ） （）（） （ ） （ ） （） ,c,c,107,7范式和判定,如何判定命题公式为永真式、永假式和可满足的呢或二个命题公式等价，归纳有三种方法： （1）真值表法：对于变元的所有真值指 派，看对应命题公式的真值。 （2）命题演算方法：化简命题公式至最简式，看是否存在和 （）、（）等价，若不则为可满足的。

33、 （3）范式方法：本节就介绍此法。,108,7范式和判定,什么叫范式 把命题公式化归为一种标准的形式，称此标准形式为范式。 什么叫判定 以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。 讨论范式和主范式的目的就是为了进行判定。,109,7范式和判定,析取范式和合取范式： 设命题变元为：、，则：（）的析取式称为“和”；（）的合取式称为“积”。 定义：命题公式的变元和变元的否定之积称为基本积，而变元和变元的否定之和称为基本和。,110,7范式和判定,例：设、为二个命题变元，则：， ， 称为基本和；， ， ， 称为基本积。 若

34、“基本和”或“基本积”中的子公式”，称为此基本积（和）的因子。 例： 的因子有： 、 、 、 ,111,7范式和判定,定理：一个基本积必定是永假式， 它的充分必要条件是，它至少包含一对因子， 其中一个是另一个的否定。 证明： （）充分条件： 、为基本积中一对因子该基本积一定为永假式。 （）（） （） （）必要条件：基本积为永假式基本积中包含、这对因子。,112,7范式和判定,反证法：假设基本积中不包含、这样的因子，且为永假式。若给基本积中的命题变元指派“”，而命题变元的否定指派为“”， 在基本积中不包含、这对因子， 基本积得到的真值为“”，这和假设相矛盾； 基本积中必然包含、这对因子才能使基本

35、积为“”。,113,7范式和判定,定理：一个“基本和”必定为永真式， 其充要条件（当且仅当）是，它至少包含一对因子，其中一个是另一个的否定。 定义：与给定命题公式等价的一个公式，如果是由基本积之和组成，则称它为命题公式的析取范式。并记为：PP1 P2 Pn（nI+）。其中P1，P2Pn均为基本积。 方法可按下列三步（或四步）进行：,114,7范式 和判定,（）利用等价公式：化去“”、“”联结词，把命题公式变为与其等价的用，表达的公式。 例: ， （）（） （）（） （）将“”深入到原子命题变元之前，并使变元之前最多只有一个“”词。 例：（） ,115,7范式和判定,（）利用“”对“”的分配，将

36、公式化成为析取范式。 （）除去永假项得最简析取范式。 例：求（）（）的析取范式： 解：原式 (（） （）) (（） （）),116,7范式和判定,( （） （）) ( （） （）) -（1）化去词 （ ）（）（ ） -（2）将“”深入到变元前面，并最多保留一个 （ ）（ ）（ ）（ ）（ ） -（3）“”对或“”的分配，化成为析取范式 （）（） -（4）最简析取范式,117,7范式 和判定,讨论定义： （）从上例看出，一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等价的。 （）若一个命题公式的析取范式中每一个基本积均为永假式，则该公式也一定为永假式。 即，PP1P2Pn （P

37、1，P2Pn均为基本积） 则，当P1P2 Pn F时， 一定为永假式。 (可用来判定是否为永假式),118,7范式和判定,例：（析取范式） （ ）（ ） 永假式 定义：与给定命题公式等价的一个公式，如果它是由基本和之积所组成，则称它是给定命题公式的合取范式。 并表示成： Q Q1 Q2 Qn，(nI+),其中Q!,Q2,Qn均为基本和。,119,7范式和判定,求一个命题公式的合取范式的方法和求析取范式的方法类同： 第（）、（）步相同； 第（）利用“”对“”的分配就行； 第（）去掉永真的析取项。,120,7范式和判定,例：求（）（）的合取范式 原式 （）（） 化去“”词 （ ）（ ） “”深入到

38、变元前，并最多保留一个 （）（ ）（ ） “”对“”的分配 （ ）（ ）（ ）（ ） （最简合取范式）,121,7范式和判定,讨论定义： （）给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。 （）若一个命题公式的合取范式中的各基本和的真值为“”，则该命题公式一定是永真式。 (可用来判定是否为永真式) 例：（ ）（）（）,122,7范式和判定,主析取范式。 定义：在个变元的基本积中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此基本积为极小项。 例：对二个命题变元讲，极小项有22=4个，即：、 、 对一个命题变元讲，极小项有21=2个，即：、,1

39、23,7范式和判定,对三个命题变元讲，极小项有23=8个， 即：、 、 、 推广到一般：个命题变元构成的不同极小项有2n个（nI+）。使得每个极小项为真的赋值仅有一个。,124,7范式和判定,定义：对给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的主析取范式。 定理：在真值表中，一个公式的真值为的指派所对应的极小项的析取，即为此公式的主析取范式。,125,7范式和判定,例：求出、 （）、的主析取范式,126,7范式和判定,则可直接写出各命题公式的主析取范式： （ ）（ ）（） （ ）（ ）（） （） （）（）（） （） 讨论此定理： （1）只要命题公式不是永假式，则一定可以根据

40、该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“”的行，对应写出极小项的析取式，且一定是唯一的。,127,7范式和判定,（2）若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2n个极小项。 （3）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。 （4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“”的个数。,128,7范式和判定,下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步： （）将命题公式化归为与其等价的析取范式； （）除去永假项，合并基本积中相同项（例：），变为最简析取范式。 （）利用添变元的方法，将所有基本积变为极小

41、项。,129,7范式和判定,例：二个变元、，利用“”对或“”的分配添项 （） （）（） （） （）（） （）合并相同的极小项变为一项。 例：求（）的主析取范式 解：原式（）（） -（1）化为析取范式,130,7范式和判定, （） -（2）消去永假项，变为最简析取范式 （）（） （）（）（） -（3）添项 （）（） -（4）合并相同最小项,131,7范式和判定,例：证明（） 证明方法是写出二个命题公式的主析范式，看其是否相同： （）（） （）（）（） 而 （）（） （）（）（）（） （）（）（） 主析范式相同，有（） ,132,7范式和判定,主合取范式 定义：在个变元的基本和中，若每个变元与其否

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

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

44、式，则一定有： 主析范式极小项数主合范式极大项数2n 下面介绍不用真值表求一命题公式主合取范式的方法： （1）化为与命题公式等价的合取范式； （2）除去真值为“T”的析取项和除去析取项中相同变元且只保留一个，变为最简合取式； （3）添项，使析取项均变为极大项；,139,7范式和判定,例如：、为二个变元， 即：（） （）（ ） （4）合并相同的极大项，保留一项。 例：求（）的主合取范式 解：原式 （） （） （） （）（ ）,140,7范式和判定,主范式排序（列）的唯一性 （）极小项极其编码 为了确保主范式的唯一性，二个安排： （a）各命题变元的位置安排一固定次序； （b）对极小项、极大项安排一

45、个次序。 对于有个变元的命题公式，则最多可有2n个极小项，用m0 m1 m2n-1来表示。 下面列出三个变元，且、的位置已排定，则,141,7范式和判定,142,7范式和判定,例：设一命题公式有五个变元，P0,P1,P2,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 ）,143,7范式和判定,通过上例归纳出一求极小项m(i)十的方法： (a)把(i)十变换成等价的(J0,J1Jn-1)二 (b

46、)由二进制写出其对应的极小项： 例：求（）（）的编码表达式：（设、次序已定） 解：原式（ ）（ ）（）（ ）,144,7范式和判定, m(001) 二 m(010)二 m(100)二 m(101)二 m(1)十 m(3)十 m(7)十 m(6)十 m1,m3,m7,m61,3,6,7 （）极大项及其编码 用M0,M1,M2n-1表示个变元的命题公式的极大项。 求极大项的方法：,145,7范式和判定,(a)把(i)十变换成等价的(J0,J1Jn-1)二 (b)由二进制数写出其对应的极大项： 例：求（）（）的极大项编码表示（设、次序已定）,146,7范式和判定,解：原式 （）（ ） （ ）（ ）

47、M(000) 二 M(010)二 M(100)二 (110)二 M (0)十 M (2)十 M (4)十 M (5)十 M0,M2,M4,M5 0,2,4,5,147,7范式和判定,极大项和极小项编码约定刚好相反， 从上例中，（）（ ） 1,3,6,7 0,2,4,5 例：写出（ ）的主析和主合编码表示,148,7范式和判定,P Q1 0,2,3 主析范式为：（ ）（ ）（） 主合范式为： P Q 且 P Q（ ）（ ）（）,149,7范式和判定,主范式的个数 在介绍联结词总结时讲到： 一个原子命题变元有四个不同的真值表（221个）； 二个原子命题变元有16个不同的真值表（222个）； 以此类

48、推，若有个变元的命题公式，则可构成22n个不同的真值表。 得到结论： 对于含有个变元的命题公式，必定可写出22n个主范式，若排除永真式或永假式，则实际可写出（ 22n ）个主析（或主合）范式。,150,8推理理论,按公认的推论规则，从前提集合中推导出一个结论来，这样的推导过程称为演绎，或者叫形式证明。 在任何论证中，若认定前提是真的，且从前提集合推导出结论的论证是遵守了逻辑规则的，则我们称此结论是合法的。 根据逻辑规则推导出来的任何结论称为有效结论。 推论规则就是指确定论证的有效性的判据，常是用命题形式表示这些规则，而不涉及实际命题和它的真值。,151,8 推理理论,本节介绍的证明方法，归纳分

49、成三类： （一）真值表技术； （二）推论规则； （三）间接证明法。 真值表技术的主要依据是“”的真值表定义。 若当且仅当 （）为永真式。,152,8推理理论,真值表技术： 定义：给定二个命题公式和，当且仅当是一个永真式，才可以说是从推导出来的，或称是前提的有效结论。 定义：设H1，H2,Hm,都是命题公式，当且仅当H1 H2 Hm ，才可以说是前提集合 H1，H2,Hm 的有效结论。,153,8推理理论,从给定真值表常用的判断方法有二种： （）检查真值表中H1，H2,Hm全部为“”的所有行，看结论是否也均为“”，若均为“”，则结论有效。否则结论无效。 （）看结论为“”的所有行，检查每行前提H1

50、，H2,Hm中是否至少有一个为，若有“”，则结论有效；若有均为“”的行，则结论无效。 例：试证明下列结论是否有效： 画出真值表：,154,8推理理论,由真值表可见： （）， 有效 （）， 无效 （）， （） 有效 （） ， （） 有效,155,8推理理论,（）， 无效 例：H1：如果大连是一个大城市，则大寨是一个乡村； H2：大寨是一个乡村； ：大连是一个大城市； 则：， 或者称：不能从前提集合中推导出来。,156,8推理理论,推理（论）规则： 从这节开始，我们只讨论命题论证的有效性，而不去讨论命题的真假值； 在推论规则中不需要有真值表，也不需要对命题进行真值指派。 推理规则的依据是常用的永真

51、蕴含式和等价公式。 I1； I2； I3，,157,8推理理论,I4 （）， I5 ，（） I6 （），（） （） I7 （） （）（） I8 （），（） （） I9 （），（） （） I10 ,158,8推理理论,下面介绍二个规则： P规则：在推导的任何步骤上都可以引入前提（条件） T规则：在推导过程中，如果前面有一个或多个公式永真蕴含S，则可以把S引入推导过程之中。 例1：证明：PQ,Q R,PR 推理过程：,159,8推理理论,步骤 推理过程 规则 根据(1) PQ P (2) P P (3) Q T I(1)(2) (4) Q R P (5) R T I(3)(4) 也可以这样推理：

52、(1) PQ P (2) Q R P (3) PR T I(1)(2),160,8推理理论,(4) P P (5) R T I(3)(4) 例2 证明： (PQ),(P R),(Q S)SR (1) (PQ) P (2) P Q T(1) E16 (3) Q S P (4) P S T(2)(3) I6 (5) S P T(4) E18,161,8推理理论,(6) P R P (7) S R T(6) I6 (8) SR T(7) E16 下面引进条件证明规则CP：如果能从Q和给定的前提集合P中推导出R来，则就能从前提集合中推导出（Q R）来。 即: (PQR)则：P (QR),162,8推理

53、理论,例1： P(Q S), RP,Q RS 证: (1) R 附加前提 (2) RP P (3) RP T(2) E (4) P T(1)(3) I (5) P(Q S) P (6) Q S T(4)(5) I,163,8推理理论,(7) Q P (8) S T(6)(7) I (9) RS CP 例2: PQ P(P Q) (1) P 附加前提 (2) PQ P (3) Q T(1)(2) I (4) P Q T(1)(3) (5) P(P Q) CP,164,8推理理论,3间接证明法：（反证法、归谬法）定义给出命题公式H1,H2Hm， H1H2 Hm具有真值为“T”，则命题公式集合H1,

54、H2Hm称为是一致的。否则称H1,H2Hm是非一致的。,165,8推理理论,定理设H1,H2Hm是一致的，同时设C是一个命题公式，如果前提集合H1,H2Hm,C是非一致的，则一定有H1,H2HmC成立。 证明：由条件H1H2 Hm C F H1H2 Hm C必定为永假式。而H1H2 Hm是一致的，即为永真式，从而只有C为永假式，则C 一定为永真式， 故H1H2 HmC成立。,166,8推理理论,例：证明 P Q (PQ) 证: (1) ( (PQ) 假设前提 (2) PQ T(1) (3) P T(2) (4) P Q P (5) P T(4) (6) P P T(3)(5) (7) F,16

55、7,8推理理论,例2:证明: RQ, RS , SQ, PQ P (1) (P) 假设前提 (2) P T(1) (3) PQ P (4) Q T(2)(3) (5) SQP (6) QS T(5) (7) S T(4)(6) (8) RS P (9) RT(7)(8),168,8推理理论,(10) RQP (11) QT(9)(10) (12)Q QT(4)(11) 讨论： 由上例可见，间接证明法在结论较为简单的条件下，使用是比较方便的，实际上间接证明法也可以用CP规则代替它。,169,8推理理论,间接证明法：特殊条件下的CP规则 H1H2 Hm C F 由CP规则： H1H2 Hm C F

56、 CF C H1,H2HmC成立,170,8推理理论,例：一位计算机工作者协助公安人员审查一起谋杀案，经调查，他认为下列情况均是真的。 （1）会计张某或邻居王某谋害了厂长。 （2）如果会计张某谋害了厂长，则谋害不可能发生在半夜。 （3）如果邻居王某的证词不正确，则在半夜时房里灯光未灭。 （4）如果邻居王某的证词是正确的，则谋害发生在半夜。 （5）在半夜房子里的灯光灭了，且会计张某曾贪污过。,171,8推理理论,解：设 P：会计张某谋害了厂长 Q：邻居王某谋害了厂长 N：谋害发生在半夜 O：邻居王某的证词是正确的 R：半夜时房子的灯光灭了 A：会计张某曾贪污过列出条件公式：,172,8推理理论,(1) PQ (4) QN (2) PN (5) RA (3) O R 推导过程为： (1) RA P (6) N T (2) R T (7) PN P (3) O R P (8) P T (4