第3章命题逻辑-2.ppt

1、2020/8/7,49-1,5.4范式,5.4.1 析取范式和合取范式,定义5.14-1 (1) 命题变元或命题变元的否定称为文字。 (2)有限个文字的析取式称为子句；有限个文字的合取式称为短语。 例1 (1) P，P是文字。,(2) P，P，PQR，PP，PQR 等都是子句。,(3) P，P，PQR，PP，PQR 等都是短语。,2020/8/7,49-2,定义5.14-2 (3) 有限个短语的析取式称为析取范式；有限个子句的合取式称为合取范式。,例2 (1) P，P，PQR, PQR, (PQ)(PQ)，等都是析取范式。,(2) P，P，PQR， PQR, (PQ)(PQ)，等都是合取范式。

2、,结论: 任意的命题公式都可通过下列步骤化为等价的范式:,(1) 用联结词集 “，” 取代公式中的“，”；,（2） 将移到各命题变元之前；,（3）用相应的运算“律”将公式化为要求的范式。,2020/8/7,49-3,例3 求公式 (PQ)R 的析取范式和合取范式。,解 (PQ)R (PQ)R, 析取范式,(PQ)R,(PR)(QR) 合取范式,注：公式的析（合）取范式不唯一。,2020/8/7,49-4,1.极小项与极大项 定义5.15-1 （1）设P1、P2、Pn是n个命题变元，一个短语或子句如果恰好包含所有这n个命题变元或命题变元的否定，且排列顺序与P1、P2、Pn的顺序一致，则称此短语或

3、子句为关于P1、P2、.、Pn的一个极小项或极大项。,5.4.2 主析取范式和主合取范式,例1 对于P, Q, R 而言, PQR, PQR, PQR 等都是极小项,而 PPR, PPQ, PQ, R Q P 都不是关于P, Q, R的极小项.,2020/8/7,49-5,2.极小项与极大项的性质与记号,(1) 对于n个命题变元，共有2n个不同的极小项和2n个不同的极大项，分别记为m0，m1，m2n-1和M0，M1，M2n-1。例如关于P, Q, R 有:,2020/8/7,49-6,(2) 含有n个命题变元的极小项mi和极大项Mi，作为命题公式，共有2n个不同的解释。,在这2n个不同的解释中

4、，有且仅有一个解释使得mi为1，有且仅有一个解释使得Mi为0，。,例如:,2020/8/7,49-7,(3) mi = Mi, Mi = mi；i=0,1,2,2n-1, mimj=F ; MiMj=T；ij；i,j0,1,2,2n-1,(4) 每个不为永假式的短语, 均可表示为与之等价的极小项或极小项的析取; 每个不为永真式的子句, 均可表示为与之等价的极大项或极大项的合取.,2020/8/7,49-8,2. 主析取范式和主合取范式,定义5.15-2 (2) 由有限个极小项组成的析取范式称为主析取范式；,(3) 由有限个极大项组成的合取范式称为主合取范式。,定理5.4 任何命题公式都存在唯一

5、一个与之等价的主析取范式和主合取范式.,注: 永假式无主析取范式或者说主析取范式为“空”； 永真式无主合取范式或者说主合取范式为“空”.,2020/8/7,49-9,证明 对任意的命题公式G，若G为永假式，由注释G 的主析取范式为“空”。 若G不为永假式，则先将G化为析取范式，再去掉其中为永假式的短语，并将其中不为永假式的短语用与之等价的极小项的析取取代，合并相同项即得G 的主析取范式。,类似可求得G 的主合取范式。 唯一性（略）,3. 主析取范式和主合取范式的求法,（1）公式转换法,即利用定理5.15证明中描述的方法,2020/8/7,49-10,例2求GPQ 的主析取范式和主合取范式。 解

6、 GPQ PQ,= (P (QQ) )( (PP) Q ),( = M2 主合取范式), (P Q) (P Q) (P Q) (P Q),= (P Q) (P Q) (P Q),(= m0 m1 m3 主析取范式),例3求 PQ 的主合取范式。 解 PQ = (P (Q Q) )( (P P) Q ),2020/8/7,49-11,续 (P (Q Q) )( (P P) Q ),= (P Q) (P Q)(P Q) (P Q) ),= (P Q) (P Q)(P Q),(2) 真值表技术(Technique of Truth Table),方法: 首先列出给定公式G 的真值表, 由表可得 G

