第2章 一阶逻辑

《第2章 一阶逻辑》由会员分享，可在线阅读，更多相关《第2章 一阶逻辑（122页珍藏版）》请在金锄头文库上搜索。

1、第第2章章 一阶逻辑一阶逻辑 第第2章章 一阶逻辑一阶逻辑 2.1 一阶逻辑的基本概念一阶逻辑的基本概念 2.2 一阶逻辑公式及解释一阶逻辑公式及解释 2.3 等值演算和前束范式等值演算和前束范式 2.4 一阶逻辑推理理论一阶逻辑推理理论 2.5 例题选解例题选解 习习 题题 二二第第2章章 一阶逻辑一阶逻辑 2.1 一阶逻辑的基本概念一阶逻辑的基本概念 首先我们将简单命题的结构分解成个体和谓词。个体（客体）我们讨论的对象。可以是具体的，也可以是抽象的。个体域（论域）个体所构成的非空集合。全总个体域（无限域）包含宇宙中一切事物的个体域。谓词简单命题中，表示一个个体的性质或多个个体间的关系的词。

2、第第2章章 一阶逻辑一阶逻辑 之所以称之为谓词，是因为谓词和个体词一起构成了简单命题中的主谓结构。如：小王是学生。3是素数。2整除6。2加3等于5。上面这些简单命题中，小王、2、3、5、6均是个体，是学生，是素数，整除，加等于均是谓词。第第2章章 一阶逻辑一阶逻辑 前两个谓词描述的是一个个体的性质，称为一元谓词；第三个表示两个个体之间的关系，称为二元谓词；第四个表示三个个体之间的关系，称为三元谓词。以此类推，我们将描述n（n2）个个体之间关系的谓词称为n元谓词。通常用大写字母F、G、H（可加下标）来表示谓词。第第2章章 一阶逻辑一阶逻辑 F表示是学生； G表示整除； H表示加等于。这时F、G、

3、H表示的是具体的谓词，称为谓词常元，否则，称为谓词变元。显然，单独的一个谓词（即使是谓词常元）并不能构成一个完整的句子，必须以个体词取代方能构成一个句子。第第2章章 一阶逻辑一阶逻辑 通常我们用小写的英文字母a、b、c（可加下标）等表示个体。这样，小王是学生可符号化为F（a），其中a表示小王。若用b表示小李，则F（b）就表示小李是学生。若用c1表示2，用c2表示6，则G（c1，c2）就表示2整除6。这里，a、b、c1、c2均是具体的个体，称为个体常元。一般地，我们用F（x）表示x是学生，其中的x称为个体变元（简称变元，亦称个体词）。类似，我们也可用G（x，y）表示x整除y。第第2章章 一阶逻辑

4、一阶逻辑 我们称由谓词符和变元符组成的符号串为命题函数。之所以称为命题函数，是因为命题函数不是命题，只有谓词为常元并将其中的变元代以具体的个体后，才能构成命题。例如：G（x，y）：x整除y。并不是命题，但若取a：2，b：6，则G（a，a），G（a，b）以及G（b，a）均是命题，前两个是真命题，第三个是假命题。G（a，a）、G（a，b）等称为0元谓词，它们不含个体变元，0元谓词即命题。第第2章章 一阶逻辑一阶逻辑 【例2.1.1】将下列语句形式化为谓词逻辑中的命题或命题函数。（1）小王是二年级大学生。（2）小王是李老师的学生。（3）如果xy且yx，则x=y。解（1）令F（x）：x是大学生；G（x

5、）：x是二年级的；a：小王。则原句形式化为： F（a）G（a）。第第2章章 一阶逻辑一阶逻辑 （2）令F（x，y）：x是y的学生；a：小王；b：李老师。则原句形式化为：F（a，b）。（3）令F（x，y）：xy；G（x，y）：x=y。式化为：（F（x，y）F（y，x）G（x，y）。第第2章章 一阶逻辑一阶逻辑 前两句均是命题，第三句因为含有变元所以是命题函数。但实际上我们知道，只要将x、y限制在数的范围内，第三句是定理，是永真的。这就涉及到了个体域。在简单命题中，常有一些表示数量关系的词语，诸如所有的、有一些等等，用来表示论域中的全体或部分个体，在谓词逻辑中，我们用量词把它们形式化。第第2章章

6、一阶逻辑一阶逻辑 1全称量词“全称量词用来表示个体域中的全体。表自然语言中的所有的、任意的、每一个等等。如：任意偶数均能被2整除。句子可改写成：“在偶数集合中的任意的x，x能被2整除。”取个体域为偶数集，用F（x）表示“x能被2整除”，用x表示“任意的x”，则原句形式化为：xF（x）。第第2章章 一阶逻辑一阶逻辑 2存在量词“存在量词用来表示论域中的部分个体。表自然语言中的存在着一些、至少有一个、有等等。如：我们班有人会吸烟。句子可改写成：在我们班有一些x，x会吸烟。取个体域为“我们班的同学”，用G（x）表示“x会吸烟”，用 x表示有些x，则原句形式化为：xG（x）。第第2章章 一阶逻辑一阶逻

