离散数学 面向21世纪课程教材 耿素云 屈婉玲 编著 高等教育出版社

离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用。 学习离散数学的目的在于培养学生的抽象推理、逻辑思维和归拉构造等能力，提高学生利用数学方法解决问题的技能，以及为后续课程作必要的准备，为学生的进一步学习奠定计算机数学的基础。它所涉及的概念、方法和理论，大量地应用在数字电路，编译原理，数据结构，操作系统，数据库，算法等。

第一部分 数理逻辑 第二部分 集合论 第三部分 代数结构 第四部分 图论

第一部分 数理逻辑

1.1.1 命题与联结词 一、基本概念 命题：能够判断真假的陈述句。 真值：命题的真假，只取两个值：真1假0。 能够判断真假 陈述句 例如： 1.1.1 命题与联结词 一、基本概念 命题：能够判断真假的陈述句。 能够判断真假 陈述句 真值：命题的真假，只取两个值：真1假0。 例如： 4是素数。 x大于y。 2009年元旦是晴天。 请不要吸烟！ 我正在说假话。 （是命题） （不是命题） （不是命题，“悖论”）

二、命题的表示 符号化：本书中，命题通常用小写字母或带下标的小写字母表示。完全由符号构成的语言为形式语言。 例如： p：4是素数。 q: 是无理数。 r1：我是一名大学生。

三、原子命题与命题联结词 原子命题（简单命题）：不能被分解为更简单的陈述句的命题。 复合命题：由原子命题通过联结词联结而成的命题。 例如： （1）2和3是素数。 （2）6或8是素数。 复合命题：由原子命题通过联结词联结而成的命题。 常用命题联结词：

Def1.1 否定联结词﹁: ﹁p为真 iff p为假 例： p：我是大学生。 ﹁p：我不是大学生。 P ﹁P 1 Def1.2 合取联结词∧: p∧ q为真 iff p、q 同时为真 （两点注意如书P3页） 例： p：张林是大学生。 q：李响是大学生。 p∧ q：张林和李响都是大学生。 p q p∧ q 1

注：“相容或”和“排斥或” 例1.4： Def1.3 析取联结词∨：p ∨ q为假 iff p、q全为假 （1）张晓静爱唱歌或爱听音乐。 1 注：“相容或”和“排斥或” 例1.4： （1）张晓静爱唱歌或爱听音乐。 （2）张晓静是江西人或安徽人。 （3）张晓静只能挑选202或203房间。

Def1.4 蕴涵联结词→: p → q为假 iff p为真q为假 1 q → p p：蕴涵式的前件 q：蕴涵式的后件 1 注1：“只要p，就q”、”因为p，所以q”、”只有q才p”、 ”除非q才p”、”除非q，否则非p”； 注2：p和q可以无任何关系。(形式蕴涵，实质蕴涵) 注3：蕴涵式前件为假时，蕴涵式为真 见书p5页例1.5

Def1.5 等价联结词 ： p  q为真 iff p和q同真值 1 例：将下列命题符号化，并讨论它们的真值。 （1） 是无理数当且仅当加拿大位于亚洲。 （2）2＋3＝5的充要条件是 是无理数。 （3）若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 （4）当王晓红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。

说明： 多次使用联结词集中的联结词，可以组成更为复杂的复合命题。求复杂命题的真值时，除根据其自身的真值定义外，约定： （1）联结词结合力的强弱次序为 （2）相同的联结词，按从左至右的顺序计算，即先出现者先运算。 见书P7页例1.7

1.1.2 命题公式及其赋值 基本概念 Def1.6 子公式 命题常项 命题常元 命题变项 命题变元 命题公式 （合式公式） 1.1.2 命题公式及其赋值 基本概念 命题常项 命题常元 命题变项 命题变元 命题公式 （合式公式） Def1.6 （1）单个命题变项是合式公式，并称为原子命题公式； （2）如果A是公式，则（﹁A）是公式； （3）如果A、B是公式，则(A∧B)、(A∨B)、(AB)、 (AB)也是合式公式； （4）只有有限次的应用(1) 、(2)、(3)所得到的包括命题 变元、联结词和括号的符号串是合式公式。简称公式。 子公式 P8页3点说明

