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

1、公式公式的赋值定义：的赋值定义：n 将将给定公式给定公式A A中所含命题变元指定具体的一组真值中所含命题变元指定具体的一组真值，称这组真值，称这组真值为给公式为给公式 A A的的赋值（或解释赋值（或解释）。）。 公式公式A A在此组赋值（解释）下就具有确定的在此组赋值（解释）下就具有确定的真值真值。 1 1）公式）公式 A A的所有的所有赋值组数赋值组数与公式所含变元有关与公式所含变元有关 （共有（共有 2 2n n 组）组） 2 2）若公式）若公式A A在在此组解释下的真值为真此组解释下的真值为真(1,T(1,T），），则称此组赋值为则称此组赋值为成成真赋值真赋值。 3 3）若公式）若公式A

2、 A 在在此组解释下的真值为假此组解释下的真值为假(0,F(0,F），），则称此组赋值则称此组赋值为为成假赋值成假赋值。p q (p q)(qp) (pq)(pq) 0 0 1 1 0 1 0 0 1 0 0 0 11 1 1 （0,00,0）与（）与（1,11,1）为公式的为公式的成真成真赋值。赋值。 （0,10,1）与（）与（1,01,0）为公式的为公式的成假成假赋值赋值 n 命题命题公式的分类公式的分类（根据公式在赋值下的真值情况进行分类）（根据公式在赋值下的真值情况进行分类）1 1）若命题公式在它的）若命题公式在它的各种赋值下取值均为真各种赋值下取值均为真, ,则称命题公式是则称命题公

3、式是重言式或永真式重言式或永真式。2 2）若命题公式在它的）若命题公式在它的各种赋值下取值均为假各种赋值下取值均为假, ,则称命题公式是则称命题公式是矛盾式或永假式矛盾式或永假式。3 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

4、） 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 1 0 1 1 11 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 返回返回对于形似于条件命题的构成形式对于形似于条件命题的构成形式 即即 A BA B 而且要说明是而且要说明是重言式重言式 如：如：QQ（Q Q） P P 可利用条件联结词的性质来给予证明可利用条件联结词的性质来给予证明分析分析1 1：若要得出：当设：若要得出：当设 A A为真，为真，B B为假的情况不会出现，为假的情况不会出现， 那么那么A B A B 为为永真式永真式。 可证明：设前件为

5、真可证明：设前件为真分析分析2 2： 还可以从设还可以从设 B B为假，推出为假，推出A A为真的情况不会出现（为真的情况不会出现（A A为假），为假）， 那么那么A B A B 为为永真式永真式。 证明：证明： 设后件为假设后件为假 ( (（Q Q）( QR)( QR) ( (R)R) n 不同不同真值表的公式真值表的公式 1 1）当命题变元确定后，通过五个连接词及其命题变元可以）当命题变元确定后，通过五个连接词及其命题变元可以构成构成无数个不无数个不 同表现形式同表现形式的命题公式。的命题公式。 问题：这些不同形式的命题公式的问题：这些不同形式的命题公式的真值表真值表是否都不相同？是否都不

6、相同？ 先看变元仅有两个先看变元仅有两个p,q p,q 那么关于这两个变元的公式的赋值仅有那么关于这两个变元的公式的赋值仅有4 4组组 任何关于这两个变元的公式的所有真值表只能是任何关于这两个变元的公式的所有真值表只能是一组一组4 4位位二进制数二进制数 4 4位二进制数的不同状态共有位二进制数的不同状态共有16162 24 4 关于关于2 2个变元的不同真值表的公式仅有个变元的不同真值表的公式仅有1616种。以此推断：种。以此推断： 2 2）当命题变元确定后，由于其公式的）当命题变元确定后，由于其公式的赋值组数是确定的赋值组数是确定的（共（共2 2n n组）组） 公式在一组赋值下是一个真值（

7、一位二进制）公式在一组赋值下是一个真值（一位二进制） 在在2 2n n组赋值下对应为组赋值下对应为2 2n n位二进制位二进制 n n个变元的不同真值表的公式仅有（个变元的不同真值表的公式仅有（2 2）（2 2n）种种 例：例：2 2个变元的个变元的1616种不同真值表种不同真值表P q(pp) (qq)P qP qP P q q(P q)P q0 0 0 00000000 1 000011111 0 001100111 1 01010101P q(P q)P q qq P P P q(P q)(Pp) (qq)0 0 1 11111110 1 000011111 0 001100111 1

8、01010101例：看几个公式的真值表：例：看几个公式的真值表：p q p q p q0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 p q p q (p q)(qp) (pq)(pq) 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 公式的表现形式不同但具有相同的真值表公式的表现形式不同但具有相同的真值表也可以说：对所含变元的也可以说：对所含变元的所有赋值下所有赋值下，其，其公式的真值均相同公式的真值均相同我们把这类公式定义为我们把这类公式定义为“是逻辑等值的是逻辑等值的”为了更方便地对命题公式进行讨论为了更方便地对命题公式进行讨论（确定其真值

9、、公式的分类及其推（确定其真值、公式的分类及其推理），象代数式那样进行演算（化理），象代数式那样进行演算（化简），有必要引入一些化简原则。简），有必要引入一些化简原则。代数式代数式的化简原则是等值的化简原则是等值（不论变（不论变量的取值如何，代数式的值是相等量的取值如何，代数式的值是相等的），对于命题公式来说化简的原的），对于命题公式来说化简的原则是逻辑等值。则是逻辑等值。返回返回第二章第二章 命题逻辑等值演算命题逻辑等值演算一、逻辑等值定义一、逻辑等值定义 给定两个命题公式给定两个命题公式A A 和和 B B，设，设 A A 和和 B B 含有共同的含有共同的n n个命题变元。个命题变元。若

10、对于这若对于这 n n 个命题变元的所有可能的赋值，个命题变元的所有可能的赋值，命题公式命题公式A A 与与B B的的真值均相同真值均相同，则称命题公式，则称命题公式 A A 逻辑等值于命题公式逻辑等值于命题公式B B。 并记作并记作 A A B B。 逻辑等值的另外的形式定义：逻辑等值的另外的形式定义： 给定两个命题公式给定两个命题公式A A 和和 B B，若，若由由A A和和B B构成的等价式构成的等价式 A BA B为重为重言式言式（永真式），则称命题公式（永真式），则称命题公式 A A 逻辑等值于命题公式逻辑等值于命题公式B B。 两个两个定义可定义可相互证明相互证明注：注： 1 1、

11、“”不是连接词，仅表示不是连接词，仅表示两个公式具有等值关系（不能用两个公式具有等值关系（不能用等号），等号），所构成的式子不是命题公式所构成的式子不是命题公式 2 2、等值的性质：、等值的性质： 对任意公式对任意公式A A，( (进行演算的理论基础进行演算的理论基础) ) ）自反性：）自反性：A A ； ）对称性：若）对称性：若A ，则，则 A； ）传递性：若）传递性：若A ， 则则A 3 3、判断两个公式是否等值的方法、判断两个公式是否等值的方法n 真值表真值表方法：方法：列出两个公式的真值表，列出两个公式的真值表，看其真值是否相同看其真值是否相同（最（最基础的方法）基础的方法） 验证验证

12、 公式公式 pq pq 与公式与公式pqpq等值等值 (A B ) (A B ) A B A B 代数式的演算无法采用此种代数式的演算无法采用此种方法方法n 演算法：演算法：以以经过验算的等值式为基础经过验算的等值式为基础（乘法公式等值定律）（乘法公式等值定律） 利用置换规则（等值代换）及其等值的性质利用置换规则（等值代换）及其等值的性质 得到其他的等值式得到其他的等值式 （与代数式的演算类似）（与代数式的演算类似） 下面引入经过验算得出的等值定律下面引入经过验算得出的等值定律 为使定律使用的更广泛，定律中使用为使定律使用的更广泛，定律中使用元语言元语言的表示方法的表示方法 二、等值定律二、等

13、值定律1 1双重否定律双重否定律 A A2 2. . 幂等律幂等律 A A A A A A3. 3. 结合律结合律 (A B )C A (B C) (A B )C A (B C)4. 4. 交换律交换律 A B B A A B B A5. 5. 分配律分配律 A (B R) (A B )(A R) A (B R) (A B )(A R)6. 6. 吸收律吸收律 A (A B ) A A (A B ) A 7. 7. 德德摩根律摩根律 (A B ) A B (A B ) A B 8. 8. 同一律同一律 A A F A A T 9. 9. 零律零律 A T T A F F10. 10. 排中律排

14、中律 T A A 1111矛盾律矛盾律 F A A 1212蕴涵等值式蕴涵等值式 A B A B1313等价等值式等价等值式 A B （A B）（ B A） A B （A B）（ B A） A B （A B）（ A B） 同真同假同真同假1414假言易位（逆否命题）假言易位（逆否命题） A B B A1515等价否定等值式等价否定等值式 A B A B1616归谬论归谬论 （ A B） （A B ） A三、置换规则：三、置换规则： 设设 （A A）是含公式）是含公式A A的命题公式的命题公式，（B B）是用公式）是用公式B B置换了置换了（A A）中所有出现的）中所有出现的A A所得到的命题公

15、式，则所得到的命题公式，则 若若A A B B有有 （A A） （B B） 注注：置换规则类似于代数中的变量替换：置换规则类似于代数中的变量替换如：公式如：公式 (pq) r (pq) r 因为因为pqpq与与pqpq等值等值故故可用可用pq pq 置换置换pqpq所得到的公式与原式是等值所得到的公式与原式是等值的的即：即： (pq) r （pq） r （pq） r 与（与（pq） r 等值等值故有故有（pq） r （pq） r （p q） r 例：证明下列等值式例：证明下列等值式 (PQ)(P(PQ)(P（PQ) PQ) (PQ) (PQ)解：解： (PQ)(P(PQ)(PQ)(P(PQ)

16、(PQ)(P(PQ) (PQ)(P(PQ) 蕴涵蕴涵等值等值(PQ)(PQ) (PQ)(PQ) 等幂律等幂律(PQ)PQ(PQ)PQ(PP)(QP)Q (PP)(QP)Q 分配律分配律 T (QP)Q T (QP)Q 同一律同一律 QP QP 等幂律等幂律 PQ PQ 交换律交换律2）证明等值式）证明等值式 (pq) r (P r) (q r) （ p )p )(qr) qr四、利用等值演算可确定公式的类型四、利用等值演算可确定公式的类型判断判断(pq) p q 的类型的类型若能得到若能得到 (pq) p q 则则可得到公式为重言式可得到公式为重言式若 A则可得到公式为矛盾式则可得到公式为矛盾

17、式因因为为(pq) p q 公式公式( p（q) ） r 的类型的类型公式公式（ （q) p） 的类型的类型利用等值演算还可以化简一个命题公式利用等值演算还可以化简一个命题公式命题公式的等值演算是数理逻辑中的最基本运算命题公式的等值演算是数理逻辑中的最基本运算. . 析取范式与合取范式析取范式与合取范式 (公式的标准型式）一简单析取式和简单合取式一简单析取式和简单合取式 1 1）“文字文字”定义定义 命题变项及其否定统称作文字命题变项及其否定统称作文字 2 2）仅由有限个文字构成的析取式称作）仅由有限个文字构成的析取式称作简单析取式简单析取式 pq pq 、 p q r q p q r q 3

18、 3）仅由有限个文字构成的合取式称作）仅由有限个文字构成的合取式称作简单合取式简单合取式( (项）项） q p p q r pq p p q r p 4) 4) 简单析取式和简单合取式的性质：简单析取式和简单合取式的性质： 一个简单析取式是重言式当且仅当它一个简单析取式是重言式当且仅当它同时含同时含某个某个命题变项命题变项及它的否定式及它的否定式 一个简单合取式是矛盾式当且仅当它一个简单合取式是矛盾式当且仅当它同时含同时含某个某个命题变项命题变项及它的否定式及它的否定式二析取范式和合取范式二析取范式和合取范式1 1、定义、定义(1)(1)由有限个简单合取式构成的析取式称为析取范式由有限个简单合

19、取式构成的析取式称为析取范式( (代数式）代数式） p p qq rr q pq p ppq q p(2)(2)由有限个简单析取式构成的合取式称为合取范式由有限个简单析取式构成的合取式称为合取范式 (pq)(pq) qq p p pp qq r r q(3)(3)析取范式与合取范式统称为范式析取范式与合取范式统称为范式 AiAi(i=1,2(i=1,2n)n)为简单合取式，为简单合取式，A=A=A1A1 A2A2 . .AnAn为析取范式为析取范式 p p qq r r p p q q prq pr qq 是含是含三个简单合取式三个简单合取式的析的析取范式取范式 Bi(i=1,2Bi(i=1,

20、2n)n)为简单析取式，为简单析取式，B=B=B1B1 B2B2 . . BnBn为合取范式为合取范式 p q rp q r (pq)(pq) qq p p （p p q）（qprqpr）q q 是含是含三个简单析取式三个简单析取式的合取范式的合取范式 2 2、性质：、性质：1)1)一个析取范式是矛盾式当且仅当它的一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式每个简单合取式都是矛盾式2)2)一个合取范式是重言式当且仅当它的一个合取范式是重言式当且仅当它的每个简单析取式都是重言式每个简单析取式都是重言式 p p P q q q q 0 0 0 0 0 0 （p pp p）（qqqq）

21、1 1 1 1 1 13 3、范式存在定理、范式存在定理 任一命题公式都任一命题公式都存在存在着与之等值的着与之等值的析取范式与合取范式析取范式与合取范式利用等值定律可将任何公式化成与之等值的析取范式和合取范式利用等值定律可将任何公式化成与之等值的析取范式和合取范式 确定析取范式和合取范式确定析取范式和合取范式 (pq)（p r) (pq) （p r) 总可以通过以下方法步骤：总可以通过以下方法步骤：1 1消去联结词消去联结词 ( (若存在若存在) )2 2否定号的消去否定号的消去( (利用双重否定律利用双重否定律) )或内移或内移( (利用德摩根律利用德摩根律) )3 3利用分配律：利用利用

22、分配律：利用对对的分配律求析取范式，的分配律求析取范式， 对对的分配律的分配律求合取范式求合取范式 是否唯一是否唯一? ?例例: : 确定确定 (p (p q) r) p q) r) p 的析取范式及合取范式的析取范式及合取范式 ( (p (p q) q) r) p r) p (p (p q) q) r) r) p p (p (p q) q) r) r) p p (p (p q q p ) ( p ) ( r r p) p) (p (p q q p ) ( p ) ( r r p) p) 合取范式合取范式 (p (p q ) ( q ) ( r r p) p) 合取范式合取范式(p (p q) r) p