一阶逻辑ppt课件

.,1,离散数学,一阶逻辑,.,2,内容回顾,命题逻辑的特点和局限性:命题是命题演算的基本单位不再对简单命题进行分解无法研究命题的内部结构及命题之间内在的联系在推理方面存在的局限性例如，无法判断著名的“苏格拉底三段论”的正确性课P37,.,3,P：凡人都是要死的Q：苏格拉底是人R：所以苏格拉底是要死的前提:P,Q结论:R（PQ）R表示上述推理，但它不是重言式所以,无法判断“苏格拉底三段论”的正确性,.,4,其原因是P，Q，R这样的表示太粗略，没有把它们的内在联系反映出来。要反映这种内在联系，就要对简单命题做进一步的分析，分析出其中的个体词、谓词、量词等，研究它们的形式结构及逻辑关系，总结出正确的推理形式和规则-这就是一阶逻辑所研究的内容一阶逻辑也称谓词逻辑,.,5,本章学习:一阶逻辑的基本概念一阶逻辑合式公式及解释一阶逻辑等值式一阶逻辑推理理论,第2章一阶逻辑,.,6,今日内容,一阶逻辑的基本概念个体词、谓词、量词等基本概念一阶逻辑下如何将命题符号化,.,7,2.1一阶逻辑基本概念,一阶逻辑中，简单命题被分解成个体词和谓词个体词：可以独立存在的客体可以是一个具体的事物，也可以是一个抽象的概念例如，李明，玫瑰花，黑板，自然数，2，思想，定理等都可以做为个体词谓词：用来刻画个体词的性质或个体词之间关系的词语例如：是人；和是同学,.,8,例：在下面3个简单命题中：1.2是无理数2.王宏是程序员。3.小李比小赵高2厘米。个体词:2，王宏,小李,小赵谓词:是无理数，是程序员，比高2厘米其中：“是无理数”，“是程序员”：表示个体词性质“比高2厘米”：表示个体词之间关系,.,9,注：个体词与谓词的划分并不唯一例如，可以把“2”和“无理数”看成个体词，把“是：看成谓词,.,10,与个体词相关的概念:个体常项：表示具体的或特定的个体的词用小写的英文字母a，b，c，表示个体变项：表示抽象的或泛指的个体的词用小写的英文字母x，y，z，表示,.,11,个体域（论域）：个体变项的取值范围个体域可以是有限事物的集合，例如：1，2，3，4a，b，c计算机，2，狮子也可以是无限事物的集合，例如自然数集合，实数集合等特别是，当无特殊声明时，将宇宙间的一切事物组成个体域，称为全总个体域,.,12,与谓词相关的概念:谓词常项：表示具体性质或关系的谓词例如：可以用F表示“是无理数“谓词变项：表示抽象的或泛指的谓词谓词常项和变项都用大写英文字母F，G，H，表示F，G，H表示的是谓词常项还是谓词变项要根据上下文而定,.,13,F（x）:表示x具有性质F如F（x）:x是学生F（x，y）：表示x和y具有关系F如F（x，y）：x和y是同学以后常称这种个体变项和谓词的联合体为谓词,.,14,例如：若F（x）表示“x是无理数”，L（x，y）表示“x比y高2厘米”，a表示2，b表示小李，c表示小赵则F（a）表示“2是无理数”，L（b，c）表示“小李比小赵高2厘米”。,.,15,谓词的元,一个谓词中所包含的个体词的数目称为该谓词的元数含有n（n1）个个体词的谓词成为n元谓词一元谓词通常表示个体词的性质，n（n2）元谓词通常表示个体词之间的关系用P（x1，x2，xn）表示泛指的n元谓词，是以个体变项x1，x2，xn的个体域为定义域，以0，1为值域的n元函数在这里，n个个体变项的顺序不能随意改动,.,16,谓词与命题的关系,一般说来，谓词P（x1，x2，xn）不是命题，它的真值无法确定为了使它成为命题，必须指定某一谓词常项代替P指定n个个体常项a1，a2，an分别代替n个个体变项x1，x2，xn,.,17,例如，L（x，y）是一个2元谓词，它不是命题当令L（x，y）表示“x小于y”之后，该谓词中的谓词部分便成为了常项，但它不是命题当取a为2，b为3时，L（a，b）才是命题，并且是真命题同理，当取c为2，d为1时，L（c，d）为假命题,.,18,有时将不带个体变项的谓词称为0元谓词L（a，b），L（c，d）是0元谓词一旦一个0元谓词中的谓词的意义明确之后，该0元谓词就是命题命题逻辑中的简单命题都可以用0元谓词表示，因而可将命题看成谓词的特殊情况命题逻辑中的联结词在一阶逻辑中均可应用一阶逻辑是命题逻辑的拓展,.,19,例:将下列命题用0元谓词符号化1.2是素数且是偶数.2.如果2大于3,则2大于4.如果张明比李民高,李民比赵亮高,则张明比赵高.l解题步骤：（a）找出个体词和谓词（b）符号化谓词和个体词（c）使用符号化了的谓词和个体词及逻辑联结词进行命题符号化,.,20,2是素数且是偶数（a）找出个体词和谓词个体常项：2谓词常项：是素数、是偶数（b）符号化谓词和个体词F（x）：x是素数G（x）：x是偶数a：2（c）命题符号化为F（a）G（a）,.,21,2.如果2大于3,则2大于4.（a）找出个体词和谓词个体常项：2，3，4谓词常项：大于（b）符号化谓词和个体词F（x，y）：x大于ya：2b：3c：4（c）命题符号化为F（a,b）F（a,c）,.,22,3.如果张明比李民高,李民比赵亮高,则张明比赵亮高.（a）找出个体词和谓词个体常项：张明，李民，赵亮谓词常项：比高（b）符号化谓词和个体词F（x，y）：x比y高a：张明b：李民c：赵亮（c）命题符号化为:（F（a,b）F（b,c）F（a,c）,.,23,量词：有些命题除了有个体词和谓词外，还有表示数量的词例如：所有的人要死的有的人活百岁以上,.,24,两种量词全称量词：对应日常语言中的“一切”，“所有的”，“任意的”等词，用符号“”表示x表示对个体域里的所有个体，xF（x）表示个体域里的所有个体都有性质F,.,25,两种量词存在量词：对应日常语言中的“存在着”，“有一个”，“至少有一个”等词，用符号“”表示x表示存在个体域里的个体，xF（x）表示至少存在个体域里的一个个体具有性质F,.,26,带量词命题的符号化例如：1.所有的人要死的2.有的人活百岁以上由于量词与个体域之间有紧密的联系，在考虑命题符号化问题时，必须先明确个体域假设个体域D是人类的集合1.符号化为xF（x），其中，F（x）：x是要死的这个命题是真命题2.符号化为xG（x），其中，G（x）：x活百岁以上这个命题也是真命题,.,27,现在假设个体域D是全总个体域这时，xF（x）和xG（x）不能表达原命题的意义，因为1.所有的人要死的。2.有的人活百岁以上。变成了1.所有的个体要死的。变严格2.有的个体活百岁以上。变松垮,.,28,个体域D是全总个体域时,命题应转述为1.所有的人要死的。2.有的人活百岁以上。1.对所有个体而言,如果它是人,则它是要死的。2.存在着个体,它是人并且活百岁以上。需要引进新的谓词M（x）：x是人。这样的表示了个体词取值范围的谓词称为特性谓词,.,29,使用特性谓词M（x），所给命题就可以符号化为:1.x（M（x）F（x）2.x（M（x）G（x）注意：特性谓词在不同量词下的不同用法,.,30,使用量词时的注意点在不同的个体域中，命题符号化的形式可能不一样如果事先没有给出个体域，都应以全总个体域为个体域在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的个体域和谓词的含义确定之后，n元谓词要转化为命题至少需要n个量词,.,31,使用量词时的注意点当个体域为有限集时，如D=a1，a2，am，对于任意的谓词A（x），都有xA（x）A（a1）A（a2）A（am）xA（x）A（a1）A（a2）A（am）这实际上是将一阶逻辑中的命题公式转化成为了命题逻辑中的命题公式,.,32,例:个体域D=a,b,c，消去下面公式中的量词xR（x）yS（y）原式R（a）R（b）R（c）yS（y）R（a）R（b）R（c）(S（a）S（b）S（c）),.,33,使用量词时的注意点多个量词同时出现时，不能随意颠倒它们的顺序。颠倒后会改变原命题的含义例如，对于命题“对任意的x，存在着y，使得x+y=5”应符号化为：xyH（x，y）其中，H（x，y）：x+y=5而不能符号化为yxH（x，y）这一公式表示：存在y，对任意的x有x+y=5,.,34,例:在一阶逻辑中将下面命题符号化。1.凡有理数均可表成分数。2.有的有理数是整数个体域为全总个体域,解：F（x）：x可表成分数G（x）：x是整数引入特性谓词：R（x）：x是有理数。1.x（R（x）F（x）2.x（R（x）G（x）,.,35,例:在一阶逻辑中将下面命题符号化。1.凡偶数均能被2整除2.存在着偶素数。3.没有不犯错误的人。4.在北京工作的人未必都是北京人。解：本题未指定个体域，因而取个体域为全总个体域。,.,36,1.凡偶数均能被2整除F（x）：x是偶数G（x）：x能被2整除x（F（x）G（x）2.存在着偶素数。F（x）：x是偶数H（x）：x是素数x（F（x）H（x）,.,37,3.没有不犯错误的人M（x）：x是人I（x）：x犯错误x（M（x）I（x）或x（M（x）I（x）4.在北京工作的人未必都是北京人J（x）：x是人K（x）:x在北京工作P（x）:x是北京人x（J（x）K（x）P（x）,.,38,练习:在一阶逻辑下将命题符号化1.鸟都会飞翔2.并不是所有的人都爱吃糖3.有人爱看小说4.没有不爱看电影的人,.,39,练习:在一阶逻辑下将命题符号化1.鸟都会飞翔F(x):x是鸟；G(x):x会飞；x(F(x)G(x)2.并不是所有的人都爱吃糖F(x):x是人；G(x):x爱吃糖；x(F(x)G(x)或：$x(F(x)G(x)3.有人爱看小说F(x):x是人；G(x):x爱看小说；$x(F(x)G(x)4.没有不爱看电影的人F(x):x是人；G(x):x爱看电影；$x(F(x)G(x),.,40,例使用多元谓词在一阶逻辑中将下列命题符号化。1.一切人都不一样高。2.每个自然数n都有后继数n+1。3.有的自然数n无先驱数n-1。解：因为题目中没指明个体域，因而使用全总个体域。,.,41,1.一切人都不一样高。可将命题转译（详述）为：对于任意的两个个体x和y，如果x是人，y是人,而且x与y不是同一个人（个体），那么x和y不一样高。令M（x）:x是人H（x，y）：x与y是同一个人（个体）L(x，y)：x和y一样高。则命题可符号化为xy(（M(x)M（y）H(x，y)）L(x，y),.,42,1.一切人都不一样高。也可将命题转译为：不存在这样的事实：有两个个体x和y，x是人，y是人，而且x与y不是同一个人，x和y一样高。则命题可符号化为（xy(M(x)M(y)H(x，y)L(x，y)）两种符号化的结果是等值的,.,43,2.每个自然数n都有后继数n+1。命题可转译为：对于所有的个体，如果它是一个自然数，则肯定存在另一个个体，它是自然数而且是前一个个体的后继数。令F（x）：x是自然数；H（x，y）：y是x的后继数。则命题可符号化为x(F(x)y(F(y)H(x，y),.,44,3.有的自然数n无先驱数n-1。命题可转译为：存在这样的个体x，它是一个自然数，对任意的个体y，如果y是自然数那么y不是x的先驱数。令：F（x）：x是自然数；H（x，y）：y是x的先驱数。则命题可符号化为x(F(x)y(F(y)H(x，y),.,45,练习:在一阶逻辑下将命题符号化凡是对顶角都相等解