离散数学第1章命题逻辑.ppt

《离散数学第1章命题逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学第1章命题逻辑.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学授课教师：仝允战第一章第一章 命题逻辑命题逻辑（Proposition LogicProposition LogicProposition LogicProposition Logic）命题符号化及联结词命题符号化及联结词命题符号化及联结词命题符号化及联结词命题公式及分类命题公式及分类命题公式及分类命题公式及分类等值演算等值演算等值演算等值演算联结词全功能集联结词全功能集联结词全功能集联结词全功能集对偶与范式对偶与范式对偶与范式对偶与范式推理理论推理理论推理理论推理理论1 12 23 34 45 56 62 2简介简介逻辑学：逻辑学：研究推理的一门学科研究推理的一门学科数理逻辑

2、：数理逻辑：用数学方法研究推理的一门数学学科用数学方法研究推理的一门数学学科 一套符号体系一套符号体系+一组规则一组规则3 3简介简介数理逻辑的内容：数理逻辑的内容：古典数理逻辑：古典数理逻辑：命题逻辑、谓词逻辑命题逻辑、谓词逻辑 现代数理逻辑：现代数理逻辑：逻辑演算、公理化集合论、递归逻辑演算、公理化集合论、递归论、模型论、证明论论、模型论、证明论4 4命题逻辑命题逻辑命题命题(Proposition)：一个有确定真或假意义的语句。一个有确定真或假意义的语句。命题符号化及联结词命题符号化及联结词1 15 5EXAMPLE 1 EXAMPLE 1 下列句子都是命题：下列句子都是命题：1.华盛顿

3、是美国的首都。华盛顿是美国的首都。2.多伦多是加拿大的首都。多伦多是加拿大的首都。3.1+1=2。4.2+2=3。命题命题1和和3是真命题，是真命题，2和和4是假命题。是假命题。命题符号化及联结词命题符号化及联结词6 6命题符号化及联结词命题符号化及联结词EXAMPLE 2 EXAMPLE 2 考虑如下句子：考虑如下句子：1.现在几点了？现在几点了？2.认真阅读一下。认真阅读一下。3.x+1=2.4.x+y=z.句子句子1和和2不是命题，因为它们都不是陈述句。不是命题，因为它们都不是陈述句。句子句子3和和4不是命题，由于不是命题，由于x，y和和z的值不确定，的值不确定，使得它们的真值都不唯一。

4、使得它们的真值都不唯一。7 7命题的语句形式：命题的语句形式：陈述句陈述句非命题语句：非命题语句：疑问句、命令句、感叹句、疑问句、命令句、感叹句、非命题陈述句：悖论语句（真值不唯一）非命题陈述句：悖论语句（真值不唯一）命题符号化及联结词命题符号化及联结词8 8命题的符号表示：命题的符号表示：大小写英文字母：大小写英文字母：P、Q、R、p、q、r命题真值命题真值(Truth Values)的表示：的表示：真：真：T、1 假：假：F、0命题符号化及联结词命题符号化及联结词9 9命题语句真值确定的几点说明：命题语句真值确定的几点说明：1、时间性、时间性 2、区域性、区域性 3、标准性、标准性命题真值

5、间的关系表示：命题真值间的关系表示：真值表真值表(Truth Table)命题符号化及联结词命题符号化及联结词1010DEFINITION 1.DEFINITION 1.设设p为任一命题，复合命题为任一命题，复合命题“非非p”（或或“p的否定的否定”）称为）称为p的的否定式否定式。记作。记作 p。为为否定联结词否定联结词。真值表见。真值表见Table 1。(Let p be a Let p be a proposition.The statement “It is not the case that proposition.The statement “It is not the case t

6、hat p.”is another proposition,called the negation of p.p.”is another proposition,called the negation of p.The negation of p is denoted by The negation of p is denoted by p.The proposition p.The proposition p is read“not p.”p is read“not p.”)p p的否定的否定的否定的否定命题符号化及联结词命题符号化及联结词1111Table 1 Table1否定命题的真值表

