离散数学课堂PPT(左孝凌版)

《离散数学课堂PPT(左孝凌版)》由会员分享，可在线阅读，更多相关《离散数学课堂PPT(左孝凌版)（442页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,*,第一章 命题逻辑,,1,－,1,命题及其表示法,,1.,什么是命题,,命题：能判断真假的陈述句。,,命题的值叫它的真值。,,真值：“真”：表示判断正确。记作,True,，用,T,表示。,,“假”：表示判断错误。记作,False,，用,F,表示。,,例,1,判断下列句子中哪些是命题？,,（,1,）,2,是素数。,,（,2,）雪是黑色的。,,（,3,）,2+3=5,,,（,4,）明年,10,月,1,日是晴天。,,（,5,）,3,能被,2,整除。,,（,6,）这朵花真好看呀！,,（,7,）明天下午

2、有会吗？,,（,8,）请关上门！,,（,9,）,X+Y>5,,,（,10,）地球外的星球上也有人。,,（,11,）我正在说谎。,,2,．命题的符号化表示,,命题的符号化就是用符号表示命题。,,,简单命题（或原子命题）：简单陈述句表示的命题。用,P,，,Q,，,R,…,,P,i,,Q,i,,R,i,,…,表示。,,,例,P:2,是偶数。,,,Q:,雪是黑色的。,,命题常量（或命题常元）：简单命题。,,命题变项（或命题变元）：真值可以变化的简单陈述句。不是命题。,,例：,x+y,>5,,,命题变项也用,P,，,Q,，,R,…,,,P,i,,Q,i,,R,i,,…,表示。,,,复合命题：由简单命题用

3、联结词联结而成的命题。,,例,2,将下列命题符号化。,,（,1,）,3,不是偶数。,,（,2,）,2,是素数和偶数。,,（,3,）林芳学过英语或日语。,,（,4,）如果角,A,和角,B,是对顶角，则角,A,等于角,B,。,,解：（,1,）设,P,：,3,是偶数。,,ᄀP,（,ᄀ,：表示并非）,,（,2,）设,P,：,2,是素数；,Q,：,2,是偶数。,,,P∧Q ( ∧:,表示和,),,,（,3,）设,P,：林芳学过英语；,Q,：林芳学过日语。,,,P∨Q (∨:,表示或,),,,（,4,）设,P,：角,A,和角,B,是对顶角；,Q,：角,A,等于角,B,。,,,P→Q,（→个表示如果,

4、……,则,……,）,,,1,－,2.,联结词,,定义,1,－,2.1,,设,P,为任一命题，,P,的否定是一个新的命题，称为,P,的,否定式，,记作,ᄀP,。,ᄀ,为,否定联结词。,,,P,ᄀP,,T,,F,,F,,T,例,p,：,3,是偶数。,,,ᄀp,：,3,不是偶数。,,,定义,1,－,2.2,,设,P,、,Q,为两命题，复合命题“,P,并且,Q”,（或“,P,和,Q”,）称为,P,与,Q,的,合取式，,记作,P∧Q,，∧为,合取联结词。,,∧表示自然语言中的“既,……,又,……”,，,,“不仅,……,而且,……”,，,,“虽然,……,但是”,,P,Q,P ∧Q,T,T,T,T,F,F,

5、F,T,F,F,F,F,,例,3,将下列命题符号化。,,（,1,）李平既聪明又用功。,,（,2,）李平虽然聪明，但不用功。,,（,3,）李平不但聪明，而且用功。,,（,3,）李平不是不聪明，而是不用功。,,解：设,P,：李平聪明；,Q,：李平用功。,,（,1,）,P∧Q,,（,2,）,P∧ᄀQ,,（,3,）,P∧Q,,（,4,）,ᄀ,（,ᄀP,）∧,ᄀQ,,,注意：不是见到“和” 、“与”就用 ∧。,,例：“李文和李武是兄弟”，“王芳和陈兰是好朋友”是简单命题。,,定义,1,－,2.3,,设,P,、,Q,为两命题，复合命题“,P,或,Q”,称为,P,与,Q,的,析取式，,记作,P∨Q,，∨为,

6、析取联结词。,P,Q,P ∨Q,T,T,T,T,F,T,F,T,T,F,F,F,,析取式,P∨Q,表示的是一种相容性或，即允许,P,和,Q,同时为真。,,例：“王燕学过英语或日语”,P∨Q,,,自然语言中的“或”具有二义性，有时表示不相容的或。,,例：“派小王或小李中的一人去开会” 。为排斥性的或。,,P,：派小王去开会；,Q,：派小李去开会。,,（,P∧ᄀQ,）∨（,ᄀP∧Q,） ，,,（,P∨Q,）∧,ᄀ,（,P∧Q,）,,定义,1,－,2.4,,设,P,、,Q,为两命题，复合命题“如果,P,，则,Q”,称作,P,与,Q,的,蕴涵式，,记作,P→Q,，→为,蕴涵联结词。,P,Q,P →

7、Q,T,T,T,T,F,F,F,T,T,F,F,T,,在,P→Q,中，,Q,是,P,的必要条件，,P,是,Q,的充分条件。表示自然语言,,“只要,P,就,Q”,，,,“,P,仅当,Q”,，,,“只有,Q,，才,P”,,注意：,1.,在自然语言中，“如果,P,，则,Q”,中的,P,与,Q,往往有某 种内在的联系，但在数理逻辑中，,P→Q,中的,P,与,Q,不一定有内在的联系。,,2.,在数学中，“如果,P,，则,Q”,表示,P,为真，,Q,为真的逻辑关系，但在数理逻辑中，当,P,为假时,P→Q,为真。,,例,4,将下列命题符号化。,,(1),只要不下雨，我就骑自行车上班。,,(2),只有不下雨，

8、我才骑自行车上班。,,(3),若,2+2,＝,4,，则太阳从东方升起。,,(3),若,2+2≠4,，则太阳从东方升起。,,(4),若,2+2,＝,4,，则太阳从西方升起。,,(5),若,2+2≠4,，则太阳从西方升起。,,解：在（,1,）、（,2,）中，设,P,：天下雨；,Q,：我骑自行车上班。,,（,1,）,ᄀP→Q,（,2,）,Q →ᄀP,,在（,3,）－（,6,）中，设,P,：,2+2,＝,4,；,Q,：太阳从东方升起；,R:,太阳从西方升起。,,（,1,）,P→Q,， 真值为,T,（,2,）,ᄀP→Q,， 真值为,T,,（,3,）,P→R,， 真值为,F,（,4,）,ᄀP

