离散数学PPT完整全套教学课件

2023/7/41第1章1命题及联结词第1章2命题公式翻译真值表第1章3真值表与等价公式第1章4蕴含与范式第1章5范式第1章6命题逻辑的推理第2章1谓词与量词第2章2谓词翻译第2章3谓词等价式第2章4谓词推理第3章1集合第4章1笛卡尔积与关系第4章2关系的性质关系的复合第4章3关系的运算第4章4等价关系与等价类第4章5相容关系第4章6偏序关系第4章7函数的概念第4章8函数运算第4章9基数第5章1代数系统的概念第5章2半群第5章3群与子群第5章4阿贝尔群循环群置换群第5章5陪集拉格朗日定理第6章1图的基本概念第6章2图中的路与图的连通性第6章3图的矩阵表示第7章1欧拉图第7章2汉密尔顿图第7章3二分图第7章4平面图第7章5图的着色第8章1无向树与生成树第8章2根数及其应用2023/7/421931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。从广义上讲，数理逻辑包括四论、两演算——即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书也只研究这两个演算。数理逻辑(MathematicalLogic)2023/7/43判断命题的两个步骤：是否为陈述句；是否有确定的、唯一的真值。例判断下列句子是否为命题。(1)今天天气多好啊！(2)请你关上门.(3)Howdoyoudo?

(4)3+3=8.

(5)吸烟有害健康。T感叹句，不是命题祈使句，不是命题疑问句，不是命题F1.1

命题及其表示方法2023/7/44(6)太阳从西方升起。(7)x+3>9(8)1+101=110(9)今天是星期三当且仅当2+2=4。(10)如果太阳从西方升起，那么2是奇数。

(11)今年国庆是晴天。

(12)明天我去看电影。(13)宇宙中有外星人。(14)我正在说谎。不是命题二进制中为真，十进制中为假FT是命题，其真值到国庆就知道是命题，客观上能判断真假悖论，不是命题F是命题，客观上能判断真假1.1

命题及其表示方法2023/7/45说明只有具有确定真值的陈述句才是命题。一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”。“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。如上例中的(11)(12)(13).1.1

命题及其表示方法2023/7/46二、命题的表示方法在本书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3,…,或数字(1),[2],…,等表示命题，称之为命题标识符(PropositionIdentifier)。例如P：这节课是数学课

Q：5是负数。

P3：明天天气晴。

(2)：太阳从西方升起。皆为符号化的命题，其真值依次为1、0、1或0、0。1.1

命题及其表示方法2023/7/47命题常量(PropositionConstant)：表示确定命题的命题标识符。命题标识符又有命题常量、命题变元和原子变元之分。命题变元(PropositionValiable)

：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。原子变元(AtomicValiable)：当命题变元表示原子命题时，该变元称为原子变元。1.1

命题及其表示方法2023/7/48注意：一个符号(如P)，它表示的是命题常量还是命题变元，一般由上下文来确定。命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与“变数x不是数”是一样的道理。1.1

命题及其表示方法2023/7/49简单命题(SimpleProposition)/原子命题(AtomicProposition)/本原命题(PrimitiveProposition)：不能分解为更简单的陈述语句的命题(如上例中的命题)。三、命题的分类复合命题(CompoundProposition)

：由简单命题通过联结词联结而成的命题。联结词就是复合命题中的运算符。1.1

命题及其表示方法2023/7/410四、小结本节主要要求大家掌握命题的定义怎样判定一句话到底是不是命题命题的分类真值原子命题、复合命题1.1

命题及其表示方法2023/7/411离散数学

(DiscreteMathematics)2023/7/4121.2命题联结词(LogicalConnectives)否定联结词(Negation)合取联结词(Conjunction)析取联结词(Disjunction)条件联结词(蕴涵联结词Conditional)双条件联结(等值联结词Biconditional)小结2023/7/413一、否定联结词(Negation)¬在命题逻辑中，主要研究的是复合命题，而复合命题是由原子命题与逻辑联结词组合而成，联结词是复合命题的重要组成部分。定义1-2.1

设P为一命题，P的否定是一个新的复合命题，称为P的否定式，记作“¬P”，读作“非P”，符号“¬”

称为否定联结词。¬P为真当且仅当P为假.1.2

命题联结词(LogicalConnectives)2023/7/414联结词“¬”的定义真值表P¬P0110“¬”属于一元运算符.1.2

命题联结词(LogicalConnectives)2023/7/415例1P：西安是一个城市.Q：3是偶数.则

¬P：西安不是一个城市.

¬Q：3不是偶数.例2P：西安处处清洁.¬P的含义是什么？

A:西安处处不清洁

B:西安不处处清洁1.2

命题联结词(LogicalConnectives)2023/7/416例3

Q：在座的都是男同学.¬Q的含义是什么？

A:在座的各位不都是男同学。

B:在座的各位都不是男同学。1.2

命题联结词(LogicalConnectives)2023/7/417二、合取联结词(Conjunction)PQP∧Q

000010100111定义1-2.2

设P,Q为命题，复合命题“P并且Q”(或“P与Q”)称为P与Q的合取式，记作P∧Q，符号“∧”称为合取联结词。当且仅当P和Q同时为真时P∧Q为真。联结词“∧”的定义真值表1.2

命题联结词(LogicalConnectives)2023/7/418“∧”属于二元(binary)运算符.合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”、“…和…”、“…与…”等都可以符号化为∧。1.2