例： Def1.7 （1）若公式A是单个的命题变项，则称A为0层合式。 （2）称A是n＋1（ ）层公式是指下面情况之一： （a）A＝ ﹁B，B是n层公式； （b）A=B∧C,其中B，C分别为i层和j层公式， 且n＝max(i，j)； （c）A＝B∨C，其中B，C的层次及n同（b）； （d）A＝BC，其中B，C的层次及n同（b）； （e）A＝BC，其中B，C的层次及n同（b）。 （3）若公式A的层次k，则称A是k层公式。 例： （（P∨Q）（∧Q）） （PR∧Q）

命题的翻译 例： （1）小王不但聪明而且用功。 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命题联结词。 例： （1）小王不但聪明而且用功。 （2）虽然天气很冷，老王还是来了。 （3）他一边吃饭一边看电视。 （4）不经一事，不长一智。

（3）上午如果不下雨，我就去看电影；否则，就在家里读书或看报。 解：设p：上午下雨；q：我去看电影；r：我在家里读书；s：我在家里看报。 本例可表示为： （pq）∧（p（r∨s））。 （4）说电影院是拥挤的或者戏院是人们常去的是不对的；而说商店是顾客稀少的或者戏院是令人讨厌的也是不对的。 解：设p：电影院是拥挤的；q：戏院是人们常去的；r：商店是顾客稀少的；s：戏院是令人讨厌的。 本例可表示为： （p∨q）∧ （r∨s）

真值表 Def1.8 设p1，p2，…，pn是出现在命题公式A中的全部命题变项，给p1，p2，…，pn各指定一个真值，称为对A的一个解释或赋值。若指定的一组值使A的真值为1，则称这组值为A的成真赋值，若使A的真值为0，则称这组值为A的成假赋值。 如 思考：含有n个命题变项的公式有多少种不同的赋值？ Def1.9 将命题公式A在所有赋值下取值情况列成表，称作A的真值表。

构造真值表的具体步骤： 例：（1）（ p→q ）∧q （1）找出公式中所含的全体命题变项p1，p2，…，pn ，列出2n个赋值。 （2）按从低到高的顺序写出公式的各个层次。 （3）对应各个赋值计算出各层次的真值，只到最后计算出公式的真值。 例：（1）（ p→q ）∧q p q p→q （ p→q ） （ p→q ）∧q 1

（2） （p∧q）→r p q r p r p∧q （p∧q）→r 1

命题公式的分类 Def1.10 设A为任一命题公式： （1）如果A在所有解释下取值均为真，则称A是永真式或重言式； 如书P10页，表1.3表1.4 P11页例1.9、1.10（哑元）

1.2.1 等 值 式 例： Def2.1 设A和B是两个命题公式，若A、B构成的等值式A↔B为重言式，则称A和B是等值的。记为AB。 1.2.1 等 值 式 Def2.1 设A和B是两个命题公式，若A、B构成的等值式A↔B为重言式，则称A和B是等值的。记为AB。 注：“↔”和“”的区别？ 判断两个公式A与B是否等值的方法：真值表法 例： p q A B A ↔ B 1

常用等价公式(一) （1）双重否定律  AA （2）幂等律 A∨AA ； A∧AA （3）交换律 A∨BB∨A ； A∧BB∧A （4）结合律 （A∨B）∨CA∨（B∨C） （A∧B）∧CA∧（B∧C） （5）分配律 A∨（B∧C）（A∨B）∧（A∨C） A∧（B∨C）（A∧C）∨（B∧C) （6）德·摩根律 （A∨B）A∧B （A∧B）A∨B （7）吸收律 A∨（A∧B）A；A∧（A∨B）A

常用等价公式(二) （8）零律 A∨11 ； A∧00 （9）同一律 A∨0A ； A∧1A （10）排中律 A∨A1 （12）蕴涵等值式 A→BA∨B （13）等价等值式 AB（A→B）∧（B→A） （A∨B）∧（A∨B） （A∧B）∨（A∧B） （14）假言易位 A→BB→A （15）等价否定等值式 ABABBA （16）归缪式 （A→B）∧（A→B）A

等值演算：由已知的等值式推导出另外的一些等值式的过程。 置换规则：设（A）是一个含有子公式A的命题公式，（B）是用公式B置换了（A）中的子公式A后得到的公式，如果AB，那么（A）（B）。 例： 由蕴涵等值式 ： 由置换规则：

等值演算的用途： 一、验证等值式： 例如： 二、判断公式类型： 例如：

