第一章命题逻辑总复习080913

1、离散数学-总复习（一）第一章 命题逻辑 1 命题命题：具有真假意义的陈述句。 2 原子命题：原子命题：不能再细分的命题。 3 复合命题：复合命题：可以通过一些命题联结词构成的新命题。 4 命题联结词命题联结词：否定词、合取词、析取词、蕴否定词、合取词、析取词、蕴涵词涵词和等价词等价词。 5 命题联结词的优先顺序：命题联结词的优先顺序：, ,1 否定词 （P2）设P表示命题，则P P不真不真 是另一命题，记为 P，读为 非非P P否定词可用右表定义，此表称为 P的真值真值表表. .P P0 1 102 合取词 若 P,Q 表示命题，则 P P并且并且Q Q 也是命题，记为 PQPQ , ,读读为

2、 P P合合取取Q Q. .PQ 的真值表如右表所示.由真值表可知 PQ PQ 真真, ,当且仅当当且仅当 P,Q P,Q 俱真俱真. .P QPQ0 00 11 01 100013 析取词 若 P,Q 表示命题，则 P P或者或者Q Q 也是命题，记为 PQPQ, ,读读为 P P析取析取Q Q。 PQ 的真值表如右表所示。由真值表可知 PQ PQ 为真为真, ,当且仅当当且仅当P,Q P,Q 至少至少有一个为真。有一个为真。P QPQ0 00 11 01 101114 蕴涵词 若 P,Q 表示命题，则 P P蕴涵蕴涵Q Q 也是命题，记为 PQ,读为 P P蕴蕴涵涵Q Q. PQ 的真值表

3、如右表所示。由真值表可知PQPQ为假为假, ,当且仅当当且仅当P P为为真而真而Q Q为假为假. . P QPQ0 00 11 01 111015 等值词 (p4) 若 P,Q 表示命题，则 P P等值于等值于Q Q 也是命题,记为 P PQ Q, , 读为 P P等值于等值于Q Q. P PQ Q 的真值表如右表所示. 由真值表可知 P PQ Q 为真为真, ,当且仅当当且仅当P P与与Q Q有相同的真有相同的真值值. .P QPQ0 00 11 01 11001命题符号化自然语言翻译为逻辑式 如果P，则Q。 PQPQ 只要P，就Q。 PQPQ 只有Q，才P。 PQPQ P仅当Q。 PQPQ

4、 除非P，否则Q。 PQPQ P当且仅当Q。 P PQ Q 虽然P，但是Q。 P PQ Q 一边P，一边Q。 P PQ Q P或Q 。 P PQ Q1.2 命题公式及分类（P6）真值表：真值表：在命题公式在命题公式A A中中, , 对于命题变元的每一组对于命题变元的每一组赋值和由它们所确定的命题公式赋值和由它们所确定的命题公式A A的真值列成表，的真值列成表，称做命题公式称做命题公式A A 的的真值表真值表。命题公式的分类命题公式的分类:判断公式类型的方法：判断公式类型的方法：真值表法、等值演算法、主真值表法、等值演算法、主析（合）取范式法。析（合）取范式法。证明公式等值的方法证明公式等值的方

