离散数学教学课件：lecture 3 等值式

1、定义定义2.1 设A,B式两个命题公式，若A ,B构成的等价式A B为重言式，则称A与B是等值的等值的，记作A B. 注意：注意：定义中给出的符号不是联结词符，它是用来说明A与B等值（A B是重言式）的一种记法，因而是元语言符号。 判断等值式有如下方法： 1.真值表 2.等值演算 3.范式 哑元哑元 ：一组公式中共同含有多个变元，如果某变元在公式p中没有出现，则称其为该公式的哑元。 1. 双重否定律 A A （2.1） 3. 交换律 AB BA，AB BA （2.3） 5. 分配律 A(BC) (AB)(AC) （对的分配律） A(BC) (AB)(AC) （对的分配律） （2.5） 6. 德

2、摩根律 (AB) AB，(AB) AB （2.6） 2. 幂等律 A AA，A AA （2.2） 4. 结合律 (AB)C A(BC) (AB)C A(BC) （2.4） 7. 吸收律 A(AB) A，A(AB) A （2.7） 8. 零律 A1 1,A0 0 （2.8） 10. 排中律 AA 1 （2.10） 12. 蕴涵等值式 AB AB （2.12） 14. 假言易位 AB BA （2.14） 9. 同一律 A0 A，A1 A （2.9） 11. 矛盾律 AA 0 （2.11） 16. 归谬论 (AB)(AB) A （2.16） 13. 等价等值式 (A B) (AB)(BA) （2.1

3、3） 15. 等价否定等值式 A B A B （2.15） 置换规则置换规则 设(A)是含公式A的命题公式，(B)是用公式B置换了(A)中所有的A后得到的命题公式，若B A，则(B) (A). 例例2.4 证明：(pq)r p(qr) 2.2 范式范式 每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式的根情况。逻辑公式在等值演算下也有标准形-范式，范式有两种：析取范式和合取范式。 定义定义2.2 命题变项及其否定统称作文字文字。仅有有限个文字构成的析取式称作简单析取式简单析取式。仅有有限个文字构成的合取式称作简单合取式简单合取式。 问：一个文字是？ 定理定理2.1 （1）一个简单

4、析取式是重言式当且仅当它同时含某个命题变项及它的否定式。 （2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。 证明：证明： 设Ai是含n个文字的简单析取式，若Ai中既含有某个命题变项pj，又含有它的否定式pj，由交换律、排中律和零律可知，Ai为重言式。反之，若Ai为重言式，则它必同时含某个命题变项及它的否定式，否则，若将Ai中的不带否定号的命题变项都取0，带否定号的命题变项都取1，此赋值为Ai的成假赋值，这与Ai是重言式相矛盾。类似的讨论可知，若Ai是含n个命题变项的简单合取式，且Ai为矛盾式，则Ai中必同时含有某个命题变项及它的否定式，反之亦然。 定义定义2.3 （1）

5、由有限个简单合取式构成的析取式称为析取范式析取范式。 （2）由有限个简单析取式构成的合取式称为合取范式合取范式。 （3）析取范式与合取范式统称为范式范式。 定理定理2.2 （1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 （2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。 定理定理2.3 （范式存在定理）任一命题公式都存在着与之等值的析取范式与合取范式。 证明证明 首先，我们观察到在范式中不出现联结词与 。由蕴涵等值式与等价等值式可知 AB AB A B (AB)(AB) （2.17） 因而在等值的条件下，可消去任何公式中的联结词和 。 其次，在范式中不出现如下形

6、式的公式： A,(AB),(AB)对其利用双重否定律和德摩根律，可得 A A (AB) AB (AB) AB （2.18） 再次，在析取范式中不出现如下形式的公式： A(BC) 在合取范式中不出现如下形式的公式： A(BC) 利用分配律，可得 A(BC) (AB)(AC) A(BC) (AB)(AC) (2.19) 由（2.17）,（2.18）,（2.19）3步，可将任一公式化成与之等值的析取范式或合取范式。 据此定理，求范式可使用如下步骤： 1.消去联结词和. 2.否定号的消去（利用双重否定律）或内移（利用德摩根律）; 3.利用分配律：利用对的分配律求析取范式，对的分配律求合取范式。 例例2

7、.7 求下面公式的析取范式与合取范式： (pq) r 解解 为了清晰和无误，演算中利用交换律，使得每个简单析取式或合取式中命题变项的出现都是按字典顺序，这对下文中求主范式更为重要。 （1）先求合取范式 (pq) r(pq) r （消去） (pq)r)(r(pq) （消去 ） (pq)r)(rpq) （消去） (pq)r)(pqr) （否定号内移） (pr)(qr)(pqr) （对分配律） 经过五步演算，得到了含三个简单析取式的合取范式。 问：合/析取范式是唯一的吗？ 定义定义2.4 在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一

8、次，且第i个命题变项或它的否定式出现在从左算起的第i位上（若命题变项无角标，就按字典顺序排列），称这样的简单合取式（简单析取式）为极小项（极大项）极小项（极大项）。 由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而n个命题变项共可产生2n个不同的极小项。其中每个极小项都有且仅有一个成真赋值。若成真赋值所对应的二进制数转换为十进制数i，就将所对应极小项记作mi.类似地，n个命题变项共可产生2n个极大项，每个极大项只有一个成假赋值，将其对应的十进制数i做极大项的角标，记作Mi。重要重要 定理定理2.4 设mi与Mi是命题变项p1,p2,pn形成的极小项和极大项，则 mi Mi，M

9、i mi 定义定义2.5 设由n个命题变项构成的析取范式（合取范式）中所有的简单合取式（简单析取式）都是极小项（极大项），则称该析取范式（合取范式）为主析取范式（主合取范式）主析取范式（主合取范式）。 定理定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。例例2.8 求例2.7中公式的主析取范式和主合取范式。 解解 （1）求主析取范式。 在例2.7中已给出的公式的析取范式，即 （pq） r (pqr)(pr)(qr) 在此析取范式中，简单合取式pr，qr都不是极小项。下面分别求出它们派生的极小项。注意，因为公式含三个命题变项，所以极小项均由三个文字组成。 （pr）

10、 p（qq）r (pqr)(pqr) m1m3 而简单合取式pqr已是极小项m4。于是 qr (pp)qr (pqr）(pqr) m3m7 (pq) r m1m3m4m7 四、几点注意四、几点注意 1. 由公式的主析取范式求主合取范式 设公式A含n个命题变项。A的主析取范式含s(0s2n)个极小项，即 A mi1 mi2 mis,0ij2n-1 ,j=1,2,s。 由定理2.4可知 A A (mj1mj2mj2n-s) mj1 mj2 mj2n-s Mj1 Mj2 Mj2n-s 没出现的极小项为mj1,mj2,mj2n-s,它们的角标的二进制表示为A的成真赋值，因而A的主析取范式为 A = mj1mj2mj2n-s于是，由公式的主析取范式，即可求出它的主合取范式。 例例2.13 由公式的主析取范式，求主合取范式： A m1m2m3 (A中含两个命题变项p,q,r) 解解 A的主析取范式中没出现的极小项为m0,m4,m5,m6,m7，因而 B M0M4M5M6M7 问：由公式的主合取范式，是否也可以确定主析取范式？ 如何确定？ 2重言式与矛盾式的主合取范式 矛盾式无成真赋值，因而矛盾式的主合取范式含2n（n为公式中命题变项个数）个极大项。而重言式无成假赋值，因而主合取范式不含任何极大项。将重