命题联结词(LogicalConnectives)2023/7/41919例3

将下列命题符号化.(1)张三既聪明又用功.

(2)张三虽然聪明，但不用功.(3)张三不但聪明，而且用功.(4)张三不是不聪明，而是不用功.不要见到“与”或“和”就使用联结词∧。例如:“我与你是兄弟”是合取式吗？

A:是B：不是，是原子命题

解解设P：张三聪明。Q：张三用功。1.2

命题联结词(LogicalConnectives)则(2)P∧¬Q(3)P∧Q(4)¬(¬P)∧¬Q(1)P∧Q2023/7/420“∧”与自然语言中“与”“和”的不同之处：1.2

命题联结词(LogicalConnectives)(2)自然语言中有时在各种不同意义上使用联结词“与”，“和”，不能一概用表示，有时是原子命题。2023/7/421三、析取联结词(Disjunction)∨PQP∨Q000011101111定义1-2.3

设P,Q为命题，复合命题“P或Q”称为P与Q的析取式，记作P∨Q，符号∨称为析取联结词.P∨Q为真当且仅当P与Q中至少有一个为真.联结词“∨”的定义真值表1.2

命题联结词(LogicalConnectives)2023/7/422“∨”属于二元(binary)运算符.析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。由析取联结词的定义可以看出，“∨”与汉语中的联结词“或”意义相近，但又不完全相同。在现代汉语中，联结词的“或”实际上有“可兼或”和“排斥或”之分。考察下面命题：(1)小王爱打球或爱跑步。设P：小王爱打球。Q：小王爱跑步。1.2

命题联结词(LogicalConnectives)（可兼或）则上述命题可符号化为：P∨Q2023/7/423(4)人固有一死，或重于泰山或轻于鸿毛.(2)张三学过英语或法语。设P：张三学过英语。Q：张三学过法语(3)派小王或小李中的一人去开会。设P：派小王去开会。Q：派小李去开会。(5)ab=0,即a=0或b=0.由此可见,“P∨Q”表示的是“可兼或”.则上述命题可符号化为：P∨Q则上述命题可符号化为：(P∧¬Q)∨(¬P∧Q)1.2

命题联结词(LogicalConnectives)（可兼或）（排斥或）（排斥或）（可兼或）2023/7/424注意：当P和Q客观上不能同时发生时，“P或Q”可以符号化为“P∨Q”。“∨”与自然语言中“或”的不同之处：例如：小王现在在宿舍或在图书馆。设P：小王现在在宿舍。Q：小王现在在图书馆。则上述命题可符号化为：P∨Q。1.2

命题联结词(LogicalConnectives)

1、不能看到或就写成析取

2、或有时可以表示“约数”，要注意区分“小王或小李有且仅有一个是大学生”A:可兼或B:排斥或2023/7/425四、条件联结词(蕴涵联结词Conditional)→PQP→

Q001011100111定义1-2.4

设P,Q为命题，复合命题“如果P那么Q(若P则Q)”称为P与Q的条件命题，记作PQ.PQ为假当且仅当P为真且Q为假。称符号“”为条件联结词。并称P为前件，Q为后件.联结词“”的定义真值表1.2

命题联结词(LogicalConnectives)2023/7/426

如果天下雨，那么地面湿。设P：天下雨。Q：地面湿。1.2

命题联结词(LogicalConnectives)PQP→Q0001101111012023/7/427PQ表示的基本逻辑关系是：Q是P的必要条件或P是Q的充分条件.因此复合命题“只要P就Q”、“因为P，所以Q”、“仅当Q则P”、“当P则Q”、“只有Q才P”等都可以符号化为PQ的形式。“”属于二元(binary)运算符。例5

将下列命题符号化。(1)天不下雨，则草木枯黄。设P：天下雨。Q：草木枯黄。则原命题可表示为：¬P→Q。1.2

命题联结词(LogicalConnectives)2023/7/428(2)如果小明学日语，小华学英语，则小芳学德语。

设P：小明学日语Q：小华学英语R：小芳学德语(3)只要不下雨，我就骑自行车上班。(4)只有不下雨，我才骑自行车上班。设P：天下雨。Q：我骑自行车上班。设P：天下雨。Q：我骑自行车上班。则原命题可表示为：(P∧Q)→R则原命题可表示为：¬P→Q则原命题可表示为：Q→¬P。1.2

命题联结词(LogicalConnectives)2023/7/429例6

设P：2+2=4

Q：太阳从东方升起R：太阳从西方升起符号化下列命题，并判断命题的真值：(1)如果2+2=4，则太阳从东方升起。(2)如果2+2=4，则太阳从西方升起。(3)如果2+2≠4，则太阳从东方升起。(4)如果2+2≠4，则太阳从西方升起。解(1)P→Q，T1.2

命题联结词(LogicalConnectives)(2)P→R，F(3)¬P→Q，T(4)¬P→R，T2023/7/430注意:与自然语言的不同：前件与后件可以没有任何内在联系！在数学中，“若P则Q”往往表示前件P为真，则后件Q为真的推理关系.但数理逻辑中，当前件P为假时，P→Q的真值为真。1.2

命题联结词(LogicalConnectives)2023/7/431五、双条件联结词(等值联结词Biconditional)PQPQ001010100111定义1-2.5设P,Q为命题，复合命题“P当且仅当Q”称为P与Q的双条件命题，记作PiffQ或PQ，符号称为双条件（等值）联结词。PQ为真当且仅当P与Q的真值相同。联结词“”的定义真值表1.2

