离散数学(一阶逻辑)ppt课件.ppt

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

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

2、….个体变项:用小写的英文字母x,y,z….个体域:个体的取值范围.全总个体域:指宇宙中的一切事物.62.谓词的相关概念谓词:表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词:表示事物的性质多元谓词(n元谓词,n2):表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：xy，…0元谓词:不含个体变项的谓词,即命题常项或命题变项7例1用0元谓词将命题符号化(1)墨西哥位于南美洲F(x)：x位于南美洲a：墨西哥F(a)二、一阶逻辑中命题符号化8（2）2是素数且是偶数.F(x

3、):x是素数;G(x):x是偶数;a:2符号化为F(a)G(a)（3）如果2大于3,则2大于4.L(x,y):x大于y.a:2;b:3;c:4符号化为L(a,b)L(a,c)二、一阶逻辑中命题符号化9例2.（1）凡人都要死的。（2）有人活百岁以上103.量词量词:表示数量的词全称量词:表示任意的,所有的,一切的，不存在一个…不…”如x表示对个体域中所有的xxF(x)表示个体域中的所有个体具有属性F。存在量词:表示存在,有的,至少有一个如x表示在个体域中存在xxF(x)表示存在个体域中的个体具有属性F。11明确个体域例2

4、.（1）凡人都要死的。（2）有人活百岁以上考虑个体域D为人类集合xF(x),其中F(x)：x是要死的。xG(x),其中G(x)：x活百岁以上。考虑个体域为全总个体域对于所有个体而言，如果它是人，则它是要死的。引入新谓词M(x):x是人。x(M(x)→F(x))存在着个体，它是人并且活百岁以上。x(M(x)∧G(x))12一阶逻辑中命题符号化(续)例3在一阶逻辑中将下面命题符号化(1)正数都大于负数(2)有的无理数大于有的有理数解注意:题目中没给个体域,一律用全总个体域(1)令F(x):x为正数,G(y):y为负数,L(x,y)

5、:x>yx(F(x)y(G(y)L(x,y)))或xy(F(x)G(y)L(x,y))两者等值(2)令F(x):x是无理数,G(y):y是有理数,L(x,y)：x>yx(F(x)y(G(y)L(x,y)))或xy(F(x)G(y)L(x,y))两者等值13用量词时的注意点在不同的个体域中，命题符号化的形式可能不一样；如果事先没有给出个体域，都应以全总个体域为个体域；个体域和谓词的含义确定之后，n元谓词要转化为命题至少需要n个量词(此点以后再讨论)；当个体域为有限集时，如果D={a1,a2,…an},由量

6、词的意义可以看出，对于任意的谓词A(x),都有：xA(x)A(a1)∧A(a2)∧…∧A(an);xA(x)A(a1)∨A(a2)∨…∨A(an).多个量词同时出现时，不能随意颠倒他们的顺序。14例题对任意的x，存在着y，使得x+y=5.H(x,y)表示x+y=5可符号化成：xyH(x,y)不可符号化成：yxH(x,y)P37.例题2.2、2.3、2.4、2.515第2章一阶逻辑2.1一阶逻辑基本概念2.2一阶逻辑合式公式及解释2.3一阶逻辑等值式第二章一阶逻辑162.2一阶逻辑公式及解释合式公式(简称公式)个体变项的

7、自由出现和约束出现解释与分类17一阶逻辑合式公式采用字母表定义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;谓词符号：F,G,H,…,Fi,Gi,Hi,i≥1;量词符号：，；联结词：┐，∧，∨，→，↔；括号和逗号:(,).18项的递归定义定义2.2个体常项和变项是项；若（x1,x2,….,xn）是任意的n元函数，t1,t2,….,tn是项，则（t1,t2,….,tn）是项。只有有限次地使用

8、①、②生成的符号串才是项。个体常项、变项是项，由它们构成的n元函数和复合函数还是项19原子公式定义2.3设R(x1,x2,…,xn)是任意的n元谓词，t1,t2,…,tn是任意的n个项，则称R(t1,t2,…,tn)是原