Web: http://staff.ustc.edu.cn/~xiaomj 离散数学 I 肖明军 Web: http://staff.ustc.edu.cn/~xiaomj Email: xiaomj@ustc.edu.cn

引言 课程简介 离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，它研究的对象是有限个或可数的离散量。充分描述了计算机科学离散性的特征。 离散数学是传统的逻辑学、集合论、数论基础、算法设计、组合分析、离散概率、关系理论、图论与树、抽象代数、布尔代数、计算模型等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。 离散数学是随着计算机科学的发展而逐步建立起来的一门新兴的工具性学科，形成于七十年代。

引言 课程意义 教学内容 数理逻辑、集合论、代数结构、图论 离散数学是计算机科学的数学基础，其基本概念、理论、方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法设计、人工智能、计算机网络等专业课程中，是这些课程的基础课程。 离散数学学习十分有益于概括抽象能力、逻辑思维能力、归纳构造能力的提高，能够培养提高学生的数学思维能力和对实际问题的求解能力。 教学内容 数理逻辑、集合论、代数结构、图论

引言 教学内容 第一部分 数理逻辑 第一章 命题逻辑 第二章 谓词逻辑 第二部分 集合论 第三章 集合代数 第四章 二元关系

引言 教学内容 第二部分 集合论 第五章 函数 第六章 集合的基数 第三部分 代数结构 第七章 代数系统 第八章 群论

引言 教学内容 第三部分 代数结构 第九章 环与域 第十章 格与布尔代数

第一部分 数理逻辑 逻辑学 是一门研究思维形式和规律的科学。分为辩证逻辑和形式逻辑两种。思维的形式结构包括了概念﹑判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答，就是判断。由一个或几个判断推出另一判断的思维形式就是推理。 数理逻辑 用数学方法研究推理的规律称为数理逻辑。所谓数学方法就是引用一套符号体系的方法，所以数理逻辑又称作符号逻辑。

第一部分 数理逻辑 现代数理逻辑 逻辑演算、逻辑演绎、模型论、证明论、递归函数论、公理化集合论等。 我们要介绍的是数理逻辑中最基本的内容：命题逻辑和谓词逻辑。即一般所谓的古典逻辑。 德国数学家莱布尼茨Leibniz（现代逻辑的首席创始人）；布尔Boole （奠基人，逻辑的数学分析）；弗雷格（数论的基础）

第一章 命题逻辑 命题逻辑也称命题演算或语句逻辑。它研究以“命题”为基本单位构成的前提和结论之间的可推导关系，研究什么是命题？如何表示命题？怎样由一组前提推导一些结论。 判断 概念 推理

1.1 命题与命题联结词 1.1.1命题 定义1.1：具有确切真值的陈述句(或断言)称为命题(Proposition)。 命题的取值称为真值。真值只有“真”和“假”两种，分别用“T”或“1”和“F”或“0”表示。 注意：命题的真值非真即假，只有两种取值，这样的系统为二值逻辑系统。

1.1 命题与命题联结词 例1-1：命题示例。 (a):今天下雪 (b):3+3=6 (c):2是偶数而3是奇数 (d):陈胜起义那天，杭州下雨 (e):较大的偶数都可表为两个质数之和 (f):x+y>4 (g):真好啊! (h):x=3 (i):你去哪里？ (j):我正在说谎。 注意：由定义知，一切没有判断内容的句子如命令，感叹句，疑问句，祈使句，二义性的陈述句等都不能作为命题。 a-e为命题，f-j非命题

1.1 命题与命题联结词 例1-2：下列句子哪些是命题，判断命题的真假。 (1):2是素数 (2):北京是中国的首都 (3):这个语句是假的 (1):2是素数 (2):北京是中国的首都 (3):这个语句是假的 (4):x+y>0 (5):我喜欢踢足球 (6):地球外的星球上也有人 (7):明年国庆节是晴天 (8):把门关上 (9):你要出去吗？ (10):今天天气真好啊！ 1: T; 2: T; 3 非命题; 4: 非命题; 5: 命题; 6: 命题; 7: 命题; 8-10: 非命题

1.1 命题与命题联结词 注意 命题一定是通过陈述句来表达；反之，并非一切的陈述句都一定是命题。 命题的真值有时可明确给出，有时还需要依靠环境条件，实际情况，时间才能确定其真值。但其真值一定是唯一确定的。

1.1 命题与命题联结词 命题可分为两种类型： 注意： 简单命题：若一个命题已不能分解成更简单的命题，则该命题叫原子命题或本原命题或简单命题（Simple Proposition） 复合命题（Compound Proposition）：可以分解为简单命题的命题，而且这些简单命题之间是通过关联词（如“或者”,“并且”,“不”，“如果… 则…”,“当且仅当”等）和标点符号复合而构成一个复合命题。 例，合肥是安徽的省会当且仅当鸟会飞。 注意： 命题通常用大写英文字母（可带下标）来表示。

1.1 命题与命题联结词 1.1.2 命题联结词 命题通常可以通过一些联结词复合而构成新的命题，这些联结词被称为逻辑联结词。用数学方法研究命题之间的逻辑关系时（也就是在命题演算中），这些联结词可以看作是运算符，因此也叫作逻辑运算符。 常用的联结词有以下5个： 定义1.2：设P是任一命题，复合命题“非P”（或“P的否定”）称为P的否定式（Negation），记作¬P，“¬”为否定联结词。 ¬P为真当且仅当P为假。 如：P：2是素数，则¬P：2不是素数。

1.1 命题与命题联结词 定义1.3：设P ﹑Q是任意两个命题，复合命题“P并且Q”（或“P和Q”）称为P与Q的合取式（Conjunction），记作P ∧ Q，“∧ ”为合取联结词。 P ∧ Q为真当且仅当P，Q同为真。 例，P：2是素数，Q：2是偶数。则P ∧ Q：2是素数并且是偶数。

1.1 命题与命题联结词 定义1.4：设P ﹑Q是任意两个命题，复合命题“P或Q” 称为P与Q的析取式（Disjunction），记作P ∨ Q，“∨ ”为析取联结词。 P ∨ Q为真当且仅当P，Q至少一个为真。 例，P：2是素数，Q：2是奇数。则P ∨ Q：2是素数或是奇数。

1.1 命题与命题联结词 定义1.5：设P ﹑Q是任意两个命题，复合命题“如果P则Q” 称为P与Q的蕴含式（Implication），记作P→Q，“→”为 蕴含联结词，P称为蕴含式的前提，假设或前件，而Q称为结论式后件。P→Q为假当且仅当P为真Q为假。 例，P：G是正方形，Q：G的四边相等，则P→Q：如果G是正方形，则G的四边相等。 蕴含式P→Q可以用多种方式陈述： “若P，则Q”; “P是Q的充分条件”; “Q是P的必要条件”; “Q每当P”; “P仅当Q”等。

1.1 命题与命题联结词 给定命题P→Q，我们把Q→P，﹁P→﹁Q， ﹁Q→﹁P分别叫作命题P→Q的逆命题，反命题和逆反命题。 定义1.6：设P，Q是任意两个命题，复合命题“P当且仅当Q”称为P与Q的等价式(Equivalence)，记作P↔Q，“↔”为等价联结词。 P↔Q为真当且仅当P，Q同为真假。 例如，P：合肥是安徽省会，Q：鸟会飞，则P↔Q：合肥是安徽省会当且仅当鸟会飞。 如果P↔Q是真，则P→Q和Q→P是真，反之亦然，因此P↔Q也读作“P是Q的充要条件”或“P当且仅当Q”。

1.1 命题与命题联结词 五个联结词的真值表 联结词 记号 表达式 读法 真值结果 否定 ¬ ¬P 非P ¬P为真当且仅当P为假 合取 ∧ P ∧ Q P且Q P ∧ Q为真当且仅当P，Q同为真 析取 ∨ P ∨ Q P或Q P ∨ Q为真当且仅当P，Q至少一个为真 蕴含 → P→Q 若P则Q P→Q为假当且仅当P为真Q为假 等价 ↔ P↔Q P当且仅当Q P↔Q为真当且仅当P，Q同为真假

1.1 命题与命题联结词 一般约定： a)：运算符(联结词)结合力强弱顺序为：¬， ∧，∨，→，↔；凡符合此顺序的，括号可省略。 b)：相同的运算符，从左到右次序计算时，括号可省去。 c)：最外层括号可省。 如，(¬((P ∧ ¬Q) ∨R) →((R ∨P)∨Q)) ¬(P ∧ ¬Q∨R) →R ∨P∨Q