7、辑 【例2.1.2】在全总个体域中形式化下列命题：（1）任意的偶数均能被2整除。（2）我们班有人吸烟。解（1）引入特性谓词H（x）：x是偶数。任意的偶数均能被2整除的涵义是：全总个体域中有子集-偶数集，该子集中的每个元素均具有一种性质，世间万物，只要你属于这个子集，你就必然具有这种性质，所以是蕴含式。特性谓词以蕴含式的前件加入。则原句可形式化为：x（H（x）F（x）第第2章章 一阶逻辑一阶逻辑 （2）引入特性谓词W（x）：x是我们班的人。我们班有人吸烟的涵义可以这样理解：在宇宙间的万物（全总个体域）中，有一个子集-我们班，还有另一个子集-吸烟的人。强调的是既在我们班，又吸烟的的人，所以是两个子

8、集的交集。特性谓词用合取项加入。则原句可形式化为：x（W（x）G（x）第第2章章 一阶逻辑一阶逻辑 【例2.1.3】将下列命题形式化为一阶逻辑中的命题：（1）没有不犯错误的人。（2）人总是要犯错误的。解设M（x）：x是人，F（x）：x犯错误。则原句形式化为：（1）x（M（x）F（x）（2）x（M（x）F（x）第第2章章 一阶逻辑一阶逻辑 【例2.1.4】将下列命题形式化为一阶逻辑中的命题：（1）所有的病人都相信医生。（2）有的病人相信所有的医生。（3）有的病人不相信某些医生。（4）所有的病人都相信某些医生。第第2章章 一阶逻辑一阶逻辑 解设F（x）：x是病人，G（x）：x是医生，H（x，y）：

9、x相信y。（1）本命题的意思是：对于每一个x，如果x是病人，那么对于每一个y，只要y是医生，x就相信y。因此，本命题符号化为：x（ F（ x） y（ G（ y） H（ x，y）或x y（F（x）G（y）H（x，y）第第2章章 一阶逻辑一阶逻辑 （2）本命题的意思是：存在着这样的x，x是病人且对于每一个y，只要y是医生，x就相信y。因此，本命题符号化为：x（F（x）y（G（y）H（x，y）第第2章章 一阶逻辑一阶逻辑 （3）本命题的意思是：存在着这样的x和y，x是病人，y是医生，x不相信y。因此，本命题符号化为：xy（F（x）G（y）H（x，y）或x (F（x）y（G（y）H（x，y）（4）本命

10、题的意思是：对于每个x，如果x是病人，就存在着医生y，使得x相信y。因此，本命题符号化为：x（F（x）y（G（y）H（x，y）)第第2章章 一阶逻辑一阶逻辑 例2.1.5】将下列命题形式化为一阶逻辑中的命题：（1）任意一个整数x，均有另一个整数y，使得x+y等于0。（2）存在这样的实数x，它与任何实数y的乘积均为y。解（1）设Z（x）：x是整数，E（x，y）：x=y，f（x，y）=x+y。则原句形式化为：x（Z（x）y（Z（y）E（f（x，y），0）第第2章章 一阶逻辑一阶逻辑 （2）设R（x）：x是实数，E（x，y）：x=y，g（x，y）=xy。则原句形式化为：x（R（x）y（R（y）E（g

11、（x，y），y）第第2章章 一阶逻辑一阶逻辑 2.2 一阶逻辑公式及解释一阶逻辑公式及解释 上一节中我们在一阶逻辑中符号化得到的命题和命题函数就是一阶逻辑公式(谓词公式)。至此，在一阶逻辑中，我们已涉及到以下这些符号：(1)个体变元符号：用小写的英文字母x，y，z（或加下标）等表示。(2)个体常元符号：用小写的英文字母a，b，c（或加下标）等表示。第第2章章 一阶逻辑一阶逻辑 (3)运算符号：用小写的英文字母f，g，h（或加下标）等表示。(4)谓词符号：用大写的英文字母F，G，H（或加下标）等表示。(5)量词符号：，。(6)联结词符号：，。(7)逗号和圆括号。第第2章章 一阶逻辑一阶逻辑 一个

12、符号化的命题是一串由这些符号所组成的表达式，但并不是任意一个由此类符号组成的表达式就对应于一个命题。所以要给出严格的定义。定义2.2.1项的定义：(1)任何一个个体变元或个体常元是项。(2)如果f是n元运算符，t1，t2，tn是项，则f（t1，t2，tn）是项。(3)所有的项由且仅由有限次使用（1）、（2）所生成。第第2章章 一阶逻辑一阶逻辑 例如，x，a，f（x，a），f（g（x，a，b），h（x）均是项，其中h、f和g分别是一元、二元和三元运算符。而h（a，b）不是项，因为h是一元运算符，但h（a，b）中h的后面跟了两个项，同样g（x）也不是项（理由请读者自己考虑）。第第2章章 一阶逻辑一

13、阶逻辑 定义2.2.2 若F是n元谓词，t1，t2，tn是项，则F（t1，t2，tn）是原子公式。由定义可知，原子命题是不含量词和联结词的谓词公式。同命题逻辑中的情况相似，这里也可以用联结词将原子公式复合成分子公式。（事实上我们已经这样做了。）第第2章章 一阶逻辑一阶逻辑 定义2.2.3 一阶逻辑中的合式公式（wff）的递归定义：（1）原子公式是合式公式。（2）若A 是合式公式，则（ A）也是合式公式。（ 3） 若 A、 G均 是 合 式 公 式 ， 则 （ AB） 、（AB）、（AB）和（AB）也均是合式公式。（4）若F是合式公式，x是个体变元，则xF、xF也是合式公式。（5）只有有限次按规