三、应用题： 例：在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 听完以上3人的判断后，王教授笑着说，你们3人中有一人说得全对，有一人说得对了一半，另一人说得全不对。试用逻辑演算法分析王教授到底是哪里人？

解：设命题 p：王教授是苏州人。 q：王教授是上海人。 r：王教授是杭州人。 甲的判断：A1＝ p∧q 乙的判断：A2＝p∧q 丙的判断：A3＝ q∧r 可能情况： （1）甲全对，乙对一半，丙全错 F1 （2）甲全对，乙全错，丙对一半 F2 （3）甲对一半，乙全对，丙全错 F3 （4）甲对一半，乙全错，丙全对 F4 （5）甲全错，乙对一半，丙全对 F5 （6）甲全错，乙全队，丙对一半 F6

F1(p∧q)∧((p∧q)∨( p∧q))∧ (q∧r) 0 F2 (p∧q)∧(p∧q)∧((q∧r)∨(q∧r))  p∧q∧ r F3 ((p∧q)∨(p∧q))∧(p∧q)∧(q∧r) 0 F4 ((p∧q)∨(p∧q))∧(p∧q)∧(q∧r) 0 F5 (p∧q)∧((p∧q)∨( p∧q))∧(q∧r) 0 F6 (p∧q)∧(p∧q)∧((q∧r)∨(q∧r)) p∧q∧r 综合以上6种情况： 仅有F2成立，因此王教授是上海人。 甲说的全对，乙说对了一半，丙说得全错。

1.2.2 析取范式与合取范式 Def2.2 命题变项及其否定统称为文字。仅由有限个文字构成的析取式称作简单析取式。仅由有限个文字构成的合取式称为简单合取式。 例： p，q，p∨q，p∨q∨r等为简单析取式 p，q，p∧q，p∧q∧r等为简单合取式 注：一个文字既是简单析取式又是简单合取式 定理2.1 （1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。 （2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。

范式 Def2.3 （1）仅由有限个简单合取式构成的析取式称为析取范式。 （2）仅由有限个简单析取式构成的合取式称为合取范式。 （3）析取范式与合取范式统称为范式。 例：取Ai为简单合取式，A1＝p∧q，A2＝q，A3＝ p∧r 则A＝A1∨A2∨A3＝（p∧q）∨q∨（p∧r）是由A1A2A3构造成的析取范式。 同理：B＝B1∧B2∧B3＝p∧（p∨q）∧（q∨r）是由B1B2B3构造成的合取范式。

性质： 定理2.2 （1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 （2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。 由定义可知，范式有如下特征： （1）不含蕴涵词→和等价词； （2）不含双重否定 ； （3）否定词仅出现在命题变元之前； （4）析取范式是简单合取式的析取， 合取范式是简单析取式的合取。

定理2.3（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。 求给定公式的范式步骤如下： （1）消去联结词→，（公式2.12或2.13 ） （2）否定号的消去（公式2.1或2.6） （3）利用分配率（公式2.5） 例：求公式（p→q）r的析取范式与合取范式。 注：范式不唯一

主范式 Def2.4 在含有n个命题变项p1，p2，…，pn的简单合取范式中，若每个命题变元或其否定不同时存在，但二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位置上（若命题变元无脚标，则按字典顺序排列），这样的简单合取式称为极小项。相应的，满足上述条件的简单析取式称为极大项。 n个命题变项共可产生2n个不同的极小项（极大项），记为mi（Mi）。（见下页图）

极小项 极大项 0 0 m0 M0 0 1 m1 M1 1 0 m2 M2 1 1 m3 M3 公式 成真赋值 名称 成假赋值 p∧q 表2.3 两个命题与变项形成的极小项极大项 极小项 极大项 公式 成真赋值 名称 成假赋值 p∧q 0 0 m0 p∨q M0 p∧q 0 1 m1 p∨q M1 p∧q 1 0 m2 p∨q M2 p∧q 1 1 m3 p∨q M3 含有三个命题变项的极小项与极大项见书P25表2.4

定理2.4 设mi与Mi是命题变项p1，p2，…，pn形成的极小项和极大项，则miMi ，Mimi Def2.5 设G为公式，p1，p2，…，pn为G中的所有命题变元，若G的析取范式(合取范式)中每一个合取项（析取项）都是p1，p2，…，pn的一个极小项（极大项），则称其为G的主析取范式（主合取范式）。 定理2.5 任意的命题公式都存在一个唯一的与之等价的主析取范式和主合取范式。（证明如书）