命题联结词(LogicalConnectives)2023/7/432“P当且仅当Q”可译为说明:1.2

命题联结词(LogicalConnectives)PQ“”属于二元(binary)运算符。双条件命题PQ所表达的逻辑关系是，P与Q互为充分必要条件，相当于(PQ)∧(QP).只要P与Q的真值同为1或同为0，PQ的真值就为1，否则PQ的真值为0。双条件联结词连接的两个命题之间可以没有因果关系。2023/7/433例6

分析下列命题的真值(P:2+2=4Q:3是奇数)(1)2+2=4当且仅当3是奇数.(2)2+2=4当且仅当3不是奇数.(3)2+2≠4当且仅当3是奇数.(4)2+2≠4当且仅当3不是奇数.P¬Q，约定:运算次序优先级：¬，，，→，.相同的运算符按从左至右次序计算，否则要加上括号。最外层圆括号可省去。PQ，¬PQ，¬P¬Q，1.2

命题联结词(LogicalConnectives)TFFT2023/7/434六、小结本节介绍了五种联结词(¬，，，→，)。重点是理解和掌握五种联结词的内涵及它们与自然语言中相应联结词的不同之处.1.2

命题联结词(LogicalConnectives)2023/7/435离散数学

(DiscreteMathematics)命题公式与翻译2023/7/4361.3命题公式与翻译命题公式的定义复合命题的符号化(翻译)小结2023/7/437一、命题公式(PropositionFormula)的定义定义1-3.1

单个命题变元和命题常量称为原子公式。定义1-3.2

命题演算的合式公式(wff：Well-formedformula)，规定为：(1)原子公式是合式公式。(2)若A是合式公式，则(¬A)也是合式公式。(3)若A，B是合式公式，则(A∧B)，(A∨B)，(AB)，(AB)也是合式公式。(4)当且仅当有限次地应用(1)~(3)所得到的包含原子公式、联结词和括号的符号串是合式公式。1.3命题公式与翻译2023/7/438命题演算的合式公式是由命题变元、命题常量、联结词和圆括号按一定的逻辑关系联结起来的符号串，是以递归的形式来定义的合式公式也称为命题公式，并简称为公式。命题公式一般不是命题，仅当公式中的命题变元用确定的命题代入时，才得到一个命题。其真值依赖于代换变元的那些命题的真值。1.3命题公式与翻译2023/7/4391.3命题公式与翻译约定：运算次序优先级：¬，，，→，.相同的运算符按从左至右次序计算，否则要加上括号。最外层圆括号可省去。2023/7/440例1

指出(P→(PQ))是否是命题公式，如果是，则具体说明。解①P是wff由(1)②Q是wff由(1)③PQ是wff由(3)④(P→(PQ))由(3)例2(PQ),(R∧S)∨¬Q,P，¬P等均为合式公式，而PQ∨S,(PW)Q)等不是合式公式。1.3命题公式与翻译2023/7/441二、复合命题的符号化(翻译)有了命题演算的合式公式的概念，我们可以把自然语言中的有些语句(复合命题)，翻译成数理逻辑中的符号形式。基本步骤如下：(1)分析出各原子命题，将它们符号化；(2)使用合适的联结词，把简单命题逐个的联结起来，组成复合命题的符号化表示.1.3命题公式与翻译2023/7/442例3

符号化下列命题：(1)尽管他有病，但他仍坚持工作。设P：他有病。Q：他坚持工作。则该命题可以表示为：P∧Q(2)说数理逻辑枯燥无味或毫无价值，那是不对的。设P：数理逻辑枯燥无味。Q：数理逻辑毫无价值。则该命题可以表示为：¬(P∨Q)(3)张三与李四组成一个学习小组。设P：张三与李四组成一个学习小组。则该命题可以表示为：P1.3命题公式与翻译2023/7/443(4)假如上午不下雨，我去看电影，否则就在家里读书或看报。设P：上午下雨。Q：我去看电影。R：我在家读书。S：我在家看报。则该命题可以表示为：(¬PQ)∧(P(R∨S))(5)除非你通知我，否则我不开会。设P：你通知我。Q：我开会。则该命题可以表示为：

A:¬P¬Q

B:PQ

1.3命题公式与翻译除非=如果不2023/7/444(6)除非你努力，否则你将失败。设P：你努力。Q：你将失败。则该命题可以表示为：A:

P¬Q

B:

¬PQ1.3命题公式与翻译除非=如果不2023/7/445(7)一个人起初说：“占据空间的、有质量的而且不断变化的叫做物质”；后来他改说：“占据空间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。设P：它占据空间。Q：它有质量。R：它不断变化。W：它是物质。则第一句话可表示为：(P∧Q∧R)W第一句话可表示为：(P∧QW)∧(WR)(8)只要我还有一口气，我就要战斗。设P：我有一口气。Q：我要战斗。

