离散数学命题逻辑

1、2022-3-612022-3-62v逻辑：是研究推理的科学。公元前四世纪由希腊的哲学家亚里斯多德首创。作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。 逻辑可分为：1.形式逻辑 2.辩证逻辑 v辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。v形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。2022-3-63v数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式

2、逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。v上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。2022-3-64v1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。v从广义上讲，数理逻辑包括四论、两演算即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题演算和谓词演算。本书也只研究这两个演算。2022-3-65v数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑

3、、时态逻辑等都是目前比较热门的研究领域。v本篇我们只从语义出发，对数理逻辑中的命题演算与谓词演算等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。2022-3-662022-3-67v 命题的定义v 命题的表示方法v 命题的分类v 小结2022-3-68一、命题(Statement,Proposition)的定义l 数理逻辑研究的中心问题是推理(inference)，而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。 l 命题的真值(Truth,Value)：命题的判断结果。命题的真值只取两个值：真(用T(true)或1表示)、假(用F(false)或

4、0表示) 。定义1-1.1 具有确定真假值的陈述句，称为命题。l 真命题：判断为正确的命题，即真值为真的命题。l 假命题：判断为错误的命题，即真值为假的命题。2022-3-69判断命题的两个步骤：l 是否为陈述句；l 是否有确定的、唯一的真值。例 判断下列句子是否为命题。(1) 今天天气多好啊！(2) 请你关上门.(3) How do you do ? (4) 3+3=8 . (5) 吸烟有害健康。T感叹句，感叹句，不是命题不是命题祈使句，祈使句，不是命题不是命题疑问句，疑问句，不是命题不是命题F2022-3-610(6) 太阳从西方升起。(7) x+39(8) 1+101=110(9) 国足

5、能杀入2014世界杯当且仅当2+2=4。(10)如果太阳从西方升起，那么2是奇数。 (11)今年五月一日是晴天。 (12)明天我去看电影。(13)宇宙中有外星人。(14)我正在说谎。不是命题不是命题二进制中为真，十进制中为假二进制中为真，十进制中为假FT是命题，其真值到五是命题，其真值到五月一日月一日方可知道方可知道是命题，客观上能判断真假是命题，客观上能判断真假悖论，不是命题悖论，不是命题F是命题，客观上能判断真假是命题，客观上能判断真假2022-3-611说明l 只有具有确定真值的陈述句才是命题。一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。l 因为命题只

6、有两种真值，所以“命题逻辑”又称 “二值逻辑”。 l “具有确定真值”是指客观上的具有，与我们是否 知 道 它 的 真 值 是 两 回 事 。 如 上 例 中 的(11)(12)(13).2022-3-612二、命题的表示方法v在本书中，用大写英文字母 A,B,P,Q 或带下标的字母P1,P2,P3, , 或数字(1),2, ,等表示命题，称之为命题标识符(Proposition Identifier)。例如 P：梅西是球星。 Q：5是负数。 P3：明天天气晴。 (2)：太阳从西方升起。皆为符号化的命题，其真值依次为1、0、1或0、0。2022-3-613l 命题常量(Proposition

7、Constant)：表示确定命题的命题标识符。v命题标识符又有命题常量、命题变元和原子变元之分。 l 命题变元(Proposition Valiable) ：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。l 原子变元(Atomic Valiable)：当命题变元表示原子命题时，该变元称为原子变元。2022-3-614注意：l 一个符号(如P)，它表示的是命题常量还是命题变元，一般由上下文来确定。l 命题变元可以表示任意命题，它不能确定真值，故命题变元不是命题。这与“变数x不是数”是一样的道理。2022-3-615l 简单命题(Simple Proposition)/原子命题(Atom

8、ic Proposition)/本原命题(Primitive Proposition)：不能分解为更简单的陈述语句的命题(如上例中的命题)。三、命题的分类l 复合命题(Compound Proposition) ：由简单命题通过联结词联结而成的命题。联结词就是复合命题中的运算符。 2022-3-616四、小结l 本节主要介绍了命题、命题的真值、原子命题、复合命题、命题标识符、命题常量、命题变元和原子变元的概念。l 重点理解和掌握命题、命题变元两个概念。作业：P8 (1)2022-3-6172022-3-618v 否定联结词(Negation) v 合取联结词(Conjunction) v 析取

9、联结词(Disjunction) v 条件联结词(蕴涵联结词Conditional) v 双条件联结(等值联结词Biconditional) v 小结2022-3-619一、否定联结词(Negation) l 在命题逻辑中，主要研究的是复合命题，而复合命题是由原子命题与逻辑联结词组合而成，联结词是复合命题的重要组成部分。定义1-2.1 设P为一命题，P的否定是一个新的复合命题，称为P的否定式，记作 “P”，读作“非P”，符号“” 称为否定联结词。 P为真当且仅当P为假.2022-3-620l 联结词“”的定义真值表PP0110l “” 属于一元运算符.2022-3-621例1 P：西安是一个城