5、法：真值表法、等值演算法、主析真值表法、等值演算法、主析( (合合) )取范式法。取范式法。)()()log(esatisfiablorycontradictytauto可满足式矛盾式重言式或永真式1.3 等值演算（P9） 重要的等价式重要的等价式: 1） 双重否定律双重否定律: : A A A A， 2） 等幂律等幂律: : A A A A A A， A A A A A A， 3） 交换律交换律: A A B BA A B B， A A B B A A B B， 4） 结合律结合律: :（A A B B） C C A A （B B C C），）， （A A B B） C C A A （B B

6、 C C），），1.3 等值演算（P9）5）分配律）分配律: :A A （B B C C）（A A B B） （A A C C），）， A A （B B C C）（A A B B） （A A C C），），6）德德摩根律摩根律: : （A A B B） A A BB， （A A B B） A A BB，7）吸收律吸收律: A A （A A B B）A A， A A （A A B B）A A，8）零律零律: : A A 1 1 1 1， A A 0 0 0 0，9）同一律同一律: : A A 0 0 A A， A A 1 1 A A，10）排中律排中律: : A A A A1 1， 11）矛盾律

7、矛盾律: : A A A A0 0，1.3 等值演算（P9）12） 蕴涵等值式蕴涵等值式: : A AB B A A B B，13） 等价等价等值式等值式: : A AB B (AB)(AB) (BA)(BA)，14） 假言易位假言易位: A AB B B B AA，15） 等价否定等价否定等值式等值式: : A AB B AABB，16） 归谬论归谬论: (A AB B ) ( ( A A B)B) AA。简单析取式：简单析取式：仅有有限个命题变项或其否定组仅有有限个命题变项或其否定组成的析取式。成的析取式。简单合取式：简单合取式：仅有有限个命题变项或其否定组仅有有限个命题变项或其否定组成的

8、合取式。成的合取式。性质性质:（1）一个简单析取式是重言式）一个简单析取式是重言式当且仅当它同当且仅当它同时含有某个命题变元及其否定式。时含有某个命题变元及其否定式。（2）一个简单合取式是矛盾式）一个简单合取式是矛盾式当且仅当它同当且仅当它同时含有某个命题变元及其否定式。时含有某个命题变元及其否定式。析取范式析取范式：简单合取式的析取式称为：简单合取式的析取式称为析取范式。析取范式。合取范式合取范式：简单析取式的合取式称为：简单析取式的合取式称为合取范式。合取范式。性质性质:v 一个析取范式是矛盾式一个析取范式是矛盾式,当且仅当它的每一个当且仅当它的每一个v 简单合取式都是矛盾式简单合取式都是

9、矛盾式;(2) 一个合取范式是重言式一个合取范式是重言式,当且仅当它的每一个当且仅当它的每一个简单析取式都是重言式。简单析取式都是重言式。 求求命题公式的命题公式的范式的基本步骤：范式的基本步骤：（1）将公式中的将公式中的联结词化归成联结词化归成, 及及 。（2）将否定将否定词词消去或内移到各命题变元之前。消去或内移到各命题变元之前。（3）利用分配律、结合律将公式转化为合取范式利用分配律、结合律将公式转化为合取范式或析取范式。或析取范式。 极极小项：小项：在含有在含有n个命题变元的简单合取式中个命题变元的简单合取式中,若若 每个命题变元或其否定出现且仅出现一次，称这每个命题变元或其否定出现且仅

10、出现一次，称这 样的简单合取式为样的简单合取式为极极小项。小项。 含有三个命题变元含有三个命题变元P,Q,RP,Q,R的极小项的极小项: : 极小项极小项 编码编码 真值指派真值指派 极小项的真值极小项的真值 P P QQ RR m m000/000/m m0 0 000000 1 1 PP QQ R mR m001/001/m m1 1 001 1 001 1 PP Q Q RR m m010/010/m m2 2 010 1 010 1 PP Q Q R R m m011/011/m m3 3 011 011 1 1 P P QQ R mR m100/100/m m4 4 100 1 10

11、0 1 P P QQ R R m m101/101/m m5 5 101 1 101 1 P P Q Q RR m m110/110/m m6 6 110 1 110 1 P P Q Q R R m m111/111/m m7 7 111 1 111 1极小项的性质极小项的性质:没有两个极小项是等价的没有两个极小项是等价的, 且每个极小项有且仅且每个极小项有且仅有一个成真赋值，若成真赋值所对应的二进制有一个成真赋值，若成真赋值所对应的二进制数转数转化为十进制数为化为十进制数为i,就将所对应的极小项记作就将所对应的极小项记作mi。(2) 任意两个不同的极小项的合取为矛盾式。任意两个不同的极小项的

12、合取为矛盾式。(3) 全体极小项的析取为永真式。全体极小项的析取为永真式。主析取范式主析取范式：A的析取范式中，所有的简单合取的析取范式中，所有的简单合取式式都是极小项，则称该析取范式为都是极小项，则称该析取范式为A的主析取范式的主析取范式。(1) （真值表法、等值演算法）（真值表法、等值演算法） 真值表法：真值表法：在命题公式在命题公式A的真值表中的真值表中,真值为真值为1的的指派对应的极小项的析取称为指派对应的极小项的析取称为A的主析取范式。的主析取范式。等值演算法等值演算法:(1) 将将A化为析取范式化为析取范式 ;(2) 除去除去 中所有永假的析取项中所有永假的析取项;(3) 将将 中

13、重复出现的简单合取式和相同变元都消去中重复出现的简单合取式和相同变元都消去 ;(4) 若若 中某简单合取式中某简单合取式B中不含命题变元中不含命题变元P Pi i, 添加添加( (P Pi i PPi i), 然后应用分配律展开。然后应用分配律展开。 即即 B B B 1 1B B (P(Pi i PPi i) (B(B P Pi i) ) ( (B B PPi i) )。AAAA极极大项：大项：在含有在含有n个命题变元的简单析取式中个命题变元的简单析取式中,若每个命若每个命题变元或其否定出现且仅出现一次，称这样的简单析题变元或其否定出现且仅出现一次，称这样的简单析取式为取式为极极大项。大项。

14、 含有三个命题变元含有三个命题变元P,Q,RP,Q,R的极大项的极大项: : 极大项极大项 编码编码 真值指派真值指派 极大项的真值极大项的真值 P P Q Q R R M M000/000/M M0 0 000000 0 0 P P Q Q R MR M001/001/M M1 1 001 001 0 0 P P QQ R MR M010/010/M M2 2 010 010 0 0 P P QQ R MR M011/011/M M3 3 011 011 0 0 P P Q Q R MR M100/100/M M4 4 100 100 0 0 P P Q Q R R M M101/101/M

15、 M5 5 101 101 0 0 P P QQ R R M M110/110/M M6 6 110 110 0 0 P P QQ RR M M111/111/M M7 7 111 0 111 0极大项的性质极大项的性质:没有两个极大项是等价的没有两个极大项是等价的, 且每个极大项有且仅且每个极大项有且仅有一个成假赋值，若成假赋值所对应的二进制数有一个成假赋值，若成假赋值所对应的二进制数转转化为十进制数为化为十进制数为i，就将所对应的极大项记作就将所对应的极大项记作Mi。(2) 任意两个不同的极大项的析取为永真式。任意两个不同的极大项的析取为永真式。(3) 全体极大项的合取为矛盾式。全体极大项

16、的合取为矛盾式。主合取范式主合取范式：A的合取范式中，所有的简单析取的合取范式中，所有的简单析取式式都是极大项，则称该合取范式为都是极大项，则称该合取范式为A的主合取范式的主合取范式。(1) （真值表法、等值演算法）（真值表法、等值演算法）真值表法：真值表法：在命题公式在命题公式A的真值表中的真值表中,真值为真值为0的的指派对应的极大项的合取称为指派对应的极大项的合取称为A的主合取范式。的主合取范式。等值演算法等值演算法:(1) 将将A化为合取范式化为合取范式 ;(2) 除去除去 中所有永真的合取项中所有永真的合取项;(3) 将将 中重复出现的简单析取式和相同变元都消去中重复出现的简单析取式和

17、相同变元都消去;(4) 若若 中某简单析取式中某简单析取式B中不含命题变元中不含命题变元P Pi i, 添加添加( (P Pi i PPi i), 然后应用分配律展开，然后应用分配律展开， 即即 B B B 0 0B B (P(Pi i PPi i) (B(B P Pi i) ) ( (B B PPi i) )。AAAA 主析主析(合合)取范式的应用取范式的应用： 设公式设公式A中含有中含有n个命题变元，则个命题变元，则（1）A为重言式为重言式A的的主析取范式主析取范式含全部含全部2n个极个极小小项。项。（2）A为矛盾式为矛盾式A的的主析取范式主析取范式不含任何极小项，记不含任何极小项，记 A

18、的主析取范式为的主析取范式为0。（3）A为可满足式为可满足式A的的主析取范式主析取范式至少含一个极小项。至少含一个极小项。（4）A为矛盾式为矛盾式A的的主合取范式主合取范式含全部含全部2n个极大项。个极大项。（5）A为重言式为重言式A的的主合取范式主合取范式不含任何极大项，记不含任何极大项，记 A的主合取范式为的主合取范式为1 。（6）A为可满足式为可满足式A的的主合取范式主合取范式中极大项的个数一中极大项的个数一 定小于定小于2n 。 证明证明C是是A的有效结论的最常用的方法有三的有效结论的最常用的方法有三种：种： 间接证法直接证法真值表法附加前提证明法归谬法1)真值表法真值表法 :构造命题公式构造命题公式H1 H2 Hn C的的真值表，若为永真，则真值表，若为永真，则H1 H2 Hn C 推理推理正确。正确。2)直接证法直接证法 ：由一组前提，利用一些公认的由一组前提，利用一些公认的推理规则推理规则，根据已知的等价或蕴含公式推演得到有效结论。，根据已知的等价或蕴含公式推演得到有效结论。常用的推理规则：常用的推理规则：P规则规则:（也称前提引入规则