离散数学(第二章)

1、离散数学许雷（数学与信息科学学院）邮箱：）电话：180802219261.3 命题公式的等值式定义定义1: 给定两个命题公式给定两个命题公式A和和B，设，设P1 ,P2 ,Pn为出现于为出现于A和和B中的所有原子变元中的所有原子变元,若给若给P1 , P2 ,Pn任一组真值指派任一组真值指派, A和和B的真值的真值都相同都相同,则称则称A和和B是等价的或逻辑相等是等价的或逻辑相等.记作记作A B。1.3 命题公式的等值式注注: (1) “ ”不是逻辑联结词不是逻辑联结词.(2)命题公式之间的逻辑相等关系具有命题公式之间的逻辑相等关系具有： 自反性：自反性：A A ； 对称性：若对称性：若A B

2、，则，则B A； 传递性：若传递性：若A B且且B C，则，则A C。1.3 命题公式的等值式证明公式等价的方法：证明公式等价的方法：1. 真值表法真值表法 2. 等值演算法等值演算法1. 真值表法真值表法 例例1.1.111 1111 0110 1110 0 Q QPPP Q 1.3 命题公式的等值式例例2. 证明证明: PQ (PQ) (QP)PQ PQ QP PQ (PQ) (QP)0 00 00 01 11 10 01 11 11.3 命题公式的等值式例例2. 证明证明: PQ (PQ) (QP)PQ PQ QP PQ (PQ) (QP)0 00 01 11 11 11 10 01 1