7、否定命题的真值表pp1001命题符号化及联结词命题符号化及联结词1212EXAMPLE 3 EXAMPLE 3 设设p表示表示“今天是星期五今天是星期五”，则则 p表示表示“今天不是星期五今天不是星期五”。显然，当显然，当p的真值为的真值为0时，时，p的的真值为真值为1。命题符号化及联结词命题符号化及联结词1313命题符号化及联结词命题符号化及联结词设设p，q为两命题，复合命题为两命题，复合命题“p并且并且q”（或或“p和和q”）称作称作p与与q的的合取式合取式。记作。记作p q。为为合取联结词合取联结词。真值表见。真值表见Table 2。(Let p and q be proposition

8、s.The proposition p and q,denoted by p q,is the proposition that is true when both p and q are true and is false otherwise.The proposition p q is called the conjunction of p and q.)p p和和和和q q的合取的合取的合取的合取DEFINITION 2.DEFINITION 2.1414命题符号化及联结词命题符号化及联结词Table 2 Table2两个命题的合取的真值表两个命题的合取的真值表p qp q0 00 11

9、 01 100011515EXAMPLE 4 EXAMPLE 4 用用p表示命题表示命题“今天是星期五今天是星期五”，q表示命题表示命题“今天下雨今天下雨”，则命题则命题p与与q的合取式是什么？的合取式是什么？解答：解答：解答：解答：p p与与与与q q的合取式的合取式的合取式的合取式 p p q q是是是是“今天是星期五，而今天是星期五，而今天是星期五，而今天是星期五，而且今天下雨。且今天下雨。且今天下雨。且今天下雨。”如果是星期五，又下雨，则该如果是星期五，又下雨，则该如果是星期五，又下雨，则该如果是星期五，又下雨，则该命题为真；如果是除星期五外的任意一天，或命题为真；如果是除星期五外的任

10、意一天，或命题为真；如果是除星期五外的任意一天，或命题为真；如果是除星期五外的任意一天，或者虽是星期五但没下雨，则该命题为假。者虽是星期五但没下雨，则该命题为假。者虽是星期五但没下雨，则该命题为假。者虽是星期五但没下雨，则该命题为假。命题符号化及联结词命题符号化及联结词1616命题符号化及联结词命题符号化及联结词设设p，q为两命题，复合命题为两命题，复合命题“p或或q”称作称作p与与q的的析取式析取式。记作。记作p q。为为析取联结词析取联结词。真。真值表见值表见Table 3。(Let p and q be propositions.The proposition p or q,denote

11、d by p q,is the proposition that is false when p and q are both false and true otherwise.The proposition p q is called the disjunction of p and q.)p p和和和和q q的析取的析取的析取的析取DEFINITION 3.DEFINITION 3.1717命题符号化及联结词命题符号化及联结词Table 3 Table3两个命题的析取的真值表两个命题的析取的真值表p qp q0 00 11 01 101111818还是以还是以Example 4 为例，命题

12、为例，命题p与与q的析取式是什么？的析取式是什么？解答：解答：解答：解答：p p与与与与q q的析取式的析取式的析取式的析取式 p p q q是是是是“今天是星期五或今天今天是星期五或今天今天是星期五或今天今天是星期五或今天下雨。下雨。下雨。下雨。”只有今天既不是星期五，又没有下雨，只有今天既不是星期五，又没有下雨，只有今天既不是星期五，又没有下雨，只有今天既不是星期五，又没有下雨，则该命题为假；如果今天是星期五或者今天下雨则该命题为假；如果今天是星期五或者今天下雨则该命题为假；如果今天是星期五或者今天下雨则该命题为假；如果今天是星期五或者今天下雨了（包括下雨的星期五），则该命题就为真。了（包