9、→R,真值为,T,,定义,1-2.5,,设,P,、,Q,为两命题，复合命题“,P,当且仅当,Q”,称作,P,与,Q,的,等价式，,记作,P⇄,,Q,， ⇄,,为,等价联结词。,,,P⇄Q,表示,P,与,Q,互为充分必要条件,。,,P,Q,P ⇄ Q,T,T,T,T,F,F,F,T,F,F,F,T,,例,5,将下列命题符号化。,,（,1,）,2+2,＝,4,，当且仅当,3,是奇数。,,（,2,）,2+2,＝,4,，当且仅当,3,不是奇数。,,（,3,）,2+2≠4,，当且仅当,3,是奇数。,,（,4,）,2+2≠4,，当且仅当,3,不是奇数。,,（,5,）两圆的面积相等，当且仅当它们的半径相同

10、。,,（,6,）两角相等当且仅当它们是对顶角。,,解：（,1,）－（,4,）设,P,：,2+2,＝,4,；,Q,：,3,是奇数。,,（,1,）,P⇄Q,真命题,,（,2,）,P⇄ᄀQ,假命题,,（,3,）,ᄀP⇄Q,假命题,,（,4,）,ᄀP⇄ᄀQ,真命题,,（,5,）设,P,：两圆的面积相等；,Q,：两圆的面积相同。,,,P⇄Q,真命题,,（,6,）设,P,：两角相等；,Q,：它们是对顶角。,,,P⇄Q,假命题,,4.5,种联结词的优先级顺序：,ᄀ,，∧，∨，→，⇄,,,,1-3,命题公式与翻译,,,,1.,命题公式,,命题公式：由命题常量、,命题变元,、联结词、括号 等组成的符号

11、串。,,,,命题公式中的命题变元称作命题公式的分量。,,定义,1,－,3.1,,（,1,）单个命题常量或命题变 元,,Q,R,…,,Pi,Qi,Ri,,…,,，,F,，,T,是合式公式。,,（,2,）如果,A,是合式公式，则（,ᄀA,）也是合式公式。,,（,3,）如果,A,、,B,是合式公式，则（,A∧B,）、（,A ∨B,）、（,A→B,）、（,A⇄B,）也是合式公式。,,（,4,）只有有限次地应用（,1,）－（,3,）组成的符号串才是合式公式。,,,例：,P, ᄀP, (ᄀP)), (0∧P),P→(P→Q),,,((P∨Q) →R) →(ᄀR),是公式；,,,PQ→R,, ᄀ

12、(P→), ᄀP→Q),不是公式。,,2.,翻译,,翻译就是把自然语言中的有些句子符号化。,,复合命题符号化的基本步骤：,,（,1,）分析出各简单命题，将它们符号化。,,（,2,）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。,,例 将下列命题符号化。,,（,1,）小王是游泳冠军或是百米冠军。,P∨Q,,（,2,）小王现在在宿舍或在图书馆。,P∨Q,,（排斥性或，不可能同时为真）,,(3),选小王或小李中的一人当班长。,,（,P ∧ ᄀQ,）,∨,（,ᄀP∧Q,）或,ᄀ,（,P⇄Q,）,,（排斥性或，可能同时为真）,P,Q,原命题,P⇄Q,ᄀ,（,P⇄Q,）,T,T,F

13、,T,F,T,F,T,F,T,F,T,T,F,T,F,F,F,T,F,,(4),如果我上街，我就去书店看看，除非我很累。,,ᄀR→(P→Q),或 （,ᄀR∧P,）→,Q,（除非：如果不）,,,(5),王一乐是计算机系的学生，他生于,1968,年或,1969,年，他是三好学生。,P∧,（,Q ∨R,）∧,S,,,（,6,）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。,,A,：我们要做到身体好,,B,：我们要做到学习好,,C,：我们要做到工作好,,P,：我们要为祖国四化建设面奋斗。,,命题符号化形式为：（,A∧B∧C,）⇄,P,,,1,－,4,真值表与等价公式,,1.,真值表,,定义,

14、1,－,4.1,含,n,个（,n≥1,）个命题变元（分量）的命题公式，共有,2,n,组真值指派。将命题公式,A,在所有真值指派之下取值的情况列成表，称为,A,的真值表。,,,构造真值表的步骤：,,(1),找出命题公式中所含的所有命题变元,P1,P2,…,,Pn,。列出所有可能的真值指派。,,,(2),对应每种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值。,,例,1,构造求,ᄀP∨Q,的真值表。,P,Q,ᄀP,ᄀP∨Q,T,T,F,T,T,F,F,F,F,T,T,T,F,F,T,T,,例,2,给出（,P∧Q,）∧,ᄀP,的真值表。,P,Q,P∧Q,ᄀP,（,P∧Q,）∧,ᄀP,

15、T,T,T,F,F,T,F,F,F,F,F,T,F,T,F,F,F,F,T,F,,例,3,给出（,P∧Q,）∨（,ᄀP∧ᄀQ,）的真值表。,P,Q,ᄀP,ᄀQ,P∧Q,ᄀP∧ᄀQ,（,P∧Q,）∨（,ᄀP∧ᄀQ,）,T,T,F,F,T,F,T,T,F,F,T,F,F,F,F,T,T,F,F,F,F,F,F,T,T,F,T,T,,例,4,给出,ᄀ,（,P∧Q,）⇄（,ᄀP∨ᄀQ,）的真值表。,P,Q,P∧Q,ᄀ,（,P∧Q,）,ᄀP,ᄀQ,ᄀP∨ᄀQ,ᄀ,（,P∧Q,）⇄（,ᄀP∨ᄀQ,）,T,T,T,F,F,F,F,T,T,F,F,T,F,T,T,T,F,T,F,T,T,F,T,T,F,F,F

16、,T,T,T,T,T,,由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为,T,（,F,）。如例,4,和例,2,,,2,．等价公式,,从真值表中可以看到，有些命题公式在分量的各种指派下，其对应的真值都完全相同，如,ᄀP∨Q,与,P→Q,的对应真值相同。,P,Q,ᄀP,ᄀP∨Q,P→Q,T,T,F,T,T,T,F,F,F,F,F,T,T,T,T,F,F,T,T,T,（,P∧Q,）∨（,ᄀP∧ᄀQ,）与,P⇄Q,对应的真值相同。,,定义,1,－,4.2,,给定两个命题公式,A,和,B,，设,P,1,，,P,2,，,…,，,P,n,为所有出现于,A,和,B