3、0 00 01 10 01 10 00 01 10 00 01 11 11 11 11 11 11.3 命题公式的等值式例例3：判断公式判断公式 P(QR)、(PQ)R是否等价是否等价P Q RPQQRP(QR)(PQ)R00001001010100001101100011010111010111111.3 命题公式的等值式P Q RPQQRP(QR)(PQ)R00001110010111010001101101111000111101011111010001111111例例3：判断公式判断公式 P(QR)、(PQ)R是否等价是否等价1.3 命题公式的等值式2. 等值演算法等值演算法(Equi

4、valent Calculation) 等值演算中使用的一条重要规则：等值演算中使用的一条重要规则：置换规则置换规则定义定义2 (子公式子公式)：如果如果X是是wff A的一部分的一部分,且且X本身也是本身也是wff，则称，则称X是是A的子公式。例如的子公式。例如, P (P Q)为为Q (P (P Q)的子公式。的子公式。1.3 命题公式的等值式(置换定理置换定理Axiom of rePlacement) 设设X是是wff A的子的子wff，若，若XY，则若将，则若将A中的中的X用用Y来置换，所得公式来置换，所得公式B与与A等价，即等价，即AB。证：证：因为对变元的任一指派因为对变元的任一指

5、派,X与与Y真值相同，真值相同，所以所以Y取代取代X后，公式后，公式B与公式与公式A对变元的任对变元的任一指派真值也相同一指派真值也相同,所以所以AB。1.3 命题公式的等值式注注: : 满足满足置换定理置换定理的条件的置换称为等价置的条件的置换称为等价置 换换(或等价代换或等价代换).定义定义2( (等值演算等值演算) )：根据已知的等价公式根据已知的等价公式, ,推演出另外一些等价公式的过程称为推演出另外一些等价公式的过程称为等值演等值演算算.1.3 命题公式的等值式v常用的等价式：常用的等价式： 1.双重否定律双重否定律： P P 2.结合律：结合律：(P Q) RP (Q R) (P

6、Q) RP (Q R) (PQ)RP(QR) 3.交换律交换律: P QQ P P Q Q P PQ QP 4. 分配律分配律: P (Q R )(P Q) (P R) P (Q R)(P Q) (P R)1.3 命题公式的等值式v常用的等价式：常用的等价式： 5.幂等律幂等律: : P P P P P P 6.吸收律吸收律: P (P Q) P P (P Q) P 7.德德.摩根律摩根律: (P Q)P Q (P Q)P Q 8.同一律同一律: P 0P P 1P 9.零律零律: P 11 P 001.3 命题公式的等值式v常用的等价式：常用的等价式： 10.否定律否定律： P P1 P P

7、0 11. 蕴涵等值式蕴涵等值式: : PQ P Q 12. 等价等值式等价等值式: PQ(PQ) (QP) 13. 假言易位假言易位: PQQ P 14. 等价否定等值式等价否定等值式: PQPQ 15. 归谬论归谬论: (PQ ) ( PQ)P 1.3 命题公式的等值式其中其中P, Q, R等代表任意命题公式等代表任意命题公式. 这样上面的这样上面的每一个公式都是一个模式每一个公式都是一个模式, 它可以代表无数多它可以代表无数多个同类型的命题公式个同类型的命题公式. 例如例如, P P1 中中, 用用(P Q)置换置换P,则得则得 (P Q) (P Q)1 ,用用P置换置换P,则得则得 (

8、P) (P)1 。1.3 命题公式的等值式例例1 1： 证明证明 Q(P (P Q)QP证证: Q(P (P Q) QP P(吸收律吸收律)例例2： 证明证明 (P Q) QP Q证：证：(P Q) Q(P Q) (Q Q)(P Q) T P Q1.3 命题公式的等值式例例3：证明：证明(PQ)(Q R) P Q R证：证：(PQ)(Q R) (P Q)(Q R) (P Q) (Q R) (P Q) (Q R) (P Q R) (Q Q R) P Q R 1.3 命题公式的等值式例例4：验证验证P(QR) (PQ)R证证: 右右(PQ)R PQR P(QR) P(QR) P(QR)练：练：1.

9、(PQ)(PR)P(QR) 2.(PQ)(PQ)(PQ)(PQ) 1.3 命题公式的等值式等值演算的应用：等值演算的应用： 1.验证等值式验证等值式 2.判定公式的类型（判定公式的类型（p23,例例2.5） 3.解决工作生活中的判断问题解决工作生活中的判断问题例例5：甲、已、丙甲、已、丙3人根据口音对王教授是哪人人根据口音对王教授是哪人进行了判断：进行了判断： 甲说：王教授不是苏州人，是上海人甲说：王教授不是苏州人，是上海人 已说：王教授不是上海人，是苏州人已说：王教授不是上海人，是苏州人 丙说：王教授既不是上海人，也不是杭州人丙说：王教授既不是上海人，也不是杭州人结果结果3人中有一人全对，一

10、人对一半，一人全错。人中有一人全对，一人对一半，一人全错。问王教授是哪人？问王教授是哪人？1.4 析取范式与合取范式定义定义1: (1)文字文字：命题变元及其否定统称为文字：命题变元及其否定统称为文字(如如P , P). (2)简单析取式简单析取式：仅有有限个文字组成的析取式。：仅有有限个文字组成的析取式。 如如:P，P Q，P P，Q P P，P Q R S.(3)简单合取式简单合取式：仅有有限个文字组成的合取式。：仅有有限个文字组成的合取式。 如如:P, Q , Q P，P P，Q P P, P Q R.注意：注意：单个文字既是简单析取式又是简单合取式单个文字既是简单析取式又是简单合取式从

11、定义不难看出从定义不难看出:定理定理1：（1）一个简单析取式是）一个简单析取式是重言式重言式当且仅当它同当且仅当它同时含有某个时含有某个命题变元及其否定式命题变元及其否定式。（2）一个简单合取式是）一个简单合取式是矛盾式矛盾式当且仅当它同当且仅当它同时含有某个时含有某个命题变元及其否定式命题变元及其否定式。1.4 析取范式与合取范式 定义定义2: (1)析取范式析取范式：一个命题公式称为：一个命题公式称为析取范式析取范式,当且当且仅当它具有形式仅当它具有形式: A1A2An (n大于等于1)其中其中Ai(i=1,2,3,n)为简单合取式为简单合取式.如：如：PQ ，(PQ)(PQR), QP.

12、 (2)合取范式合取范式：一个命题公式称为：一个命题公式称为合取范式合取范式,当且当且仅当它具有形式仅当它具有形式: A1A2An (n大于等于1)其中其中Ai(i=1,2,3,n)为简单析取式为简单析取式.如：如：P Q ，(PQ)(PQR), QP.1.4 析取范式与合取范式(3)范式范式：析取范式与合取范式统称为：析取范式与合取范式统称为范式范式。显然显然, 任何合任何合(析析)取范式的对偶式是析取范式的对偶式是析(合合)取范式取范式.析取范式与合取范式的性质析取范式与合取范式的性质: :定理定理2 2：(1) (1) 一个析取范式是矛盾式一个析取范式是矛盾式, ,当且仅当它的每当且仅当

13、它的每 一个简单合取式都是矛盾式一个简单合取式都是矛盾式; ;(2)(2)一个合取范式是重言式一个合取范式是重言式, ,当且仅当它的每当且仅当它的每 一个简单析取式都是重言式一个简单析取式都是重言式. .1.4 析取范式与合取范式定理定理3 (范式存在定理范式存在定理)任一个命题公式都存在着与之等价的析取范式与任一个命题公式都存在着与之等价的析取范式与合取范式。合取范式。1.4 析取范式与合取范式求命题公式的范式的基本步骤求命题公式的范式的基本步骤：1.4 析取范式与合取范式（）利用等价公式：化去（）利用等价公式：化去“”、“”联联结词，把命题公式变为与其等价的用结词，把命题公式变为与其等价的

14、用，表达的公式。表达的公式。 例例: ， （）（） （）（）（）将（）将“”深入到原子命题变元之前，并使深入到原子命题变元之前，并使变元之前最多只有一个变元之前最多只有一个“”词。词。例：例：（） 1.4 析取范式与合取范式（）利用（）利用对对的分配，将公式化为析取的分配，将公式化为析取范式，求合取范式利用范式，求合取范式利用对对 的分配的分配 。（）除去永假项得最简析取范式与合取范（）除去永假项得最简析取范式与合取范式。式。例：求（例：求（ ） R R的合取范式的合取范式 解：原式解：原式 （ ） R R （消去（消去 ） 1.4 析取范式与合取范式 （ ） R R） （R R （ ） （消

15、去消去） （ ） R R ） （ R R （ ） （消去（消去 ） （ ） R R ） （ P P R R ）（否定内移（否定内移 ）（ R R ） （ R R ） （ P P R R ）（ 对或对或的分配的分配 ）1.4 析取范式与合取范式例：求（例：求（ ） R R的析取范式的析取范式 解：原式解：原式 （ ） R R （消去（消去) （ ） R R ） （ P P R R ） （否定内移（否定内移 ） （ P P ） （ ） （ R R ） （R R P P） （R R ） （R R R R ） （ R R ） （ R R P P） （R R ）（ 对对的分配）的分配）1.4 析取范式与

16、合取范式注意注意：（1）单个命题变元既是简单合取式，又是单个命题变元既是简单合取式，又是简单析取式；公式简单析取式；公式PQR既可以看成是既可以看成是三个简单析取式构成的合取范式，也可以三个简单析取式构成的合取范式，也可以看成是析简单合取式构成的析取范式。看成是析简单合取式构成的析取范式。（2）一个命题公式的析一个命题公式的析(合合)取范式不是唯一取范式不是唯一的。的。1.4 析取范式与合取范式 例例1：求：求(P Q)R)P的析取范式与合取范式的析取范式与合取范式 解解: 原式原式(PQ)R)P(PQ )R)P(PR )(QR)P (析取范式析取范式)P(PR )(QR)P(QR) (析取范

17、式析取范式)(PQ P )(RP ) (合取范式合取范式)(PQ)(RP ) (合取范式合取范式)1.4 析取范式与合取范式 例例2：求：求(P Q) R的析取范式与合取范式的析取范式与合取范式 解解: 原式原式(PQ) R)(R(PQ) )(PQ)R)(R (PQ) )(PQ)R)(RPQ )(P Q)R)(RPQ )(PR)(QR)(RPQ ) (合取范式合取范式)(PQ)(RPQ ) )(R (RPQ )(PQR)(RP)(RQ) (析取范式析取范式)1.4 析取范式与合取范式命题公式的主析命题公式的主析(合合)取范式取范式(由于一个命题公式的析由于一个命题公式的析(合合)取范式不是唯一

18、取范式不是唯一, 因而它们不能作为命题公式的规范形式因而它们不能作为命题公式的规范形式(标准形标准形式式), 为了使任意命题公式化为唯一的标准形式为了使任意命题公式化为唯一的标准形式, 下下面引入主范式的概念面引入主范式的概念.1.4 析取范式与合取范式1.命题公式的主析取范式命题公式的主析取范式定义定义3：在含有在含有n个命题变元的个命题变元的简单合取简单合取式中式中,若每个命题变元和它的否定不同时出现，而二者若每个命题变元和它的否定不同时出现，而二者之一必出现且仅出现一次，称这样的之一必出现且仅出现一次，称这样的简单合取简单合取式式为为小项小项.例如例如,三个命题变元三个命题变元P,Q,R

19、,其小项共有其小项共有8个个:1.4 析取范式与合取范式 小项小项 编码编码 真值指派真值指派 小项的真值小项的真值 P Q R m000/ m0 000 1 P Q R m001/m1 001 1 P Q R m010/m2 010 1 P Q R m011/m3 011 1 P Q R m100/m4 100 1 P Q R m101/m5 101 1 P Q R m110/m6 110 1 P Q R m111/m7 111 11.4 析取范式与合取范式考虑：考虑：n个命题变元可产生多少个小（个命题变元可产生多少个小（大大）项？）项？ n个变元的小项个变元的小项: m0 P1 P2 .

20、Pn m1 P1 P2 . Pn m2n-1P1 P2 . Pn1.4 析取范式与合取范式极小项的性质极小项的性质:没有两个小项是等价的没有两个小项是等价的, 且每个极小项有且且每个极小项有且仅有一个成真赋值，若成真赋值所对应的二仅有一个成真赋值，若成真赋值所对应的二进制数转化为十进制数为进制数转化为十进制数为i，就将所对应的，就将所对应的极小项记作极小项记作mi。(2) 任意两个不同的极小项的合取为矛盾式任意两个不同的极小项的合取为矛盾式.(3) 全体极小项的析取为永真式全体极小项的析取为永真式.1.4 析取范式与合取范式定义定义4：设命题公式设命题公式A中含有中含有n个命题变元个命题变元,

21、 如果如果A的的析析取范式中，所有的取范式中，所有的简单合取简单合取式都是式都是极小项极小项，则称该，则称该析取析取范式范式为为A的主析取的主析取范式范式。定理定理4:任何命题公式都存在着与之等价的主任何命题公式都存在着与之等价的主析取范式，并且是唯一的。析取范式，并且是唯一的。求主析取范式的方法求主析取范式的方法：真值表；等值演算发：真值表；等值演算发1.4 析取范式与合取范式真值表法：真值表法：在真值表中，一个公式的真值为在真值表中，一个公式的真值为1的指派所对的指派所对应的极小项的析取，即为公式的主析取范式应的极小项的析取，即为公式的主析取范式例：求出例：求出、 （）、）、的主析取范式的

22、主析取范式1.4 析取范式与合取范式例：求出例：求出、 （）、）、的主析取范式的主析取范式100111011101101010101100（）1.4 析取范式与合取范式则可直接写出各命题公式的主析取范式：则可直接写出各命题公式的主析取范式：（ ）（ ）（）（）（）（）（）（）（）（）（）1.4 析取范式与合取范式（1）只要命题公式不是永假式，则一定可以根）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为，其方法是找出该公式为1的行，对应写出极的行，对应写出极小项的析取式，且一定是唯一的。小项的析取式，且一

23、定是唯一的。（2）若命题公式是含有）若命题公式是含有n个变元的永真式，则个变元的永真式，则它的主析取范式一定含有它的主析取范式一定含有2n个极小项。个极小项。（3）若二个命题公式对应的主析取范式相同，）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。则此二个命题公式一定是等价的。（4）命题公式的主析取范式中极小项的个数一）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为定等于对应真值表中真值为1的个数。的个数。1.4 析取范式与合取范式等值演算法等值演算法：下面介绍不用真值表，直接求命题公式主析取范下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步：式的方

24、法，分四步：（）将命题公式化归为与其等价的析取范式；（）将命题公式化归为与其等价的析取范式； （）除去永假项，合并基本积中相同项例：（）除去永假项，合并基本积中相同项例：），变为最简析取范式。），变为最简析取范式。（）利用添变元的方法，将所有基本积变为极（）利用添变元的方法，将所有基本积变为极小项。小项。1.4 析取范式与合取范式例：二个变元、，利用例：二个变元、，利用“”对或对或“”的的分配添项分配添项（） （）（） （） （）（）（）合并相同的极小项变为一项。（）合并相同的极小项变为一项。例：求（例：求（）的主析取范式的主析取范式解：原式解：原式（）（） -（1）化为析取范式）化为析取范式

25、 1.4 析取范式与合取范式 （） -（2）消去永假项，变为最简析取范式）消去永假项，变为最简析取范式（）（）（）（）（） -（3）添项）添项（）（） -（4）合并相同最小项）合并相同最小项1.4 析取范式与合取范式例例1：求：求(P Q)R)P的主析取范式的主析取范式。 解解: 原式原式(PQ)R)PP(QR) (析取范式析取范式)(P(QQ)(RR)(PP) (QR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式主析取范式)m7m6m5m4m2m2m4m5m6m71.4 析取范式与合取范式例例2：求：求(PQ

26、)R的主析取范式的主析取范式。解解:(PQR)(RP)(RQ) (析取范式析取范式)(PQR)(R P)(QQ) (PP) (RQ ) (PQR)(PQR)(PQR) (PQR)(PQR ) (PQR)(PQR) (PQR) (PQR) (主析取范式主析取范式) m1 m3 m4 m7 1.4 析取范式与合取范式2.命题公式的主合取范式命题公式的主合取范式定义定义5：在含有在含有n个命题变元的个命题变元的简单析取简单析取式中式中,若每个命题变元和它的否定不同时出现，而二者若每个命题变元和它的否定不同时出现，而二者之一必出现且仅出现一次，称这样的之一必出现且仅出现一次，称这样的简单析取简单析取式

27、式为为极大项极大项.例如例如,三个命题变元三个命题变元P,Q,R,其大项共有其大项共有8个个:1.4 析取范式与合取范式 大项大项 编码编码 真值指派真值指派 大项的真值大项的真值 P Q R M000/M0 000 0 P Q R M001/M1 001 0 P Q R M010/M2 010 0P Q R M011/M3 011 0P Q R M100/M4 100 0P Q R M101/M5 101 0 P Q R M110/M6 110 0 P Q R M111/M7 111 01.4 析取范式与合取范式极大项的性质极大项的性质:没有两个大项是等价的没有两个大项是等价的, 且每个极大

28、项有且仅且每个极大项有且仅有一个成假赋值，若成假赋值所对应的二进有一个成假赋值，若成假赋值所对应的二进制数转化为十进制数为制数转化为十进制数为i，就将所对应的极大，就将所对应的极大项记作项记作Mi。(2) 任意两个不同的极大项的析取为永真式任意两个不同的极大项的析取为永真式.(3) 全体极大项的合取为矛盾式全体极大项的合取为矛盾式.1.4 析取范式与合取范式定义定义6：设命题公式设命题公式A中含有中含有n个命题变元个命题变元, 如如果果A的的合取范式合取范式中，所有的中，所有的简单析取简单析取式都是式都是大大项项，则称该，则称该合取合取范式范式为为A的主合取范式的主合取范式。定理：定理：任何命

29、题公式都存在着与之等价的主任何命题公式都存在着与之等价的主合取范式，并且是唯一的。合取范式，并且是唯一的。1.4 析取范式与合取范式定理定理5:在命题公式在命题公式A的真值表中的真值表中,真值为真值为0的的指派对应的大项的合取指派对应的大项的合取, 即为即为A的主的主合取范合取范式式一个命题公式一个命题公式A的主合取范式的主合取范式, 还可以通过等还可以通过等值演算的方法求出值演算的方法求出, 其推演步骤其推演步骤:(1) 将将A化为合取范式化为合取范式 ;(2) 除去合取范式中所有永真的合取项除去合取范式中所有永真的合取项;1.4 析取范式与合取范式(3) 将合取范式中重复出现的简单析取式和

30、相同将合取范式中重复出现的简单析取式和相同变元都消去变元都消去;(4)若合取范式中某简单析取式若合取范式中某简单析取式B中不含命题变中不含命题变元元Pi, 添加添加(Pi Pi), 然后应用分配律展开然后应用分配律展开. 即即 B B 0B (Pi Pi) (B Pi) (B Pi).注：注：1.1.命题公式的主析命题公式的主析( (合合) )取范式唯一。取范式唯一。 2.2.两命题公式若有相同的主析两命题公式若有相同的主析( (合合) )取范取范 式，则二命题公式等价式，则二命题公式等价. .1.4 析取范式与合取范式例例3：求：求(P Q)R)P的主合取范式的主合取范式。 解解: 原式原式