则该命题可以表示为：PQ1.3命题公式与翻译2023/7/446(9)只要功夫深，铁杵磨成针。设P：功夫深。Q：铁杵磨成针。则该命题可以表示为：PQ(10)只有睡觉才能恢复体力。设P：睡觉。Q：恢复体力。则该命题可以表示为：QP(11)小王晚上回家，除非下大雨。设P：小王晚上回家。Q：下大雨。则该命题可以表示为：¬QP1.3命题公式与翻译(12)若要人不知，除非己莫为。设P：人知。Q：己为。则该命题可以表示为：QP2023/7/447(13)除非天气好，我才骑自行车上班。设P：天气好。Q：我骑自行车上班。则该命题可以表示为：¬P¬Q(14)除非你陪我或代我叫辆车子，否则我不出去。设P：你陪我。Q：你代我叫辆车。R：我出去。则该命题可以表示为：¬(P∨Q)¬R1.3命题公式与翻译(15)天黑了，我得回家了。设P：天黑了。Q：我回家。则该命题可以表示为：PQ2023/7/448(16)北京到上海的14次列车是下午5点半开或6点开。设P：北京到上海的14次列车是下午5点半开。

Q：北京到上海的14次列车是下午6点开。1.3命题公式与翻译PQP☆Q0001101101101001P☆Q2023/7/449(17)张三与李四有且仅有一人是大学生。设P：张三是大学生。Q：李四是大学生。则该命题可以表示为：¬(PQ)(18)张三正在游泳或正在睡觉。设P：张三正在游泳。Q：张三正在睡觉。则该命题可以表示为：¬(PQ)(19)天黑了，我得回家了。设P：天黑了。Q：我回家。则该命题可以表示为：PQ1.3命题公式与翻译2023/7/450三、小结本节介了命题公式的概念及复合命题的符号化。重点是理解命题公式的递归定义，掌握复合命题的符号化方法.翻译的步骤：找出原子命题，分析逻辑关系，找出合适的联结词，注意括号。重点是条件式的翻译只要，只有，除非，每当，仅当，当且仅当1.3命题公式与翻译2023/7/451离散数学

(DiscreteMathematics)2023/7/4PQ000110110110101110001.4真值表与等价公式复习符号化命题：我们不能既划船又跑步P：我们划船Q：我们跑步翻译

A:

B:

C:2023/7/4PQP☆Q000110111.4真值表与等价公式复习符号化命题：或者你没给我写信或者信丢了P：你给我写信了Q：信丢了A:

B:

10012023/7/4541.4真值表与等价公式真值表(TruthTable)等价公式(PropositionalEquivalences)小结2023/7/455一、真值表定义1-4.1

设P1,P2,…,Pn是出现在公式A中的全部的命题变元，给P1,P2,…,Pn

各指定一个真值，称为对A的一个真值指派或赋值(Assigment)或解释。若指定的一组值使A的真值为真(假)，称这组值为A的成真(假)指派.前面在定义联结词时，曾经使用过真值表，本节给出真值表的定义。1.4真值表与等价公式2023/7/456比如:对公式(PQ)∧R，赋值011(即令P=0，Q=1，R=1)为(PQ)∧R的成真赋值；另一组赋值010为(PQ)∧R的成假赋值；还有000，001，111……考虑：含有n个命题变元的公式共有多少组不同的赋值？定义1-4.2

在命题公式A中，对于命题变元的每一种可能的真值指派和由它们所确定的命题公式A的真值列成表，称做命题公式A的真值表。1.4真值表与等价公式2023/7/457对公式A构造真值表的具体步骤为：(1)找出公式中所有命题变元P1,P2,…,Pn。

(2)按从小到大的顺序列出命题变元P1,P2,…,Pn的全部2n组赋值。(3)对应各组赋值计算出公式A的真值，并将其列在对应赋值的后面。1.4真值表与等价公式2023/7/458PQPQ¬(PQ)¬P¬Q¬(PQ)(¬P¬Q)00011011例1给出¬(PQ)(¬P¬Q)的真值表。1.4真值表与等价公式00011110111011112023/7/459PQRPQ(PQ)∧R000001010011100101110111例2构造公式(PQ)∧R的真值表。1.4真值表与等价公式11110011010100012023/7/4601.4真值表与等价公式练习1构造公式(PQ)(¬Q¬P)的真值表。练习2构造公式¬(PQ)∧Q的真值表。2023/7/461练习1构造公式(PQ)(¬Q¬P)的真值表。PQ¬P¬QPQ¬Q¬P(PQ)(¬Q¬P)000110111.4真值表与等价公式110010101101110111112023/7/462PQ

P

Q¬(P

Q)¬(P

Q)∧Q00011011练习2构造公式¬(PQ)∧Q的真值表。1.4真值表与等价公式1101001000002023/7/463给定n个命题变元，按合式公式的形成规则可以形成无数多个命题公式,但这些无穷尽的命题公式中，有些具有相同的真值表。考虑：由n个命题变元能生成多少种真值(表)不同的命题公式？二、等价公式1.4真值表与等价公式PQA

000110112023/7/464定义1-4.3

给定两个命题公式A和B，设P1,P2,…,Pn为出现于A和B中的所有原子变元，若给P1,P2,…,Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等，记作AB。“”不是逻辑联结词.命题公式之间的逻辑相等关系具有：

(1)自反性：AA；

(2)对称性：若AB，则BA；

(3)传递性：若AB且BC，则AC。1.4真值表与等价公式2023/7/465PQPQQ→PP→Q(P→Q)(Q→P)00011011证明公式等价的方法：真值表法等值演算法1、真值表法

例3

证明:PQ(P→Q)(Q→P)1.4真值表与等价公式10011011110110012023/7/466例4

