离散数学—第二章一阶逻辑.ppt

《离散数学—第二章一阶逻辑.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一阶逻辑——理学院数学系仝辉一阶逻辑的基本概念一阶逻辑合式公式及解释一阶逻辑等值式一阶逻辑推理理论第二章一阶逻辑苏格拉底三段论判断下面推理的正确性凡人都是要死的。苏格拉底是人。所以苏格拉底是要死的。用p,q,r表示三个命题，则（p∧q）→r并不是重言式。原因缺少命题内在的联系的反映。个体词,谓词简单的命题被分解成个体词与谓词.6是合数；王宏是程序员；小李比小赵高2厘米。个体词相关的基本概念个体词:是可以独立存在的客体.个体常项:用小写的英文字母a,b,c,d….个体变项:用小写的英文字母x,y,z….个体域:个体的取值范围.全总个体域:指宇宙中的一切

2、事物.谓词相关的基本概念谓词常项:表示具体性质或关系的谓词,用F,G,H表示.谓词变项:表示抽象的性质或关系的谓词,也用F,G,H表示,但要根据个体变项x,y等来定.x具有属性F,则用F(x)表示.x,y具有关系L,则用L(x,y)表示.谓词中的个体词数称为元数,含n个个体词的谓词称为n元谓词,如：P(x1,x2,x3,…,xn).通常，一元谓词是表示个体词的性质；n(n>1)元谓词是表示个体词之间的关系，且各个体词顺序不能随意改动。如：L(x,y):代表x小于y；而L(y,x):代表y小于x。谓词和命题的关系通常，n元谓词不是命题，因其真值无法确定

3、。如：L(x,y)。并没说明其谓词的意思。当其谓词已为常项，其还不是命题。如：L(x,y)：x小于y。其真值仍无法确定。只有当其谓词为常项，且n元个体词全为常量时，L(a,b)才是命题。如：a=2,b=3,其真值可唯一确定。通常，将不带个体变项的谓词叫0元谓词。此时其不一定是命题。只有当谓词为常项时，才是命题。命题逻辑中的联结词在一阶逻辑中均可使用。例题2是素数且是偶数.F(x):x是素数;G(x):x是偶数;a:2符号化为F(a)^G(a)如果2大于3,则2大于4.L(x,y):x大于y.a:2;b:3;c:4符号化为L(a,b)->L(a,c)量

4、词量词:表示数量的词.全称量词:对应日常生活中用到的“一切”，“所有的”，“任意的”，“不存在一个…不…”等词，用符号“”表示。x表示个体域中的所有个体。xF(x)表示个体域中的所有个体具有属性F。存在量词:对应日常生活中用到的“存在着”，“有一个”，“至少有一个”,“不是所有的…都不…”等词，用符号“”表示。x表示存在个体域中的个体。xF(x)表示存在个体域中的个体具有属性F。明确个体域考虑个体域D为人类集合凡人都要死的。xF(x),其中F(x)：x是要死的。有人活百岁以上。xG(x),其中G(x)：x活百岁以上。考虑个体域为全总

5、个体域对于所有个体而言，如果它是人，则它是要死的。引入新谓词M(x):x是人。M(x)称为特性谓词x(M(x)→F(x))存在着个体，它是人并且活百岁以上。x(M(x)∧G(x))用量词时的注意点在不同的个体域中，命题符号化的形式可能不一样；如果事先没有给出个体域，都应以全总个体域为个体域；个体域和谓词的含义确定之后，n元谓词要转化为命题至少需要n个量词(此点以后再讨论)；当个体域为有限集时，如果D={a1,a2,…an},由量词的意义可以看出，对于任意的谓词A(x),都有：xA(x)A(a1)∧A(a2)∧…∧A(an);xA(x)A(

6、a1)∨A(a2)∨…∨A(an).多个量词同时出现时，不能随意颠倒他们的顺序。例题对任意的x，存在着y，使得x+y=5.H(x,y)表示x+y=5可符号化成：xyH(x,y)不可符号化成：yxH(x,y)P40.例题2.2、2.3、2.4、2.5一阶逻辑的基本概念一阶逻辑合式公式及解释一阶逻辑等值式一阶逻辑推理理论第二章一阶逻辑一阶逻辑合式公式采用字母表定义2.1字母表个体常项：a,b,c,…,ai,bi,ci,….,i≥1;个体变项：x,y,z,…,xi,yi,zi,….,i≥1;函数符号：f,g,h,…,fi,gi,hi,….,i≥1;

7、谓词符号：F,G,H,…,Fi,Gi,Hi,i≥1;量词符号：，；联结词：┐，∧，∨，→，↔；括号和逗号:(,).项的递归定义定义2.2个体常项和变项是项；若（x1,x2,….,xn）是任意的n元函数，t1,t2,….,tn是项，则（t1,t2,….,tn）是项。只有有限次地使用①、②生成的符号串才是项。a,b,x,y,f(x,y)=x+y，h(x,y)=x•y都是项。原子公式、合式公式定义2.3:原子公式设R(x1,x2,…,xn)是任意的n元谓词，t1,t2,…,tn是项，则称R(t1,t2,….,tn)为原子公式。定义2.4:合式公式原

8、子公式是合式公式；若A是合式公式，则(7A)是合式公式；若A,B是合式公式，则(A∧B),(A∨B),(A→