离散数学第2章

2.2 命题逻辑等值演算• 2.2.1 等值式与等值演算– 等值式与基本等值式 – 真值表法与等值演算法 • 2.2.2 联结词完备集– 真值函数 – 联结词完备集 – 与非联结词和或非联结词1等值式定义2.11 若等价式AB是重言式, 则称A与B等值, 记作 AB, 并称AB是等值式说明: (1) 是元语言符号, 不要混同于和= (2) A与B等值当且仅当A与B在所有可能赋值下的真值都相 同, 即A与B有相同的真值表 (3) n个命题变项的真值表共有 个, 故每个命题公式都有无穷多个等值的命题公式 (4) 可能有哑元出现. 在B中出现, 但不在A中出现的命题变 项称作A的哑元. 同样,在A中出现, 但不在B中出现的命题变 项称作B的哑元. 哑元的值不影响命题公式的真值.2真值表法例2.11 判断 (pq) 与 pq 是否等值解结论: (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 10 1 1 0 1 0 0 11 0 0 1 1 0 0 11 1 0 0 1 0 0 13真值表法(续)例2.12 判断下述3个公式之间的等值关系:p(qr), (pq)r, (pq)r 解p q r p(qr) (pq)r (pq)r0 0 0 1 0 10 0 1 1 1 10 1 0 1 0 1 0 1 1 1 1 11 0 0 1 1 1 1 0 1 1 1 11 1 0 0 0 01 1 1 1 1 1 p(qr)与(pq)r等值, 但与(pq)r不等值 4基本等值式双重否定律 AA 幂等律 AAA, AAA 交换律 ABBA, ABBA 结合律 (AB)CA(BC) (AB)CA(BC) 分配律 A(BC)(AB)(AC) A(BC) (AB)(AC) 德摩根律 (AB)AB(AB)AB 吸收律 A(AB)A, A(AB)A5基本等值式(续)零律 A11, A00 同一律 A0A, A1A排中律 AA1矛盾律 AA0蕴涵等值式 ABAB等价等值式 AB(AB)(BA)假言易位 ABBA等价否定等值式 ABAB归谬论 (AB)(AB) A6等值演算等值演算: 由已知的等值式推演出新的等值式的过程置换规则: 若AB, 则(B)(A) 例2.13 证明 p(qr)  (pq)r证 p(qr)  p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq) r （蕴涵等值式）7实例等值演算不能直接证明两个公式不等值. 证明两个公式不等值的基本思想是找到一个赋值使一个成真, 另一个成假.例2.14 证明: p(qr) (pq) r方法一 真值表法（见例2.12）方法二 观察法. 容易看出000使左边成真, 使右边成假.方法三 先用等值演算化简公式, 再观察.8实例例 用等值演算法判断下列公式的类型(1) q(pq) 解 q(pq)  q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律）该式为矛盾式.9实例(续)(2) (pq)(qp) 解 (pq)(qp)  (pq)(qp) （蕴涵等值式）  (pq)(pq) （交换律） 1该式为重言式.10实例(续)(3) ((pq)(pq))r 解 ((pq)(pq))r (p(qq))r （分配律） p1r （排中律） pr （同一律）非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结:A为矛盾式当且仅当A0; A为重言式当且仅当A1说明:演算步骤不唯一,应尽量使演算短些。

11真值函数定义2.12 称F:{0,1}n{0,1}为n元真值函数n元真值函数共有 个每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式1元真值函数p 0 0 0 1 11 0 1 0 1 122元真值函数p q0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 1p q0 0 1 1 1 1 1 1 1 10 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 11 1 0 1 0 1 0 1 0 113联结词完备集定义2.13 设S是一个联结词集合, 如果任何n(n1) 元真 值 函数都可以由仅含S中的联结词构成的公式表示,则称S 是 联结词完备集定理2.1 下述联结词集合都是完备集: (1) S1={, , ,  , } (2) S2={, , , } (3) S3={,  , } (4) S4={, } (5) S5={, } (6) S6={, }AB  (AB)(BA) AB  AB AB   (AB)   (AB) AB   (AB) AB  (A)B   AB14复合联结词与非式: pq(pq), 称作与非联结词 或非式: pq(pq), 称作或非联结词pq为真当且仅当p,q不同时为真 pq为真当且仅当p,q同时为假定理2.2 {},{}是联结词完备集 证  p  (pp)  pppq   (pq)  (pq)  (pq)(pq) 得证{}是联结词完备集. 对于{}可类似证明.152.3 范式• 2.3.1 析取范式与合取范式– 简单析取式与简单合取式 – 析取范式与合取范式 • 2.3.2 主析取范式与主合取范式– 极小项与极大项 – 主析取范式与主合取范式 – 主范式的用途16简单析取式与简单合取式文字:命题变项及其否定的统称 简单析取式:有限个文字构成的析取式 如 p, q, pq, pqr, …简单合取式:有限个文字构成的合取式 如 p, q, pq, pqr, …定理2.3 (1) 一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定 (2) 一个简单合取式是矛盾式当且仅当它同时含某个命 题 变项和它的否定17析取范式与合取范式析取范式:由有限个简单合取式组成的析取式A1A2Ar, 其中A1,A2,,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式A1A2Ar , 其中A1,A2,,Ar是简单析取式 范式:析取范式与合取范式的统称 定理2.4 (1) 一个析取范式是矛盾式当且仅当 它的每一个简单合取式都是矛盾式 (2) 一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式18范式存在定理定理2.5 任何命题公式都存在着与之等值的析取范式与 合 取范式. 证 求公式A的范式的步骤： (1) 消去A中的, ABABAB(AB)(AB) (2) 否定联结词的内移或消去 A A(AB)AB(AB)AB 19范式存在定理(续)(3) 使用分配律A(BC)(AB)(AC) 求合取范式 A(BC) (AB)(AC) 求析取范式例2.16 求(pq)r 的析取范式与合取范式 解 (pq)r (pq)r  (pq)r 析取范式 (pr)(qr) 合取范式注意: 公式的。