1.1 命题与命题联结词 例1.3：符号化下列命题。 a)：他既有理论知识又有实践经验 b)：i. 如果明天不是雨夹雪则我去学校 ii. 如果明天不下雨并且不下雪，则我去学校 iii. 如果明天下雨或下雪则我不去学校 iv. 明天我将风雨无阻一定去学校 v. 当且仅当明天不下雪并且不下雨时我才去 学校 a)解：设P：他有理论知识；Q：他有实践经验。则命题转化为： P ∧ Q b)解：设P：明天下雨；Q：明天下雪；R：我去学校 则 i)： ¬(P∧Q) →R ii)： ¬P∧ ¬Q →R iii)：P ∨Q → ¬ R iv)： P∧Q∧R∨¬P∧Q∧R∨P∧¬Q∧R∨¬ P∧¬Q∧R v)： ¬ P∧¬Q ↔ R

1.1 命题与命题联结词 c)：说小学生编不了程序，或说小学生用不了个人计算机，那是不对的。 d)：若不是他生病了或出差了，我是不会同意他不参加学习的。 e)：如果我上街了，我就去书店看看，除非我很累。 c)：说小学生编不了程序，或说小学生用不了个人计算机，那是不对的。 解：设P：小学生会编程序；Q：小学生会用个人计算机； 则¬ (¬ P ∨ ¬ Q) d)：若不是他生病了或出差了，我是不会同意他不参加学习 解：设P：他生病了；Q：他出差了；R：我们同意他不参加学习； 则¬(P∨Q) ↔ ¬R或¬(P∨Q) ↔ ¬R e)：如果我上街了，我就去书店看看，除非我很累 解：设P：我上街；Q：我去书店看看；R：我很累； 则：P →(¬R →Q)或¬R →(P →Q)或(¬R ∧P) →Q

1.1 命题与命题联结词 注意： ¬是自然语言中的“非”﹑“不” 和“没有”等的逻辑抽象 ∧是自然语言中的“并且” ﹑“既… 又…” ﹑“且” ﹑“和”等的逻辑抽象 ∨是自然语言中的“或”和“或者”等的逻辑抽象；但“或”有“可兼或” ﹑“不可兼或” ﹑“近似或”三种 P→Q是自然语言中的“只要P，就Q” ﹑“因为P，所以Q” ﹑“P仅当Q”等的逻辑抽象

1.1 命题与命题联结词 (5) ↔是自然语言中的“充分必要条件”和“当且仅当”等的逻辑抽象 (6)联结词连接的是两个命题真值之间的联结，而不是命题内容之间的连接，因此复合命题 的真值只取决于构成他们的各原子命题的真 值 (7) ∧，∨，↔具有对称性，而¬，→没有 (8) ∧，∨， ¬与计算机中的与门，或门，非门电路是相对应的 看P6-7 例1.4-1.5，P9 例1.7

1.1 命题与命题联结词 符号化下列命题 a)：1. 张晓静爱唱歌或爱听音乐 2. 张晓静是江西人或安徽人 b)：a是给定的一个正整数， 1. 只要a能被4整除，则a一定能被2整除 2. a能被4整除，仅当a能被2整除 3. 除非a能被2整除，a才能被4整除 4. 除非a能被2整除，否则a不能被4整除 5. 只有a能被2整除，a才能被4整除

1.2 公式的解释与真值表 1.2.1：命题公式 就像在代数学里引入变量一样，为了更广泛的应用命题演算，在数理逻辑中也引入了命题变量。使得在研究时，只需考虑命题的真值，而不知晓命题的具体含义。 定义1.7：一个特定的命题是一个常值命题(Constant Proposition)，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元、命题变项)(Proposition Variable)。命题变量无具体的真值，它的值域是集合{T，F}(或{1，0})。

1.2 公式的解释与真值表 原子命题在不指派真值时称为命题变元，而复合命题由原子命题和联结词构成，可以看作是命题变元的函数，且该函数的值仍为“真”或“假”，可以称为真值函数（True Value Function）或命题公式。但不是说原子命题和联结词的一个随便的组合都可以为命题公式，我们用递归的方法来定义命题公式。

1.2 公式的解释与真值表 定义1.8：命题公式 (1).命题变元本身是一个公式； (2).如果P是公式，则¬P也是公式； (3).如果P，Q是公式，则P∧Q﹑ P∨Q﹑ P→Q﹑ P↔Q也是公式； (4).命题公式(Prepositional Formula)是仅由有限步使用规则(1)~(3)后产生的结果。公式常用符号G﹑H…等表示。 例，(¬ P∧Q)，(P→(¬P ∧Q)) ，(((P∧Q) ∧(R ∨Q)) ↔(P →R))是命题公式 (P →Q )∧¬ Q)， (P →Q， (¬ P∨Q ∨(R， P∨Q ∨不是命题公式

1.2 公式的解释与真值表 注意： 如果G是含有n个命题变元 P1, P2, …,Pn的公式，通常记为G（P1, …,Pn）或简记为G。 原子命题变元是最简单的（合式）公式，也叫原子（合式）公式。 合成公式没有真值，只有对其变元进行指派后才有真值。 合成公式无限多。

1.2 公式的解释与真值表 合成公式的层次： (1).若公式A是一单个的命题变项，则称A为0层公式； (2).称A是n+1(n≥0)层公式只需满足下列情况只一： a). A=¬B，B是n层公式； b). A=B∧C，其中B，C分别为i层和j层公式,且n=max(i, j)； c). A=B∨C，其中B，C的层次同b； d). A=B→C，其中B，C的层次同b； e). A=B↔C，其中B，C的层次同b； 从图论的观点来看每个多层公式可以用一个“树”来表示。

1.2 公式的解释与真值表 1.2.2：公式的解释与真值表 公式本身没有真值，只有在对其所有命题变元指定真值后才变成一个具有真值的命题。 定义1.9：设命题变元P1, P2, …,Pn是出现在公式G中的所有命题变元，指定P1, P2, …,Pn一组真值，则这组这组称为G的一个解释(Explanation),并记作I。 一般来说，若有n个命题变元，则应有2n个不同的解释。 定义1.10：公式G在其所有可能的解释下所取真值的表，称作G的真值表(Truth)。

1.2 公式的解释与真值表 例1.4：5个联结词的真值表(T：1，F：0) P Q ¬P P∧Q P ∨ Q P→Q P↔Q 1

1.2 公式的解释与真值表 例1.5：设公式G= ((P∧Q) →R )∧(P↔Q)，其中P，Q，R是G的命题变元，则其真值表如下： P Q 1

1.2 公式的解释与真值表 1.2.3：一些特殊的公式 例1.6：考虑：G1= ¬(P→Q) →P； G2=(P→Q) ∧P； G3= ¬(P∧ ¬ Q) ↔ ¬ (P→Q) 公式G1对所有可能的解释都具有“真”值，G3对所有解释都具有“假”值，公式G2则具有“真”和“假”值。

1.2 公式的解释与真值表 1.重言式： 定义1.11： (1). 公式G称为永真公式（重言式），如果在它的所有解释下都为“真”； 注意： (1). 重言式的否定是矛盾式，矛盾式的否定是重言式，所以研究其一就可以了；

1.2 公式的解释与真值表 (2). 重言式的合取，析取，蕴含，等值等都是重言式； (3). 重言式中有许多非常有用的恒等式叫永真蕴含式。 对任意的公式，判定其是否为永真公式，永假公式，可满足公式的问题称为给定公式的判定问题。由于一个命题公式的解释的数目是有穷的，所以命题逻辑的判定问题是可解的，即命题的永真，永假性是可判定的。其判定方法有真值表法和公式推演法。

1.2 公式的解释与真值表 2.恒等式： 例1.7： 判定公式： (1).(P→Q) ↔(¬ P∨Q); 例1.7： 判定公式： (1).(P→Q) ↔(¬ P∨Q); (2). ((P→Q)∧P) →Q； (3). P↔(Q ∧R)。 2.恒等式： 定义1.12：公式G，H，如果在其任意解释下，其真值相同，则称G是H的等价式(Equivalent)或称G恒等于H，记作GH。 解： (1).永真公式； (2).永真公式； (3). 可满足公式。