13、括下雨的星期五），则该命题就为真。了（包括下雨的星期五），则该命题就为真。了（包括下雨的星期五），则该命题就为真。EXAMPLE 5 EXAMPLE 5 命题符号化及联结词命题符号化及联结词1919命题符号化及联结词命题符号化及联结词设设p，q为两命题，复合命题为两命题，复合命题“如果如果p，则则q”称作称作p与与q的的蕴含式蕴含式。记作记作 pq。称称p为蕴为蕴含式的含式的前件前件(hypothesis)，q为蕴含式的为蕴含式的后后件件(conclusion)。称作称作蕴含联结词蕴含联结词。真值。真值表见表见Table 4。(Let p and q be propositions.The i

14、mplication pq is the proposition that is false when p is true and q is false and true otherwise.)如果如果如果如果p p，则，则，则，则q q单条件，单条件，单条件，单条件，蕴涵蕴涵蕴涵蕴涵p p：前提前提前提前提 q q：结论结论结论结论DEFINITION 4.DEFINITION 4.2020命题符号化及联结词命题符号化及联结词Table 4 Table4蕴含式蕴含式p q的真值表的真值表p qp q0 00 11 01 111012121命题符号化及联结词命题符号化及联结词 用用p表示命题表

15、示命题“天下雨天下雨”，用，用q表示命题表示命题“我骑自行车上班我骑自行车上班”，将下列命题符号化：，将下列命题符号化：（1）只要不下雨，我就骑自行车上班。）只要不下雨，我就骑自行车上班。（2）只有不下雨，我才骑自行车上班。）只有不下雨，我才骑自行车上班。解答：解答：解答：解答：（1 1）中，）中，）中，）中，p p是是是是q q的充分条件，因而符号化为的充分条件，因而符号化为的充分条件，因而符号化为的充分条件，因而符号化为 pqpq；（2 2）中，中，中，中，p p是是是是q q的必要条件，因而符号化为的必要条件，因而符号化为的必要条件，因而符号化为的必要条件，因而符号化为qq p p。EX

16、AMPLE 6 EXAMPLE 6 2222命题符号化及联结词命题符号化及联结词设设p，q为两命题，复合命题为两命题，复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式。记作。记作pq，称作称作等价联结词等价联结词。真值表见真值表见Table 5。(Let p and q be propositions,The biconditional pq is the proposition that is true when p and q have the same truth values and is false otherwise.)p p当且仅当当且仅当当且仅当当且仅当q q双

17、条件，等价双条件，等价双条件，等价双条件，等价DEFINITION 5.DEFINITION 5.2323命题符号化及联结词命题符号化及联结词Table 5 Table5等价式等价式p q的真值表的真值表p qp q0 00 11 01 110012424命题符号化及联结词命题符号化及联结词将下一命题符号化：将下一命题符号化：“只有（仅当）只有（仅当）你是计算机科学系的学你是计算机科学系的学生或者你不是新生，你才可以通过校园网生或者你不是新生，你才可以通过校园网上上Internet。”解答：解答：a (c f)EXAMPLE 7 EXAMPLE 7 cfa2525 将下一命题符号化：将下一命题

18、符号化：“如果你身高小于如果你身高小于4英尺，你就不能乘英尺，你就不能乘坐过山车，除非你超过了坐过山车，除非你超过了16岁。岁。”解答：解答：解答：解答：(1)(1)(r r s)s)q.q.(2)(2)s(r s(r q).q).EXAMPLE 8 EXAMPLE 8 r rq qs s如果你身高小于如果你身高小于如果你身高小于如果你身高小于4 4英尺，而英尺，而英尺，而英尺，而且你不超过且你不超过且你不超过且你不超过1616岁，那么你就岁，那么你就岁，那么你就岁，那么你就不能乘坐过山车。不能乘坐过山车。不能乘坐过山车。不能乘坐过山车。如果你不超过如果你不超过如果你不超过如果你不超过1616

19、岁，那么岁，那么岁，那么岁，那么当你身高小于当你身高小于当你身高小于当你身高小于4 4英尺时，你英尺时，你英尺时，你英尺时，你就不能乘坐过山车。就不能乘坐过山车。就不能乘坐过山车。就不能乘坐过山车。命题符号化及联结词命题符号化及联结词2626命题符号化及联结词命题符号化及联结词“说离散数学是枯燥无味的或毫无价值说离散数学是枯燥无味的或毫无价值的，那是不对的。的，那是不对的。”p：离散数学是有味道的；离散数学是有味道的；q：离散数学是有价值的；离散数学是有价值的；EXAMPLE 9 EXAMPLE 9 符号化为：符号化为：符号化为：符号化为：(p p q)q)2727命题逻辑命题逻辑命题公式及分