10、市. Q：3是偶数.则 P：西安不是一个城市. Q：3不是偶数.例2 P：西安处处清洁. Q：这些都是男同学.则 P：西安不处处清洁 (注意，不是处处不清洁). Q：这些不都是男同学.2022-3-622二、合取联结词(Conjunction) PQPQ 000010100111定义1-2.2 设P,Q为命题，复合命题“P并且Q” (或“P与Q”)称为P与Q的合取式，记作PQ，符号“” 称为合取联结词。当且仅当P和Q同时为真时PQ 为真。 l 联结词“”的定义真值表2022-3-623l “” 属于二元(binary)运算符.l 合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则

11、为假。l 自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”、 “和”、 “与”等都可以符号化为 。2022-3-62424例3 将下列命题符号化.(1) 张三既聪明又用功. (2) 张三虽然聪明，但不用功.(3) 张三不但聪明，而且用功.(4) 张三不是不聪明，而是不用功.l 不要见到“与”或“和”就使用联结词 。例如: (1) 我与你是兄弟。 (2) 张三和李四是朋友。解解 设 P：张三聪明。 Q：张三用功。则(2) PQ(3) PQ(4) (P)Q (1) PQ2022-3-625例4 试生成下列命题的合取.(1) P：房间里有张桌子. Q：今天是

12、星期三.(2) S：李平在吃饭. R：张明在吃饭. .(1)逻辑学中允许两个相互独立无关的，甚至互为否定的 原子命题生成一个新的命题如上例的 1).l“”与自然语言中“与”“和”的不同之处：解,(.) (2)自然语言中有时在各种不同意义上使用联结词与 和 ，不能一概用去翻译 如：我与你是兄弟(1) PQ：房间里有张桌子且今天是星期二.(2) SR：李平与张明在吃饭. 2022-3-626三、析取联结词(Disjunction)PQPQ000011101111定义1-2.3 设P,Q为命题，复合命题“P或Q” 称为P与Q的析取式，记作PQ ，符号称为析取联结词. PQ为真当且仅当 P与Q中至少有

13、一个为真.l 联结词“”的定义真值表2022-3-627l “” 属于二元(binary)运算符.l 析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。l 由析取联结词的定义可以看出， “”与汉语中的联结词“或”意义相近，但又不完全相同。在现代汉语中，联结词的“或”实际上有“可兼或”和“排斥或”之分。考察下面命题： (1) 小王爱打球或爱跑步。 设P：小王爱打球。 Q：小王爱跑步。（可兼或） 则上述命题可符号化为：P Q2022-3-628(4)人固有一死，或重于泰山或轻于鸿毛. (2) 张三学过英语或法语。 设P：张三学过英语。 Q：张三学过法语(3) 派小王或小李中的一

14、人去开会。 设P：派小王去开会。Q：派小李去开会。(5) ab=0, 即a=0 或 b=0. 由此可见, “P Q”表示的是“可兼或”. 则上述命题可符号化为： P Q 则上述命题可符号化为：(PQ) (PQ)（可兼或）（排斥或）（排斥或）（可兼或）2022-3-629l 注意：当P和Q客观上不能同时发生时，“P或Q”可以符号化为“P Q”。1 .2 （）逻辑学中允许联结两个毫无关系的命题（）自然语言中有时在各种不同意义上使用联结词或 ，不能一概用去翻译（如: 张三或李四都可以做这件事）.l“”与自然语言中“或”的不同之处： 例如：小王现在在宿舍或在图书馆。 设 P：小王现在在宿舍。Q：小王现

15、在在图书馆。 则上述命题可符号化为：P Q。2022-3-630四、条件联结词(蕴涵联结词Conditional)PQP Q001011100111定义1-2.4 设P,Q为命题，复合命题“如果P那么Q(若P则Q)” 称为P与Q的条件命题，记作P Q. P Q为假当且仅当P为真且Q为假。称符号“”为条件联结词。并称P为前件，Q为后件. l 联结词“”的定义真值表2022-3-631l PQ表示的基本逻辑关系是：Q是P的必要条件或P是Q的充分条件. 因此复合命题“只要P就Q”、“因为P，所以Q”、“P仅当Q” 、“Q每当P” 、“只有Q才P”等都可以符号化为P Q 的形式。l “”属于二元(bi

16、nary)运算符。例5 将下列命题符号化。(1)天不下雨，则草木枯黄。 设 P：天下雨。Q：草木枯黄。 则原命题可表示为： PQ。2022-3-632(2)如果小明学日语，小华学英语，则小芳学德语。 设 P：小明学日语 Q：小华学英语 R：小芳学德语(3)只要不下雨，我就骑自行车上班。(4)只有不下雨，我才骑自行车上班。 设 P：天下雨。Q：我骑自行车上班。 设 P：天下雨。Q：我骑自行车上班。 则原命题可表示为：(PQ)R 则原命题可表示为： PQ 则原命题可表示为： Q P 。2022-3-633例6 设 P：2+2=4 Q：太阳从东方升起 R：太阳从西方升起符号化下列命题，并判断命题的真