14、则（1）（4）构成的谓词公式才是合式公式。第第2章章 一阶逻辑一阶逻辑 【例2.2.1】考察下列一阶公式中每个量词的辖域及每个变元的出现是约束的或自由的。（1）x（F（x）yH（x，y）（2）x（F（x）G（x）x（F（x）H（x）（3）xF（x）G（x）第第2章章 一阶逻辑一阶逻辑 解（1）全称量词x的辖域是（F（x）yH（x，y），其中x的两次出现均是约束出现，是约束变元；存在量词y的辖域是H（x，y），其中y的出现是约束的，y是约束变元。（ 2） 第 一 个 全 称 量 词 x的 辖 域 是（F（x）G（x），其中x的出现均是约束出现，是 约 束 变 元 ； 第 二 个 全 称 量 词

15、x的 辖 域 是（F（x）H（x），其中x的出现均是约束出现，是约束变元。第第2章章 一阶逻辑一阶逻辑 （3）唯一的存在量词x的辖域是F（x），其中x的出现是约束出现，是约束变元；而x的第三次出现是在G（x）中的出现，是自由出现，第三个x是自由变元。由例题可见，在一个一阶逻辑公式中，某个个体变元（符）的出现可以既是约束的，又是自由的，如（3）中的x。另外，同一个变元（符）即使都是约束的，也可能是在不同的量词辖域中出现，如（2）中的x。为了避免混淆，可对约束变元进行换名，使得一个变元（符）在一个公式中只以一种形式出现。这样做时需遵守下面的规则：第第2章章 一阶逻辑一阶逻辑 换名规则（1）将量词的

16、作用元及其辖域中所有同符号的变元用一个新的变元符代替。（2）新的变元符是原公式中所没有出现的。（3）用（1）、（2）得到的新公式与原公式等值。第第2章章 一阶逻辑一阶逻辑 【例2.2.2】对公式x（F（x）G（x，y）H（x，y）换名，下面的几种做法中哪个是正确的？（1）z（F（z）G（z，y）H（x，y）（2）y（F（y）G（y，y）H（x，y）（3）z（F（z）G（x，y）H（x，y）第第2章章 一阶逻辑一阶逻辑 解只有（1）是正确的。（2）的换名违反了规则（2），使得G（x，y）中的y的出现改变了性质。（3）的换名违反了规则（1），使得G（x，y）中的x的出现改变了性质。对公式中自由出现

17、的变元也可换符号，称为代替，同样需要遵守下面的规则：代替规则（1）将公式中所有同符号的自由变元符用新的变元符替换。（2）新的变元符是原公式中所没有出现的。（3）用（1）、（2）得到的新公式与原公式等值。第第2章章 一阶逻辑一阶逻辑 【例2.2.3】对公式x（F（x）G（x，y）H（x，y）做代替，下面的几种做法中哪个是正确的？（1）x（F（x）G（x，y）H（z，y）（2）x（F（x）G（x，z）H（u，y）（3）z（F（z）G（x，y）H（y，y）请读者自己做出分析。第第2章章 一阶逻辑一阶逻辑 定义2.2.4 没有自由变元的公式称为闭式。如例2.2.1中的（1）、（2）两式均是闭式，而（3

18、）不是闭式。事实上，仅就个体变元而言，自由变元才是真正的变元，而约束变元只在表面上是变元，实际上并不是真正意义上的变元。换言之，含有自由变元的公式在解释后仍是命题函数，还需赋值方成命题，而不含自由变元的闭式一旦给出解释就成了命题。第第2章章 一阶逻辑一阶逻辑 定义2.2.5 一个解释I由以下四部分组成：（1）为个体域指定一个非空集合DI。（2）为每个个体常元指定一个个体。（3）为每个n元运算符指定DI上的一个n元运算。（4）为每个n元谓词符指定DI上的一个n元谓词。第第2章章 一阶逻辑一阶逻辑 【例2.2.4】 设f，g均为二元运算符，E，L均为二元谓词符，给定解释I如下：个体域DI为自然数集

19、合；f（x，y）=x+y，g（x，y）=xy，a=0；E（x，y）：x=y，L（x，y）：xy。求下列公式在解释I下的真值。第第2章章 一阶逻辑一阶逻辑 （1）xyL（x，y）（2）x（E（f（x，a），x）L（g（x，a），a）（3）y（E（x，y）L（x，y）（4）E（f（x，a），g（x，a）第第2章章 一阶逻辑一阶逻辑 解(1)式中没有自由变元，是闭式，在解释I下的意义是：对于每一个自然数x，均存在着自然数y，使得xy。显然这是一个真命题。（2）式中也没有自由变元，是闭式，在解释I下的意义是：对于每一个自然数x，x+0=x并且x00。00不真，所以这是一个假命题。（3）式中x是自由变元

20、，不是闭式，在解释I下的意义是：对于每一个自然数y，x=y或者xy。因为x取0时，原式为真；x取1时，原式为假，所以这是命题函数，而非命题。第第2章章 一阶逻辑一阶逻辑 （4）式中x是自由变元，不是闭式，在解释I下的意义是：x+0=x0。因为x取0时，原式为真；x非0时，原式为假，所以这是命题函数，而非命题。如上所言，含有自由变元的公式在解释后仍是命题函数，还需赋值方成命题。第第2章章 一阶逻辑一阶逻辑 定义2.2.6赋值是建立在解释I上的函数，且有：（1）（xi）= ，即对自由变元xi指派一个DI中的个体 。（2）（f（t1，t2，tn）=（t1），（t2），（tn），其中fi是I对f的解释