20、类命题公式及分类2 2P P、QQ、R R 称为称为称为称为原子命题原子命题原子命题原子命题(Atomic Proposition)Atomic Proposition)。原子命题或加上逻辑联结词组成的表达式成为原子命题或加上逻辑联结词组成的表达式成为原子命题或加上逻辑联结词组成的表达式成为原子命题或加上逻辑联结词组成的表达式成为复合命题复合命题复合命题复合命题(Compositional Proposition)Compositional Proposition)。从从从从命题常量命题常量命题常量命题常量 到到到到 命题变量命题变量命题变量命题变量(Propositional Variabl

21、e)Propositional Variable)命题公式：命题公式：命题公式：命题公式：1.1.原子命题是命题公式；原子命题是命题公式；原子命题是命题公式；原子命题是命题公式；2.2.设设设设P P是命题公式，则是命题公式，则是命题公式，则是命题公式，则 P P也是命题公式；也是命题公式；也是命题公式；也是命题公式；3.3.设设设设P P、QQ是命题公式，则是命题公式，则是命题公式，则是命题公式，则(P P Q)Q)、(P(P Q)Q)、(PQ)(PQ)、(P(P Q)Q)也是命题公式；也是命题公式；也是命题公式；也是命题公式；4.4.有限次地使用有限次地使用有限次地使用有限次地使用1 1、

22、2 2、3 3所得到的也是命题公式。所得到的也是命题公式。所得到的也是命题公式。所得到的也是命题公式。Proposition Formulas,Well-Formed Formulas(wff)Proposition Formulas,Well-Formed Formulas(wff)2828命题公式及分类命题公式及分类命题公式的运算规则：命题公式的运算规则：逻辑联接词的优先级：逻辑联接词的优先级：、命题公式的表达式的运算规律：命题公式的表达式的运算规律：同代数表达式同代数表达式命题公式的运算方法：命题公式的运算方法：所有公式中的命题变量用指定命题（真值）代所有公式中的命题变量用指定命题（真值

23、）代入（或指派），得到一个公式对应的真值。入（或指派），得到一个公式对应的真值。性质性质性质性质1 1：如果一个命题公式有如果一个命题公式有n个互异的命题变量，个互异的命题变量，则命题公式对应的真值有则命题公式对应的真值有2n种可能分布。种可能分布。2929命题公式及分类命题公式及分类EXAMPLE 10 EXAMPLE 10 求下列命题公式的真值表：求下列命题公式的真值表：求下列命题公式的真值表：求下列命题公式的真值表：（1 1）p p (q (q r).r).Table6Table6p p (q (q r)r)的真值表的真值表的真值表的真值表p q rp q rr rq q r rp p

24、(q (q r)r)0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 11 10 01 10 01 10 01 10 01 10 01 11 11 10 01 11 10 00 00 00 01 10 01 11 13030命题公式及分类命题公式及分类EXAMPLE 10 EXAMPLE 10 求下列命题公式的真值表：求下列命题公式的真值表：求下列命题公式的真值表：求下列命题公式的真值表：（2 2）(p p (pq)q.(pq)q.Table7Table7(p(p (pq)q(pq)q

25、的真值表的真值表的真值表的真值表p qp qpqpq p p (pq)(pq)(p p (pq)(pq)qq0 00 00 10 11 01 01 11 11 11 10 01 10 00 00 01 11 11 11 11 13131命题公式及分类命题公式及分类EXAMPLE 10 EXAMPLE 10 求下列命题公式的真值表：求下列命题公式的真值表：求下列命题公式的真值表：求下列命题公式的真值表：（3 3）(pq)pq)q.q.Table8Table8(pq)(pq)q q 的真值表的真值表的真值表的真值表p qp qpqpq(pq)pq)(pq)pq)q q0 00 00 10 11 0

26、1 01 11 11 11 10 01 10 00 01 10 00 00 00 00 03232命题公式及分类命题公式及分类永真式永真式永真式永真式(Tautology)Tautology)：公式中的命题变量无论怎样公式中的命题变量无论怎样公式中的命题变量无论怎样公式中的命题变量无论怎样代入，公式对应的真值恒为代入，公式对应的真值恒为代入，公式对应的真值恒为代入，公式对应的真值恒为1 1。永假式永假式永假式永假式(Contradiction)Contradiction)：公式中的命题变量无论公式中的命题变量无论公式中的命题变量无论公式中的命题变量无论怎样代入，公式对应的真值恒为怎样代入，公式

