离散数学-第一章(3.5周)

1、12345678910第一篇 数理逻辑数理逻辑11126 6 重言式与蕴含式重言式与蕴含式7 7 其它联结词其它联结词8 对偶与范试对偶与范试9 推理理论推理理论 1 1、命题：命题：能判定真假的陈述句能判定真假的陈述句 2、命题的定义中包含二层含义命题的定义中包含二层含义 (1)在语法上；在语法上；命题必须是陈述句。而疑问句、祈使句命题必须是陈述句。而疑问句、祈使句 和感叹句等无所谓真假，所以不是命题。和感叹句等无所谓真假，所以不是命题。 (2)命题具有唯一的真值，这与我们是否知道它的真假是两回事。命题具有唯一的真值，这与我们是否知道它的真假是两回事。命题的真值：命题的真值：陈述句为真或为假

2、的这种性质，称为陈述句为真或为假的这种性质，称为命题的真值。命题的真值。真命题：真命题：与事实相符的命题为真命题，其真值为真，与事实相符的命题为真命题，其真值为真， 用用l(或或T)表示；表示；假命题：假命题：与事实不相符的命题则称为假命题，其真与事实不相符的命题则称为假命题，其真值为假，用值为假，用0(或或F)表示。表示。真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题用大写英文字母用大写英文字母 A，B，C, ;A1，A2, , ;n;n表示表示简单命题，这些表示命题的符号称为简单命题，这些表示命题的符号称为命题标识符

3、命题标识符。 例如，令例如，令 P：3 3是有理数，则是有理数，则 p 的真值为的真值为 1 Q：2 + 5 7，则，则 q 的真值为的真值为 0 20 T F PF T P F F F F F T F T P Q T F T T P Q 解解 令令 p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则 (1) pq (2) pq (3) p q.解解 令令 r : 张辉是三好学生，张辉是三好学生，s :王丽是三好学生王丽是三好学生 (4) rs. (5) 令令 t : 张辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题 . F F F T F T T T P Q T F T T

4、 P Q例例 将下列命题符号化将下列命题符号化 (1) 2或或4是素数是素数. (2) 2或或3是素数是素数. (3) 4或或6是素数是素数. (4) 小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨. (5) 王晓红生于王晓红生于1975年或年或1976年年. 3.析取式与析取联结词析取式与析取联结词“” T T F TP Q F F F T T F T T P Q真值关系：“善意的推定善意的推定”注意：注意： pq 与与 q p等值（真值相同）等值（真值相同） pqpqpqpqqp qpqpqp5.双条件双条件(等价式与等价联结词等价式与等价联结词)“”真值关系： T F F T

5、F F F T T F T T P QPQ5.等价式与等价联结词等价式与等价联结词“” 例例 用符号形式表示下列命题。用符号形式表示下列命题。 （1）如果明天早上下雨或下雪，那么我不去学校）如果明天早上下雨或下雪，那么我不去学校 （2）如果明天早上不下雨且不下雪，那么我去学校。）如果明天早上不下雨且不下雪，那么我去学校。 （3）如果明天早上不是雨夹雪，那么我去学校。）如果明天早上不是雨夹雪，那么我去学校。 （4）只有当明天早上不下雨且不下雪时，我才去学校。）只有当明天早上不下雨且不下雪时，我才去学校。 解解 令令P：明天早上下雨；：明天早上下雨； Q：明天早上下雪；：明天早上下雪； R：我去学

