离散数学：1-3 等值演算1-4 联结词全功能集

1、11.3 命题逻辑等值演算命题逻辑等值演算 等值式等值式基本等值式基本等值式等值演算等值演算置换规则置换规则2等值式定义定义1.10 若等价式若等价式AB是重言式是重言式, 则称则称A与与B等值等值, 记作记作AB, 并称并称AB是是等值式等值式用真值表可验证两个公式是否等值用真值表可验证两个公式是否等值请验证：请验证：p(qr) (p q) r p(qr) (pq) r 说明说明: (1) 是是元语言符号元语言符号, 不要混同于不要混同于和和=(2) A与与B等值当且仅当等值当且仅当A与与B在所有可能赋值下的真值都相在所有可能赋值下的真值都相同同, 即即A与与B有有相同的真值表相同的真值表(

2、3) n个命题变项的真值表共有个命题变项的真值表共有 个个, 故每个命题公式都有故每个命题公式都有无穷多个等值的命题公式无穷多个等值的命题公式n223真值表法(续)例例2 判断下述判断下述3个公式之间的等值关系个公式之间的等值关系: p(qr), (pq)r, (p q)r解解 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 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不等值不等值4真值表法

3、例例1 判断判断 (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 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 15基本等值式双重否定律双重否定律 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)

4、AB (A B)AB6基本等值式(续)吸收律吸收律 A (A B)A, A (A B)A零律零律 A 11, A 00 同一律同一律 A 0A, A 1A排中律排中律 AA1矛盾律矛盾律 AA0蕴涵等值式蕴涵等值式 ABA B等价等值式等价等值式 AB(AB) (BA)假言易位假言易位 ABBA等价否定等值式等价否定等值式 ABAB归谬论归谬论 (AB) (AB)A7等值演算与置换规则等值演算与置换规则 等值演算等值演算: 由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则：若：若AB, 则则 (B) (A) 等值演算的基础：等值演算的基础： (1) 等值

5、关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递 (2) 基本的等值式基本的等值式 (3) 置换规则置换规则 8等值演算等值演算等值演算: 由已知的等值式推演出新的等值式由已知的等值式推演出新的等值式的过程的过程置换规则置换规则: 若若AB, 则则 (B) (A) 例如例如:p(qr) p( q r)( (蕴涵等值式、置换规则蕴涵等值式、置换规则) )9等值演算等值演算等值演算: 由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程置换规则置换规则: 若若AB, 则则 (B) (A) 例如例如:p(qr) p( q r)( (蕴涵等值式、置换规则蕴涵等值式、置换

6、规则) )证证: : 令令 A=(qr); B=( q r)显然显然AB,令令 (X)=pX，则，则 (A)= pA= p(qr) (B)= pB= p( q r)10等值演算例如例如 qr q r( (蕴涵等值式、置换规则蕴涵等值式、置换规则) )例如例如 p(qr) p( q r) p ( q r)p(qr) p (qr) p ( q r) ( (蕴涵等值式、置换规则蕴涵等值式、置换规则) )11等值演算等值演算等值演算: 由已知的等值式推演出新的等由已知的等值式推演出新的等值式的过程值式的过程置换规则置换规则: 若若AB, 则则 (B) (A) 例例3 证明证明 p(qr) (p q)r

7、12应用举例应用举例证明两个公式等值证明两个公式等值 例例1 证明证明 p(qr) (p q)r证证 p(qr) p ( q r) （蕴涵等值式，置换规则）（蕴涵等值式，置换规则） ( pq) r （结合律，置换规则）（结合律，置换规则） (p q) r （德（德 摩根律，置换规则）摩根律，置换规则） (p q) r （蕴涵等值式，置换规则）（蕴涵等值式，置换规则） 说明说明: :也可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍） 因为每一步都用置换规则，故可不写出因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 13应用举例应用举

8、例证明两个公式不等值证明两个公式不等值例例2 证明证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假. 方法一方法一 真值表法（自己证）真值表法（自己证） 方法二方法二 观察赋值法观察赋值法. 容易看出容易看出000, 010等是左边的等是左边的的成真赋值，是右边的成假赋值的成真赋值，是右边的成假赋值. 方法三方法三 用等值演算先化简两个公式，再观察用等值演算先化简两个公式，再观察.14应用举例应用举例判断公式类

9、型判断公式类型 例例3 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1) q(pq) 解解 q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德（德 摩根律）摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式. 15例例3 (续续)(2) (pq)( qp) 解解 (pq)( qp) ( p q)(qp) （蕴涵等值式）（蕴涵等值式） ( p q)( p q) （交换律）（交换律） 1由最后一步可知，该式为重言式由最后一步可知，该式为重