17、值：(1) 如果 2+2=4，则太阳从东方升起。(2) 如果 2+2=4，则太阳从西方升起。(3) 如果 2+24，则太阳从东方升起。(4) 如果 2+24，则太阳从西方升起。解(1) P Q， T(2) PR， F(3) P Q ， T(4) P R， T2022-3-634注意:l 与自然语言的不同：前件与后件可以没有任何内在联系！l 在数学中，“若P则Q”往往表示前件P为真，则后件Q为真的推理关系. 但数理逻辑中，当前件P为假时， P Q的真值为真。2022-3-635五、双条件联结词(等值联结词Biconditional) PQP Q001010100111定义1-2.5 设P,Q为命

18、题，复合命题“P当且仅当Q” 称为P与Q的双条件命题，记作 P iff Q 或 PQ，符号称为双条件（等值）联结词。 PQ为真当且仅当P与Q的真值相同。l 联结词“”的定义真值表2022-3-636l “P仅当Q” 可译为l “P每当Q” 可译为l “P当且仅当Q” 可译为说明:PQQPPQl “”属于二元(binary)运算符。l 双条件命题PQ所表达的逻辑关系是，P与Q互为充分必要条件，相当于(PQ)(QP). 只要P与Q的真值同为1或同为0，PQ的真值就为1， 否则PQ的真值为0。双条件联结词连接的两个命题之间可以没有因果关系。2022-3-637例6 分析下列命题的真值(P: 2+2=

19、4 Q: 3是奇数 ) (1) 2+2=4 当且仅当3是奇数 . (2) 2+2=4 当且仅当3不是奇数 . (3) 2+24 当且仅当3是奇数 . (4) 2+24 当且仅当3不是奇数 . PQ，约定:l 运算次序优先级：， ， ，.l 相同的运算符按从左至右次序计算，否则要加上括号。l 最外层圆括号可省去。PQ，PQ，PQ，TFFT2022-3-638作业: P8 (3), (5). l 预习1.3, 1.4，并思考: (1) 何谓合式公式? (2) 复合命题符号化的基本步骤是什么? (3) 何谓真值表? (4) 两个命题公式等价的涵义是什么? (5) 两个等价的命题公式其真值表有何关系?

20、六、小结l 本节介绍了五种联结词(， ， ，)。l 重点是理解和掌握五种联结词的内涵及它们与自然语言中相应联结词的不同之处.2022-3-6392022-3-640v 命题公式的定义v 复合命题的符号化(翻译)v 小结2022-3-641一、命题公式(Proposition Formula)的定义定义1-3.1 单个命题变元和命题常量称为原子公式。定义1-3.2 命题演算的合式公式(wff：Well-formed formula)，规定为：(1) 原子公式是合式公式。 (2) 若A是合式公式，则(A)也是合式公式。(3) 若A，B是合式公式，则(AB)，(AB)， (AB)，(AB)也是合式公