6、校。：我去学校。 （2）（）（PP QQ）R； （1）（）（PQ） R；（4 4）RR（PP Q Q） （3） (PQ）R；练习练习 将下列命题符号化将下列命题符号化 （1） 派小王或小李出差；派小王或小李出差； （2） 我们不能既划船又跑步；我们不能既划船又跑步； （3） 如果你来了，那么他唱不唱歌将看你是否伴奏而定；如果你来了，那么他唱不唱歌将看你是否伴奏而定； （4） 如果李明是体育爱好者，但不是文艺爱好者，那么如果李明是体育爱好者，但不是文艺爱好者，那么 李明不是文体爱好者；李明不是文体爱好者； （5） 假如上午不下雨，我去看电影，否则就在家里看书。假如上午不下雨，我去看电影，否则就在

7、家里看书。解解 （1） 令令P：派小王出差；：派小王出差；Q：派小李出差。：派小李出差。 命题符号化为命题符号化为PQ。 （2） 令令P：我们划船；：我们划船；Q：我们跑步。则命题可：我们跑步。则命题可 表示为表示为(PQ）。 （3） 令令P：你来了；：你来了；Q：他唱歌；：他唱歌；R：你伴奏。：你伴奏。 则命题可表示为则命题可表示为 P（QR） （4） 令令P：李明是体育爱好者；：李明是体育爱好者；Q：李明是文艺爱好者。：李明是文艺爱好者。 则命题可表示为则命题可表示为（P Q）（P Q） （5） 令令P：上午下雨；：上午下雨；Q：我去看电影；：我去看电影；R：我在家读书。：我在家读书。 则

8、命题可表示为则命题可表示为（ P Q）（PR）。 例例 B = ( p q) q 的的真值表真值表例例 C= (p q) r 的的真值表真值表 例例 构造下列命题公式的真值表，并判断它们是何种构造下列命题公式的真值表，并判断它们是何种类型的公式类型的公式 （1）（）（PQ） （PQ）；）； （2）（）（QP）（PQ）；）； （3 3）（）（PQPQ）（QRQR）（PPR R）。）。 是是重言式重言式 是可满足公式。是可满足公式。矛盾式。矛盾式。 命题公式的等值关系命题公式的等值关系 定义定义 设设A和和B是两个命题公式是两个命题公式, P1, P2, , Pn 是所有是所有出现于出现于A和和B

9、中的命题变元，如果对于中的命题变元，如果对于P1, P2, , Pn 的任一的任一组真值指派，组真值指派，A和和B的真值都相同的真值都相同,则称公式则称公式A和和B等值，记等值，记为为A B,称称 AB为等值式。为等值式。注意注意： (1) A(1) A与与B B等值等值, ,并不要求并不要求A A与与B B含有相同的命含有相同的命题变元题变元（2 2）符号）符号“”与与“”的区别与联系。的区别与联系。 “”不是联结词，不是联结词，A AB B不表示一个公式，它表示两不表示一个公式，它表示两个公式间的一种关系，即等值关系。个公式间的一种关系，即等值关系。 “”是联结词，是联结词，A AB B是

10、一个公式。是一个公式。 定理定理:AB当且仅当当且仅当AB是永真公式。是永真公式。 （3） 可以验证等值关系是等价关系。可以验证等值关系是等价关系。 即即自反性自反性：对任意公式：对任意公式A，有，有AA。 对称性对称性：对任意公式：对任意公式A，B，若，若AB，则，则BA。 可传递性可传递性：对任意公式：对任意公式A A、B B、C C，若，若A AB B，B BC C，则则A AC C。 （4）当）当A是重言式时，是重言式时，A1；当；当A是矛盾式是矛盾式时，则时，则A0。基本的等值式基本的等值式 设设P、Q、R是命题变元，下表中列出了是命题变元，下表中列出了24个最基本的等值式个最基本的

11、等值式:编号编号 公公 式式E1E1E2E2E3E3E4E4E5E5E6E6E7E7 PQQP 交换律交换律 PQQP 交换律交换律 (PQ)R P(QR) 结合律结合律 (PQ)R P(QR) 结合律结合律 P(QR) (PQ)(PR) 分配律分配律 P(QR) (PQ)(PR) 分配律分配律 P0P 同一律同一律 P1P 同一律同一律 P P1 互否律互否律 P P0 互否律互否律 （ P）P 双重否定律双重否定律 PPP 幂等律幂等律 PP P 幂等律幂等律 编号 公公 式式E8E8E9E9E10E10E11E12E13E14E15P11 零一律 P00 零一律P（PQ）P 吸收律P（P

12、Q）P 吸收律 （PQ）PQ 德.摩根定律 （PQ）PQ 德.摩根定律PQPQPQ (PQ)(PQ)P (QR) (PQ) RPQ (PQ)(QP) PQQP等值式的判别等值式的判别 有两种方法：真值表方法，命题演算方法有两种方法：真值表方法，命题演算方法 1、真值表方法、真值表方法 例例 用真值表方法证明用真值表方法证明 E10： (P Q) PQ 解解 令：令：A= (P Q)，B= PQ，构造，构造A，B 以及以及A B的真值表如下：的真值表如下： PQP Q (P Q) P Q PQAB000111110110100111100101 由于公式由于公式AB所标记的列全为所标记的列全为1

13、，因此，因此AB。 10100001例例 用真值表方法证明用真值表方法证明E E1111：P PQ QP P Q Q解解 令令A=PA=PQ Q，B=B= P P Q Q 构造构造A A，B B以及以及A AB B的真值表如下：的真值表如下：PQ P P QPQAB001111011111100001 由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB.110111 例例 用真值表方法判断用真值表方法判断PQPQ是否成立是否成立. 解解 令令A=PA=PQ Q，B=B= P PQ Q 构造构造A A，B B以及以及A AB B的真值表的真值表PQ P Q PQPQAB00111

14、11011001001100 由于公式由于公式A AB B所标记的列不全为所标记的列不全为1 1，A AB B不是永不是永真公式，因此真公式，因此A AB B不成立。不成立。101100111 (1) 代入规则代入规则 代入规则代入规则 对于重言式中的任一命题变元出现的对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。每一处均用同一命题公式代入，得到的仍是重言式。2等值演算方法等值演算方法 例如例如 F=（PQ）（ QP）是重言式，若）是重言式，若用公式用公式AB代换命题变元代换命题变元P得公式得公式 F1=（AB）Q）（ Q（AB），）， F1仍是重言式。仍是重言

15、式。注意：因为注意：因为A B当且仅当当且仅当A B是重言式。所以，是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。一命题公式代入，则得到的仍是等值式。(2) 置换规则置换规则 定义定义1-101-10 设设C C是命题公式是命题公式A A的一部分（即的一部分（即C C是是公式公式A A中连续的几个符号），且中连续的几个符号），且C C本身也是一个命题本身也是一个命题公式，则称公式，则称C C为公式为公式A A的的子公式。子公式。 例如例如 设公式设公式A=A=（ PQPQ）（P PQ Q）（RR

16、S S）。）。 则则 PQ，PQ，（，（PQ）（R S）等均是）等均是A的子公式，的子公式， 但但 PP，P P和和Q Q等均不是等均不是A A的子公式，的子公式， 置换规则置换规则 设设C C是公式是公式A A的子公式，的子公式，C CD D。如。如果将公式果将公式A A中的子公式中的子公式C C置换成公式置换成公式D D之后，得到的公式之后，得到的公式是是B B，则，则A AB B。 (3) (3) 等值演算等值演算 等值演算是指利用已知的一些等值式，根据置换等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外规则、代入规则以及等值关系的可传递性推导出另

17、外一些等值式的过程。一些等值式的过程。 由代入规则知前述的基本等值式，不仅对任意的命由代入规则知前述的基本等值式，不仅对任意的命题变元题变元P P，Q Q，R R是成立的，而且当是成立的，而且当P P，Q Q，R R分别为命题公分别为命题公式时，这些等值式也成立式时，这些等值式也成立 例例 证明命题公式的等值关系：证明命题公式的等值关系： （PQ）（RQ）（PR）Q；证明证明 （PQ）（RQ） （ PQ）( RQ) E11 （ P R）Q E3 ( 分配律分配律) (PR)Q (德德.摩根定律摩根定律) (PR) Q E11 所以（所以（PQ）（RQ）（PR）Q 例例3 证明下列命题公式的等值

18、关系证明下列命题公式的等值关系 (P Q ) ( P ( P Q ) ) P Q 证明证明 (P Q) ( P ( P Q) (P Q) ( ( P P ) Q ) E2(结合律结合律) (P Q) ( P Q) E7(幂等律幂等律) ( P Q ) ( P Q ) E1 (交换律交换律) P (Q (P Q) E2(结合律结合律) P Q E 1，E9(交换律，吸收律交换律，吸收律) 例例4 判别下列公式的类型。判别下列公式的类型。 （1） Q ( P（ PQ）) （2）（）（PQ） P解解（1） Q （ P（ PQ） Q （P（ PQ） E11,E6 Q （P P）（PQ） E3 Q （1

19、（PQ） E5 Q （PQ） E4 Q P Q E10 （Q Q） P E1,E2 0 E5,E8 所以所以Q ( P ( PQ)是矛盾式。是矛盾式。 （2） （PQ） P （ PQ） P E11 P E9 于是该公式是可满足式。于是该公式是可满足式。 1.5 重言式与蕴含式重言式与蕴含式一、一、重言式的性质及判定重言式的性质及判定1、任两个重言式的合取或析取仍是重言式、任两个重言式的合取或析取仍是重言式2、一个重言式的同一分量都用任何公式置换，仍、一个重言式的同一分量都用任何公式置换，仍为重言式为重言式.3、 AB当且仅当当且仅当A B为为重言式重言式补充：补充： 重言式与蕴含式重言式与蕴含

20、式二、二、蕴含式蕴含式定义定义1-111-11 设设A A，B B是两个公式，若公式是两个公式，若公式A AB B是重言式，即是重言式，即A AB B1 1，则称公式则称公式A A蕴含公式蕴含公式B B，记作，记作A AB B。称。称“A AB”B”为为蕴含式蕴含式。 注意：注意：符号符号“”和和 “ “”的区别和联系与符的区别和联系与符号号“”与与“”的区别和联系类似。的区别和联系类似。 “”不是联结词，不是联结词， “ “AB”不是公式，它表示公式不是公式，它表示公式A与与B之间存在蕴含关系。之间存在蕴含关系。 “”是联系词，是联系词，AB是一个公式。是一个公式。 AB当且仅当当且仅当AB

21、是永真公式是永真公式 。基本的蕴含式基本的蕴含式 编号蕴蕴 含含 式式I1PQPI2PQQI3P PQI4P PQI5QPQI6 (PQ)PI7 (PQ) QI8 设设P P、Q Q、R R是命题变元，下表中列出了是命题变元，下表中列出了1414个最个最基本的蕴含式。基本的蕴含式。P (PQ)Q编号蕴蕴 含含 式式I9 Q (PQ)PI10 P (P Q) QI11(PQ) (QR)PRI12(P Q) (PR) (QR) RI13I14(p-Q) (R-S)=(P R)-(Q S)(pQ) (QR)=(PR)蕴含式的判别蕴含式的判别 判定判定“A B”是否成立的问题可转化为判定是否成立的问题

22、可转化为判定A B是否为重言式，有下述判定方法：是否为重言式，有下述判定方法： （1）真值表；）真值表； （2）等值演算；）等值演算；（3）假定前件）假定前件A为真；为真； （4）假定后件）假定后件B为假。为假。 1. 真值表方法真值表方法 例例 证明证明I14 ：(（PQ）（P R）（Q R）) R 证明证明 令公式令公式 F =（PQ）（PR）（QR）R， 其真值表如下：其真值表如下： 公式公式F对任意的一组真值指派取值均为对任意的一组真值指派取值均为1，故，故F是重言式。是重言式。 2. 等值演算方法等值演算方法 例例 证明证明 I I1111：PP（P PQ Q） Q Q 证明证明 （

23、PP（P PQ Q） Q Q （PP（ PQPQ） Q Q E E2020 （ PP （ PQPQ）Q EQ E1111 （ PQPQ） （ PQPQ） E E6 6 1 1 代入规则代入规则,E,E5 5 因此因此 PP（P PQ Q） Q Q 3. 假定前件假定前件A真真 假定前件假定前件A A为真，检查在此情况下，其后件为真，检查在此情况下，其后件B B是否也为真。是否也为真。 ABAB001011100111 例例证明证明 I12 : Q （PQ） P证明证明令前件令前件 Q（PQ）为真，）为真，则则 Q为真为真, 且且PQ为真。为真。于是于是Q为假，因而为假，因而P也为假。由此也为假

24、。由此 P为真。为真。故蕴含式故蕴含式 I12 成立。成立。 4、 假定后件假定后件B假假 假定后件假定后件B B为假，检查在此情况下，其前件为假，检查在此情况下，其前件A A是否也为假是否也为假. . 例例7 证明蕴含式证明蕴含式(PQ) (RS) (P R) (Q S)证明证明 令后件令后件(P R)(Q S)为假，则为假，则P R为真，为真，Q S为假为假,于是于是P、R均为真，而均为真，而Q和和S至少一个为假。至少一个为假。 由此可知由此可知 PQ与与RS中至少一个为假中至少一个为假, 因此因此(PQ) (RS)为假为假.故上述蕴含式成立。故上述蕴含式成立。74定义定义:逆换式、反换式

25、、逆反式的含义：对逆换式、反换式、逆反式的含义：对PQ而而言，言，QP为其的逆换式，为其的逆换式， P Q为其的反换式，为其的反换式， P为其的逆反式。为其的逆反式。(PQ) ( P )(QP) ( P Q)CC1.7 1.7 对偶与范式对偶与范式一、对偶式一、对偶式 定义定义1-171-17 一个仅含有否定、析取、合取联结一个仅含有否定、析取、合取联结词的命题公式词的命题公式A A，将将它的其中的它的其中的析取变合取、合取变析取变合取、合取变析取、析取、0 0变变1 1、1 1变变0 0后后所得的公式称为原公式的对偶式，所得的公式称为原公式的对偶式，记为记为A A* *。 例题例题1:1:写

26、出下列表达式的对偶式写出下列表达式的对偶式(a)、(P Q)Q) R R(b)、(P Q Q) T T(c)、 (P Q Q) (P (P (Q(Q S)S)解：解：(a)、(P Q)Q) R R(b)、(P Q Q) (c)、 (P Q Q) (P (P (Q(Q S)S)1.7 1.7 对偶与范式对偶与范式一、对偶式一、对偶式例题例题1:1:写出下列表达式的对偶式写出下列表达式的对偶式P Q Q解：解：P Q Q(P(P Q)Q)故对偶式为：故对偶式为： (P(P Q)Q) P Q Q 对偶式是相互的对偶式是相互的 对偶原理：对偶原理：AB,AB,则有则有A A* * BB* *1.7 1

27、.7 对偶与范式对偶与范式二、二、 析取范式和合取范式析取范式和合取范式 定义定义1 1 仅由有限个命题变项或其否定构成的仅由有限个命题变项或其否定构成的合合取式称取式称为简单为简单合合取式，即：取式，即：一个命题公式若它具有一个命题公式若它具有P P1 1* *PP2 2* *PPn n* *的形式（的形式（n1n1），其中），其中P Pi i* *是命题变是命题变元元P Pi i或其否定或其否定PPi i ，也称其为，也称其为质合取式。质合取式。 例如例如,PQRS,PQRS是由命题变元是由命题变元P P、Q Q、R R、S S组成组成的一质合取式。的一质合取式。 1.7 1.7 对偶与范

28、式对偶与范式二、二、 析取范式和合取范式析取范式和合取范式 1、 定义定义2 2 仅由有限个命题变项或其否定构成的析取式称仅由有限个命题变项或其否定构成的析取式称为简单析取式，即：为简单析取式，即：一个命题公式若具有一个命题公式若具有P P1 1* *PP2 2* *PPn n* *（n1n1）的形式，其中）的形式，其中P P* *i i是命题变是命题变元元P Pi i或是其否定或是其否定PPi i ，也称其为，也称其为质析取式质析取式。 例如例如, , QPRQPR是由命题变元是由命题变元P P、Q Q、R R组成的组成的一质析取式。一质析取式。 2 2、定理：、定理： （1）一质合取式为永

29、假式的充分必要条件是，它同时一质合取式为永假式的充分必要条件是，它同时包含某个命题变元包含某个命题变元P及其否定及其否定P。 （2）一质析取式为永真式的充分必要条件是，它同时一质析取式为永真式的充分必要条件是，它同时包含某个命题变元包含某个命题变元P及其否定及其否定P。 例如例如A=P1P2P3.则则(P1,P2,P3)=(0,1,0)的指派，使的指派，使A的真值为的真值为0. 充分性充分性：设：设A含命题变元含命题变元Pi和和Pi，而，而PiPi是永真式，是永真式， 由结合律和零一律，由结合律和零一律，A的真值必为的真值必为1，故，故A也是永真式。也是永真式。 3 3、定义、定义仅由有限个简

30、单合取式构成的析取仅由有限个简单合取式构成的析取式称为析取范式。即具有式称为析取范式。即具有A1A2AA1A2An n(n1)(n1)的形的形式的公式，其中式的公式，其中A Ai i是质合取式。是质合取式。 例如例如，F F1 1=P(PQ)R(=P(PQ)R( PP QR)QR)是一析是一析取范式。取范式。 4 4、定义定义仅由有限个简单析取式构成的合取仅由有限个简单析取式构成的合取式称为合取范式。即具有式称为合取范式。即具有A A1 1AA2 2AAn n (n1)(n1)的形式的公式，其中的形式的公式，其中AiAi是质析取式。是质析取式。 例如例如，F F2 2= = P(PQ)R(PP

31、(PQ)R(P QR)QR)是一合取是一合取范式。范式。F F3 3=(=( PRQ)(PQ)R(PPRQ)(PQ)R(P R)R)也是一也是一合取范式。合取范式。 6、求公式的析取范式和合取范式、求公式的析取范式和合取范式任何一个命题公式都可以变换为与它等值的析任何一个命题公式都可以变换为与它等值的析取范式或合取范式。按下列步骤进行：取范式或合取范式。按下列步骤进行：（1 1）利用）利用E20-EE20-E2424消去公式中的运算符消去公式中的运算符“”和和“”；PQPQ PQ (PQ)( P Q)PQ (PQ)(QP) (2) (2) 利用德利用德 摩根定律将否定符号摩根定律将否定符号“

32、”向内向内延伸，使之只作用于命题变元；延伸，使之只作用于命题变元； （3 3）利用双重否定律）利用双重否定律E E1 1将将 ( ( P)P)置换成置换成P P； （4 4）利用分配律、结合律将公式归约为合取范）利用分配律、结合律将公式归约为合取范式或析取范式。式或析取范式。 例例1 求求F1=(P(QR)S的合取范式和析取范式的合取范式和析取范式 解解 F1 (P( QR)S P ( QR)S P(Q R)S (析取范式析取范式) 又又 F1 P(Q R)S ( PS)(Q R) ( PSQ)( PS R) （合取范式）（合取范式） 另外由另外由 F1 ( PSQ)( PS R)( P( P

33、S R)(S( PS R)(Q( PS R)PS(Q P)(QS)(Q R) （析取范式）（析取范式）例例2 2 求求 F F2 2= = (PQ) (PQ) (PQ) (PQ)的析取范式、合的析取范式、合取范式。取范式。解解F2 ( (PQ) (PQ)(PQ) (PQ) (PQ)(PQ)( (PQ) (PQ) (P(Q(PQ)( P Q( P Q) (PQ)( P Q) （合取范式）（合取范式） (P( P Q)(Q( P Q) (P P) (P Q)( PQ)(Q Q)（析取范式）（析取范式）三、主析取范式和主合取范式三、主析取范式和主合取范式 1、定义：定义：设有命题变元设有命题变元P

34、P1 1，P P2 2，,P,Pn n ，形如形如 的的命题公式称为是由命题变元命题公式称为是由命题变元P P 1 1，P P2 2，P Pn n所产生的所产生的最小项最小项。而形如。而形如 的命题公式称为是由命题变元的命题公式称为是由命题变元P P1 1，P P2 2，P Pn n所产生的所产生的最大项最大项 。其中。其中P Pi i* *为为P Pi i或为或为 P Pi i(i=1,2,n).(i=1,2,n). 例如例如, ,P P1 1PP2 2PP3 3， P P1 1PP2 2 P P3 3均是由均是由P P1 1，P P2 2，P P3 3所所产生的最小项。产生的最小项。P P

35、1 1 P P2 2PP3 3是由是由P P1 1，P P2 2，P P3 3产生的一个产生的一个最大项。最大项。 *1iniP*1iniP 2 2、定义：、定义：若公式若公式A的析取范式中的简单合的析取范式中的简单合取式全是最小项，称取式全是最小项，称为主析取范式。为主析取范式。3 3、定义、定义若公式若公式A的合取范式中的简单析取式全的合取范式中的简单析取式全是最大项，称是最大项，称为主合取范式。为主合取范式。例如例如( ( P P1 1P P2 2 P P3 3) ) ( ( P P1 1 P P2 2 P P3 3) ) (P(P1 1 P P2 2 P P3 3) )是一个主析取范式

36、。是一个主析取范式。 (P(P1 1P P2 2 P P3 3) ) (P(P1 1 P P2 2 P P3 3) ) ( ( P P1 1P P2 2P P3 3) ) ( ( P P1 1 P P2 2P P3 3) )是一个主合取范式。是一个主合取范式。 4 4、用真值表求主范式、用真值表求主范式定理定理1:1:在真值表中在真值表中, ,一个公式的真值为一个公式的真值为T T的指派的指派所对应的小项的析取所对应的小项的析取, ,即为此公式的主析取范即为此公式的主析取范式式. .定理定理2:2:在真值表中在真值表中, ,一个公式的真值为一个公式的真值为F F的指派的指派所对应的大项的合取所

37、对应的大项的合取, ,即为此公式的主合取范即为此公式的主合取范式式. . 例例4 求公式求公式 F1 = (PQ) ( PR) (QR)和和F2=P (PQ) ( Q P)的主析取范式。的主析取范式。 解解 F1 (PQ) ( PR) (QR) (PQ（ R R) ）( PR （ Q Q) ) (QR （ P P) )(PQ R) (PQ R) ( PR Q ) ( PR Q) (QR P ) (QR P)5、求公式的主析取范式和主合取范式、求公式的主析取范式和主合取范式对任一给定的公式除了用求范式时的四个步骤外，还要对任一给定的公式除了用求范式时的四个步骤外，还要利用同一律、等幂律、互否律、

38、分配律等进一步将简单合取利用同一律、等幂律、互否律、分配律等进一步将简单合取式（质析取式）变换为最小项（最大项）的形式。式（质析取式）变换为最小项（最大项）的形式。 定理定理1-6 每一个不为永假的命题公式每一个不为永假的命题公式F F（P P1 1, , P P2 2, , P, , Pn n）必与一个由）必与一个由P P1 1，P P2 2，P Pn n所产生的主所产生的主析取范式等值。析取范式等值。 永真公式永真公式的主析取范式包含所有的主析取范式包含所有2 2n n个最小项。个最小项。 永假公式永假公式的主析取范式是一个空公式。用的主析取范式是一个空公式。用0 0表示。表示。 例例 求

39、公式求公式 F1 = P(P (QP)和公式和公式 F2 = (PQ) (PQ)的主析取范式的主析取范式. 解解 F1P(P( QP) E11 P(P Q)(PP) E3( P(Q Q)(P Q)(P(Q Q) E7,E4,E5 ( PQ)( P Q)(P Q)(PQ)(P Q) E3 ( PQ)( P Q)(P Q)(PQ) E1,E7 F2(PQ) (PQ) ( P Q) (PQ) E11 ( P PQ) (Q PQ) E3 0 0 E 1, E 5 0例例5 求公式求公式 F F1 1= (P= (PQ)Q) (P(PQ)Q)和和 公式公式F F2 2=P=P(P(P (Q(QP)P)的

40、主合取范式的主合取范式F F1 1 ( ( P P Q)Q) (P(PQ) Q) E E1111 ( ( P P Q)Q) (P(P (Q(QQ)Q) ( ( Q Q (P(PP)P) E E 5 5, E, E4 4 ( ( P P Q)Q) (P(P Q)Q) (P(PQ)Q) (P(PQ)Q) ( ( P PQ) EQ) E 3 3 (P (P Q)Q) (P(PQ)Q) ( ( P P Q)Q) ( ( P PQ) Q) E E 7 7 解解 F2 P(P( QP) E11 ( PP)( P QP) E3 11 E5,E1 1 定理定理1-7 每一个不为永真的公式每一个不为永真的公式

41、F(PF(P1 1, P, P2 2, , , , P Pn n）必与一个由）必与一个由P P1 1, P, P2 2, , P, , Pn n所产生的主合取范式等所产生的主合取范式等值。值。永假公式永假公式的主合取范式包含所有的主合取范式包含所有 2 2n n个最大项。个最大项。永真公式永真公式的主合取范式是一空公式，用的主合取范式是一空公式，用1 1表示。表示。 1.8 命题演算的推理理论命题演算的推理理论 一、推理一、推理 推理是由已知的命题得到新命题的思维过程。推理是由已知的命题得到新命题的思维过程。 定义定义1-19 设设A A和和B B是两个命题公式，如果是两个命题公式，如果A A

42、B B，即如果命题公式即如果命题公式A AB B为重言式，则称为重言式，则称B B是前提是前提A A的结的结论或从论或从A A推出结论推出结论B B。一般地设。一般地设H H1 1，H H2 2，,H,Hn n和和C C是一是一些命题公式些命题公式, ,若蕴含式若蕴含式H H1 1HH2 2HHn n C C ( (* *) )成立，则称成立，则称C C是前提集合是前提集合 H H1 1，H H2 2，,H,Hn n 的结论，的结论，或称从前提或称从前提H H1 1，H H2 2，,H,Hn n能推出结论能推出结论C C。有时也记作。有时也记作H H1 1，H H2 2，,H,Hn n C C

43、1、真值表法、真值表法 对于命题公式中所有命题变元的每一组真值指派作出该对于命题公式中所有命题变元的每一组真值指派作出该公式的真值表，看是否为永真公式的真值表，看是否为永真。P Q0 00 11 01 1解解 构造其真值表如下：构造其真值表如下： P QPQ（PQ）P(（PQ）P) QQ11101101010100100111例例1 考察结论考察结论C是否是下列前提是否是下列前提H1，H2的结论。的结论。 （1）H1：PQ，H2：P，C：Q二、如何判断由一个前提集合能否推出某个结论二、如何判断由一个前提集合能否推出某个结论 （2 2）H H1 1：PQPQ， H H2 2： P P ， C C

44、： Q Q解解 构造其真值表如下：构造其真值表如下： P QPQ（PQ） P1111101101000010(（PQ） P) Q1011P QP Q0 00 00 10 11 01 01 11 1 在这里，我们不关心结论是真还是假，而主要关心在这里，我们不关心结论是真还是假，而主要关心由给定的前提是否能推出这个结论来。由给定的前提是否能推出这个结论来。2、等值演算方法、等值演算方法PRRQQP、.)()(是永真公式即需证明PRRQQP例例 证明证明分析根据题意，需证明分析根据题意，需证明.)()(是永真公式即需证明PRRQQP ()()()PQQRRRP ()()PQQRP ()()PQRQQ

45、RP PRQP)( PRQP)(1PRQP )()( PRRQQP证明证明PRRQQP) )( ()( ( 3 3、“形式证明形式证明”方法方法 （1）基本术语）基本术语 形式证明形式证明：一个描述推理过程的命题序列，其中每个一个描述推理过程的命题序列，其中每个命题或者是已知的命题，或者是由某些前提所推得的结论，命题或者是已知的命题，或者是由某些前提所推得的结论，序列中最后一个命题就是所要求的结论，这样的命题序列称序列中最后一个命题就是所要求的结论，这样的命题序列称为形式证明。为形式证明。 有效的证明有效的证明：如果证明过程中的每一步所得到的结论如果证明过程中的每一步所得到的结论都是根据推理规

46、则得到的，则这样的证明称作是有效的。都是根据推理规则得到的，则这样的证明称作是有效的。 有效的结论有效的结论：通过有效的证明而得到结论，称作是有效：通过有效的证明而得到结论，称作是有效的结论。的结论。 合理的证明合理的证明：一个证明是否有效与前提的真假没有关一个证明是否有效与前提的真假没有关系。如果所有的前提都是真的，那么通过有效的证明所得到的系。如果所有的前提都是真的，那么通过有效的证明所得到的结论也是真的。这样的证明称作是合理的。结论也是真的。这样的证明称作是合理的。 合理的结论合理的结论：一个结论是否有效与它自身的真假没有关一个结论是否有效与它自身的真假没有关系。通过合理证明而得到的结论

47、称作合理的结论。系。通过合理证明而得到的结论称作合理的结论。 ( 2) 推理规则推理规则 前提引用规则前提引用规则：在证明的任何步骤上都可以引在证明的任何步骤上都可以引用前提。用前提。 结论引用规则结论引用规则：在证明的任何步骤上所得到的在证明的任何步骤上所得到的结论都可以在其后的证明中引用。结论都可以在其后的证明中引用。 置换规则置换规则：在证明的任何步骤上，命题公式的在证明的任何步骤上，命题公式的子公式都可以用与它等值的其它命题公式置换子公式都可以用与它等值的其它命题公式置换。 代入规则代入规则：在证明的任何步骤上，重言式中的在证明的任何步骤上，重言式中的任一命题变元都可以用一命题公式代入

48、，得到的仍是任一命题变元都可以用一命题公式代入，得到的仍是重言式。重言式。 例例2 2 证明证明 RR（PQPQ）是前提）是前提PQPQ，Q QR R，P PS S ，S S的结论。的结论。 所以所以PQ，QR，PS， S R（PQ)编号编号 公公 式式 依依 据据（1）（2）（3）（4）（5）（6）（7）（8）PS S PPQQQRRR（PQ） 前提（前提引入规则）前提（前提引入规则）前提（前提引入规则）前提（前提引入规则）T（1）,（2）I前提前提T（3），（），（4）I前提前提T（5），（），（6）IT（4），（），（7）I例例3 3 证明证明RSRS是前提是前提PP（QSQS），），

49、RP RP和和Q Q的有效结论。的有效结论。 证明证明 编号编号公公 式式依依 据据 (1) (2) (3) (4) (5) (6) (7) (8) (9) RP RP P（ QS） R（QS） R（ QS） Q（ RS） Q RS RS 前提前提T（1）E 前提前提T（2）,（3）IT（4）ET（5）E 前提前提T（6），（），（7）T（8）E 例例4 符号化下面语句的推理过程，并指出推理是符号化下面语句的推理过程，并指出推理是否正确。否正确。“如果甲是冠军，则乙或丙将得亚军；如果乙得如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；亚军，则甲不能得冠

50、军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军，可知丁不能得亚军事实是甲已得冠军，可知丁不能得亚军”。 解解 设设 A：甲得冠军；：甲得冠军；B：乙得亚军；：乙得亚军； C：丙得亚军；：丙得亚军；D：丁得亚军。：丁得亚军。 推理过程符号化为推理过程符号化为 A（BC），），B A，DC，A D 推理过程符号化为推理过程符号化为 A（BC），），B A，DC，A D编号编号公公 式式依依 据据（1）（2）（3）（4）（5）（6）（7）（8）（9）AA（BCBC）A ABCBC(A(A）BABABBC CD CD CDD前提前提前提前提T T（1 1），（），（2 2）I IT T（2 2）E

51、E前提前提T T（4 4），（），（5 5）I IT T（3 3），（），（6 6）I I前提前提T T（7 7）, ,（8 8）I I 4、 间接证明间接证明(或反证法或反证法) 定义定义如果对于出现在公式如果对于出现在公式H H1 1，H H2 2，,H,Hn n中的命题变元中的命题变元的任何一组真值指派，公式的任何一组真值指派，公式H H1 1，H H2 2，,H,Hn n中至少有一个为假，中至少有一个为假，即它们的合取式即它们的合取式H H1 1 HH2 2HHn n是矛盾式，则称公式是矛盾式，则称公式H H1 1，H H2 2，HHn n是不相容的。否则称公式是不相容的。否则称公式H H1 1，H H2 2,H,Hn n是相容的。是相容的。 定理定理 若存在一个公式若存在一个公式R，使得，使得 H1H2 Hn R R则公式则公式H1，H2，,Hn是不相容的。是不相容的。 为了证明为了证明H H1 1、H H2 2、H H n nC C，利用定理，将，利用定理，将 C C 添 加 到 这 一 组 前 提