离散数学0343728

1、第一章第一章 命题逻辑命题逻辑 知识点：知识点： 1 1、命题的符号化；、命题的符号化； 2 2、合式公式；、合式公式； 3 3、公式的分类及永真公式；、公式的分类及永真公式； 4 4、合式公式的范式；、合式公式的范式； 5 5、命题逻辑的推理理论。、命题逻辑的推理理论。 1.4 范范 式式 文字的含义：文字的含义： 命题变元和命题变元的否定称为命题变元和命题变元的否定称为文字，文字，并称并称 命题变元为命题变元为正文字，正文字，命题变元的否定为命题变元的否定为反文字。反文字。 例如：例如：RRQPP、等都是文字等都是文字。 一、合取范式一、合取范式 1、基本和、基本和 （1）基本和的定义）基

2、本和的定义： BA 基本和的归纳定义是：基本和的归纳定义是： 文字是基本和；文字是基本和； 若若 A, B 是基本和，则是基本和，则 也是基本和。也是基本和。 例如：例如： RQP PPRPQPRQPP 、 等都是基本和。等都是基本和。 基本和的一般形式为：基本和的一般形式为：, 2 2 1 1 m m b i b i b i PPP )1 (,1mjbni jj 其中，其中， 为为 0 0 或或 1 1。 定理定理1.4.1 i P 一个基本和是永真式，当且仅当它同时含一个基本和是永真式，当且仅当它同时含 )1 (niP i 有某命题变元有某命题变元 及其否定及其否定 。 （3）基本和的性质

3、）基本和的性质： （2）基本和的一般形式）基本和的一般形式： BA 合取范式的归纳定义如下：合取范式的归纳定义如下： 基本和是合取范式；基本和是合取范式； 若若 A 和和 B 是合取范式，则是合取范式，则 也是合取也是合取 范式。范式。 例如：例如： （1）合取范式的定义）合取范式的定义： （定义（定义1.4.3） )()(PPRPQPQPP、 等都是合取范式。等都是合取范式。 从上面的定义和例子可以看出：从上面的定义和例子可以看出：合取范式是合取范式是和和 之积之积的形式。的形式。 2、合取范式、合取范式 BA 设设 B 是合取范式，是合取范式，A 是合式公式。若是合式公式。若 ， 则称则称

4、 B 是是 A 的的合取范式合取范式。 （2）合取范式的恒等定义）合取范式的恒等定义： （定义（定义1.4.4） （3）合取范式的计算）合取范式的计算： 消去联结词消去联结词 ；（；（E14、E15） 将否定词将否定词 移至命题变元前，并消去双移至命题变元前，并消去双 重否定；（重否定；（E10、E11、E1） 利用分配律、结合律将公式化为合取范式。利用分配律、结合律将公式化为合取范式。 （E6 E9） 和 例例1.4.1 求求)()(RQQP 解解 的合取范式。的合取范式。 ()() ()() ()() ()() ()() ( ()() () () ()() PQQR PQQR PQQR Q

5、RPQ PQQR QRPQ PQQR QRPQ PQRQPR 蕴含等值式蕴含等值式E14 等价等值式等价等值式E15 蕴含等值式蕴含等值式E14 双重否定律双重否定律E1 德德.摩根定律摩根定律E10 分配律分配律E8 例例 ()PQRPQPR ()() ()()()() PQPPQR PPQPPRQR 可见：合取范式的表达式可见：合取范式的表达式不唯一不唯一。 n b n bb PPP 21 21 n 个命题变元个命题变元P1，P2，Pn的最大项是的最大项是 （其中（其中 bi 取取 0 或或 1）。）。 （1）最大项的定义）最大项的定义： （定义（定义1.4.5） 可见：可见： 在最大项中

6、，都会出现在最大项中，都会出现 ，且只出，且只出 现一次。现一次。 n 个命题变元最多可以构成个命题变元最多可以构成 2n 个不同的最个不同的最 大项。大项。 3、主合取范式、主合取范式 ii PP或 n b n bb PPP 21 21 对于最大项对于最大项 记该最大项为记该最大项为 。 最大项为假的概念最大项为假的概念： n bbb M 21 有且仅有一有且仅有一 个解释使其为假，即个解释使其为假，即 n bbbI 21 (其中其中 ) ii bb1 （2）主合取范式的定义）主合取范式的定义： （定义（定义1.4.6） BA 主合取范式主合取范式的归纳定义是：的归纳定义是： 最大项是主合取

7、范式；最大项是主合取范式； 若若 A 和和 B 是主合取范式，则是主合取范式，则 也是主也是主 合取范式。合取范式。 BA 设设 B 是主合取范式，是主合取范式，A 是合式公式。是合式公式。 若若 ，则称，则称 B 是是 A 的的主合取范式主合取范式。 （3）主合取范式的恒等定义）主合取范式的恒等定义： （定义（定义1.4.7） 逻辑恒等变换方法的求解步骤：逻辑恒等变换方法的求解步骤： 先求合取范式；先求合取范式； 去掉合取范式中永真的基本和；去掉合取范式中永真的基本和； 合并相同的文字和基本和；合并相同的文字和基本和； 对基本和中对基本和中补入未出现的命题变元补入未出现的命题变元，然后，然后

8、 展开公式，化简直至得到主合取范式。展开公式，化简直至得到主合取范式。 求主合取范式可用两种方法，即：求主合取范式可用两种方法，即：逻辑恒等变换逻辑恒等变换 的方法和的方法和真值表真值表的方法。的方法。 （4）主合取范式的计算）主合取范式的计算： 例例1.4.2 求求)()(RPQP的主合取范式。的主合取范式。 450 ()() ()()()() ()()() ()() () ()()() ()()() ()()() () PQPPQR PPQPPRQR PQPRQR PQRRPRQQ QRPP PQRPQRPRQ PRQQRPQRP PQRPQRPQR PQR MMM 2 0, 2, 4,5

9、M 原式 补项补项 例例1.4.3 用真值表的方法求解例用真值表的方法求解例1.4.2。 PQRPQPPR(PQ)(PR) 0 00 00 00 01 10 00 0 0 00 01 10 01 11 11 1 0 01 10 00 01 10 00 0 0 01 11 10 01 11 11 1 1 10 00 00 00 00 00 0 1 10 01 10 00 00 00 0 1 11 10 01 10 00 01 1 1 11 11 11 10 00 01 1 0245 ()() ()() 0, 2, 4,5 PQRPQR PQRPQR MMMM 原式原式 例例1.4.4 通过求主合

10、取范式，证明：通过求主合取范式，证明： )()(RPQRQP 二、析取范式二、析取范式 1、基本积、基本积 （1）基本积的定义）基本积的定义： BA 基本积的归纳定义是：基本积的归纳定义是： 文字是基本积；文字是基本积； 若若 A, B 是基本积，则是基本积，则 也是基本积。也是基本积。 例如：例如： RQP PPRPQPRQPP 、 等都是基本积。等都是基本积。 基本积的一般形式为：基本积的一般形式为：, 2 2 1 1 m m b i b i b i PPP )1 (,1mjbni jj 其中，其中， 为为 0 0 或或 1 1。 定理定理1.4.2 一个基本积是永假式，当且仅当它同时一个

11、基本积是永假式，当且仅当它同时 含有某一命题变元及其否定。含有某一命题变元及其否定。 （3）基本积的性质）基本积的性质： （2）基本积的一般形式）基本积的一般形式： BA 析取范式析取范式的归纳定义如下：的归纳定义如下： 基本积是析取范式；基本积是析取范式； 若若 A 和和 B 是析取范式，则是析取范式，则 也是析取也是析取 范式。范式。 例如：例如： （1）析取范式的定义）析取范式的定义： （定义（定义1.4.9） )()(PPRPQPQPP、 等都是析取范式。等都是析取范式。 从上面的定义和例子可以看出：从上面的定义和例子可以看出：析取范式是析取范式是积积 之和之和的形式。的形式。 2、析

12、取范式、析取范式 BA 设设 B 是析取范式，是析取范式，A 是合式公式。若是合式公式。若 ， 则称则称 B 是是 A 的的析取范式析取范式。 （2）析取范式的恒等定义）析取范式的恒等定义： （定义（定义1.4.10） （3）析取范式的计算）析取范式的计算： 消去联结词消去联结词 ；（；（E14、E15） 将否定词将否定词 移至命题变元前，并消去双移至命题变元前，并消去双 重否定；（重否定；（E10、E11，E1） 利用分配律、结合律将公式化为析取范式。利用分配律、结合律将公式化为析取范式。 （E6 E9） 和 例例1.4.5 求求)()(RQQP的析取范式。的析取范式。 解解()() ()(

13、) ()()()() ()()()() () () PQQR PQQR PQQRPQQR PQQRPQQR PQQPQR PQRQQR PQRPQR 例例 () ()() PQPQRR PQRQR 可见：析取范式的表达式也可见：析取范式的表达式也不唯一不唯一。 n b n bb PPP 21 21 n 个命题变元个命题变元P1，P2，Pn的最小项是的最小项是 （其中（其中 bi 取取 0 或或 1）。）。 （1）最小项的定义）最小项的定义： （定义（定义1.4.11） 可见：可见： 在最小项中，都会出现在最小项中，都会出现 ，且只出现，且只出现 一次。一次。 n 个命题变元最多可以构成个命题变

14、元最多可以构成 2n 个不同的最个不同的最 小项。小项。 ii PP或 3、主析取范式、主析取范式 n b n bb PPP 21 21 对于最小项对于最小项 ，记该最小项，记该最小项 最小项为真的概念最小项为真的概念： n bbb m 21 有且仅有一有且仅有一 个解释使其为真，即个解释使其为真，即 n bbbI 21 为为 定义定义1.4.12 BA 主析取范式主析取范式的归纳定义是：的归纳定义是： 最小项是主析取范式；最小项是主析取范式； 若若 A 和和 B 是主析取范式，则是主析取范式，则 也是主也是主 析取范式。析取范式。 （2）主析取范式的定义）主析取范式的定义： BA 设设 B

15、是主析取范式，是主析取范式，A 是合式公式。是合式公式。 若若 ，则称，则称 B 是是 A 的的主析取范式主析取范式。 定义定义1.4.13 （3）主析取范式的恒等定义）主析取范式的恒等定义： 求主析取范式也有两种方法：求主析取范式也有两种方法：逻辑恒等变换逻辑恒等变换的方的方 法和法和真值表真值表的方法。的方法。 主析取范式的求解步骤主析取范式的求解步骤： 先求析取范式；先求析取范式； 去掉析取范式中永假的基本积；去掉析取范式中永假的基本积； 合并相同的文字和基本积；合并相同的文字和基本积； 对基本积中对基本积中补入未出现的命题变元补入未出现的命题变元，然后，然后 展开公式，化简直至得到主析

16、取范式。展开公式，化简直至得到主析取范式。 （4）主析取范式的计算）主析取范式的计算： 例例1.4.6 求求)()(RPQP的主析取范式。的主析取范式。 7631 ()() ()() ()() 1,3, 6, 7 PQRRPRQQ PQRPQR PQRPQR mmmm 原式原式 例例1.4.7 用真值表的方法求解例用真值表的方法求解例1.4.6。 PQRPQPPR(PQ)(PR) 0 00 00 00 01 10 00 0 0 00 01 10 01 11 11 1 0 01 10 00 01 10 00 0 0 01 11 10 01 11 11 1 1 10 00 00 00 00 00

17、0 1 10 01 10 00 00 00 0 1 11 10 01 10 00 01 1 1 11 11 11 10 00 01 1 1367 ()() ()() 1,3, 6, 7 PQRPQR PQRPQR mmmm 原式原式 三、主范式之间的关系三、主范式之间的关系 1、最大项与最小项之间的关系、最大项与最小项之间的关系 含有含有 n 个命题变元的最大项和最小项之间存在下个命题变元的最大项和最小项之间存在下 列关系：列关系： FMMm TmjiTMM mMjiFmm i i ii i i ji iiji n n 12 0 12 0 )6(;) 3( ;)5();()2( ;)4();() 1 ( 若 若 2、主范式、主范式之间的关系之间的关系 若已知公式若已知公式 A 的主析取范式为的主析取范式为 则它的主合取范式为则它的主合取范式为 tpiiii n pt 1 ,12 , 1, 0),( 21 其中， sp iiijjjj t n ps 1 ,12 , 1, 0),( 2121 其中，