17、,中的原子变元,,,若给,P,1,，,P,2,，,…,，,P,n,任一组真值指派,,A,和,B,的真值都相同,,,则称,A,和,B,是,等价,的或,逻辑相等,。记作,A⇔B,。,,,例,5,证明,P⇄Q⇔,（,P→Q,）∧（,Q→P,）,,证明 列出真值表,P,Q,P→Q,Q→P,(P→Q,）∧,( Q→P,）,P⇄Q,T,T,T,T,T,T,T,F,F,T,F,F,F,T,T,F,F,F,F,F,T,T,T,T,,,24,个重要的等价式,,,,P⇔ᄀᄀP,双重否定律,,P⇔P∨P,等幂律,,P⇔P∧P,,P∨Q⇔Q∨P,交换律,,P∧Q⇔Q∧P,,（,P∨Q,）∨,R⇔P∨,（,Q∨R,）

18、 结合律,,（,P∧Q,）∧,R⇔P∧,（,Q∧R,）,,P∨,（,Q∧R,）⇔（,P∨Q,）∧（,P∨R,） 分配律,,P∧,（,Q∨R,）⇔（,P∧Q,）∨（,P∧R,）,,ᄀ,（,P∨Q,）⇔,ᄀP∧ᄀQ,德,·,摩根律,,ᄀ,（,P∧Q,）⇔,ᄀP∨ᄀQ,,P∨,（,P∧Q,）⇔,P,吸收律,,P∧,（,P∨Q,）⇔,P,,P∨T ⇔T,零律,,P∧F ⇔F,,P∨F⇔P,同一律,,P∧T ⇔P,,P∨ᄀP ⇔T,排中律,,P∧ᄀP ⇔F,矛盾律,,P→Q ⇔ᄀP∨Q,蕴涵等价式,,P,⇄,,Q ⇔,（,P→Q,）∧（,Q→P,） 等价等价式,,P→Q ⇔ᄀQ→ᄀP,假言易位,,P,

19、⇄,,Q ⇔ᄀP,⇄,ᄀQ,等价否定等价式,,（,P→Q,）∧（,P→ᄀQ,）⇔,ᄀP,归谬论,,,,其中,P,、,Q,和,R,代表任意的命题公式,。,,例,6,验证吸收律,P∨,（,P∧Q,）⇔,P,和,,,P∧,（,P∨Q,）⇔,P,P,Q,P,∧,Q,P∨,（,P∧Q,）,P∨Q,P∧,（,P∨Q,）,T,T,T,T,T,T,T,F,F,T,T,T,F,T,F,F,T,F,F,F,F,F,F,F,,定义,1-4.3,,如果,X,是合式公式,A,的一部分,,,且,X,本身也是一个合式 公式,,,则称,X,为公式,A,的子公式。,,,定理,1,－,4.1,如果,X,是合式公式,A,的子公

20、式，若,X⇔Y,，如果将,A,中的,X,用,Y,来置换，所得到公式,B,与公式,A,等价，即,A⇔B,。,,,证明,因为在相应变元的任一种指派下，,X,与,Y,的真值相同，故以,Y,取代,X,后，公式,B,与公式,A,在相应的指派下，其真值必相同，故,A⇔B,。,,,,满足定理,1,－,4.1,的置换称为等价置换（等价代换）,,例,7,证明,P→Q⇔ᄀ,（,P∧ᄀQ,）,,,证明,P→Q ⇔ᄀP∨Q,， （根据蕴涵等价式）,,,,ᄀ P∨Q ⇔ᄀ,（,P∧ᄀq,），（德,·,摩根律）,,,即,P→q⇔ᄀ,（,P∧ᄀq,）,,,例,8,证明,P→(Q→R) ⇔(P∧Q) →R,,,证明,P

21、,→,(Q→R),,,,⇔ᄀP∨(,Q→R,),（蕴涵等价式）,,,⇔,ᄀP∨(ᄀQ∨R),（蕴涵等价式）,,,⇔,(ᄀP∨ᄀQ) ∨R,（结合律）,,,⇔,ᄀ(P∧Q) ∨R,（德,·,摩根律）,,,⇔,(P∧Q) →R,（蕴涵等价式）,,例,9,证明,P⇔(P∧Q) ∨(P∧ᄀQ),,,证明,P,,,⇔P∧,1,(,同一律,),,,,⇔P∧(Q∨ᄀQ),（排中律）,,,,⇔,(P∧Q) ∨(P∧ᄀQ),（分配律）,,练习,1.,证明,Q∨ᄀ( (ᄀP∨Q) ∧P)⇔T;,,2.,证明,(P∨ᄀP) →( (Q∧ᄀQ) ∧R) ⇔F,,3.,证明,(P→Q) ∧ᄀP⇔ᄀP,,1,,证明,Q∨

22、ᄀ( (ᄀP∨Q) ∧P),,⇔Q∨ᄀ( (ᄀP∧P) ∨(P∧Q) ),（分配律）,,⇔,Q∨ᄀ( F ∨(P∧Q) ),（矛盾律）,,⇔,Q∨ᄀ(P∧Q),（同一律）,,⇔,Q∨(ᄀP∨ᄀQ),（德,·,摩根律）,,⇔,(Q∨ᄀQ) ∨ᄀP,（结合律）,,⇔,T∨ᄀP,（排中律）,,⇔,T,（零律）,,2.,证明,(P∨ᄀP) →( (Q∧ᄀQ) ∧R),,⇔T→( (Q∧ᄀQ) ∧R),（排中律）,,⇔,T→(F∧R),（矛盾律 ）,,⇔,T→F,（零律）,,⇔,ᄀT∨F,（蕴涵等值式）,,⇔,F∨F⇔F,（等幂律）,,,3.,证明,(P→Q) ∧ᄀP,,⇔(ᄀP∨Q) ∧ᄀP,（蕴涵等

23、价值式）,,⇔,ᄀP,（吸收律）,,,,,1-5,重言式与蕴涵式,,,定义,1,－,5.1,,给定一命题公式 ，若无论对分量作什么样的指,,派，其对应的真值永为,T,，则称该命题公式 为,重言式,或,永真式,。,,,定义,1,－,5.2,,给定一命题公式 ，若无论对分量作什么样的指,,,派，其对应的真值永为,F,，则称该命题公式 为,矛盾式,或,永假式,。,,,,定理,1,－,5.1,,任何两个重言式的合取或析取，仍然是一个重言式。,,定理,1,－,5.2,,一个 重言式，对同一分量，都 用任何合式公式 置换，其结果仍为一重言式。,,,证明,由于重言式的真值与分量的指派无关，帮对同一分量以任何

24、合式公式置换后，重言式的真值仍永为真。,,对于矛盾式也有类似于定理,1,－,5.1,和定理,5,－,1.2,的结果。,,,例,1,证明 （（,P∨S,）∧,R,）∨,ᄀ,（（,P,∨S,）∧,R,）为重言式。,,证明 因为,P∨ᄀP,⇔T,，用,（（,P∨S,）∧,R,）置换,P,得,,（（,P∨S,）∧,R,）∨,ᄀ,（（,P∨S,）∧,R,）⇔,T,,,,定理,1,－,5.3,,设,A,、,B,为两命题公式,A,⇔,B,，当且仅当,A,⇄B,为一个重言式。,,证明 若,A⇔B,，则,A,、,B,有相同的真值，即有,A⇄B,永为,T,。,,若,A⇄B,为重言式，则,A⇄B,永为,T,， 故,

25、A,、,B,的真值相同，即,A⇔B,。,,例,2,证明,ᄀ,（,P∧Q,）⇔（,ᄀP∨ᄀQ,）,,,证明 做,ᄀ,（,P∧Q,）⇄（,ᄀP∨ᄀQ,）的真值表。,,P,Q,P∧Q,ᄀP,ᄀQ,ᄀ,（,P∧Q,）,ᄀP∨ᄀQ,ᄀ,（,P∧Q,）⇄,ᄀP∨ᄀQ,T,T,T,F,F,F,F,T,T,F,F,F,T,T,T,T,F,T,F,T,F,T,T,T,F,F,F,T,T,T,T,T,由以上真值表可知，,ᄀ,（,P∧Q,）⇄,ᄀP∨ᄀQ,为重言式，根据定理,1,－,5.3,得,ᄀ,（,P∧Q,）⇔（,ᄀP∨ᄀQ,）,,定义,1,－,5.3,,当且仅当,P,→Q,是重言式时，我们称,“,P,蕴涵,Q

26、,”,，并记作,P⇒Q,,。,,做,P→Q Q→P,，,ᄀP→ᄀQ,，,ᄀQ→ᄀp,,的真值表,P,Q,ᄀ,P,ᄀQ,P→Q,,ᄀQ→,ᄀP,Q→P,ᄀP→,ᄀ,Q,T,T,F,F,T,T,T,T,T,F,F,T,F,F,T,T,F,T,T,F,T,T,F,F,F,F,T,T,T,T,T,T,由此得,P→Q ⇔ ᄀQ→ᄀP,，,Q→P⇔ ᄀP→ᄀQ,， 因此要,P⇒Q,，只要证明,ᄀQ⇒ᄀP,，反之亦然。,,,要证明,P⇒Q,，即证,P→Q,是重言式，对于,P→Q,来说，除,P,的真值取,T,，,Q,的真值取,F,这样一种指派时，,P→Q,的真值为,F,外，其余情况,P→Q,的真值为,T,，

27、故要征,P⇒Q,，只要对条件,P→Q,的前件,P,，指定真值为,T,，若由此指出,Q,的真值为,T,，则,P→Q,为重言式，即,P⇒Q,成立；同理，如对条件命题,P→Q,中，假定后件,Q,的真值为,F,，若由此推出,P,的真值为,F,，即推证了,ᄀQ→ᄀP,。 故,P⇒Q,成立。即,,,若,P,为,T,时，推出,Q,为,T,,,或若,Q,为,F,时，推出,P,为,F,,则,P⇒Q,。,,,例,1,推证,ᄀQ∧,（,P→Q,）⇒,ᄀP,,证法,1,假定,ᄀQ ∧,（,P→Q,）为,T,，则,ᄀQ,为,T,，且,P→Q,为,T,。,,所以,Q,为,F,，,P→Q,为,T,，,,所以,P,为,F,，

28、故,ᄀP,为,T,。,,证法,2,假定,ᄀP,为,F,，则,P,为,T,，,,①若,Q,为,F,，则,P→Q,为,F,，,ᄀQ∧,（,P→Q,）为,F,，,,②若,Q,为,T,，则,ᄀQ,为,F,，,ᄀQ∧,（,P→Q,）为,F,，,,所以,ᄀQ∧,（,P→Q,）⇒,ᄀP,,常用的蕴涵式如下：,,P∧Q ⇒P,,P∧Q ⇒Q,,P⇒P∨Q,,ᄀP⇒P→Q,,Q⇒P→Q,,ᄀ,（,P→Q,） ⇒,P,,ᄀ,（,P→Q,） ⇒,ᄀQ,,P∧,（,P→Q,）⇒,Q,,ᄀQ∧,（,P→Q,）⇒,ᄀp,,ᄀP∧,（,P∨Q,）⇒,Q,,（,P→Q,）∧（,Q→R,）⇒,P→R,,（,P∨Q,）∧（,P→

29、R,）∧（,Q→R,）⇒,R,,（,P→Q,）∧（,R→S,）⇒（,P∧R,）→（,Q∧S,）,,（,P,⇄,Q,）∧（,Q,⇄,R,）⇒（,P,⇄,R,）,,,,定理,1,－,5.4,,设,P,、,Q,为任意两个 命题公式，,P,⇔,Q,的充分,,必要条件是,P,⇒,Q,且,Q,⇒,P,,证明 若,P⇔Q,，则,P,⇄,Q,为重言式。,,因为,P⇄Q ⇔,（,P,→,Q,）∧（,Q→P,），,,故,P→Q,为,T,， 且,Q→P,为,T,，,,因为,P⇒Q,且,Q→P,成立。,,反之，若,P⇒Q,且,Q⇒P,，,,则,P→Q,为,T,， 且,Q→P,为,T,，,,因此,P⇄Q ⇔,（,P

30、→Q,）∧（,Q→P,）为,T,，,,即,P⇔Q,,,,这个定理也可以作为两个公式等价的定义。,,蕴涵的几个常用的性质：,,（,1,）设,A,、,B,、,C,为合式公式，若,A⇒B,且,A,为重言式，则,B,也是重 言式。,,证明 因为,A→B,永为,T,，所以当,A,为,T,时，,B,必,T,。,,（,2,）若,A⇒B,，,B⇒C,，则,A⇒C,,,证明 由,A⇒B,，,B⇒C,得,A→B,，,B→C,为重言式,,所以（,A→B,）∧（,B→C,）为重言式，,,根据（,P→Q,）∧（,Q→R,）⇒,P→R,,,所以 （,A→B,）∧（,B→C,）⇒,A→C,，,,由性质（,1,）得：,A→C

31、,为重言式，即,A⇒C,,,（,3,）,A⇒B,，且,A⇒C,，那么,A⇒,（,B∧C,）,,证明 由假设知,A→B,，,A→C,为重言式。,,①设,A,这,T,，则,B,、,C,为,T,，,,故,B∧C,为,T,，,,因此,A→,（,B∧C,）为,T,，,,②若,A,为,F,，则,A→,（,B∧C,）为,T,，,,所以,A⇒,（,B,∧,C,）,,,,,,（,4,）若,A⇒B,且,C⇒B,，则,A∨C,⇒,B,,,证明 因为,A→B,为,T,，,C→B,为,T,，,,故（,ᄀA,∨B,）∧（,ᄀC ∨B,）为,T,，,,则（,ᄀA∧ᄀC,）∨,B,为,T,，,,即,ᄀ,（,A∨C,）∨,

32、B,为,T,，,,即 （,A∨C,）→,B,为,T,，,,所以（,A∨C,）,⇒,B,,,,,,1,－,6,其他联结词,,,定义,1,－,6.3,,设,P,、,Q,是两个命题公式，复合命题,P↑ Q,称作,P,和,Q,的“与非”。,,P↑Q⇔ᄀ,（,P∧Q,）,P,Q,P ↑ Q,T,T,F,T,F,T,F,T,T,F,F,T,,联结词“↑”的几个性质：,,（,1,）,P↑P ⇔ ᄀ,（,P∧P,）⇔,ᄀp,,（,2,） （,P↑Q,）↑（,P↑Q,）⇔,ᄀ,（,P↑Q,）⇔,P∧Q,,（,3,）（,P↑P,）↑（,Q↑Q,）⇔,ᄀP↑ᄀQ⇔,,ᄀ,（,ᄀP∧ᄀq,）⇔,P∨Q,,,定义,

33、1,－,6.3,,设,P,、,Q,是两个命题公式，复合命题,P,↓,Q,称作,P,和,Q,的“或非”。,,P↓,,Q⇔ᄀ,（,P,∨,Q,）,,,P,Q,P ↓ Q,T,T,F,T,F,F,F,T,F,F,F,T,,联结词“↓,,”的几个性质：,,（,1,）,P↓,,P ⇔ ᄀ,（,P∨P,）⇔,ᄀp,,（,2,） （,P ↓Q,）,↓,（,P↓Q,）⇔,ᄀ,（,P↓Q,）⇔,P∨Q,,（,3,）（,P↓P,）↓（,Q↓Q,）⇔,ᄀP↓ᄀQ ⇔ P∧Q,,,,当有,n,个命题变元时，可构成,2,2,n,种不等价的命题公式，如,n,＝,2,时，有,16,种不等价的命题公式。，见,27,页表,1

34、,－,6.5,。,,,,,最小联结词组：对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。,,由于（,1,）（,P,⇄Q,）,⇔（,P→Q,）∧（,Q→P,）,,（,2,）（,P→Q,）⇔,ᄀP∨Q,,,（,3,）,P∧Q⇔ᄀ,（,ᄀ P∨ ᄀ Q,）,,（,4,）,P∨Q⇔ᄀ,（,ᄀP∧ᄀq,）,,故由“,ᄀ”,、“∧”、“∨”，“→”、“⇄”这五个联结词组成的命题公式，必可以由,{ᄀ,，∧,},或,{ᄀ,，∨,},组成的命题公式所替代。,,,1,－,7,对偶与范式,,定义,1,－,7.1,在给定的命题公式,A,中，将∨换成∧，∧换成∨，若有特殊变元,F,和,T,亦相互取代，所得

35、命题公式,A*,称为,A,的对偶式。,,,A,和,A*,互为对偶式。,,例,1: P∧Q,与,P∨Q,,,ᄀ(P∧Q ),与,ᄀ(P∨Q),,( P∨Q) ∧R,与,(P∧Q) ∨R,,ᄀ(P∧T) ∨Q,与,ᄀ(P ∨F) ∧Q,均为对偶式,.,,,例,2,：,P↑Q,、,P ↓Q,的对偶式。,,解：,P↑Q⇔ ᄀ(P∧Q ),，,P↑Q,的对偶式为,ᄀ(P∨Q),,,,P ↓Q⇔ᄀ,（,P∨Q,）,，,P ↓Q,的对偶式为,ᄀ(P∧Q ),,,,定理,1,－,7.1,设,A,和,A*,互为对偶式,, P,1,,P,2,,…,,P,n,，是出现在,A,和,A*,中的全部的命题变元,,,则,,

36、,ᄀ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,),,,例,:,设,A(P,Q,R) ⇔P∧(ᄀQ∨R) ①,,,得,:A*(P,Q,R) ⇔P∨(ᄀQ∧R) ②,,(1),由①知,: ᄀA(P,Q,R) ⇔ᄀP∨(Q∧ᄀR),,,由②知,: A*(ᄀP, ᄀQ, ᄀR) ⇔ᄀP∨(Q∧ᄀR),,,所以,: ᄀA(P,Q,R) ⇔A*(ᄀP, ᄀQ, ᄀR),,类似地,,,有,A(ᄀP, ᄀQ, ᄀR) ⇔ᄀA*(P

37、,Q, R),,,,定理,1,－,7.2,设,P,1,,P,2,,…,,P,n,,是出现有命题公式,A,和,B,中的所有命题变元，若,A ⇔B,，则,A* ⇔B*,。,,证明：因为,A ⇔B,，,,即,A(P1,P2,…,,Pn,) ⇄ B(P1,P2,…,,Pn,),是重言式，,,,,A(ᄀP1, ᄀP2,…,,ᄀPn,) ⇄ B(ᄀP1, ᄀP2,…,,ᄀPn,),是重言式，,,,故,A(ᄀP1, ᄀP2,…,,ᄀPn,) ⇔ B(ᄀP1, ᄀP2,…,,ᄀPn,),,,由定理,1,－,7.1,得,,,ᄀ A*(P1,P2,…,,Pn,) ⇔ᄀ B*(P1,P2,…,,Pn,),,,,因此

38、,A* ⇔B*,,,,例,4,如果,A(P,Q,R),是,P↑,（,Q∧ᄀ,（,R↓P,）），求它的对偶式,A*(P,Q,R),。并求与,A,及,A*,等价，但仅包含联结词“,ᄀ”,、“∧”、“∨”的公式。,,解： 因,A(P,Q,R),是,P↑,（,Q∧ᄀ,（,R↓P,））,,故,A*(P,Q,R),是,P ↓,（,Q∨ᄀ,（,R↑P,））,,但,P↑,（,Q∧ᄀ,（,R↓P,））,,⇔,P↑,（,Q∧,（,R,∨,P,））,,⇔,ᄀ,（,P∧,（,Q∧,（,R∨P,）））,,所以,P ↓,（,Q∨ᄀ,（,R↑P,）） ⇔,ᄀ(P∨,（,Q,∨,（,R∧P,））,),,,,,,,定义,1,

39、－,7.2,,一个命题公式 称为,合取范式,，当且仅当它具有形式,A,1,∧A,2,∧…,∧,A,n,（,n≥1,）。其中,A,1,，,A,2,，,…,，,A,n,都是命题变元或其否定所组成的析取式。,,,例,ᄀP∨∧(P∨Q) ∧(P∨ᄀP ) ∧(ᄀP∨ᄀR),,,,定义,1,－,7.3,,一个命题公式 称为,析取范式,，当且仅当它具有形式,A,1,∨A,2,∨… ∨ A,n,（,n≥1,）。其中,A,1,，,A,2,，,…,，,A,n,都是命题变元或其否定所组成的合取式。,,,例,(P∧ᄀQ∧ᄀR) ∨,(P∧ᄀQ),∨(,P∧ᄀQ∧R,),,,,求合取范式或 析取范式的步骤：,,（,1

40、,）将公式中的联结词化归成,ᄀ,、∧、∨。,,（,2,）将,ᄀ,消去或内移。,,（,3,）利用分配律、交换律求合取范式或析取范式。,,（求合取范式：∨对∧；,,求析取范式： ∧对∨ ）,,注意任何命题的析取范式和合取范式都不是唯一的。,,,,例求下面命题公式的合取范式和析取范式。,,（（,P∨Q,）→,R,）→,P,,解（,1,）求合取范式,,（（,P∨Q,）→,R,）→,P,,⇔,（,ᄀ,（,P∨Q,）∨,R,）→,P,,⇔ᄀ(ᄀ(P∨Q) ∨R) ∨P,,⇔ᄀ((ᄀP∧ᄀQ) ∨R) ∨P,,⇔(ᄀ(ᄀP∧ᄀQ) ∧ᄀR) ∨P,,⇔((ᄀᄀP∨ᄀᄀQ) ∧ᄀR) ∨P,,⇔,((P∨Q

41、) ∧ᄀR) ∨P,,⇔(P∨Q∨P) ∧(ᄀR∨P),,⇔,（,P∨Q,）∧,(ᄀR∨P),,(2),求析取范式,,((P∨Q) ∧ᄀR) ∨P,,⇔(P∧ᄀR) ∨(Q∧ᄀR) ∨P⇔,P∨,（,P∧,ᄀ R,）,∨,,(Q∧ᄀR),,⇔P∨(Q∧ᄀR),,练习：求下面命题公式的合取范式和析取范式。,,（,1,）求合取范式,,(P→Q),⇄,,R,,⇔(ᄀP∨Q),⇄,,R,,⇔((ᄀP∨Q) →R) ∧(R→(ᄀP∨Q)),,⇔(ᄀ(ᄀP∨Q) ∨R) ∧(ᄀR∨(ᄀP∨Q)),,⇔((P∧ᄀQ) ∨R) ∧(ᄀR∨ᄀP∨Q),,⇔(P∨R) ∧(ᄀQ∨R) ∧(ᄀR∨ᄀP∨Q),,（,

42、2,）求析取范式,,((P∧ᄀQ,),∨R) ∧(ᄀR∨ᄀP∨Q),,⇔,（,(P∧ᄀQ) ∧(ᄀR∨ᄀP∨Q),）∨,(R∧(ᄀR∨ᄀP∨Q)),,⇔((P∧ᄀQ) ∧ᄀR) ∨((P∧ᄀQ) ∧ᄀP) ∨((P∧ᄀQ) ∧Q)),,∨((R∧ᄀR) ∨(R∧ᄀP) ∨(R∧Q)),,⇔ (P∧ᄀQ∧ᄀR) ∨,(P∧ᄀP∧ᄀQ),∨(,P∧ᄀQ∧Q,),,∨,(R∧ᄀR),∨(ᄀP∧R) ∨(Q∧R),,⇔ (P∧ᄀQ∧ᄀR) ∨(ᄀP∧R) ∨(Q∧R),,定义,1,－,7.4,n,个命题变元的合取式，称作布尔合取或小项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,,

