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

《离散数学 第二章 命题逻辑等值演算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、q)→(q→┓p)1110pqrp→(p∨q∨r)00010011010101111001101111011111返回对于形似于条件命题的构成形式即A→B而且要说明是重言式如：┐Q∧（Ｐ→Q）→┐P可利用条件联结词的性质来给予证明分析1：若要得出：当设A为真，B为假的情况不会出现，那么A→B为永真式。可证明：设前件为真分析2：还可以从设B为假，推出A为真的情况不会出现（A为假），那么A→B为永真式。证明：设后件为假(（Ｐ→Q）∧(Q→R))→(Ｐ→R)不同真值表的公式1）当命题变元确定后，通过五个

4、连接词及其命题变元可以构成无数个不同表现形式的命题公式。问题：这些不同形式的命题公式的真值表是否都不相同？先看变元仅有两个p,q那么关于这两个变元的公式的赋值仅有4组任何关于这两个变元的公式的所有真值表只能是一组4位二进制数4位二进制数的不同状态共有16＝24关于2个变元的不同真值表的公式仅有16种。以此推断：2）当命题变元确定后，由于其公式的赋值组数是确定的（共2n组）公式在一组赋值下是一个真值（一位二进制）在2n组赋值下对应为2n位二进制n个变元的不同真值表的公式仅有（2）（2n）种例：2个变

5、元的16种不同真值表Pq(p∧┑p)∨(q∧┑q)P∧qP∧┑qP┑P∧qq┑(P↔q)P∨q000000000001000011110001100111101010101Pq┑(P∨q)P↔q┑qq→P┑PP→q┑(P∧q)(P∨┑p)∧(q∨┑q)001111111101000011110001100111101010101例：看几个公式的真值表：pqp→q┓p∨q0011011110001111pqp↔q(p→q)∧(q→p)(p∧q)∨(┓p∧┓q)00111010001000011111

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

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

8、两个公式的真值表，看其真值是否相同（最基础的方法）验证公式p→q与公式┑p∨q等值┐(A∧B)⇔┐A∨┐B代数式的演算无法采用此种方法演算法：以经过验算的等值式为基础（乘法公式－等值定律）利用置换规则（等值代换）及其等值的性质得到其他的等值式（与代数式的演算类似）下面引入经过验算得出的等值定律为使定律使用的更广泛，定律中使用元语言的表示方法二、等值定律1．双重否定律A⇔┐┐A2.幂等律A∨A⇔AA∧A⇔A3.结合律(A∨B)∨C⇔A∨(B∨C)(A∧B)∧C⇔A∧(B∧C)4.交换