21、，ti（i=1，2，n）是项。第第2章章 一阶逻辑一阶逻辑 【例2.2.5】设f，g均为二元运算符，E，L均为二元谓词符，给定解释I及赋值如下：个体域DI为自然数集合；f（x，y）=x+y，g（x，y）=xy，a=0；E（x，y）：x=y，L（x，y）：xy。1（x）=0，2（x）=1。求下列公式在解释I和赋值分别为1，2下的真值。第第2章章 一阶逻辑一阶逻辑 （1）y（E（x，y）L（x，y）（2）E（f（x，a），g（x，a）（3）xE（g（x，a），a）第第2章章 一阶逻辑一阶逻辑 解(1)式在解释I及赋值1下的含义是：对于每个自然数y，0=y或者0y。即0是最小的自然数，这是真命题。在

22、解释I及赋值2下的含义是：对于每个自然数y，1=y或者1y。即1是最小的自然数，这是假命题。(2)式在解释I及赋值1下的含义是：0+0=00，这是真命题。在解释I及赋值2下的含义是：1+0=10，这是假命题。第第2章章 一阶逻辑一阶逻辑 (3)式中不含自由变元，无需考虑赋值。在解释I下的意义是：对于每一个自然数x，x0=0。这是真命题。在上一节我们曾提到过，当个体域为有穷集DI=a1，a2，an时：xF（x）F（a1）F（a2）F（an）xG（x）G（a1）G（a2）G（an）因此，当解释I中的个体域D为有穷集时，可先消量词再求真值。第第2章章 一阶逻辑一阶逻辑 【例2.2.6】 设解释I为：

23、DI=2，3，f（2）=3，f（3）=2，F（2，2）=F（2，3）=0，F（3，2）=F（3，3）=1。在I下消去下列公式的量词并求真值。（1）F（2，f（2）F（3，f（3）（2）xyF（y，x）（3）x（F（x，f（x）yF（f（x），f（y）第第2章章 一阶逻辑一阶逻辑 解（1）式中不含量词，所以直接求真值。F（2，f（2）F（3，f（3）F（2，3）F（3，2）010第第2章章 一阶逻辑一阶逻辑 (2)xyF（y，x）x（F（2，x）F（3，x）（F（2，2）F（3，2）（F（2，3）F（3，3）（01）（01）111第第2章章 一阶逻辑一阶逻辑 (3)x（F（x，f（x）yF（f（

24、x），f（y）（F（2,f（2）yF（f（2）,f（y）（F（3,f（3）yF（f（3）,f（y）（F（2,f（2）（F（f（2）,f（2）F（f（2）,f（3）（F（3,f（3）（F（f（3）,f（2）F（f（3）,f（3）（F（2,3）（F（3,3）F（3,2）（F（3,2）（F（2,3）F（2,2）（0（11）（1（00）（01）（10）100第第2章章 一阶逻辑一阶逻辑 定义2.2.7一阶逻辑公式的分类：永真式（逻辑有效式）在任何解释I及I的任何赋值下均为真的一阶公式；永假式（矛盾式）在任何解释I及I的任何赋值下均为假的一阶公式；可满足式至少有一种解释和一种赋值使其为真的一阶公式。第第

25、2章章 一阶逻辑一阶逻辑 由定义可知，要判定一个公式A不是永真式，只需找到一个解释I和I下的一个赋值，使A在I和下为假；要判定一个公式A不是永假式，只需找到一个解释I和I下的一个赋值，使A在I和下为真；要判定一个公式A是可满足式，只需找到一个解释I和I下的一个赋值，使A在I和下为真，再找到一个解释I和I下的一个赋值，使A在I和下为假。第第2章章 一阶逻辑一阶逻辑 【例2.2.7】讨论下列公式的类型：（1）xF（x）xF（x）（2）x G（x）xG（x）（3）xyF（x，y）y xF（x，y）第第2章章 一阶逻辑一阶逻辑 解（1）公式xF（x）xF（x）在任何解释I下的含义是：如果个体域DI中的

26、每个元素x均有性质F，则DI中的某些元素x必有性质F。前件xF（x）为真时，后件xF（x）永远为真，所以公式xF（x）xF（x）是永真式。第第2章章 一阶逻辑一阶逻辑 （2）公式x G（x）xG（x）在任何解释I下的含义是：个体域DI中的每个元素x均不具有性质G，且DI中的某些元素x具有性质G。这是两个互相矛盾的命题，不可能同时成立，所以公式 xG（x）xG（x）是永假式。第第2章章 一阶逻辑一阶逻辑 （3）公式xyF（x，y）yxF（x，y）既不是永真式，也不是永假式。由于这是闭式，故无需考虑赋值，只要给出一个使其成真的解释和一个使其成假的解释即可。给定解释I1：DI1为自然数集，F（x，y