43、,n,个命题变元 共有,2,n,个小项。,,例两个命题变元,P,和,Q,，其小项为：,P∧Q,，,P∧ᄀQ,，,ᄀP∧Q,，,ᄀP∧ᄀQ,,3,个命题变项,P,、,Q,、,R,可形成,8,个小项：,,,m,000,,⇔ᄀP∧ᄀQ∧ᄀR,,m,001,⇔ᄀP∧ᄀQ∧R,,m,010,⇔ᄀP∧Q∧ᄀR,,m,011,⇔ᄀP∧Q∧R,,m,100,⇔P∧ᄀQ∧ᄀR,,M,101,⇔P∧ᄀQ∧R,,m,110,⇔P∧Q∧ᄀR,,m,111,⇔P∧Q∧R,,,小项的性质：,,（,1,）每一个小项当其真值指派与编码相同时，其真值为,T,，其余均为,F,。,,（,2,）任意两个不同小项的合取永为,F,。,,

44、（,3,）,m,0,∨m,1,∨m,2,∨m,3,∨m,4,∨m,5,∨m,6,∨m,7,⇔T,,,,定义,1,－,7.3,,对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。,,,定理,1,－,7.3,,在真值表中，一个 公式的真值为,T,的指派所对小项的析取，即为此公式的主析取范式。,,例,6,给定,P →Q,，,P∨Q,和,ᄀ,（,P∧Q,），求这些公式的主析取范式。,,解：真值表如下：,P,Q,P,→Q,P∨Q,ᄀ,（,[P∧Q,）,T,T,T,T,F,T,F,F,T,T,F,T,T,T,T,F,F,T,F,T,故,P →Q⇔,（,ᄀP∧ᄀ

45、Q,）∨（,ᄀP∧Q,）∨（,P∧Q,）,,,P∨Q⇔,（,ᄀP∧Q,）∨（,P∧ᄀQ,）∨（,P∧Q,）,,ᄀ,（,P∧Q,）⇔（,ᄀP∧ᄀQ,）∨（,ᄀP∧Q,）∨（,P∧Q,）,,例,7,设一公式,A,的真值表如下，求公式,A,的主析取范式。,P,Q,R,A,T,T,T,T,T,T,F,F,T,F,T,F,T,F,F,T,F,T,T,F,F,T,F,F,F,F,T,F,F,F,F,T,解 公式,A,的主析取范式 为：,,A⇔,（,ᄀP∧ᄀQ∧,ᄀ,R,）∨（,P∧ᄀR∧ᄀR,）∨（,P∧Q∧R,）,,例,8,求（,P∧Q,）∨（,ᄀP∧R,）∨（,Q∧R,）的主析取范式。,,解：原式⇔（

46、,P∧Q∧,（,R∨ᄀR,））,,∨（,ᄀP∧R∧,（,Q∨ᄀQ,））,,∨（,Q∧R∧,（,P∨ᄀp,））,,,⇔（,P∧Q∧R,）∨（,P∧Q∧ᄀR,）∨,,（,ᄀP∧Q∧R,）∨（,ᄀP∧ᄀQ∧R,）∨,,,（,P∧Q∧R,）∨（,ᄀP∧Q∧R,）,,⇔（,P∧Q∧R,）∨（,P∧Q∧ᄀR,）∨,,（,ᄀP∧Q∧R,）∨（,ᄀP∧ᄀQ∧R,）,,例,9,求,P,→,（（,P,→Q,）∧,ᄀ,（,ᄀQ∨ᄀP,））的主析取范式。,,解：原式⇔,ᄀP∨,（（,ᄀP,∨,Q,）,∧,（,Q∧P,））,,⇔,ᄀP∨,（（,ᄀP∧Q∧P,）∨（,Q∧Q∧P,））,,⇔,ᄀP∨,（,Q∧P,）,,⇔,

47、ᄀP∧,（,Q∨ᄀQ,）∨（,P∧Q,）,,⇔（,ᄀP∧Q,）∨（,ᄀP∧ᄀQ,）∨（,P∧Q,）,,求主析取范式的步骤：,,（,1,）求析取范式。,,（,2,）去掉永假的析取项。,,（,3,）去掉重复的合取项、合并相同变元。,,（,4,）对合取项补入没出现的命题变元。（,P∨ᄀP,）,,,定义,1,－,7.6,n,个命题变元的析取式，称作布尔析取或大项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,,,,n,个命题变元 共有,2n,个小项。,,,例 两个命题变元,P,和,Q,，其小项为：,P∨Q,，,,,P∨ᄀQ,，,ᄀP∨Q,，,ᄀP∨ᄀQ,,,,3,个命题变项,P,、,

48、Q,、,R,可形成,8,个大项：,,,M,000,,⇔P∨Q∨R,,M,001,⇔P∨Q∨,ᄀ,R,,M,010,⇔P∨,ᄀ,Q∨R,,M,011,⇔P∨,ᄀ,Q∨,ᄀ,R,,M,100,⇔,ᄀ,P∨Q∨R,,M,101,⇔,ᄀ,P∨Q∨,ᄀ,R,,M,110,⇔,ᄀ,P∨,ᄀ,Q∨R,,M,111,⇔,ᄀ,P∨,ᄀ,Q∨,ᄀ,R,,,大项的性质：,,,（,1,）每一个大项当其真值指派与编码相同时，其真值为,F,，其余均为,T,。,,,（,2,）任意两个不同大项的析取永为,T,。,,,（,3,）,M,0,∧M,1,∧M,2,∧M,3,∧M,4,∧M,5,∧M,6,∧M,7,⇔F,,,,定义,1

49、,－,7.7,对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。,,,,定理,1,－,7.4,,在真值表中，一个公式的真值为,F,的指派所对大项的合取，即为此公式的主合取范式。,,,例,10,利用真值表求（,P∧Q,）∨（,ᄀP∧R,）的主合取范式与主析取范式。,P,Q,R,P,∧Q,ᄀP,∧R,（,P∧Q,）∨（,ᄀP∧R,）,T,T,T,T,F,T,T,T,F,T,F,T,T,F,T,F,F,F,T,F,F,F,F,F,F,T,T,F,T,T,F,T,F,F,F,F,F,F,T,F,T,T,F,F,F,F,F,F,,主合取范式：（,ᄀ,P∨Q∨

50、,ᄀ,R,）∧（,ᄀ,P∨Q∨R,）∧（,P∨,ᄀ,Q∨R,）∧（,P∨Q∨R,）,,,主析取范式：（,P∧Q∧R,）∨（,P∧Q∧ᄀR,）∨（,ᄀP∧Q∧R,）∨（,ᄀP∧ᄀQ∧R,）,,求主合取范式的步骤：,,（,1,）求合取范式。,,（,2,）去掉所有为,T,的合取项。,,（,3,）合并相同的析取项和变元。,,（,4,）补入没出现的命题变元。（即添加,P∧ᄀP,）,,,,例,11,求,（,P∧Q,）∨（,ᄀP∧R,）的主合取范式。,,解：原式⇔ （,P∧Q,）∨,ᄀP,）∧（（,P∧Q,）∨,R,）,,⇔（,P∨ᄀp,）∧（,Q∨ᄀp,）∧（,P∨R,）∧（,Q∨R,）,,⇔ （,Q∨ᄀ

51、p,）∧（,P∨R,）∧（,Q∨R,）,,⇔（,Q∨ᄀP∨,（,R∧ᄀR,））,,∧（,P∨R∨,（,Q∧ᄀQ,））,,∧（,Q∨R∨,（,P∧ᄀP,））,,⇔ （,Q∨ᄀP∨R,）∧（,Q∨ᄀP∨ᄀR,）,,∧（,P∨R∨Q,）∧（,P∨R∨ᄀQ,）,,∧,（,Q∨R∨P,）∧（,Q∨R∨ᄀP,）,,⇔（,ᄀP∨Q,∨,R,）∧（,ᄀP,∨Q,∨ᄀR,）,,∧（,P∨,ᄀQ,∨R,）∧（,P∨Q∨R,）,,用,∑表示小项的析取,,用∏表示大项的合取,,例如,（,P∧Q,）∨（,ᄀP∧R,）,,,⇔（,ᄀP∨Q∨R,）∧（,ᄀP∨Q∨ᄀR,）,,∧（,P∨ᄀQ∨R,）∧（,P∨Q∨R,）,,,

52、⇔,M,000,∧M,010,∧M,100,∧M,101,,,⇔∏0,2,4,5,,,⇔m,001,∨m,011,∨m,110,∨m,111,,,⇔∑1,3,6,7,,,1-8,推理理论,,推理是从前提推出结论的思维过程,,,前提是指已知的命题公式,,,结论是从前提出发应用推理规则推出来的命题公式。前提可以是多个 。,,,定义,1,－,8.1,设,H,1,，,H,2,，,…,，,H,n,,，,C,是命题公式，若（,H,1,∧H,2,∧…∧,H,n,）→,C,为重言式,,,则称,C,是一组前提,H,1,,H,2,,…,,H,n,的有效结论。记作：,,,H,1,∧H,2,∧…∧,H,n,⇒,,C,

53、,,,真值表法,,推理方法 直接证法,,间接证法,,,（,1,）真值表法,,若,H,1,，,H,2,，,…,，,H,n,都为,T,的行，,C,也为真；,,或若,C,为假的行，,H,1,，,H,2,，,…,，,H,n,,中至少有一个为假,,,则,H,1,∧H,2,∧…∧,H,n,⇒ C,成立。,,,,例,1,一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。,,解：设,P,：统计表格的错误是由于材料不可靠。,,,Q,：统计表格的错误是由于计算不可靠。,,前提是：,P∨Q,，,ᄀP,，结论是：,Q,，即证明,

54、,（,P∨Q,）,∧,ᄀP⇒ Q,P,Q,P∨Q,ᄀP,T,T,T,F,T,F,T,F,F,T,T,T,F,F,F,T,故（,P∨Q,）,∧,ᄀP⇒ Q,,,,例,2,如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可以得到解答。,,解：设,P,：张老师来了。,,,Q,：李老师来了。,,,R,：这个问题可以得到解答。,,本题可译为：,,（,P →R,）∧（,Q→R,）∧（,P∨Q,）⇒,R,,P,Q,R,P,→R,Q,→R,P∨Q,T,T,T,T,T,T,T,T,F,F,F,T,T,F,T,T,T,T,T,F,F,F,T,T,F,

55、T,T,T,T,T,F,T,F,T,F,T,F,F,T,T,T,F,F,F,F,T,T,F,,（,2,）直接证法,,,就是由一组前提，利用一些公认的推理规则，根据已知的等价公式或蕴涵公式，推出有效结论。,,,P,规则：前提在推导过程中随时可以引用。,,,T,规则：已经推出的公式在以后的推导过程中可随时引用。,,常用蕴涵式见,43,页表,1,－,8.3,,例,1,证明（,P∨Q,）,∧,（,P,→R,）,∧（,Q→S,）,⇒,S,∨R,,,证法,1,（,1,）,P∨Q P,,,（,2,）,ᄀP,→Q T,（,1,）

56、,E,,,（,3,）,Q→S P,,,（,4,）,ᄀP→S T,（,2,），（,3,）,I,,,（,5,）,ᄀS→P T,（,4,）,E,,,（,6,）,P→R P,,,（,7,）,ᄀS→R T,（,5,），（,6,）,I,,,（,8,）,S∨R T,（,7,）,E,,,证法,2,（,1,）,P→R

57、 P,,,（,2,）,P∨Q→R∨Q T,（,1,）,I,,,（,3,）,Q→S P,,,（,4,）,Q∨R→S∨R T,（,3,）,I,,,（,5,）,P∨Q→S∨R T,（,2,），（,4,）,I,,,（,6,）,P∨Q P,,,（,7,）,S∨R T,（,5,），（,6,）,I,,,例,2,证明（,W∨R,）→

58、,V,，,V→C∨S,，,S→U,，,ᄀC ∧ᄀU ⇒ᄀW,,证明,（,1,）,ᄀC ∧ᄀU P,,,（,2,）,ᄀU T,（,1,）,I,,,（,3,）,S→U P,,,（,4,）,ᄀS T,（,2,）,,,（,3,）,I,,(5) ᄀC T,（,1,

59、）,I,,(6) ᄀC ∧ᄀS T(4),(5) I,,(7) ᄀ(C ∨S) T(6)E,,(8),（,W∨R,）→,V P,,(9) V→(C∨S) P,,(10),（,W∨R,）→,(C∨S) T(8),(9)I,,(11) ᄀ(,（,W∨R,）,T(7),(10)I,,(12) ᄀW ∧ᄀR T(11

60、)E,,(13) ᄀW T(12)E,,(3),间接证法,1(,归谬法,),,,要证,H,1,∧H,2,∧…∧,H,n,⇒ C,,,即要证,H,1,∧H,2,∧…∧,H,n,→ C,为重言式,,,H,1,∧H,2,∧…∧,H,n,→C,,,⇔,ᄀ(H,1,∧H,2,∧…∧,H,n,) ∨C,,⇔ᄀ(H,1,∧H,2,∧…∧,H,n,∧ᄀ,C),,因此只要证,H,1,∧H,2,∧…∧,H,n,∧ᄀ,C,为矛盾式,.,,,,,例,3,证明,A→B, ᄀ(B∨C),可逻辑推出,ᄀA,,证明,(1) A→B

61、 P,,(2) A P(,附加前提,),,(3) ᄀ(B∨C) P,,(4) ᄀB∧ᄀC T(3)E,,(5) B T(1),(2)I,,(6) ᄀB T(4) I,,(7) B∧ᄀB (,矛盾,) T(5),(6

62、) I,,例,4,证明,(P∨Q) ∧(P→R) ∧(Q→S) ⇒S∨R,,证明,(1) ᄀ(S∨R) P,,(2) ᄀS∧ᄀR T(1)E,,(3) P∨Q P,,(4) ᄀP→Q T(3)E,,(5) Q→S P,,(6) ᄀP→S

63、 T(4),(5) I,,(7) ᄀS→P T(6),,(8) (ᄀS∧,ᄀR,) →(P∧,ᄀR,) T(7) I,,(9) P∧ᄀR T(2),(8) I,,(10) P→R P,,(11) ᄀP ∨R T(10)E,,(12)

64、ᄀ(P ∧ᄀR,) T(11)E,,(13),(P ∧ᄀR,),∧ᄀ(P ∧ᄀR,) (,矛盾,) T(9),(12) I,,(4),间接证法,2(,附加前提法,),,要证,H1∧H2∧…∧,Hn,⇒ R→C,,只要证,( H1∧H2∧…∧,Hn,)→(R→ C),为重言式,,,(H1∧H2∧…∧,Hn,)→(R→ C),,⇔ᄀ( H1∧H2∧…∧,Hn,) ∨(ᄀR∨ C),,⇔ᄀ( H1∧H2∧…∧,Hn∧R,) ∨ C,,⇔( H1∧H2∧…∧,Hn,∧R) → C,,只要证,( H1∧H2∧…∧,Hn,∧,R,) ⇒ C,,由

65、,(S∧R) ⇒ C,证得,S⇒(R → C),称为,CP,规则,。,,例,5,证明,A →(B→C), ᄀD∨A, B,重言蕴涵,D→C,,证明,(1) D P(,附加前提,),,(2) ᄀD∨A P,,(3) A T(1),(2) I,,(4) A →(B→C) P,,(5) B→C T(3),(4) I,,(

66、6) B P,,(7) C T(5),(6) I,,(8) D→C CP,,例,6,设有下列情况,,,结论是否有效,?,,(a),或者是天晴,,,或者是下雨。,,(b),如果是天晴，我去看电影。,,(c),如果我去看电影，我就不看书。,,结论：如果我在看书则天在下雨。,,解 若设,M,：天晴。,Q,：下雨 。,,,S,：我看电影。,R,：我看书。,,即证：,M,∀Q,，,M,→S,，,S→ᄀR,，推出,R→Q,,其中,M∀Q ⇔ᄀ(M,⇄Q,）,,,(1) R P,（附加前提）,,,(2) S→ᄀR P,,(3) R →ᄀS T(2) E,,(