离散数学第1章.ppt

Click to edit Master title style,*,*,*,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,离散数学,主讲：杨建华,1,第1章 命题逻辑,1.1 命题符号化及联结词,1.2 命题公式及分类,1.3 等值演算,1.4 联结词全功能集,1.5 对偶与范式,1.6 推理理论,2,1.1 命题符号化及联结词,命题,真值：,T（1）F（0）,命题标识符,3,命题联结词,复合命题,、,原子,命题,命题联结词 否定,l,合取,析取,蕴涵,等价,4,否定,定义1.1,设,P,表示一个命题，复合命题,“,非,P,”,称为,P,的否定式，记作,l,P,。,l,为否定联结词。,l,P,为真当且仅当,P,为假。,5,合取,定义1.2,设,P,和,Q,为两个命题，复合命题“,P,并且,Q,”（,或“,P,和,Q,”）,称作,P,与,Q,的合取式，记作,P,Q。,为合取联结词。,P,Q,为真当且仅当,P,与,Q,同时为真。,6,析取,定义1.3,设,P,和,Q,为两个命题，复合命题“,P,或,Q,”，,称作,P,与,Q,的析取式，记作,P,Q。,为析取联结词。,P,Q,为真当且仅当,P,与,Q,至少一个为真。,7,蕴涵,定义1.4,设,P,和,Q,为两个命题复合命题“如果,P，,则,Q,”,称作,P,与,Q,的蕴涵式，记作,P,Q,，,称,P,为蕴涵式的前件，,Q,为蕴涵式的后件,称作蕴涵联结词。,P,Q,为,假,当且仅当,P,为真而,Q,为假。,8,等价,定义1.5,设,P,和,Q,为两个命题，复合命题“,P,当且仅当,Q,”,称作,P,与,Q,的等价式，记作,P,Q,。,称作等价联结词。,P,Q,为真当且仅当,P,、,Q,真值相同。,9,真值,P Q,l,P,PQ,P,Q,PQ,P,Q,0 0,1,0,0,1,1,0 1,1,0,1,1,0,1 0,0,0,1,0,0,1 1,0,1,1,1,1,10,1.2 命题公式及分类,原子：单个命题变元和命题常元称为原子命题公式，简称原子公式或原子。,命题公式：复合命题，称为合式公式，也简称为公式。,11,命题公式,定义1.6,公式是由下列规则生成的：,单个原子公式是公式。,若,P,是公式，则,l,P,也是公式。,若,P,、,Q,是公式，则(,P,Q,)、(,P,Q,)、(,P,Q,),和(,P,Q,),都是公式。,只有有限次使用、和生成的符号串才是公式。,12,解释,定义1.8,设,A,为一公式，,p,1,p,2,p,n,为出现在,A,中的所有的命题变项。给,p,1,p,2,p,n,指定一组真值，称为对,A,的一个赋值或解释。,若指定的一组值使,A,的值为真，则称这组值为,A,的成真赋值;若使,A,的值为假，则称这组值为,A,的成假赋值。,13,真值表,P,Q,R,P,Q,P,QR,0,0,0,0,1,0,0,1,0,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,P,Q,R,P,QR,0,0,0,1,0,0,1,1,0,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,1,1,0,0,1,1,1,1,14,分类,定义1.9,设,A,为任意公式，则,若,A,在各种赋值下取值均为真，则称,A,为重言式，或永真式(恒真式)。,若,A,在各种赋值下取值均为假，则称,A,为矛盾式，或永假式(恒假式)。,若,A,至少存在一组赋值是成真赋值，则称,A,为可满足式。,15,1.3 等值演算,定义1.10,设,A,和,B,是两个命题公式，若,A,B,是永真式，则称,A,与,B,是等值的，或逻辑相等，记作,A,B,。,16,等值式有下列性质：,自反性，即对任意公式,A,，,有,A,A,。,对称性，即对任意公式,A,和,B,，,若,A,B,，,则,B,A,。,传递性，即对任意公式,A,、,B,和,C,，,若,A,B,、,B,C,，,则,A,C,。,17,基本等值式,命题定律,双否定,:(1),A,A,幂等律：,(2),A,A,A,(3),A,A,A,交换律：,(4),A,B,B,A,(5),A,BB,A,A,B,B,A,18,基本等值式,结合律：,(6)(,A,B,),C,A,(,B,C,),(7),(,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),分配律:,(8),A,(,B,C,),(,A,B,)(,A,C,),(9),A,(,B,C,),(,A,B,)(,A,C,),德摩根律,：,(10),(,A,B,),A,B,(11),(,A,B,),A,B,19,基本等值式,吸收律：,(12),A,(,A,B,),A,(13),A,(,A,B,),A,零 律：,(14),A,T,T,(15),A,F,F,同一律：,(16),A,F,A,(17),A,T,A,排中律:,(18),A,A,T,互补律：,(19),A,A,F,(,矛盾律),20,基本等值式,蕴涵等值式,：(20),A,B,A,B,等价等值式,：,(21),A,B,(,A,B,)(,B,A,),假言易位,：(22),A,B,B,A,(,逆反律),等价否定等值式：(23),A,B,A,B,归谬律：,(24),(,A,B,)(,A,B,),A,21,置换规则,子公式：公式之中含有的公式,定理1.1,设公式,A,是命题公式,(,A,),的子公式，,(,B,),是用公式,B,置换了,(,A,),中的,A,之后得到的命题公式。如果,A,B,，,则,(,A,),(,B,)。,该定理称为置换规则。,22,代入规则,定理1.1.1,在一个永真式,A,中，任何一个原子命题变元,R,出现的每一处，用任意另一个公式代入，所得公式,B,仍是永真式。,本定理称为代入规则。,23,等值演算,证明,P,l,Q,Q,P,Q,P,l,Q,Q,Q,（,P,l,Q,）,交换律,（,Q,P）,（,Q,l,Q,）,分配律,（,Q,P）,1,互补律.,置换规则,Q,P,同一律,P,Q,交换律,24,1.4 联结词全功能集,定义1.11,设,A,和,B,是两个命题公式，复合命题“,P,、,Q,之中恰有一个成立”称为,P,与,Q,的排斥或或异或，记作,P,Q。,为异或联结词。,P,Q,为真当且仅当,P,和,Q,的真值不同时25,定义1.12,设,A,和,B,是两个命题公式，复合命题“,P,与,Q,的否定”称为,P,与,Q,的与非式，记作,P,Q。,为与非联结词。,P,Q,为真当且仅当,P,、,Q,不同时为真。,26,定义1.13,设,A,和,B,是两个命题公式，复合命题“,P,或,Q,的否定”称为,P,与,Q,的或非式，记作,P,Q。,为或非联结词。,P,Q,为真当且仅当,P,、,Q,同时为假。,27,极小全功能集,定义1.15,称联结词集,G,为全功能集，如果由,G,中联结词构成的公式能等价表示任意命题公式。,定义1.16,称联结词集,G,为极小全功能集，如果,G,满足条件：由,G,中联结词构成的公式能等价表示任意公式；,G,中的任一联结词不能用其余联结词等价表示。,28,1.5 对偶与范式,定义1.17,在仅含有联结词,、和的命题公式,A,中，若把和互换，0和1互换，所得命题公式称为,A,的对偶式，记作,A,*,。,（,A,*,）,*,=,A,29,对偶,定理1.2,设,A,和,A,*,互为对偶式,p,1,p,n,是出现,A,和,A,*,中的全部的命题变元，则,A,(,p,1,p,2,p,n,),A,*,(,p,1,p,2,p,n,),A,(,p,1,p,2,p,n,),A,*,(,p,1,p,2,p,n,),定理1.3(对偶原理）,设,A,和,B,为两个命题公式，若,A,B,则,A,*,B30,范式,定义1.18,仅由有限个命题变元及其否定构成的析取式，称为简单析取式。,仅由有限个命题变元及其否定构成的合取式，称为简单合取式。,定义1.19,仅由有限个简单合取式构成的析取式，称为析取范式；,仅由有限个简单析取式构成的合取式，称为合取范式。,31,范式存在定理,定理1.4,对于任何一命题公式，都存在与其等值的析取范式和合取范式。,定理1.4.1,简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。,定理1.4.2,简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。,32,定理1.4.3,公式,A,为永假式的充要条件是,A,的析取范式中每个简单合取式至少包含一个命题变元及其否定。,定理1.4.4,公式,A,为永真式的充要条件是,A,的合取范式中每个简单析取式至少包含一个命题变元及其否定,。,33,极小项与极大项,定义1.20,在含有,n,个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为极小项。,定义1.22,在含有,n,个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该简单析取式为极大项。,34,极小项,真值表,P Q,l,P,l,Q,l,P,Q,P,l,Q,PQ,0 0,1,0,0,0,0 1,0,1,0,0,1 0,0,0,1,0,1 1,0,0,0,1,m,0,m,1,m,2,m,3,35,极大项真值表,P Q,P,Q,P,l,Q,l,P,Q,l,P,l,Q,0 0,0,1,1,1,0 1,1,0,1,1,1 0,1,1,0,1,1 1,1,1,1,0,M,0,M,1,M,2,M,3,36,主析取,范式,定义1.21,设公式,A,中含,n,个命题变项，如果,A,的析取范式中，其简单合取式都是极小项，则称该范式为,A,的主析取范式。,定理1.5,任意命题公式的主析取范式都是存在的，并且是惟一的。,37,主合取,范式,定义1.23,设公式,A,中含,n,个命题变项，如果,A,的合取范式中，其简单析取式都是极大项则称该范式为,A,的主合取范式。,定理1.6,任意命题公式的主合取范式都是存在的，并且是惟一的。,38,1.6 推理理论,定义,公式,G、H,，,对任意解释,I，,如果,G,为真，则,H,也为真，则称,H,是,G,的逻辑结论，或,G,逻辑蕴涵,H,。,记为,G,H,。,定理,H,是,G,的逻辑结论，当且仅当,G,H,是永真式。,39,逻辑蕴涵,定义,公式,H,1,H,n,P,，,对任意解释,I，,如果,H,1,H,n,为真，则,P,也为真，则称,P,是,H,1,H,n,的逻辑结论（有效结论），即,H,1,H,2,H,n,逻辑蕴涵,P。,记为,H,1,H,2,H,n,P,。,定理,公式,P,是H,1,H,2,H,n,的逻辑结论，当且仅当,H,1,H,2,H,n,P,是永真式。,40,推理规则,规则(也称前提引入规则)：在推导过程中，前提可视需要引入使用。,规则(也称结论引入规则)：在推导过程中，前面已导出的有效结论都可作为后续推导的前提引入。,置换规则：等值的命题公式可互换。,41,推理定律,(1),P,P,Q,附加,(2),P,，,Q,P,Q,合取引入,(3)(,P,Q,),Q,化简,(4),P,，(,P,Q,),Q,假言推理,(5)(,P,Q,),(,Q,R,),P,R,假言三段论,(6),P,，(,P,Q,),Q,析取三段论,(7),Q,，(,P,Q,),P,拒取式,42,证明方法,直接证明法,H P,间接证明法,HP,P,H,附加前提证明法,规则(附加前提规则)：若推出有效结论为条件式,R,C,时，只需将其前件,R,加入到前提中作为附加前提,再去推出后件,C,即可。,43,第2章 一阶逻辑,2.1 一阶逻辑基本概念,2.2 一阶逻辑合式公式及解释,2.3 一阶逻辑等值式,2.4 一阶逻辑推理理论,44,2.1 一阶逻辑基本概念,谓词,量词,全称量词,存在量词,特性谓词,45,每一个苹果都是红的。,任意一个整数都是有理数。,有些实数是有理数。,存在实数使,x+5=4。,对每一个实数，都有(,x+1),2,=x,2,+2x+1。,46,2.2 一阶逻辑合式公式及解释,定义2.2,项由下列规则形成：,个体常元和个体变元是项；,若,f,是,n,元函数，且,t,1,，,t,2,，,t,n,是项，则,f,(,t,1,，,t,2,，,t,n,),是项；,所有项都由和生成。,定义2.3,若,P,(,x,1,，,x,2,，,x,n,),是,n,元谓词，,t,1,，,t,2,，,t,n,是项，则称,P,(,t,1,，,t,2,，,t,n,),为原子谓词公式，简称原子公式。,47,合式谓词公式,定义2.4,合式谓词公式 定义如下：,原子公式是合式公式；,若,A,是合式公式，则(,A,),是合式公式；,若,A,、,B,是合式公式，则(,A,B,)，(,A,B,)，(,A,B,),和(,A,B,),都是合式公式；,若,A,是合式公式，,x,是个体变元，则(,x,),A,、(,x,),A,都是合式公式；,仅有有限次使用、和形成的才是合式公式。,48,约束变元,定义2.5,一个谓词公式,A,，,其中有一部分形如(,x,),B,(,x,),或(,x,),B,(,x,)，,则称它为,A,的,x,约束部分，称,B,(,x,),为相应量词的作用域或辖域。在辖域中，,x,的所有出现称为约束出现，,x,称为约束变元；,B,中不是约束出现的其它个体变元的出现称为自由出现，这些个体变元称自由变元,。,49,闭式,定义2.6,设,A,为任意一个公式，若,A,中无自由出现的个体变元，则称,A,为封闭的合式公式，简称闭式。,50,改名规则,约束变元改名规则：将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。,自由变元代入规则：对某自由出现的个体变元可用个体常元或与原公式中不同的个体变元去代入，且处处代入。,51,解释,定义2.7,一个解释,I,由下面4部分组成：,非空个体域,D,I,D,I,中部分特定元素,D,I,上一些特定函数,D,I,上一些特定谓词,52,公式,分类,定义2.8,设,A,为一公式，,如果,A,在任何解释下都是真的，则称,A,为逻辑有效式，或永真式；,如果,A,在任何解释下都是假的，则称,A,为矛盾式，或永假式；,若至少存在一个解释使,A,为真，则称,A,为可满足式。,53,2.3 一阶逻辑等值式,定义2.10,设,A,、,B,为任意两个公式，若,A,B,为逻辑有效的，则称,A,与,B,是等价的，记为,A,B,，,称,A,B,为等值式。,54,量词否定等,值,式,定理2.1,量词否定等价式：,(1,),(,x,),A,(,x,),(,x,),A,(,x,),(2),(,x,),A,(,x,),(,x,),A,(,x,),A,(,x,),为任意公式,55,量词辖域缩小或扩大等值式,定理2.2,(1)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(2)(,x,)(,A,(,x,),B),(,x,),A,(,x,),B,(3)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(4)(,x,)(,B,A,(,x,),B,(,x,),A,(,x,),(5)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(6)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(7)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(8)(,x,)(,B,A,(,x,),B,(,x,),A,(,x,)。,56,量词分配等,值,式,定理2.3,量词分配等,值,式,(1,)(,x,)(,A,(,x,),B,(,x,),x,),A,(,x,)(,x,),B,(,x,),(2)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),定理,2.4,多重量词等,值,式,(1)(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(2)(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),57,前束范式,定义2.11,设,A,为一个谓词公式，如果它有如下形式：,(,Q,1,x,1,)(,Q,2,x,2,)(,Q,k,x,k,),B，,则称,A,为前束范式。,其中,Q,i,(1,i,k,),为,或,，,B,为不含有量词的谓词公式。,58,2.4 一阶逻辑推理理论,定义,公式,P,是,H,1,H,2,H,n,的逻辑结论，当且仅当,H,1,H,2,H,n,P,是永真式。,定理2.5,(1)(,x,),A,(,x,)(,x,),B,(,x,),(,x,)(,A,(,x,),B,(,x,),(2)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),(3)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),(4)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),59,量词消去规则,全称量词消去规则(简称,UI,或,US,规则)：,(,x,),A,(,x,),A,(,c,),其中,c,为任意个体常元,(,x,),A,(,x,),A,(,y,),A,(,x,),对,y,是自由的,存在量词消去规则(简称,EI,或,ES,规则)：,(,x,),A,(,x,),A,(,c,),其中,c,为特定个体常元,60,量词引入规则,全称量词引入规则(简称,UG,规则)：,A,(,x,),(,y,),A,(,y,),存在量词引入规则(简称,EG,规则)：,A,(,c,),(,y,),A,(,y,),其中,c,为特定个体常元,A,(,x,),(,y,),A,(,y,),61,