第1章命题逻辑.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二篇 数理逻辑,第二篇 数理逻辑,逻辑学是一门研究人的思维科学,可分为,:,辨证逻辑：以辨证法认识论的世界观为基础的逻辑学,它研究反映客观世界辩证发展过程的人类思维形态的逻辑学。,形式逻辑：研究思维形式结构和规律的学科，是一门工具性学科。,用数学的方法研究形式逻辑中推理规则的理论称为数理逻辑。即以量的形式来研究思维规律。它引入一套符号体系来表示逻辑关系，故此也称符号逻辑。,辩证逻辑 传统演绎逻辑,逻辑学传统形式逻辑 传统归纳逻辑,简单逻辑方法,形式逻辑,现代演绎逻辑,（数理逻辑）,现代形式逻辑 现代归纳逻辑,(,归纳、类比、,概率统计逻辑等）,非标准逻辑,（模态逻辑等）,传统形式逻辑,传统形式逻辑也称普通逻辑,指的是以亚里士多德三段论和培根归纳法为代表的逻辑分支。它研究的对象是日常用的概念、判断和推理等。如直接推理、三段论推理、选言推理、假言推理、枚举归纳、求因果五法等。,特点是使用自然语言来表示判断形式和推理形式。,现代形式逻辑,现代形式逻辑是指以数理逻辑、语言逻辑和归纳逻辑为代表的逻辑分支。,数理逻辑,首先是莱布尼茨提出建立一种类似数学演算的方式来表示思维过程的构想。他这个构想一百年后,1847,年由英国数学家布尔所建立的逻辑代数实现，后来经过弗雷格、罗素和怀特海的努力下，建立了包括命题逻辑和谓词逻辑两个核心演算的数理逻辑。,语言逻辑,语言逻辑包括逻辑语义学和逻辑语用学等，是对人类语言交流中特殊的语言环境和语义要素的深入研究。,归纳逻辑,归纳逻辑包括归纳、类比和概率逻辑等，其中概率逻辑实际上是数学概率论在逻辑推理中的应用。为了解决非必然性推理的结论的可靠性问题而引入概率方法来确定推理的可靠性。,在数理逻辑中，它撇开研究对象的实质含义，把直观的内容抽象为形式化，而且仅仅研究其形式关系，这些形式关系是数理逻辑研究的关键。,数理逻辑在计算机科学中的作用,:,（,1,）在程序设计中的应用。,（,2,）在逻辑电路设计中的应用。,（,3,）在定理证明中的应用。,a.1976,年阿贝尔、黑肯的四色定理证明。,世界政区图,.jpg,b.,张景中院士的几何题机器证明。,张景中,.,ppt,（,4,）在程序正确性证明中的应用。,继续,第一章 命题逻辑,1.1,命题与联结词,1.2,命题公式,1.3,等价公式,1.4,其他联结词及联结词的完备性,1.5,范式,1.6,蕴含公式,1.7,推理理论,第一讲 命题、联接词,教学要求,:,1.,理解命题的基本概念,;,2.,掌握五个基本逻辑联接词,。,重点：,1.,命题；,2.,联接词的含义及应用。,难点：,条件联接词的含义。,第一节 命题与联结词,1.1.1,命题及其表示,人们的思维活动是靠自然语言来表达的。然而,由于自然语言易产生二义性,用它来表示严格的推理就不合适了。为了解决这个问题,在数理逻辑中必须引进了一种形式化的语言。,自然语言的基本单位是句子。,陈述句,自然语句 祈使句,疑问句,感叹句,因为只有陈述句才能够表达对事物有“肯定”或“否定”的思维方式，我们把这种“肯定”和“否定”称为真值（,Truth,）。例如陈述句“今天下雨”，这是一个判断。如果今天真的下雨，则这个判断的值为真,(true),；如果今天没有下雨，则这个判断的值为假（,false,）。,我们把具有这种特点的句子叫命题，它是形式语言中的基本单位。,定义,1-1,在数理逻辑中，把能惟一判断真假的陈述句称为命题,(proposition),，以命题作为研究对象的逻辑称为命题逻辑,(proposition logic),。,命题可能为真，也可能为假。命题的真,(,ture,),、假,(false),统称为命题的真值,(truth values),。真值为真的命题称为真命题,(,ture,proposition),，记作“,1”,（也可记作“,T”,）；真值为假的命题称为假命题,(false proposition),，记作“,0”,（也可记作“,F,”,）。,要判断一个句子是否为命题，应首先判断它是否为陈述句，再判断它是否有惟一的真值；若它是具有惟一真值的陈述句，则为命题。,从以上分析解答可以看出：,命题一定是陈述句，但并非所有陈述句都是命题。,命题必须有惟一确定的真值，但其真值可能受到环境、判断的标准及认识程度的限制，一时无法确定，只要能分辨真假值的判断均为命题。,命题可分为原子命题和复合命题。,定义,1-2,凡不能再分解的命题称为原子命题,(atomic,proposition,),。由原子命题和联结词联结而成的命题称为复合命题,(compound proposition),。,原子命题是命题逻辑的基本单位，是一个不可再分的个体，其真假性独立于其他命题。,有的命题是由原子命题和联结词“非,”,、“不（是）,”,、“,和,”,、“不但,而且,”,、“（或者）,或者,”,、“如果,就（那么）,”,、“,当且仅当,”,等组成。这种,通过一系列的命题联结词,(,或称命题运算符,proposition operator),把原子命题组合起来的命题称为复合命题,(compound proposition,),。,数理逻辑也称符号逻辑，它引入一套符号体系来表示命题和命题之间的联系，这个过程称为命题形式化。,命题形式化可分为原子命题形式化和命题之间联系的形式化。在数理逻辑中，通常用大写英文字母或带下标的大写英文字母,P,，,Q,，,R,，,P,1,，,Q,2,，,来表示命题。,用来表示命题的符号称为命题标识符。,例如,:P,：广州是广东省的省会。,Q,:,今天天下雨。,定义,1-3,如果一个命题标识符代表任意未知命题，则称该命题标识符为命题变元。如果一个命题标识符代表一个确定的命题，则称之为命题常元。,命题变元类似代数中的变量，命题常元类似常量，但两者有着本质的区别。命题变元或常元代表的是命题元素，而变量和常量代表的是一个数值。,命题变元不是命题，因为其真值没有确定。当用确定的命题代入命题变元时称为对命题变元的指派或代入。,如果一个命题变元代表一个原子命题时，称为原子变元。,1.1.2,命题联结词,命题联结词与日常语言中的联结词类似，例如：“如果,那么,”,、“不但,而且,”,、“不”、“并且”、“或者”等等。但这些联结词没有经过严格定义，有的在意义上模棱两可，使用起来不很确切。,在数理逻辑中，联结词必须经过严格定义，它们的含义有时并不完全与日常语言的联结词一致，为了区别，我们把,命题演算中的联结词称为命题联结词或逻辑联结词。,命题联结词与自然语言中的联结词的区别：,命题联结词经过严格定义，不含二义性。,命题联结词只起逻辑联结作用，而不考虑被联结命题的实际含义。,1.,否定（,Negation,）,定义,1-4,设,P,为任意命题，复合命题“非,P,”,（或“,P,的否定”）称为,P,的否定式，记作：,P,。“,”,为否定联结词。命题,P,读作“非,P,”,。,逻辑否定是一个一元联结词，它与日常语言中的“不”、“无”、“没有”、“非”等联结词相似。它是对原命题的否定，其真值与原命题相反。,例如：,p,：今天天下雨。,则,P,：今天天不下雨。,为了书写方便，通常用,0,代替,F,，,1,代替,T,，如表,1-1,。,P,P,0,1,1,0,表,1-1,2.,合取,(conjunction),定义,1-5,设,P,、,Q,为任意两个命题，当这两个命题起着同等重要作用时，可用合取联结词进行联结。记作,p,Q,。,复合命题,p,Q,称为,P,与,Q,的合取式。“,”是合取联结词。命题,P,Q,读作“,P,与,Q,”,，也可读作“,P,与,Q,的合取”。,当且仅当,P,与,Q,同时为真时，,P,Q,为真，否则为假。其真值表如表,1-2,所示。,P Q,0 0,0 1,1 0,1 1,0,0,0,1,表,1-2,例如,P,：李杰学习很努力；,Q,：李杰很聪明。,则,p,Q,表示李杰学习很努力也很聪明。“李杰学习很努力也很聪明”是真，当且仅当“李杰学习很努力”、“李杰很聪明”都是真的。,日常语言中与合取相似的联结词有：“,和,”,、“,与,”,、“,并且,”,、“既,又,”,、“不但,而且,”,、“尽管,仍然,”,，但不等同于自然语言联结词。,例,1-2,将下列命题形式化,（,1,）小刚和小明都是男孩子。,（,2,）张华既会唱歌又会跳舞。,解（,1,）设,P,：小刚是男孩子，,Q,：小明是男孩子；,则该命题符号化为：,P,Q,。,（,2,）设,R,：张华会唱歌，,S,：张华会跳舞；,则该命题符号化为：,R,S,。,【,说明,】,不能一见到,“,和,”,、,“,与,”,就用,“,”,，需要从具体语句的实际含义去判断。例如，,“,韩平和张雷是好朋友,”,是原子命题，因为它无法分解成两个以上的原子命题,所以它不是复合命题。这个,“,和,”,没有逻辑含义。,3.,析取,(disjunction),定义,1-6,设,P,、,Q,为任意两个命题，若,P,和,Q,是一种“或”的关系，,则由析取联结词“,”将命题,P,、,Q,组成的复合命题，称为,P,、,Q,的析取式，记作：,PQ,。命题读作“,P,或,Q,”,，也可读作“,P,与,Q,的析取”。,PQ,为真,当且仅当,P,与,Q,中至少一个为真，因此只有,P,和,Q,同时为假时,PQ,才为假。的真值表如表,1-3,所示。,P Q,0 0,0 1,0,1 1,0,1,1,1,表,1-3,日常语言中的“（或者）,或者,”,、“可能,可能,”,等词均可符号化为“,”。,【,说明,】,析取又称为逻辑“或”。它可分为可兼或（,inclusive or,）和不可兼或（,exclusive or,）。联结词“”代表的是可兼或，还有不可兼或。,例如：命题“小李在看书或听音乐”，这里的“或”显然是“可兼或”；而命题“小李正在教室看书或正在图书馆上网”的“或”是“不可兼或”，因为同一个人不可能同时出现在两个不同的地方。不可兼或指的是二者不能同时存在。因此，析取联结词“”只表示“可兼或”。关于不可兼或将在,1.3.2,中介绍。,例,1-3,将下列命题符号化：,（,1,）小李在看书或听音乐。,（,2,）小李正在教室看书或正在图书馆上网。,（,3,）小张昨天走了三十或四十公里。,解（,1,）设,p,：小李在看书，,Q,：小李在听音乐；,则该命题符号化为：,P,Q,。,（,2,）设,R,：小李正在教室看书，,S,：小李正在图书馆上网；此命题必须使用多个联结词，命题符号化为：。,（,3,）只能作为一个原子命题，其中的“或”表示近似。,4.,条件,(conditional implication),定义,1-7,设,P,、,Q,为任意两个命题，若,P,、,Q,以因果关系的形式组成的复合命题，则称该命题为条件命题，记为,P,Q,。“,”为条件命题联结词。命题,P,Q,读作“如果,P,，,那末,Q,”,，或“,P,推出,Q,”,，也可读作“若,P,，则,Q,”,。,P,为条件命题的前件,(antecedent),，,Q,为条件命题的后件,(consequent),，,P Q,0 0,0 1,0,1 1,1,1,0,1,PQ,的逻辑关系为：,P,是,Q,的充分条件，或,Q,是,P,的必要条件。的真值表如表如右。,在真值表中，除了前件为真，后件为假时为假，其余都为真。,前件为假不是我们考虑的对象，所以不管后件是真还是假，都有为真。这种情况逻辑学上称为“,善意推定,”,。,正是因为这个“善意推定”，阿基米德才会说：“给我一个支点，我能把地球撬起来。”，这句话永远是对的，因为没有谁能给他这样一个支点，前件总为假，不管他能否把地球撬起来，他都是对的。,条件命题,PQ,中，,P,是,Q,的充分条件，,Q,是,P,的必要条件。在自然语言中,P,Q,可翻译为：“如果,P,，那么,Q,”,；“只要,P,，就,Q,”,；“因为,P,，所以,Q,”,；“,P,仅当,Q,”,；“只有,Q,，才,P,”,；“除非,Q,才,P,”,；“除非,Q,，否则非,P”,。,例,1-4,将下列命题符号化,(1),如果明天是晴天，那么明天举行学校运动会。,(2),如果明天举行学校运动会，明天必定是晴天。,(3),如果明天不是晴天，明天不举行学校运动会。,(4),如果明天不举行学校运动会，则明天不是晴天。,解 设,P,：明天是晴天。,Q,：明天举行学校运动会。,（,1,）,原命题,（,2,）逆命题,（,3,）反命题,（,4,）逆反命题,从上述例子可以看出，原命题与逆反命题意思相同（即等价 ），逆命题与反命题意思相同。这一点非常重要，在推理过程中，有时按原命题进行推导比较困难，而用逆反命题却可收到事半功倍的效果。,5.,双条件,(,biconditional,),定义,1-8,给定任意两个命题,P,、,Q,，如果,P,Q,而且,Q P,则由它们组成的复合命题称为双条件命题,记作,:,P Q,。“”为双条件联结词。命题读作“,P,当且仅当,Q,”,。缩写为,P,iff,Q,。,P,Q,的逻辑关系为：,P,与,Q,互为充分必要条件。,P,Q,为真当且仅当,P,与,Q,的真值相同,(,P,与,Q,同为真或,P,与,Q,同为假,),。,P,Q,的真值表如右表所示。,P Q,0 0,0 1,0,1 1,1,0,0,1,例,1-5,符号化下列命题,（,1,）两个三角形全等,当且仅当两个三角形对应边相等。,（,2,）四边形,ABCD,是平行四边形，当且仅当它的对边平行。,解（,1,）,P,：两个三角形全等。,Q,：两个三角形对应边相等。,符号化为：,P,Q,即,P,当且仅当,Q,，（,PQ,）（,QP,）其中,（,PQ,）表示,P,仅当,Q,（,QP,）当,Q,，则,P,1.1.3,逻辑联结词的优先级,为了使命题的符号化变得清晰而简洁，需要给命题联结词规定优先级次序，,5,种联结词也称为逻辑运算符，其优先级次序规定为：“,”,、“”、“”、“”、“”。其中“,”,的优先级最高，“”的优先级最低。,如果有括号，括号最优先。在同一括号层并列两个以上相同的联结词，则按从左到右的顺序运算。例如：,P,Q,R,的含义与,(,p,(,Q,),R,相同，,而与,p,(,Q,),R,),或,p,(,(,Q,R,),的含义不同。,第二讲 命题公式、真值表和命题公式类型,教学要求：,1,、理解命题公式含义；,2,、掌握真值表的构造方法；,3,、利用真值判断命题公式类型。,重点难点：,1,、真值表；,2,、命题公式的翻译。,第二节 命题公式,不包含联结词的命题叫做原子命题,至少包含一个联结词的命题称为复合命题。若命题表达式中包含的是具体的命题，或者命题变元，则称之为命题公式。命题变元称为命题公式的分量。,并非由命题常元、变元、联结词和括号组成的字符串都是命题公式。在此给出一个严谨的定义，在给出定义之前先介绍递归定义（,Inductive definition,）的方法。,递归定义一般用于定义集合的元素，整个过程分为三步：,（,1,）基础：确定某个对象在集合中。,（,2,）递归：确定构造集合元素的方法。,（,3,）界限：确定集合元素的范围。,例如：定义一个非负偶数集合,E,。,解：（,1,）基础：,（,2,）递归：,（,3,）界限：除非有限次地应用基础和递归步造成的数是偶数外，其余均不是偶数。,1,2,1,命题公式,命题公式也称命题演算的合适公式,(Well form formula,简写为,wff,),。,定义,1-6,命题公式的递归定义如下：,(1),单个的命题常元或命题变元是命题公式；,(2),如果,A,是一个命题公式，则,(,A),也是命题公式；,(3),如果,A,和,B,都是命题公式，则,(,A,B),、,(A,B),、,(A,B),、,(A,B),也是命题公式；,(4),当且仅当有限次地应用（,1,）、,(2),、（,3,）所得到的符号串是命题公式外，其余不是命题公式。,例如下列不是命题公式,:P,Q,、,p,Q,、,(,p,Q,),R,、,B,、（,A,B,）,。,而 、是命题公式。,根据逻辑联结词的优先级别可省略一些圆括号，如上述命题公式可写成：、。,【,说明,】,在命题公式的定义中，引进了,A,、,B,等符号，它们可以代表任意的公式，本书以后出现的,A,、,B,等符号除特别说明外，均表示公式。,1,2,2,命题公式的翻译,一、把自然语言描述的命题抽象为形式命题,(,即形式化,),形式化时应注意联结词的选择，确定联结词时除根据自然语言的联结词外，还要考虑语句的实际含义。,例如：大家要取得好成绩，除非努力学习。,其中“除非”是“只有”，除此之外没有其它条件。因此努力学习是取得好成绩的必要条件。,设,P,：大家要取得好成绩；,Q,：大家要努力学习。,则命题形式化为：,练习,(,1),大家只有努力学习，才能取得好成绩。,(2),大家除非努力学习，否则不能取得好成绩。,(3),只要成绩好，学习就肯定努力。,(4),大家要取得好成绩,仅当大家努力学习,.,例,1-6,将下列命题符号化,（,1,）,8,能被,2,整除，但不能被,6,整除。,（,2,）林强学过英语或法语。,（,3,）方梅出生于,1956,年或,1957,年。,解（,1,）设,p,：,8,能被,2,整除，,Q,：,8,能被,6,整除；,则该命题符号化为：,（,2,）设,p,：林强学过英语，,Q,：林强学过法语。,由于林强既可能学过其中一种语言，也可同时学这两种语言，所以这是可兼或。,则该命题符号化为：,（,3,）设,p,：方梅出生于,1956,年，,Q,：方梅出生于,1957,年。,由于方梅可能出生于,1956,年，也可能出生于,1957,年，还可能出生于其它年份，但不可能既出生于,1956,年又出生于,1957,年。所以这是不可兼或。,该命题应符号化为：,自然语言例题中的联接词有显式和隐式,隐式联接词要通过领会题意获取,题,(4),属于这个类型。,例,1-7,设,P:,明天下雨。,Q,:,明天下雪。,R,:,我去学校。,试把下列命题符号化,:,1),如果明天不是雨夹雪,我就去学校。,2),如果明天既不下雨又不下雪,我就去学校。,3),明天下雨或者下雪,我就不去学校。,解：,1,),(,PQ),R,2,)(PQ)R,3,)(P,Q),R,二、把符号命题翻译成自然语言命题,这种翻译比较简单，只要求用词准确，力求保持原命题的意思。,例,设,A,:,今天下雨。,B,:,今天下雪。,C,:,今天天晴。试把下列形式语言翻译成自然语言,:,1)(,A,B,),2),C,(,A,B,),3),A,B,C,解,:1),说今天下雨且下雪是不对的。,2),今天天晴当且仅当今天既不下雨又不下雪。,3),如果今天下雨或者下雪,今天就不是晴天。,习题,1.,将下列命题形式化,小王不但聪明而且能干。,说逻辑学枯燥无味或毫无价值是不对的。,如果有雾，我就不能搭船而是乘车过江。,我现在乘火车或坐飞机。,2.,设,P:,天下雨。,Q,：我将进城。,R,：我有时间。,试将下列命题形式化或翻译成自然语言命题。,天没下雨，我也没有进城。,如果我有时间，我将进城。,如果天不下雨而且我又有时间，我将进城。,（,RQ,）,Q,（,RP,）,（,Q,R,）（,RQ,）,3.,她不但外表美，而且心灵美。,4.,你除非努力,否则你将失败。,1,2,3,真值表,用确定的命题取代命题公式中的命题变元,使之成为命题,这个过程称为对命题公式赋值或指派。,包含命题分量的命题公式没有确定的真值，但可以假设公式中各个分量的不同取值来分析命题公式的真值情况。这样命题公式的真值情况就依赖于命题公式的结构和命题公式中各分量指派的真值。,对命题公式中的各个分量指派一组真值，称这组真值为命题公式的一个解释。,为了使命题公式的真值情况一目了然，可采用真值表的形式表示。,定义,1-9,对命题公式分量真值的各种可能解释，就确定了命题公式的各种真值情况，将其汇成表，就是该公式的真值表。,若一个命题公式包含,n,个命题分量，则对分量真值指派的各种可能组合为,2,n,种。,真值表的构造规则：,（,1,）在真值表左栏按公式中命题分量出现的顺序列出所有分量，右栏列出结果命题。,（,2,）用,0,2,n,-1,的二进制计数顺序给命题分量指派真值。,（,3,）为了使真值表更加明了，可将各层次命题的结果列在命题分量和结果命题之间。,例,1-9,构造命题公式 的真值表。,P Q,0 0,0 1,0,1 1,1,1,0,0,0,1,0,0,1,0,1,1,例,1-10,构造公式 的真值表。,解：,P Q R,0 0 0,0 0 1,0 1 0,0 1 1,0 0,1 0 1,1 0,1 1 1,0 1 1,0 0 0,0 1 1,0 0 0,0 1 1,0 0 0,1 1,1 0 1,0,1,0,1,1,0,1,1,1,2,4,重言式,从真值表中可以发现，某些命题公式不论其分量真值作何指派，其真值总为真，或者总为假。,例,1-11,构造下列命题的真值表。,（,1,）,（,2,）,（,3,）,解,(1),p Q,P,Q,p,(p,Q,),(,p,(p,Q,)Q,0 0,0 1,0,1 1,1,1,0,1,0,0,0,1,1,1,1,1,解（,2,）,P Q,P,Q,(,p,Q,),(,p,Q,),Q,0 0,0 1,1 0,1 1,1,1,0,1,0,0,1,0,0,0,0,0,解（,3,）,p Q R,P,Q,R,(P,Q),R,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,1,1,1,0,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,定义,1-10,（,1,）给定一个命题公式，若无论对其分量真值作何指派，其真值总为真，则称该公式为重言式或永真式。,（,2,）给定一个命题公式，若无论对其分量真值作何指派，其真值总为假，则称该公式为矛盾式或永假式。,（,3,）给定一个命题公式，若对其分量真值的某些指派，其真值为真，而另一些指派其真值为假，则称该命题公式为可满足的或偶然式。,定理,1-1,任何两个重言式的合取或析取仍然是一个重言式。,证明：根据定义，因为任何重言式不论分量真值作何指派，其真值总为真，而两个真值为真的命题的合取或析取一定为真。,练习,1.,构造下列命题公式的真值表,Q,(P,Q),P,(P,Q),(R,Q),R,2.,判别下列命题公式中哪些是重言式,?,矛盾式,?,偶然式,?,(P,Q)(QP),(P,Q),(Q,P)(P,Q),(P,Q)(P,QP),作业,:,(P25),1.2(3)(6),1.3(3)(4),第三讲 等价公式,教学要求：,1,、熟练掌握等价公式；,2,、利用等价公式进行等价演算。,重点难点：,1,、等价演算。,第三节 等价公式,从真值表中可以发现，两个有相同命题分量但结构不同的命题公式，对其分量真值的不同指派，其真值总相同，如：,例,1-12,构造下列命题公式的真值表。,（,1,）构造命题公式 的真值表。,（,2,）构造命题公式 的真值表。,解,(1),P Q,0 0,0 1,0,1 1,1,1 0,0 1,0 0,1,1,0,1,1,1,0,1,1,1,0,1,解（,2,）,P Q,0 0,0 1,0,1 1,1 0 1,1 0 0 0,0 1 0 0,0 0 1 0,1,0,0,1,1,0,0,1,.,.,命题公式的等价,定义,1-11,给定两个命题公式,A,和,B,，设 是所有出现在,A,和,B,中的命题分量，若对 的任一组真值指派，,A,和,B,的真值都相同，则称,A,和,B,等价或逻辑相等。记为,A B,。,从真值表中可知，命题公式,等价；等价。,定理,1-2,设,A,和,B,是任意两个命题公式，,A B,当且仅当,A,B,为重言式。,证明：,若,A B,，则,A,和,B,的真值相同，即同为真或同为假。根据双条件命题的定义,A,B,为真，所以,A,B,为重言式。,若,A,B,为重言式，则,A,B,为永真，根据双条件命题的定义，,A,和,B,的真值相同，所以,A B,。,注意：不是联结词，,A,B,也不是命题公式,。,常用的命题等价公式有：,其中包含否定、合取和析取联结词的等价命题公式称为命题定律，包含条件和双条件联结词的等价命题公式,称为联结词归化。,联结词归化,1,3,2,命题公式的等价演算,在算术运算中,我们可以根据运算符的优先次序，将算术表达式中某一部分用其结果代替，得到的新表达式与原表达式相等。在命题演算中，我们同样可以用命题公式某一部分的等价命题公式代入，所得的新命题公式与原公式等价，这个过程称为置换。置换时要求被置换部分应该是命题合适公式。,定义,1-12,如果,X,是命题公式,A,的一部分，且,X,本身是一个合适公式，则称,X,为公式,A,的子公式,。,定理,1-3,设,X,是命题公式,A,的子公式，若,XY,，如果将,A,中的,X,用,Y,置换，所得的公式,B,与命题公式,A,等价。,证明：,因为在相应分量的任一种真值指派下，,X,和,Y,的真值都相同，用,Y,置换,X,后，公式,B,与,A,在相应分量的真值指派下，其真值仍相同，所以,A,B,。,例,1-13,推导证明吸收律 。,证明：,同一律,分配律,零 律,同一律,例,1-14,推导证明下列各式,（,1,）,证明：,联结词规化,分配律,德,.,摩根公式,（,2,）,证明：,联结词归化,联结词归化,结合律,德,.,摩根公式,联结词归化,例,1-15,已知程序流程图如下,试化简该流程。,P,S,R,S,W,y,n,y,n,解：运行,S,程序段的条件：,P(pR,),运行,W,程序段的条件：,p,R,经过等价变换：,执行程序段,S,的条件为：,执行程序段,W,的条件为：,P,R,S,W,y,n,例,1-16,化简下列各式,（,1,）,解：,（,2,）,解：,利用等价演算可以证明公式的等价，也可以化简形式较复杂的命题公式。除此之外，还可以利用等价演算判断命题公式的类型。若命题公式,A,通过等价演算后,A,等价于,1,，则,A,必为重言式；若,A,等价于,0,，则,A,必为矛盾式。,练习,1.,用推导法证明下列命题公式是等价的,:,P,(QP)P(PQ),(PQ)(P,Q),(,P,Q),P,(QR)(P,Q),(PR),作业,:(P26),1.4 (2)(4),第四讲 其它逻辑运算符及其功能完备性,教学要求：,1,、其它逻辑运算符；,2,、逻辑运算符的功能完备性；,3,、逻辑运算符的功能完备最小集合。,重点难点：,第四节,其它联结词及联结词的完备性能,1,4,1,其它联接词,前面介绍了,、,、,、,五个联接词，除此之外还有联接词 。,其中,1.,异或（,exclusive or),定义：设,P,和,Q,是两个命题，当且仅当,P,和,Q,的真值不相同时，其复合命题的真值为真，否则为假，则称,P,和,Q,为异或,(,排斥或），记为 。,其真值表如下,P Q,0 0,0 1,0,1 1,0,1,1,0,1,4,2,联结词的功能完备性,我们已经介绍了,9,个联结词，除了这,9,个联结词外，是否还需要定义更多的联结词？,设,p,和,Q,是两个命题变元，为运算符。由于,p,和,Q,有,4,种可能的真值指派,(,即,00,01,10,11),所以,恰可构成,2,4,个不等价的命题公式,设达式,则真值表如下：,PQ,F,1,F,2,F,3,F,4,F,5,F,6,F,7,F,8,F,9,F,10,F,11,F,12,F,13,F,14,F,15,F,16,0 0,0 1,1 0,1 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,0,1,1,1,1,0,0,1,1,0,1,1,1,1,0,1,1,1,1,从真值表中可知：为,F,1,、,F,16,为永真和永假式。,F,4,、,F,6,为,p,和,Q,。,F,11,、,F,13,为,p,和,Q,。,F,2,、,F,8,分别为,p,Q,和,p,Q,。,F,3,、,F,5,为 和 。,F,7,为 。,F,9,为 。,F,10,为 。,F,12,、,F,14,分别为,Q,p,和,p,Q,。,F,15,为 。,由上述分析，除永真、永假和命题变元本身外，命题联结词,9,个就够了。,1,4,3,联结词最小功能完备集,虽然定义了上述,9,个联结词，但这些联结词并非在任何情况都是必要的，因为包含某些联结词的公式可以用另外一些联结词的公式进行等价代换。,定义,1-16,一个联结词集，对于任何一个命题公式，都能由仅含该联结词集的命题公式表示，则称该联结词集为联结词功能完备集。对于一个联结词集，如果其中的某一联结词可用联结词集中的其它联结词等价代换，则称该联结词为冗余联结词。,例,1-18,用等价演算法消去联结词集中的冗余联结词，从而产生新的联结词集。考察联结词集 。,（,1,）由 ，故,是冗余联结词，得新的联结词集 。,（,2,）由 ，故,是冗余联结词，得新的联结词集 。,（,3,）由 故 的冗余联结词，得到新的联结词集 。,（,4,）由 ，故 的冗余联结词，得到新的联结词集 。,（,5,）可以证明，与 中不含冗余联结词,.,（,6,）从,(1),、,(2),、,(3),可知，由 中五个联结词组成的命题公式，必可由 或 组成的命题公式所替代。,按以上方法可考察九个联结词的联结词集，不难发现,和 都是功能完备集。,究竟什么是最小功能完备集呢？不含冗余联结词的联结词功能完备集称为联结词最小功能完备集。如,第五讲 蕴含公式,教学要求：,1,、掌握蕴含公式的证明方法；,2,、熟记常见的蕴含公式。,重点难点：,1,、蕴含公式；,2,、蕴含公式的证明。,第六节,蕴含公式,如果双条件命题,A,B,为重言式，则,A B,。而条件命题,AB,是不对称的，如果,A,B,为真，,B,不一定能推出,A,。那么,A,和,B,究竟存在什么关系呢？,1,6,1,蕴含公式,定义,1-26,设,A,，,B,是命题公式,若,A,B,是重言式,则称,A,B,是蕴含重言式，记为,A,B,，,读作“,A,永真蕴含,B,”,。简称,A,蕴含,B,即,AB,iff,A,B,1,注意,:,与,是意义不同的符号。,证明：,所以,P(pQ)Q,下面介绍几种证明,A,永真蕴含,B,的方法。,方法一：用真值表法或等价变换,(,推导,),法证明,A,B,1,例,1-24,证明 。,P Q PQ P,(PQ)(P,(PQ)Q,0 0,0 1,1 0,1 1,1,1,0,1,0,0,0,1,1,1,1,1,方法二：通过分析的方法来证明一个条件命题是蕴含式。由于原命题等价于其逆反命题，即,ABB,A,，所以用分析法证明,A,B,，有如下两种方法,:,(1,),假设前件,A,为真时,推出后件,B,也为真,则,AB,;,(2,),假设后件,B,为假时,推出前件,A,也为假,则,AB,。,例,1-25,证法,1,：假设前件 为,1,，则 。即,Q,为,0,，又因为 为,1,，所以,p,必为,0,。,故此 为,1,。蕴含式成立。,证法,2,：假设后件 为,0,，则,P,为,1,。,(a),若,Q,为,0,，则 为,0,，所以 为,0,。,(b),若,Q,为,1,，则 为,0,，所以 为,0,。,故此 成立。,例,1-26,如果我认真学习，我的“离散数学”不会不及格，,如果我不热衷于玩电子游戏，我将认真学习，,但我的“离散数学”不及格。,结论：我热衷于玩电子游戏。,证明：,设,P,：我认真学习。,Q,：我的“离散数学”及格。,R,：我热衷于玩电子游戏。,符号化为：,设前件 为,1,，则 为,1,、为,1,、为,1,。所以,Q,为,0,，因为 为,1,，所以,p,为,0,。,又因为 为,1,，所以 为,0,，故此,R,为,1,。,所以推导有效。,常见的蕴含重言式,析取三段论,假言推论,拒取式,假言三段论,二难推论,化简式一,附加式,化简式二,例,1-27,分析证明 。,证明：假设后件 为,0,，则,P,为,1,，,R,为,0,。,(a),若,Q,为,1,，则 为,0,，所以 为,0,；,(b),若,Q,为,0,，则 为,0,，所以 为,0,。,故此：成立。,1,6,2,蕴含公式的性质,（,1,）设,A,、,B,是命题公式，若,A,B,且,A,为重言式，则,B,必是重言式。,证明,:,因为,A,B,，所以,A,B,为,1,，又因为,A,为,1,，所以,B,为,1,，即,B,为重言式。,（,2,）蕴含关系是传递的，即,A,B,且,B,C,，则,A,C,。,证明：,因为,A,B,而且,B,C,，所以,A,B,和,B,C,为真。,即,(A,B),(,B,C),为真。根据假言三段论可知,根据性质,1,得,A,C,为真，即,第六讲 逻辑推理,教学要求：,1,、熟练掌握推理规则；,2,、灵活应用推理定律；,3,、合理使用推理方法。,重点难点：,1,、逻辑推理。,第七节,推理理论,逻辑学的主要任务是提出一套推理规则，按照公认的推理规则从前提集合中推导出一个结论来，这个推理过程称为演绎或形式证明。,在一般的论证中，主要是根据实践经验。如果确认前提为真，并遵守恰当的推理规则，则可期望所得的结论也是真的。倘若认定前提是真的，从前提推导出结论的论证是遵守逻辑推理规则，且公认此结论是真实的，则这个论证称为合法论证。一般论证中必须特别注意论证的合法性。,所谓合法是指前提和结论都符合客观实际情况，大家公认是真实的。即合情、合理、合法，令人信服。,在数理逻辑中情况稍有不同，它把注意力集中在推理规则的研究上，如果依据这些推理规则，从前提推导出来的任何结论都称为有效结论，这种论证称为有效论证。在确认论证有效性时，前提与结论的真实性不起任何作用，也就是说，在数理逻辑中，只关心论证的有效性，而不大关心论证的合法性。,有一故事：父子两人上山砍柴，父亲突然被老虎叼走，儿子提起斧子来救。父亲在虎口中说，砍虎脚，不要砍虎身，若砍老虎身，老虎皮就有破洞，将来卖不起价钱。,这个故事中的推理都是有效的，但不合法。为什么？,蕴含式的定义是：给定两个命题公式,A,和,B,，当且仅当,A,B,是一个重言式，则称,A,蕴含,B,，记为,A,B,，又称,B,是,A,的有效结论或,B,由,A,逻辑推出。这个定义可以推广到有,n,个前提的情况。,定义,1-27,设 是命题公式，当且仅当,则称,C,是前提集合 的有效结论。,判别有效结论的过程就是论证的过程，论证方法千变万化，但基本方法是真值表法、直接证法和间接证法。,（一）真值表法,设 是出现的前提集合 和,C,中的所有命题分量，假定对 作全部的真值指派就能确定 和,C,的真值，那么通过真值表就可以确定结论,C,是否是前提集合的有效论证，这个方法称为真值表法。,利用真值表判别一个有效论证的方法：,方法一：,在真值表上，若前提,H,1,H,2,H,3,H,n,均为真的所有行，结论,C,也为真，则论证有效。,方法二：,在真值表上，若结论,C,为假的每一行，其前提,H,1,H,2,H,3,H,n,中至少有一个为假，则论证有效。,例,1-28,如果我认真学习，我的“离散数学”不会不及格，,如果我不热衷于玩电子游戏，我将认真学习，,但我的“离散数学”不及格。,结论：我热衷于玩电子游戏。,P:,我认真学习，,Q:,我的“离散数学”及格，,R:,我热衷于玩电子游戏。,符号化为：,其真值表如下：,解：,判断法一：真值表中，只有第,2,行的前提都为,1,，其结论也为,1,，所以论证有效。,判断法二：真值表中，第,1,、,3,、,5,、,7,行为,0,，每行的前提至少有一个为,0,，所以论证有效。,P Q R,R,p,Q,Rp,Q,R,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,1,0,1,0,1,0,