21、式。(4) 当且仅当有限次地应用(1)(3)所得到的包含原 子公式、联结词和括号的符号串是合式公式。2022-3-642l 命题演算的合式公式是由命题变元、命题常量、联结词和圆括号按一定的逻辑关系联结起来的符号串，是以递归的形式来定义的l 合式公式也称为命题公式，并简称为公式。l 命题公式一般不是命题，仅当公式中的命题变元用确定的命题代入时，才得到一个命题。其真值依赖于代换变元的那些命题的真值。2022-3-643约定：l 运算次序优先级：， ， ，.l 相同的运算符按从左至右次序计算，否则要加上括号。l 最外层圆括号可省去。2022-3-644例1 指出(P(PQ)是否是命题公式，如果是，则

22、具体说明。解 P是wff 由(1) Q是wff 由(1) PQ是wff 由(3) (P(PQ) 由(3) 例2 (P Q) , (R S) Q , P，P等均为合式公式，而PQ S , (P W) Q)等不是合式公式。2022-3-645二、复合命题的符号化(翻译)l 有了命题演算的合式公式的概念，我们可以把自然语言中的有些语句(复合命题)，翻译成数理逻辑中的符号形式。基本步骤如下： (1) 分析出各原子命题，将它们符号化； (2) 使用合适的联结词，把简单命题逐个的联结起来，组成复合命题的符号化表示.2022-3-646例3 符号化下列命题：(1) 尽管他有病，但他仍坚持工作。设P：他有病。

23、Q：他坚持工作。则该命题可以表示为：PQ(2) 说数理逻辑枯燥无味或毫无价值，那是不对的。设P：数理逻辑枯燥无味。Q：数理逻辑毫无价值。则该命题可以表示为：(PQ)(3) 张三与李四组成一个学习小组。设P：张三与李四组成一个学习小组。则该命题可以表示为：P2022-3-647(4) 假如上午不下雨，我去看电影，否则就在家里读书或看报。设P：上午下雨。Q：我去看电影。R：我在家读书。S：我在家看报。则该命题可以表示为： (PQ)(P(RS)(5) 除非你通知我，否则我不开会。设P：你通知我。Q：我开会。则该命题可以表示为： PQ(6) 除非你努力，否则你将失败。设P：你努力。Q：你将失败。则该命

24、题可以表示为： PQ2022-3-648(7) 一个人起初说：“占据空间的、有质量的而且不断变化的叫做物质”；后来他改说：“占据空间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。设P：它占据空间。Q：它有质量。R：它不断变化。W：它是物质。则第一句话可表示为： (PQR)W第一句话可表示为： (PQW)( WR)(8) 只要我还有一口气，我就要战斗。设P：我有一口气。Q：我要战斗。 则该命题可以表示为： PQ2022-3-649(9) 只要功夫深，铁杵磨成针。设P：功夫深。Q：铁杵磨成针。则该命题可以表示为： PQ(10) 只有睡觉才能恢复体力。

25、设P：睡觉。Q：恢复体力。则该命题可以表示为： QP(11)小王晚上回家，除非下大雨。设P：小王晚上回家。Q：下大雨。则该命题可以表示为： QP2022-3-650(12)若要人不知，除非己莫为。设P：人知。Q：己为。则该命题可以表示为： QP(13)除非天气好，我才骑自行车上班。设P：天气好。Q：我骑自行车上班。则该命题可以表示为： PQ(14)除非你陪我或代我叫辆车子，否则我不出去。设P：你陪我。Q：你代我叫辆车。R：我出去。则该命题可以表示为： (PQ)R2022-3-651(15)天黑了，我得回家了。设P：天黑了。Q：我回家。则该命题可以表示为： PQ(16)张三与李四有且仅有一人是大

26、学生。设P：张三是大学生。Q：李四是大学生。则该命题可以表示为： (PQ)(17)张三正在游泳或正在睡觉。设P：张三正在游泳。Q：张三正在睡觉。则该命题可以表示为： (PQ)2022-3-652三、小结作业: P12 (5),(7)l 本节介了命题公式的概念及复合命题的符号化。l 重点是理解命题公式的递归定义，掌握复合命题的符号化方法.2022-3-6532022-3-654v 真值表(Truth Table)v 等价公式(Propositional Equivalences)v 小结2022-3-655一、真值表定义1-4.1 设P1,P2, ,Pn是出现在公式A中的全部的命题变元，给P1,

27、 P2 , Pn 各指定一个真值，称为对A的一个真值指派或赋值(Assigment)或解释。若指定的一组值使A的真值为真(假)，称这组值为A的成真(假)指派.l 前面在定义联结词时，曾经使用过真值表，本节给出真值表的定义。2022-3-656l 比如:对公式(PQ)R，赋值011(即令P=0，Q=1，R=1)为(PQ)R的成真赋值；另一组赋值010为(PQ)R的成假赋值；还有000，001，111l 考虑：含有n个命题变元的公式共有多少组不同的赋值？定义1-4.2 在命题公式A中，对于命题变元的每一种可能的真值指派和由它们所确定的命题公式A的真值列成表，称做命题公式A的真值表。2022-3-6

28、57l 对公式A构造真值表的具体步骤为： (1)找出公式中所有命题变元P1,P2,Pn。 (2)按从小到大的顺序列出命题变元P1,P2,Pn的全部2n组赋值。 (3)对应各组赋值计算出公式A的真值，并将其列在对应赋值的后面。2022-3-658PQPQ(PQ)PQ(PQ) (PQ)00011011例1 给出(PQ)(PQ)的真值表。00011110111011112022-3-659PQRPQ(P Q) R000001010011100101110111例2 构造公式 (P Q)R的真值表。11110011010100012022-3-660练习1 构造公式 (PQ)(QP)的真值表。PQP

29、QP QQP(PQ)(QP)00011011110010101101110111112022-3-661PQ P Q(P Q) (P Q) Q00011011练习2 构造公式 (P Q) Q 的真值表。1101001000002022-3-662l 给定n个 命题变元，按合式公式的形成规则可以形成无数多个命题公式, 但这些无穷尽的命题公式中，有些具有相同的真值表。l 考虑：由n个命题变元能生成多少种真值(表)不同的命题公式？(n1)二、等价公式2022-3-663定义1-4.3 给定两个命题公式A和B，设P1,P2, Pn为出现于A和B中的所有原子变元，若给P1, P2, ,Pn任一组真值指派

30、，A和B的真值都相同，则称A和B是等价的或逻辑相等，记作A B。l “”不是逻辑联结词.l 命题公式之间的逻辑相等关系具有： (1) 自反性：A A ； (2) 对称性：若A B，则B A； (3) 传递性：若A B且B C，则A C。2022-3-664PQPQ QPPQ(PQ) (QP)00011011证明公式等价的方法：l 真值表法 l 等值演算法1、真值表法 例3 证明: PQ (PQ)(QP)10011011110110012022-3-665例4 判断公式 P(QR)、(PQ)R是否等价。PQ R P QQ R P (Q R) (P Q) R00000101001110010111

31、0111由真值表可知，两个公式为等价式。000000111111110111011101111111012022-3-6662、等值演算法(Equivalent Caculation)（利用P15表1-4.8)重要的等价式(补充)： 11. 条件转化律： PQ PQ 12. 双条件转化律: PQ (PQ)(QP) 13. 逆否律(假言易位)： PQ QP 14. 双条件否定等价式：PQ PQ 15. 归谬律： (PQ)(PQ) P其中P，Q，R等代表任意命题公式. 2022-3-667l 置换/替换规则(Rule of Replacement)：等值演算中使用的一条重要规则。定义1-4.4(子

32、公式) 如果X是wff A的一部分，且X本身也是wff，则称X是A的子公式(Subformula)。例如，P(PQ) 为Q (P(PQ)的子公式。2022-3-668定理1-4.1(置换定理Axiom of replacement) 设X是wff A的子wff，若XY，则若将A中的X用Y来置换，所得公式B与A等价，即AB。证：因为对变元的任一指派，X与Y真值相同，所以Y取代X后，公式B与公式A对变元的任一指派真值也相同，所以AB。l 满足定理1-4.1条件的置换称为等价置换(或等价代换).定义1-4.5(等值演算) 根据已知的等价公式，推演出另外一些等价公式的过程称为等值演算.2022-3-6

33、69例6 证明 (PQ)Q PQ例5 证明 Q(P(PQ)QP证 Q(P(PQ)QP (吸收律)证 (PQ)Q (PQ)(QQ) (PQ)T PQ2022-3-670例7 证明（PQ）（QP） PQR证 (PQ)(QP) (PQ)(QR) (PQ)(QR) (PQ)(QR) (PQR)(QQR) PQR 2022-3-671例8 验证P(QR) (P Q) R练习：(1) (P Q) (P R) 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 (Q R) P (Q R)2022-3-672l 等值演算在

34、计算机硬件设计中,在开关理论和电子元器件中都占有重要地位.三、小结 l 本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（24个）。l 重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。作业：P17 (1)b,d,e. (4)c,d (7)e,g,h (8).l 思考题：(9)l 预习：1.5, 1.62022-3-6732022-3-674v命题公式的分类v重言式(Tautology)的性质v蕴含式( Implication)v小结2022-3-675一、命题公式的分类l 重言式(Tautology)/永真式l 矛盾式(Contradiction)

35、/永假式(Absurdity)l 可满足式(Satisfactory)l 仅可满足式/偶然式(Contingency)2022-3-676定义1-5.1 设A为任一命题公式，(1) 若A在其各种赋值下的取值均为真，则称A是重言式或永真式，记为T或1。(2) 若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式，记为F或0。(3) 若A不是矛盾式则称A为可满足式。(4) 既不是重言式，也不是矛盾式，称为偶然式。2022-3-677判别命题公式的类型的方法: :l 真值表法l 等值演算法：将所给命题公式通过等值演算化为最简单的形式, 然后再进行判别.(重言式)例1 判别下列命题公式的类型.(1)

36、 Q(PQ)P) (2) (PP)(QQ)R (3) (PQ)P (矛盾式)(可满足式)2022-3-678二、重言式的性质定理1-5.1 任何两个重言式的合取或析取，仍然是一重言式.证明 设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故AB T，AB T2022-3-679定理1-5.2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。证明：由于重言式(矛盾式)的真值与对变元的赋值无关，故对同一变元以任何合式公式置换后，重言式(矛盾式)的真值仍永为T（F）。2022-3-680定理1-5.3 A，B是两个命题公式，A B的充要条件是A B为重言式。

37、证明 若AB为重言式，则AB永为T，即A，B的真值表相同，所以AB。反之，若A B，则A，B真值表相同， 所以AB永为T，从而AB为重言式。2022-3-681三、蕴含式( Implication)定义1-5.2 当且仅当 P Q 是一个重言式时，我们称“P蕴含Q”，并记作 P Q.设原命题为PQ，则l 逆换式：QPl 反换式：PQl 逆反式：QP2022-3-682它们之间具有如下关系:l PQ QP l QP PQ证明 PQ 的三种方法：l 真值表法：即列出PQ的真值表，观察其是否为永真。l 直接证法：假定前件P是真，推出后件Q是真。l 间接证法：假定后件是假，推出前件是假，即证QP 。2

38、022-3-683例1 证明 Q （PQ） P证法1：真值表法(略)证法2：若 Q(PQ)为真，证法3：若P为假，则P为真，再分二种情况：若Q为真，则Q为假，从而Q(PQ)为假；若Q为假，则PQ为假，从而Q(PQ)为假，根据 ，有 Q(PQ)P。则 Q，PQ为真，所以Q为假，P为假，所以P为真。2022-3-684l P21表1-5.2给出了14个蕴含式。1P QP化简式2P QQ化简式3PP Q附加式4PPQ5QPQ6(PQ)P7(PQ)Q2022-3-685l P21表1-5.2给出了14个蕴含式。8P (PQ)Q假言推理9Q (PQ)P拒取式10 P (P Q)Q析取三段论11 (PQ)

39、 (QR)PR 假言三段论12 (P Q) (PR) (QR)R二难推理13 (PQ) (RS)(P R)(Q S)14 (PQ) (QR)PR等价三段论2022-3-686l 等价式与蕴含式的关系：定理1-5.4 设P，Q为任意两个命题公式，PQ的充要条件为 PQ 且 QP.证 若PQ，则PQ为永真式，因为 PQ （PQ）（QP），所以 PQ，QP为永真式，从而 PQ，QP.反之，若PQ，QP，则PQ，QP为永真式，所以（PQ）（QP）为永真式，从而 PQ为永真式，即PQ.2022-3-687l 蕴含的性质：设A，B，C为任意wff,(1) 若AB，且A为永真式，则B必为永真式.(2) 若A

40、B，BC，则AC.(3) 若AB，AC，则ABC.(4) 若AB且CB，则ACB.2022-3-688四、小结l 本节介绍了命题公式的分类，重言式、矛盾式与蕴含式的概念及其性质，等价式与蕴涵式的关系。l 重点掌握： (1) 用等值演算法判别命题公式的类型。 (2) 重言式、矛盾式与蕴涵式的性质。 (3) 等价式与蕴涵式的关系。作业：P23 (1)a,b,c (7) (8)e,f (9). 2022-3-6892022-3-690v不可兼析取(排斥或/异或)(Exclusive or)v与非联结词(Nand)v或非联结词(Nor)v条件否定联结词(Non-conditional)v最小联结词组(

41、The minimal set of connectives)v小结2022-3-691l 在第二节(1.2)中我们定义了五种基本的联结词， ，但在命题逻辑中，这些联结词还不能很广泛地直接表达命题之间的联系(例如, “P异或Q”只能间接地表示为(PQ)(PQ)，为此本节再给出逻辑设计中常用的另外四种联结词.2022-3-692一、不可兼析取/排斥或/异或(Exclusive-OR， )v定义1-6.1 设P、Q为两个命题，复合命题“P、Q之中恰有一个为真” 称为P与Q的不可兼析取，记作P Q，符号“ ” 称为异或联结词。P Q 为真当且仅当P和Q的真值不同.vvvPQP Q0000111011

42、10v2022-3-693例 派小王或小李中的一人去开会。（排斥或） l 定义了联结词“ ”后，命题逻辑中的有些命题就可以符号化为非常简捷的形式. 设P：派小王去开会。Q：派小李去开会。 则上述命题可符号化为： P Q 2022-3-694l “ ” 属于二元(binary)运算符。 l 联结词 的性质：设P，Q，R为命题公式，则有 (1) P Q Q P (交换律) (2) (P Q) R P (Q R) (结合律) (3) P(Q R) (PQ) (PR) (分配律) (4) (P Q) (PQ) (PQ) (5) (P Q) (PQ) (6) P P F, F P P, T P P202

43、2-3-695定理1-6.1 设P，Q， R为命题公式， 如果P Q R，则P RQ，Q RP，且P Q R 为一矛盾式. 证 如果 P QR，则 P RP (P Q)(P P) QF QQ Q RQ (P Q)F PP P Q RR RF 2022-3-696二、与非联结词(NAND，)PQP Q001011101110定义1-6.2 设P,Q为二命题，复合命题“P与Q的否定” 称为P与Q的与非式，记作 PQ，符号“” 称为与非联结词。PQ 为真当且仅当P和Q不同时为真.2022-3-697l 由定义可知，PQ (PQ)l “” 属于二元(binary)运算符l 联结词“”的性质： (1)

44、PP ( PP) P (2) (PQ)(PQ) ( PQ)(PQ) (3)(PP)(QQ) PQ(PQ)PQ 2022-3-698定义1-6.3 设P,Q为二命题，复合命题“P或Q的否定” 称为P与Q的或非式，记作PQ ，符号“”称为或非联结词. PQ为真当且仅当P与Q同为假.PQP Q001010100110三、或非联结词(NOR，)2022-3-699l 由定义可知，PQ (PQ)l “” 属于二元(binary)运算符l 联结词“”的性质： (1) PP (PP) P (2) (PQ)(PQ) (PQ) (PQ) (3)(PP)(QQ)PQ(PQ)PQ2022-3-6100四、条件否定联

45、结词(Non-conditional， )cc定义1-6.4 设P，Q为二命题，复合命题“P Q” 称为命题P与Q的条件否定式P Q为真当且仅当P为真且Q为假.ccccPQP Q000010101110c2022-3-6101l 由定义可知，P Q (P Q)l “ ” 属于二元(binary)运算符.l 有了联结词 后，命题演算的合式公式的定义1-3.2可加入这四个联结词.ccc, , , 2022-3-6102l 至此，对于一元和二元逻辑运算，我们一共定义了9个联结词，为了直接表达命题之间的联系，是否还需要定义其它联结词呢? l 如果不需要定义其他联结词，那这9个联结词是否都是必须的？l

46、哪些是必须的？五、最小联结词组(The minimal set of connectives)下面以含两个命题变元P、Q的所有互不等价的命题公式为例，来说明这一问题。2022-3-6103P QFPQPQPQPQP QPQ0 0000000000 1000011111 0001100111 101010101P QPQPQQQPPPQPQT0 0111111110 1000011111 0001100111 101010101c cl 由两个命题变元P，Q所构成的互不等价的24个命题公式如下：2022-3-6104 l 由上表可知，9个联结词足以直接表达命题之间的各种联系，即含n个命题变元的所

47、有 个互不等价的命题公式，均可由这9个联结词直接表达，不需要定义其他联结词。l 在二元运算中，9个联结词并不都是必要的。为此，我们定义最小联结词组。2n2022-3-6105定义1-6.5 一个联结词集合，如果用其中联结词足以把任何命题公式等价地表示出来，而去掉其中任何一个联结词则不能，我们称这个联结词集合为最小联结词组(The minimal set of connectives)l 最小联结词组具有： (1) 完备性 (2) 最小性2022-3-6106l 对于9个联结词的集合, , , , ，(1) PQ (PQ) (QP)(2) PQP Q (3) P Q (P Q)(4) P Q (

48、P Q) (5) (P Q) (PQ)(6) PQ (PQ)(7) PQ (PQ)(8) P Q (PQ)c c c c 2022-3-6107l 任意命题公式都可由仅包含， 或， 的命题公式等价代换，即9个联结词的集合中至少有七个冗余联结词。而联结词， 和， 不再有冗余联结词，故， 或， 为最小联结词组。l 实际中为了使用方便, 命题公式常常同时包含， ， .c c l 其他最小联结词组： ， 2022-3-6108 P (PP)PP PQ (PQ) (PQ)(PQ)(PQ)PQ (PQ) (PP)(QQ) (PP)(QQ)例1 试证是最小联结词组.证例2 试证，是最小联结词组证PQ(PQ)

49、(PQ)PQ(P)QPQ2022-3-6109l 本节主要介绍了四种新的联结词 及最小联结词组.c , 五、小结作业: P29 (1), (2), (4)2022-3-6110l 预习1.7，并思考：(1)何谓命题公式的(主)析(合)取范式?(2)命题公式的(主)析(合)取范式唯一吗?(3)为何要将命题公式化为与之等价的主析(合)取范式?(4)如何将命题公式化为与之等价的主析(合)取范式?(5)两个等价的命题公式其(主)析(合)取范式有何关 系?2022-3-61112022-3-6112v对偶式与对偶原理(Dualistic Formula & Duality Principle)v

50、命题公式的析(合)取范式(The Disjunctive & Conjunctive Normal Forms of a Propositional Formula)v命题公式的主析(合)取范式(The Principal Disjunctive & Conjunctive Normal Form of a Propositional Formula)v小结2022-3-6113一、对偶式与对偶原理l 在1.4中我们给出了命题定律(P15表1-4.8)，其中多数等价公式（仅含联结词， ， ）都是成对出现的，每一对公式的不同之处是将 与 互换，T与F互换，我们把这样的公式称为是对

51、偶的. 定义1-7.1 设命题公式A仅含有联结词、 、 ，在A中将 、 、F、T分别换以 、 、T、F，得出公式A*，则A*称为A的对偶公式。l (A*)*=A2022-3-6114例1 (P(QR)*=P(QR) (PQ)1)*=(PQ)0) 由 PQ (PQ) 和 PQ (PQ) 可知 (PQ)*= PQ2022-3-6115l 关于对偶式我们有如下两个定理:定理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)证明

52、因为 (PQ)PQ，(PQ)PQ所以A(P1 , P2 ,Pn )A*(P1 , P2 , Pn)同理A*(P1 , P2 ,Pn )A(P1 , P2 , Pn)。2022-3-6116定理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)

53、B*(P1 , P2 ,Pn ).因此 A*B* 。2022-3-6117例2 因为 P(PQ)P由对偶原理，有 P(PQ) P. 例3 若A1 则 A*(1)* 即 A*0.例4 设A为 (PQ)(P(PQ)，B为PQ，且AB，则 A*B*PQ。2022-3-6118定理1-7.3 设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

54、)永真. 2022-3-6119即 B*(P1 , P2 , Pn)A*(P1 , P2 , Pn) 永真.以 Pi代Pi (i=1，2n)，得 B*(P1 , P2 , Pn)A*(P1 , P2 , Pn)永真.所以 B* A* .定理1-7.3 设A，B为两个仅含有联结词， ， 的命题公式，若AB，则B*A*。2022-3-6120二、命题公式的析(合)取范式l 从前面的讨论可知，存在大量互不相同的命题公式，实际上互为等价，因此，有必要引入命题公式的标准形式，使得相互等价的命题公式具有相同的标准形式。这无疑对判别两个命题公式是否等价以及判定命题公式的类型是一种好方法，同时对命题公式的简化

55、和推证也是十分有益的。2022-3-6121定义1-7.2(1)文字：命题变元及其否定统称为文字(如P , P). (2)简单析取式：仅有有限个文字组成的析取式。如P，PQ，PP，QPP，PQRS.(3)简单合取式：仅有有限个文字组成的合取式。如 P，Q，QP，PP，QPP，pQR.l 一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定式。l 一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定式。2022-3-6122定义1-7.3(1)析取范式：一个命题公式称为析取范式，当且仅当它具有形式：A1A2An (n大于等于1)其中Ai(i=1,2,3,n)为简单合取式。如：PQ

56、，(PQ)(PQR)，QP.(2)合取范式：一个命题公式称为合取范式，当且仅当它具有形式：A1A2An (n大于等于1)其中Ai(i=1,2,3,n)为简单析取式。如：PQ，(PQ)(PQR)，QP.(3)范式：析取范式与合取范式统称为范式。2022-3-6123l 析取范式与合取范式的性质：(1) 一个析取范式是矛盾式，当且仅当它的每一个简单合取式都是矛盾式；(2) 一个合取范式是重言式，当且仅当它的每一个简单析取式都是重言式。定理1-7.4 (范式存在定理) 任一个命题公式都存在着与之等价的析取范式与合取范式。l 任何合(析)取范式的对偶式是析(合)取范式。2022-3-6124l 求命题

57、公式的范式的基本步骤：(1) 将公式中的联结词化归成，及。(2) 将利用下列双重否定律、徳摩根律否定联结词消去或内移到各命题变元之前。 A A ( AB) AB ( AB) AB(3) 利用分配律、结合律将公式转化为合取范式或析取范式。 C(AB) (CA)(CB) C(AB) (CA)(CB)2022-3-6125例5 求(PQ)R)P的析取范式与合取范式。解 原式 (PQ)R)P (PQ )R)P (PR )(QR)P (析取范式) P(PR )(QR) P(QR) (析取范式) (PQP)(RP) (合取范式) (PQ)(RP ) (合取范式)2022-3-6126例6 求(P Q) R