1.2 公式的解释与真值表 定理1.1：对于公式G和H， GH的充分必要条件是公式G ↔H是重言式。 证明： 必要性：假定GH，则G和H在其任意解释I下，或同为真或同为假，由“↔”的意义知， G ↔H在任意解释I下，其真值为真，即G ↔H为重言式； 充分性：假设公式G ↔H是重言式，I是它的任意解释，在I下， G ↔H为真，因此，G，H或同为真或同为假，由于I的任意性，故有GH。

1.2 公式的解释与真值表 注意与↔不同： (1).  ：逻辑等价关系， G  H不是命题公式； (3).计算机不能判断G，H是否逻辑等价，而可计算G ↔H是否为重言式。

1.2 公式的解释与真值表 常用逻辑恒等式（P，Q，R为任意命题，T为真命题，F为假命题）： E1 ¬¬P<=>P 双否定 E2 P∨P<=>P ∨的幂等律 E3 P∧P<=>P ∧的幂等律 E4 P∨Q<=>Q∨P ∨的交换律 E5 P∧Q<=>Q∧P ∧的交换律 E6 (P∨Q) ∨R<=>P∨(Q∨R) ∨的结合律 E7 (P∧Q) ∧R<=>P∧(Q∧R) ∧的结合律 E8 P∧(Q∨R) <=>P∧Q∨P∧R ∧在∨上的分配律 E9 P∨ (Q∧R) <=>(P∨Q)∧(P∨R) ∨在∧上的分配律 E10 ¬(P∨Q) <=>¬P∧¬Q 德·摩根定律 E11 ¬(P∧Q) <=>¬P∨¬Q

1.2 公式的解释与真值表 E12 P∨(P∧Q) <=>P 吸收律 E13 P∧ (P∨Q) <=>P E14 (P→Q) <=>¬P∨Q 蕴含等值式 E15 (P↔Q) <=>(P→Q) ∧(Q→P) 等价等值式 E16 P∨T<=>T 零律 E17 P∧F<=>F E18 P∨F<=>P 同一律 E19 P∧T<=>P E20 P∨¬P<=>T 排中律 E21 P∧¬P<=>F 矛盾律 E22 (P∧Q→R) <=>(P→(Q→R)) 输出律 E23 ((P→Q) ∧(P→¬Q)) <=>¬P 归谬律 E24 (P→Q) <=>¬Q→¬P 逆反律

1.2 公式的解释与真值表 3.永真蕴含式： 定义1.13：若A→B是一永真式，那么称为永真蕴含式，记为AB，读作A永真蕴含B 常用的永真蕴含式 I1 P=>P∨Q I2 P∧Q=>P I3 P∧(P→Q) =>Q I4 (P→Q) ∧¬Q=>¬P I5 ¬P∧(P∨Q) =>Q I6 (P→Q) ∧(Q→R) =>(P→R) I7 (P→Q) =>((Q→R) →(P→R)) I8 ((P→Q) ∧(R→S)) =>(P∧R→Q∧S) I9 ((P↔Q) ∧(R↔S)) =>(P↔R)

1.2 公式的解释与真值表 4.恒等式和永真蕴含式的两个性质： (1).若A<=>B， B<=>C，则A<=>C；若A=>B， B=>C，则A=>C. (即逻辑恒等和永真蕴含都是可传递的) 证明：A<=>B， B<=>C，即A↔B， B↔C为重言式，对任意的解释I，A和B，B和C的真值相同，则A和C的真值相同。 ∴A ↔C为重言式，即A<=>C； A=>B， B=>C，即A→B， B→C为真； ∴ (A→B)∧(B→C)为真，由公式I6： A→C为重言式，即A=>C。

1.2 公式的解释与真值表 (2).若A=>B， A=>C，则A=>B∧C. 证明：A为真时，B，C都为真，则B∧C也为真，即A→B∧C为真；A为假时，则不管B∧C是真还是假时，A→B∧C均为真，因此A=>B∧C。

1.2 公式的解释与真值表 1.2.4：代入规则和替换规则 当一个公式是永真式或永假式时，其公式的真值完全跟随其命题变元的真值的变化而变化，因此，当用其他公式来取代公式中的命题变元时，不会改变公式的永真性和永假性 定理1.2(代入定理) ：设G(P1, …,Pn)是一个命题公式，其中P1, …,Pn是命题变元，G1(P1, …,Pn), … Gn(P1, …,Pn)为任意的命题公式，此时若G是永真公式或永假公式，则用G1取代P1,…,Gn取代Pn后，得到的新的命题公式G(G1,…,Gn) <=> G’(P1, …,Pn)也是一个永真公式或永假公式。

1.2 公式的解释与真值表 例1.8：设G(P, Q) = ¬(P→Q) →P；用H(P, Q) =(P ∧Q)；S(P, Q) =(P ↔Q)代入G验证代入定理。 定理1.3(替换定理) ：设G1是G的子公式，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到的新的命题公式H，若G1<=>H1，则G<=>H。 例1.9：简化开关电路： 解：G(H, S) <=> ¬(H→S)→H <=> ¬((P ∧Q) →(P↔Q))→(P∧Q) <=>G’(P, Q); 用真值表验证 ，先验证G(H, S)，再验证G’(P, Q)。 解：设P：开关P闭合，Q：开关Q闭合，S：开关S闭合，G：灯泡亮 则G<=>(P∧Q∧S)∨(P∧R∧S) <=>(P∧S∧Q)∨(P∧S∧R) <=>(P∧S) ∧(Q∨R) Q S P P R S

1.2 公式的解释与真值表 例1.10：将下面程序语言进行化简： if A then if B then X else Y else if B then X else Y 例1.11：简化逻辑电路： P ∧ Q ∨ ∧ R ∧ 则执行X的条件为：(A∧B)∨(¬A∧B) <=>B∧(A∨¬A) <=>B 执行Y的条件为：(A∧¬B)∨(¬A∧¬B) <=>¬B∧(A∨¬A) <=>¬B 解：设P：输入端P为高电位，Q：输入端Q为高电位，R：输入端R为高电位； 则：((P∧Q)∨(P∧R))∧(Q∨R) <=>(P∧(Q∨R))∧(Q∨R) ∴电路简化为： ∴程序可简化为：if B then X else Y，流程图为： ∨