27、对应的真值恒为怎样代入，公式对应的真值恒为怎样代入，公式对应的真值恒为0 0。可满足式可满足式可满足式可满足式(Satisfaction)Satisfaction)：公式中的命题变量无公式中的命题变量无公式中的命题变量无公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为论怎样代入，公式对应的真值总有一种情况为论怎样代入，公式对应的真值总有一种情况为论怎样代入，公式对应的真值总有一种情况为1 1。一般命题公式一般命题公式一般命题公式一般命题公式(Contingency)Contingency)：既不是永真公式也既不是永真公式也既不是永真公式也既不是永真公式也不是永假公式。不是永假公式。不

28、是永假公式。不是永假公式。3333命题公式及分类命题公式及分类性质性质2：（1）设）设P是永真命题公式，则是永真命题公式，则P的否定的否定公式是永假命题公式；公式是永假命题公式；（2）设）设P是永假命题公式，则是永假命题公式，则P的否定的否定公式是永真命题公式；公式是永真命题公式；（3）设）设P、Q是永真命题公式，则是永真命题公式，则(P Q)、(P Q)、(PQ)、(P Q)也是也是永真命题公式永真命题公式。3434命题公式及分类命题公式及分类小小 结结1.1.命题的概念：定义、逻辑值、命题的概念：定义、逻辑值、命题的概念：定义、逻辑值、命题的概念：定义、逻辑值、符号化表示符号化表示符号化表

29、示符号化表示2.2.从简单命题到复合命题：从简单命题到复合命题：从简单命题到复合命题：从简单命题到复合命题：逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级逻辑联接词：运算方法、运算优先级3.3.从命题常量到命题变量，从命题常量到命题变量，从命题常量到命题变量，从命题常量到命题变量，从复合命题到命题公式：从复合命题到命题公式：从复合命题到命题公式：从复合命题到命题公式：命题公式的真值描述：真值表命题公式的真值描述：真值表命题公式的真值描述：真值表命题公式的真值描述：真值表4.4.命题公式的分类：命题公式的分类：命题公式的分类：命题公式的分类：永真

30、公式、永假公式、可满足公式永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式永真公式、永假公式、可满足公式 、一般公式、一般公式、一般公式、一般公式 3535Propositional EquivalencesPropositional Equivalences设设A，B为两命题公式，若等价式为两命题公式，若等价式AB是重是重言式，则称言式，则称A与与B是是等值等值的。记作的。记作AB。(The propositions A and B are called logically equivalent if AB is a tautology.The notation AB denot

31、es that A and B are logically equivalent.)逻辑等值，或逻辑等价逻辑等值，或逻辑等价逻辑等值，或逻辑等价逻辑等值，或逻辑等价DEFINITION 6.DEFINITION 6.命题逻辑命题逻辑等值演算等值演算3 33636证明证明(p q)与与p q 是等值的。是等值的。（这个等值关系是德（这个等值关系是德（这个等值关系是德（这个等值关系是德 摩根摩根摩根摩根(De Morgan)De Morgan)定律之定律之定律之定律之一。德一。德一。德一。德 摩根是十九世纪中叶的英国数学家。）摩根是十九世纪中叶的英国数学家。）摩根是十九世纪中叶的英国数学家。）摩根