27、）：xy。此时公式的前件xyF（x，y）表示“对于每个自然数x，均有自然数y比x大”是真命题，而后件y xF（x，y）表示“存在着自然数y比每个自然数x均大”是假命题。因此，I1是使xyF（x，y）y xF（x，y）为假的解释。第第2章章 一阶逻辑一阶逻辑 给定解释I2：DI2为自然数集，F（x，y）：xy。此时公式的前件xyF（x，y）表示“对于每个自然数x，均有自然数y比x小”是假命题（x为0时，y不存在），因此，I2是使xyF（x，y）y xF（x，y）为真的解释。第第2章章 一阶逻辑一阶逻辑 定义2.2.8设A（p1，p2，pn）是含命题变元p1，p2，pn的命题公式，B（B1，B2,

28、，Bn）是以一阶公式B1，B2,，Bn分别代替p1，p2,，pn在A中的所有出现后得到的一阶公式，称B是A的一个代换实例。例如，F（x）G（y），xF（x）yG（y）均是命题公式pq的代换实例，也是p的代换实例。显然有以下定理。第第2章章 一阶逻辑一阶逻辑 定理2.2.1命题逻辑永真式的任何代换实例必是一阶逻辑的永真式。同样，命题逻辑永假式的任何代换实例必是一阶逻辑的永假式。证明略。定理2.2.1为我们提供了一大类一阶逻辑的有效式。因此，判断一个一阶逻辑公式是否是永真式或永假式，我们既可以用定义2.2.7（如例2.2.7），也可以用其是否是命题逻辑的永真式或永假式的代换实例来判断。第第2章章

29、一阶逻辑一阶逻辑 2.3 等值演算和前束范式等值演算和前束范式 定义2.3.1设A与B是公式，若AB是永真式，则称A与B等值，或称A与B逻辑等价，记作AB。第第2章章 一阶逻辑一阶逻辑 显然，AB当且仅当在任何解释I和I中的任意赋值下，A与B有相同的真值。即在I和下，A为真当且仅当B为真，或者，A为假当且仅当B为假。同时，要证明两个公式不等值，只需找到一个解释I和I中的一个赋值，使得两个公式在I和下，一个为真，另一个为假。第第2章章 一阶逻辑一阶逻辑 【例2.3.1】判断公式F（x）和F（y）是否等值。解F（x）表示x具有性质F，F（y）表示y具有性质F，容易看出两个意思并不一样。取解释I：个

30、体域D为整数集，F（x）：x是奇数，赋值（x）=1，（y）=2，则在I和下，F（x）为真，F（y）为假。因此，F（x）与F（y）不等值。第第2章章 一阶逻辑一阶逻辑 【例2.3.2】判断公式xyF（x,y）与公式y xF（x，y）是否等值。解直接观察是不等值的。由于两个公式均是闭式，所以只需给出一个解释I，使其在I下一个为真，另一个为假。取解释I：D为鞋子的集合，F（x，y）：x与y能配成一双。则在I下，xyF（x,y）表示“每一只鞋子均有另一只鞋子能与其配成一双”是真命题，而公式y xF（x，y）表示“有这样的鞋子能与任何一只鞋子配成一双”是假命题。因此，两个公式xyF（x,y）与y xF（

31、x，y）不等值。第第2章章 一阶逻辑一阶逻辑 量词转换律（A（x）是任一一阶公式） xA（x）xA（x） （1）xA（x）xA（x） （2）第第2章章 一阶逻辑一阶逻辑 量词辖域扩缩律（A（x）是任一一阶公式，B是任一不含x的一阶公式）xA（x）Bx（A（x）B） （1）xA（x）Bx（A（x）B） （2）xA（x）Bx（A（x）B） （3）xA（x）Bx（A（x）B） （4）第第2章章 一阶逻辑一阶逻辑 证明（1）在任何解释I和I中的任意赋值下， xA（x）B=1当且仅当xA（x）=1且B=1当且仅当B=1且对于DI中的每一个元素c，A（c）=1当且仅当对于DI中的每一个元素c，A（c）B=

32、1当且仅当x（A（x）B）=1第第2章章 一阶逻辑一阶逻辑 （2）在任何解释I和I中的任意赋值下，xA（x）B=0当且仅当xA（x）=0且B=0当且仅当B=0且存在DI中的元素c，使得A（c）=0当且仅当存在DI中的元素c，使得A（c）B=0当且仅当x（A（x）B）=0第第2章章 一阶逻辑一阶逻辑 第第2章章 一阶逻辑一阶逻辑 （4）式的证明留给读者。另外，下面的等值式也称作量词辖域的扩缩律。第第2章章 一阶逻辑一阶逻辑 证明（5）（6）、（7）、（8）的证明留给读者。第第2章章 一阶逻辑一阶逻辑 量词分配律A（x）、B（x）是任一一阶公式）第第2章章 一阶逻辑一阶逻辑 证明（1）在任何解释I

33、和I中的任意赋值下， x（A（x）B（x）=1当且仅当对于DI中的每一个元素c，A（c）B（c）=1当且仅当对于DI中的每一个元素c，A（c）=1且B（c）=1当且仅当xA（x）=1且xB（x）=1当且仅当xA（x）xB（x）=1第第2章章 一阶逻辑一阶逻辑 第第2章章 一阶逻辑一阶逻辑 【例2.3.3】证明下列等值式:第第2章章 一阶逻辑一阶逻辑 证明第第2章章 一阶逻辑一阶逻辑 定义2.3.2设A为一阶公式，若A具有如下形式 Q1x1Q2x2QkxkB则称A为前束范式。其中Qi（1ik）是量词符或，xi（1ik）是变元符，B是不含量词的公式。第第2章章 一阶逻辑一阶逻辑 在一阶逻辑推理中，

