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

1、 2.2 析取范式与合取范式析取范式与合取范式2.1 等值式等值式2.2 析取范式与合取范式析取范式与合取范式2.3 联结词的完备集联结词的完备集真值表相同真值表相同逻辑运算构成逻辑运算构成命题代数命题代数, 具有下列运算律具有下列运算律.排中律排中律矛盾律矛盾律这些关系式仅这些关系式仅涉及涉及 , , 三三个联结词个联结词上列运算律都可以用真值表来证明上列运算律都可以用真值表来证明.真值表相同真值表相同例如例如条件等值式条件等值式: A B A B涉及联结词涉及联结词 , 的运算律有的运算律有双条件等值式双条件等值式: (AB) (AB) (BA)假言易位假言易位: A B B A等价否定律

2、等价否定律: A B A B以及以及: A (B C) (AB) C 等等.很常用很常用等值关系的确立等值关系的确立:1. 真值表真值表;2. 等值演算等值演算: 运用保持等值性的规则由已知的等值运用保持等值性的规则由已知的等值式式(模式模式)推出新的等值式推出新的等值式.代入规则代入规则: 等值式模式的代换实例是等值式等值式模式的代换实例是等值式.在蕴涵等值式在蕴涵等值式 A B A B 中取中取 A 为为 p, B 为为 q 得得p q p q.而取而取 A 为为 p q r, B 为为 p q 则得则得(p q r) (p q) (p q r) (p q).具体的等值式叫做等值式具体的等

3、值式叫做等值式模式模式的的代入实例代入实例.置换规则置换规则 设设 (A) 是含公式是含公式 A 的命题公式的命题公式, (B) 是是用公式用公式 B 置换了置换了 (A) 中所有的中所有的 A 后得到的命题公后得到的命题公式式, 若若B A, 则则 (B) (A).例如例如, (A)= A r = (pq) r (B) = B r= ( p q ) r 由由 A = p q p q = B 可得可得(pq) r ( p q)r.2.1 等值式等值式2.2 析取范式与合取范式析取范式与合取范式2.3 联结词的完备集联结词的完备集定义定义 命题变元及其否定叫做命题变元及其否定叫做文字文字. 仅由

4、文字构成仅由文字构成的析取式叫做的析取式叫做简单析取式简单析取式. 仅由文字构成的合取式仅由文字构成的合取式叫做叫做简单合取式简单合取式.l简单析取式是重言式简单析取式是重言式 它同时含某个命题变元及它同时含某个命题变元及其否定其否定.重言式重言式: p p, p r p;非重言式非重言式: p q, p q r.l简单合取式是矛盾式简单合取式是矛盾式 它同时含有某个命题变元它同时含有某个命题变元及其否定及其否定.矛盾式矛盾式:p p, p p r;非矛盾式非矛盾式: p q, p q r.l由简单合取式构成的析取式叫做由简单合取式构成的析取式叫做析取范式析取范式.A = A1 A2 A3 =

5、 (p q) ( q r) p.l由简单析取式构成的合取式称为由简单析取式构成的合取式称为合取范式合取范式. A = A1 A2 A3 = (p q r) ( p q) r. p q r 是一个析取范式是一个析取范式(一个简单合取式一个简单合取式), 也是也是一个合取范式一个合取范式(三个简单析取式的合取三个简单析取式的合取)p q r 是一个析取范式是一个析取范式(三个简单合取式的析取三个简单合取式的析取), 也是一个也是一个合取范式合取范式(一个简单析取式一个简单析取式). (文字文字), 简单式简单式( ), 范式范式( ).证明证明(构造性构造性) 利用蕴涵等值式与等价等值式消去公式中

6、的利用蕴涵等值式与等价等值式消去公式中的蕴涵词和等价词蕴涵词和等价词 和和 :A B A B,A B ( A B) (A B).利用双重否定律和德利用双重否定律和德摩根律消去摩根律消去公式公式中的否定词中的否定词 或将或将之内移直至与命题变元结合成文字之内移直至与命题变元结合成文字: A A, (A B) A B, (A B) A B.视所求范式类型视所求范式类型, 分别利用分配律分别利用分配律A (B C) (A B) (A C) 或或A (B C) (A B) (A C)将合取词将合取词 (求析取范式时求析取范式时)或析取词或析取词 (求合取范式时求合取范式时)内移内移.即可将任一公式化成