32、是十九世纪中叶的英国数学家。）解答：真值表见解答：真值表见解答：真值表见解答：真值表见Table 9Table 9。因为对于因为对于因为对于因为对于p p和和和和q q 所所所所有可能的组合，有可能的组合，有可能的组合，有可能的组合，(p p q)q)和和和和p p q q的真的真的真的真值都相同，所以这两个命题是等值的。值都相同，所以这两个命题是等值的。值都相同，所以这两个命题是等值的。值都相同，所以这两个命题是等值的。EXAMPLE 11 EXAMPLE 11 等值演算等值演算3737Table 9 Table9(p q)与与p q的真值表的真值表p qp q(p q)p qp q0 00

33、 11 01 101111000110010101000等值演算等值演算3838证明证明pq 与与p q 是等值的。是等值的。解答：真值表见解答：真值表见解答：真值表见解答：真值表见Table 10Table 10。因为对于因为对于因为对于因为对于p p和和和和q q 所有可能的组合，所有可能的组合，所有可能的组合，所有可能的组合，pq pq 和和和和p p q q的真值的真值的真值的真值都相同，所以这两个命题是等值的。都相同，所以这两个命题是等值的。都相同，所以这两个命题是等值的。都相同，所以这两个命题是等值的。EXAMPLE 12 EXAMPLE 12 等值演算等值演算3939Table

34、10 Table10pq与与p q 的真值表的真值表p qpq p p q0 00 11 01 1110111001101等值演算等值演算4040证明证明p(q r)与与(p q)(p r)是等是等值的。值的。（分配律）（分配律）（分配律）（分配律）解答：真值表见解答：真值表见解答：真值表见解答：真值表见Table 11Table 11。因为对于因为对于因为对于因为对于p p、q q和和和和r r所所所所有可能的组合，有可能的组合，有可能的组合，有可能的组合，p p (q(q r)r)和和和和(p p q)q)(p(p r)r)的的的的真值都相同，所以这两个命题是等值的。真值都相同，所以这两个