1.2 公式的解释与真值表 例1.12：求证： (1).P∨¬((P∨¬Q)∧Q)是永真公式； (2).P→(Q→R)<=>(P∧Q)→R; (3).(P∧(Q∨R))∨(P∧¬Q∧ ¬R)<=>P; (4).(¬P∧(¬Q∧R))∨(Q∧R)∨(P∧R)<=>R; 证明： (1). P∨¬((P∨¬Q)∧Q) <=> P∨¬(P∨¬Q)∨¬Q <=>(P∨¬Q)∨ ¬(P∨¬Q) <=>T (2). P→(Q→R) <=>¬P∨(Q→R) <=>¬P∨(¬Q ∨R) <=>(¬P∨¬Q)∨R <=>¬ (P∧Q)∨R <=>(P∧Q)→R (3).(P∧(Q∨R))∨(P∧¬Q∧ ¬R) <=> P∧((Q∨R)∨(¬Q∧ ¬R) <=> P∧((Q∨R)∨¬ (Q∨R) <=> P∧T <=> P (4).(¬P∧(¬Q∧R))∨(Q∧R)∨(P∧R) <=> ((¬P∧¬Q)∧R)∨((Q∨P)∧R) <=> (¬(P∨Q)∧R)∨((Q∨P)∧R) <=> (¬(P∨Q) ∨(Q∨P))∧R <=> T∧R <=> R

¬A(P1,P2, …,Pn)<=>A*(¬P1, ¬P2, …, ¬Pn) 公式(1) 1.2 公式的解释与真值表 1.2.5：对偶原理 定义1.14：设公式A，其中仅有联结词∧， ∨，¬。在A中将∧，∨，T，F分别换以∨，∧，F，T得到公式A*，则A*称为A的对偶公式。 对A*采取同样的替换，又得到A，所以A也是A*的对偶，即对偶是相互的。 例，¬P∨(Q∧R)和¬P∧(Q∨R)互为对偶；P∨F和P∧T互为对偶。 定理1.4：设A和A*是对偶式，P1,P2, …,Pn是出现于A和A*中所有命题变元，于是 ¬A(P1,P2, …,Pn)<=>A*(¬P1, ¬P2, …, ¬Pn) 公式(1) 证明：(用归纳法证明) (1): ¬Pi<=>¬Pi；¬T<=>F；¬F<=>T；所以当A是由一个变元或常元构成时公式(1)成立； (2): 设A1(P1,P2, …,Pn)，A2(P1,P2, …,Pn)对公式(1)成立，即： ¬A1(P1,P2, …,Pn)<=>A1*(¬P1, ¬P2, …, ¬Pn) ¬A2(P1,P2, …,Pn)<=>A2*(¬P1, ¬P2, …, ¬Pn) 现证明：①A1∧A2，②A1∨A2，③¬A1时， 公式(1)也成立。 ①记A1∧A2为A，A<=> A1∧A2则A*<=> A1*∨A2*,由定义： ¬A(P1,P2, …,Pn) <=>¬(A1(P1,P2, …,Pn)∧A2(P1,P2, …,Pn)) <=>¬A1(P1,P2, …,Pn)∨¬A2(P1,P2, …,Pn) <=>A1*(¬P1, ¬P2, …, ¬Pn)∨A2*(¬P1, ¬P2, …, ¬Pn) <=>A*(¬P1, ¬P2, …, ¬Pn) ②A1∨A2，同理可证 ③¬A1，记¬A1为A，¬A1<=>A则A* <=>¬A* <=>¬(¬A1(P1,P2, …,Pn)) <=>¬(A1*(¬P1,¬P2, …,¬Pn)) <=>A*(¬P1,¬P2, …,¬Pn) ∴公式(1)成立

1.2 公式的解释与真值表 定理1.5：若A<=>B，且A，B为命题变元P1,P2, …,Pn及联结词∧，∨，¬构成的公式，则A*<=>B* (对偶原理) 例，若(P∧Q)∨(¬P∨(¬P∨Q)<=> ¬P∨Q，则由对偶原理，得 (P∨Q)∧(¬P∧(¬P∧ Q)<=> ¬P∧Q 定理1.6：如果A=>B，且A，B为命题变元P1,P2, …,Pn及联结词∧，∨，¬构成的公式，则B*=>A* 证明： A<=>B，即 A(P1,P2, …,Pn)↔B(P1,P2, …,Pn)永真 ∴ ¬ A(P1,P2, …,Pn)↔ ¬B(P1,P2, …,Pn)永真 由定理1.4 ：A*(¬P1, ¬P2, …, ¬Pn) ↔B*(¬P1, ¬P2, …, ¬Pn)永真 由代入定理：A*(P1, P2, …, Pn)↔B*(P1, P2, …, Pn)永真 ∴ A*<=>B* 证明： A=>B，即 A(P1,P2, …,Pn)→B(P1,P2, …,Pn)永真 ∴ ¬ B(P1,P2, …,Pn)↔ ¬A(P1,P2, …,Pn)永真 由代入定理：以¬Pi代Pi，得： B*(P1, P2, …, Pn)↔A*(P1, P2, …, Pn)永真 ∴ B*=>A*

1.3 联结词的完备集 1.3.1 联结词的扩充 1. 一元运算： 我们来看一个命题变元在一个一元运算的作用下可能的真值表。 P f1 f2 我们知道，命题公式通过等价公式的转换，可以以不同的形式表示出来。我们前面介绍了5个联结词，是否够用呢？ 1.3.1 联结词的扩充 1. 一元运算： 我们来看一个命题变元在一个一元运算的作用下可能的真值表。 P f1 f2 f3 f4 1

1.3 联结词的完备集 2.二元运算： 考虑两个变元在一个二元运算作用下可能的真值表。 因此，最多只能定义4种运算，但除了否定之外，永假，永真，恒等作为运算意义不大，所以一般不再定义其它一元运算。 2.二元运算： 考虑两个变元在一个二元运算作用下可能的真值表。 P Q f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 1 永假 或非 蕴含否定 合取 非P 非Q 等价 异或 恒等Q 恒等P 与非 蕴含 析取 永真 ☆ △ ◇

1.3 联结词的完备集 ◇：已定义；☆：意义不大；△：可再定义 f1=P∧¬P=F，f2= ¬(P∨Q)，f3= ¬(P→Q)， f4= ¬(Q→P)， f5 =P∧Q， f6 = ¬P， f7 = ¬Q， f8=(P↔Q)， f9 = ¬(P↔Q) f10=Q， f11=P， f12 = ¬(P∧Q)， f13 =P→Q， f14 = P∨Q， f15 = Q→P， f16 =P∨¬P=T， 其中：f2，f3(或f4)，f9，f12都是两个联结词的组合，为了叙述方便，可以引进下列几个联结词：

1.3 联结词的完备集 P Q<=>¬(P↔Q) ，P Q<=>¬(P→Q) ， 记号 复合命题 读法 记法 备注 f9 异或 P不可兼或Q P异或Q P　Q 逻辑电路中的异或门 f3，f4 蕴含否定 P和Q的蕴含否定 P蕴含否定Q P　 Q f12 与非 ↑ P和Q的与非 P与非Q P↑Q 逻辑电路中的与非门 f2 或非 ↓ P和Q的或非 P或非Q P↓Q 逻辑电路 中的或非门 P Q<=>¬(P↔Q) ，P Q<=>¬(P→Q) ， P↑Q<=>¬(P∧Q) ， P↓Q<=>¬(P∨Q) ， 这9个联结词构成命题演算中的所有联结词。

1.3 联结词的完备集 1.3.2 与非，或非，异或的性质 1.与非的性质： P↑QQ↑P，P↑P  ¬P， (P↑Q)↑(P↑Q)P∧Q， (P↑P)↑(Q↑Q)P∨Q 2.或非的性质： P↓Q  Q↓P，P↓P  ¬P， (P↓Q)↓(P↓Q)P∨Q， (P↓P)↓(Q↓Q)P∧Q 3.异或的性质： P<=>0，0 P<=>P， 1 P<=>¬P

1.3 联结词的完备集 1.3.3：全功能联结词 定义1.15：设S是联结词的集合，(1)用S中的联结词表示的公式，可以等价地表示任何命题公式，则称S是一个联结词完备集 (或全功能集合) (Adequate Set of Connectives)，(2)S是一个联结词的完备集，且S中无冗余的联结词(即集合中不存在可以被其中的其它联结词所定义的联结词)，则称S为极小联结词完备集。 由前面1.3.1的分析知，{¬,∧,∨,→,↔}是一个联结词完备集，而A→B<=>¬A∨B， A↔B<=>(A→B)∧(B→A)，所以→，↔是冗余的，故{¬,∧,∨}也是一个联结词完备集,而A∨B<=>¬(¬A∧¬B)，所以∨也是冗余的, ∴ {¬,∧}也是一个联结词完备集，进一步地,可知{¬,∧}是一个极小联结词完备集。 为了表达全部的命题公式，至少需要用多少个联结词呢？

1.3 联结词的完备集 证明联结词完备集{¬,∧}是一个极小的。 同理，{¬,∨}，{¬, →}，{¬, }也是极小完备集，此外由1.3.2中↑，↓的性质可知 ，{↑}，{↓}也是极小完备集； {∧,∨,→, ↔}及其子集不是完备集； 实际应用中经常采取的联结词集合为{¬,∧,∨}。 例1.13：试将公式(P→(Q∨¬R))∧(¬P∧Q)用仅含{¬ ，∨}的公式等价地表示出来。 证明：用反证法。 假设¬是冗余的联结词，则¬可由仅含∧的公式表示，则对于任意的公式A，B ，…，有¬A<=>A∧B∧ …当A，B ，…均为0时，右边真值为0，左边真值为1，矛盾，∴ ¬不是冗余的； 而二元联结词∧不可能一元联结词¬来表示, ∴∧也不是冗余的； ∴ {¬,∧}是极小完备集。 解： (P→(Q∨¬R))∧(¬P∧Q) <=> (¬P∨(Q∨¬R))∧(¬P∧Q) <=> (¬P∧(¬P∧Q))((Q∨¬R))∧(¬P∧Q) <=>(¬P∧Q)∨(Q∧¬P∧Q)∨(¬R∧¬P∧Q) <=> (¬P∧Q)∨(¬P∧Q) ∨((¬P∧Q) ∧¬R) <=> (¬P∧Q) <=> ¬(P∨¬Q)

1.4：范式 1.4.1：范式 对于给定公式的判定问题，可用真值表方法加以解释，但当公式中命题变元的数目较大时，计算量较大，每增加一个命题变元，真值表的行数要翻倍，计算量加倍，此外，对于同一问题，可以从不同的角度去考虑，产生不同的但又等价的命题公式，即同一个命题可以有不同的表达形式。这样给命题演算带来了一定的困难，因此，有必要使命题公式规范化，为此，引入了范式的概念。

1.4：范式 定义1.16： (1)：命题变元或命题变元的否定称为文字； (2)：有限个文字的析取式称为简单析取式(基本和)，有限个文字的合取式称为简单合取式(基本积)； (3)：由有限个简单合取式构成的析取式称为析取范式(Disjunctive Normal From)，由有限个简单析取式构成的合取式称为合取范式(Conjunctive Normal From)。

1.4：范式 例如， ①：P，¬P ；②：P∨Q∨ ¬R； ③：¬P∧Q∧R；④：(P∧Q)∨(¬P∧Q)； ⑤：(P∨Q)∧(¬P∨Q)； 性质： (1)：一个文字既是一个析取范式又是一个合取范式； (2)：一个析取范式为矛盾式，当且仅当它的每个简单合取式是矛盾式； (3)一个合取范式为重言式，当且仅当它的每个简单析取式是重言式。 ①：P，¬P 是文字，简单析取式，简单合取式，析取范式，合取范式； ②：P∨Q∨ ¬R是简单析取式，析取范式，合取范式； ③：¬P∧Q∧R是简单合取式，析取范式，合取范式； ④：(P∧Q)∨(¬P∧Q)是析取范式； ⑤：(P∨Q)∧(¬P∨Q)是合取范式。

1.4：范式 定理1.7：任一命题公式都存在着与之等值的析取范式和合取范式。 例1.14：求公式(P∧¬Q) ↔(P→R)的析取范式和合取范式。 证明：对于任一公式，可用下面的方法构造出与其等值的范式： (1)利用等价公式：A ↔B<=>(A→B)∧(B→A)使公式中仅含联结词¬，∧，∨； (2)利用德•摩根定律和双重否定律¬(A∨B) <=> ¬A∧¬B，¬(A∧B) <=> ¬A∨¬B， ¬ ¬A <=>A将否定符¬移到命题变元前，并去掉多余的否定符； (3)利用分配律A∧(B∨C) <=>(A∧B)∨(A∧C)， A∨(B∧C) <=>(A∨B)∧(A∨C)将公式化成析取范式或合取范式，所得即与原公式等价。 证毕 解： (P∧¬Q) ↔(P→R) <=> ((P∧¬Q)→(P→R))∧((P→R)→(P∧¬Q)) <=> (¬(P∧¬Q)∨(P→R))∧(¬(P→R)∨(P∧¬Q)) <=>((¬P∨Q)∨(¬P∨R))∧(¬(¬P∨R)∨(P∧¬Q)) <=>(¬P∨Q∨¬P∨R)∧( P∧¬R)∨(P∧¬Q)) <=>(¬P∨Q∨R)∧P∧ (¬R∨¬Q)(合取范式) <=>(Q∧P∧¬R)∨(R∧P∧¬R) ∨ (Q∧P∧¬Q)∨(R ∧P∧¬Q) <=>(Q∧P∧¬R)∨(R∧P∧¬Q)(析取范式)

1.4：范式 1.4.2：主析取范式和主合取范式 范式虽然为命题公式提供了一种统一的表达形式，但这种表达形式却并不是唯一的。如公式(P∨Q)∧(P∨R)与之等价的公式有：P∨(Q∧R)，(P∧P)∨(Q∧R) ，P∨(Q∧¬Q)∨(Q∧R)，P∨(P∧R)∨(Q∧R),等，这种不唯一的表达形式给研究问题带来了不便，因此有必要引进更为标准的范式。 定义1.17：(1)包含A中所有命题变元或其否定一次仅一次的简单合取式，称为极小项；(2)包含A中所有命题变元或其否定一次仅一次的简单析取式，称为极大项；(3)由有限个极小项组成的析取范式称为主析取范式； (4)由有限个极大项组成的合取范式称为主合取范式。

1.4：范式 1.极小项和极大项的性质 一般来说，对于n个命题变元，则应有 个不同的极小项和 个不同的极大项。 对于两个命题变元P，Q来说，由于每个P，Q可以取命题变元自身和其否定，所以其对应的极小项和极大项分别有四项：P∧Q， ¬P∧Q，P∧¬Q，¬P∧¬Q；P∨Q， ¬P∨Q, P∨¬Q， ¬P∨¬Q。其真值表如下： 一般来说，对于n个命题变元，则应有 个不同的极小项和 个不同的极大项。 P Q P∧Q ¬P∧Q P∧¬Q ¬P∧¬Q ¬P∨¬Q ¬P∨Q P∨¬Q P∨Q 1

1.4：范式 性质： (1)：没有两个不同的极小项是等价的，且每个极小项只有一组真值指派使该极小项的真值为真，因此可给极小项编码，使极小项为“T”和那组真值指派为对应的极小项编码；如极小项¬P∧¬Q∧¬R只有在P，Q，R分别取真值0，0，0时才为真，所以有时又可用 ( )来表示，又如¬P∧Q∧¬R也可用 ( )来表示。 (2)：没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假。因此可给极大项编码，使极大项为“F”的那组真值指派为对应的极大项的编码，如极大项¬P∨¬Q∨¬R只有在P，Q，R分别取真值1，1，1时才为假，所以有时又可用 来表示。

1.4：范式 三个命题变元的真值取值与极小项和极大项的对应对位关系表： P Q R 极小项 极大项 m0= ¬P∧¬Q∧¬R m0= ¬P∧¬Q∧¬R M0= P∨Q∨R 1 m1= ¬P∧¬Q∧R M1= P∨Q∨¬R m2= ¬P∧Q∧¬R M2= P∨¬Q∨R m3= ¬P∧Q∧R M3= P∨¬Q∨¬R m4= P∧¬Q∧¬R M4= ¬P∨Q∨R m5= P∧¬Q∧R M5= ¬P∨Q∨¬R m6= P∧Q∧¬R M6= ¬P∨¬Q∨R m7= P∧Q∧R M7= ¬P∨¬Q∨¬R

1.4：范式 (3)：任意两极小项的合取必假，任意两个极大项的析取必为真。极大项的否定是极小项，极小项的否定是极大项，即 (4)：所有极小项的析取为永真公式，所有极大项的合取是永假公式，即

1.4：范式 2.主析取范式和主合取范式的存在性和唯一性 定理1.8：任何命题公式的主析取范式和主合取范式存在且唯一，即任何命题公式都有且仅有一个与之等价的主合取范式和主析取范式。 [真值表技术] 例1.15：求命题公式((P∧Q)→R)∧(P↔Q)的主析取范式。 例1.16：求命题公式(P→Q)↔R的主合取范式。 证明：(证明该定理的方法与过程实际也就是求一个公式的主析取范式和主合取范式的方法，主要有两种不同的方法，一是真值表技术，一是公式转换法) [真值表技术] 根据极小项的性质，任何一个极小项的真值解释中仅有一种解释使得其真值为真，而主析取范式是由一些极小项的析取构成，因此考虑命题公式的真值表，对命题公式的每一个为真的解释，存在且唯一存在一个对应的极小项，将所有真值解释对应的极大项做析取，得到主析取范式，由极小项的性质知，在所有解释下，该主析取范式与原命题公式的真值相同，即等价。由主析取范式的构造方式知，该主析取范式存在且唯一存在。同理，主合取范式也存在且唯一存在。 解：首先看该命题公式的真值表： P Q R ((P∧Q)→R)∧(P↔Q) 0 0 0 1 0 0 1 1 1 1 1 1 其余 0 考虑三种真值的解释，对应的极小项分别为m0，m1，m7，即¬P∧¬Q∧¬R， ¬P∧¬Q∧R，P∧Q∧R， ∴其主析取范式为： (¬P∧¬Q∧¬R)∨(¬P∧¬Q∧R) ∨ (P∧Q∧R)。 解：其真值表如下： P Q R (P→Q)↔R 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 其余 1 考虑四种真值为假的解释，对应的极大项为M0，M2，M5，M6 所以其主合取范式为：(P∨Q∨R) ∧(P∨¬Q∨R) ∧(¬P∨Q∨¬R) ∧( ¬P∨¬Q∨R)

1.4：范式 利用真值表技术求主析取范式和主合取范式的方法： ① ：选出公式的真值结果为真的所有行，在这样的行中，找到其每一个解释所对应的极小项，将这些极小项析取即可得到相应的主析取范式； ②：选出公式的真值结果为假的所有行，在这样的行中，找到其每一个解释所对应的极大项，将这些极大项合取即可得到相应的主合取范式。

1.4：范式 [公式转换法] 唯一性： 设任一命题公式A有两个主析取范式B和C，则因为A<=>B， A<=>C，所以B<=>C，若B，C是A的(在不计极小项的顺序的情况下)不同的主析取范式，则必有在存在极小项mi，mi只存在于B，C之一中，不妨设mi在B中,而不在C中，因此i之二进制表示B的一个真值解释，而对于C则为真值为假的解释，这与B<=>C矛盾，所以B和C相同，同理主合取范式也是唯一的。 例1.17：利用公式的等价求G=(P→Q)∧R的主析取范式和主合取范式 除了利用真值表技术外，还可利用公式之间的等价关系来求主范式，其步骤如下： 首先利用定理1.7中的方法，将公式转化为等价的范式： (1)利用等价公式中的等价式和蕴含式将公式中的→，↔用联结词¬，∧，∨来取代； (2)利用德•摩根定律将否定号¬移到各个命题变元的前端； (3)利用结合律，分配律，吸收律，等幂律，交换律等将公式化成其等价的析取和合取范式 在此基础上，进一步将其转化为主范式 (4)在析取范式的简单合取式和合取范式的简单析取式中，如同一命题变元出现多次，则将其化成只出现一次； (5)去掉析取范式中的所有永假式的简单合取式和合取范式中所有永真式的简单析取式，即去掉简单合取式中含有形如P∧¬P的子公式和简单析取式中含有形如P∨¬P的子公式; (6)若析取范式的某一个简单合取式中缺少该命题公式中所规定的命题变元，如缺少命题变元P，则可用公式(¬P∨P)∧Q=Q 将命题变元补进去，并利用分配律展开，然后合并相同的简单析取式，此时得到的简单析取式将是标准的极大项； (7)利用等幂律将相同的极小项和极大项合并,同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。 解：G =(P→Q)∧R =(¬P∨Q)∧R =((¬P∨Q)∨(R∧¬R))∧((P∧¬P)∨(Q∧¬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)(主合取范式) G =(P→Q)∧R =(¬P∨Q)∧R =(¬P∧R)∨(Q∧R) =(¬P∧(¬Q∨Q)∧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) (主合取范式)

1.4：范式 3：主合取范式和主析取范式之间的转换 真值表技术和公式转换方式在求主析取范式和主合取范式各有其优点，在公式中的命题变元较少时时，利用真值表技术更为简单。当命题变元较多时，一般采用公式转换法，而在公式转换中，有时求主析取范式更为方便，而有时求主合取范式更为方便。但两者之间必然有相应的关系。下面介绍一种两者之间的转换方法。

1.4：范式 (1)：已知公式G的主析取范式求公式G的主合取范式的步骤如下： b：G<=>¬(¬G)即是G的主合取范式 a：求¬G的主析取范式，即G的主析取范式中没有出现过的极小项的析取 b：G<=>¬(¬G)即是G的主合取范式 即：若 为G的主析取范式，则 为¬G的主析取范式，其中 后剩下的极小项。则 为G的主合取范式。

1.4：范式 (2)：已知公式G的主合取范式，求G的主析取范式的步骤如下： a：求¬G的主合取范式，即G的主合取范式中没有出现过的极大项的合取 b： G<=>¬(¬G)即是G的主析取范式， 即，若 为G的主合取范式，则 为¬G的主合取范式。其中 后剩下的极大项。 则 为G的主析取范式

1.4：范式 例1.18：设G=(P∧Q)∨(¬P∧R)∨(¬Q∧¬R),求其对应的主析取范式和主合取范式 性质： (1)：如果命题公式是永真公式<=>它的主析取范式包含所有极小项，此时主合取范式不含有任何极大项，为空，记1或T (2)：如果命题公式是永假公式<=>它的主合取范式包含所有极大项，此时主析取范式不含有任何极小项，为空，记0或F (3)：两个命题公式A，B，A<=>B当且仅当A与B有相同的真值表，又当且仅当A与B有相同的主析取范式(主合取范式)。(真值表和主范式是描述命题公式标准形式的两种不同的等价形式)。 解： G=(P∧Q)∨(¬P∧R)∨(¬Q∧¬R) <=>(P∧Q∧(¬R∨R))∨(¬P∧(¬Q∨Q)∧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)∨(P∧Q∧R) <=>m0∨m1∨m3∨m4∨m6∨m7 ¬G= m2∨m5 G<=> ¬ ¬G <=> ¬ (m2∨m5) <=> ¬m2∧¬m5 <=>M2∧M5<=>(P∨¬Q∨R)∧(¬P∨Q∨¬R)

1.4：范式 5.主范式的应用 (1).求公式的成真或成假赋值。 如：p →q<=>m0∨m1∨m3=m00∨m01∨m11 ∴00，01，11是成真赋值，10是成假赋值 (2).判定问题。 根据主范式的定义和性质，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式A，其次按下列条件判定之：

1.4：范式 ①若A<=>T，或A可化为与其等价的含 个极小项的主析取范式，则A为永真式； ②若A<=>F，或A可化为与其等价的含 个极大项的主合取范式，则A为永假式； ③若A不与T或F等价，且又不含 个极小项或极大项，则A为可满足的。 例，判定公式：(1).(P→Q)∧Q； (2). (P→Q) →(¬ P∨Q)。 解：(1) (P→Q)∧Q<=>M0∧M2<=>m1∨m3 ∴可满足； (2) (P→Q) →(¬ P∨Q)<=>¬(¬ P∨Q)∨(¬ P∨Q)<=>T ∴永真。

1.4：范式 (3).证明等价性。 由于任何一公式的主范式是唯一的，所以求给定两公式的主范式，若主范式相同，则给定两公式是等价的。 例，求证(P→Q) ∧(P→R)<=>P→ (Q∧R). (4).解决实际问题。 例，某科研所要从3名科研骨干A，B，C中挑选1-2名出国进修，由于工作需要，选派时要满足以下条件： ①若A去，则C同去；②若B去，则C不能去；③若C不去，则A或B可以去。 证明：(P→Q) ∧(P→R) <=>(¬P∨Q)∧(¬P∨R) <=>((¬P∨Q)∨(¬R∨R))∧(¬P∨(¬Q∨Q)∨R) <=>(¬P∨Q∨R)∧(¬P∨Q∨¬R))∧(¬P∨Q∨R)∧(¬P∨¬Q∨R) <=>M4∧M5∧M4∧M6 <=>M4∧M5∧M6 P→(Q∧R) ∴两公式等价。 解：设：p：派A去；q：派B去；r：派C去。 由已知条件可得公式： (p →r)∧(q→¬r)∧(¬r→ (p ∨q)) 经过演算得： m1∨m2∨m5 由于m1=¬p ∧q ∧r，m2=¬p ∧q ∧¬r，m5=p ∧¬q ∧r 可知，选派方案有3中： (a).C去，而A，B都不去； (b).B去，而A，C都不去； (c).A，C同去，而B不去。

1.5：命题逻辑的推理理论 1.5.1：推理的基本概念和推理形式 推理也称论证，它是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题形式。 定义1.18：设G1，G2，…，Gn，H是命题公式，若对于G1，G2，…，Gn，H中出现的命题变元的任意一组赋值，或者G1∧G2∧…Gn为假，或者当G1∧G2∧…Gn为真，H也为真，则称H是G1，G2，…，Gn的有效结论(Efficacious Conclusion)或逻辑结果(Logic Conclusion)。 G1，G2，…，Gn仍为一组前提(Premise)。 命题逻辑主要包括三方面的内容：概念，判断，推理。即首先用符号化来表示各式各样的语句，并对语句进行肯定与否定的判断，然后通过一个或几个判断来推出结论。我们把从前提(Premise)(或假设Hypothesis)出发，依据公认的推理规则，推导出一个结论(Conclusion)，这一过程称为有效推理(Efficacious Inference)或形式证明(Formal Proof)。所得的结论称为有效结论(Efficacious Conclusion)。值得注意的是，我们关心的不是结论的真实性而是所谓推理的有效性，前提的实际真值不作为确定推理有效性的依据。而所谓推理有效，指的是它的结论是它的前提的合乎逻辑的结果。即，如果它的前提都为真，那么所得的结论也必然为真。而并不是要求前提或结论一定为真或假。如果推理是有效的话，那么不可能它的前提为真时，而它的结论为假。

1.5：命题逻辑的推理理论 定理1.9：命题公式G1，G2，…，Gn推出结论H的推理正确或公式H是前提条件{G1，G2，…，Gn}的逻辑结果，当且仅当(G1∧G2∧…Gn) →H为重言式。 =>：逻辑蕴含关系， G=>H不是命题公式，计算机判断G=>H办不到； →：蕴含联结词，G →H是命题公式，计算机可判断G →H为永真公式。 因此我们可以用蕴含式来描述推理。 我们将由{G1，G2，…，Gn}推理H，用蕴含式表示为： (G1∧G2∧…Gn) →H 将由{G1，G2，…，Gn}正确推理出H，用蕴含式表示为： G1∧G2∧…Gn =>H 证明：根据推理的逻辑结果的定义以及永真蕴含式的定义可知，定理成立。

1.5：命题逻辑的推理理论 1.5.2：判断结论有效的方法 推理的形式结构为：G1∧G2∧…Gn →H，书写为： 1.真值表法；2.等值演算法；3.主析取范式法

1.5：命题逻辑的推理理论 1.真值表法 设P1，P2，…，Pn是出现在前提G1，G2， …，Gn和结论H中的一切命题变元，如果将P1，P2，…，Pn中所有可能的介绍及G1，G2， …，Gn，H的对应真值结果都在一个表中，根据“→”的定义，则有如下判断方法： (1)对所有G1，G2， …，Gn都具有真值T的行(表示前提为真的行)，如果在每个这样的行中，H也具有真值T，则H是G1，G2， …，Gn的逻辑结果； (2)对所有H具有真值为F的行(表示结论为假的行)，如果在每一个这样的行中， G1，G2， …，Gn中至少有一个公式的真值为F(前提也为假)。则H是G1，G2， …，Gn的逻辑结果。

1.5：命题逻辑的推理理论 例1.18：判断下列H是否为前提G1，G2的逻辑结果。 (1). H：Q; G1：P，G2：P→Q； (2). H：¬P; G1：P→Q ，G2：¬Q； (3). H：Q; G1： ¬P，G2：P→Q； 2.等值演算法 直接用等值演算来判断推理的形式结构是否是重言式。 例1.19：下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。 解：(1){G1,G2}|=H，(2){G1,G2}|=H，(3){G1,G2}|≠H。 解：设，p：马芳下午去看电影。q：马芳下午去游泳。 前提：p∨ q，¬p；结论：q 推理的形式结构：((p∨ q) ∧¬p) →q 用等值演算法来判断上式是否为重言式。 ((p∨ q) ∧¬p) →q <=> ¬((p∨ q) ∧¬p) ∨ q <=>((¬ p ∧ ¬ q) ∨ p) ∨ q <=>((¬ p ∨ p) ∧ (¬ q∨ p)) ∨ q <=> ¬ q∨ p∨ q <=>1

1.5：命题逻辑的推理理论 3.主析取范式法 将推理的形式结构转化为主析取范式，但仍判断其是否为重言式。 例1.20：若下午气温超过30℃，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温超过了30 ℃。 以上方法，当形式结构比较复杂，特别是所含的命题变元较多时，一般很不方便，下面介绍构造证明法。 解：设，p：下午气温超过30℃，q：王小燕去游泳，r：王小燕去看电影。 前提：p →q，q→¬r；结论：¬r→p。 推理的形式结构：((p →q)∧( q→¬r)) → (¬r→p)， 用主析取范式法判断上式是否为重言式。 ((p →q)∧( q→¬r)) → (¬r→p) <=> ¬((¬ p ∨ q)∧(¬ q∨¬r)) ∨(r∨p) <=> ((p ∧ ¬ q) ∨(q∧r)) ∨r∨p <=> p ∨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) <=>m1 ∨m3 ∨m4 ∨m5 ∨m6 ∨m7 可见((p →q)∧( q→¬r)) → (¬r→p)不是重言式(主析取范式中少两个极小项m0，m2)，所以推理不正确。

1.5：命题逻辑的推理理论 1.5.3：构造证明法 构造证明法是依据一些公认的推理规则，从前提出发，推导结论，它可以看作公式的序列，其中每个公式都是按照事先规定的规则得到的，且可将所用的规则在公式后写明，该系列最后一个公式是所要证明的结论。 (1)推理规则： ⑴前提引入规则：在推理的任何步骤上都可以引入前提； ⑵结论引入规则：在推理的任何步骤上所得到的结论都可以做为后续证明的前提； ⑶置换规则：在推理的任何步骤上，命题公式的子公式都可以用与之等价的公式置换，得到公式序列中又一个公式。

1.5：命题逻辑的推理理论 (2)推理定理：(一些重要的永真蕴含式) 1.A=>(A∨B) 附加律 2.A∧B=>A 化简律 4 .(A→B) ∧¬B =>¬A 拒取式 5.(A˅B) ∧¬B =>A 析取三段论 6 .(A→B) ∧(B→C) =>A→C 假言三段论 7 .(A↔B) ∧(B↔C) =>A↔C 等价三段论 8 .(A→B)∧(C→D)∧(A∨C) =>(B∨D) 构造性二难 (A→B)∧(¬A→B)∧(A∨¬A) =>B构造性二难(特殊形式) 9 .(A→B)∧(C→D)∧(¬B∨¬D) =>(¬A∨¬C)破坏性二难

1.5：命题逻辑的推理理论 由着9个定律中的8个可以得到8个推理规则： ⑷附加规则：A|=(A∨B) ⑸化简规则：(A∧B)|=A ⑺拒取式规则：(A→B)，¬B|=¬A ⑻假言三段论规则：(A→B)，(B→C)|=(A→C) ⑼析取三段论规则：(A ˅ B)，¬B|=A ⑽构造性二难规则：(A→B)，(C→D)，(A∨C) |=(B∨D) ⑾破坏性二难规则：(A→B)，(C→D)，(¬B∨¬D) |=(¬A∨¬C) ⑿合取引入规则：A，B|=(A∧B)

1.5：命题逻辑的推理理论 例1.21：构造下列推理的证明： 前提：p ∨q，p →¬r，s →t，¬s →r，¬t 结论：q 例1.22：分析下列事实：“早饭我吃面包或蛋糕；如果我吃面包，那么我还要喝牛奶；如果我吃蛋糕，那么我还要喝咖啡；但我没有喝咖啡，所以早饭我吃的是牛奶和面包。”写出前提和有效结论并证明之。 例1.23：用构造法证明，找出下列推理的有效结论。 如果我考试通过了，那么我很快乐；如果我快乐，那么阳光灿烂；现在是晚上11点，天很暗。 证明：(1) s →t 前提引入 (2) ¬t 前提引入 (3) ¬s (1)，(2)拒取式 (4) ¬s →r 前提引入 (5) r (3)，(4)假言推理 (6) ¬ ¬r (5)置换 (7) p → ¬r 前提引入 (8) ¬p (6)，(7)拒取式 (9) p ∨q 前提引入 (10) q ∨p (9)置换 (11) q (10)，(8)析取三段论 解：令P：早饭我吃面包；Q：早饭我吃蛋糕；R：我喝牛奶；S：我喝咖啡。 由题意知，前提为P∨Q，P→R，Q→S，¬S；有效结论为Ｐ∧Ｒ。 　　证明如下：① Q→S 前提引入 　　　　　　　② ¬S 前提引入　 　　　　　　　③ ¬Ｑ ①，②拒取式 　　　　　　　④ P∨Q 前提引入 　　　　　　　⑤ ¬Ｑ→Ｐ ④置换 　　　　　　　⑥ Ｐ ③，⑤假言推理 　　　　　　　⑦ Ｐ→Ｒ 前提引入 　　　　　　　⑧ R ⑥，⑦假言推理 ⑨ Ｐ∧Ｒ ⑥，⑧合并引入 解：设P：我考试通过了；Q：我很快乐；R：阳光灿烂；S：天很暗。 前提：P →Q，Q →R， ¬R∧S 推理：(1) P →Q 前提引入 (2) Q →R 前提引入 (3) P →R (1)，(2)假言三段论 (4) ¬R∧S 前提引入 (5) ¬R (4)化简 (6) ¬R (3)，(5)拒取式 ∴有效结论为：我考试没通过。

1.5：命题逻辑的推理理论 (3)P1∧P2∧…∧Pn →(P → Q)形式命题的证明。 附加前提证明法(CP规则) 若P1，P2，…，Pn ，P|= Q，则P1，P2，…，Pn |= P→Q 附加前提证明法的意义在于：当推理的结论是蕴含式时，可以将其前件作为附加前提引用，只要能推理出其后件，则原推理成立。 例1.24：如果A参加球赛，则B或C也将参加球赛。如果B参加球赛，则A不参加球赛。如果D参加球赛，则C不参加球赛。所以，A若参加球赛，则D不参加球赛。 证明：P1∧P2∧…∧Pn →(P → Q) <=> ¬(P1∧P2∧…∧Pn) ∨(¬P ∨ Q) <=> ¬P1 ∨ ¬P2 ∨ … ∨ ¬Pn ∨¬P ∨ Q <=> ¬(P1∧P2∧…∧Pn ∧P) ∨ Q <=> (P1∧P2∧…∧Pn ∧P) → Q 解：设A：A参加球赛；B：B参加球赛；C：C参加球赛；D：D参加球赛。 前提：Ａ→B ∨C，B →¬A，D →¬C；结论： A→¬D。 推理：(1) Ａ→B ∨C 前提引入 (2) A 附加前提引入 (3) B ∨C (1)，(2)假言推理 (4) B →¬A 前提引入 (5) A →¬B (4)置换 (6) ¬B (2)，(5)假言推理 (7) C (3)，(6)析取三段论 (8) D →¬C 前提引入 (9) C →¬D (8)置换 (10) ¬D (7)，(9)析取三段论 (11) A→¬D CP

1.5：命题逻辑的推理理论 例1.25：设前提条件T={P→(Q→S)，¬R∨P，Q},公式G=R →S，证明T|=G。 (4)反证法(归谬法) 定义1.19：设G1，G2，…，Gn是一组命题公式P1，P2，…，Pn是出现在G1，G2，…，Gn中的一切命题变元，I是它的任意解释，若有解释I使G1∧G2∧…∧Gn取值为“真”，则称公式G1，G2，…，Gn是一致的(Consistency)。如对任意的解释I，都有G1∧G2∧…∧Gn取值为“假”，则称公式G1，G2，…，Gn是不一致的(Inconsistency),或者说G1∧G2∧…∧Gn是一个矛盾式。 证明：(1) R 附加前提引入 (2) ¬R∨P 前提引入 (3) ¬ ¬R (1)置换 (4) P (2)，(3)析取三段论 (5) P→(Q→S) 前提引入 (6) Q→S (4)，(5)假言推理 (7) Q 前提引入 (8) S (6)，(7)假言推理 (9) R →S CP

1.5：命题逻辑的推理理论 定理1.10：设命题公式集合{G1，G2，…，Gn}是一致的，于是从前提集合{G1，G2，…，Gn}出发可以逻辑地推出公式H的充要条件是从前提集合{G1，G2，…，Gn，¬H}出发，可以逻辑推出一个矛盾式来。 由定理知： 归谬法：将结论的否定作为附加前提引入，公式序列的最后得到一矛盾式，则原结论成立。 证明：必要性：由于G1，G2，…，Gn|=H ∴G1∧G2∧…∧Gn →H永真， 而G1∧G2∧…∧Gn →H <=> ¬(G1∧G2∧…∧Gn ) ∨H <=> ¬(G1∧G2∧…∧Gn ∧¬H) 即¬(G1∧G2∧…∧Gn ∧¬H)永真， 即G1∧G2∧…∧Gn ∧¬H为矛盾式； 充分性： G1∧G2∧…∧Gn 是矛盾式当且仅当G1∧G2∧…∧Gn |=R ∧¬R 由于G1∧G2∧…∧Gn ∧¬H|= R ∧¬R ∴G1∧G2∧…∧Gn ∧¬H →R ∧¬R永真， 而R ∧¬R是矛盾式， ∴G1，G2，…，Gn ，¬H不一致 即(G1∧G2∧…∧Gn ∧¬H) <=> ¬(¬(G1∧G2∧…∧Gn) ∨H) <=> ¬(G1∧G2∧…∧Gn → H) ∴¬(G1∧G2∧…∧Gn → H)为矛盾式， 即G1∧G2∧…∧Gn →H为永真式， ∴ G1∧G2∧…∧Gn |= H

1.5：命题逻辑的推理理论 例1.26：证明：p →(q ∨r)|=(p →q) ∨(p →r) 例1.27：证明下面论述的有效性：在意甲比赛中，假如有四只球队，其比赛情况如下：如果国际米兰夺冠，则AC米兰或尤文图斯获亚军；若尤文图斯获亚军，国际米兰队部能获得冠军，若拉齐奥队获得亚军，则AC米兰队部能获得亚军；最后，国际米兰夺冠。所以拉齐奥队部能获得亚军 证明：p →(q ∨r)|=(p →q) ∨(p →r) (1) ¬((p →q) ∨(p →r)) 否定结论引入 (2) ¬(p →q) ∧¬ (p →r) (1)置换 (3) ¬(p →q) (2)化简 (4) ¬p ∧q (3)置换 (5) ¬(p →r) (2)化简 (6) p ∧¬r (5)置换 (7) p (6)化简 (8) p →(q ∨r) 前提引入 (9) q ∨r (7)，(8)假言推理 (10) ¬r (6)化简 (11) q (9)，(10)析取三段论 (12) ¬q (4)化简 (13) q ∧¬q (11)，(12)合取引入 ∴推理正确 证明：设P：国际米兰夺冠；Q：AC米兰获得亚军；R：尤文图斯获得亚军；S：拉齐奥获得亚军。 则前提：P →Q ∨R，R → ¬P， S → ¬Q，P；结论： ¬S； 用反证法， (1) ¬ ¬S 否定结论引入 (2) S (1)置换 (3) S → ¬Q 前提引入 (4) ¬Q (2)，(3)假言推理 (5) P →Q ∨R 前提引入 (6) P 前提引入 (7) Q ∨R (5)，(6)假言推理 (8) (Q ∨R) ∧ (¬ Q ∨ ¬ R) (7)置换 (9) Q ∨R (8)化简 (10) R (4)，(9)析取三段论 (11) 　 R → ¬Ｐ 　　 前提引入 (12) ¬P (10)，(11)假言推理 (13) P ∧¬P (6)，(12)合取引入

1.6：命题演算的自然推理形式系统 1.形式系统的基本概念 永真式是命题逻辑推理中一个非常基本的重要概念，为了系统研究它们，就需要把所有的永真式包括在一个系统内，作为一个整体来研究，这样的系统应当是一个形式系统，也只有形式系统，才能进行充分的研究，从而掌握全部规律。 在形式系统中，用符号语言来表达原始概念和用于推演的逻辑规则，决定一切的是符号串和符号串之间的关系，合法符号串的识别，系统内的推演都可以根据合法符号串而形成规则和推理规则(符号串之间的关系)机械的完成；只有这样的系统，才是本质上能做符号变换的计算机可以接受的。

1.6：命题演算的自然推理形式系统 形式系统一般有以下几个部分组成 (1).字母表：由不加定义而采用的符号组成，字母表指此形式系统可以使用的符号； (2).字母表上符号串的一个子集Form：Form中的元素称为公式，Form指此形式系统可以使用的符号串； (3).Form的一个子集是Axiom： Axiom中的元素称为公理， Axiom指此形式系统一开始便接受而不加证明的定理； (4).推理规则系Rule：Rule中的元素称为推理规则，Rule规定了公式间的转换关系。

1.6：命题演算的自然推理形式系统 对于一个形式系统，Axiom和Rule均可以为空，当两者皆为空时，系统仅仅为一个语句生成系统，在数理逻辑中，如果Axiom非空，则称为公理系统，若Axiom为空，则称为自然推理系统。 对于一个具体的实际系统，用形式系统来描述，有两个具体的问题必须解决： (1).可靠性问题：形式系统中正确推理出来的公式，定理在所讨论的具体实际系统中是否为永真； (2).完备性问题：具体实际系统中的永真的语句是否均为形式系统内的定理。

1.6：命题演算的自然推理形式系统 (2)联结词符： ¬， ∧，∨，→，↔； 2.命题演算的自然推理形式系统P 1)字母表： (1)命题符：p，q，r，…，p1，q1，r1， … (2)联结词符： ¬， ∧，∨，→，↔； (3)括号与逗号(，) 2)公式(同前面命题公式的定义) 3)推理规则(用1.5定义的12条规则) 3.可靠性和完备性 (1)可靠性：如果G1，G2，…Gn |=H，则G1∧G2∧…Gn →H永真 (2)完备性：定理1.9。