7、与之等值的析取即可将任一公式化成与之等值的析取/合取合取范式范式.例例3 求求 A = (p q) r 的析取范式与合取范式的析取范式与合取范式.解解 (1)先求合取范式先求合取范式(p q) r得合取范式得合取范式. ( p q) r) (r (p q) ( ( p q) r) ( r p q) (p q) r) ( p q r) (p r) ( q r) ( p q r)(消去消去)(消去消去)( 内移内移)( 内移内移)例例3 求求 A = (pq)r 的析取范式与合取范式的析取范式与合取范式.(2)求析取范式求析取范式 (pqr) ( p r) (q r)析取范式析取范式/合取范式不是

8、唯一的合取范式不是唯一的 (rp)(pq q) (pqr) (r q) (rr)( 内移内移)析取范式析取范式析取范式析取范式(pqp) (p q) r ( p q) r) (r (p q) ( ( p q) r) ( r p q) (p q) r) ( p q r)(消去消去)(消去消去)( 内移内移)极小极小(大大)项项: 在含有在含有n个命题变元的简单合个命题变元的简单合(析析)取式中取式中, 若第若第 i 个变元的两个文字个变元的两个文字(该变元或其否定该变元或其否定)恰好出现恰好出现一个一个, 且出现在第且出现在第 i 位上位上(按角标或字典顺序按角标或字典顺序). 小项，大项的编码

9、规则小项，大项的编码规则 每个极小项都恰有一个成真赋值每个极小项都恰有一个成真赋值 每个极每个极大大项都恰有一个成项都恰有一个成假假赋值赋值任两个不同的小项的合取式为永假式任两个不同的小项的合取式为永假式.任两个不同的任两个不同的大大项的项的析析取式为永取式为永真真式式. 每个极小项都恰有一个成真赋值每个极小项都恰有一个成真赋值 每个极每个极大大项都恰有一个成项都恰有一个成假假赋值赋值 任两个不同的小项的合取式为永假式任两个不同的小项的合取式为永假式. 任两个不同的任两个不同的大大项的项的析析取式为永取式为永真真式式.mi mj 0, Mi Mj 1 (i j). 所有小所有小(大大)项的析项

10、的析(合合)取为永真取为永真(假假).m0 m1 . ms 1 (s = 2n 1),M0 M1 . Ms 0 (s = 2n 1).相同编码的小项与大项互为否定相同编码的小项与大项互为否定: mi Mi, Mi mi例如例如, m101 p1 p2 p3 M101101l主析取范式主析取范式: 由小项构成的析取式由小项构成的析取式12,siiiAmmm l主合取范式主合取范式: 由大项构成的合取式由大项构成的合取式12,siiiAMMM 0 ij 2n 1, j = 1, 2, , s.主范式主范式0 ij 2n 1, j = 1, 2, , s.主范式唯一存在定理主范式唯一存在定理 任何命

11、题公式都存在着与之等任何命题公式都存在着与之等值的主析取范式和主合取范式值的主析取范式和主合取范式, 并且是唯一的并且是唯一的.证证 每一命题公式每一命题公式 A 都有着与之等值的析取范式都有着与之等值的析取范式:A A1 A2 Ar.若某个若某个 Ai 不含第不含第 j 个变元的文字个变元的文字(pj 或或 pj), 则补上则补上Ai Ai 1 Ai (pj pj) (Ai pj) (Aj pj)式中重复出现的变元式中重复出现的变元, 小项和矛盾式都应小项和矛盾式都应“消去消去”:p p p, mi mi mi, p p B 0, B 0 B.继续此过程直到析取范式的每一项都恰含每一个变继续

12、此过程直到析取范式的每一项都恰含每一个变元的文字元的文字(即都成为小项即都成为小项), 即得主析取范式即得主析取范式.再证明唯一性再证明唯一性. 假设假设 A 存在两个主析取范式存在两个主析取范式 B 和和 C, 则则 B C. 假如假如 B 和和 C 含不同的小项含不同的小项, 例如小项例如小项 mi 只只出现在出现在 B 中而不出现在中而不出现在 C 中中, 则角标则角标 i 的二进制表示的二进制表示是是 B 的成真赋值的成真赋值, 但是但是 C 的成假赋值的成假赋值. 这与这与 B C 矛矛盾盾, 故故 B 与与 C 必含相同的小项必含相同的小项, 将小项按其角标顺序将小项按其角标顺序排