10、言式.问：最后一步为什么等值于问：最后一步为什么等值于1？ 16例例3 (续续)(3) (p q) (pq) r) 解解 (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式的可这不是矛盾式，也不是重言式，而是非重言式的可满足式满足式. .如如101是它的成真赋值是它的成真赋值, ,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1说明：演算步骤不惟一说明：演算步骤不惟一, ,应尽量使演算短些应尽量使

11、演算短些171.4 联结词全功能集联结词全功能集 复合联结词复合联结词 排斥或排斥或 与非式与非式 或非式或非式真值函数真值函数联结词全功能集联结词全功能集18复合联结词复合联结词 排斥或排斥或: p q(pq) ( p q)与非式与非式: p q(p q)或非式或非式: p q(p q) 19真值函數真值函數 n22n22问题：含问题：含n个命题变项的所有公式共产生多少个互个命题变项的所有公式共产生多少个互不相同的真值表？不相同的真值表？ 答案为答案为 个，为什么？个，为什么？定义定义 称定义域为称定义域为000, 001, , 111，值域，值域为为0,1的函数是的函数是n元真值函数元真值

12、函数，定义域中的元素是，定义域中的元素是长为长为n的的0,1串串. 常用常用F:0,1n0,1 表示表示F是是n元真值元真值函数函数. 共有共有 个个n元真值函数元真值函数. 例如例如 F:0,120,1，且，且F(00)=F(01)=F(11)=0，F(01)=1，则，则F为一个确定的为一个确定的2元真值函数元真值函数.20真值函数定义定义称称F:0,1n0,1为为n元元真值函数真值函数n元真值函数共有元真值函数共有 个个每一个命题公式对应于一个真值函数每一个命题公式对应于一个真值函数每一个真值函数对应无穷多个命题公式每一个真值函数对应无穷多个命题公式n221元真值函数元真值函数 p 0 0

13、 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF21命题公式与真值函数命题公式与真值函数 )2(13F对于任何一个含对于任何一个含n个命题变项的命题公式个命题变项的命题公式A，都存在，都存在惟一的一个惟一的一个n元真值函数元真值函数F为为A的真值表的真值表. .等值的公式对应的真值函数相同等值的公式对应的真值函数相同.下表给出所有下表给出所有2元真值函数对应的真值表元真值函数对应的真值表, 每一个含每一个含2 2个命题变项的公式的真值表都可以在下表中找到个命题变项的公式的真值表都可以在下表中找到. 例如：例如：pq, p q, ( p q) ( (pq) q) 等等都

14、对应都对应表中的表中的222元真值函数对应的真值表元真值函数对应的真值表p q0 00 10 11 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 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(0FFFFFFFFp q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF23联结词的全功能集联结词的全功能集

15、 定义定义 在一个联结词的集合中，如果一个联结词可在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为由集合中的其他联结词定义，则称此联结词为冗余冗余的联结词的联结词，否则称为，否则称为独立的联结词独立的联结词.例如例如, ,在联结词集在联结词集 , , , , 中，由于中，由于 pqp q,所以，所以，为冗余的联结词为冗余的联结词; 类似地，类似地，也是冗余的也是冗余的联结词联结词. 又在又在 , , 中，由于中，由于 p q( pq)，所以，所以， 是冗余的联结词是冗余的联结词. 类似地，类似地， 也是冗余的联也是冗余的联结词结词. 24联结词的全功能集联结词的全

16、功能集( (续续) )定义定义 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1) 元元真值函数都可以由仅含真值函数都可以由仅含S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S是是联结词全功能集联结词全功能集. 若不含冗余的联结词若不含冗余的联结词则称其为则称其为极小全功能集极小全功能集。说明：说明： 若若S是联结词全功能集，则任何命题公式都可用是联结词全功能集，则任何命题公式都可用S中的联结词表示中的联结词表示. 若若S1, S2是两个联结词集合，且是两个联结词集合，且S1 S2. 若若S1是全是全功能集，则功能集，则S2也是全功能集也是全功能集. 25联

17、结词完备集定理定理下述联结词集合都是下述联结词集合都是全功能集全功能集:(1) S1= , , , , (2) S2= , , , (3) S3= , , (4) S4= , (5) S5= , (6) S6= , AB (AB) (BA)AB A BA B (A B) ( AB)A B ( AB)A B ( A) B AB26复合联结词与非式与非式: p q(p q), 称作称作与非联结词与非联结词或非式或非式: p q(p q), 称作称作或非联结词或非联结词p q为真当且仅当为真当且仅当p,q不同时为真不同时为真p q为真当且仅当为真当且仅当p,q不同时为假不同时为假定理定理 , 是联结词是联结词全功能集全功能集证证 p (p p) p p p q (p q) (p q) (p q) (p q)得证得证 是联结词是联结词全功能集全功能集. 对于对于 可类似证明可类似证明.27