31、(PQ)R)P (PQ)(RP ) (合取范式合取范式)(PQ)(RR )(RP )(QQ)(PQR)(PQR)(PQR) (PQR) (PQR)(PQR)(PQR) (主合取范式主合取范式)M0M1M31.4 析取范式与合取范式 例例4：求：求(PQ)R的主合取范式的主合取范式。 解解: 原式原式(PR)(QR)(RPQ) (合取范合取范式式)(PR)(QQ) (PP) (QR) (PQR ) (PQR)(PQR)(PQR) (PQR)(PQR ) (PQR)(PQR) (PQR)(PQR ) (主合取范式主合取范式)M0M2M5 M6 1.4 析取范式与合取范式3.3.主析取范式和主合取范

32、式关系主析取范式和主合取范式关系设设Z为命题公式为命题公式A的主析取范式中所有小项的足的主析取范式中所有小项的足标集合，标集合，R为命题公式为命题公式A的主合取范式中所的主合取范式中所有大项的足标集合有大项的足标集合,则则 R=0,1，2.2n-1-Z或或 Z=0,1，2.2n-1-R。故已知命题公式故已知命题公式A的主析取范式，可求得其主的主析取范式，可求得其主合取范式；反之亦然。合取范式；反之亦然。注意到小项与大项之间具有关系：注意到小项与大项之间具有关系：miMi，Mimi（例：（例：m5：P Q R M5：P Q R）1.4 析取范式与合取范式4.主析主析(合合)取范式的应用取范式的应

