1、 第一篇第一篇 数理逻辑数理逻辑 引言引言 第一章第一章 数理逻辑数理逻辑 第二章第二章 非经典逻辑简介非经典逻辑简介 引言引言：数理逻辑简介：数理逻辑简介1、逻辑学：、逻辑学：研究人的思维（推理）形式的学科。其中的核心研究人的思维（推理）形式的学科。其中的核心内容是推理的有效性。内容是推理的有效性。2、形式逻辑：、形式逻辑：用自然语言研究人的思维（推理）形式。又称语用自然语言研究人的思维（推理）形式。又称语言逻辑，由言逻辑，由 古希腊思想家、哲学家亚里斯多德在古希腊思想家、哲学家亚里斯多德在2300多年前创立，多年前创立，至今仍在不断发展和完善中。至今仍在不断发展和完善中。3、数理逻辑：、数
2、理逻辑：用数学方法研究人的思维（推理）形式，由用数学方法研究人的思维（推理）形式，由17世世纪德国哲学家和数学家莱布尼兹创立。由于数学具有符号化、一义纪德国哲学家和数学家莱布尼兹创立。由于数学具有符号化、一义性两大特征，所以人们常常把数理逻辑称为符号逻辑。性两大特征，所以人们常常把数理逻辑称为符号逻辑。4、数理逻辑在逻辑学中的地位：、数理逻辑在逻辑学中的地位：初等逻辑初等逻辑 命题逻辑命题逻辑 经典逻辑经典逻辑 谓词逻辑（一阶逻辑）谓词逻辑（一阶逻辑）高等逻辑高等逻辑 公理集论公理集论 证明论证明论数理逻辑数理逻辑 递归论递归论 模型论模型论 多值逻辑多值逻辑 非经典逻辑非经典逻辑 模态逻辑模
3、态逻辑 非单调逻辑非单调逻辑 模糊逻辑模糊逻辑 多值逻辑多值逻辑第一章第一章 数理逻辑数理逻辑 1.1 命题及命题联结词命题及命题联结词 1.2 命题公式及命题公式之间的逻辑关系命题公式及命题公式之间的逻辑关系 1.3 谓词与量词谓词与量词 1.4 谓词公式及谓词公式之间的逻辑关系谓词公式及谓词公式之间的逻辑关系 1.5 范式范式 1.6 数理逻辑推理理论数理逻辑推理理论 1.7 数理逻辑推理系统数理逻辑推理系统N 1.8 谓词逻辑推理系统谓词逻辑推理系统NL 1.1 命题及命题联结词命题及命题联结词1.1.1 命题命题 一、定义：具有确定真值的判断称为命题。一、定义：具有确定真值的判断称为命
4、题。二、说明：二、说明：1、命题是逻辑学中的最基本单元。、命题是逻辑学中的最基本单元。2、由命题的定义知，每个命题都具有两个要素，即、由命题的定义知，每个命题都具有两个要素，即 它必是一个陈述句它必是一个陈述句，并且有唯一的真值。，并且有唯一的真值。3、有的判断虽然它的真值，但只要它的真值非、有的判断虽然它的真值，但只要它的真值非0即即1，则它也，则它也是一个命题。是一个命题。三、命题的分类三、命题的分类 1、按命题的真值情况，所有命题可分为真命题和假命题两类。、按命题的真值情况，所有命题可分为真命题和假命题两类。2、按命题的复杂程度，所有命题可分为简单命题和复合命题两类。、按命题的复杂程度，
5、所有命题可分为简单命题和复合命题两类。四、命题符号四、命题符号 本教材中用大写英文字母或大写英文字母加下标来表示简单命题，本教材中用大写英文字母或大写英文字母加下标来表示简单命题，用命题公式来表示复合命题。用命题公式来表示复合命题。1.1.2 命题联结词命题联结词一、定一、定 义义 （1）否定（）否定（）：设）：设P是任意一个命题，是任意一个命题，P的真值为的真值为1当且仅当当且仅当P的真值为的真值为0。（2）合取（）合取（）：设）：设P，Q是任意两个命题，是任意两个命题，PQ的真值为的真值为1当且仅当当且仅当P，Q的的真值都为真值都为1。（3）析取（）析取（）：设）：设P，Q是任意两个命题，
6、是任意两个命题，PQ的真值为的真值为0当且仅当当且仅当P，Q的的真值都为真值都为0。（4）蕴涵（）蕴涵（）：设）：设P，Q是任意两个命题，是任意两个命题，PQ的真值为的真值为0当且仅当当且仅当P的真值的真值为为1，且，且Q的真值为的真值为0。（5）等价（）等价（）：设）：设P，Q是任意两个命题，是任意两个命题，P Q的真值为的真值为1当且仅当当且仅当P的的真值和真值和Q的真值相同。的真值相同。二、联结词的优先级二、联结词的优先级 在同一层次中，各联结词的优先级由高到低依次为：在同一层次中，各联结词的优先级由高到低依次为：，。1.1.3 命题的符号化命题的符号化 例例 将下列命题符号化。将下列命
7、题符号化。（1）两军相遇，勇者胜。）两军相遇，勇者胜。（2）小王很聪明，但是不用功学习，所以他的成绩不好。）小王很聪明，但是不用功学习，所以他的成绩不好。（3）我不能一边吃饭，一边踢球。）我不能一边吃饭，一边踢球。（4）只要我有足够的钱，我就一定会去买一部新手机。只要我有足够的钱，我就一定会去买一部新手机。（5）只有我有足够的钱，我才会去买新手机。）只有我有足够的钱，我才会去买新手机。（6）李芳是否唱歌，完全视王强是否伴奏而定。）李芳是否唱歌，完全视王强是否伴奏而定。解解：（：（1）令令P：两军相遇：两军相遇 Q：勇者胜：勇者胜 则符号化为：则符号化为：PQ （2）令令P：小王很聪明：小王很聪
8、明 Q：小王用功学习：小王用功学习 R：小王的成绩：小王的成绩 好好 则符号化为：则符号化为：P Q R （3）令令P：我正在吃饭：我正在吃饭 Q：我正在踢球：我正在踢球 则符号化为：则符号化为：（PQ）（4）令）令P：我有足够的钱：我有足够的钱 Q：我去买一部新手机：我去买一部新手机 则符号化为：则符号化为：PQ（5）令）令P：我有足够的钱：我有足够的钱 Q：我去买一部新手机：我去买一部新手机 则符号化为：则符号化为：PQ （6）令令P：李芳唱歌：李芳唱歌 Q：王强伴奏：王强伴奏 则符合化为：则符合化为：P Q 例例 设设P表示表示“天下雨天下雨”，Q表示表示“我有空闲时间我有空闲时间”，R
9、表示表示“我去看球我去看球赛赛”。请用自然语言表示下面的复合命题。请用自然语言表示下面的复合命题。（1）Q R （2）Q（P R）（3）PR解：（解：（1）虽然我有空闲时间，但是我还是没有去看球赛。）虽然我有空闲时间，但是我还是没有去看球赛。（2）只要我有空闲时间，那么我去看球赛当且仅当天不下雨。）只要我有空闲时间，那么我去看球赛当且仅当天不下雨。（3）我冒着雨去看球赛。）我冒着雨去看球赛。说明：在符号化一个命题的时候，首先需要将其中的每个简单命题找出来，并分说明：在符号化一个命题的时候，首先需要将其中的每个简单命题找出来，并分别用一个命题符号表示，然后通过分析命题（关键是其中的连词）的含义，
10、选择别用一个命题符号表示，然后通过分析命题（关键是其中的连词）的含义，选择适当的联结词来反映它们的逻辑意义，最终用联结词把各命题符号连接起来，得适当的联结词来反映它们的逻辑意义，最终用联结词把各命题符号连接起来，得到该命题的符号化形式。到该命题的符号化形式。有了联结词和命题符号以后，每个符合数理逻辑语法规范的符号串（即下节所说有了联结词和命题符号以后，每个符合数理逻辑语法规范的符号串（即下节所说的命题公式）就表示了一类结构相同命题。如果进一步指定符号串中每个命题符的命题公式）就表示了一类结构相同命题。如果进一步指定符号串中每个命题符号的含义，则该符号串便成了一个具体的命题。号的含义，则该符号串
11、便成了一个具体的命题。1.2 命题公式及命题公式之间的逻辑关系命题公式及命题公式之间的逻辑关系1.2.1 命题公式命题公式一、构造（递推）式定义一、构造（递推）式定义（1）单个命题符号及）单个命题符号及0，1是命题公式；是命题公式；（2）若）若A是命题公式，则是命题公式，则A也是命题公式；也是命题公式；（3）若）若A，B是命题公式，则是命题公式，则(AB),(AB),(AB),(AB)也是命也是命题公式；题公式；（4）有限次使用）有限次使用(1)(2)(3)(4)所形成的符号串是命题公式。所形成的符号串是命题公式。二、内涵式定义二、内涵式定义 设设$是由命题符号、是由命题符号、0、1、联结词、
12、括号组成的长度有限的符、联结词、括号组成的长度有限的符号串，如果号串，如果$中的每个符号都有意义，则称中的每个符号都有意义，则称$是一个命题公式。是一个命题公式。1.2.2 公式的赋值公式的赋值一、定义：一、定义：设设A是一个含有命题符号是一个含有命题符号P1、P2、Pn的公式，用的公式，用n个确定的真值个确定的真值t1、t2、tn分别赋值给分别赋值给P1、P2、Pn，称为对公式称为对公式A作了一种赋值。作了一种赋值。二、赋值的意义二、赋值的意义 一般情况下，一个命题公式在赋值之前是没有真值的（或者说一般情况下，一个命题公式在赋值之前是没有真值的（或者说是不确定的）。是不确定的）。但是任何一个
13、命题公式作了一种赋值后，就可以求出一个唯一但是任何一个命题公式作了一种赋值后，就可以求出一个唯一的、确定的真值来了。的、确定的真值来了。所以，我们可以通过赋值，来对一个命题公式进行考察。所以，我们可以通过赋值，来对一个命题公式进行考察。三、成真赋值与成假赋值三、成真赋值与成假赋值成真赋值：成真赋值：使命题公式使命题公式A的真值为的真值为1的赋值称为的赋值称为A的一种成真的一种成真赋值。赋值。成假赋值：成假赋值：使命题公式使命题公式A的真值为的真值为0的赋值称为的赋值称为A的一种成假的一种成假赋值。赋值。四、赋值的数目四、赋值的数目定理：定理：设设A是一个含有是一个含有n n种命题符号的公式，则
14、对种命题符号的公式，则对A共有共有2n种种不同的赋值。不同的赋值。本定理利用组合数学中的乘法定理易证。本定理利用组合数学中的乘法定理易证。1.2.3 1.2.3 真值表真值表 对给定的公式对给定的公式A，将，将A在每种赋值下的真值都求出来，然后在每种赋值下的真值都求出来，然后按一定的规范汇列成表，这样得到的表称为公式按一定的规范汇列成表，这样得到的表称为公式A的真值表。的真值表。例例 设有公式设有公式 A=（PQ）P）R），则其真值表见），则其真值表见下表下表。P Q R （PQ）P）R）0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0
15、 0 1 1 1 1 实际中构造一个公式的真值表时，经常把运算的中间结果也放入实际中构造一个公式的真值表时，经常把运算的中间结果也放入表中，如下表。表中，如下表。P Q R PQ P （PQ）P （PQ）P）R）0 0 0 0 1 1 10 0 1 0 1 1 10 1 0 0 1 1 10 1 1 0 1 1 11 0 0 0 0 1 11 0 1 0 0 1 11 1 0 1 0 0 01 1 1 1 0 0 11.2.4 公式的分类公式的分类一、命题公式的分类一、命题公式的分类1、永真式：在任何赋值情况下真值都为、永真式：在任何赋值情况下真值都为1的命题公式。的命题公式。2、永假式：在任
16、何赋值情况下真值都为、永假式：在任何赋值情况下真值都为0的命题公式。的命题公式。3、可满足式：至少有一种成真赋值的命题公式。、可满足式：至少有一种成真赋值的命题公式。二、命题公式之间的逻辑关系二、命题公式之间的逻辑关系1、如果公式、如果公式A是个永真式，则是个永真式，则A必是永假式。必是永假式。2、如果公式、如果公式A是个永假式，则是个永假式，则A必是永真式。必是永真式。3、如果公式、如果公式A是个可满足式，则是个可满足式，则A必不是永假式。必不是永假式。4、如果如果A是永真式，则是永真式，则A必是可满足式。必是可满足式。5、如果、如果A是永假式，是永假式，B是任一公式，则是任一公式，则AB必
17、是永假式，必是永假式，AB必必 是永真式。是永真式。6、如果、如果A是永真式，是永真式，B是任一公式，则是任一公式，则AB必是永真式，必是永真式，BA必是永真式必是永真式1.2.5 命题公式之间的逻辑关系命题公式之间的逻辑关系 一、等值一、等值 1、定义：、定义：设设A、B是命题公式，如果在任何一种赋值下，是命题公式，如果在任何一种赋值下，A、B的真的真值都相同，则称值都相同，则称A等值于等值于B，有时也称，有时也称A与与B是等值的。记作是等值的。记作A B。显然有显然有 A B 当且仅当当且仅当 A B是永真式。是永真式。2、等值的性质、等值的性质 对任意的公式对任意的公式A、B、C，下面的
18、结论都成立。，下面的结论都成立。（1）A A。（自反性）（自反性）（2）若）若A B，则，则B A。（对称性）（对称性）（3）若）若A B，且，且B C，则，则A C。（传递性）（传递性）3 3、基本等值式、基本等值式 设设A A、B B、C C是任意的公式，是任意的公式，1 1表示任意一个永真式，表示任意一个永真式，0 0表示任意一个表示任意一个永假式，则下列等值式成立。永假式，则下列等值式成立。（1 1）A A 双重否定律双重否定律 （2）A AA 等幂律等幂律 A AA（3）AB BA 交换律交换律 AB BA （4）（）（AB）C A（BC）结合律结合律 （AB）C A（BC）（5）A
19、（BC）（AB）（AC）分配律分配律 A（BC）（AB）（AC）（6）（AB）A B 德德摩根律摩根律 （AB）A B（7）A（AB）A 吸收律吸收律 A（AB）A（8）A0 A 同一律同一律 A1 A（9）A0 0 零律零律 A1 1（10）A A 1 排中律排中律（11）A A 0 矛盾律矛盾律（12）AB AB 蕴涵等值式蕴涵等值式（13）A B （AB）（B A）等价等值式等价等值式（14）AB B A 假言易位假言易位（15）（）（AB）（A B）A 归缪律归缪律4、等值式的证明、等值式的证明法一法一 真值表法真值表法 要证明要证明A B，只需证明，只需证明A，B的真值表完全相同即可
20、。的真值表完全相同即可。例例 证明证明(PQ)P Q 证明：作出证明：作出（PQ）和）和 P Q 的真值表如下的真值表如下 P Q PQ (PQ)P Q P Q 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 因为因为(PQ)与与 P Q的真值表完全相同，所以的真值表完全相同，所以(PQ)P Q。法二法二 等值变换法等值变换法 定理：定理：设设A是任意一个公式，是任意一个公式，A1是是A的一个子公式，若将的一个子公式，若将A中的中的 A1 用与之等值的公式用与之等值的公式 A2替换掉，得到的公式记为替换掉，得到的公式记为A/若若A
21、1A2，则，则 A A/。上述定理又称为替换规则，它说明当把上述定理又称为替换规则，它说明当把A中的任何子公式用与中的任何子公式用与之等值的公式替换以后，得到的新公式必等值于之等值的公式替换以后，得到的新公式必等值于A。我们把。我们把“将公将公式式A变换成与之等值的公式变换成与之等值的公式B”称为称为“对对A作了一次等值变换作了一次等值变换”。根据替换规则，要证明等值式根据替换规则，要证明等值式A B，只需要证明公式，只需要证明公式A可以可以通过等值变换变成通过等值变换变成B即可。在变换的过程中，每一步变换都是利用即可。在变换的过程中，每一步变换都是利用一个基本等值式而进行的。一个基本等值式而
22、进行的。例例 证明证明 P（Q R）（PQ）R。证：证：P（Q R）P（QR）（蕴涵等值式）（蕴涵等值式）P（QR）（蕴涵等值式）（蕴涵等值式）（P Q）R （结合律）（结合律）（PQ）R （德（德摩根律）摩根律）（PQ）R （蕴涵等值式）（蕴涵等值式）二、蕴涵二、蕴涵 1、定义：、定义：设设A、B是命题公式，如果在任何一种使是命题公式，如果在任何一种使A真值为真值为1赋值下，赋值下，B的真值都为的真值都为1，则称，则称A蕴涵蕴涵B。记作。记作 A B。显然有显然有 A B 当且仅当当且仅当 A B是永真式。是永真式。2、等值的性质、等值的性质 对任意的公式对任意的公式A、B、C，下面的结论都
23、成立。，下面的结论都成立。（1）A A。（自反性）（自反性）（2）若）若 A B，且，且B C，则，则A C。（传递性）（传递性）3、基本等值式、基本等值式 设设A、B、C是任意的公式，是任意的公式，1表示任意一个永真式，表示任意一个永真式，0表示任意一表示任意一个永假式，则下列蕴涵式成立。个永假式，则下列蕴涵式成立。(1)A AB附加规则附加规则 A BA (2)AB A化简规则化简规则 AB B (3)AB，A B 假言推理规则假言推理规则 (4)AB，A B 析取三段论规则析取三段论规则 AB，B A (5)AB，B A 拒取式规则拒取式规则 (6)AB，BC AC 假言三段论规则假言三
24、段论规则 (7)AB，CD，AC BD 构造性二难推理规则构造性二难推理规则 (8)A，B AB 合取引入规则合取引入规则 1.3 谓词与量词谓词与量词1.3.1 个体个体一、个体一、个体：可以独立存在的对象。：可以独立存在的对象。一般，能用名词来代表的对象都是个体。个体可以是一个具体的一般，能用名词来代表的对象都是个体。个体可以是一个具体的事物，也可以是一个抽象的概念。事物，也可以是一个抽象的概念。二、个体符号二、个体符号：用小写英文字母表示个体。：用小写英文字母表示个体。特别，用特别，用a,b,c,a1,a2,a3,等表示确定的个体，称为个体常元；等表示确定的个体，称为个体常元；用用x,y
25、,z,x1,x2,x3,等表示任何一个个体，称为个体变元。等表示任何一个个体，称为个体变元。三、个体域：三、个体域：个体变元的取值范围称为个体域，用个体变元的取值范围称为个体域，用D D表示。是一个集表示。是一个集合，代表讨论范围内所有事物组成的集合。合，代表讨论范围内所有事物组成的集合。四、全总个体域：四、全总个体域：所有个体组成的集合称为全总个体域，用所有个体组成的集合称为全总个体域，用U U表示。表示。1.3.2 1.3.2 谓词谓词一、谓词：一、谓词：用来刻画个体的性质或个体之间的关系的句子成分。用来刻画个体的性质或个体之间的关系的句子成分。一般，谓词在作为命题的句子中取到谓语的作用。
26、一般，谓词在作为命题的句子中取到谓语的作用。二、谓词符号：用大写英文字母或大写英文字母加下标来表示个体。二、谓词符号：用大写英文字母或大写英文字母加下标来表示个体。如如F,G,H,F 1,F 2,F3,等。等。三、谓词的元数：三、谓词的元数：1、0元谓词：具体的命题称为一元谓词。元谓词：具体的命题称为一元谓词。2、一元谓词：刻画某种性质的谓词称为一元谓词。、一元谓词：刻画某种性质的谓词称为一元谓词。3、n元谓词：刻画元谓词：刻画n（n大于等于大于等于2）个个体之间的关系的谓词称为）个个体之间的关系的谓词称为n元谓词。元谓词。四、命题函数：一个四、命题函数：一个n元谓词总是同元谓词总是同n个个体
27、符号结合起来使用，称为个个体符号结合起来使用，称为命题函数。命题函数。对一个命题函数，如果其中含有对一个命题函数，如果其中含有m种个体变元，则称这个命题函种个体变元，则称这个命题函数是一个数是一个m元命题函数。例如元命题函数。例如F（a，b，c）是一个）是一个0元命题函数，元命题函数，G（x，y）是一个）是一个2元命题函数，元命题函数，H（a，x）是一个）是一个1元命题函数。元命题函数。1.3.3 量词量词 一、量词：刻画对讨论范围（个体域）中的个体下结论的方式。一、量词：刻画对讨论范围（个体域）中的个体下结论的方式。二、两个基本量词二、两个基本量词 1、全称量词：表示、全称量词：表示“对任意
28、的对任意的”、“每个每个”、“所有的所有的”等下结论方式的量词称为全称量词。用符号等下结论方式的量词称为全称量词。用符号“”表示。表示。2、存在量词：表示、存在量词：表示“有的有的”、“至少有一个至少有一个”、“存在存在”等下结论方式的量词称为存在量词。用符号等下结论方式的量词称为存在量词。用符号“”表示。表示。三、量词的作用元三、量词的作用元 一般，单独的量词符号是没有意义的。量词的后面必须紧跟一般，单独的量词符号是没有意义的。量词的后面必须紧跟一个个体变元，这个个体变元称为该量词的作用元。例如一个个体变元，这个个体变元称为该量词的作用元。例如 x中，中，x 是是 的作用元；的作用元；y中，
29、中，y 是是 的作用元。的作用元。四、量词的辖域：即量词的作用范围。四、量词的辖域：即量词的作用范围。1.3.4 命题的符号化命题的符号化 利用谓词逻辑的三类符号个体、谓词、量词，可以将任何利用谓词逻辑的三类符号个体、谓词、量词，可以将任何命题进行符号化。命题进行符号化。在对一个命题符号化时，应注意下列几点：在对一个命题符号化时，应注意下列几点：1.在不同的个体域情况下，同一个命题符号化的结果可能在不同的个体域情况下，同一个命题符号化的结果可能不同。不同。2.若没有指定个体域，则应以全总个体域为个体域进行符若没有指定个体域，则应以全总个体域为个体域进行符号化。号化。3.当个体域中除了命题中所述
30、个体以外，还有其它种类的当个体域中除了命题中所述个体以外，还有其它种类的个体时，必须使用特性谓词。个体时，必须使用特性谓词。4.使用特性谓词后，若量词为全称量词使用特性谓词后，若量词为全称量词“”，则联结词应使用蕴涵，则联结词应使用蕴涵联结词联结词“”；若量词为存在量词若量词为存在量词“”，则联结词应使用合取联结词，则联结词应使用合取联结词“”。5.个体域和谓词的含义确定以后，个体域和谓词的含义确定以后，n元谓词要转化为具体的命题，至元谓词要转化为具体的命题，至少需要少需要n个个量词。量词。6.多个量词同时出现时，各个量词的先后顺序不能随意颠倒。多个量词同时出现时，各个量词的先后顺序不能随意颠
31、倒。例例.（1）尽管有的人很聪明，但未必一切人都很聪明。）尽管有的人很聪明，但未必一切人都很聪明。（2）不管白猫还是黑猫，能抓老鼠的就是好猫。）不管白猫还是黑猫，能抓老鼠的就是好猫。（3）不存在比飞机更快的牛车。）不存在比飞机更快的牛车。解：（解：（1）令）令F（x）：）：x是人是人 G（x）：）：x很聪明很聪明 则符号化为：则符号化为：x（F（x）G（x）x（F （x）G（x）（2）令）令F（x）：）：x是白猫是白猫 G（x）：）：x是黑猫是黑猫 H（x）：）：x能抓老鼠能抓老鼠 I（x）：）：x是好猫是好猫 则符号化为：则符号化为：x（F（x）G（x）H（x）I（x）（3）令）令F（x）：
32、）：x 是牛车是牛车 G（x）：）：x 是飞机是飞机 H（x，y）：）：x比比y快快 则则 x（F（x）y（G（y）H（x，y）1.4 谓词公式及谓词公式之间的逻辑关系谓词公式及谓词公式之间的逻辑关系 1.4.1 谓词逻辑中的合法符号谓词逻辑中的合法符号 一共有如下七类：一共有如下七类：（1）个体常元符号：用带或不带下标的小写英文字母）个体常元符号：用带或不带下标的小写英文字母a,b,c,a1,a2，a3来表示。当个体域来表示。当个体域D给出时，它代表是给出时，它代表是D中某个特定的元素。中某个特定的元素。（2）个体变元符号：用带或不带下标的小写英文字母）个体变元符号：用带或不带下标的小写英文
33、字母x,y,z,x1,x2,x3来表示。当个体域来表示。当个体域D给出时，它可以代表给出时，它可以代表D中任何一个元素。中任何一个元素。（3）函数符号：用带或不带下标的小写英文字母）函数符号：用带或不带下标的小写英文字母f,g,h,f1,f2,f3,来表示。当个体域来表示。当个体域D给出时，给出时，n元函数符号元函数符号f(x1,x2,xn)是一个是一个D的函数。的函数。（4）谓词符号）谓词符号:用带或不带下标的大写英文字母用带或不带下标的大写英文字母F,G,H,F1,F2,F3,来表示。当个体域来表示。当个体域D给出时，给出时，n元谓词符号元谓词符号f(x1,x2,xn)是一个是一个0，10
34、,1的函数。的函数。（5）量词符号：全称量词）量词符号：全称量词，存在量词，存在量词 （6）联结词符号：）联结词符号：，（7）辅助符号：（，），）辅助符号：（，），1.4.2 项项 项的构造性定义如下：项的构造性定义如下：（1）单个个体常元符号，单个个体变元符号都是项；）单个个体常元符号，单个个体变元符号都是项；（2）若）若f(x1,x2,xn)是是n元函数，元函数，t1，t2，tn是项，是项，则则 f(t1，t2，tn )也是项；也是项；（3）仅仅由有限次使用）仅仅由有限次使用(1),(2)产生的符号串才是项。产生的符号串才是项。说明：每个项都是表示一个个体的符号串。说明：每个项都是表示一个
35、个体的符号串。1.4.3 谓词公式谓词公式 谓词公式的构造性定义如下：谓词公式的构造性定义如下：（1 1）若）若F(x1,x2,xn)是是n元谓词，元谓词，t1,t2,tn是项，则是项，则F(t1,t2,tn )是是谓词公式；谓词公式；（2）若）若A，B是谓词公式，则是谓词公式，则 A、A B、A B、AB、AB也是谓词公式；也是谓词公式；（3）若）若A是谓词公式，是谓词公式，x是个体变元符号，则是个体变元符号，则 x A、x A也是谓词公式；也是谓词公式；（4）只有有限次使用只有有限次使用(1)、(2)、(3)产生的符号串才是谓产生的符号串才是谓词公式。词公式。显然，谓词公式中只可能含有显然
36、，谓词公式中只可能含有1.4.1中所列出的符中所列出的符号。号。1.4.4 有关谓词公式的概念有关谓词公式的概念 （1）约束变元：受到量词作用的个体变元。）约束变元：受到量词作用的个体变元。（2）自由变元：未受到量词作用的个体变元。）自由变元：未受到量词作用的个体变元。（3）闭式：不含自由变元的谓词公式。）闭式：不含自由变元的谓词公式。（4）开式：含有自由变元的谓词公式。）开式：含有自由变元的谓词公式。显然，每个个体变元不是约束变元就是自由变元。显然，每个个体变元不是约束变元就是自由变元。同样，每个谓词公式，不是开式就是闭式。同样，每个谓词公式，不是开式就是闭式。1.4.5 谓词公式的解释谓词
37、公式的解释一、定义一、定义对谓词公式对谓词公式G的一种解释由如下四部分组成：的一种解释由如下四部分组成：（1）非空的个体域集合非空的个体域集合D；（2）G中的每个个体常量符号，指定为中的每个个体常量符号，指定为中的某个特定元素；中的某个特定元素；（3）G中的每个中的每个n元函数符号，指定为元函数符号，指定为中的某个特定的中的某个特定的n元函数；元函数；（4）G中的每个中的每个n元谓词符号，指定为元谓词符号，指定为 0，1 中的某个特定的中的某个特定的n n元谓元谓词。词。二、解释的数目二、解释的数目 对任何一个谓词公式，都有无穷多种不同的解释。对任何一个谓词公式，都有无穷多种不同的解释。三、解
38、释的意义三、解释的意义 （1）对谓词公式）对谓词公式G的一种解释，实际上是将的一种解释，实际上是将G中的每个不确定的因中的每个不确定的因素都指定一种确定的含义。素都指定一种确定的含义。（2）任何一个闭式在作了一种解释以后，可以求出唯一的一个真值；）任何一个闭式在作了一种解释以后，可以求出唯一的一个真值；但有的开式无论对其作出何种解释，都得不到确定的真值。但有的开式无论对其作出何种解释，都得不到确定的真值。（3）本教材中，如果不作特殊说明，所提到的谓词公式都指的是闭）本教材中，如果不作特殊说明，所提到的谓词公式都指的是闭式。式。1.4.6 谓词公式的分类谓词公式的分类一、谓词公式的分类一、谓词公
39、式的分类 1、有效公式：在任何解释情况下真值都为、有效公式：在任何解释情况下真值都为1的谓词公式。又可的谓词公式。又可称为永真式。称为永真式。2、矛盾公式：在任何解释情况下真值都为、矛盾公式：在任何解释情况下真值都为0的谓词公式。又可的谓词公式。又可称为永假式。称为永假式。3、可满足公式：至少有一种成真解释的谓词公式。、可满足公式：至少有一种成真解释的谓词公式。二、谓词公式之间的逻辑关系二、谓词公式之间的逻辑关系 1、如果谓词公式、如果谓词公式A是个永真式，则是个永真式，则A必是永假式。必是永假式。2、如果谓词公式、如果谓词公式A是个永假式，则是个永假式，则A必是永真式。必是永真式。3、如果谓
40、词公式、如果谓词公式A是个可满足式，则是个可满足式，则A必不是永假式。必不是永假式。4、如果如果A是永真式，则是永真式，则A必是可满足式。必是可满足式。5、如果、如果A是永假式，是永假式，B是任一谓词公式，则是任一谓词公式，则AB必是永假式，必是永假式，AB必是永真式。必是永真式。6、如果、如果A是永真式，是永真式，B是任一谓词公式，则是任一谓词公式，则AB必是永真式，必是永真式，BA必是永真式。必是永真式。1.4.7 谓词公式之间的逻辑关系谓词公式之间的逻辑关系 一、等值一、等值 1、定义：设、定义：设A，B是两个公式，如果是两个公式，如果AB是有效公式，则称是有效公式，则称A等值于等值于B
41、，记作，记作A B，并称，并称A B是一个等值式。是一个等值式。显然，公式显然，公式A等值于公式等值于公式B的充分必要条件是，在任何一种解的充分必要条件是，在任何一种解释下释下A，B的真值的真值 都是相同的。都是相同的。2、基本等值式、基本等值式 （1）命题逻辑基本等值式的推广命题逻辑基本等值式的推广 利用代入实例的特性（永真的命题公式的任何代入实例都是利用代入实例的特性（永真的命题公式的任何代入实例都是有效公式），有效公式），可以得到一些与可以得到一些与命题逻辑基本等值式结构相同的，谓词逻辑命题逻辑基本等值式结构相同的，谓词逻辑中的基本等值式。中的基本等值式。例如，由例如，由 P P 可推广
42、出可推广出 xF(x)xF(x)，由，由PQ PQ 可推广出可推广出 xF(x)x yG(x，y)xF(x)x yG(x，y)等等等等。（2）谓词逻辑中特有的基本等值式）谓词逻辑中特有的基本等值式 设设A(x)，B(x)都是含自由变元都是含自由变元x的任意的谓词公式，的任意的谓词公式，C是不含作为自由变元在其中出现的任意的谓词公式，则有下列结是不含作为自由变元在其中出现的任意的谓词公式，则有下列结论。论。a.换名规则换名规则 x A(x)yA(y)，其中，其中y不在不在A(x)中出现；中出现；xA(x)yA(y)，其中其中y不在不在A(x)中出现。中出现。b.量词否定律量词否定律 xA(x)x
43、 A(x)x A(x)x A(x)c.量词消去律量词消去律 当个体域当个体域D是有限集合，即是有限集合，即D=a1,a2,an 时，有时，有 xA(x)A（a1）A（a2）A（an）；）；x A(x)A（a1）A（a2）A（an）。）。d.量词分配律量词分配律 x（A(x)B(x)）xA(x)x B(x)；x（A(x)B(x)）xA(x)x B(x)。e.量词辖域的扩张与收缩量词辖域的扩张与收缩 x（A(x)C）xA(x)C；x（A(x)C）xA(x)C；x（A(x)C）xA(x)C；x（C A(x)）C xA(x)；x（A(x)C）xA(x)C；x（A(x)C）xA(x)C；x（A(x)C）
44、xA(x)C；x（C A(x)）C xA(x)。二、二、蕴涵蕴涵 1、定义：、定义：设设A，B是两个谓词公式，如果是两个谓词公式，如果AB是有效公式，是有效公式，则称则称A蕴涵蕴涵B，记，记 作作AB，并称，并称A B是一个蕴涵式。是一个蕴涵式。2、基本等值式、基本等值式 （1）命题逻辑基本蕴涵式的推广命题逻辑基本蕴涵式的推广 利用代入实例的特性（永真利用代入实例的特性（永真的命题公式的任何代入实例都是有效公的命题公式的任何代入实例都是有效公 式），可以得到一些与式），可以得到一些与命命题逻辑基本蕴涵式结构相同的，谓词逻辑中的基本蕴涵式。题逻辑基本蕴涵式结构相同的，谓词逻辑中的基本蕴涵式。例如
45、，由例如，由P Q P 可推广出可推广出 xF（x）yG（y）xF（x）；）；由由P QP Q，P Q可推出可推出 xF（x）x yG（x，y），），xF（x）x yG（x，y）等等。等等。（2）谓词逻辑中特有的基本蕴涵式）谓词逻辑中特有的基本蕴涵式 设设A（x），），B（x）都是含自由变元）都是含自由变元x的任意的谓词公式，则下的任意的谓词公式，则下述结论成立。述结论成立。a.xA（x）x A（x）；）；b.x（A（x）B（x）x A（x）x B（x）；）；c.xA（x）xB（x）x（A（x）B（x）；）；d.x A（x）xB（x）x（A（x）B（x）；）；e.x（A（x）B（x）xA（x）
46、xB（x）；）；f.x（A（x）B（x）x A（x）x B（x）。）。1.5 范式范式1.5.1 主析主析(合合)取范式取范式一、析一、析(合合)取范式取范式 1、简单合、简单合(析析)取式：由单个命题变元或单个命题变元的否定所组取式：由单个命题变元或单个命题变元的否定所组成的合成的合(析析)取式。取式。约定：单个命题变元符号或单个命题变元的否定既是简单合取式，约定：单个命题变元符号或单个命题变元的否定既是简单合取式，也是简单析取式。也是简单析取式。2、析、析(合合)取范式：由有限个简单合取范式：由有限个简单合(析析)取式组成的析取式。取式组成的析取式。约定：单个简单合约定：单个简单合(析析)
47、取式既是析取范式，也是合取范式。取式既是析取范式，也是合取范式。3、析、析(合合)取范式的存在性：对任何一个命题公式，都存在与之等取范式的存在性：对任何一个命题公式，都存在与之等值的析值的析(合合)取范式。但不唯一。取范式。但不唯一。4、析、析(合合)取范式的求法：取范式的求法：事实上，对任何一个命题公式事实上，对任何一个命题公式A，都可以通过下列，都可以通过下列3步，等值步，等值变换成析变换成析(合合)取范式。取范式。第一步：利用蕴涵等值式、等价等值式第一步：利用蕴涵等值式、等价等值式 AB AB A B （AB）（BA）消去消去A中的联结词中的联结词，。第二步：利用德第二步：利用德摩根律摩
48、根律 （AB）A B （AB）A B 将公式中的每个将公式中的每个 移到单个命题变元前。移到单个命题变元前。第三步：适当利用结合律、分配律、交换律、等幂律、吸收律、第三步：适当利用结合律、分配律、交换律、等幂律、吸收律、双重否定律等基双重否定律等基 本等值式，将公式化成析（合）取范式。本等值式，将公式化成析（合）取范式。例例.求命题公式（求命题公式（PQ）R）P的析取范式和合取范式。的析取范式和合取范式。解：（解：（1）求析取范式）求析取范式（PQ）R）P （PQ）R）P 蕴涵等值式蕴涵等值式 （PQ）R）P 蕴涵等值式蕴涵等值式 （P Q）R）P 德德摩根律摩根律 （P Q）R）P 德德摩根
49、律摩根律 （PQ）R）P 德德摩根律摩根律 （PQ）R）P 双重否定律双重否定律 （P R）（Q R）P 分配律分配律 （P R）（Q R）P 结合律结合律（2）求合取范式）求合取范式 前前6步变换同（步变换同（1），有），有（PQ）R）P （PQ）R）P （PQ）P）（RP）分配律分配律 （P（QP）（RP）结合律结合律 （P（PQ）（RP）交换律交换律 （PP）Q）（RP）结合律结合律 （PQ）（RP）等幂律等幂律二、主析（合）取范式二、主析（合）取范式 1、极小（大）项、极小（大）项 （1）定义：设）定义：设G是含有是含有n种命题变元种命题变元P1,P2,Pn的命题公式，若的命题公式，若
50、简单合取式简单合取式m中，命题变元中，命题变元P1,P2,Pn 都在都在m中出现且仅出现一次，中出现且仅出现一次，则称则称m是G的一个极小项；若简单析取式若简单析取式M中，命题变元中，命题变元P1,P2,Pn都在都在M中出现且仅出现一次，则称中出现且仅出现一次，则称M是G的一个极大项。（2）极小（大）项的数目：一个含有）极小（大）项的数目：一个含有n 种命题变元的命题公式共种命题变元的命题公式共有有2n个不同的极小项和个不同的极小项和 2n个不同的极大项。个不同的极大项。（3）极小（大）项的性质）极小（大）项的性质 含含n种命题变元的命题公式种命题变元的命题公式A的极小（大）项有下述性质：的极