mm∧（pi∨pi）（ m∧pi）∨（m∧pi） mm∨（pi∧pi）（ m∨pi）∧（m∨pi） 求主范式步骤如下： （1）求G的析取范式（合取范式）G'； （2）若G中某个简单合取式（简单析取式）m中没有出现某个命题变元pi或其否定pi，则将m作如下等价变换： mm∧（pi∨pi）（ m∧pi）∨（m∧pi） mm∨（pi∧pi）（ m∨pi）∧（m∨pi） （3）将重复出现的命题变元、矛盾式和重复出现的极小项（极大项）都消去； （4）重复步骤（2）、（3），直到每一个简单合取式（简单析取式）都为极小项（极大项）；

例：求公式（p→q）r的主析取范式与主合取范式。 解：由析取范式

由合取范式：

p q r （p→q）r 1 结论：含有n个命题变项的公式，若它既不是矛盾式又不是重言式，则它的主析取范式所含极小项的个数与其主合取范式中所含极大项的个数之和为2n个。真值表中为1的行对应极小项的下标；为0的行则对应极大项下标。

例：求公式 的主范式 方法一：真值表法 方法二：等值演算法

主范式的用途： （1）求公式的成真或成假赋值； （2）判断公式的类型； （3）判断两个命题公式是否等价； （4）分析和解决实际问题。 例：某科研所要从3名科技骨干A，B，C中挑选1～2名出国进修。由于工作需要，选派时要满足以下条件： （1）若A去，则C同去； （2）若B去，则C不能同去； （3）若C不去，则A或B可以去。 问：所里应如何选派他们？

解：设p：派A去； q：派B去； r：派C去 由3个已知条件可得： 则： 求上式主析取范式可得： 因此选派方案有3种（a）C去，而A、B不去； （b）B去，A、C不去； （c）A、C同去，B不去。

1.2.3 联结词的完备集 Def2.6 称F：{0,1}n→{0,1}为n元真值函数。 Def2.7设S是一个联结词集合，如果任何n（n 1）元真值函数都可以 由仅含S中的联结词构成的公式表示，则称S是联结词完备集。 定理2.6 S＝{ }是联结词完备集。 Def2.8 设p，q为两个命题，复合命题“p与q的否定式”（“p或q的否定式” ）称作p，q的与非式（或非式），记做p↑q（p ↓ q）。符号↑称作与非联结词（或与联结词）。 p↑q为真当且仅当p与q不同时为真（ p ↓ q 为真当且仅当p与q同时为假）。 定理2.7 {↑}，{↓}都是联结词完备集。

作业：P38习题二 4、（2）（3） 7、（2） 8、（3）

1.3.1 推理的形式结构 推理 Def3.1 设A1、A2……Ak、B都是命题公式，若对于A1、A2……Ak、B中出现的命题变项的任意一组赋值，或者A1∧A2∧……∧Ak为假，或者A1∧A2∧……∧Ak为真时，B也为真，则称由前提A1、A2……Ak推出B的推理是有效的或正确的，并称B是有效的结论。 说明，例3.1如书 定理3.1 命题公式A1、A2……Ak推B的推理正确当且仅当（A1∧A2∧……∧Ak）→B为重言式。 记为： A1∧A2∧……∧Ak B

（1）若a能被4整除，则a能被2整除；a能被4整除，所以a能被2整除。 判断方法： （1）真值表法 （2）等值演算法 （3）主析取范式法 前提： A1，A2，……，Ak 结论： B 例：判断下列推理是否正确 （1）若a能被4整除，则a能被2整除；a能被4整除，所以a能被2整除。 （2）若a能被4整除，则a能被2整除；a能被2整除，所以a能被4整除。 （3）下午马芳或去看电影或去游泳。她没去看电影，所以，她去游泳了。 （4）若下午气温超过30°C，则王晓燕必去游泳。若她去游泳，她就不去看电影了。所以，若王晓燕没去看电影，下午气温必超过了30°C。