判断公式P(QR)、(P∧Q)R是否等价。PQRP∧QQRP(QR)(P

∧

Q)R000001010011100101110111由真值表可知，两个公式为等价式。1.4真值表与等价公式000000111111110111011101111111012023/7/4672、等值演算法(EquivalentCaculation)命题定律即常见的等价式：1.4真值表与等价公式2023/7/4682、等值演算法(EquivalentCaculation)重要的等价式(补充)：14.双条件否定等价式：PQ¬P¬Q15.归谬律：(PQ)(P¬Q)¬P1.4真值表与等价公式PQPQ¬P¬Q¬P¬Q0011110101001000101110012023/7/469置换/替换规则(RuleofReplacement)：等值演算中使用的一条重要规则。定义1-4.4(子公式)如果X是wffA的一部分，且X本身也是wff，则称X是A的子公式(Subformula)。例如，P(PQ)为Q(P(PQ))的子公式。1.4真值表与等价公式2023/7/470定理1-4.1(置换定理Axiomofreplacement)

设X是wffA的子wff，若XY，则若将A中的X用Y来置换，所得公式B与A等价，即AB。证：因为对变元的任一指派，X与Y真值相同，所以Y取代X后，公式B与公式A对变元的任一指派真值也相同，所以AB。□满足定理1-4.1条件的置换称为等价置换(或等价代换).定义1-4.5(等值演算)

根据已知的等价公式，推演出另外一些等价公式的过程称为等值演算.1.4真值表与等价公式2023/7/471例6

证明(P¬Q)Q

PQ例5证明Q→(P(PQ))Q→P证Q→(P(PQ))Q→P(吸收律)证

(P¬Q)Q(PQ)(¬QQ)(PQ)TPQ1.4真值表与等价公式2023/7/472例7证明（P→Q）→（QR）

PQR证(P→Q)→(QR)

(¬PQ)→(QR)¬(¬PQ)(QR)(P¬Q)(QR)

(PQR)(¬QQR)

PQR1.4真值表与等价公式2023/7/473例8验证P(QR)(P

∧

Q)R练习：(1)((PQ)∧(PR))P(Q

∧R)(2)(P∧¬Q)∨(¬P∧

Q)(P∨

Q)∧¬(P∧

Q)证(P

∧

Q)R¬(P

∧

Q)∨R¬P

∨¬Q

∨R¬P

∨(¬Q

∨R)¬P

∨(QR))P(QR)1.4真值表与等价公式2023/7/474等值演算在计算机硬件设计中,在开关理论和电子元器件中都占有重要地位.三、小结

本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。1.4真值表与等价公式2023/7/475离散数学

(DiscreteMathematics)2023/7/4761.5重言式与蕴含式命题公式的分类重言式(Tautology)的性质蕴含式(Implication)小结2023/7/477命题公式的分类重言式(Tautology)/永真式矛盾式(Contradiction)/永假式(Absurdity)可满足式(Satisfactory)仅可满足式/偶然式(Contingency)1.5重言式与蕴含式2023/7/478定义1.5.1

设A为任一命题公式，(1)若A在其各种赋值下的取值均为真，则称A是重言式或永真式，记为T或1。(2)若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式，记为F或0。(3)若A不是矛盾式则称A为可满足式。(4)既不是重言式，也不是矛盾式，称为仅可满足式或偶然式。1.5重言式与蕴含式2023/7/479判别命题公式的类型的方法:真值表法等值演算法：将所给命题公式通过等值演算化为最简单的形式,然后再进行判别.(重言式)例1判别下列命题公式的类型.(1)Q∨¬((¬P∨Q)∧P)(2)(P∨¬P)(Q∧¬Q)∧R(3)(PQ)∧¬P(矛盾式)(可满足式)1.5重言式与蕴含式2023/7/480重言式的性质定理1.5.1

任何两个重言式的合取或析取，仍然是一重言式.证明设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故A∧BT，A∨BT1.5重言式与蕴含式2023/7/481定理1.5.2

一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。证明：由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。1.5重言式与蕴含式2023/7/482定理1.5.3

A，B是两个命题公式，AB的充要条件是AB为重言式。证明若AB为重言式，则AB永为T，即A，B的真值表相同，所以AB。反之，若AB，则A，B真值表相同，所以AB永为T，从而AB为重言式。1.5重言式与蕴含式PQ001110111110001111112023/7/483蕴含式(Implication)定义1.5.2

当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作PQ.设原命题为PQ，则逆换式：QP反换式：¬P¬Q逆反式：¬Q¬P1.5重言式与蕴含式2023/7/484它们之间具有如下关系:PQ

¬Q¬PQP

¬P¬Q证明PQ的三种方法：真值表法：即列出PQ的真值表，观察其是否为永真。直接证法：假定前件P是真，推出后件Q是真。间接证法：假定后件是假，推出前件是假，即证¬Q¬P。1.5重言式与蕴含式PQ0010111001112023/7/485例1