35、命题是等值的。真值都相同，所以这两个命题是等值的。真值都相同，所以这两个命题是等值的。EXAMPLE 13 EXAMPLE 13 等值演算等值演算4141Table 11 Table 11 Table11Table11p p (q(q r)r)与与与与(p p q)q)(p(p r)r)的真值表的真值表的真值表的真值表p q rp q rq q r rp p (q(q r)r)p p q qp p r r(p p q)q)(p(p r r)0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1

36、 10 00 00 01 10 00 00 01 10 00 00 01 11 11 11 11 10 00 01 11 11 11 11 11 10 01 10 01 11 11 11 11 10 00 00 01 11 11 11 11 1等值演算等值演算4242 下面给出下面给出下面给出下面给出2424个重要的等值式个重要的等值式个重要的等值式个重要的等值式（祥见（祥见（祥见（祥见P9P9）：）：）：）：双双双双重否定律、等幂律、交换律、结合律、分配律、重否定律、等幂律、交换律、结合律、分配律、重否定律、等幂律、交换律、结合律、分配律、重否定律、等幂律、交换律、结合律、分配律、德德德德

37、摩根律、吸收律、零律、同一律、排中律、摩根律、吸收律、零律、同一律、排中律、摩根律、吸收律、零律、同一律、排中律、摩根律、吸收律、零律、同一律、排中律、矛盾式、蕴含等值式、等价等值式、假言易位、矛盾式、蕴含等值式、等价等值式、假言易位、矛盾式、蕴含等值式、等价等值式、假言易位、矛盾式、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。等价否定等值式、归谬论。等价否定等值式、归谬论。等价否定等值式、归谬论。根据已知的等值式，推演出另外一些等值式根据已知的等值式，推演出另外一些等值式根据已知的等值式，推演出另外一些等值式根据已知的等值式，推演出另外一些等值式的过程称为的过程称为的过程称为的

38、过程称为等值演算等值演算等值演算等值演算。在进行等值演算时，往往。在进行等值演算时，往往。在进行等值演算时，往往。在进行等值演算时，往往用到用到用到用到置换规则置换规则置换规则置换规则。等值演算等值演算4343证明证明(p(p q)与与p q是等值的。是等值的。EXAMPLE 14 EXAMPLE 14 0 00 0等值演算等值演算4444证明证明(p q)(p q)是重言式。是重言式。EXAMPLE 15 EXAMPLE 15 1 11 11 1等值演算等值演算4545判断命题公式逻辑等价的方法：判断命题公式逻辑等价的方法：1.真值表真值表 2.命题公式的演算命题公式的演算 基本等值定理；基

39、本等值定理；公式的代入不变性（置换规则）；公式的代入不变性（置换规则）；等值关系的传递性。等值关系的传递性。等值演算等值演算4646命题公式逻辑等价关系的应用：命题公式逻辑等价关系的应用：1、判定是否逻辑等价（等值）；、判定是否逻辑等价（等值）；2、判断是否为永真公式或永假公式；、判断是否为永真公式或永假公式；3、命题公式的化简。、命题公式的化简。等值演算等值演算4747设设p,q为两命题，复合命题为两命题，复合命题“p,q之中恰有一个成立之中恰有一个成立”称为称为p与与q的的排斥或排斥或或或异或异或。记作。记作p q，称作称作排排斥或斥或或或异或联结词异或联结词。真值表见真值表见Table

40、12。(Let p and q be propositions.The exclusive or of p and q,denoted by p q,is the proposition that is true when exactly one of p and q is true and is false otherwise.)p p和和和和q q的异或的异或的异或的异或DEFINITION 7.DEFINITION 7.命题逻辑命题逻辑联结词全功能集联结词全功能集4 44848Table 12 联结词全功能集联结词全功能集01100 00 11 01 1p qp qTable12异或异或

41、p q的真值表的真值表p p q q (p(p q)q)(p p q)q)4949设设p,q为两命题，复合命题为两命题，复合命题“p与与q的否定的否定”称为称为p与与q的的与非式与非式。记作。记作p q，称作称作与与非联结词非联结词。真值表见真值表见Table 13。(Let p and q be propositions.The and not of p and q,denoted by p q,is the proposition that is false when p and q are both true and true otherwise.)p和和q的与非的与非DEFINITIO

42、N 8.DEFINITION 8.联结词全功能集联结词全功能集5050Table 13 Table13与非式与非式p q的真值表的真值表p qp q0 00 11 01 11110p p q q (p(p q)q)联结词全功能集联结词全功能集5151设设p,q为两命题，复合命题为两命题，复合命题“p或或q的否定的否定”称为称为p与与q的的或非式或非式。记作。记作p q，称称作作或非联结词或非联结词。真值表见真值表见Table 14。(Let p and q be propositions.The or not of p and q,denoted by p q,is the propositi

43、on that is true when p and q are both false and false otherwise.)p和和q的或非的或非DEFINITION 9.DEFINITION 9.联结词全功能集联结词全功能集5252Table 14 Table14与非式与非式p q的真值表的真值表p qp q0 00 11 01 11000p p q q (p(p q)q)联结词全功能集联结词全功能集5353逻辑联结词集是逻辑联结词集是功能完备集功能完备集(Functionally Complete Set)：任一个命题公式都能够等价于仅包含这些任一个命题公式都能够等价于仅包含这些任一个

44、命题公式都能够等价于仅包含这些任一个命题公式都能够等价于仅包含这些逻辑联结词联结起来的公式。逻辑联结词联结起来的公式。逻辑联结词联结起来的公式。逻辑联结词联结起来的公式。逻辑联结词集是逻辑联结词集是极小功能完备集极小功能完备集：是功能完备集并且没有冗余联结词。是功能完备集并且没有冗余联结词。是功能完备集并且没有冗余联结词。是功能完备集并且没有冗余联结词。联结词全功能集联结词全功能集5454例例1：、是功能完备的，但不是是功能完备的，但不是极小功能完备的极小功能完备的。例例2：、是是极小功能完备的极小功能完备的。例例3：、是是极小功能完备的极小功能完备的。联结词全功能集联结词全功能集5555DE

45、FINITION 10.DEFINITION 10.命题公式命题公式P的的对偶公式对偶公式(Dual)：将将P中的中的 析取联结词换成合取联结词，析取联结词换成合取联结词，合取联结词换成析取联结词，合取联结词换成析取联结词，1换成换成0，0换成换成1（如果存在的话）。（如果存在的话）。记为记为P*.命题逻辑命题逻辑对偶与范式对偶与范式5 55656对偶原理对偶原理(Duality Principle)：设设设设P P，QQ是两命题公式，如果是两命题公式，如果是两命题公式，如果是两命题公式，如果 P P Q Q，则则则则 P*P*Q*Q*。例：例：例：例：A A：(P (P Q)Q)Q Q B

46、B：P P Q Q这里，这里，这里，这里，A A B B，分分分分析是否析是否析是否析是否A*A*B*B*。对偶与范式对偶与范式5757命题公式的标准化命题公式的标准化范式范式小项小项小项小项(small item)/small item)/合取式合取式合取式合取式(conjunctive form):conjunctive form):若干个原子命题或其否定的合取。若干个原子命题或其否定的合取。若干个原子命题或其否定的合取。若干个原子命题或其否定的合取。大项大项大项大项(large item)/large item)/析取式析取式析取式析取式(disjunctive form):disjun

