计算机数学基础上-离散数学课件

1.2 命题公式与赋值真值指派定义：命题公式与赋值，命题P含有n个命题变项P1，P2,…,Pn，给P1，P2,…,Pn各指定一个真值0或1，称为对P的一个赋值(真值指派).若指定的一组值使P的值为1，则这组值为P的真指派；若使P的值为0，则称这组值称为P的假指派.真值表：一个公式P在所有赋值下取值情况列成的表1.2 命题公式与赋值真值指派1构造真值表的步骤(1)将变元按一定顺序排出，再按从内到外的顺序列出公式的各个运算层次，将它们排在表头上；(2)如有n个变元，则所有可能的赋值有2n组，每组可用n位的二进制数表示，按字典顺序每行排一组(3)在表上由左到右填写相应的真值。构造真值表的步骤(1)将变元按一定顺序排出，再按从内到外的21.2 命题公式与赋值构造命题公式的真值表例子：P12课堂练习：用真值表判定公式PQ与PQ是否等值

1.2 命题公式与赋值构造命题公式的真值表31.2 命题公式与赋值命题公式的分类重言式或永真式矛盾式或永假式可满足式仅可满足式1.2 命题公式与赋值命题公式的分类4重言式或永真式：矛盾式或永假式：命题公式A在各种赋值下取值均为假。可满足式：命题公式A至少存在一组赋值为成真赋值。仅可满足式：既不是矛盾式也不是重言式若A在各种赋值下取值恒为真,则A为重言式。设A是一个命题公式，命题公式的类型重言式或永真式：矛盾式或永假式：命题公式A在各种赋值下取值均51.3命题定理基本等值式：也称为命题定律或命题定理，一共16组25个，见书P16（熟记）1.3命题定理基本等值式：也称为命题定律或命题定理，一共16常用的重要等值公式表：1、AA双重否定律2、AAA3、AAA等幂律4、ABBA5、AB

BA交换律常用的重要等值公式表：1、AA双重否定律2、AA76、(AB)

C7、(AB)C

结合律8、A(B

C)9、A(B

C

)

分配律10、(AB)11、(AB)德·摩根律A(BC)A(BC)(AB)(AC)(AB)(AC)A

B