33、用(1)求公式的成真求公式的成真/成假赋值：成假赋值： 若公式若公式A中含有中含有n个命题变元，且个命题变元，且A的主析的主析取范式含取范式含s个极小项，则个极小项，则A有有s个成真赋值，个成真赋值，有有2n-s个成假赋值。（即主析取范式中的小个成假赋值。（即主析取范式中的小项对应的编码是公式项对应的编码是公式A的成真赋值；反之的成真赋值；反之主合取范式中的大项对应的编码是公式主合取范式中的大项对应的编码是公式A的成假赋值）的成假赋值）.1.4 析取范式与合取范式(2)判断公式的类型判断公式的类型： 设公式设公式A中含有中含有n个命题变元，则：个命题变元，则：（1） A为重言式为重言式 A的的

34、主析取范式主析取范式含全部含全部2n个极个极小项小项（2）A为矛盾式为矛盾式 A的的主析取范式主析取范式不含任何极小项，不含任何极小项， 记记A的主析取范式为的主析取范式为0（3） A为可满足式为可满足式 A的的主析取范式主析取范式至少含一个极小项至少含一个极小项（4） A为矛盾式为矛盾式 A的的主合取范式主合取范式含全部含全部2n个极大项个极大项（5） A为重言式为重言式 A的的主合取范式主合取范式不含任何极大项，不含任何极大项， 记记A的主合取范式为的主合取范式为1 （6） A为可满足式为可满足式 A的的主合取范式主合取范式中极大项的个数中极大项的个数 一定小于一定小于2n 1.4 析取范

