析取范式与合取范式

《析取范式与合取范式》由会员分享，可在线阅读，更多相关《析取范式与合取范式（40页珍藏版）》请在文档大全上搜索。

1、作 业2.11 p,q:0 r,s:1 (p (q r) (r s)(p r) ( q s)( p q r) (p q r)( p q r s) (p q r s)12.2 命题逻辑等值演算2.2.1 等值式与等值演算等值式与等值演算等值式与基本等值式等值式与基本等值式真值表法与等值演算法真值表法与等值演算法2.2.2 联结词完备集联结词完备集真值函数真值函数联结词完备集联结词完备集与非联结词和或非联结词与非联结词和或非联结词2等值式3定义定义2.11 若等价式若等价式AB是重言式是重言式, 则称则称A与与B等值等值, 记作记作AB, 并称并称AB是是等值式等值式说明说明: (1) 是是元语言

2、符号元语言符号, 不要混同于不要混同于和和=(2) A与与B等值当且仅当等值当且仅当A与与B在所有可能赋值下的真值都相在所有可能赋值下的真值都相同同, 即即A与与B有相同的真值表有相同的真值表(3) n个命题变项的真值表共有个命题变项的真值表共有 个个, 故每个命题公式都有故每个命题公式都有无穷多个等值的命题公式无穷多个等值的命题公式(4) 可能有哑元出现可能有哑元出现. 在在B中出现中出现, 但不在但不在A中出现的命题变中出现的命题变项称作项称作A的的哑元哑元. 同样同样,在在A中出现中出现, 但不在但不在B中出现的命题变中出现的命题变项称作项称作B的哑元的哑元. 哑元的值不影响命题公式的真

3、值哑元的值不影响命题公式的真值.n22真值表法例例1 判断判断 (p q) 与与 p q 是否等值是否等值解解4结论结论: (p q) ( p q) p q p q p q (p q) p q (p q)( p q) 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1真值表法(续)例例2 判断下述判断下述3个公式之间的等值关系个公式之间的等值关系: p(qr), (pq)r, (p q)r解解5 p q r p(qr) (pq)r (p q)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0

4、 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)与与(p q)r等值等值, 但与但与(pq)r不等值不等值基本等值式双重否定律双重否定律 AA幂等律幂等律 A AA, A AA交换律交换律 A BB A, A BB A结合律结合律 (A B) CA (B C) (A B) CA (B C)分配律分配律 A (B C)(A B) (A C) A (B C) (A B) (A C)德摩根律德摩根律 (A B)AB (A B)AB吸收律吸收律 A (A B)A, A (A B)A6基本等值式(续)零律零律 A 11, A

5、 00 同一律同一律 A 0A, A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB) (BA)假言易位假言易位 ABBA等价否定等值式等价否定等值式 ABAB归谬论归谬论 (AB) (AB) A7等值演算等值演算等值演算: 由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则: 若若AB, 则则 (B) (A) 例例3 证明证明 p(qr) (p q)rp49,例例2.12(1)证证 p(qr) p ( q r) （蕴涵等值式）蕴涵等值式） ( pq) r （结合律）结合律） (p q) r （

6、德摩根律）德摩根律） (p q) r （蕴涵等值式）蕴涵等值式）8实例9等值演算不能直接证明两个公式不等值等值演算不能直接证明两个公式不等值. 证明两个公式不证明两个公式不等值的基本思想是找到一个赋值使一个成真等值的基本思想是找到一个赋值使一个成真, 另一个成假另一个成假.例例4 证明证明: p(qr) (pq) r p52方法一方法一 真值表法（见例真值表法（见例2）方法二方法二 观察法观察法. 容易看出容易看出000使左边成真使左边成真, 使右边成假使右边成假.方法三方法三 先用等值演算化简公式先用等值演算化简公式, 再观察再观察.实例例例5 用等值演算法判断下列公式的类型用等值演算法判断

7、下列公式的类型(1) q(pq) 解解 q(pq) q( p q) （蕴涵等值式）蕴涵等值式） q (pq) （德摩根律）德摩根律） p (qq) （交换律，结合律）交换律，结合律） p 0 （矛盾律）矛盾律） 0 （零律）（零律）该式为矛盾式该式为矛盾式.10实例(续)(2) (pq)( qp) 解解 (pq)( qp) ( p q)(qp) （蕴涵等值式）蕴涵等值式） ( p q)( p q) （交换律）交换律） 1该式为重言式该式为重言式.11实例(续)(3) (p q) (pq) r) 解解 (p q) (pq) r) (p (qq) r （分配律）分配律） p 1 r （排中律）排中

8、律） p r （同一律）同一律）非重言式的可满足式非重言式的可满足式. .如如101是它的成真赋值是它的成真赋值, ,000是它的是它的成假赋值成假赋值.12总结总结:A为矛盾式当且仅当为矛盾式当且仅当A0; A为重言式当且仅当为重言式当且仅当A1说明说明:演算步骤不惟一演算步骤不惟一, ,应尽量使演算短些应尽量使演算短些真值函数定义定义2.12 称称F:0,1n0,1为为n元元真值函数真值函数13n元真值函数共有元真值函数共有 个个每一个命题公式对应于一个真值函数每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式每一个真值函数对应无穷多个命题公式n221元真值函数元真值函数

9、p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF142元真值函数元真值函数 p q 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 p q 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(

10、8FFFFFFFF联结词完备集定义定义2.13 设设S是一个联结词集合是一个联结词集合, 如果任何如果任何n(n 1) 元真值元真值函数都可以由仅含函数都可以由仅含S中的联结词构成的公式表示中的联结词构成的公式表示, ,则称则称S是是联结词完备集联结词完备集定理定理2.1 下述联结词集合都是完备集下述联结词集合都是完备集:(1) S1= , , , , (2) S2= , , , (3) S3= , , (4) S4= , (5) S5= , (6) S6= , 15AB (AB) (BA)AB A BA B (A B) ( AB)A B ( AB)A B ( A) B AB复合联结词与非式与

11、非式: p q(p q), 称作称作与非联结词与非联结词或非式或非式: p q(p q), 称作称作或非联结词或非联结词p q为真当且仅当为真当且仅当p,q不同时为真不同时为真p q为真当且仅当为真当且仅当p,q同时为假同时为假定理定理2.2 , 是联结词完备集是联结词完备集证证 p (p p) p p p q (p q) (p q) (p q) (p q)得证得证 是联结词完备集是联结词完备集. 对于对于 可类似证明可类似证明.162.3 范式2.3.1 析取范式与合取范式析取范式与合取范式简单析取式与简单合取式简单析取式与简单合取式析取范式与合取范式析取范式与合取范式2.3.2 主析取范式