58、的析取范式与合取范式。解 原式 (PQ) R)(R(PQ) ) (PQ)R)(R (PQ) ) (PQ)R)(RPQ ) (P Q)R)(RPQ ) (PR)(QR)(RPQ ) (合取范式) ( ( P Q ) ( R P Q ) ) ( R (RPQ ) (PQR)(RP)(RQ) (析取范式)2022-3-6127例7 求(PQ)(PQ)的析取范式与合取范式。解 (PQ)(PQ) (PQ)(PQ)(PQ)(PQ) (PQ)PQ)(PQ)(PQ) (PQ)(QP) (析取范式) (PQ)(PQ) (合取范式)注意：l 单个命题变元既是简单合取式，又是简单析取式；公式PQR既可以看成是合取范

59、式，也可以看成是析取范式。l 一个命题公式的析(合)取范式不是唯一的。2022-3-6128三、命题公式的主析(合)取范式l 由于一个命题公式的析(合)取范式不是唯一, 因而它们不能作为命题公式的规范形式(标准形式), 为了使任意命题公式化为唯一的标准形式, 下面引入主范式的概念.1. 命题公式的主析取范式定义1-7.4 在含有n个命题变元的简单合取式中，若每个命题变元和它的否定不同时出现，而二者之一必出现且仅出现一次，称这样的简单合取式为小项.2022-3-6129例如，三个命题变元P、Q、R，其小项共有8个： 小项 编码 真值指派 小项的真值 PQR m000/m0 000 1 PQR m

60、001/m1 001 1 PQR m010/m2 010 1 PQR m011/m3 011 1 PQR m100/m4 100 1 PQR m101/m5 101 1 PQR m110/m6 110 1 PQR m111/m7 111 12022-3-6130l 考虑：n个命题变元可产生多少个小项？2nl n个变元的小项： m0 P1P2.Pn m1 P1P2.Pn m2n-1 P1P2.Pnl 小项的真值表：P33 表1-7.1，表1-7.22022-3-6131PQP QP QP QP Q001000010100100010110001l 含有两个命题变元的小项真值表：2022-3-6132小项的性质：l 任