证明¬Q（P→Q）¬P证法1：真值表法(略)证法2：若¬Q(P→Q)为真，证法3：若¬P为假，则P为真，再分二种情况：①若Q为真，则¬Q为假，从而¬Q(P→Q)为假；②若Q为假，则P→Q为假，从而¬Q(P→Q)为假，根据①②，有¬Q(P→Q)¬P。1.5重言式与蕴含式则¬Q，P→Q为真，所以Q为假，P为假，所以¬P为真。2023/7/486P21表1-5.2给出了14个蕴含式。1.5重言式与蕴含式1PQP化简式2PQQ化简式3PPQ附加式4¬PPQ5QPQ6¬(PQ)P7¬(PQ)¬Q2023/7/487P21表1-5.2给出了14个蕴含式。1.5重言式与蕴含式8P(PQ)Q假言推理9¬Q(PQ)¬P拒取式10¬P(PQ)Q析取三段论11(PQ)(QR)PR假言三段论12(PQ)(PR)(QR)R二难推理13(PQ)(RS)(PR)(QS)14(PQ)(QR)PR等价三段论2023/7/488等价式与蕴含式的关系：定理1.5.4

设P，Q为任意两个命题公式，PQ的充要条件为PQ且QP.证若PQ，则PQ为永真式，因为PQ（P→Q）（Q→P），所以P→Q，Q→P为永真式，从而PQ，QP.反之，若PQ，QP，则P→Q，Q→P为永真式，所以（P→Q）（Q→P）为永真式，从而PQ为永真式，即PQ.1.5重言式与蕴含式2023/7/489蕴含的性质：设A，B，C为任意wff,(1)若AB，且A为永真式，则B必为永真式.(2)若AB，BC，则AC.(3)若AB，AC，则ABC.(4)若AB且CB，则ACB.1.5重言式与蕴含式2023/7/490小结本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。重点掌握：(1)用等值演算法判别命题公式的类型。(2)重言式、矛盾式与蕴涵式的性质。(3)等价式与蕴涵式的关系。1.5重言式与蕴含式2023/7/491离散数学

(DiscreteMathematics)2023/7/492复习1.5重言式与蕴含式判断公式类型：Q∨¬((¬P∨Q)∧P)2023/7/493蕴含式(Implication)定义1.5.2

当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作PQ.设原命题为PQ，则逆换式：QP反换式：¬P¬Q逆反式：¬Q¬P1.5重言式与蕴含式2023/7/494它们之间具有如下关系:PQ

¬Q¬PQP

¬P¬Q证明PQ的三种方法：真值表法：即列出PQ的真值表，观察其是否为永真。直接证法：假定前件P是真，推出后件Q是真。间接证法：假定后件是假，推出前件是假，即证¬Q¬P。1.5重言式与蕴含式PQ0010111001112023/7/495例1

证明¬Q（P→Q）¬P证法1：真值表法(略)证法2：若¬Q(P→Q)为真，证法3：若¬P为假，则P为真，再分二种情况：①若Q为真，则¬Q为假，从而¬Q(P→Q)为假；②若Q为假，则P→Q为假，从而¬Q(P→Q)为假，根据①②，有¬Q(P→Q)¬P。1.5重言式与蕴含式则¬Q，P→Q为真，所以Q为假，P为假，所以¬P为真。2023/7/41.5重言式与蕴含式2023/7/41.5重言式与蕴含式2023/7/41.5重言式与蕴含式2023/7/499等价式与蕴含式的关系：定理1.5.4

设P，Q为任意两个命题公式，PQ的充要条件为PQ且QP.证若PQ，则PQ为永真式，因为PQ（P→Q）（Q→P），所以P→Q，Q→P为永真式，从而PQ，QP.反之，若PQ，QP，则P→Q，Q→P为永真式，所以（P→Q）（Q→P）为永真式，从而PQ为永真式，即PQ.1.5重言式与蕴含式2023/7/4100蕴含的性质：设A，B，C为任意wff,(1)若AB，且A为永真式，则B必为永真式.(2)若AB，BC，则AC.(3)若AB，AC，则ABC.(4)若AB且CB，则ACB.1.5重言式与蕴含式2023/7/4101小结本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。重点掌握：(1)用等值演算法判别命题公式的类型。(2)重言式、矛盾式与蕴涵式的性质。(3)等价式与蕴涵式的关系。1.5重言式与蕴含式2023/7/4102离散数学