AB6、(AB)C7、(AB)C结合律8、A(812、A(AB)A13、A(AB)A吸收律*14、A1115、A00零律16、A0A17、A1

A同一律12、A(AB)A13、A(AB)919、

A

A0矛盾律20、

AB

AB

蕴涵等值式*假言易位等价否定等值式归谬论*21、

AB(AB)(BA)等价等值式22、

ABB

A23、

ABB

A24、(AB)(AB)

A18、

A

A1排中律19、AA0矛盾律20、ABAB10以上24个等值式必须熟记，并注意其中所含的A、B、C可以是任意的一个命题公式，因而每个公式是一个模式，可以代表无数多个同类型的命题公式。利用24个基本等值式，不用真值表法也可以推演很多的等值式来。以上24个等值式必须熟记，并注意其中所含的A、B、C可以是任11置换定理：(A)是含命题公式A的命题公式,(B)是用B置换了(A)中的A之后得到的命题公式。如果AB,则(A)(B)置换定理：(A)是含命题公式A的命题公式,(B)是用12判断两个公式是否等值：判断AB是否为重言式等值演算法:可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。判断两个公式是否等值：131.3命题定理判定命题公式类型的方法：真值表法:对于任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.推导法:

利用基本等值式(双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.1.3命题定理判定命题公式类型的方法：14例利用等值演算证明下列等值公式(2)P(PQ)(PQ)解题思想可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。(1)P(QR)(PQ)R例利用等值演算证明下列等值公式(2)P(P15解：(1)P

(Q

R)¬

P

(Q

R)¬

P(¬Q

R)(¬

P¬

Q)R

¬(P

Q

)R(P

Q)

R)蕴涵等值公式蕴涵等值公式结合律德·摩根律蕴涵等值公式(1)P(QR)(PQ)R解：(1)P(QR)¬P(Q16解：(2)PP

1P

(Q

¬

Q)(P

Q)(P

¬

Q)同一律排中律分配律(2)P(PQ)(PQ)解：(2)PP1P(Q¬Q)17例判别下列公式的类型(1)Q

¬((¬

PQ)

P)(2)(P

¬

P)((Q

¬

Q)

R)(3)(PQ)¬

P解题分析真值表法可以判别公式类型(重言、永假、可满足)，但等值演算的方法更简捷。例判别下列公式的类型(1)Q¬((¬18解：(1)Q

¬((¬

PQ)

P)Q

¬(Q

P)分配律矛盾律同一律(1)Q

¬((¬

PQ)

P)Q

(¬

Q

¬

P)德·摩根律结合律排中律Q¬((¬

P

P)(Q

P))Q¬(0(Q

P))1¬

P(Q¬

Q)¬

P解：(1)Q¬((¬PQ)P)Q19故(1)是重言式1零律故(1)是重言式1零律20¬1000010(？)(？)(？)(？)(？)(？)(3)类似(1),(2)可知：(PQ)¬

P¬P(自己做做)(2)(P

¬

P)((Q

¬

Q)

R)解：(2)(P

¬

P)((Q

¬

Q)

R)1((Q

¬Q)

R)1(0

R)¬1000010(？)211.2 命题公式与赋值真值指派定义：命题公式与赋值，命题P含有n个命题变项P1，P2,…,Pn，给P1，P2,…,Pn各指定一个真值0或1，称为对P的一个赋值(真值指派).若指定的一组值使P的值为1，则这组值为P的真指派；若使P的值为0，则称这组值称为P的假指派.真值表：一个公式P在所有赋值下取值情况列成的表1.2 命题公式与赋值真值指派22构造真值表的步骤(1)将变元按一定顺序排出，再按从内到外的顺序列出公式的各个运算层次，将它们排在表头上；(2)如有n个变元，则所有可能的赋值有2n组，每组可用n位的二进制数表示，按字典顺序每行排一组(3)在表上由左到右填写相应的真值。构造真值表的步骤(1)将变元按一定顺序排出，再按从内到外的231.2 命题公式与赋值构造命题公式的真值表例子：P12课堂练习：用真值表判定公式PQ与PQ是否等值

1.2 命题公式与赋值构造命题公式的真值表241.2 命题公式与赋值命题公式的分类重言式或永真式矛盾式或永假式可满足式仅可满足式1.2 命题公式与赋值命题公式的分类25重言式或永真式：矛盾式或永假式：命题公式A在各种赋值下取值均为假。可满足式：命题公式A至少存在一组赋值为成真赋值。仅可满足式：既不是矛盾式也不是重言式若A在各种赋值下取值恒为真,则A为重言式。设A是一个命题公式，命题公式的类型重言式或永真式：矛盾式或永假式：命题公式A在各种赋值下取值均261.3命题定理基本等值式：也称为命题定律或命题定理，一共16组25个，见书P16（熟记）1.3命题定理基本等值式：也称为命题定律或命题定理，一共127常用的重要等值公式表：1、AA双重否定律2、AAA3、AAA等幂律4、ABBA5、AB

BA交换律常用的重要等值公式表：1、AA双重否定律2、AA286、(AB)

C7、(AB)C

结合律8、A(B

C)9、A(B

C

)

分配律10、(AB)11、(AB)德·摩根律A(BC)A(BC)(AB)(AC)(AB)(AC)A

B

AB6、(AB)C7、(AB)C结合律8、A(2912、A(AB)A13、A(AB)A吸收律*14、A1115、A00零律16、A0A17、A1

A同一律12、A(AB)A13、A(AB)3019、

A

A0矛盾律20、

AB

AB

蕴涵等值式*假言易位等价否定等值式归谬论*21、

AB(AB)(BA)等价等值式22、

ABB

A23、

ABB

A24、(AB)(AB)

A18、

A

A1排中律19、AA0矛盾律20、ABAB31以上24个等值式必须熟记，并注意其中所含的A、B、C可以是任意的一个命题公式，因而每个公式是一个模式，可以代表无数多个同类型的命题公式。利用24个基本等值式，不用真值表法也可以推演很多的等值式来。以上24个等值式必须熟记，并注意其中所含的A、B、C可以是任32置换定理：(A)是含命题公式A的命题公式,(B)是用B置换了(A)中的A之后得到的命题公式。如果AB,则(A)(B)置换定理：(A)是含命题公式A的命题公式,(B)是用33判断两个公式是否等值：判断AB是否为重言式等值演算法:可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。判断两个公式是否等值：341.3命题定理判定命题公式类型的方法：真值表法:对于任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.推导法:

利用基本等值式(双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.1.3命题定理判定命题公式类型的方法：35例利用等值演算证明下列等值公式(2)P(PQ)(PQ)解题思想可以从左或右的任一个公式开始演算；演算的每一步都要用置换定理。(1)P(QR)(PQ)R例利用等值演算证明下列等值公式(2)P(P36解：(1)P

(Q

R)¬

P

(Q

R)¬

P(¬Q

R)(¬

P¬

Q)R

¬(P

Q

)R(P

Q)

R)蕴涵等值公式蕴涵等值公式结合律德·摩根律蕴涵等值公式(1)P(QR)(PQ)R解：(1)P(QR)¬P(Q37解：(2)PP

1P

(Q

¬

Q)(P

Q)(P

¬

Q)同一律排中律分配律(2)P(PQ)(PQ)解：(2)PP1P(Q¬Q)38例判别下列公式的类型(1)Q

¬((¬

PQ)

P)(2)(P

¬

P)((Q

¬

Q)

R)(3)(P