35、式与合取范式(3)判断两个命题是否等价判断两个命题是否等价5.解决实际问题：解决实际问题：某科研所有三名青年高级工程师某科研所有三名青年高级工程师A，B，C。所里要选派他们中的所里要选派他们中的1到到2人出国进修，由人出国进修，由于所里工作的需要，选派时必须满足以下于所里工作的需要，选派时必须满足以下条件：条件：若若A去，则去，则C也去也去若若B去，则去，则C不能去不能去若若C不去，则不去，则A或或B去去问所里应如何选派他们？问所里应如何选派他们？1.4 析取范式与合取范式解解: 设设 P:派派A去。去。Q :派派B去。去。R :派派C去。去。根据所要满足的条件，得命题公式为：根据所要满足的条

36、件，得命题公式为： (PR)(Q R)(R( PQ) )求此公式的主析取范式求此公式的主析取范式:原式原式(PQR)(PQR)(PQR) 因此有三种选派方案：去，而、都不去；去因此有三种选派方案：去，而、都不去；去，而、都不去；、都去，而不去，而、都不去；、都去，而不去.1.4 析取范式与合取范式小结小结:本节主要介绍了范式、本节主要介绍了范式、 析析(合合)取范式、取范式、(主主)析析(合合)取范式。重点掌握取范式。重点掌握(主主)析析(合合)取范式的求取范式的求法。法。 作业作业: 1. 习题习题2: 7、8、9、30 2. 预习预习2.31.5 联结词的完备集v定义定义: 0, 1上的上的n元函数元函数 f: 0, 1n 0, 1 就称为一个就称为一个n元真值函数（布尔函数）元真值函数（布尔函数）v自变量有自变量有2n组不同的取值，真值函数取组不同的取值，真值函数取值只有两种：值只有两种：1 0 n共有共有 种不同的真值函数种不同的真值函数22n1.5 联结词的完备集问题：v常用五个联常用五个联结结词词， ， ， ，是否有冗余呢？是否有冗余呢？ABABAB( AB) (B A) 1.5 联结词的完备集联结词完备集联结词完备集 定义：定义：一个联结词集合，若对于任何一个一个联结词集合，若对于任何一个公式均可以用该集