赵洪銮《离散数学》第一章7-8节.ppt

复习,真值表 等价公式 证明方法（真值表、公式证明法）,16组重要等值式,1、双重否定律 P P 2、幂等律 P P P P P P 3、交换律 P QQ P P Q Q P 4、结合律 (P Q) R P (Q R) (P Q) R P (Q R),5、分配律 P (Q R) (P Q) (P R) P (Q R) (P Q) (P R) 6、吸收律 P (P Q) P P (P Q) P 7、德摩根律 (P Q) P Q (P Q) P Q 8、零律 P T T P F F 9、同一律 P F P P T P,10、排中律 P P T 11、矛盾律 P P F 12、蕴涵等值式 PQ P Q 13、等价等值式 P Q （PQ） （QP） 14、假言易位 PQ Q P 15、等价否定等值式 P Q P Q 16、归谬论 （PQ） （ P Q ） P,记忆技巧：借助 集合的运算式， 看成并， 看 成交， 看成 补，T看成全集， F看成空集， 再加12-16条。,其他等价公式,其他联接词 (1) P Q (P Q); 双条件否定(不可兼析取或,异或) (2) P Q (P Q); 条件否定 (3) P Q (P Q); 与非 (4) P Q (P Q); 或非,1-7 对偶与范式,对偶 范式,一、对偶式,定义1-7.1：在给定的仅含有, , 的命题公式中，将换成，将换成，T和F互换，所得公式A称为A的对偶式。,例1：写出（PQ） R的对偶式,解：对偶式为 （PQ） R,写出（P Q）T， PFT的对偶式,定理1-7.2: 设P1,P2, Pn是出现在公式A和B中的所有原子变元,如果,A B,则A B.,二. 公式的标准型范式,1. 范式,定义1-7.2：一个命题公式称为合取范式，当且仅当它具有 A1A2An 其中A1,A2, ,An都是由命题变元或其否定所组成的析取式.,定义1-7.3: 一个命题公式称为析取范式，当且仅当它具有 A1A2An 其中A1,A2, ,An都是由命题变元或其否定所组成的合取式.,例如: (PQR) (PQ) Q P(PQ)(PQR),合取范式,析取范式,步骤,可以通过下面3个步骤将任一命题公式化为合取范式或析取范式： 将公式中的联结词化归成，及； 利用德.摩根律将否定符号直接移到各个命题变元之前； 利用分配律、结合律将公式归约为合取范式或析取范式。,例5: 求（P（Q R）S 的析取范式和合取范式,解：原公式 (P（QR）)S,（P（QR）S, P（QR）S, （PSQ）（PSR）,析取范式,合取范式,所以 原式(PQ) (PQ) (PQ) (PQ),例6: 求(PQ) (PQ)的析取范式。,解：因为 (A B) (AB) (AB),(P QPQ) (PQ) (PQ),(P QPQ) (PP) (PQ) (QP) (QQ),注意：任一命题公式都可以化为合取范式或析取范式的形式,2. 范式的应用,利用范式对公式进行判断： (1)公式A为永假式的充要条件是A的析取范式中每个简单合取式至少包含一个命题变元及其否定。 例：A(P1,P2,Pn) (P1 P1 ) (P2 P2 ) (2)公式A为永真式的充要条件是A的合取范式中每个简单析取式至少包含一个命题变元及其否定。 例：B(P1,P2,Pn) (P1 P1 ) (P2 P2 ) ,例如: 判断下列公式为何种公式： (1) P（Q R） (PR) (2) （PQ）P,解:(1) P（QR）（PR） （P QRP）（PQRR）永真,(2) （PQ）P （ PQ）P （ PP）（QP）可满足式,3. 范式不唯一性,P(QR) (PQ)(PR) (PP)(PR)(QP)(QR) 分配律,对识别公式是否等价带来一定困难， 解决方式：主范式,1. 主析取范式,小项的概念 定义1-7.4: n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,例如：PQ，PQ，PQ，PQ 是 PQ P 不是 问题：n个变元可有多少小项？,三.公式的主范式,见课本P33表1-7.2，三个变元的情况,下标表示法：命题变元按字典顺序排列，命题变元对应1，变元的否定对应0。对小项依二进制编码（或用十进制编码）。,如： PQ,PQ,m11(m3),m01(m1),PQ,m10(m2),PQ,m00(m0),小项的性质：,(1)每一小项当其真值指派与编码相同时，其真值为T，在其余指派情况下均为F。 (2)任意两个不同小项的合取为假。 例：m110m100 =(PQR) (PQR) PPQRR F (3)全体小项的析取值永为真。 2n-1 mi=m0 m1 m 2n-1T i=0,主析取范式,定义1-7.5：在给定公式的析取范式中，其简单合取式都是小 项，则称该范式为主析取范式。 例:P (QR) (PQ) (PR) 不是,可由两种方法构成: 1)公式推导法 2)列表法,(PQR) (PQR) (PQR),由基本等价公式推出主析取范式。其推演步骤可归纳为： 化为析取范式 . 删除永假的简单合取式 化简重复出现的变元（等幂律） (4) 补进未出现的变元（同一律） 添加(PP),然后利用分配律展开,公式推导法,例8 求(PQ) (PR) (QR)的主析取范式。,解 原式(PQ(RR) (PR(QQ) (QR(PP) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR),注意 主析取范式的唯一性,例9 求P(PQ) (QP)的主析取范式,解 原式 P(PQ) (QP) P(PQP) (QQP), P(PQP) (QP) P(QP), (P(QQ) (QP) (PQ) (PQ) (PQ),列表法,定理1-7.3: 在真值表中,一个公式的真值为T的指派所对应的小项的析取,即为此公式的主析取范式。,例6.求下列公式的主析取范式: P Q，PQ，(PQ)，A,PQ ,(PQ) (PQ) (P Q),PQ ,(PQ) (PQ) (PQ),(PQ) ,(PQ) (PQ) (PQ),A ,(PQ) (PQ),如： PQ M00(M0) PQ M10(M2),大项的概念,定义1-7.6 n个命题变元的析取式，称作布尔析取或大项。其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,例如：PQ，PQ，PQ，PQ,下标表示法：命题变元按字典顺序排列，命题变元对应0，变元的否定对应1。对大项依二进制编码（或用十进制编码）。,PQ M01(M1) PQ M11(M3),2. 主合取范式,大项的性质,每一大项当其真值指派与编码相同时，其值为F，在其余指派情况下均为T。 (2)任意两个不同大项的析取式为永真。 Mi Mj T (ij) (3)全体大项的合取式必为永假，记为： 2n-1 Mi = M0M1M2n-1 F i=0,主合取范式,定义1-7.7 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。,同样地求解主合取范式的方法也有两种：列表法和公式推导法,定理1-7.4 在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。,列表法,m11 m01,例 求（ PQ）Q的主合取范式与主析取范式,( PQ）（PQ）；(PQ) (PQ),M10 M 00,公式推导法,步骤： (1)化为合取范式 (2)删除永真的合取项(简单析取式) (3)化简重复出现的变元（等幂律） (4)补进未出现的变元（同一律） (QQ),例11 化(PQ) (PR)为主合取范式,解 原式(PP) (PR) (QP) (QR) (PR) (QP) (QR) 合取范式, (PQR) (PQR) (PQR) (PQR) 课本上采用真值表法,(PR(QQ) (QP(RR) (PP) QR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR),3.主析取范式与主合取范式之间的关系,例如: (PQ)Q m1m3, 则(PQ)Q M0M2,由主析取范式求主合取范式的步骤: a.找出主析取范式中所没有的小项下标 b.对a中下标,求其对应的大项 c.写出b中所得大项的合取,即为该式的主合取范式.,求(ABC) (A (BC)的主析（合）取范式。,解 原式(A(BC) (ABC) (A(BC) (AABC) (A(A(BC) (BC) (ABC) ) (BC) (A(BC),(ABC) (ABC) =m000m111=0,7,解1 利用主析取范式与主合取范式之间的关系 原式 1，2，3，4，5，6,4. 主范式的应用,(1)用以判定为何种公式. 设A为含n个变元的主范式： a. 若A T，或A可化为与其等价的含 2n 个小项的主析取范式，则A为永真式。 b.若 A F，或A可化为与其等价的含 2n 个大项的主合取范式，则A为永假式。 c.若 A 不与F等价，且又不含 2n 个大项或者小项，则A为可满足式。,例:判断下列公式为何类公式(PQ)Q (PQ)Q M0M2 m1m3;大小项数目均不到4,故为可满足式. (2)证明等价式成立:主范式相同，则给定的两个命题公式等价 例 A(A(AB), AB(AB),1-8 推理理论,在逻辑学中，把从前提出发，依据公认的推理规则，推导出一个结论，这一过程称为有效推理或形式证明。所得的结论叫有效结论。,在数理逻辑中，集中研究的是用来从前提导出结论的推理规则和论证原理。这里最关心的不是结论的真实性，而是推理的有效性。与这些规则有关的理论称为推理理论。,定义1-8. 1：设A和C是两个命题公式，当且仅当AC为一重言式，即AC，称C是A的有效结论。,这个定义可推广到有n个前提的情况。,设H1，H2，Hn，C是命题公式，当且仅当 H1H2HnC 称C是一组前提H1，H2，Hn的有效结论。,一、基本定义,(1) 真值表法,二、论证方法,判断有效结论的过程就是论证过程，论证方法基本分为,设P1，Pm是出现于前提H1，Hn和结论C中的全部命题变元，列出这个真值表，即可看出H1H2HnC是否成立。,例1：一份统计报表的错误，或者是材料不可靠，或是因计算错误，这份报表有错不是材料不可靠，所以这份报表是由于计算有错误。,P(PQ)Q,解：P：材料不可靠 Q：计算错误,由一组前提、公认的推理规则，利用已知的等价或蕴含公式，推出有效的结论。,(2)直接证法：,P规则：前提在推导中的任何时候都可引入使用。常用的蕴含式和等价式见表P43。,T规则：前面已导出的有效结论可作为后续推导引入。,例2：证明( PQ)(PR)(QS)SR,(1) PQ P,(2) PQ T(1)E,(3) QS P,(4) PS T(2)(3)I,(5) SP T(4)E,(6) PR P,(7) SR T(5)(6)I,(8) SR T(7)E,定义1-8.2：假设公式H1，H2，Hn中的命题变元为P1，P2，Pm的一些真值指派，如果能使H1H2Hn的真值为T ，则称公式H1，H2，Hn是相容的。如果对于P1，P2，Pm的每一组真值指派，使得H1H2Hn的真值均为F，则称公式H1，H2，Hn是不相容的。,(3) 间接证法,设要证：H1H2HnC，记为SC。,即证其逆反式CS为永真，,即CS为永真，,故CS为永假，,所以要证H1H2HnC。,只要证明C与 H1H2Hn是不相容的。,例3：证明AB， (BC)可逻辑推出A,(1) AB P,(2) A P(附加前提),(3) (BC) P,(4) B C T(3) E,(5) B T(1),(2),I,(6) B T(4) I,(7) BB T(5),(6) I,若要证：H1H2Hn(RC)，记为SRC,CP规则：结论为RC时，R作为附加前提引入，推出后件C。,因为S(RC) S(RC),(SR) C,(SR)C,(SR) C,将R作为附加前提，如有(SR)C，即证得S(RC)。,例4：证明A(BC)，DA，B蕴含DC,(1) D P(附加前提),(2) DA P,(3) A T(1),(2) I,(4) A(BC) P,(5) BC T(3),(4) I,(6) B P,(7) C T(5),(6) I,(8) DC CP,推理理论： 1、真值表法： 2、直接证法：P规则，T规则。 3、间接证法：利用不相容的概念，CP规则。,1.命题及其表示法 基本概念：命题 命题标识符:命题变元，命题常量 真值：T和F,1和0 重点：命题的判断 （这句话是对的） 2.联结词 基本概念：联接词的定义及使用( ) 最小联结词组（,）（, ） 重点：联结词的使用,第一章小结,练习1 1、判断是否为命题 1)4+x=5. 2)若x=1,则x+1=5。 2、将下列命题符号化 1）气候很好或很热 2）天气炎热但湿度较低 3）控制台打字机即可作输入设备，又可作输出设备 4）要求有使用C+或Java的经验,3.命题公式与翻译 基本概念：命题公式（合式公式），命题的翻译（命题公式符号化 ） 重点：命题的翻译 4.真值表与等价公式 基本概念：真值表（真值指派），等价公式，子公式 重点：真值表的列法，等价公式的证明，16个命题定律,练习2 1、用符号形式写出下列命题 a)假如上午不下雨，我去看电影，否则就在家里读书或看报 b)我今天进城，除非下雨 c)仅当你走我将留下 2、列出真值表 (PQ)(PQ R),练习2 3、试证下式为重言式 (AB)(BC) (CA)(AB) (BC) (CA),5.重言式与蕴含式 基本概念：重言式，矛盾式，可满足式，蕴含式 重点：重言式、矛盾式、可满足式的判断，等价公式 的证明，蕴含式的证明，14个