7、的主析取范式 = 所有使G为真的解释所对应的极小项的析取 G 的主合取范式 = 所有使G为假的解释所对应的极大项的合取,2020/8/7,49-12,例4 求G1PQ和G2PQ 的主析取范式和主合取范式。 解 列出公式 G1 和 G2 的真值表:,由表可得 G1 = (P Q) (P Q) (P Q) 主析取范式,= PQ 主合取范式,G2 = (P Q) (P Q) 主析取范式,= (P Q ) (P Q ) 主合取范式,2020/8/7,49-13,例5 求 G = (PQ)R 的主析取范式和主合取范式。,解 列出其真值表：,由此得 G的主析取范式= (PQR) (PQR)(PQR),G的

8、主合取范式 (PQR)(PQR)(PQR)(PQR)(PQR),2020/8/7,49-14,例6 设公式 G(PQ)(PQR), 求 (1) G的主析取范式和主合取范式; (2) G 的主析取范式. 解 (1) G(P Q)(PQR) (P Q)(RR)(PQR) (P QR)(P QR)(PQR) 主合取范式,4.主析取范式和主合取范式之间的转换, M4 M5 M6,= m0 m1 m2 m3 m7,= (PQR)(P QR) (PQ R)(PQR)(PQR) 主析取范式,2020/8/7,49-15,(2) 由(1), G m0 m1 m2 m3 m7,所以 G = m4 m5 m6,=

9、 (PQR)(P QR) (PQ R) 主析取范式,例7 设公式 G G(P,Q)的真值表如下表, 求G的主析取范式.,解 由表可得 G = (P Q) (P Q),2020/8/7,49-16,主范式的性质,任何命题公式都存在唯一一个与之等价的主析取范式和主合取范式； 命题公式是永真公式当且仅当它的主析取范式包含所有的极小项，此时无主合取范式或者说主合取范式为“空”； 命题公式是永假公式当且仅当它的主合取范式包含所有的极大项，此时无主析取范式或者说主析取范式为“空”； 两个命题公式是相等的当且仅当它们的主析取范式相等(即含有相同的极小项)和主合取范式相等(即含有相同的极大项)。,2020/8

10、/7,49-17,有一逻辑学家误入某部落，被拘于劳狱，酋长意欲放行，他对逻辑学家说： “今有两门，一为自由，一为死亡，你可任意开启一门。为协助你脱逃，今加派两名战士负责解答你所提的任何问题。惟可虑者，此两战士中一名天性诚实，一名说谎成性，今后生死由你自己选择。” 逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。该逻辑学家应如何发问？,例,解：逻辑学家手指一门问身旁的一名战士说：“这扇门是死亡门，他(指另一名战士)将回答是，对吗？”,2020/8/7,49-18,当被问战士回答“对”，则逻辑学家开启所指的门从容离去。当被问的战士回答“否”，则逻辑学家开启另一扇门从容离去。,分析：如果被问者是

11、诚实战士，他回答“对”。则另一名战士是说谎战士，他回答“是”，那么，这扇门不是死亡门。 如果被问者是诚实战士，他回答“否”。则另一名战士是说谎战士，他回答“不是”，那么，这扇门是死亡门。 如果被问者是说谎战士，可以类似分析。,例（续2）,2020/8/7,49-19,设：P：被问战士是诚实人。 Q：被问战士的回答是“是”。 R：另一名战士的回答是“是”。 S：这扇门是死亡门。,例（续3）,2020/8/7,49-20,5.5命题逻辑的推理理论,命题演算的一个主要任务在于提供一种正确的思维规律，即推理规则，应用此规则从一些前提中推导出一个结论来，这种推导过程称为有效推理或形式证明。,设G，H是两

12、个公式，称H是G的逻辑结果(或称G蕴涵H)当且仅当对任意解释I，如果 I 满足G，则 I 也满足H。将G 蕴涵 H 记为 GH, 也称GH 是有效的, 此时G 称为前提，H 称为结论。,一、 基本概念,2020/8/7,49-21,证明 “”假设H是G的逻辑结果，I是G，H的任意解释. 若 I 满足G, 由假设, I 也满足H，故GH为真;若I不满足G，此时无论I是否满足H，都有GH为真。由I 的任意性知GH为永真公式。 “”设GH为永真公式，I是使得G为真的任意解释，因GH为永真，所以H必为真，即在I下，若I满足G，则I满足H，所以GH。,定理 5.16 公式 G 蕴涵公式 H 当且仅当公式