13、列排列(析取有交换律析取有交换律), 则所得表达式是唯一的则所得表达式是唯一的. 主合取范式的存在性和唯一性可类似证明主合取范式的存在性和唯一性可类似证明.定理的证明过程给出了求任一命题公式定理的证明过程给出了求任一命题公式 A 的主析取的主析取范式的步骤范式的步骤:1. 求出求出 A 的一个析取范式的一个析取范式:A A1 A2 Ar;2. 补进简单合取式补进简单合取式 Ai 中未出现的每个变元中未出现的每个变元:Ai Ai 1 Ai (p p);3. 消去矛盾式消去矛盾式, 合并重复出现的变元合并重复出现的变元, 小项小项:p p B 0, B 0 B, p p p, mi mi mi,

14、4. 将小项按角标顺序排列将小项按角标顺序排列.例例4 用等值演算法求用等值演算法求 A = (p q) q 的主析取范式和的主析取范式和主合取范式主合取范式.主析取范式主析取范式析取范式析取范式再求再求 A = (p q) q 的主合取范式的主合取范式.合取范式合取范式主合取范式主合取范式解解主析取范式的用途主析取范式的用途命题公式的主析取范式和真值表都明显地表示出命题公式的主析取范式和真值表都明显地表示出公式的常用特性公式的常用特性.(pq) r m1 m3 m4 m7,各极小项各极小项(含三个文字含三个文字)的角标的二进制数分别是的角标的二进制数分别是001, 011, 100, 111

15、(长为长为3), 这四个赋值是成真赋值这四个赋值是成真赋值, 其余其余的赋值的赋值, 即即000, 010, 101, 110, 为成假赋值为成假赋值.设公式设公式 A 中含中含 n 个命题变项个命题变项, 容易看出容易看出:(1) A 为重言式为重言式 A 的主析取范式含全部的主析取范式含全部 2n 个小项个小项.(2) A 为矛盾式为矛盾式 A 的主析取范式不含任何极小项的主析取范式不含任何极小项.规定矛盾式的主析取范式为规定矛盾式的主析取范式为 0.(3) A 为可满足式为可满足式 A 的主析取范式至少含一个小项的主析取范式至少含一个小项.主析取范式的用途主析取范式的用途例例6 用主析取

16、范式判断公式的类型用主析取范式判断公式的类型:(1) (pq) q; (2) p (p q); (3) (p q) r.解解 注意命题变项的数目注意命题变项的数目, 它决定它决定小项所含文字数目小项所含文字数目.(1) (p q) q ( p q) q (p q) q = 0,这是这是矛盾式矛盾式.(2) p (p q) p p q p ( q q) p ( q q) ( p p) q ( pq) ( p q) (pq) (p q) ( p q) (p q) ( pq) ( p q) (pq) (p q) m0 m1 m2 m3含全部小项含全部小项, 故为重言式故为重言式(事实上事实上演算到第

17、一步即知演算到第一步即知).(3) (p q) r (p q) r ( pq) r ( pq ( r r) ( p p) ( q q) r) ( pqr) ( pq r) ( p q r) (pq r) (p q r) m0 m1 m3 m5 m7.是非重言式的可满足式是非重言式的可满足式, 因主析取范式含有小项但没因主析取范式含有小项但没含全部含全部(8个个)极小项极小项.l等值的公式必有相同的主析取范式等值的公式必有相同的主析取范式, 反之亦然反之亦然.主析取范式的用途主析取范式的用途例例7 判断下面两组公式是否等值判断下面两组公式是否等值:(1) p 与与 (p q) (pq), (2)