34、需要将公式化成前束范式形式，这总是可以办到的。即任何一个一阶公式均可等值演算成前束范式，化归过程如下：（1）消去除、之外的联结词；（2）将否定符移到量词符后；（3）换名使各变元不同名；（4）扩大辖域使所有量词处在最前面。第第2章章 一阶逻辑一阶逻辑 【例2.3.4】将下面公式化成前束范式。第第2章章 一阶逻辑一阶逻辑 解第第2章章 一阶逻辑一阶逻辑 第第2章章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论一阶逻辑推理理论 在一阶逻辑中，由前提A1，A2，An推出结论B的形式结构仍然是A1A2AnB。如果此式是永真式，则称由前提A1，A2，An推出结论B的推理正确，记作A1A2AnB或者A1，A2

35、，AnB，否则称推理不正确。第第2章章 一阶逻辑一阶逻辑 由于谓词演算是在命题演算的基础上，进一步扩大了谓词与量词的功能，因此容易想到，命题演算中有关推理演绎的规则基本上适用于谓词演算，即在命题逻辑中的各项推理规则在一阶逻辑推理中仍然适用，当然也会有不少只适用于谓词演算的概念与规则。全称量词消去规则（简称UI规则）第第2章章 一阶逻辑一阶逻辑 规则成立的条件：（1）t是任意个体变项或常项。（2）A（t）中约束变元个数与A（x）中约束变元个数相同。第第2章章 一阶逻辑一阶逻辑 全称量词引入规则（简称UG规则）规则成立的条件：（1）A（t）在任何解释I及I中对t的任何赋值下均为真。（2）x不在A（

36、t）中约束出现。第第2章章 一阶逻辑一阶逻辑 存在量词引入规则（简称EG规则）规则成立的条件：（1）c是特定的个体常元。（2）x不在A（c）中出现。第第2章章 一阶逻辑一阶逻辑 规则成立的条件：（1）c是使A（c）为真的特定的个体常元。（2）xA（x）是闭式，且c不在A（x）中出现。特别需要注意的是，使用这些规则的条件非常重要，如在使用过程中违反了这些条件就可能导致错误的结论。存在量词消去规则（简称EI规则）第第2章章 一阶逻辑一阶逻辑 【例2.4.1】证明推理所有的自然数均是实数，3是自然数，因此，3是实数。正确。解设N（x）：x是自然数，R（x）：x是实数，则推理形式化为： x（N（x）R

37、（x），N（3）R（3）下面进行证明。（1）x（N（x）R（x）前提引入（2）N（3）R（3）（1）UI（3）N（3）前提引入（4）R（3）（2）（3）假言推理第第2章章 一阶逻辑一阶逻辑 【例2.4.2】构造下面推理的证明：前提x（F（x）（G（x）H（x），x（F（x）P（x）结论x（P（x）H（x）第第2章章 一阶逻辑一阶逻辑 解（1）x（F（x）（G（x）H（x）前提引入（2）x（F（x）P（x）前提引入（3）F（c）P（c）(2)EI（4）F（c）（G（c）H（c）（1）UI（5）F（c）（3）化简（6）G（c）H（c）（4）（5）假言推理（7）P（c）（3）化简（8）H（c）（6）

38、化简（9）P（c）H（c）（7）（8）合取引入（10）x（P（x）H（x）（9）EG第第2章章 一阶逻辑一阶逻辑 【例2.4.3】设前提为xyF（x，y），下面推理是否正确？（1）xyF（x，y）前提引入（2）yF（y，y）（1）UI解xyF（x，y）yF（y，y）的推理并不正确。如果给定解释I：个体域为实数集，F（x，y）：xy。则xyF（x，y）意为对于每个实数x，均存在着比之更小的实数y，这是一个真命题。而yF（y，y）意为存在着比自己小的实数，是假命题。之所以出现这样的错误，是违反了UI规则成立的条件（2）。第第2章章 一阶逻辑一阶逻辑 【例2.4.4】设前提为xyF（x，y），下面推

39、理是否正确？（1）xyF（x，y）前提引入（2）yF（t，y）（1）UI（3）F（t，c）（2）EI（4）xF（x，c）（3）UG（5）yxF（x，y）（4）EG第第2章章 一阶逻辑一阶逻辑 解xyF（x，y）yxF（x，y）的推理并不正确。取与例2.4.3相同的解释，则由xyF（x，y）为真，而yxF（x，y）意为存在着最小实数，是假命题，知推理不正确。之所以出现这样的错误，是第（3）步违反了EI规则成立的条件（2）。第第2章章 一阶逻辑一阶逻辑 【例2.4.5】构造下面推理的证明：前提x（F（x）G（x）结论xF（x）xG（x）分析本题直接证明很困难，注意到结论部分是蕴涵式，应考虑用附加前