基本蕴涵式 （1）A（A∨B）； （2）(A∧B)A； (A∧B)B； （3）(A→B)∧AB； （4）(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.3.2 自然推理系统P Def3.2 如书P48 Def3.3 自然推理系统P定义如下： 1.字母表 2.合式公式 3.推理规则

推理规则 （1）前提引入规则：可以在证明的任何时候引入前提； （2）结论引入规则：在证明的任何时候，已证明的结论都可以作为后续证明的前提； （3）置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。

（4）假言推理规则：A，A→BB； （5）附加规则：AA∨B； （6）化简规则：A，BA； （7）拒取式规则： A→B ，BA； （8）假言三段论规则：A→B，B→CA→C； （9）析取三段论规则： A∨B，BA； （10）构造性二难推理规则： A→B，C→D，A∨C B∨D ； （11）破坏性二难推理规则： A→B，C→D， B∨D A∨C； （12）合取引入规则：P，QP∧Q；

推理常用方法 1、直接证法 直接证法就是根据一组前提，利用前面提供的一些推理规则，根据已知的等价公式和蕴涵式，推演得到有效的结论的方法，即有前提直接推导出结论。

1、直接证法 例 构造下列推理的证明。 （1）前提： 结论： （2）前提： 例 构造下列推理的证明。 （1）前提： 结论： （2）前提： （3）若数a是实数，则它不是有理数就是无理数。若a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数。所以a是无理数。

2．间接证法 间接证法主要有如下两种情况。 （1）附加前提证明法 有时要证明的结论以蕴涵式的形式出现，即推理的形式结构为： （A1∧A2∧…∧An）（A→B） 设（A1∧A2∧…∧An）为S，则上述推理可表示为证明S（A→B），即证明S→（A→B）为永真式。 则可证明： S ∧ AB

例 用附加前提证明法证明下面推理。 前提：p→（q→r），s∨p，q 结论：s→r 证明： （1）s∨p 前提引入规则 例 用附加前提证明法证明下面推理。 前提：p→（q→r），s∨p，q 结论：s→r 证明： （1）s∨p 前提引入规则 （2）s 附加前提引入规则 （3）p （1）（2）析取三段论规则 （4）p→（q→r） 前提引入规则 （5）q→r （3）（4）假言推理规则 （6）q 前提引入规则 （7）r （5）（6）假言推理规则

注：此时命题公式A代表任意命题公式。 （2）归缪法 设A1，A2，…，An是n个命题公式，如果构造形式为（A1∧A2∧…∧An）→B，若将B做为前提能推出矛盾来，如（A∧A ），则说明推理正确。 注：此时命题公式A代表任意命题公式。

例 用归缪法证明 前提：p∨q，p→r，q→s 结论：s∨r 证明 （1）（s∨r） 附加前提引入规则 （2）s∧r （1）置换规则

（8）p∨q 前提引入规则 （9）p （7）（8）析取三段论规则 （10）p→r 前提引入规则 （11）r （9）（10）假言推理规则 （12）r∧r （4）（11）合取引入规则

应用题： 例 一个公安人员审查一件盗窃案，已知下列事实： （1）甲或乙盗窃了电脑； （2）若甲盗窃了电脑，则作案时间不能发生在午夜； （3）若乙的证词正确，则午夜时间屋里灯光未灭； （4）若乙的证词不正确，则作案时间发生在午夜； （5）午夜时屋里灯光灭了。 试问：盗窃电脑的是甲还是乙？

1.4.1 一阶逻辑命题的符号化 例（a）5是质数。 （b）张明生于北京。 （c）7＝3×2。 5 张明 北京 7 3 2 1.4.1 一阶逻辑命题的符号化 1．个体词 ：个体词是指研究对象中不依赖于人的主观而独立存在的具体的或抽象的客观实体 个体常项或个体常元 ： 个体变项或个体变元 ： 个体域或全总个体域 ： 例（a）5是质数。 （b）张明生于北京。 （c）7＝3×2。 5 张明 北京 7 3 2

例（a）5是质数。 A(x)：x是质数 （b）张明生于北京。 B(x,y)：x生于y （c）7＝3×2。 C(x,y,z)：x＝y×z 2．谓词：用来刻画个体词的性质或个体词之间关系的词，一般来说，“x是A”类型的命题可以用A（x）表达。对于 “x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表示“…大于…”谓词。我们把A（x）称为一元谓词，B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。 例（a）5是质数。 （b）张明生于北京。 （c）7＝3×2。 A(x)：x是质数 B(x,y)：x生于y C(x,y,z)：x＝y×z

谓词常项，谓词变项 例 将下列命题在谓词逻辑中符号化，并讨论它们的真值： （1）只有4是素数，8才是素数。 （2）如果2小于3，则8小于7。 例 将下列命题在谓词逻辑中符号化，并讨论它们的真值： （1）只有4是素数，8才是素数。 （2）如果2小于3，则8小于7。 解（1）设谓词G（x）：x是素数，a：4，b：8；（1）中的命题符号化为谓词的蕴涵式： G（b）→G（a） 由于此蕴涵式的前件为假，所以（1）中的命题为真。 （2）设谓词H（x，y）：x小于y，a：2，b：3，c：8，d：7（2）中的命题符号化为谓词的蕴涵式： H（a，b）→H（c，d） 由于此蕴涵式的前件为真，后件为假，所以（2）中的命题为假。

3. 量词 （1）全称量词： “一切的”、“所有的”、“每一个”等可符号化为“”，用x ，y等表示个体域里所有个体，xF(x)，yG(y)分别表示个体域里所有个体都有性质F和都有性质G。 （2）存在量词： “存在”、“有一个”、“至少有一个”等可符号化为“”，用x，y等表示个体域里有的个体，xF(x)，yG(y)分别表示个体域里存在有的个体有性质F和都有性质G。

例 ：在个体域分别限制为（a）和（b）条件时，将下面的命题符号化： （1）所有人都是要死的。 （2）有的人天生就近视。 其中：（a）个体域D1为人类集合。 （b）个体域D2为全总个体域。 解（a）令F（x）：x要死的；G（x）：x天生就近视。 （1）在个体域D1中除人外，没有其他的事物，因而 （1）可符号化为：x F（x） （2）在个体域D1中有些人是天生就近视，因而（2）可符号化为谓词的蕴涵式：x G（x）

（b）在个体域D2中除人外，还有其他的事物，因而在将（1）、（2）符号化时，必须考虑先将人分离出来，令 M（x）：x是人。 在D2中，（1）、（2）可分别描述如下： （1）对于宇宙间的一切事物，如果事物是人，则他是要死的。 （2）在宇宙间存在着天生就近视的人。 将（1）、（2）分别符号化为： （1） x（M（x）F（x）） （2） x（M（x）∧G（x）） 在个体域D1、D2中命题（1）、（2）都是真命题。

说明： 1. 在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。 2. 同一个命题，在不同个体域中的真值也可能不同。 特性谓词 （1）对全称量词，特性谓词作为蕴涵式之前件而加入之。 （2）对存在量词，特性谓词作为合取项而加入之。

例 将下列命题符号化，并指出真值情况。 （1）没有人登上过月球。 （2）所有人的头发未必都是黑色的。 解 个体域为全总个体域，令M（x）：x是人。 （1）令F（x）：x登上过月球。命题（1）符号化为： x（M（x）∧F（x）） 设a是1969年登上月球完成阿波罗计划的一名美国人，则M（a）∧F（a）为真，故命题（1）为假。 （2）令H（x）：x的头发是黑色的。命题（2）可符号化为：x（M（x）H（x）） 我们知道有的人头发是褐色的，所以 x（M（x）H（x））为假，故命题（2）为真。

例 将下列命题符号化。 （1）猫比老鼠跑得快。 （2）有的猫比所有老鼠跑得快。 （3）并不是所有的猫比老鼠跑得快。 （4）不存在跑得同样快的两只猫。 解 设个体域为全总个体域。令C（x）：x是猫；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同样快。 这4个命题分别符号化为： （1）x y（C（x）∧M（y）Q（x，y））； （2）x（C（x）∧y（M（y）Q（x，y）））； （3）x y（C（x）∧M（y）Q（x，y））； （4）x y（C（x）∧C（y）∧L（x，y）））。

注： 1、分析命题中表示性质和关系的谓词，分别符号化为一元和n（n>1）元谓词。 2、根据命题的实际意义选用全称量词或存在量词。 3、一般说来，多个量词出现时，它们的顺序不能随意调换。 4、有些命题的符号化形式可不仅一种。 试符号化“苏格拉底”论证

1.4.2 一阶逻辑公式与解释 定义4.3 设P（x1，x2，…，xn）是n元谓词公式，其中，x1x2，…，xn是个体变项，则称P（x1，x2，…，xn）为谓词演算的原子公式。 定义4.4 谓词演算的合式公式定义如下： （1）原子公式是合式公式； （2）若A是合式公式，则（﹁A）也是合式公式； （3）若A，B是合式公式，则（A∧B）、（A∨B）、（A→B）、（A↔B）是合式公式； （4）若A是合式公式，则x A、x A是合式公式； （5）只有有限次地应用（1）~（4）构成的符号串才是合式公式。

约束变元与自由变元 定义4.5 在公式xA和xA中，称x为指导变元，A为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变元均称为自由出现。 例 指出下列各式量词的辖域及变元的约束情况： （1）x（F（x，y）→ G（x，z）） （2）x（P（x）→y R（x，y）） （3）x（F（x）→ G（y））→ y（H（x）∧M（x，y，z））

定义4.6 设A是任意的公式，若A中不含自由出现的个体变项，则称A是封闭的公式，简称闭式。 定义4.7 解释 书P66例4.8 例：讨论公式P(x)∧xP(x)的真值。 设P(x)仅可解释为（1）A(x):x是质数（2）B(x):x是合数；论述域是{3，4} P(x) x P(x)∧xP(x) A(x) 3 A(x) 4 B(x) 3 B(x) 4 1

定理4.1 封闭的公式在任何解释下都变成命题。 定义4.8 设A为一公式，若A在任何解释下均为真，则称A为永真式。若A在任何解释下均为假，则称A为矛盾式（或永假式）。若至少存在一个解释使A为真，则称A是可满足式。 定义4.9 代换实例 定理4.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。

例 指出下面公式在解释I下的真值。 G=x（P（f（x））∧Q（x，f（a）））； 给出如下的解释I： D={2，3}； a：2； f（2）：3、 f（3）：2； P（2）：0、 P（3）：1； Q（2，2）：1、Q（2，3）：1、Q（3，2）：0、Q（3，3）：1； 解 G = （P（f（2））∧Q（2，f（2）））∨ （P（f（3））∧Q（3，f（2））） = （P（3）∧Q（2，3））∨（P（2）∧Q（3，3）） = （1∧1）∨（0∧1） = 1

1.5.1 一阶逻辑等值式与置换规则 定义2.7 设A、B是一阶逻辑中的任意两个公式，若AB是永真式，则称公式A与B是等值的。记作AB，称AB是等值式。 1.消去量词等值式 设个体域是有限的为：D={ a1，a2，…，an}，则有 （1）xA（x）A（a1）∧A（a2）∧…∧A（an） （2）xA（x）A（a1）∨ A（a2）∨…∨A（an） 2. 量词否定等值公式： （1）﹁x A（x） x﹁A（x） （2）﹁x A（x） x﹁A（x）

3. 量词辖域收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则： （1）x（A（x）∨B） x A（x）∨B x（A（x）∧B） x A（x）∧B x（A（x）→ B） x A（x）→ B x（B→A（x）） B → x A（x） （2）x（A（x）∨B） x A（x）∨B x（A（x）∧B） x A（x）∧B x（A（x）→ B） x A（x）→ B x（B→A（x）） B→x A（x）

三条原则： 置换规则 换名规则 代替规则 4. 量词分配等值式 设A(x)，B(x)是任意的含自由出现个体变项x的公式， 则 （1）x（A（x）∧B（x））x A（x）∧x B（x） （2）x（A（x）∨B（x））x A（x）∨x B（x） 三条原则： 置换规则 换名规则 代替规则 如书P69例

例 证明下列各等价式 （1）﹁x（A（x）∧B（x）） x（A（x）→﹁B（x）） （2）﹁x（A（x）→ B（x）） x（A（x）∧﹁B（x）） 证明 （1）﹁x（A（x）∧B（x））  x ﹁（A（x）∧B（x））  x（﹁A（x）∨﹁B（x））  x（A（x）→﹁B（x）） （2）﹁x（A（x）→ B（x））  x ﹁（A（x）→ B（x））  x ﹁（﹁A（x）∨B（x））  x（A（x）∧﹁B（x））

1.5.2 一阶逻辑前束范式 定义5.2 一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾，则该公式称为前束范式。 定义5.2 一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾，则该公式称为前束范式。 如：x y（F(x)∧G(y)→H(x,y)） x y w t（﹁A（x，y）∨B（w，v，t）） 定理5.3(前束范式存在定理) 任意一个一阶公式都可以化为与它等价的前束范式。

例：求下面公式的前束范式 （1）xF（x）∧xG（x） （2）xF（x）∨xG（x） （3）xF（x，y）→yG（x，y） （4）（x1F（x1，x2）→x2G（x2））→ x1H（x1，x2，x3） 注：前束范式不唯一

1.5.3 一阶逻辑的推理理论 推理定律的几组来源： 第一组：命题逻辑的代换实例； 第二组：由基本等值式生成的推理定律； 第三组：几个重要的推理定律： （1）x A（x）∨x B（x） x（A（x）∨B（x）） （2）x（A（x）∧B（x）） x A（x）∧x B（x） （3）x（A（x）→ B（x）） x A（x）→ x B（x） （4）x（A（x）→ B（x）） x A（x）→ x B（x） （5）x A（x）→ x B（x） x（A（x）→ B（x））

1．全称量词消去规则（简称UI规则） (1)x A（x） A（y） (2)x A（x） A（c） 其中，A是谓词，两式成立的条件： （1）中y为任意不在A（x）中约束出现的个体变元； （2）中c为个体域中的任意一个个体常元。 （3）用y或c去取代A（x）中的自由出现的x时，一定要在x自由出现的一切地方进行取代。

2．全称量词引入规则（简称UG规则） A（y） x A（x） 该式成立条件是： （1）无论A（y）中自由出现的个体变项y取何值，A（y）应该均为真。 （2）取代自由出现的y的x也不能在A（y）中约束出现。

3．存在量词引入规则（简称EG规则） A（c） x A（x） 该式成立的条件是： （1）c为个体域中的个体常元； （2）取代c的x不能在A（c）中出现过。

4．存在量词消去规则（简称EI规则） x A（x） A（c） 该式成立的条件是： （1）c为个体域中使A成立的特定个体常元。 （2）c不在A（x）中出现。 （3）若A（x）中除自由出现的x外，还有其他自由出现的个体变项，此规则不能使用。 只能对前束范式使用以上四条规则

一阶逻辑自然推理系统F： 定义5.3 ：自然推理系统F定义如下： 1.字母表 2.合式公式 3.推理规则： （1）前提引入规则 （2）结论引入规则 （3）置换规则 （4）假言推理规则 （5）附加规则 （6）化简规则 （7）拒取式规则 （8）假言三段论规则 （9）析取三段论规则（10）构造性二难推理规则 （11）合取引入规则 （12）UI规则 （13）UG规则 （14）EG规则 （15）EI规则

例1 在自然推理系统F中，构造下面推理的证明 前提：x（F（x）→G（x））， xF（x） 结论：xG（x） 证明： （1）xF（x） 前提引入规则 （2）F（c） （1）EI （3）x（F（x）→G（x））前提引入规则 （4）F（c）→G（c） （3）UI （5）G（c） （2）（4）假言推理规则 （6）xG（x） （5）EG 思考：如果把（1）（2）与（3）（4）交换？

例2 在自然推理系统F中，构造下面推理的证明 前提：x（F（x）→G（x））, x (F（x）∧H（x）） 结论： x （G（x）∧H（x）） 证明 ： （1） x (F（x）∧H（x））) 前提引入规则 （2） F（c）∧H（c） （1） EI （3） F（c） （2）化简规则 （4） H（c） （2）化简规则 （5） x（F（x）→G（x）） 前提引入规则 （6） F（c）→G（c） （5）UI （7） G（c） （3）（6）假言推理 （8） G（c）∧H（c） （7）（4）合取引入 （9） x （G（x）∧H（x）） （8）EG

例3 证明苏格拉底论证。 设： M（x）：x是一个人。 D（x）：x是要死的。 a：苏格拉底。 论证可符号化为 前提: x（M（x）→ D（x））, M（a） 结论： D（a） 证明 （1）x（M（x）→ D（x）） 前提引入规则 （2）M（a）→ D（a） （1）UI （3）M（a） 前提引入规则 （4）D（a） （2）（3）假言推理规则

例4：构造下列推理的证明： 不存在能表示成分数的无理数，有理数都能表示成分数。因此，有理数都不是无理数。 设： F（x）：x为无理数 G（x）：x为有理数 H（x）：x能表示成分数