《离散数学》谓词逻辑.ppt

《《离散数学》谓词逻辑.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章一阶（谓词）逻辑谓词逻辑命题逻辑的局限性：命题逻辑不研究命题的内部结构、成分及命题之间的内在联系，以至于无法处理一些简单而又常见的推理过程。例如，下列推理：所有的人都是要死的。苏格拉底是人。苏格拉底是要死的。众所周知,这是真命题。但在命题逻辑中,如果用P,Q,R表示以上三个命题，则上述推理过程为：（P∧Q）R。借助命题演算的推理理论不能证明其为重言式。一阶逻辑深入研究一个命题内部的结构，把一个简单的命题分解为个体和谓词两部分，并重视其中表示数量信息的结构，进而建立起谓词逻辑理论。第2章谓词逻辑定义可以独立存在的具体事物或抽象的概念称为个体。例如，电子计算机、李明、

2、玫瑰花、黑板、实数、中国、思想、唯物主义等，客体也可称之为主语。类似的方法，引入表示个体的标识符。定义一个个体标识符，如果表示具体的或确定的个体为个体常项，而表示抽象的或泛指的（或者说取值不确定的）个体称为个体变项。个体常项一般用小写英文字母a,b,c…或带下标的ai,bi,ci…表示，个体变项一般用小写英文字母x,y,z…或带下标的xi,yi,zi…表示。2.1一阶逻辑基本概念定义个体变元的取值范围称为个体域或论域。如果把宇宙间一切事物组成个体域，则称为全总个体域。个体域可以是有穷集合，例如{1,2,3,4,5}，{a,b,c}等，也可以是无穷集合，例如自然数集，实数集

3、等。同时约定，本书在论述或推理中如无指明所采用的个体域，则都是使用全总个体域。2.1一阶逻辑基本概念定义命题中刻画单个个体的性质或者刻画两个及以上个体之间关系的词叫谓词。同样，要引入标识符表示谓词。定义表示具体性质或关系的谓词称为谓词常项，表示抽象的或泛指的性质或关系的谓词称为谓词变项。无论是谓词常项或变项都用大写英文字母P,Q,R…或带下标的Pi,Qi,Ri…表示，要根据上下文区分。2.1一阶逻辑基本概念例如：①张明是个劳动模范。②李华是个劳动模范。③王红是个大学生。[刻划客体的性质]④小李比小赵高2cm。⑤点a在b与c之间。⑥阿杜与阿寺同岁。[刻划客体之间的相互关系]

4、“...是个劳动模范”、“...是个大学生”、“…比…高2cm”、“…在…与…之间”都是谓词。由于谓词与个体之间有密切的联系，实践中常把二者写在一起：个体变元具有性质F，记作F(x)；个体变元x,y之间具有关系L，记作L(x,y)；一般把用函数的形式表示的谓词与个体变元的联合体也称为谓词。而把谓词中的变元实例化后，谓词就成为命题了。2.1一阶逻辑基本概念(1)F(x)表示x是个劳动模范a：张明F(a)就代表命题：张明是个劳动模范(2)H(x,y)表示x是y的老师s：小李t：小赵H(s,t)表示命题：小李是小赵的老师（3)R(x,y,z)表示z=x+yR(2,3,4)表示命

5、题4＝3+22.1一阶逻辑基本概念谓词中所含的个体变元数称为谓词的元数。含n个个体词的谓词称为n元谓词。例如上题，其中(1)、(2)、(3)分别为一元谓词、二元谓词、三元谓词。一般用P(x1,x2,...,xn)表示n元谓词：（1)如果从函数观点来看待n元谓词，则其定义域依赖于个体变元的定义域（个体域），值域为｛0,1｝；（2)n元谓词不是命题，由于谓词P也有可能是变元，所以只有用具体的谓词常项代替P，用具体的个体常项代表个体变元后，方为命题，称命题为0元谓词；（3)谓词中个体变元的顺序不能随意改动。2.1一阶逻辑基本概念例7.2、用0元谓词将命题符号化要求：先将它们在命

6、题逻辑中符号化，再在一阶逻辑中符号化(1)墨西哥位于南美洲在命题逻辑中,设p:墨西哥位于南美洲符号化为p,这是真命题在一阶逻辑中,设a：墨西哥，F(x)：x位于南美洲符号化为F(a)2.1一阶逻辑基本概念(2)是无理数仅当是有理数在命题逻辑中,设p：是无理数，q：是有理数.符号化为pq,这是假命题在一阶逻辑中,设F(x):x是无理数,G(x):x是有理数符号化为(3)如果2>3，则3<4在命题逻辑中,设p：2>3，q：3<4.符号化为pq,这是真命题在一阶逻辑中,设F(x,y)：x>y，G(x,y)：x

7、）如果张明比李民高，李民比赵亮高，则张明比赵亮高.在命题逻辑中,设p：张明比李民高，q：李民比赵亮高,r:张明比赵亮高.符号化为：pqr在一阶逻辑中,设F(x,y)：x比y高a:张明，b:李民，c:赵亮符号化为：F(a,b)F(b,c)F(a,c)2.1一阶逻辑基本概念定义表示个体常元或变元之间数量关系的词叫量词；表示“全部”，“所有的”，“一切的”，“每一个”，“任意的”等数量关系的词叫全称量词，用符号“”表示；如x表示对个体域中所有的x;xF(x)表示个体域中所有的x都具有性质F;表示“存在一些”，“有一些”