40、提证明法。第第2章章 一阶逻辑一阶逻辑 证明（1）x（F（x）G（x）前提引入（2）xF（x）附加前提引入（3）F（t）（2）UI（4）F（t）G（t）（3）UI（5）G（t）（3）（4）假言推理（6）xG（x）（5）UG（7）xF（x）xG（x）CP第第2章章 一阶逻辑一阶逻辑 【例2.4.6】构造下面推理的证明：前提x（F（x）G（x）结论x（y（F（y）H（x，y）z（G（z）H（x，z）分析本题直接证明会感到无从下手，而由于结论并非蕴涵式（x的辖域是其后整个公式），附加证明法也不适用，此时我们应考虑归缪法。第第2章章 一阶逻辑一阶逻辑 证明（1）x（y（F（y）H（x，y）z（G（z）

41、H（x，z）否定结论引入（2）x（y（F（y）H（x，y）z（G（z）H（x，z）（1）置换第第2章章 一阶逻辑一阶逻辑 （3）（y（F（y）H（a，y）z（G（z）H（a，z）（2）EI（4）y（F（y）H（a，y）z（G（z）H（a，z）（3）置换第第2章章 一阶逻辑一阶逻辑 （5）y（F（y）H（a，y）（4）化简（6）F（b）H（a，b）（5）EI（7）F（b）（6）化简（8）x（F（x）G（x）前提引入（9）F（b）G（b）（8）UI（10）G（b）（7）（9）假言推理（11）z（G（z）H（a，z）（3）化简第第2章章 一阶逻辑一阶逻辑 （12）z（G（z）H（a，z）（11）置换

42、（13）G（b）H（a，b）（12）UI（14）H（a，b）（6）化简（15）H（a，b）（14）置换（16）G（b）（13）（15）析取三段论（17）G（b）G（b）（10）（16）合取引入第第2章章 一阶逻辑一阶逻辑 2.5 例题选解例题选解 【例2.5.1】在高等数学中极限定义为：任给小正数，则存在正数，使得当0|x-a|时，恒有|f（x）-b|成立。将上述定义用一阶逻辑公式表示。第第2章章 一阶逻辑一阶逻辑 分析因为高等数学中的极限概念是在实数范围内给出的，所以不妨设定个体域为实数域。观察整个定义，只有一种“小于”关系，这应当用一个二元谓词表示；而“差的绝对值”是一个运算，应当用运算符

43、表示。解设L（x，y）：xy，g（x，y）：|x-y|，则定义可表示为：（L（0，）（L（0，）x（L（0，g（x，a）L（g（x，a），） L（g（f（x），b），）第第2章章 一阶逻辑一阶逻辑 【例2.5.2】在一阶逻辑中符号化自然数的三条公理。（1）每个数都有唯一的一个数是它的后继数。（2）没有一个数使0为它的后继数。（3）每个不等于0的数都有唯一的一个数是它的直接先行者。分析在符号化命题的过程中，设定谓词尽可能少是一个原则。注意到x是y的后继数与y是x的直接先行者含义相同，所以可用一个谓词表示。第第2章章 一阶逻辑一阶逻辑 解设N（x）：x是自然数，F（x，y）：x是y的后继数，G（x

44、，y）：x=y，则（1）x（N（x）!y（N（y）F（y，x）（2）x（N（x）F（0，x）（3）x（N（x）G（x，1）!y（N（y）F（x，y）第第2章章 一阶逻辑一阶逻辑 【例2.5.3】将符号!xF（x）表达成仅用量词和的形式。分析!xF（x）的意思是：有唯一的x具有性质F。即有x具有性质F，且若还有y也具有性质F，则必有x=y。解!xF（x）x（F（x）y（F（y）x=y）第第2章章 一阶逻辑一阶逻辑 【例2.5.4】设个体域为a，b，c，消去下列公式中的量词。（1）xF（x）yG（y）（2）xy（F（x）G（y）（3）xy（F（x，y）G（y）第第2章章 一阶逻辑一阶逻辑 解（1）

45、xF（x）yG（y）（F（a）F（b）F（c）（F（a）F（b）F（c）（2）xy（F（x）G（y）y（F（a）G（y）y（F（b）G（y）y（F（c）G（y）（F（a）G（a）（F（a）G（b）（F（a）G（c）（F（b）G（a）（F（b）G（b）（F（b）G（c）（F（c）G（a）（F（c）G（b）（F（c）G（c）第第2章章 一阶逻辑一阶逻辑 （3）xy（F（x，y）G（y） y（ F（ a， y） G（ y） ） y（ F（ b， y） G（ y） ） y（ F（c，y）G（y）（F（a，a）G（a）（F（a，b）G（b）（F（a，c）G（c）（F（b，a）G（a）（F（b，b）G（b

46、）（F（b，c）G（c）（F（b，a）G（a）（F（b，b）G（b）（F（b，c）G（c）第第2章章 一阶逻辑一阶逻辑 【例2.5.5】构造下面推理的证明：前提xF（x）xG（x）结论x（F（x）G（x）证明（1）xF（x）xG（x）前提引入（2）x y（F（x）G（y）（1）置换（3）y（F（t）G（y）（2）UI（4）F（t）G（t）（3）UI（5）x（F（x）G（x）（4）UG第第2章章 一阶逻辑一阶逻辑 习习 题题 二二 1在一阶逻辑中将下列命题符号化。（1）天下乌鸦一般黑。（2）没有不散的筵席。（3）闪光的未必是金子。（4）有不是奇数的素数。（5）有且仅有一个偶素数。（6）猫是动物，