18、 (pq) r 与与 (p q) r.解解 (1)注意命题变项的数目注意命题变项的数目! p p ( q q) (p q) (p q) m2 m3,而而 (p q) (p q) m2 m3.两者相同两者相同, 所以所以 p (p q) (p q).(2) 经演算得经演算得 (p q) r m1 m3 m4 m5 m7,和和 (p q) r m0 m1 m2 m3 m4 m5 m7所以所以 (pq) r(pq) r 例例8 现要从现要从 A, B, C 3 人中挑选人中挑选 12 人出差人出差, 满足满足: (1)若若 A 去去, 则则 C 同去同去.(2)若若 B 去去, 则则 C 不能去不能

19、去.(3)若若 C 不去不去, 则则 A 或或 B 可以去可以去.问应如何选派问应如何选派?主析取范式的用途主析取范式的用途解解设设 p: 派派 A 去去; q: 派派 B 去去; r: 派派 C 去去.选派方案应使条件的合取式选派方案应使条件的合取式 T = (pr) (q r) ( r (p q).为真为真. 为求为求 T 的成真赋值的成真赋值, 推出推出 T 的主析取范式的主析取范式:T pq r p qr pq r m1 m2 m5.T pq r p qr pq r m1 m2 m5. 成真赋值有成真赋值有 001, 010, 101, 分别对应选派方案分别对应选派方案: (a) C

20、去去, 而而 A, B 不去不去. (b) B 去去, 而而 A, C 不去不去. (c) A, C 去去, 而而 B 不去不去.公式公式 A 的主析取范式的主析取范式12,siiiAmmm 中出现的小项的角标中出现的小项的角标 ij (的二进制表示的二进制表示)是是 A 的成真的成真赋值赋值, 而未出现的角标而未出现的角标 kl 是成假赋值是成假赋值, 因而是因而是 A 的的成真赋值成真赋值. 从而从而 A 的主析取范式为的主析取范式为几点注意几点注意(0 ij 2n 1, j = 1, 2, , s)nskkkAmmm 122.但但nsnsnsjjjjjjjjjmmmmmmMMM 1221

21、22122().可见可见, 由公式的主析取范式可直接写出它的主合取范式由公式的主析取范式可直接写出它的主合取范式.A AnskkkAmmm 122.例例9 由公式的主析取范式由公式的主析取范式, 求主合取范式求主合取范式: (1) A m1 m2 (A 中含命题变项中含命题变项 p, q); (2) B m1 m2 m3 (B 中含命题变项中含命题变项 p, q, r).解解 (1)A M0 M3. (2) B M0 M4 M5 M6 M7. QEI由公式的主合取范式由公式的主合取范式, 也可立即写出主析取范式也可立即写出主析取范式.l矛盾式无成真赋值矛盾式无成真赋值, 因而矛盾式的主合取范式

22、含因而矛盾式的主合取范式含全部全部 2n (n 为公式中命题变项个数为公式中命题变项个数)个极大项个极大项.l而重言式无成假赋值而重言式无成假赋值, 因而其主合取范式不含任因而其主合取范式不含任何极大项何极大项. 将重言式的主合取范式记为将重言式的主合取范式记为 1.几点注意几点注意含含 n 个命题变项的合式公式有无穷多个个命题变项的合式公式有无穷多个, 而主而主(合合)吸吸取范式数目是有限的取范式数目是有限的.ln 个命题变项可产生个命题变项可产生 2n 个小个小(大大)项项, 因而共可产生因而共可产生几点注意几点注意01222222nnnnnCCC个不同的主个不同的主(合合)析取范式析取范

23、式.这个数目也是不同的真值表的数目这个数目也是不同的真值表的数目.l真值表与主真值表与主(合合)析取范式一一对应析取范式一一对应, 是命题公式的是命题公式的两种标准的表示形式两种标准的表示形式.2.1 等值式等值式2.2 析取范式与合取范式析取范式与合取范式2.3 联结词的完备集联结词的完备集22nl n 元真值函数共元真值函数共有有 个个.l 真值函数的自变量和函数值都取真值真值函数的自变量和函数值都取真值(0或或1).F(p1, p2, , pn)每个自变量有每个自变量有 2 个取值方式个取值方式, n 个自变量共有个自变量共有 2n 个个不同取值方式不同取值方式. 对自变量的每个取值方式对自变量的每个取值方式, 函数函数值有值有 2 个取值方式个取值方式( 0 或或 1), 故故一元真值函数有一元真值函数有 4 个个:二元真值函数有二元真值函数有 16