(DiscreteMathematics)2023/7/41031.6其它联结词不可兼析取(排斥或/异或)(Exclusiveor)与非联结词(Nand)或非联结词(Nor)条件否定联结词(Non-conditional)最小联结词组(Theminimalsetofconnectives)小结2023/7/4104在第二节(1.2)中我们定义了五种基本的联结词¬，，，，，但在命题逻辑中，这些联结词还不能很广泛地直接表达命题之间的联系(例如,“P异或Q”只能间接地表示为(P¬Q)(¬PQ)，为此本节再给出逻辑设计中常用的另外四种联结词.1.6

其它联结词2023/7/4105一、不可兼析取/排斥或/异或(Exclusive-OR，)定义1.6.1

设P、Q为两个命题，复合命题“P、Q之中恰有一个为真”称为P与Q的不可兼析取，记作PQ，符号“”称为异或联结词。PQ为真当且仅当P和Q的真值不同.PQP

Q0000111011101.6

其它联结词2023/7/4106例派小王或小李中的一人去开会。（排斥或）定义了联结词“”后，命题逻辑中的有些命题就可以符号化为非常简捷的形式.设P：派小王去开会。Q：派小李去开会。则上述命题可符号化为：PQ1.6

其它联结词2023/7/4107“”属于二元(binary)运算符。1.6其它联结词联结词的性质：设P，Q，R为命题公式，则有(1)PQQP(交换律)(2)(PQ)RP(QR)(结合律)(3)P∧(QR)(P∧Q)(P∧R)(分配律)(4)(PQ)(P∧¬Q)∨(¬P∧Q)(5)(PQ)

¬(PQ)(6)PPF,FPP,TP

¬P2023/7/4108定理1.6.1

设P，Q，R为命题公式，

如果PQR，则PRQ，QRP，且PQR为一矛盾式.证如果PQR，则

PRP(PQ)(PP)QFQQQRQ(PQ)FPPPQRRRF1.6其它联结词2023/7/4109条件否定联结词(Non-conditional，)定义1.6.2

设P，Q为二命题，复合命题“PQ”称为命题P与Q的条件否定式PQ为真当且仅当P为真且Q为假.1.6其它联结词PQPQ000010101110由定义可知，PQ¬(PQ)“”属于二元(binary)运算符.2023/7/4110与非联结词(NAND，↑)PQP↑Q001011101110定义1.6.2

设P,Q为二命题，复合命题“P与Q的否定”称为P与Q的与非式，记作P↑Q，符号“↑”称为与非联结词。P↑Q为真当且仅当P和Q不同时为真.1.6其它联结词与全功能集2023/7/4111由定义可知，P↑Q¬(P∧Q)“↑”属于二元(binary)运算符联结词“↑”的性质：(1)P↑P¬(P∧P)¬P(2)(P↑Q)↑(P↑Q)¬(P↑Q)(P∧Q)

(3)(P↑P)↑(Q↑Q)¬P↑¬Q¬(¬P∧¬Q)P∨Q1.6其它联结词2023/7/4112定义1.6.3

设P,Q为二命题，复合命题“P或Q的否定”称为P与Q的或非式，记作P↓Q，符号“↓”称为或非联结词.P↓Q为真当且仅当P与Q同为假.PQP↓Q001010100110或非联结词(NOR，↓)1.6其它联结词2023/7/4113由定义可知，P↓Q¬(P∨Q)“↓”属于二元(binary)运算符联结词“↓”的性质：(1)P↓P¬(P∨P)¬P(2)(P↓Q)↓(P↓Q)¬(P↓Q)(P∨Q)(3)(P↓P)↓(Q↓Q)¬P↓¬Q¬(¬P∨¬Q)P∧Q1.6其它联结词2023/7/4114至此，对于一元和二元逻辑运算，我们一共定义了9个联结词，为了直接表达命题之间的联系，是否还需要定义其它联结词呢?如果不需要定义其他联结词，那这9个联结词是否都是必须的？哪些是必须的？五、联结词全功能集(Theminimalsetofconnectives)1.6其它联结词下面以含两个命题变元P、Q的所有互不等价的命题公式为例，来说明这一问题。2023/7/4115PQFP∧QP→QPQ→PQPQP∨Q0000000000010000111110001100111101010101PQP↓QPQ¬QQ→P¬PP→QP↑QT0011111111010000111110001100111101010101由两个命题变元P，Q所构成的互不等价的24个命题公式如下：1.6其它联结词2023/7/4116

由上表可知，9个联结词足以直接表达命题之间的各种联系，所有的逻辑含义，均可由这9个联结词直接表达，不需要定义其他联结词。1.6其它联结词在二元运算中，9个联结词并不都是必要的。为此，我们定义最小联结词组。2023/7/4117定义1.6.5

一个联结词集合，如果用其中联结词足以把任何命题公式等价地表示出来，而去掉其中任何一个联结词则不能，我们称这个联结词集合为联结词全功能集(Theminimalsetofconnectives)联结词全功能集具有：(1)完备性(2)最小性1.6其它联结词2023/7/4118对于9个联结词的集合{¬,,,,,,↑,↓,}，(1)PQ(P→Q)(Q→P)(2)PQ¬PQ(3)PQ¬(¬P¬Q)(4)PQ¬(¬P¬Q)(5)(PQ)¬(PQ)(6)P↑Q¬(P∧Q)(7)P↓Q¬(P∨Q)(8)PQ¬(PQ)1.6其它联结词2023/7/4119任意命题公式都可由仅包含{¬，}或{¬，

}的命题公式等价代换，即9个联结词的集合中至少有七个冗余联结词。而联结词{¬，}和{¬，

}不再有冗余联结词，故{¬，}或{¬，

}为最小联结词组。实际中为了使用方便,命题公式常常同时包含{¬，，

}.1.6其它联结词其他最小联结词组：{↑}，{↓}，{¬，→}，{¬，}2023/7/4120¬P¬(PP)P↑PPQ¬¬(PQ)¬(P↑Q)(P↑Q)↑(P↑Q)PQ¬(¬P¬Q)¬((P↑P)(Q↑Q))(P↑P)↑(Q↑Q)例1试证{↑}是最小联结词组.证例2

试证{¬，→}是最小联结词组证1.6其它联结词PQ¬(¬P¬Q)¬(P→¬Q)PQ¬(¬P)Q¬P→Q2023/7/4121本节主要介绍了四种新的联结词及最小联结词组.小结1.6其它联结词2023/7/4122离散数学

(DiscreteMathematics)2023/7/41231.7对偶与范式(Dual&NormalForm)对偶式与对偶原理(DualisticFormula&DualityPrinciple)命题公式的析(合)取范式(TheDisjunctive&ConjunctiveNormalFormsofaPropositionalFormula)命题公式的主析(合)取范式(ThePrincipalDisjunctive&ConjunctiveNormalFormofaPropositionalFormula)小结2023/7/4124一、对偶式与对偶原理在§1.4中我们给出了命题定律，其中多数等价公式（仅含联结词¬，，）都是成对出现的，每一对公式的不同之处是将与互换，T与F互换，我们把这样的公式称为是对偶的.1.7对偶与范式(Dual&NormalForm)2023/7/4125例11.7对偶与范式(Dual&NormalForm)(¬P(QR))*=¬P(QR)

((PQ)1)*=((PQ)0)

由P↑Q¬(P∧Q)和P↓Q¬(P∨Q)可知

(P↑Q)*=P↓Q定义1.7.1

设命题公式A仅含有联结词¬、、，在A中将、、F、T分别换以、、T、F，得出公式A*，则A*称为A的对偶公式。

(A*)*=A2023/7/4126关于对偶式我们有如下两个定理:定理1.7.1

设A，A*是对偶式，P1，P2，…，Pn是出现于A和A*中的所有原子变元，则(1)¬A(P1,P2,…,Pn)A*(¬P1,¬P2,…,¬Pn)(2)A(¬P1,¬P2,…,¬Pn)¬A*(P1,P2,…,Pn)证明因为¬(PQ)¬P¬Q，¬(PQ)¬P¬Q所以¬A(P1,P2,…,Pn)A*(¬P1,¬P2,…,¬Pn)同理¬A*(P1,P2,…,Pn)A(¬P1,¬P2,…,¬Pn)。1.7对偶与范式(Dual&NormalForm)2023/7/4127定理1.7.2(对偶原理)设A，B为两个仅含有联结词¬，，的命题公式，若AB，则A*B*。证设P1,P2,…,Pn是出现于A和B中的所有原子变元.因为A(P1,P2,…,Pn)B(P1,P2,…,Pn)所以A(P1,P2,…,Pn)B(P1,P2,…,Pn)永真.故A(¬P1,¬P2,…,¬Pn)B(¬P1,¬P2,…,¬Pn)永真.由定理1-7.1得

¬A*(P1,P2,…,Pn)¬B*(P1,P2,…,Pn).因此A*B*。1.7对偶与范式(Dual&NormalForm)2023/7/4128例2

因为

P(PQ)P由对偶原理，有

P(PQ)P.

例3

若A1则A*(1)*即A*0.例4

设A为(PQ)(¬P(¬PQ))，B为¬PQ，且AB，则A*B*即

(PQ)(¬P(¬PQ))

¬PQ。1.7对偶与范式(Dual&NormalForm)2023/7/4129设A，B为两个仅含有联结词¬，，的命题公式，若AB，则B*A*。证设P1，P2，…，Pn是出现于A和B中的所有原子变元.因为A(P1,P2,…,Pn)B(P1,P2,…,Pn)

所以A(P1,P2,…,Pn)→B(P1,P2,…,Pn)永真.从而¬B(P1,P2,…,Pn)→¬A(P1,P2,…,Pn)永真.1.7对偶与范式(Dual&NormalForm)2023/7/4130即B*(¬P1,¬P2,…,¬Pn)→A*(¬P1,¬P2,…,¬Pn)永真.以Pi代¬Pi

(i=1，2………n)，得B*(P1,P2,…,Pn)→A*(P1,P2,…,Pn)永真.所以B*A*.1.7对偶与范式(Dual&NormalForm)

设A，B为两个仅含有联结词¬，，的命题公式，若AB，则B*A*。2023/7/4131二、命题公式的析(合)取范式从前面的讨论可知，存在大量互不相同的命题公式，实际上互为等价，因此，有必要引入命题公式的标准形式，使得相互等价的命题公式具有相同的标准形式。这无疑对判别两个命题公式是否等价以及判定命题公式的类型是一种好方法，同时对命题公式的简化和推证也是十分有益的。1.7对偶与范式(Dual&NormalForm)2023/7/4132定义1.7.2(1)文字：命题变元及其否定统称为文字(如P,¬P).(2)简单析取式：仅有有限个文字组成的析取式。如P，¬PQ，P¬P，QP¬P，P¬QR¬S.(3)简单合取式：仅有有限个文字组成的合取式。如P，¬Q，Q¬P，P¬P，QP¬P，p∧¬Q∧R.一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定式。一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定式。1.7对偶与范式(Dual&NormalForm)2023/7/4133定义1.7.3(1)析取范式：一个命题公式称为析取范式，当且仅当它具有形式：A1∨A2∨……∨An(n大于等于1)其中Ai(i=1,2,3,…n)为简单合取式。如：P∨¬Q，(P∧Q)∨(P∧¬Q∧R)，Q∧¬P.(2)合取范式：一个命题公式称为合取范式，当且仅当它具有形式：A1∧A2∧……∧An(n大于等于1)其中Ai(i=1,2,3,…n)为简单析取式。如：P∧¬Q，(P∨Q)∧(P∨¬Q∨R)，Q∧¬P.(3)范式：析取范式与合取范式统称为范式。1.7对偶与范式(Dual&NormalForm)2023/7/4134析取范式与合取范式的性质：(1)一个析取范式是矛盾式，当且仅当它的每一个简单合取式都是矛盾式；(2)一个合取范式是重言式，当且仅当它的每一个简单析取式都是重言式。定理1.7.3(范式存在定理)任一个命题公式都存在着