47、ctive form):若干个原子命题或其否定的析取。若干个原子命题或其否定的析取。若干个原子命题或其否定的析取。若干个原子命题或其否定的析取。析取范式析取范式析取范式析取范式(disjunctive normal form)disjunctive normal form)：若干个小项的析取。若干个小项的析取。若干个小项的析取。若干个小项的析取。合取范式合取范式合取范式合取范式(conjunctive normal form)conjunctive normal form)：若干个大项的合取。若干个大项的合取。若干个大项的合取。若干个大项的合取。对偶与范式对偶与范式5858定理的证明思路：定理

48、的证明思路：1 1、消去对、消去对、消去对、消去对 、来说冗余的联结词；来说冗余的联结词；来说冗余的联结词；来说冗余的联结词；2 2、将否定联结词移到命题变量的前面；、将否定联结词移到命题变量的前面；、将否定联结词移到命题变量的前面；、将否定联结词移到命题变量的前面；3 3、消除多余的否定联结词；、消除多余的否定联结词；、消除多余的否定联结词；、消除多余的否定联结词；4 4、利用分配律化成合取范式和析取范式。、利用分配律化成合取范式和析取范式。、利用分配律化成合取范式和析取范式。、利用分配律化成合取范式和析取范式。定理定理定理定理1 1：任意一个命题公式都存在与之等价的：任意一个命题公式都存在

49、与之等价的：任意一个命题公式都存在与之等价的：任意一个命题公式都存在与之等价的 合取范式和析取范式。合取范式和析取范式。合取范式和析取范式。合取范式和析取范式。范式存在定理范式存在定理范式存在定理范式存在定理对偶与范式对偶与范式5959令令令令A(aA(a1 1、a a2 2、a an n)是包含有是包含有是包含有是包含有n n个变量的公式，个变量的公式，个变量的公式，个变量的公式，极小项极小项极小项极小项(extremal)extremal):小项中恰包含小项中恰包含小项中恰包含小项中恰包含n n个变量或其否定。个变量或其否定。个变量或其否定。个变量或其否定。极大项极大项极大项极大项(ext

50、remal)extremal):大项中恰包含大项中恰包含大项中恰包含大项中恰包含n n个变量或其否定。个变量或其否定。个变量或其否定。个变量或其否定。主析取范式主析取范式主析取范式主析取范式(Unique disjunctive normal form)Unique disjunctive normal form):若干个若干个若干个若干个极小项极小项极小项极小项的析取。的析取。的析取。的析取。主合取范式主合取范式主合取范式主合取范式(Unique conjunctive normal form)Unique conjunctive normal form):若干个若干个若干个若干个极大项极大