离散第四章第五章笔记

个体词

研究对象中可以独立存在的具体的或抽象的客体。

例如:

• 小王是三好学生。
• 北京是中国的首都。
• 所有偶数都能被2整除。

1. 表示具体或特定客体的个体词称为个体常项，-般用小写字母...表示;
2. 表示抽象或泛指的个体词称为个体变项，一般用小写字母 ....表示。
3. 个体变项的取值范围称为个体域( 或论域)。个体域可以是有限集合，如{1,2,3}或{a,b,c}，也可以是无限集合，如自然数集合N或实数集合R。
4. 由宇宙间一切事物组成的个体域称为全总个体域。

谓词

用来刻划个体词的性质或个体词之间相互关系的词。

例如:

1. 在命题“2 是无理数”中，“是无理数”是谓词。
2. 在命题“x是有理数”中，“....是有理数”是谓词。
3. 在命题“小王与小李同岁”中，“..与..同岁”是谓词。
4. 在命题“x与y具有关系L”中，与...具有关系L”是谓词。

• 常用大写字母等来表示谓词。
• 表示具体性质或关系的谓词称为谓词常项表示抽象或泛指的性质或关系的谓词称为谓词变项。
• :表示个体常项具有性质 (是谓词常项或变项) ; :表示个体变项具有性质(F同上)

量词

表示数量的词

全称量词:表示所有的

:对个体域中所有的
如，表示个体域中所有的具有性质

表示个体域中所有的和有关系

存在量词:表示存在，至少有一个

:个体域中至少有一一个

如，表示个体域中至少有一个具有性质

符号化命题

1. 分析命题中表示性质和关系的谓词，分别符号化为一元和n元谓词(n≥2)。
2. 根据命题的实际意义选用全称量词或存在量词。
3. 一般来说，多个量词在一起时，其顺序不能随意调换。

合式公式

1. 原子公式是合式公式.
2. 若A是合式公式，则( )也是合式公式
3. 若A，B是合式公式，则也是合式公式
4. 若A是合式公式，则 也是合式公式
5. 只有有限次地应用(1)- -(4)形成的符号串才是合式公式

合式公式简称公式

在公式和 中，称为指导变元，为相应量词的辖域.在和的辖域中的所有出现都称为约束出现，中不是约束出现的其他变项均称为是自由出现的。

设是任意的公式，若中不含自由出现的个体变项，则称为封闭的公式，简称闭式。

基本等值式

置换规则

1. 置换规则

设是含的公式，那么，若，则

2. 换名规则

设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为，则.

3. 代替规则

设为一公式，将中某个个体变项的所有自由出现用中未曾出现过的个体变项符号代替，其余部分不变，设所得公式为，则.

前束范式

谓词逻辑推理定律

命题逻辑推理定律的代换实例

由基本等值式生成的推理定律

• 量词否定等值式
• 量词辖域扩张等值式
• 量词分配等值式

谓词逻辑推理规则

1. 全称量词消去规则
2. 全称量词引入规则
3. 存在量词消去规则
4. 存在量词引入规则