左孝凌离散数学课件.ppt
148页
离散数学离散数学(Discrete Mathematics) 第一部分第一部分 数理逻辑数理逻辑（（（（Mathematical Logic)Mathematical Logic)v逻逻辑辑：：是是研研究究推推理理的的科科学学公公元元前前四四世世纪纪由由希希腊腊的的哲哲学学家家亚亚里里斯斯多多德德首首创创作作为为一一门门独独立立科科学学，，十十七七世世纪纪，，德德国国的的莱莱布布尼尼兹兹(Leibniz)给给逻逻辑辑学学引引进进了了符符号号, 又又称称为数理逻辑为数理逻辑(或符号逻辑或符号逻辑) 逻辑逻辑可分为：可分为：1. 形式逻辑（通过数学方法）形式逻辑（通过数学方法） 数理逻辑数理逻辑 2. 辩证逻辑辩证逻辑 指引进一套符号体系的方法指引进一套符号体系的方法 辩证逻辑辩证逻辑是研究反映客观世界辩证发展过程的人类思是研究反映客观世界辩证发展过程的人类思维的形态的维的形态的 v形形式式逻逻辑辑是是研研究究思思维维的的形形式式结结构构和和规规律律的的科科学学，，它它撇撇开开具具体体的的、、个个别别的的思思维维内内容容，，从从形形式式结结构构方方面面研研究究概概念、判断和推理及其正确联系的规律。
念、判断和推理及其正确联系的规律v数数理理逻逻辑辑是是用用数数学学方方法法研研究究推推理理的的形形式式结结构构和和推推理理的的规规律律的的数数学学学学科科它它的的创创始始人人Leibniz，，为为了了实实现现把把推推理理变变为为演演算算的的想想法法，，把把数数学学引引入入了了形形式式逻逻辑辑其其后后，，又又经经多多人人努努力力，，逐逐渐渐使使得得数数理理逻逻辑辑成成为为一一门门专专门门的的学学科v上上个个世世纪纪30年年代代以以后后，，数数理理逻逻辑辑进进入入一一个个崭崭新新的的发发展展阶阶段段，，逻逻辑辑学学不不仅仅与与数数学学结结合合，，还还与与计计算算机机科科学学等等密密切关联 2024/9/18第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic））））1.1 1.1 命题及其表示方法命题及其表示方法命题及其表示方法命题及其表示方法•1.1.1 命题（命题（Proposition)•1.1.2 命题的表示方法命题的表示方法•1.1.3 命题的分类命题的分类 2024/9/181.1.1 命题命题 数数理理逻逻辑辑研研究究的的中中心心问问题题是是推推理理（（inference),而而推推理理的的前前提提和和结结论论都都是是表表达达判判断断的的陈陈述述句句，，因因而而表表达达判断的陈述句构成了推理的基本单位判断的陈述句构成了推理的基本单位。
基本概念基本概念ü 命题：能够判断真假的陈述句命题：能够判断真假的陈述句ü 命题的真值：命题的判断结果命题的真值只取两个命题的真值：命题的判断结果命题的真值只取两个 值值:真（真（用用T(true)或或1表示表示）、假（）、假（用用F(false)或或0表示表示）） ü 真命题：判断为正确的命题，即真值为真的命题真命题：判断为正确的命题，即真值为真的命题ü 假命题：判断为错误的命题，即真值为假的命题假命题：判断为错误的命题，即真值为假的命题 因而又可以称因而又可以称命题是具有唯一真值的陈述句命题是具有唯一真值的陈述句判断命题的两个步骤判断命题的两个步骤：： 1 1、是否为陈述句；、是否为陈述句； 2 2、是否有确定的、唯一的真值是否有确定的、唯一的真值 例例：判断下列句子是否为命题判断下列句子是否为命题 (1). 100是自然数是自然数 T (2). 太阳从西方升起太阳从西方升起 F (3). 3+3=8 . F (4). How do you do ? 疑问句，疑问句，不是命题不是命题(5). 明年的十月一日是晴天。
明年的十月一日是晴天是命题，其真值到是命题，其真值到明年明年 十月一日方可知道十月一日方可知道6). x+3>9 不是命题不是命题(7). 我正在说谎我正在说谎是悖论是悖论(8). 1+101=110 二进制中为真，十进制中为假二进制中为真，十进制中为假9). 如果太阳从西方升起，那么如果太阳从西方升起，那么2是奇数是奇数T(10). 国足能杀入国足能杀入2006世界杯当且仅当世界杯当且仅当2+2=4F (11). 今天天气多好啊！今天天气多好啊！ 感叹句，感叹句，不是命题不是命题(12). 请你关上门！请你关上门！ 祁使句，不祁使句，不是命题，是命题， (13). 别的星球上有生物别的星球上有生物 是命题，客观上能判断真是命题，客观上能判断真 假说明：说明：（（1）只有）只有具有确定真值具有确定真值的的陈述句陈述句才是命题一才是命题一 切没有判断内容的句子，无所谓是非的句子，切没有判断内容的句子，无所谓是非的句子， 如如感叹句、祁使句、疑问句等都不是命题感叹句、祁使句、疑问句等都不是命题 （（2）） 因为因为命题只有两种真值，所以命题只有两种真值，所以“命题逻辑命题逻辑”又称又称 “二值逻辑二值逻辑”。
(3) “具具有有确确定定真真值值”是是指指客客观观上上的的具具有有，，与与我我们们是是否否知道它的真值是两回事如上例中的（知道它的真值是两回事如上例中的（5）和（）和（13）1.1.2 命题的表示方法命题的表示方法 在在本本书书中中，，用用大大写写英英文文字字母母A,B,…,P,Q或或带带下下标标的的字字母母P1,P2,P3 , …,或或数数字字(1),[2], …,等等表表示示命命题题，，称称之之为为命题标识符命题标识符 例如：例如： P：罗纳尔多是球星罗纳尔多是球星 Q：：5是负数 P3：：明天天气晴明天天气晴 (2)：太阳从西方升起太阳从西方升起 皆为符号化的命题，其真值依次为皆为符号化的命题，其真值依次为1、、0、、1或或0、、0 命题标识符又有命题常量、命题变元和原子变元命题标识符又有命题常量、命题变元和原子变元之分命题常量命题常量：表示确定命题的命题标识符表示确定命题的命题标识符 命题变元命题变元：命题标识符如仅是表示任意命题的位置标：命题标识符如仅是表示任意命题的位置标 志，就称为命题变元。
志，就称为命题变元原子变元原子变元：当命题变元表示原子命题时，该变元称为：当命题变元表示原子命题时，该变元称为 原子变元原子变元命题变元也用命题变元也用A,B,…,P,Q,P1,P2,P3 , …, 表示1.1.3 命题的分类：命题的分类：简简单单/原原子子命命题题：：不不能能分分解解为为更更简简单单的的陈陈述述语语句句的的命命题题(如如上例中的命题上例中的命题)复合命题：复合命题：由简单命题通过由简单命题通过联结词联结词联结而成的命题联结而成的命题 联结词就是复合命题中的运算符联结词就是复合命题中的运算符 注意注意：：（（1））一一个个符符号号(如如P), 它它表表示示的的是是命命题题常常量量还还是是命命题题变变元元，，一般由上下文来确定一般由上下文来确定2））命命题题变变元元可可以以表表示示任任意意命命题题，，它它不不能能确确定定真真值值，，故故命命题题变变元元不不是是命命题题这这与与“变变数数x不不是是数数”是是一一样样的道理小小结结：：本本节节主主要要介介绍绍了了命命题题、、命命题题的的真真值值、、原原子子命命题题、、复复合合命命题题、、命命题题标标识识符符、、命命题题常常量量、、命命题题变变元元和和原原子子变变元元的的概概念念。
重重点点理理解解和和掌掌握握命命题题、、命命题题变变元元两两个个概概念 作业：作业：P8 （（1）） 13第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.2逻逻辑联结词辑联结词(Logical Connectives)1.2.1 否定联结词否定联结词(Negation) ┐1.2.2 合取联结词合取联结词(Conjunction)∧∧1.2.3 析取联结词析取联结词(Disjunction)∨∨1.2.4 条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)→1.2.5 双条件联结双条件联结(等值联结词等值联结词Biconditional) 14 在命题逻辑中,主要研究的是复合命题,而复合命题是由原子命题与逻辑联结词组合而成,联结词组是复合命题的重要组成部分.1.2.1 否定否定联结词联结词 ┐定义1.2.1 设设P为为一一命命题题，， P的的否否定定是是一一个个新新的的复复合合命命题题, 称称为为P的的否否定定式式，，记记作作 “┐P”读读作作“非非P”. 符符号号“┐ ” 称为否定联结词。
称为否定联结词 ┐P为真当且仅当为真当且仅当P为假为假.说明说明：： “┐”属于一元属于一元(unary)运算符运算符 15•“┐”的定义也可用下表来说明的定义也可用下表来说明. 联结词联结词“┐”的定义真值表的定义真值表 P ┐P0110 16例例1. P: 天津是一个城市天津是一个城市. Q: 3是偶数是偶数.于是于是: ┐P: 天津不是一个城市天津不是一个城市. ┐Q: 3不是偶数不是偶数.例例2. P:苏州处处清洁苏州处处清洁. Q:这些都是男同学这些都是男同学. ┐P:苏州不处处清洁苏州不处处清洁 (注意注意,不是处处不清洁不是处处不清洁). ┐Q:这些不都是男同学这些不都是男同学. 171.2.2 合取合取联结联结词词(Conjunction)∧∧定定义义1.2.2 设设P,Q为为二二命命题题，，复复合合命命题题“P并并且且Q”（（或或“P与与Q”））称称为为P与与Q的的合合取取式式，，记记作作P ∧∧ Q，，符符号号“∧∧” 称称为为合合取取联联结结词词. P P Q Q 为为真真当当且且仅仅当当P P和和Q Q同同时为真时为真. . 联结词联结词“∧∧”的定义真值表的定义真值表P PQ Q P P Q Q 0 00 00 00 01 10 01 10 00 01 11 11 1 18说明：说明：“∧∧” 属于二元属于二元(binary)运算符运算符.合取运算特点合取运算特点：只有参与运算的二命题全为真时，运算：只有参与运算的二命题全为真时，运算 结果才为真，否则为假。
结果才为真，否则为假 自然语言中的表示自然语言中的表示“并且并且”意思的联结词，如意思的联结词，如“既既…又又…”、、“不不但但…而而且且…”、、“虽虽然然…但但是是…”、、“一一面面…一一面面…”、、 “…和和…”、、 “…与与…”等都可以符号化为等都可以符号化为∧∧ 19例例3. 将下列命题符号化将下列命题符号化. (1) 李平既聪明又用功李平既聪明又用功. (2) 李平虽然聪明李平虽然聪明, 但不用功但不用功. (3)李平不但聪明李平不但聪明,而且用功而且用功. (4)李平不是不聪明李平不是不聪明,而是不用功而是不用功.解解: 设设 P:李平聪明李平聪明. Q:李平用功李平用功.则则 (1) P∧Q (2) P∧ ┐Q (3) P∧Q (4) ┐(┐P)∧ ┐Q 注意注意：：不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词∧∧ ！！例如例如: (1)见课本见课本P11 例题例题6 (2) 李敏和李华是姐妹李敏和李华是姐妹 （（3）李敏和张华是朋友。
李敏和张华是朋友 20 例例4. 试生成下列命题的合取试生成下列命题的合取. (1) P: 我们在我们在XNA303. Q: 今天是星期二今天是星期二. (2) S：：李平在吃饭李平在吃饭. R：张明在吃饭张明在吃饭. 解解: (1) P∧Q :我们在我们在XNA303且今天是星期二且今天是星期二. (2) S∧R:R:李平与张明在吃饭李平与张明在吃饭. 211.2.3 析取联结析取联结词词(Disjunction)∨∨定定义义1.2.3 设设P,Q为为二二命命题题，，复复合合命命题题“P或或Q” 称称为为P与与Q的的析析取取式式，，记记作作P∨∨Q ，，符符号号∨∨称称为为析析取取联联结结词词. P∨∨Q为为真真当且仅当当且仅当 P与与Q中至少有一个为真中至少有一个为真. 联结词联结词“∨∨”的定义真值表的定义真值表P PQ Q P P Q Q 0 00 00 00 01 11 11 10 01 11 11 11 1 22说明：说明：“∨∨” 属于二元属于二元(binary)运算符运算符.析析取取运运算算特特点点：：只只有有参参与与运运算算的的二二命命题题全全为为假假时时，，运算结果才为假，否则为真。
运算结果才为假，否则为真 由由析析取取联联结结词词的的定定义义可可以以看看出出，， “∨∨”与与汉汉语语中中的的联联结结词词“或或”意意义义相相近近，，但但又又不不完完全全相相同同在在现现代代汉汉语语中中，，联联结结词词的的“或或”实实际际上上有有“可可可可兼兼兼兼或或或或”和和“排斥或排斥或排斥或排斥或”之分考察下面命题：之分考察下面命题：（（1）小王爱打球或爱跑步小王爱打球或爱跑步可兼或）可兼或）可兼或）可兼或） 设设P：小王爱打球小王爱打球 Q：小王爱跑步小王爱跑步 则上述命题可符号化为：则上述命题可符号化为：P ∨∨ Q 23（（2）林芳学过英语或法语林芳学过英语或法语 （（可兼或）可兼或）可兼或）可兼或）设设P：：林芳学过英语林芳学过英语 Q：：林芳学过法语林芳学过法语 则上述命题可符号化为：则上述命题可符号化为： P ∨∨ Q（（3）派小王或小李中的一人去开会派小王或小李中的一人去开会排斥或排斥或排斥或排斥或）） 设设P：：派小王去开会派小王去开会Q：：派小李去开会派小李去开会 则上述命题可符号化为：则上述命题可符号化为：(P∧∧ Q) ∨∨( P∧∧Q)（（4）人固有一死，或重于泰山或轻于鸿毛）人固有一死，或重于泰山或轻于鸿毛.(排斥或排斥或排斥或排斥或）） （（5））ab=0, 即即a=0 或或 b=0. （（可兼或）可兼或）可兼或）可兼或）由此可见由此可见, “P ∨∨ Q”表示的是表示的是“可兼或可兼或可兼或可兼或” ”. . 注注意意：：当当P和和Q客客观观上上不不能能同同时时发发生生时时，，“P或或Q”可可以符号化为以符号化为“P ∨∨ Q”。
例如：小王现在在宿舍或在图书馆例如：小王现在在宿舍或在图书馆 设设 P：小王现在在宿舍小王现在在宿舍Q：小王现在在图书馆小王现在在图书馆 则上述命题可符号化为：则上述命题可符号化为：P ∨∨ Q 251.2.4. 条件联结词条件联结词(蕴涵联结词蕴涵联结词Conditional)→定定义义1.2.4 设设P,Q为为二二命命题题，，复复合合命命题题“如如果果P则则Q(若若P则则Q)” 称称为为P与与Q的的条条件件命命题题,记记作作P Q. P Q为为假假当当且且仅仅当当P为为真真且且Q为为假假.称称符符号号“”为为条条件件联联结结词词并并称称P为前件，为前件，Q为后件为后件. • 联结词联结词“”的定义真值表的定义真值表P PQ QP →P → Q Q0 00 01 10 01 11 11 10 00 01 11 11 1 26 注注：：（（1））P Q表表示示的的基基本本逻逻辑辑关关系系是是,Q是是P的的必必要要条条件件或或P是是Q的的充充分分条条件件. 因因此此复复合合命命题题“只只要要P P就就Q Q”、、“因因为为P P，，所所以以Q Q”、、“P P仅仅当当Q Q”、、“只有只有Q才才P”等都可以符号化为等都可以符号化为P Q 的形式。
的形式 （（2）） ”“ 属于二元属于二元(binary)运算符例例5. 5. 将下列命题符号化将下列命题符号化 （（1 1）天不下雨，则草木枯黄天不下雨，则草木枯黄 P P：天下雨 Q Q：草木枯黄草木枯黄 则原命题可表示为：则原命题可表示为： ┐P→QP→Q 27 （（2）如果小明学日语，小华学英语，则小芳学德语如果小明学日语，小华学英语，则小芳学德语 P P：小明学日语：小明学日语 Q Q：小华学英语：小华学英语 R R：小芳学德语：小芳学德语. . 则原命题可表示为：则原命题可表示为：(P∧Q)→R(P∧Q)→R （（3）只要不下雨，我就骑自行车上班只要不下雨，我就骑自行车上班 P：天下雨Q：我骑自行车上班我骑自行车上班 则原命题可表示为：则原命题可表示为： ┐P→QP→Q。
（（4））只有只有不下雨，我才骑自行车上班不下雨，我才骑自行车上班 P：天下雨Q：我骑自行车上班我骑自行车上班 则原命题可表示为：则原命题可表示为： Q Q →→┐P P （（5））如果如果 2+2=4, 则则太阳从东方升起太阳从东方升起 (P →→Q, T) P Q 如果如果 2+2=4, 则则太阳从西方升起太阳从西方升起 (P →→R, F) R 如果如果 2+2 4, 则太阳从东方升起则太阳从东方升起 (┐┐P →→Q , T) 如果如果 2+2 4, 则太阳从西方升起则太阳从西方升起 (┐┐P →→R, T)注意注意: (1)与自然语言的不同：与自然语言的不同：前件与后件可以没有任何内在联系！前件与后件可以没有任何内在联系！ (2) 在数学中，在数学中，“若若P则则Q”往往表示前件往往表示前件P为真，则后件为真，则后件Q为真的为真的推理关系推理关系. 但数理逻辑中，当前件但数理逻辑中，当前件P为假时，为假时， P →→Q的真值为真。
的真值为真 291.2.5 双条件联结双条件联结(等值联结词等值联结词Biconditional) 定定义义1.2.5 设设P,Q为为二二命命题题，，复复合合命命题题“P当当且且仅仅当当Q” 称称为为P与与Q的的双双条条件件命命题题，，记记作作P iff Q或或 PQ，，符符号号称称为为双双条条件件（（等等值值））联联结结词词 PQ为为真真当当且且仅仅当当P，，Q真值相同真值相同 联结词联结词“”的定义真值表的定义真值表P PQ QP P Q Q0 00 01 10 01 10 01 10 00 01 11 11 1 30注：注：（（1 1））P P仅当仅当Q Q 可译为可译为P→QP→Q P P当当Q Q 可译为可译为Q→PQ→P P当且仅当当且仅当Q 译为译为PQ （（2））“”属于二元属于二元(binary)运算符 (3) 双条件命题双条件命题PQ所表达的逻辑关系是所表达的逻辑关系是, P与与Q互互为充分必要条件为充分必要条件,相当于相当于(P Q) ∧∧(Q P). 只要只要P与与Q的的真值同为真值同为1或同为或同为0, PQ的真值就为的真值就为1, 否则否则PQ的真的真值为值为0. 双条件联结词连接的两个命题之间可以没有因双条件联结词连接的两个命题之间可以没有因果关系。
果关系例例6.6.分析下列命题的真值分析下列命题的真值. . (1) 2+2=4 (1) 2+2=4 当且仅当当且仅当3 3是奇数是奇数 . (P PQ)Q) P P：： 2+2=4. Q2+2=4. Q：：3 3是奇数是奇数 . . 31 (2) 2+2=4 2+2=4 当且仅当当且仅当3 3不是奇数不是奇数 . (P P┐Q)┐Q)(3) 2+2 4 (3) 2+2 4 当且仅当当且仅当3 3是奇数是奇数 . (┐P┐PQ)Q)(4) 2+2 4 (4) 2+2 4 当且仅当当且仅当3 3不是奇数不是奇数 . (┐P┐P┐Q)┐Q)约约 定定: :1. 1. 运算次序优先级：运算次序优先级：┐┐，， ，， ，，→→，，. . 2. 2. 相同的运算符按从左至右次序计算，否则要相同的运算符按从左至右次序计算，否则要 加上括号加上括号 3.3.最外层圆括号可省去最外层圆括号可省去 小结小结: 本节介绍了五种联结词本节介绍了五种联结词(┐┐，， ，， ，，→→，，),),重点重点是理解和掌握是理解和掌握五种联结词的内涵及它们与自然语言中五种联结词的内涵及它们与自然语言中相应联结词的不同之处相应联结词的不同之处. 32作业作业: 1. P8 (3), (5). 2. 预习预习§1.3, §1.4思考题思考题: 1. 何谓合式公式何谓合式公式? 2. 复合命题符号化的基本步骤是什么复合命题符号化的基本步骤是什么? 3.何谓真值表何谓真值表? 4. 两个命题公式等价的涵义是什么两个命题公式等价的涵义是什么? 5.两个等价的命题公式其真值表有何关系两个等价的命题公式其真值表有何关系? 33第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic））））1.3命题公式与翻译命题公式与翻译1.3.1 命题公式命题公式1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)1.3.1 命题合式公式命题合式公式(Well-formed formula)(wff)ü定义定义1.3.1: :单个命题变元和命题常量称为单个命题变元和命题常量称为原子公式原子公式。
ü命命题题合合式式公公式式是是由由命命题题变变元元、、命命题题常常量量、、联联结结词词和和圆圆括括号号按按一一定定的的逻逻辑辑关关系系联联结结起起来来的的符符号号串串我我们们以以如如下下递递归归的的形形式式来来定定义合式公式：义合式公式： 34ü定义定义1.3.2：：(1)(1)原子公式是原子公式是合式合式公式公式( (wffwff) ) （（2）若）若A是合式公式，则是合式公式，则( A)也是合式公式也是合式公式 （（3））若若A，，B是是合合式式公公式式，，则则(A∧∧B)，，(A∨∨B)，，(AB)，，(AB)也是合式公式也是合式公式 （（4））当当且且仅仅当当有有限限次次地地应应用用(1)~(3)所所得得到到的的包包含含原原子公式、子公式、联结词和括号的符号串是合式公式联结词和括号的符号串是合式公式注注: (1)合式公式也称为命题公式，并简称为公式合式公式也称为命题公式，并简称为公式 (2)命命题题公公式式一一般般不不是是命命题题,仅仅当当公公式式中中的的命命题题变变元元用用确确定定的的命命题题代代入入时时,才才得得到到一一个个命命题题.其其真真值值依依赖赖于代换变元的那些命题的真值于代换变元的那些命题的真值. 35例例1 1：：指出指出(P→(P(P→(P Q))Q))是否是命题公式是否是命题公式( (wffwff) )，如果是，则具体说明。
如果是，则具体说明解：解： ① ① P P是是wffwff 由由(1)(1) ② Q ② Q是是wffwff 由由(1)(1)③ P③ P Q Q是是wffwff 由由(3) ①②(3) ①②④ (P→(P④ (P→(P Q)) Q)) 由由(3) ①③(3) ①③例例2: 2: (P Q) , (R ∧∧ S) ∨ ∨ Q , P，，( P)等均为合等均为合式公式，而式公式，而PQ ∨∨S , (P W) Q)等不是合式等不是合式公式 36•1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)•有了命题演算的合式公式的概念有了命题演算的合式公式的概念,我们可我们可以把自然语言中的有些语句以把自然语言中的有些语句(复合命题复合命题),翻译成数理逻辑中的符号形式翻译成数理逻辑中的符号形式.基本步骤基本步骤如下如下:•(1) 分析出各简单命题分析出各简单命题,将它们符号化将它们符号化;•(2) 使用合适的联结词使用合适的联结词,把简单命题逐个的把简单命题逐个的联结起来联结起来,组成复合命题的符号化表示组成复合命题的符号化表示. 37•例例3：：•1) 我今天进城，除非下雨。
我今天进城，除非下雨[1-3.(7)]•2) 仅当你走我将留下仅当你走我将留下•3) 假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里• 读书或看报读书或看报•4)除非你努力，否则你将失败除非你努力，否则你将失败[P11例例5]•5)一个人起初说：一个人起初说：“占据空间的、有质量的而且不占据空间的、有质量的而且不断变化的叫做物质断变化的叫做物质”；后来他改说，；后来他改说，“占据空间占据空间的有质量的叫做物质，而物质是不断变化的的有质量的叫做物质，而物质是不断变化的问他前后主张的差异在什么地方，试以命题形式问他前后主张的差异在什么地方，试以命题形式进行分析进行分析 [1-3.(6)] 38•例例4：：P10 例题例题1 •小结小结：本节介了命题公式的概念及复合：本节介了命题公式的概念及复合命题的符号化命题的符号化.重点是理解命题公式的递重点是理解命题公式的递归定义归定义,掌握复合命题的符号化方法掌握复合命题的符号化方法.•作业作业: P12 (1),(5) 39第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.4真值真值表与等价公式表与等价公式1.4.1 真值表真值表(Truth Table)1.4.2 等价公式等价公式(Propositional Equivalences)Propositional Equivalences)1.4.1 真值表真值表 前面在定义联结词时前面在定义联结词时,曾经使用过真值表曾经使用过真值表,下面给出下面给出真值表的定义真值表的定义. 定义定义1.4.1 (对公式的赋值或解释对公式的赋值或解释)设设P1 , P2 ,…,Pn是出是出现在公式现在公式A中的全部的命题变元中的全部的命题变元, 给给P1 , P2 ,…,Pn各指各指定一个真值，称为对定一个真值，称为对A的一个的一个赋值赋值或或解释解释。
若指定的若指定的一组值使一组值使A的真值为真的真值为真(假假), 称这组值为称这组值为A的的成真成真(假假)赋值赋值. 40比比如如:对对公公式式(PQ)∧∧R,赋赋值值011(即即令令P=0,Q=1,R=1) 为为 (PQ)∧∧R的的 成成 真真 赋赋 值值 ; 另另 一一 组组 赋赋 值值 010为为(PQ)∧∧R的成假赋值；还有的成假赋值；还有000，，001，，111……考考虑虑：：含含有有n个个命命题题变变元元的的公公式式共共有有多多少少组组不同的赋值？不同的赋值？定定义义1.4.2(真真值值表表)在在命命题题公公式式A中中, 对对于于命命题题变变元元的的每每一一组组赋赋值值和和由由它它们们所所确确定定的的命命题题公公式式A的的真真值值列列成成表，称做命题公式表，称做命题公式A 的的真值表真值表 41对公式对公式A构造真值表的具体步骤为：构造真值表的具体步骤为：（（1））找找出出公公式式中中所所有有命命题题变变元元P1 , P2 ,…,Pn , 列出全部的列出全部的2n组赋值2））按按从从小小到到大大的的顺顺序序列列出出对对命命题题变变元元P1 , P2 ,…,Pn ,的全部的全部2n组赋值。
组赋值3））对对应应各各组组赋赋值值计计算算出出公公式式A的的真真值值，，并并将其列在对应赋值的后面将其列在对应赋值的后面 42例例1. 1. 给出给出┐┐(P(P Q)Q)(┐P(┐P ┐Q)┐Q)的真值表：的真值表：P P Q Q P P Q Q┐(P┐(P Q Q) )┐P┐P ┐┐Q Q┐(P┐(P Q) Q) (┐P (┐P ┐Q)┐Q)0 0 0 00 01 11 11 10 0 1 10 01 11 11 11 1 0 00 01 11 11 11 1 1 11 10 00 01 1 43例例2：构造公式：构造公式 (P Q) ∧∧R的的 真值表PQRPQ(P Q) ∧∧R0001000111010100111110000101001101011111 44•练习练习1：构造公式：构造公式 (PQ)( Q P真值表P Q P QP Q Q P(P Q)( Q P)0011111011011110010011100111 45PQ (P Q) (P Q) (P Q) ∧ Q00100011001001011100练习练习2：构造公式：构造公式 (P Q ∧∧Q 真值表。
真值表 46•1.4.2 等价公式等价公式•给定给定n个个 命题命题变元变元, 按合式按合式公式的形公式的形成规则可以形成无数多个命题公式成规则可以形成无数多个命题公式, 但这但这些无穷尽的些无穷尽的命题公式中，有些具有相同的命题公式中，有些具有相同的真值表考虑：考虑：由由n个命题变元能生成个命题变元能生成??? 种真值种真值(表表)不同的命题公式？不同的命题公式？ 47•1.4.2 等价公式等价公式•定义定义1.4.3: 给定两个命题公式给定两个命题公式A和和B,设设P1 , P2 ,…,Pn为出现于为出现于A和和B中的所有原子变元中的所有原子变元,若给若给P1 , P2 ,…,Pn任一组真值指派任一组真值指派, A和和B的真值都相同的真值都相同,则称则称A和和B是是等价的或逻辑相等等价的或逻辑相等.记作记作A B•注注: (1) “ ”不是逻辑联结词不是逻辑联结词.•(2)命题公式之间的逻辑相等关系具有命题公式之间的逻辑相等关系具有：： 自反性：自反性：A A ；对称性：若；对称性：若A B，则，则B A；； 传递性：若传递性：若A B且且B C，则，则A C。
48•证明公式等价的方法：证明公式等价的方法：•1. 真值表法真值表法 2. 等值演算法等值演算法v1. 真值表法真值表法 •例例1. ┐(P1. ┐(P Q) Q) (┐P(┐P ┐Q) ┐Q) 见真值表例题见真值表例题1.1.•例例2. 2. 证明证明: P: PQ Q (P→Q)(P→Q) (Q→P)(Q→P)P PQ QP PQ →PQ→PP→QP→Q (P→Q)(P→Q) (Q→P(Q→P) )0 00 01 11 11 11 10 01 10 00 01 10 01 10 00 01 10 00 01 11 11 11 11 11 1 49例例3：判断公式：判断公式 P(QR)、、(P∧∧Q)R是否等价是否等价P Q RP ∧ ∧ R P (Q R) (P ∧∧ Q R00001110010111010001101101111000111101011111010001111111 50 由真值表可知，两个公式为等价式由真值表可知，两个公式为等价式•2、等值演算法、等值演算法(Equivalent Caculation)（利用（利用P15表表1-4.8)•重要的等价式重要的等价式(补充补充): 11. 蕴涵等值式蕴涵等值式: : P PQ Q ┐P ┐P Q Q 12. 等价等价等值式等值式: : P PQ Q (P→Q)(P→Q) (Q→P)(Q→P) 13. 假言易位假言易位: P PQ Q ┐Q ┐Q ┐P┐P 14. 等价否定等价否定等值式等值式: : P PQ Q ┐P┐P┐Q ┐Q 15. 归谬论归谬论: (P PQ Q ) ( ( P P ┐Q)┐Q) ┐P ┐P 51 其中其中P, Q, R等代表任意命题公式等代表任意命题公式. 这样上面的每一这样上面的每一个公式都是一个模式个公式都是一个模式, 它可以代表无数多个同类它可以代表无数多个同类型的命题公式型的命题公式. 例如例如, P P ┐P┐PT T 中中, , 用用(P(P Q)Q)置置换换P,P,则得则得 (P(P Q)Q) ┐(P┐(P Q)Q)T ,T ,用用┐┐P P置换置换P,P,则则得得 (┐P(┐P) ) ┐(┐P┐(┐P) )T T 。
等值演算中使用的一条重要规则：等值演算中使用的一条重要规则：置换规则置换规则 定义定义1.4.4(1.4.4(子公式子公式) )：：如果如果X X是是wffwff A A的的一部分一部分, ,且且X X本身也是本身也是wffwff，则称，则称X X是是A A的的子公式例如子公式例如, P, P (P(P Q)Q)为为Q Q (P P (P(P Q))Q))的子公式的子公式 52定理定理1.4.1(置换定理置换定理Axiom of replacement)设设X X是是wffwff A A的子的子wffwff，若，若X XY Y，则若将，则若将A A中的中的X X用用Y Y来置换，所来置换，所得公式得公式B B与与A A等价，即等价，即A AB B证：因为对变元的任一指派证：因为对变元的任一指派,X,X与与Y Y真值相同，所以真值相同，所以Y Y 取代取代X X后，公式后，公式B B与公式与公式A A对变元的任一指派真对变元的任一指派真值也相同值也相同, ,所以所以A AB B注注: : 满足满足定理定理1.4.1的条件的置换称为等价置换的条件的置换称为等价置换(或等或等价代换价代换).定义定义1.4.5(1.4.5(等值演算等值演算) )：：根据已知的等价公式根据已知的等价公式, ,推演推演出另外一些等价公式的过程称为出另外一些等价公式的过程称为等值演算等值演算. 53例例1 1：： 证明证明 Q→Q→（（P P （（P P Q Q））））Q→PQ→P 证证: Q→: Q→（（P P （（P P Q Q））））Q→PQ→P ~~~~~~~~~~~ ~~~~~~~~~~~ P( P(吸收律吸收律) ) 例例2 2：： 证明证明 P P ┐Q┐Q Q Q P P Q Q证：证： (P(P ┐Q)┐Q) Q Q(P(P Q)Q) ( (┐Q┐Q Q)Q)( (P P Q)Q) T TP P Q Q例例3 3：证明（：证明（P→QP→Q））→→（（Q Q P P）） P P Q Q R R证：（证：（P→QP→Q））→→（（Q Q P P）） （（┐┐P P Q Q））→→（（Q Q R R）） ┐┐（（┐┐P P Q Q）） （（Q Q R R）） （（P P ┐Q┐Q）） （（Q Q R R）） （（P P Q Q R R）） （（┐┐Q Q Q Q R R）） P Q R 54例例4：：验证验证P(QR) (P ∧∧ Q) R证证: 右右 (P ∧∧ Q) ∨∨ R P ∨∨ Q ∨∨ R P ∨∨ ( Q ∨∨ R) P ∨∨ (Q R)) P (Q R)练：练：1.((P Q) ∧∧(P R)) P (Q ∧∧ R) 2.(P ∧∧ Q) ∨∨( P ∧∧ Q) (P ∨∨ Q) ∧∧ (P ∧∧ Q) 55v等等值值演演算算在在计计算算机机硬硬件件设设计计中中,在在开开关关理理论论和和电电子子元元器器件中都占有重要地位件中都占有重要地位.v小小结结: 本本节节介介绍绍了了真真值值表表、、公公式式等等价价、、等等值值演演算算和和等等价价置置换换等等概概念念，，给给出出了了常常用用的的重重要要等等价价公公式式（（24个个））。
重重点点掌掌握握用用真真值值表表法法验验证证公公式式的的等等价价性性和和等等值值演演算算法法推演两个公式等价推演两个公式等价作业：作业：P17 1 c,e, 4 a,c, 7d,e, 8.预习预习: 1.5, 1.6思考题：思考题：9 561.5.1 命题公式的分类命题公式的分类1.5.2 重言式重言式(Tautology)Tautology)与矛盾式与矛盾式 (contradictory)的性质的性质1.5.3 蕴含式蕴含式( ( Implication)Implication)第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.5重言重言式与式与蕴含蕴含式式(Tautology and Implication)(Tautology and Implication) 571.5.1 命题公式的分类命题公式的分类 复合命题复合命题(compound propositions)定义定义1.5.1 设设A为任一命题公式，为任一命题公式，（（1））若若A在在其其各各种种赋赋值值下下的的取取值值均均为为真真，，则则称称A是是重言式重言式或或永真式永真式, 记为记为T或或1。
2））若若A在在其其各各种种赋赋值值下下的的取取值值均均为为假假，，则则称称A是是矛盾式矛盾式或或永假式永假式, 记为记为F或或03））若若A不不是是矛矛盾盾式式则则称称A为为可可满满足足式式(satisfiable)注注: 由定义可知由定义可知,重言式一定是可满足式重言式一定是可满足式,反之不真反之不真. 58第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.5重言重言式与蕴含式式与蕴含式(Tautology and Implication)(Tautology and Implication) 判别命题公式的类型有两种方法判别命题公式的类型有两种方法: 真值表法和等值真值表法和等值演算法演算法. 等值演算法等值演算法是将所给命题公式通过等值演算化为最是将所给命题公式通过等值演算化为最简单的形式简单的形式, 然后再进行判别然后再进行判别.例例1.判别下列命题公式的类型判别下列命题公式的类型.(1). Q∨┓∨┓((┓┓P∨∨Q)∧∧P) (重言式重言式)(2). (P∨┓∨┓P) (Q∧┓∧┓Q)∧∧R (矛盾式矛盾式)(3). (P Q)∧┓∧┓P. (可满足式可满足式) 591.5.2 重重言言式式(Tautology)Tautology)与与矛矛盾盾式式(contradictory)的的性性质质定定理理1.5.1:任任何何两两个个重重言言式式的的合合取取或或析析取取,仍仍然然是是一一重重言言式式.（由幂等律立得）（由幂等律立得）•证明证明:设设A和和B为两个重言式为两个重言式,则不论则不论A和和B的分量指派任的分量指派任何真值何真值,总有总有A为为T,B为为T,故故A ∧∧ B T,A T,A ∨∨ B B T T•定理定理1.5.2:1.5.2:一个重言式一个重言式( (矛盾式矛盾式), ,对同一分量都用任何合对同一分量都用任何合式公式置换式公式置换, ,其结果仍为一重言式其结果仍为一重言式( (矛盾式矛盾式). .•证明证明: 由于由于重言式重言式( (矛盾式矛盾式)的真值与对变元的赋值无关，的真值与对变元的赋值无关，故对同一变元以任何故对同一变元以任何合式公式置换后，重言式合式公式置换后，重言式( (矛盾式矛盾式)的真值仍永为的真值仍永为T（（F）。
60•定理定理1.5.3：： A,B是两个命题公式，是两个命题公式，A B的的充要条件是充要条件是A B为重言式为重言式证明证明: : 若若A AB B为重言式，则为重言式，则A AB B永为永为T T，即，即A A，，B B的真的真 值表相同，所以值表相同，所以A AB B 反之，反之，若若A A B B，则，则A A，，B B真值表相同，真值表相同， 所以所以 A AB B永为永为T T，所以，所以A AB B为重言式为重言式1.5.3 蕴含式蕴含式( ( Implication)Implication)•定义定义1.5.2：当且仅当：当且仅当P Q是一个重言式时，是一个重言式时，我们称我们称“P蕴含蕴含Q”，并记作，并记作P Q. 61•它们之间具有如下关系它们之间具有如下关系: PQ Q P 由由P21 表表1-5.1 QP P Q 可以得出可以得出•因此因此, 要证明要证明P Q有三种方法有三种方法:•1)1)真值表法真值表法: :即列出即列出PQ的的真值表真值表, ,观察其是否为永真。
观察其是否为永真•2)2)直接证法直接证法: :假定前件假定前件P P是真，推出后件是真，推出后件Q Q是真•3)3)间接证法间接证法: :假定后件是假，推出前件是假假定后件是假，推出前件是假, ,即证即证 Q P 原命题原命题逆换式逆换式反换式反换式逆反式逆反式PP P Q Q P 62例例: : 证明证明┐┐Q Q （（P→QP→Q））┐┐P P1) 1) 法法1 1：真值表：真值表2) 2) 法法2 2：若：若 ┐ ┐Q Q ( (P→Q)P→Q)为真，则为真，则 ┐ ┐Q Q，，P→QP→Q为真，为真， 所以所以Q Q为假，为假，P P为假，所以为假，所以┐┐P P为真3) 3) 法法3 3：若：若┐┐P P为假，则为假，则P P为真，再分二种情况：为真，再分二种情况： ① ①若若Q Q为真，则为真，则┐┐Q Q为假为假, ,从而从而┐┐Q Q （（P→QP→Q）） 为假为假. .②②若若Q Q为假，则为假，则P→QP→Q为假，则为假，则┐┐Q Q （（P→QP→Q）为假）为假. .根据根据① ②① ②，所以，所以 ┐ ┐Q Q （（P→QP→Q））┐┐P PP21 P21 表表1-5.21-5.2给出了给出了1414个个蕴含式蕴含式, 它们都可以用上述方法加它们都可以用上述方法加以推证以推证. 63•等价式与蕴含式的关系等价式与蕴含式的关系:•定理定理1.5.4:1.5.4: 设设P,QP,Q为任意两个命题公式为任意两个命题公式,P,PQ Q的充的充要条件为要条件为P PQ Q且且Q QP.P.•证：若证：若P PQ Q，则，则P PQ Q为永真式为永真式 因为因为 P PQ Q （（P→QP→Q）） （（Q→PQ→P）） 所以所以 P→QP→Q，，Q→PQ→P为永真式为永真式, ,从而从而 P PQ Q，，Q QP.P. 反之，若反之，若P PQ Q，，Q QP P，则，则P→QP→Q，，Q→PQ→P为永真式为永真式, , 所以（所以（P→QP→Q）） （（Q→PQ→P）为永真式，）为永真式， 从而从而 P PQ Q为永真式，即为永真式，即P PQ.Q. 64•蕴含的性质蕴含的性质:•设设A A，，B B，，C C为任意为任意wffwff, ,1) 1) 若若A AB B，且，且A A为永真式，则为永真式，则B B必为永真式必为永真式. .2) 2) 若若A AB B，，B BC C，则，则A AC.C.3) 3) 若若A AB B，，A AC C，则，则A AB B C.C.4) 4) 若若A AB B且且C CB B，则，则A A C CB.B.证：证：1)1)因为因为A→BA→B，，A A永为永为T,T,所以所以B B必永为必永为T.T. 2) 2)由由I I1111 （（A→B)A→B) ( (B→CB→C））A→C,A→C,所以若所以若A AB B，， B BC C，则（，则（A→B)A→B) ( (B→CB→C）永为）永为T,T,从而从而A→CA→C永永 为为T, T, 故故A AC.C. 653) 3) （（A→BA→B）） （（A→CA→C）） （（┐┐A A B B）） （（┐┐A A C C）） ┐┐A A （（B B C C）） A→BA→B C C4) 4) （（A→BA→B）） （（C→BC→B）） （（┐┐A A B B）） （（┐┐C C B B）） （（┐┐A A ┐C┐C）） B B ┐┐（（A A C C）） B B A A C→BC→B 66•小小结结：：本本节节介介绍绍了了命命题题公公式式的的分分类类，，重重言言式式、、矛矛盾盾式式与蕴含式的概念及其性质，等价式与蕴涵式的关系。
与蕴含式的概念及其性质，等价式与蕴涵式的关系•重点掌握重点掌握: （（1 1）用等值演算法判别命题公式的类型用等值演算法判别命题公式的类型 （（2 2）重言式、矛盾式与蕴涵式的性质重言式、矛盾式与蕴涵式的性质 （（3 3）等价式与蕴涵式的关系等价式与蕴涵式的关系•作业作业: P23 (1)c,d ,(2) a ,(9).: P23 (1)c,d ,(2) a ,(9).•预习预习:1.6 :1.6 •思考题思考题:1) :1) 为什么要引入联结词为什么要引入联结词 ? ? 2) 2) 什么是最小联结词组什么是最小联结词组? ? 67第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.6其它其它联结词联结词(Other Connectives)(Other Connectives)1.6.1 不可兼析取不可兼析取(排斥或排斥或/异或异或)(exclusive or)1.6.2 与非联结词与非联结词(Nand)1.6.3 或非联结词或非联结词(Nor)1.6.4 条件否定联结词条件否定联结词(Non-conditional)1.6.5 最最小小联联结结词词组组(The minimal set of connectives) 68 在第二节在第二节(1.2)中我们定义了五种基本的联结词中我们定义了五种基本的联结词┐┐，， ，， ，，→ → ，，, ,但在但在命题逻辑中命题逻辑中,这些联结词还不能很广泛这些联结词还不能很广泛地直接表达命题之间的联系地直接表达命题之间的联系(例如例如, “P异或异或Q”只能间接地只能间接地表表示示为为(P ┐Q)┐Q) (┐(┐P Q)),Q)),为为此此本本节节再再给给出出逻逻辑辑设设计计中中常用的另外四种常用的另外四种联结词联结词.1.6.1 不可兼析取不可兼析取(排斥或排斥或/异或异或)(exclusive or)定定义义1.6.1:设设P,Q为为二二命命题题，，复复合合命命题题“P, Q之之中中恰恰有有一一个个为为真真” 称称为为P与与Q的的不不可可兼兼析析取取，，记记作作P Q，，符符号号“ ” 称称为为异异或或联联结结词词. P P Q Q 为为真真当当且且仅仅当当P P和和Q Q的的真值不同真值不同. . 69 联结词联结词“ ”的定义真值表的定义真值表P PQ Q P P Q Q 0 00 00 00 01 11 11 10 01 11 11 10 0定义了定义了联结词联结词“ ”后后, 命题逻辑中的有些命题就可命题逻辑中的有些命题就可以符号化为非常简捷的形式以符号化为非常简捷的形式.例例: 派小王或小李中的一人去开会。
派小王或小李中的一人去开会排斥或排斥或排斥或排斥或）） 设设P：：派小王去开会派小王去开会Q：：派小李去开会派小李去开会 则上述命题可符号化为：则上述命题可符号化为：(P Q) 70说明：说明：“ ” 属于二元属于二元(binary)运算符运算符.联结词联结词“ ”的性质的性质: 设设P, Q, R为命题公式为命题公式, 则有则有(1) P Q Q P (交换律交换律)(2) (P Q) R P (Q R) (结合律结合律)(3) P∧(Q R) (P∧Q ) (P∧R) (分配律分配律)(4) (P Q) (P∧∧ Q) ∨∨( P∧∧Q)(5) (P Q) (PQ)(6) P P F, F P P, T P P 71 定定理理1.6.1:设设P, Q, R为为命命题题公公式式, 如如果果 P QR,R,则则 P RQ ,Q RP, P, 且且P Q R P Q R 为一矛盾式为一矛盾式. . 证证: : 由由 P QR R 得得 P RP RP (P Q)P (P Q)(P P) Q(P P) QF QF QQ Q Q R Q RQ (P Q)Q (P Q)F PF PP P P Q R P Q RR RR RF F 721.6.2 与非联结词与非联结词(Nand ↑)定定义义1.6.2 设设P,Q为为二二命命题题，，复复合合命命题题“P与与Q的的否否定定” 称称为为P与与Q的的与与非非式式，，记记作作P↑Q，，符符号号“↑” 称称为为与与非非联联结词结词. P↑Q P↑Q 为真当且仅当为真当且仅当P P和和Q Q不同时为真不同时为真. . 联结词联结词“↑”的定义真值表的定义真值表P PQ Q P P↑Q Q 0 00 01 10 01 11 11 10 01 11 11 10 0 73说明说明: (1) 由定义可知由定义可知, P↑Q (P∧∧Q) (2)“↑” 属于二元属于二元(binary)运算符运算符.联结词联结词“↑”的性质的性质: (1) P↑P ( P∧P∧P) P (2) (P↑Q)↑(P↑Q) ( P↑Q Q)(P∧Q∧Q) (3)((3)(P↑P)↑(Q↑Q) P↑ Q ( P∧∧ Q) P∨∨Q 741.6.3 或非联结词或非联结词(Nor)定定义义1.6.3 设设P,Q为为二二命命题题，，复复合合命命题题“P或或Q的的否否定定” 称称为为P与与Q的的或或非非式式，，记记作作P↓Q ，，符符号号“↓”称称为为或或非非联联结结词词. P↓Q为真当且仅当为真当且仅当 P与与Q同为假同为假. 联结词联结词“↓”的定义真值表的定义真值表P PQ Q P↓Q P↓Q 0 00 01 10 01 10 01 10 00 01 11 10 0 75说明说明: (1) 由定义可知由定义可知, P↓Q (P∨∨Q) (2)“↓” 属于二元属于二元(binary)运算符运算符.↓联结词联结词“↓”的性质的性质: (1) P↓P ( P∨∨P P) P (2) (P↓Q)↓(P↓Q) (P↓Q) (P∨∨Q Q)(3)((3)(P↓P)↓(Q↓Q) P↓ Q ( P∨∨ Q)P∧∧Q 761.6.4 条件否定联结词条件否定联结词(Non-conditional)定定义义1.6.4 设设P,Q为为二二命命题题，，复复合合命命题题“P Q” 称称为为命命题题P与与Q的的条条件件否否定定式式, P Q为为真真当当且且仅仅当当P为为真真且且Q为为假假.• 联结词联结词“ ”的定义真值表的定义真值表P PQ QP →P → Q Q0 00 00 00 01 10 01 10 01 11 11 10 0 77说明说明: (1) 由定义可知由定义可知, P Q (P Q) (2)“ ” 属于二元属于二元(binary)运算符运算符.有了联结词有了联结词 后，合式公式的定义后，合式公式的定义1.3.2可加入这可加入这四个联结词四个联结词.1.6.5 最最 小小 联联 结结 词词 组组 (The minimal set of connectives)•至此至此,我们一共定义了我们一共定义了9 9个联结词个联结词,为了直接表达命题之间为了直接表达命题之间的联系的联系, ,是否还需要定义其它联结词呢是否还需要定义其它联结词呢? ? 回答是否定的回答是否定的. .即即含含n n个命题变元的所有个命题变元的所有 个互不等价的命题公式个互不等价的命题公式, ,均可由这均可由这 9 9个联结词直接表达个联结词直接表达. .下面我们以含两个命题变元下面我们以含两个命题变元P P，，Q Q的所的所有互等价的命题公式为例，来说明这一问题。
有互等价的命题公式为例，来说明这一问题 78由两个命题变元由两个命题变元P P，，Q Q所构成的互不等价的所构成的互不等价的 个命题公式个命题公式如下如下: :P QFP∧QP∧QP QPQ PQP Q P∨∨Q0 0 000000000 1 000011111 0 001100111 1 01010101 由上表可知由上表可知, 9 9个联结词足以直接表达命题之间的各种联个联结词足以直接表达命题之间的各种联系系. .二元运算中，二元运算中，9 9个联结词并不都是必要的个联结词并不都是必要的P QP QPQ ┓┓→→P┓┓PP→→QP QT0 0111111110 1000011111 0001100111 101010101 定义定义1.6.5：：在一个联结词的集合中在一个联结词的集合中,如果一个联结词可如果一个联结词可由该集合中的其它联结词定义由该集合中的其它联结词定义,则则称此称此联结词为冗余联联结词为冗余联结词结词,否则称为独立联结词否则称为独立联结词. 不含冗余联结词的联结词组不含冗余联结词的联结词组称为称为最小联结词组最小联结词组. .说明说明: :最小联结词组中的联结词构成的式子足以把一切最小联结词组中的联结词构成的式子足以把一切命题公式等价的表达出来。
命题公式等价的表达出来对于对于9 9个联结词的集合个联结词的集合{┐,{┐, , , ,→,,→,, , , , , , }, , }由于由于 (1) PQ (P→Q)(P→Q) (Q→P)(Q→P) (2) P (2) PQ Q┐P┐P Q Q (3) P P Q Q┐(┐P┐(┐P ┐Q)┐Q) (4) P P Q Q┐(┐P┐(┐P ┐Q)┐Q) 81 (5)(5) (P Q) (PQ) (6) P↑Q (P∧∧Q) (7) P↓Q (P∨∨Q) (8) P Q (P Q)故任意命题公式都可由仅包含故任意命题公式都可由仅包含{┐,┐, }或或{┐,┐, }的命题的命题公式等价代换公式等价代换.即即9 9个联结词的集合中至少有七个个联结词的集合中至少有七个冗余联冗余联结词结词. 又注意到联结词又注意到联结词{┐,┐, }和和{┐,┐, }不再有冗余联结不再有冗余联结词词, 故故{┐,┐, }或或{┐,┐, }为最小联结词组为最小联结词组.但实际中为了使但实际中为了使用方便用方便, 命题公式常常同时包含命题公式常常同时包含{┐,┐, , , }. 82例例1:试证试证{↑}{↑}是最小联结词组是最小联结词组. .证：证：┐┐P P┐(P┐(P P)P)P↑P P↑P P P Q Q┐┐(P┐┐(P Q)Q)┐(P↑Q)┐(P↑Q)(P↑Q)↑(P↑Q)(P↑Q)↑(P↑Q) P P Q Q┐(┐P┐(┐P ┐Q)┐Q)┐((P↑P)┐((P↑P) (Q↑Q))(Q↑Q)) (P↑P)↑(Q↑Q)(P↑P)↑(Q↑Q)例例2.2.试证试证{┐{┐，，→→} }是最小联结词组是最小联结词组 证：证：P P Q Q┐(┐P┐(┐P ┐Q)┐Q)┐(P→┐Q)┐(P→┐Q) P P Q Q┐(┐P)┐(┐P) Q Q┐P→Q┐P→Q小结小结:本节主要介绍了四种新的联结词本节主要介绍了四种新的联结词 及最及最小联结词组小联结词组. 作业作业: 1. P29 (1), (2), (4) 832. 预习预习§1.7思考题思考题: 1. 何谓命题公式的何谓命题公式的(主主)析析(合合)取范式取范式? 2.命题公式的命题公式的(主主)析析(合合)取范式唯一吗取范式唯一吗? 3.为为何何要要将将命命题题公公式式化化为为与与之之等等价价的的主主析析(合合)取取范范式式? 4. 如何将命题公式化为与之等价的主析如何将命题公式化为与之等价的主析(合合)取范式取范式? 5.两个等价的命题公式其两个等价的命题公式其(主主)析析(合合)取范式有何关系取范式有何关系? 84第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.7对偶对偶与范式与范式(Dual & Normal Form)(Dual & Normal Form)1.7.1 对偶式与对偶原理对偶式与对偶原理(Dualistic Formula & Duality Principle)1.7.2命题公式的析命题公式的析(合合)取范式取范式(The Disjunctive & Conjunctive Normal Forms of a Propositional Formula) )1.7.3命题公式的主析命题公式的主析(合合)取范式取范式(The Principal Disjunctive & Conjunctive Normal Form of a Propositional Formula) ) 85 1.7.1 对偶式与对偶原理对偶式与对偶原理(Dualistic Formula & Duality Principle)在第四节在第四节(1.4)中我们给出了命题定律中我们给出了命题定律(P15 表表1-4.8), 其中其中多数等价公式都是成对出现的多数等价公式都是成对出现的, 每一对公式的不同之处每一对公式的不同之处是是将将 与与 互换互换, ,我们把这样的公式称为是我们把这样的公式称为是对偶对偶的的. . 定定义义1.7.1:设设命命题题公公式式A A仅仅含含有有联联结结词词┐┐, , , , , ,在在A A中中将将 , , ，，F F，，T T分别换以分别换以 ，， ，，T T，，F F得出公式得出公式A A* *，则，则A A* *称为称为A A的对偶的对偶公式。
公式说明说明:(A:(A* *) )* *=A=A 86例1.(┐P(┐P (Q(Q R))R))* *=┐P=┐P (Q(Q R) R) ((((P Q)Q) 1)1)* *=((=((P Q)Q) 0)0) 由由 P↑Q ┐┐(P∧∧Q) 和和 P↓Q ┐┐(P∨∨Q) 可知可知 (P↑Q)*= P↓Q 87关于对偶式我们有如下两个定理关于对偶式我们有如下两个定理:定理定理1.7.1:设设A A，，A A* *是对偶式，是对偶式， P1 , P2 ,…,Pn是出现于是出现于A A和和A A* *中的所有原子变元中的所有原子变元, ,则则(1)(1) ┐A( ┐A(P1 , P2 ,…,Pn ) )A A* *（（┐┐P1 , ┐┐P2 ,…, ┐┐Pn））(2) (2) A(┐A(┐P1 , ┐┐P2 ,…, ┐┐Pn) )┐A┐A* *（（P1 , P2 ,…,Pn））证明证明:因为因为 ┐ ┐(P(P Q)Q)┐P┐P ┐Q┐Q ┐(P ┐(P Q)Q)┐P┐P ┐Q┐Q 所以所以┐┐A(A(P1 , P2 ,…,Pn ) )A A* *（（┐┐P1 , ┐┐P2 ,…, ┐┐Pn）） 同理同理 ┐ ┐A A* *( (P1 , P2 ,…,Pn ) )A A（（┐┐P1 , ┐┐P2 ,…, ┐┐Pn）） 88第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.7对偶对偶与范式与范式(Dual & Normal Form)(Dual & Normal Form)定定理理1.7.2(对对偶偶原原理理) ):设设A,B为为两两个个仅仅含含有有联联结结词词┐┐, , , , 的的命题公式命题公式, 若若A AB B，则，则A A* *B B* *.证：设证：设P1 , P2 ,…,Pn是出现于是出现于A A和和B B中的所有原子变元中的所有原子变元. . 因为因为 A(A(P1 , P2 ,…,Pn) )B(B(P1 , P2 ,…,Pn) ) 则则 A(A(P1 , P2 ,…,Pn) )B(B(P1 , P2 ,…,Pn) )永真永真. . 故故 A(┐A(┐P1 , ┐┐P2 ,…, ┐┐Pn) )B(┐B(┐P1 , ┐┐P2 ,…, ┐┐Pn) ) 永真永真. . 由定理由定理1.7.1得得 ┐ ┐A A* *( (P1 , P2 ,…,Pn) )┐B┐B* *( (P1 , P2 ,…,Pn ) ) 因此因此 A A* *B B* * . 89例例1 1：因为：：因为： P P (P(P Q)Q)P P 由对偶原理由对偶原理: : P P (P(P Q) Q) P P例例2: 2: 若若A A1 1 则则 A A* *(1)(1)* * 即即 A A* *0.0.例例3: 3: 设设A A为为 (P(P Q)Q) ( (┐┐P P ( (┐P┐P Q)),BQ)),B为为┐┐P P Q Q, , 且且A AB,B,则则 A A* *B B* *┐┐P P Q.Q. 90定理定理1.7.3:设设A,B为两个为两个仅含有联结词仅含有联结词┐┐, , , , 的的命题命题 公式公式, 若若A AB B，则，则B B* *A A* *。
证：设证：设P1 , P2 ,…,Pn是出现于是出现于A A和和B B中的所有原子变元中的所有原子变元. . 因为因为 A(A(P1 , P2 ,…,Pn) )B(B(P1 , P2 ,…,Pn) ) 则则 A(A(P1 , P2 ,…,Pn)→B()→B(P1 , P2 ,…,Pn) )永真永真. . 故故 ┐ ┐B(B(P1 , P2 ,…,Pn)→┐A()→┐A(P1 , P2 ,…,Pn) )永真永真. . 即即 B B* *(┐(┐P1 , ┐┐P2 ,…, ┐┐Pn)→A)→A* *(┐(┐P1 , ┐┐P2 ,…, ┐┐Pn) ) 永真永真. 以以 P Pi i代代┐┐P Pi i，， i=1i=1，，2 2………n n 得得 B B* *( (P1 , P2 ,…, Pn)→A)→A* *( (P1 , P2 ,…, Pn) )永真永真. 所以所以 B B* * A A* * . . 911.7.2命题公式的析命题公式的析(合合)取范式取范式(The Disjunctive & Conjunctive Normal Forms of a Propositional Formula) )从前面的讨论可知从前面的讨论可知, ,存在大量互不相同的命题公式，存在大量互不相同的命题公式，实际上互为等价实际上互为等价, ,因此因此, ,有必要引入命题公式的有必要引入命题公式的标准形式标准形式, ,使得相互等价的命题公式具有相同的使得相互等价的命题公式具有相同的标准形式。
这无疑对判别两个命题公式是否等标准形式这无疑对判别两个命题公式是否等价以及判定命题公式的类型是一种好方法价以及判定命题公式的类型是一种好方法, ,同时同时对命题公式的简化和推证也是十分有益的对命题公式的简化和推证也是十分有益的. . 92定义定义1.7.2: (1)文字文字：命题变元及其否定统称为文字：命题变元及其否定统称为文字(如如P , ┐┐P). (2)简单析取式简单析取式：仅有有限个文字组成的析取式仅有有限个文字组成的析取式 如如:P P，，┐┐P P Q,PQ,P ┐P┐P，，Q Q P P ┐P┐P , P P ┐Q┐Q R R ┐S.┐S.(3)简单合取式简单合取式：仅有有限个文字组成的合取式仅有有限个文字组成的合取式 如如:P, ┐Q┐Q , Q Q ┐P┐P，，P P ┐P┐P，，Q Q P P ┐P┐P, p∧┐Q∧∧┐Q∧R.从定义不难看出:（（1））一一个个简简单单析析取取式式是是重重言言式式当当且且仅仅当当它它同同时时含含有有某个命题变元及其否定式某个命题变元及其否定式2））一一个个简简单单合合取取式式是是矛矛盾盾式式当当且且仅仅当当它它同同时时含含有有某个命题变元及其否定式某个命题变元及其否定式。
93定义定义1.7.3: (1)析取范式析取范式：一个命题公式称为：一个命题公式称为析取范式析取范式,当且仅当当且仅当它具有形式它具有形式: : A1∨∨A2∨∨……∨∨An (n大于等于1)其中其中Ai(i=1,2,3,…n)为为简单合取式简单合取式.如：如：P∨┐∨┐Q ，，(P ∧∧ Q) ∨∨(P ∧┐∧┐Q∧∧R), Q∧┐P.∧┐P. (2)合取范式合取范式：一个命题公式称为：一个命题公式称为合取范式合取范式,当且仅当当且仅当它具有形式它具有形式: : A1∧∧A2∧∧……∧∧An (n大于等于1)其中其中Ai(i=1,2,3,…n)为简单析取式为简单析取式.如：如：P ∧ ┐∧ ┐Q ，，(P ∨∨ Q) ∧∧(P ∨┐∨┐Q ∨∨R), Q∧┐P.Q∧┐P.(3)范式范式：析取范式与合取范式统称为：析取范式与合取范式统称为范式范式显然显然, 任何合任何合(析析)取范式的对偶式是析取范式的对偶式是析(合合)取范式取范式. 94析取范式与合取范式的性质析取范式与合取范式的性质:(1) 一一个个析析取取范范式式是是矛矛盾盾式式,当当且且仅仅当当它它的的每每一一个简单合取式都是矛盾式个简单合取式都是矛盾式;(2)一一个个合合取取范范式式是是重重言言式式,当当且且仅仅当当它它的的每每一一个简单析取式都是重言式个简单析取式都是重言式.定理定理1.7.4 (范式存在定理范式存在定理)任任一一个个命命题题公公式式都都存存在在着着与与之之等等价价的的析析取取范范式式与合取范式。
与合取范式 95求求命题公式的命题公式的范式的基本步骤范式的基本步骤：：（（1））将公式中的将公式中的联结词化归成联结词化归成┐┐, , 及及 . .（（2））将否定将否定联结词联结词消去或内移到各命题变元之前消去或内移到各命题变元之前 利用下列等价式：利用下列等价式： ┐┐┐┐A A ┐┐( A∨∨B) ┐┐A∧∧┐┐B ┐┐( A∧∧B) ┐┐A∨∨┐┐B（（3））利利用用分分配配律律、、结结合合律律将将公公式式转转化化为为合合取取范范式式或或析析取范式取范式. C ∧∧( A ∨∨ B) （（C∧∧ A））∨∨（（C ∧∧ B）） C ∨∨( A ∧∧ B) （（C ∨∨ A））∧∧（（C ∨∨ B）） 96例例1: 求求((P Q)R)P P 的析取范式与合取范式的析取范式与合取范式.例例2: 求求(P Q) R的析取范式与合取范式的析取范式与合取范式.例例3: 求求 ┐(P Q)(P Q)的析取范式与合取范式的析取范式与合取范式.注意注意：：（（1））单单个个命命题题变变元元既既是是简简单单合合取取式式，，又又是是简简单单析析取取式式；；公公式式P∧∧Q∧∧R既既可可以以看看成成是是合合取取范范式式，，也也可可以以看看成成是是析取范式。
析取范式2））一个命题公式的析一个命题公式的析(合合)取范式不是唯一的取范式不是唯一的 例例1：求：求((P Q)R)P P的析取范式与合取范式的析取范式与合取范式 解解: 原式原式┐┐( (┐┐( (P∨∨Q) )∨∨R) )∨∨P((((P∨∨Q ) )∧∧┐┐R) )∨∨P( (P∧∧┐┐R ) )∨(∨(Q∧∧┐┐R)∨)∨P (析取范式析取范式)P∨∨( (P∧∧┐┐R ) )∨(∨(Q∧∧┐┐R) )P∨(∨(Q∧∧┐┐R) ) (析取范式析取范式)( (P∨∨Q ∨∨P ) )∧(∧(┐┐R∨∨P ) ) (合取范式合取范式)( (P∨∨Q) )∧(∧(┐┐R∨∨P ) ) (合取范式合取范式) 例例2：求：求(P Q) R的析取范式与合取范式的析取范式与合取范式 解解: 原式原式((((PQ) R)∧∧(R( (PQ) )( (┐┐( (PQ)∨∨R)∧∧(┐┐R ∨∨( (PQ) )( (┐┐( (┐┐P∨∨Q)∨∨R)∧∧(┐┐R∨∨┐┐P∨∨Q )((P∧∧ ┐┐Q)∨∨R)∧∧(┐┐R∨∨┐┐P∨∨Q )((P∨∨R)∧∧(┐┐Q∨∨R)∧∧(┐┐R∨∨┐┐P∨∨Q ) (合取范式合取范式)((P∧∧┐┐Q)∧∧(┐┐R∨∨┐┐P∨∨Q ) )∨∨(R ∧∧(┐┐R∨∨┐┐P∨∨Q )(P∧∧┐┐Q∧∧┐┐R)∨∨(R∧∧┐┐P)∨∨(R∧∧Q) (析取范式析取范式) 例例3：求：求┐(P Q)(P Q)的析取范式与合取范式的析取范式与合取范式。
解解: ┐(P┐(P Q)Q)(P(P Q)Q) ( (┐(P┐(P Q)Q) ( (P P Q))Q)) ((((P P Q)Q) ┐(P┐(P Q))Q)) ((((P P Q)Q) ┐P┐P ┐Q))┐Q)) ((((P P Q)Q) ( (┐P┐P ┐Q))┐Q)) （（P P ┐Q┐Q）） （（Q Q ┐P┐P）） (析取范式析取范式) (P∨∨Q)∧∧(┐┐P∨∨┐┐Q) (合取范式合取范式) 1001.7.3命题公式的主析命题公式的主析(合合)取范式取范式(The Principal Disjunctive & Conjunctive Normal Form of a Propositional Formula) )由于一个命题公式的析由于一个命题公式的析(合合)取范式不是唯一取范式不是唯一, 因而它们不因而它们不能作为命题公式的规范形式能作为命题公式的规范形式(标准形式标准形式), 为了使任意命题为了使任意命题公式化为唯一的标准形式公式化为唯一的标准形式, 下面引入主范式的概念下面引入主范式的概念.1.命题公式的主析取范式命题公式的主析取范式定义定义1.7.4：：在含有在含有n个命题变元的个命题变元的简单合取式简单合取式中中,若每个若每个命题变元和它的否定不同时出现，而命题变元和它的否定不同时出现，而二者之一二者之一必必出现且出现且仅出现一次仅出现一次，称这样的，称这样的简单合取式简单合取式为为小项小项. 101例如例如, ,三个命题变元三个命题变元P,Q,R,P,Q,R,其小项共有其小项共有8 8个个: : 小项小项 编码编码 真值指派真值指派 小项的真值小项的真值 ┐┐P P ┐Q┐Q ┐R┐R m m000/000/m m0 0 000000 1 1 ┐P┐P ┐Q┐Q R mR m001/001/m m1 1 001 001 1 1 ┐P┐P Q Q ┐R┐Rm m010/010/m m2 2 010 010 1 1 ┐P┐P Q Q R R m m011/011/m m3 3 011 011 1 1 P P ┐Q┐Q ┐R m┐R m100/100/m m4 4 100 100 1 1 P P ┐Q┐Q R R m m101/101/m m5 5 101 101 1 1 P P Q Q ┐R┐R m m110/110/m m6 6 110 110 1 1 P P Q Q R R m m111/111/m m7 7 111 111 1 1 102考虑：考虑：n个命题变元可产生多少个小（个命题变元可产生多少个小（大大）项）项？？(2n) n n个变元的小项个变元的小项: : m m0 0 ┐P┐P1 1 ┐P┐P2 2 …………. . ┐┐PnPn m m1 1 ┐P┐P1 1 ┐P┐P2 2 …………. . PnPn ………………………………… m m2 2n n-1-1P P1 1 P P2 2 …………. . PnPn小项的真值表：小项的真值表：P33 表表1-7.1,表表1-7.2 103小项的性质小项的性质:(1)没有两个小项是等价的没有两个小项是等价的, 且每个小项有且仅有一个且每个小项有且仅有一个成真赋值，若成真赋值所对应的二进制数转化为十进成真赋值，若成真赋值所对应的二进制数转化为十进制数为制数为i，就将所对应的小项记作，就将所对应的小项记作mi。
2) 任意两个不同的小项的合取为矛盾式任意两个不同的小项的合取为矛盾式.(3) 全体小项的析取为永真式全体小项的析取为永真式.定义定义1.7.5：：设命题公式设命题公式A中含有中含有n个命题变元个命题变元, 如果如果A的的析析取范式中，所有的取范式中，所有的简单合取式简单合取式都是都是小项小项，则称该，则称该析析取取范式范式为为A的主析取的主析取范式范式定理定理1.7.5:任何命题公式都存在着与之等价的主析取范任何命题公式都存在着与之等价的主析取范式，并且是唯一的式，并且是唯一的 104•主析取范式的求法主析取范式的求法定理定理1.7.6:在命题公式在命题公式A的真值表中的真值表中,真值为真值为1的指派对应的指派对应的小项的析取的小项的析取, 即为即为A的主析取范式的主析取范式例例1: P34 例题例题6例例2: P35 例题例题7一个命题公式一个命题公式A的主析取范式的主析取范式, 还可以通过等值演算的还可以通过等值演算的方法求出方法求出, 其推演步骤其推演步骤:(1) 将将A化为析取范式化为析取范式 ;(2) 除去除去 中所有永假的析取项中所有永假的析取项; 105(3) 将将 中重复出现的简单合取式和相同变元都消去中重复出现的简单合取式和相同变元都消去;(4)若若 中某简单合取式中某简单合取式B中不含命题变元中不含命题变元P Pi i, 添加添加( (P Pi i ┐P┐Pi i), 然后应用分配律展开然后应用分配律展开. 即即 B B B 1 1B B (P(Pi i ┐P┐Pi i) ( (B B P Pi i) ) ( (B B ┐P┐Pi i).).例例1：求：求((P Q)R)P P的主析取范式的主析取范式。
例例2: 求求(P Q) R的主析取范式的主析取范式.例例3: 求求 ┐(P Q)(P Q)的主析取范式的主析取范式. 106第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.7对偶对偶与范式与范式(Dual & Normal Form)(Dual & Normal Form)例例1：求：求((P Q)R)P P的主析取范式的主析取范式 解解: 原式原式┐┐( (┐┐( (P∨∨Q) )∨∨R) )∨∨PP∨(∨(Q∧∧┐┐R) ) (析取范式析取范式)( (P∧∧( (Q∨∨┐┐Q) )∧∧( (R∨∨┐┐R) )) )∨(∨(( (P∨∨┐┐P) )∧ (∧ (Q∧∧┐┐R) )) )( (P∧∧Q∧∧R) )∨∨( (P∧∧Q∧∧┐┐R) )∨(∨(P∧∧┐┐Q∧∧R) )∨∨ ( (P∧∧┐┐Q∧∧┐┐R) )∨∨( (P∧∧Q∧∧┐┐R) )∨(∨(┐┐P∧∧Q∧∧┐┐R) )( (P∧∧Q∧∧R) )∨∨( (P∧∧Q∧∧┐┐R) )∨(∨(P∧∧┐┐Q∧∧R) )∨∨ ( (P∧∧┐┐Q∧∧┐┐R) )∨(∨(┐┐P∧∧Q∧∧┐┐R) ) ( (主析取范式主析取范式) )m m7 7∨∨m m6 6∨∨m m5 5∨∨m m4 4∨∨m m2 2m m2 2∨∨m m4 4∨∨m m5 5∨∨m m6 6∨∨m m7 7 107第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.7对偶对偶与范式与范式(Dual & Normal Form)(Dual & Normal Form)例例2：求：求(P Q) R的主析取范式的主析取范式。
解解:原式原式(P∧∧┐┐Q∧∧┐┐R)∨∨(R∧∧┐┐P)∨∨(R∧∧Q) (析取范式析取范式)(P∧∧┐┐Q∧∧┐┐R)∨∨((R ∧∧┐┐P)∧∧(Q∨∨┐┐Q))∨∨ ((P∨∨┐P┐P) ∧∧(R∧∧Q )) (P∧∧┐┐Q∧∧┐┐R)∨∨(┐┐P∧∧Q∧∧R)∨∨(┐┐P∧∧┐┐Q∧∧R)∨∨ (P ∧∧Q∧∧R)∨(∨(┐P┐P∧∧Q∧∧R ) (P∧∧┐┐Q∧∧┐┐R)∨∨(┐┐P∧∧Q∧∧R)∨∨ (┐┐P∧∧┐┐Q∧∧R) ∨∨(P ∧∧Q∧∧R) (主析取范式主析取范式) m m1 1∨∨m m3 3∨∨m m4 4∨∨m m7 7 108例例3：求：求┐(P Q)(P Q)的主析取范式的主析取范式 解解: ┐(P┐(P Q)Q)(P(P Q)Q) （（P P ┐Q┐Q）） （（Q Q ┐P┐P）） (主析取范式主析取范式)m m1 1∨∨m m2 2 1092.命题公式的主合取范式命题公式的主合取范式定义定义1.7.6：：在含有在含有n个命题变元的个命题变元的简单析取简单析取式式中中,若每个命题变元和它的否定不同时出现，若每个命题变元和它的否定不同时出现，而二者之一必出现且仅出现一次，称这样的而二者之一必出现且仅出现一次，称这样的简单析取简单析取式为式为大项大项. 110例如例如, ,三个命题变元三个命题变元P,Q,R,P,Q,R,其大项共有其大项共有8 8个个: : 大项大项 编码编码 真值指派真值指派 大项的真值大项的真值 P P Q Q R MR M000/000/M M0 0 000000 0 0 P P Q Q ┐R M┐R M001/001/M M1 1 001 001 0 0 P P ┐Q┐Q R MR M010/010/M M2 2 010 010 0 0 P P ┐Q┐Q ┐R M┐R M011/011/M M3 3 011 011 0 0 ┐P ┐P Q Q R MR M100/100/M M4 4 100 100 0 0 ┐P ┐P Q Q ┐R ┐R M M101/101/M M5 5 101 101 0 0 ┐P ┐P ┐Q┐Q R R M M110/110/M M6 6 110 110 0 0 ┐P ┐P ┐Q┐Q ┐R┐R M M111/111/M M7 7 111 0 111 0 111n n个变元的大项个变元的大项: : M M0 0 P P1 1 P P2 2 ………… PnPn M M1 1 P P1 1 P P2 2 ………… ┐┐PnPn ………………………………… M M2 2n n-1-1 ┐P┐P1 1 ┐P┐P2 2 ………… ┐┐PnPn 112大项的性质大项的性质:(1)没有两个大项是等价的没有两个大项是等价的, 且每个大项有且仅有一个且每个大项有且仅有一个成假赋值，若成假赋值所对应的二进制数转化为十进成假赋值，若成假赋值所对应的二进制数转化为十进制数为制数为i，就将所对应的大项记作，就将所对应的大项记作Mi。
2) 任意两个不同的大项的析取为永真式任意两个不同的大项的析取为永真式.(3) 全体大项的合取为矛盾式全体大项的合取为矛盾式.定义定义1.7.7：：设命题公式设命题公式A中含有中含有n个命题变元个命题变元, 如果如果A的的合取范式合取范式中，所有的中，所有的简单析取简单析取式都是式都是大项大项，则称该，则称该合合取取范式范式为为A的主合取范式的主合取范式定理定理1.7.6:任何命题公式都存在着与之等价的主合取范任何命题公式都存在着与之等价的主合取范式，并且是唯一的式，并且是唯一的 113•主合取范式的求法主合取范式的求法定理定理1.7.7:在命题公式在命题公式A的真值表中的真值表中,真值为真值为0的指派对应的指派对应的大项的合取的大项的合取, 即为即为A的主合取范式的主合取范式例例1: P34 例题例题6例例2: P35 例题例题7一个命题公式一个命题公式A的主合取范式的主合取范式, 还可以通过等值演算的还可以通过等值演算的方法求出方法求出, 其推演步骤其推演步骤:(1) 将将A化为合取范式化为合取范式 ;(2) 除去除去 中所有永真的合取项中所有永真的合取项; 114(3) 将将 中重复出现的简单析取式和相同变元都消去中重复出现的简单析取式和相同变元都消去;(4)若若 中某简单析取式中某简单析取式B中不含命题变元中不含命题变元P Pi i, 添加添加( (P Pi i ┐P┐Pi i), 然后应用分配律展开然后应用分配律展开. 即即 B B B 0 0B B (P(Pi i ┐P┐Pi i) ( (B B P Pi i) ) ( (B B ┐P┐Pi i).).例例1：求：求((P Q)R)P P的主合取范式的主合取范式。
例例2: 求求(P Q) R的主合取范式的主合取范式.例例3: 求求 ┐(P Q)(P Q)的主合取范式的主合取范式.注：注：1.1.命题公式的主析命题公式的主析( (合合) )取范式唯一取范式唯一 2.2.两命题公式若有相同的主析两命题公式若有相同的主析( (合合) )取范式，则二取范式，则二命题公式等价命题公式等价. . 115例例1：求：求((P Q)R)P P的主合取范式的主合取范式 解解: 原式原式┐┐( (┐┐( (P∨∨Q) )∨∨R) )∨∨P ( (P∨∨Q) )∧(∧(┐┐R∨∨P ) ) (合取范式合取范式)( (( (P∨∨Q) )∨∨( (R ∧∧┐┐R ) )) )∧((∧((┐┐R∨∨P ) )∨∨( (Q∧∧┐┐Q) )) )( (P∨∨Q∨∨R) )∧∧( (P∨∨Q∨∨┐┐R) )∧(∧(P∨∨Q∨∨┐┐R) )∧∧ ( (P∨∨┐┐Q∨∨┐┐R) ) ( (P∨∨Q∨∨R) )∧∧( (P∨∨Q∨∨┐┐R) )∧∧( (P∨∨┐┐Q∨∨┐┐R) ) ( (主合取范式主合取范式) )M M0 0∧∧M M1 1∧∧M M3 3 116 例例2：求：求(P Q) R的析取范式与合取范式的析取范式与合取范式。
解解: 原式原式((P∨∨R)∧∧(┐┐Q∨∨R)∧∧(┐┐R∨∨┐┐P∨∨Q ) (合取范式合取范式)((P∨∨R)∨∨(Q∧∧┐┐Q)) ∧∧((P∧∧┐P)┐P) ∨∨(┐┐Q∨∨R)) ∧∧(┐┐P∨∨Q∨∨┐┐R ) (P∨∨Q∨∨R)∧∧(P∨∨┐┐Q∨∨R)∧∧(P∨∨┐┐Q∨∨R)∧∧ (┐P┐P∨∨┐┐Q∨∨R)∧∧(┐┐P∨∨Q∨∨┐┐R ) (P∨∨Q∨∨R)∧∧(P∨∨┐┐Q∨∨R)∧∧ (┐P┐P∨∨┐┐Q∨∨R)∧∧(┐┐P∨∨Q∨∨┐┐R ) ( (主合取范式主合取范式) )M M0 0∧∧M M2 2∧∧M M5 5 ∧∧M M6 6 117例例3：求：求┐(P Q)(P Q)的主合取范式的主合取范式 解解: ┐(P┐(P Q)Q)(P(P Q)Q)(P∨∨Q)∧∧(┐┐P∨∨┐┐Q) (主合取范式主合取范式)M M0 0∧∧M M3 3 1183.3.主析取范式和主合取范式关系主析取范式和主合取范式关系设设Z Z为命题公式为命题公式A A的主析取范式中所有小项的足标集合，的主析取范式中所有小项的足标集合，R R为命题公式为命题公式A A的主合取范式中所有大项的足标集合的主合取范式中所有大项的足标集合, ,则则R={0,1R={0,1，，2 2…….2.2n n-1}-Z -1}-Z 或或 Z={0,1Z={0,1，，2 2…….2.2n n-1}-R-1}-R。
故已知命题公式故已知命题公式A A的主析取范式，可求得其主合取范式；的主析取范式，可求得其主合取范式；反之亦然反之亦然注意到小项与大项之间具有关系：注意到小项与大项之间具有关系：┐┐m mi iM Mi i，，┐┐M Mi im mi i（例：（例：m m5 5：：P P ┐Q┐Q R MR M5 5：：┐┐P P Q Q ┐R┐R））设命题公式设命题公式A A中含中含n n个命题变元，且设个命题变元，且设A A的主析取范式中含的主析取范式中含k k个小项个小项m mj1j1，，m mj2j2，，… ，，m mikik ，则，则┐┐A A的主析取范式中必含的主析取范式中必含2 2n n-k-k个小项个小项m mi1i1,m,mi2i2, ,… ,m ,mi2i2n n-k -k , ,且且{0,1{0,1，，2 2…….2.2n n-1}--1}-{j1{j1，，j2j2，，… ，，jkjk}={i1,i2,}={i1,i2,…,i2,i2n n-k}.-k}.所以所以 119┐A┐Am mi1i1 m mi2i2 … m mi2i2n n-k -k A A┐(m┐(mi1i1 m mi2i2 … m mi2i2n n-k-k）） ┐┐m mi1i1 ┐m┐mi2i2 … ┐m┐mi2i2n n-k-k M Mi1i1 M Mi2i2 … M Mi i2 2n n-k-k例如例如, ,设命题公式设命题公式A Am m0 0 m m1 1 m m5 5 m m7 7 ，则，则 A AM M2 2 M M3 3 M M4 4 M M6 6 120第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.7对偶对偶与范式与范式(Dual & Normal Form)(Dual & Normal Form)4.主析主析(合合)取范式的应用取范式的应用(1)求公式的成真求公式的成真/成假赋值：成假赋值： 若若公公式式A中中含含有有n个个命命题题变变元元，，且且A的的主主析析取取范范式式含含s 个个小小项项，，则则A有有s个个成成真真赋赋值值，，有有2n-s个个成成假假赋赋值值。
即即主主析析取取范范式式中中的的小小项项对对应应的的编编码码是是公公式式A的的成成真真赋赋值值；；反反之之主主合合取取范范式式中中的的大大项项对对应应的的编编码码是是公公式式A的的成成假假赋值）赋值） 121(2)判断公式的类型判断公式的类型：： 设公式设公式A中含有中含有n个命题变元，则：个命题变元，则：（（1））A为重言式为重言式 A的的主析取范式主析取范式含全部含全部2n个个小小项2））A为为矛矛盾盾式式A的的主主析析取取范范式式不不含含任任何何小小项项，，记记A的的主析取范式为主析取范式为03））A为可满足式为可满足式A的的主析取范式主析取范式至少含一个至少含一个小项4））A为矛盾式为矛盾式A的的主合取范式主合取范式含全部含全部2n个大项5））A为为重重言言式式A的的主主合合取取范范式式不不含含任任何何大大项项，，记记A的的主合取范式为主合取范式为1 6））A为为可可满满足足式式A的的主主合合取取范范式式中中大大项项的的个个数数一一定定小于小于2n 122例例:判断下列命题公式的类型判断下列命题公式的类型. (1) (PQ)R (2) ┐┐(PQ) Q Q (3) (PQ) Q QQ Q 解解:(1) (PQ)R m m1 1∨∨m m3 3∨∨m m4 4∨∨m m7 7为可满足式为可满足式. 123(3)判断两个命题是否等价：判断两个命题是否等价： 设设公公式式A、、B中中共共含含有有n个个命命题题变变元元，，按按n个个命命题题变变元元求求出出A、、B的的主主析析(合合)取取范范式式 、、 。
若若 = ，则，则A B，否则，否则A、、B不等价不等价.例例:试判断下列各组命题是否等价试判断下列各组命题是否等价. (1) ( (PQ)∧∧(PR) 与与 P( (Q∧∧R) (2) P( (Q∧∧R) 与与 P∨(∨(QR) 124解解:(1) ( (PQ Q)∧∧(PR) ( (┐P┐P∨∨Q)∧∧(┐┐P∨∨R) (┐┐P∨∨Q∨(∨(R∧∧┐┐R)∧∧(┐┐P∨∨R∨(∨(Q∧∧┐┐Q) (┐┐P∨∨Q∨∨R)∧∧(┐┐P∨∨Q∨∨┐┐R)∧∧ (┐┐P∨∨R∨∨Q)∧∧ ( (┐┐P∨∨R∨∨┐┐Q) M M4 4∧∧M M5 5∧∧M M6 6 P( (Q∧∧R)┐P┐P∨∨(Q∧∧R) ( (┐P┐P∨∨Q)∧∧(┐┐P∨∨R) M M4 4∧∧M M5 5∧∧M M6 6 所以所以 ( (PQ Q)∧∧(PR) P( (Q∧∧R) 125解解(2) P( (Q∧∧R)┐P┐P∨∨(Q∧∧R) ( (┐P┐P∨∨Q)∧∧(┐┐P∨∨R) M M4 4∧∧M M5 5∧∧M M6 6 m0 ∨∨ m1 ∨∨ m2 ∨∨ m3∨∨m7 P∨(∨(QR) P∨∨┐┐Q∨∨R M M2 2 m0∨∨m1∨∨m3∨∨m4∨∨m5∨∨m6∨∨m7 所以所以 P( (Q∧∧R)与与P∨(∨(QR) 不等价不等价. 1265.解决实际问题：解决实际问题：某科研所有三名青年高级工程师某科研所有三名青年高级工程师A，，B，，C。
所里要选派所里要选派他们中的他们中的1到到2人出国进修，由于所里工作的需要，选派人出国进修，由于所里工作的需要，选派时必须满足以下条件：时必须满足以下条件：①①若若A去，则去，则C也可以去也可以去②②若若B去，则去，则C不能去不能去③③若若C不去，则不去，则A或或B可以去可以去问所里应如何选派他们？问所里应如何选派他们？ 127解解: 设设 P:派派A去Q :派派B去R :派派C去根据所要满足的条件，得命题公式为：根据所要满足的条件，得命题公式为：( (PR)∧∧(Q ┐┐R)∧∧(┐┐R( P∨∨Q) )求此公式的主析取范式求此公式的主析取范式:原式原式(┐┐P∧∧┐┐Q Q∧∧R)∨∨(┐┐P∧∧Q Q∧∧┐┐R)∨∨(P∧∧┐┐Q Q∧∧R) 因此有三种选派方案：Ｃ去，而Ａ、Ｂ都不去；Ｂ去，因此有三种选派方案：Ｃ去，而Ａ、Ｂ都不去；Ｂ去，而Ａ、Ｃ都不去；Ａ、Ｃ都去，而Ｂ不去而Ａ、Ｃ都不去；Ａ、Ｃ都去，而Ｂ不去. 1281.8.1常用的证明方法常用的证明方法1.8.2真值表法真值表法 (Truth Table)1.8.3直接证法直接证法 (Direct Proof)1.8.4 间接证法间接证法 (Indirect Proof)第一章第一章 命题逻辑命题逻辑（（（（Propositional LogicPropositional Logic）））） 1.8推理推理理论理论(Inference Theory)(Inference Theory) 129 1.8.1常用的证明方法常用的证明方法•定义定义1.8.1 ：设Ａ和Ｃ是两个命题公式：设Ａ和Ｃ是两个命题公式,当且仅当Ａ当且仅当ＡＣＣ为一重言式，即Ａ为一重言式，即ＡＣＣ,称Ｃ是Ａ的有效结论称Ｃ是Ａ的有效结论;或称Ｃ可或称Ｃ可由Ａ逻辑推出由Ａ逻辑推出.一般地一般地,如果有如果有n个前提个前提H1,H2,H3,.…,Hn , 若H1H2H3....HnC,则称C是一组前提H1,H2,…,Hn的有效结论。
•注意注意:在形式逻辑中在形式逻辑中,我们并不关心结论是否真实我们并不关心结论是否真实,而主要而主要关心结论是否可以由给定的前提推出来关心结论是否可以由给定的前提推出来,我们只注意推我们只注意推理的形式是否正确理的形式是否正确.因此因此,有效结论并不一定是正确的有效结论并不一定是正确的,只只有正确的前提经过正确的推理得到的逻辑结论才是正确有正确的前提经过正确的推理得到的逻辑结论才是正确的的. 130•证明证明C是是A的有效结论的方法就是判别重言蕴含的方的有效结论的方法就是判别重言蕴含的方法法.前面我们介绍的论证方法有真值表法、等值演算前面我们介绍的论证方法有真值表法、等值演算法、主析（合）取范式法论证方法千变万化，但法、主析（合）取范式法论证方法千变万化，但最基本、最常用的方法有三最基本、最常用的方法有三种：种： 推理证明的方法推理证明的方法 1311.8.2真值表法真值表法 (Truth Table)构造命题公式构造命题公式H1 ∧∧ H2 ∧∧ …… ∧∧ Hn →→ C的真值表，若为永的真值表，若为永真，真，H1 ∧∧ H2 ∧∧ …… ∧∧ Hn C 推理正确推理正确例：例：证明证明(( (P∨∨Q)∧)∧┐┐Q) PPQP∨Q┐┐Q( (P∨∨Q)∧)∧┐┐Q (( (P∨∨Q)∧)∧┐┐Q)P000101011001101111111001 132由上面真值表可知由上面真值表可知(( (P∨∨Q)∧)∧┐┐Q) P。
•1.8.3直接证法直接证法 (Direct Proof) )•直接证法：直接证法：由一组前提，利用一些公认的由一组前提，利用一些公认的推理规则推理规则，，根据已知的等价或蕴含公式推演得到有效结论根据已知的等价或蕴含公式推演得到有效结论•常用的推理规则常用的推理规则P规则规则:（也称前提引入规则）前提在推导过程中的任何（也称前提引入规则）前提在推导过程中的任何 时候都可以引用时候都可以引用T规则规则:在推导过程中，所证明的结论、已知的等价或蕴在推导过程中，所证明的结论、已知的等价或蕴 含公式都可以作为后续证明的前提，命题公式中含公式都可以作为后续证明的前提，命题公式中 的任何子公式都可以用与之等价的命题公式置换的任何子公式都可以用与之等价的命题公式置换 133常用的蕴含式和等价式见课本常用的蕴含式和等价式见课本P43 表表1-8.3、、1-8.4例例1.1.如果考试及格，那我高兴若我高兴，那么我如果考试及格，那我高兴若我高兴，那么我饭饭量增加我的饭量没增加，所以我考试没有及格我的饭量没增加，所以我考试没有及格试对上述论证构造证明。
试对上述论证构造证明解：设解：设P P：我考试及格：我考试及格. Q. Q：我高兴R R：我饭量增加我饭量增加则此论证可表为则此论证可表为 (P→Q)(P→Q) (Q→R)(Q→R) ┐R┐R┐P┐P 证证: : 134常用的蕴含式和等价式见课本常用的蕴含式和等价式见课本P43 表表1-8.3、、1-8.4例例1.1.如果考试及格，那我高兴若我高兴，那么我如果考试及格，那我高兴若我高兴，那么我饭量增加我的饭量没增加，所以我考试没有及饭量增加我的饭量没增加，所以我考试没有及格试对上述论证构造证明试对上述论证构造证明解：设解：设P P：我考试及格：我考试及格. Q. Q：我高兴R R：我饭量增加我饭量增加则此论证可表为则此论证可表为 (P→Q)(P→Q) (Q→R)(Q→R) ┐R┐R┐P┐P 证证: 1: 1 P→Q P→Q P P 2 2 Q→RQ→RP P 3 3 ┐ ┐R RP P 4 4 ┐ ┐Q QT T，，2 2，，3 I3 I1212 5 5 ┐ ┐P PT T，，1 1，，4 I4 I1212 135例例2.2.证明证明 R R S S是是前提前提C C D D，，C→R,D→SC→R,D→S的的有效结论有效结论。
证：证：1.C1.C D PD P 2.C→R P 2.C→R P 3.D→S P 3.D→S P 4.┐C→D T 4.┐C→D T，，1 E1 E 5.┐R→┐C T 5.┐R→┐C T，，2 E2 E 6.┐R→S T 6.┐R→S T，，5 5，，4 4，，3 3 I I1313 7.R 7.R S TS T，，6 E6 E 136例例3：：P∨∨Q , QR, PS , ┐┐S R∧∧(Q∨∨P) 证明：证明： 1. P S P (前提引入前提引入) 2. ┐┐S P (前提引入前提引入) 3. ┐┐P T1, 2 I I1111 4. P∨∨Q P (前提引入前提引入) 5. Q T3,4 I I1111 6. QR P (前提引入前提引入) 7. R T5,6 I I1111 8. R∧∧(Q∨∨P) T4,7 I I9 9 137例例4：证明：证明 (P（（Q∨∨R))∧∧(┐┐S ┐┐Q)∧∧(P∧∧┐┐S)R.证证：（：（1）） P∧∧┐┐S P （（2）） P T（（1）） I I1 1 （（3）） ┐┐S T（（1）） I I1 1 （（4）） P（（Q∨∨R) P （（5）） Q∨∨R T (2)，，(4) I I1111 （（6）） ┐┐S ┐┐Q P （（7）） ┐┐Q T(3)，，(6) I I1111 （（8）） R T(5)，，(7) I I1111 1381.8.4 间接证法间接证法 (Indirect Proof)1.附加前提证明法附加前提证明法 适用于如下类型蕴含式的证明适用于如下类型蕴含式的证明: (A1∧∧A2∧∧…∧∧Ak) (AB) (*) 欲证明欲证明(*)式，只需证明式，只需证明 (A1∧∧A2∧∧…∧∧Ak∧∧A) B 即可，因为即可，因为 139 (A1∧∧A2∧∧…∧∧Ak)(AB)┐┐(A1∧∧A2∧∧…∧∧Ak) ∨∨ (A B ) ┐┐(A1∧∧A2∧∧… Ak) ∨∨ (┐┐ A ∨∨ B ) (┐┐A1∨∨┐┐A2∨∨…∨∨ ┐┐Ak) ∨∨ (┐┐A∨∨B) ┐┐A1∨∨┐┐A2∨∨…∨∨┐┐Ak∨∨┐┐A∨∨B (┐┐A1∨∨┐┐A2∨∨…∨∨┐┐Ak∨∨┐┐A)∨∨B ┐┐(A1∧∧A2∧∧…∧∧Ak∧∧A)∨∨B (A1∧∧A2∧∧…∧∧Ak∧∧A) B这样一来这样一来,原来结论中的前件原来结论中的前件A就变成了前提就变成了前提,称称A为为附加附加前提前提. 140由证由证(A1∧∧A2∧∧…∧∧Ak∧∧A)B永真而证得永真而证得(A1∧∧A2∧∧…∧∧Ak)(AB)永永真真的的证证明明方方法法, 称为称为附加前提证明法或附加前提证明法或CP规则规则. 141例例1:证明证明:(A→B C) (B→┐A) (D→┐C) (A→┐D)证：证：1. A→B C P 2. B→┐A P 3. D→┐C P 4. A P(附加前提附加前提) 5. B C T1，，4 I I1111 6. A→┐B T2, E 7. C→┐D T3 ，，E 8. ┐B T4，，6 I I1111 9. C T5，，8 I I1111 10. ┐D T7，，9 I I1111 11. A→┐D Ｔ４，Ｔ４，10 CP 142 例例2：：前提：前提：P(QR) , SP , Q 结论：结论：SR.证明：证明： 1. SP P 2. S P（附加（附加前提引入）前提引入） 3. P T（（1, 2）） I I1111 4. P(QR) P 5. QR T（（3,4）） I I1111 6. Q P 7. R T（（5,6）） I I11 11 8. SR T（（2,7）） CPCP 1432. 归谬法归谬法定义定义1.8.21.8.2：设命题公式集合为设命题公式集合为{H{H1 1, ,H H2 2, ,H H3 3, ,. .…, ,H Hn n } }，若，若H H1 1 H H2 2 H H3 3 ........ H Hn n为永假式，则称为永假式，则称{H{H1 1, ,H H2 2, ,H H3 3, ,. .…, ,H Hn n } }是不是不相容的，否则称为相容的。
相容的，否则称为相容的由于由于 (A1∧∧A2∧∧…∧∧Ak)B ┐┐(A1∧∧A2∧∧…∧∧Ak)∨∨B ┐┐(A1∧∧A2∧∧… Ak∧∧┐┐B)故要证故要证(A1∧∧A2∧∧…∧∧Ak)B永真永真,只需证只需证A1∧∧A2∧∧… Ak∧∧┐┐B永假永假.这种将这种将┐┐B作为附加前提作为附加前提推出矛盾的证明方法称为推出矛盾的证明方法称为归谬法归谬法. 144•例例1:证明证明 (P┐Q)┐Q)∧∧(┐┐R∨∨Q)∧∧(R∧∧┐S)┐S) ┐P┐P证证：：1. P P(附加前提附加前提) 2. P┐Q┐Q P 3. ┐Q┐Q T(1, 2) I I1111 4. ┐┐R∨∨Q P 5. ┐┐R T(3,4) I I1111 6. R∧∧┐S┐S P 7. R T(6) I I1 1 8. R∧∧┐┐R(矛盾）矛盾）T(5,7) 由由8得出了矛盾得出了矛盾,根据归谬法说明原推理正确根据归谬法说明原推理正确. 145•例例2:从从P P Q→RQ→R S,(T→Q)S,(T→Q) (S→U),┐R,(W→P)(S→U),┐R,(W→P) (T→U) (T→U) 推出推出 W→┐TW→┐T证：证： 1. P1. P Q→RQ→R S P S P 2.(T→Q) 2.(T→Q) (S→U) P(S→U) P 3.(W→P) 3.(W→P) (T→U) P(T→U) P 4. ┐R P 4. ┐R P 5. W P( 5. W P(附加前提附加前提) ) 6. ┐R 6. ┐R∨∨┐S ┐S T 4 I T 4 I 7. ┐(R7. ┐(R S) T 6 ES) T 6 E 8. ┐(P 8. ┐(P Q) T 1Q) T 1，，7 I7 I1111 9 .(W→P) T3,I.(W→P) T3,I 10. P T510. P T5，，9 I9 I 11. ┐P┐P∨∨┐Q T8,E┐Q T8,E 12. ┐Q T 10 12. ┐Q T 10，，11 I11 I1111 13. T→Q T 2 IT→Q T 2 I1111 14. ┐T T 12 14. ┐T T 12，，13 I13 I1111 15. W→┐T 15. W→┐T Ｔ５Ｔ５,15 CP,15 CP 146小结小结:本节将推理证明命题公式序列化本节将推理证明命题公式序列化.主要介主要介绍了推理证明重言蕴含式的直接证法和间绍了推理证明重言蕴含式的直接证法和间接证法。
接证法 作业作业: 1. P46-47 (1)a, (2) e (3) a,b 2. 预习第二章预习第二章§2.1,§2.2 147补充补充:分分 情情 况况 证证 明明 欲证：欲证： (P(P1 1 P P2 2 ……… P Pn n) )Q Q只需证明只需证明 ｉｉ 1<=i<=n 1<=i<=n 有有 P Pi iQ Q 因为： 因为： (P(P1 1 P P2 2 ……… P Pn n)→Q)→Q ┐(P┐(P1 1 P P2 2 ……… P Pn n) ) Q Q （（┐┐P P1 1 ┐P┐P2 2 …… ┐┐P Pn n) ) Q Q (┐P(┐P1 1 Q)Q) (┐P(┐P2 2 Q)Q) ……… (┐(┐P Pn n Q Q) ) (P(P1 1→Q)→Q) (P(P2 2→Q)→Q) ……. . ( (P Pn n→Q→Q) ) 148例：证明（例：证明（((P→Q)((P→Q) P)P) (P(P Q)Q) ┐P┐P））→→Q) Q) 永真永真 证：情况证：情况1 1 1.P→Q P 1.P→Q P 2.P P 2.P P 3.Q T1 3.Q T1，，2 I2 I1111 情况情况2 2 1.P 1.P Q P Q P 2.┐P P 2.┐P P 3.Q T1 3.Q T1，，2 I2 I1111 。
