第2章一阶逻辑.

第2章一阶逻辑2在命题逻辑中，我们把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。实际上，简单命题还可以进行分解，例如，“王平是大学生”这一简单命题可以分解为主语(王平)和谓语(是大学生)，命题逻辑反映不出这一特点。其次，如下两个简单命题“王平是大学生”和“李明是大学生”，有一个共同特点——是大学生，这一共性在命题逻辑中也表示不出来。因此，有必要推广命题逻辑。第2章一阶逻辑3第三，有些简单而正确的推理过程在命题演算里不能得到证明。例如著名的苏格拉底三段论：“人都是要死的，苏格拉底是人，所以苏格拉底是要死的。”在命题逻辑中，三个原子命题分别用P，Q，R表示，现在要证明PQR，即证明PQR是重言式，但这在命题逻辑中是不可能的。因此从推理的角度看，也有必要推广命题逻辑。一阶逻辑就是命题逻辑的自然推广。第2章一阶逻辑4本章内容提要：1.一阶逻辑中的基本概念2.一阶逻辑合式公式与解释3.一阶逻辑等值式与前束范式第2章一阶逻辑5本章学习要求：一、重点掌握的核心知识点1.能够熟练运用一阶逻辑中的翻译原理对语句进行符号化,并判断谓词的真值。2.能正确地理解一阶逻辑公式的有效性，记住一阶逻辑公式的基本等价公式并能加以运用。二、一般掌握的知识点1.能给出一个一阶逻辑公式的解释并能判断其真值。2.基本理解量词辖域、约束变元、自由变元第2章一阶逻辑6定义2.1.1在原子命题中，可以独立存在的客体称为个体词。而表示单个个体的性质或两个以上个体关系的词叫谓词。如王平，李明，计算机，离散数学，精神等都可以作为个体。(1)将表示具体的或确定的个体词称为个体常元;(2)将表示抽象的或泛指的(或者说取值不确定的)个体词称为个体变元。个体常量一般用小写英文字母a,b,c…或带下标的ai,bi,ci…表示，个体变量一般用小写英文字母x,y,z…或带下标的xi,yi,zi…表示。2.1一阶逻辑基本概念2.1.1谓词7如：考查下列句子(1)北京是中国的首都。(2)离散数学是计算机的基础课程。(3)中国人是很聪明的。(4)小李比小赵高2厘米。2.1.1谓词2.1一阶逻辑基本概念8定义2.1.2个体变元的取值范围称为个体域(或论域)，把宇宙间所有个体域聚集在一起组成的个体域称为全总个体域。个体域可以是有穷集合，例如{1,2,3,4,5}，{a,b,c}等，也可以是无穷集合，例如自然数集，实数集等。2.1.1谓词2.1一阶逻辑基本概念9定义2.1.3谓词中包含的个体词数称为元数。含n(n1)个个体词的谓词称为n元谓词。记为P(x1，x2，…，xn)。此时它以x1，x2，…，xn的个体域为定义域，P(x1，x2，…，xn)的值域为{0，1}。当n=1时，称一元谓词；当n=2时，称为二元谓词，…。特别地，当n=0，称为零元谓词，即不带个体变元的谓词为零元谓词。零元谓词是命题，这样命题与谓词就得到了统一，因而可将命题看成特殊的谓词。2.1.1谓词2.1一阶逻辑基本概念10一般来说，“x是A”类型的命题可以用A(x)表达。对于“x大于y”这种两个个体之间关系的命题，可表达为B(x，y)，这里B表示“…大于…”谓词。我们把A(x)称为一元谓词，B(x，y)称为二元谓词，M(a，b，c)称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。2.1.1谓词2.1一阶逻辑基本概念11解(1)设谓词G(x)：x是素数，a：4，b：8；(1)中的题符号化为谓词的蕴涵式：G(a)→G(b)由于此蕴涵式的前件为假，所以(1)中的命题为真。(2)设谓词H(x，y)：x小于y，a：1，b：2，c：5，d：4(2)中的命题符号化为谓词的蕴涵式：H(a，b)→H(c，d)由于此蕴涵式的前件为真，后件为假，所以(2)中的命题为假。例2.1.1将下列命题符号化，并讨论它们的真值：(1)只有4是素数，8才是素数。(2)如果1小于2，则5小于4。2.1一阶逻辑基本概念12例2.1.2用个体词，谓词表示下列命题。(1)张华是大学生。解令a：张华；S(x)：x是大学生。整个命题可表示为：S(a)。说明：①若x的个体域为某大学计算机系的全体学生，则S(a)为真；②若x的个体域为某中学的全体学生，则S(a)为假；③若x的个体域为某电影院中的观众，则S(a)真值不确定。所以个体变量在哪些个体域取特定的值，对命题的真值极有影响。2.1.1谓词2.1一阶逻辑基本概念13(2)武汉位于重庆和上海之间。解令a：武汉；b：重庆；c：上海；P(x,y,z)：x位于y和z之间。整个命题可表示为P(a,b,c)。说明：显然P(a,b,c)为真，但P(b,a,c)为假。所以个体变量的顺序影响命题真值，不能随意改动。2.1.1谓词2.1一阶逻辑基本概念14综上，有如下结论：(1)谓词中个体词的顺序不能随意变更。(2)一元谓词用以描述一个个体的某种特性，而n元谓词则用以描述n个个体之间的关系。(3)0元谓词就是一般命题。(4)具体命题的谓词表示形式和n元谓词是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。(5)一个n元谓词不是一个命题，但将n元谓词中的个体变元都用个体域中某个具体的个体取代后，就成为一个命题。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。2.1.1谓词2.1一阶逻辑基本概念15例2.1.3将下列命题符号化：(1)2是素数且是偶数(2)如果2大于3，则2大于4(3)如果张明比李民高，李民比赵亮高，则张明比赵亮高。解(1)F(x)：x是素数；G(x)：x是偶数；a：2F(a)G(a)(2)L(x,y)：x大于y；a：2；b：3；c：4L(a,b)L(a,c)(3)H(x,y)：x比y高；a：张明；b：李民；c：赵亮H(a,b)H(b,c)H(a,c)2.1.1谓词2.1一阶逻辑基本概念16考虑下列命题的符号化：(1)所有的人都要死的(2)有的人活到百岁以上2.1.1谓词2.1一阶逻辑基本概念17定义2.1.4表示个体常元或变元之间数量关系的词叫量词；1.全称量词：表示“全部”，“所有的”，“一切的”，“每一个”，“任意的”等数量关系的词，用符号“”表示；(x)F(x)表示个体域里的所有个体都有有性质F。2.存在量词：表示“存在一些”，“有一些”，“至少有一个”等数量关系的词，用符号“”表示；(x)F(x),表示存在着个体域里的某个体具有有性质F。其中的x称为作用变量，F(x)称为全称量词或存在量词的辖域2.1.2量词2.1一阶逻辑基本概念18注意：量词的优先级高于任何联结词，所以(x)P(x1,x2,…,xn)、(x)P(x1,x2,…,xn)、可分别写成xP(x1,x2,…,xn)、xP(x1,x2,…,xn)，但要注意明确量词的辖域2.1.2量词2.1一阶逻辑基本概念19例2.1.4符号化下列命题(设个体域为整数集合)。(1)所有的整数都是有理数。(2)有些整数是奇数。解(1)令P(x)：x是有理数，则命题可表示为：xP(x)。(2)令Q(x)：x是奇数，则命题可表示为：xQ(x)。2.1.2量词2.1一阶逻辑基本概念20将下列命题的符号化：考虑个体域为人类的情况：(1)所有的人都要死的F(x):x是要死的xF(x)(2)有的人活到百岁以上G(x)：x活百岁以上xF(x)若个体域为全总个体域？2.1.2量词2.1一阶逻辑基本概念21引出一个新的谓词，将人分离出来。M(x)：x是人在全总个体域的情况下以上两命题可叙述如下：(1)对所有的个体而言，如果它是人，则它是要死的。x(M(x)F(x))(2)有的人活到百岁以上x(M(x)F(x))2.1.2量词2.1一阶逻辑基本概念22定义2.1.5若一个谓词P(x)是用来限制个体变元的取值范围，那么称谓词P(x)为特性谓词。在使用全总个体域时，对个体变化的真正取值范围，用特性谓词加以限制。一般地，对全称量词，将特性谓词作蕴含的前件；对存在量词，将特性谓词作合取项。2.1.2量词2.1一阶逻辑基本概念23例2.1.5符号化下列命题(设个体域为整数集合)。(1)所有的老虎都要吃人。(2)每一个大学生都会说英语。(3)所有的人都长着黑头发。(4)有一些人登上过月球。(5)有一些自然数是素数。2.1.2量词2.1一阶逻辑基本概念24解：(1)P(x):x会吃人；Q(x)：x是老虎(x)(Q(x)P(x))(2)H(x):x是大学生；G(x)：x会说英语(x)(H(x)G(x))(3)F(x):x是人；R(x)：x长着黑头发(x)(F(x)R(x))(4)F(x):x是人；M(x)：x登上过月球(x)(F(x)M(x))(5)H(x):x是自然数；S(x)：x是素数(x)(H(x)S(x))2.1一阶逻辑基本概念25一阶逻辑符号化的两条规则：统一个体域为全总个体域，而对每一个句子中个体变量的变化范围用一元特性谓词刻画之。特性谓词在加入到命题函数中时必遵守如下原则：(1)对全称量词，将特性谓词作为蕴含式的前件加入；(2)对存在量词，将特性谓词作为合取式之合取项加入。2.2.1一阶逻辑公式的语言翻译2.1一阶逻辑基本概念26在进行句子翻译时，应弄清楚以下几个方面的问题：(1)首先假定个体域为全总个体域，然后找出每个句子中具体个体域，并用一元特性谓词表示。(2)确定句子中反应个体性质或者个体之间关系的谓词，并用合适的n元谓词表示。(2)确定修饰个体词的量词，是全称量词还是存在量词。2.2.1一阶逻辑公式的语言翻译2.1一阶逻辑基本概念27例2.2.1用一阶逻辑符号化下述语句.(1)天下乌鸦一般黑。(2)没有人登上过木星。(3)在美国留学的学生未必都是亚洲人。(4)每个实数都存在比它大的另外的实数。(5)尽管有人很聪明，但未必一切人都聪明(6)对任意给定的ε0，必存在着δ0，使得对任意的x，只要|x-a|δ，就有|f(x)-f(a)|ε成立。2.2.1一阶逻辑公式的语言翻译2.1一阶逻辑基本概念28解：(1)设F(x):x是乌鸦；G(x,y):x与y一般黑(x)(y)(F(x)F(y)G(x,y))或者(x)(y)(F(x)F(y)G(x,y))(2)设H(x):x是人；M(x):x登上过木星。(x)(H(x)M(x))或(x)(H(x)M(x))(3)设H(x)：是亚洲人；A(x):是在美国留学的学生。(x)(A(x)H(x));或者：(x)(A(x)H(x))(4)设R(x):x是实数；L(x,y):x小于y(x)(R(x)(y)(R(y)L(x,y)));(5)设M(x):x是人；C(x):x很聪明(x)(M(x)C(x))(x)((M(x)C(x));(6)对任意给定的ε0，必存在着δ0，使得对任意的x，只要|x-a|δ，就有|f(x)-f(a)|ε成立。(ε)((ε0)(δ)((δ0)(x)((|x-a|δ(|f(x)-f(a)|ε))))2.2.1一阶逻辑公式的语言翻译2.1一阶逻辑基本概念29例2.2.2设P(x)：x是素数；I(x)：x是整数;Q(x,y):x+y=0.用语句描述下述句子，并判断其真假值。(1)x(I(x)P(x))(2)x(I(x)P(x))(3)(x)(y)(I(x)I(y)Q(x,y));(4)(x)(I(x)(y)(I(y)Q(x,y)));(5)(x)(x)(I(x)(I(y)Q(x,y)));2.1一阶逻辑基本概念30解设P(x)：x是素数；I(x)：x是整数;Q(x,y):x+y=0.(1)对任意的整数x，x一定是素数。F(2)存在一些整数x，x是素数。T(3对任意的整数x、y，都有x+y=0。F(4对任意的整数x，都存在着整数y，使得x+y=0。T(5)存在着整数x，使得对任意的整数y，都有x+y=0.F2.2.1一阶逻辑公式的语