离散数学 第二章 命题逻辑等值演算.pptx

1、第二章命题逻辑等值演算,公式的赋值定义： 将给定公式A中所含命题变元指定具体的一组真值，称这组真值为给公式 A的赋值（或解释）。 公式A在此组赋值（解释）下就具有确定的真值。 1）公式 A的所有赋值组数与公式所含变元有关 （共有 2n 组） 2）若公式A在此组解释下的真值为真(1,T），则称此组赋值为成真赋值。 3）若公式A 在此组解释下的真值为假(0,F），则称此组赋值为成假赋值。,p q (p q)(qp) (pq)(pq) 0 0 1 1 0 1 0 0 1 0 0 0 1 1 1 （0,0）与（1,1）为公式的成真赋值。 （0,1）与（1,0）为公式的成假赋值,命题公式的分类（根据公式

2、在赋值下的真值情况进行分类） 1）若命题公式在它的各种赋值下取值均为真,则称命题公式是重言式或永真式。 2）若命题公式在它的各种赋值下取值均为假,则称命题公式是矛盾式或永假式。 3）若命题公式不是矛盾式,则称命题公式是可满足式。(或公式至少有一组成真赋值） 例：判断公式的类型 （现在只能用真值表方法） (p q ) q p （p q r) (p q) (q p) (（p q ) q）,后一页,p q (pq)q 0 0 0 0 1 0 1 0 0 1 1 0,(pq )q） 0 0 0 0,(pq)(qp) 1 1 1 0,p q r p(pqr) 0 0 0 1 0 0 1 1 0 1 0

3、1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1,返回,对于形似于条件命题的构成形式 即 A B 而且要说明是重言式 如：Q（Q） P 可利用条件联结词的性质来给予证明 分析1：若要得出：当设 A为真，B为假的情况不会出现， 那么A B 为永真式。 可证明：设前件为真 分析2： 还可以从设 B为假，推出A为真的情况不会出现（A为假）， 那么A B 为永真式。 证明： 设后件为假 (（Q）( QR) (R),不同真值表的公式 1）当命题变元确定后，通过五个连接词及其命题变元可以构成无数个不 同表现形式的命题公式。 问题：这些不同形式的命题公式的真值表是否都不相同

4、？ 先看变元仅有两个p,q 那么关于这两个变元的公式的赋值仅有4组 任何关于这两个变元的公式的所有真值表只能是一组4位二进制数 4位二进制数的不同状态共有1624 关于2个变元的不同真值表的公式仅有16种。以此推断： 2）当命题变元确定后，由于其公式的赋值组数是确定的（共2n组） 公式在一组赋值下是一个真值（一位二进制） 在2n组赋值下对应为2n位二进制 n个变元的不同真值表的公式仅有（2）（2n）种 例：2个变元的16种不同真值表,例：看几个公式的真值表：,p q p q p q 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1,p q p q (p q)(qp) (pq)(p

5、q) 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 公式的表现形式不同但具有相同的真值表 也可以说：对所含变元的所有赋值下，其公式的真值均相同 我们把这类公式定义为“是逻辑等值的”,为了更方便地对命题公式进行讨论（确定其真值、公式的分类及其推理），象代数式那样进行演算（化简），有必要引入一些化简原则。 代数式的化简原则是等值（不论变量的取值如何，代数式的值是相等的），对于命题公式来说化简的原则是逻辑等值。,返回,第二章 命题逻辑等值演算 一、逻辑等值定义 给定两个命题公式A 和 B，设 A 和 B 含有共同的n个命题变元。若对于这 n 个命题变元的所有可能的赋

6、值，命题公式A 与B的真值均相同，则称命题公式 A 逻辑等值于命题公式B。 并记作 A B。 逻辑等值的另外的形式定义： 给定两个命题公式A 和 B，若由A和B构成的等价式 A B为重言式（永真式），则称命题公式 A 逻辑等值于命题公式B。 两个定义可相互证明 注： 1、“”不是连接词，仅表示两个公式具有等值关系（不能用等号），所构成的式子不是命题公式 2、等值的性质： 对任意公式A，(进行演算的理论基础) ）自反性：A A ； ）对称性：若A ，则 A； ）传递性：若A ， 则A ,3、判断两个公式是否等值的方法 真值表方法：列出两个公式的真值表，看其真值是否相同（最基础的方法） 验证 公式

7、 pq 与公式pq等值 (A B ) A B 代数式的演算无法采用此种方法 演算法：以经过验算的等值式为基础（乘法公式等值定律） 利用置换规则（等值代换）及其等值的性质 得到其他的等值式 （与代数式的演算类似） 下面引入经过验算得出的等值定律 为使定律使用的更广泛，定律中使用元语言的表示方法,二、等值定律 1双重否定律 A A 2. 幂等律 A A A A A A 3. 结合律 (A B )C A (B C) (A B )C A (B C) 4. 交换律 A B B A A B B A 5. 分配律 A (B R) (A B )(A R) A (B R) (A B )(A R) 6. 吸收律

8、A (A B ) A A (A B ) A 7. 德摩根律 (A B ) A B (A B ) A B 8. 同一律 A A F A A T 9. 零律 A T T A F F 10. 排中律 T A A 11矛盾律 F A A 12蕴涵等值式 A B A B 13等价等值式 A B （A B）（ B A） A B （A B）（ B A） A B （A B）（ A B） 同真同假 14假言易位（逆否命题） A B B A 15等价否定等值式 A B A B 16归谬论 （ A B） （A B ） A,三、置换规则： 设 （A）是含公式A的命题公式，（B）是用公式B置换了（A）中所有出现的A所得

9、到的命题公式，则 若A B有 （A） （B） 注：置换规则类似于代数中的变量替换 如：公式 (pq) r 因为pq与pq等值 故可用pq 置换pq所得到的公式与原式是等值的 即： (pq) r （pq） r （pq） r 与（pq） r 等值 故有（pq） r （pq） r （p q） r,例：证明下列等值式 (PQ)(P（PQ) (PQ) 解： (PQ)(P(PQ) (PQ)(P(PQ) 蕴涵等值 (PQ)(PQ) 等幂律 (PQ)PQ (PP)(QP)Q 分配律 T (QP)Q 同一律 QP 等幂律 PQ 交换律 2）证明等值式 (pq) r (P r) (q r) （ p )p )(qr

10、) qr,四、利用等值演算可确定公式的类型 判断(pq) p q 的类型 若能得到 (pq) p q 则可得到公式为重言式 若 A则可得到公式为矛盾式 因为(pq) p q 公式( p（q) ） r 的类型 公式（ （q) p） 的类型 利用等值演算还可以化简一个命题公式 命题公式的等值演算是数理逻辑中的最基本运算,. 析取范式与合取范式 (公式的标准型式） 一简单析取式和简单合取式 1）“文字”定义 命题变项及其否定统称作文字 2）仅由有限个文字构成的析取式称作简单析取式 pq 、 p q r q 3）仅由有限个文字构成的合取式称作简单合取式(项） q p p q r p 4) 简单析取式和

11、简单合取式的性质： 一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式 一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式,二析取范式和合取范式 1、定义 (1)由有限个简单合取式构成的析取式称为析取范式(代数式） p q r q p pq p (2)由有限个简单析取式构成的合取式称为合取范式 (pq) q p p q r q (3)析取范式与合取范式统称为范式 Ai(i=1,2n)为简单合取式，A=A1 A2 .An为析取范式 p q r p q q pr q 是含三个简单合取式的析取范式 Bi(i=1,2n)为简单析取式，B=B1 B2 . Bn为合取范式 p q

12、r (pq) q p （p q）（qpr）q 是含三个简单析取式的合取范式,2、性质： 1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 p P q q 0 0 0 （p p）（qq） 1 1 1,3、范式存在定理 任一命题公式都存在着与之等值的析取范式与合取范式 利用等值定律可将任何公式化成与之等值的析取范式和合取范式 确定析取范式和合取范式 (pq)（p r) (pq) （p r) 总可以通过以下方法步骤： 1消去联结词 (若存在) 2否定号的消去(利用双重否定律)或内移(利用德摩根律) 3利用分配律：利用对的分配律

13、求析取范式， 对的分配律求合取范式 是否唯一?,例: 确定 (p q) r) p 的析取范式及合取范式 (p q) r) p (p q) r) p (p q) r) p (p q p ) ( r p) (p q p ) ( r p) 合取范式 (p q ) ( r p) 合取范式 (p q) r) p （ r) (p q) r) p (p q) r) p (p q) r) p (p r ) ( q r) p 析取范式 p (p r ) ( q r) p (q r) 析取范式 (4）析取范式和合取范式的不唯一性,p (p q) p (p q) p （p q ） 析取范式 （p （q q） （p q） (p q) (p q) 析取范式 p 析取范式 (p