47、但并非所有的动物都是猫。第第2章章 一阶逻辑一阶逻辑 （7）骆驼都比马大。（8）有的骆驼比所有的马都大。（9）所有的骆驼都比某些马大。（10）有的骆驼比某些马大。第第2章章 一阶逻辑一阶逻辑 2取个体域为实数集R， 函数f在点a处连续的定义是：f在a点连续，当且仅当对每一个小正数，都存在正数，使得对所有的x，若|x-a|，则|f（x）-f（a）|。把上述定义用符号的形式表示。3在整数集中，确定下列命题的真值，运算是普通乘法。（1）xy（xy=0）（2）xy（xy=1）（3）y x（xy=1）（4）y x（xy=x）第第2章章 一阶逻辑一阶逻辑 4给定谓词如下，试将下列命题译成自然语言。P（x）

48、：x是素数。E（x）：x是偶数。O（x）：x是奇数。D（x，y）：x整除y。（1）E（2）P（2）（2）x（D（2，x）E（x）（3）x（E（x）D（x，6）（4）x（E（x）D（2，x）第第2章章 一阶逻辑一阶逻辑 （5）x（E（x）y（D（x，y）E（y）（6）x（O（x）y（P（y）D（x，y）（7）x（P（x）y（E（y）D（x，y）（8）x（E（x）P（x）y（E（y）P（y）xy）第第2章章 一阶逻辑一阶逻辑 5指出下面公式中的变量是约束的，还是自由的，并指出量词的辖域。（1）x（F（x）G（x）x（F（x）H（x）（2）xF（x）（xG（x）（xF（x）G（x）（3）x（F（x）

49、G（x，y）（xF（x）R（x，y，z）（4）x(yF（x，y，z）yxF（x，y，z）第第2章章 一阶逻辑一阶逻辑 6设个体域D=a，b，c，消去下列各式中的量词。（1）xF（x）y F（y）（2）x（F（x）yG（y）（3）x y（F（x）G（y）（4）x yF（x，y，z）7求下列公式在解释I下的真值。（1）x（F（x）G（x），解释I：个体域D=1，2；F（x）：x=1；G（x）：x=2。（2）x（pQ（x）R（a），解释I：个体域D=-2，3，6；p：12；Q（x）：x3，R（x）：x5；a：5。第第2章章 一阶逻辑一阶逻辑 8给定解释I和I中赋值v如下：个体域D为实数集，E（x，y

50、）：x=y，G（x，y）：xy，N（x）：x是自然数， f（x，y）=x-y，g（x，y）=x+y，N（x，y）=xy v（x）=1，v（y）=-2第第2章章 一阶逻辑一阶逻辑 求下列公式在解释I和赋值v下的真值。（1）x yE（g（x，y），g（y，x）（2）N（x）y（N（y）（G（y，x）E（y，x）（3）y zE（N（y，z），x）（4）xyE（N（f（x，y），g（x，y），f（N（x，x），N（y，y）（5）E（g（x，g（x，y），a）第第2章章 一阶逻辑一阶逻辑 11证明量词辖域扩缩律（4）：x A（x）Bx（A（x）B）12证明量词辖域扩缩律：（6）BxA（x）x（BA（x）

51、（7）xA（x）Bx（A（x）B）（8）BxA（x）x（BA（x）13用等值演算证明下列等值式。（ 1） x（ F（ x） G（ x） ） y F（y）zG（z）（2）xy（F（x）G（y）xF（x）yG（y）（3）x（F（x）G（x）（xG（x）xF（x）第第2章章 一阶逻辑一阶逻辑 14将下列公式化成与之等值的前束范式。（1）x（F（x）yG（x，y）（2）（xF（x）xG（x）x（F（x）G（x）（3）xF（x）x（yG（x，y）yH（x，y，z）（4）（xF（x）yG（y）（F（x）zH（z）第第2章章 一阶逻辑一阶逻辑 15构造下列推理的证明：（1）前提：xF（x）xG（x）结论：x

52、（F（x）G（x）（2）前提：x（F（x）G（x）结论：xF（x）xG（x）（提示：用附加前提法或归缪法证明）（3）前提：x（F（x）G（x）结论：x y（F（y）H（x，y）x（G（x）H（x，x）第第2章章 一阶逻辑一阶逻辑 （4）前提：xF（x），x（F（x）G（x）H（x）结论：xH（x）（5）前提：xF（x）x（F（x）G（x）R（x），xF（x），xG（x）结论：xy（R（x）R（y）（6）前提：x（y（S（x，y）M（y）z（P（z）R（x，z）结论：zP（z）x y（S（x，y）M（y）第第2章章 一阶逻辑一阶逻辑 16在一阶逻辑中构造下列推理的证明。（1）有理数都是实数。有的有理数是整数。因此，有的实数是整数。（2）所有的有理数都是实数。所有的无理数也都是实数。任何虚数都不是实数。所以，虚数既非有理数也非无理数。（3）不存在不能表示成分数的有理数。无理数都不能表示成分数。所以，无理数都不是有理数。第第2章章 一阶逻辑一阶逻辑 17在一阶逻辑中构造下列推理的证明。（1）有些病人相信所有的医生。所有的病人都不相信骗子。因此，所有的医生都不是骗子。（2）任何人如果他喜欢步行，他就不喜欢乘汽车。每个人或者喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车。因此有的人不爱步行。