13、GH 是永真的。,2020/8/7,49-22,定义5.16设G1,G2,Gn,H是公式, 称H是G1,G2,Gn的逻辑结果(或G1,G2,Gn共同蕴涵H)，当且仅当H是G1G2Gn的逻辑结果。记为G1,G2,GnH, 此时也称G1,G2,GnH是有效的. G1,G2,Gn 称为一组前提，有时用集合来表示,记=G1,G2,Gn ；H称为结论。又称H是前提集合的逻辑结果。记为H。,定理 5.16 公式 H 是前提集合G1,G2,Gn 的逻辑结果当且仅当 G1G2GnH 为永真公式。,2020/8/7,49-23,注:“”与“”的区别,“” 是一般的蕴涵联结词， “” 是关系符. 对公式G和H,

14、GH 仍是一个公式，而 G H 不是命题公式； 直接用计算机来判断是否有 GH 是办不到的，然而计算机却可通过“计算”公式GH是否永真来判断是否有 GH。,二、 判断有效结论的常用方法 1.真值表技术,2020/8/7,49-24,方法: 设P1,P2,Pn是出现在前提G1,G2,Gn和结论H中的一切命题变元. 先将G1,G2,Gn，H 列在一个真值表中，再按如下方法作判断：,(1) 对所有G1,G2,Gn都具有真值T的行,考查H的真值, 如果在每一个这样的行中，H 也具有真值T，则H 是 G1,G2,Gn 的逻辑结果。 (2) 对所有H 具有真值为F 的行,如果在每一个这样的行中， G1,G

15、2,Gn 中至少有一个公式的真值为F，则H 是 G1,G2,Gn 的逻辑结果.,2020/8/7,49-25,例1 判断下列H 是否是前提G1,G2的逻辑结果.,(1)H：Q；G1：P；G2：PQ； (2)H：P；G1：PQ；G2：Q； (3)H： Q；G1：P；G2：PQ。,解：建立真值表如下：,?,是,是,不是,2020/8/7,49-26,（1） 如果明天天晴，那么我们外出旅游；明天的确天晴。所以明天我们外出旅游。 （2）如果明天天晴，那么我们外出旅游；明天没有天晴。所以明天我们不外出旅游。,例2 判断下列推理是否正确？,解 设 P：明天天晴 Q：明天我们外出旅游 （1） 前提为 ： P

16、Q ，P 结论为：Q ,由例1的（1）： P ，PQ Q，即推理正确。,（2） 前提为 ：PQ， P 结论为： Q ,2020/8/7,49-27,2.演绎法,指从前提出发,按推理规则,推导出一个结论来.,(1) 推理定律 (基本蕴涵式),设G，H，I，J是任意的命题公式，则有：, I1：GH G(简化规则) I2：GH H, I3：G GH(添加规则) I4：H GH, I5：G GH I6：H GH,2020/8/7,49-28, I7：(GH) G I8：(GH) H, I9：G, H GH, I12：G,GH H(分离规则), I13：H,GH G (否定后件式), I14：GH,HI

17、 GI(假言三段论), I15：GH,GI,HI I(二难推论),2020/8/7,49-29,(2) 三个推理规则,规则P (前提引入规则)：在推导的过程中，可以随时引 入前提。,规则T (逻辑结果引用规则)：在推导的过程中，可以随时 引入公式S，该公式S是由其前的一个或多个公式推导 出来的逻辑结果。,规则CP (附加前提规则)：如果能从给定的前提集合 公式P推导出S，则能从此前提集合推导出PS。,说明: 由“”的定义可推知“”具有自反性 (即对任意的公式G,均有G G) 和 传递性 (即对任意的公式G,H,S , 若有 G H, H G , 则必有均有G S) .,2020/8/7,49-

18、30,定义5.17 从前提集合 推出一个结论H的演绎是构造命题公式的一个有限序列: H1, H2, , Hn 其中每个 Hi 或者是 中的某个前提, 或者是前面某些 Hj(ji) 的有效结论, 并且Hn 就是H, 则称公式H 为该演绎的有效结论, 或者称从前提 能够演绎出结论H来.,例3 设前提=PQ,PR,QS,公式G=SR。证明 G。,证 法1： PQ P PQT,(1),E QS P PS T,I, SPT,E PRP SR T,I SRT,E,2020/8/7,49-31, 将前提中的PR 改为PR 也可推出同样的结论（书中另一例), 为什么?,说明 （1）法2: 因结论SR = SR，所以可利用规则CP将 S作为附加前提引进，而推出R 。（证明 略）,例4 设= P(QS), RP, Q ,G = RS。 证明：G。,证：RP(附加前提) RPP PT,I P (QS) P QST,I QP ST,I RSCP,2020/8/7,49-32,如果今天是星期1，则十点钟要