离散数学-耿素云PPT(第5版)2.1-2.ppt

《离散数学-耿素云PPT(第5版)2.1-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第2章一阶逻辑2.1一阶逻辑基本概念2.2一阶逻辑合式公式及解释2.3一阶逻辑等值式与前束范式22.1一阶逻辑基本概念个体词谓词量词一阶逻辑中命题符号化命题逻辑的局限性苏格拉底三段论：凡是人都要死的.苏格拉底是人.所以苏格拉底是要死的.在命题逻辑中，只能用p、q、r表示以上3个命题，上述推理可表成(p∧q)→r这不是重言式34基本概念——个体词、谓词、量词个体词（个体）:所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a,b,c表示个体变项：抽象的事物，用x,y,z表示个体域:个体变项的取值范围有限个体域，如{a,b,c},{1,2

2、}无限个体域，如N,Z,R,…全总个体域:宇宙间一切事物组成5基本概念(续)谓词:表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词:表示事物的性质多元谓词(n元谓词,n2):表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：xy，…0元谓词:不含个体变项的谓词,即命题常项或命题变项6基本概念(续)量词:表示数量的词全称量词:表示任意的,所有的,一切的等如x表示对个体域中所有的x存在量词:表示存在,有的,至少有一个等如x表示在个体域中存在x7一阶逻辑中命题符号化例用0元谓词将命题

3、符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1)墨西哥位于南美洲在命题逻辑中,设p:墨西哥位于南美洲符号化为p在一阶逻辑中,设a：墨西哥，F(x)：x位于南美洲,符号化为F(a)8例(续)(2)是无理数仅当是有理数在命题逻辑中,设p：是无理数，q：是有理数.符号化为pq在一阶逻辑中,设F(x):x是无理数,G(x):x是有理数符号化为在命题逻辑中,设p：2>3，q：3<4.符号化为pq在一阶逻辑中,设F(x,y)：x>y，G(x,y)：x3，则3<49一阶逻辑中命题符号化(续)

4、例在一阶逻辑中将下面命题符号化(1)人都爱美;(2)有人用左手写字分别取(a)D为人类集合,(b)D为全总个体域.解：(a)(1)设G(x):x爱美,符号化为xG(x)(2)设G(x):x用左手写字,符号化为xG(x)(b)设F(x):x为人，G(x):同(a)中(1)x(F(x)G(x))(2)x(F(x)G(x))这是两个基本公式,注意它们的使用10一阶逻辑中命题符号化(续)例在一阶逻辑中将下面命题符号化(1)正数都大于负数(2)有的无理数大于有的有理数解注意:题目中没给个体域,使用全总个体域(1)令F(x):x为正数,G(y):y为负

5、数,L(x,y):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))两者等值11一阶逻辑中命题符号化(续)几点注意：1元谓词与多元谓词的区分无特别要求,应使用全总个体域,引入特性谓词量词顺序一般不能随便颠倒两个基本形式x(F(x)G(x))和x(F(x)G(x))的使用否定的表示，如“没有不呼吸的人”等同于“所有的人都呼吸”

6、“不是所有的人都喜欢吃糖”等同于“存在不喜欢吃糖的人”122.2一阶逻辑公式及解释合式公式(简称公式)个体变项的自由出现和约束出现解释与赋值公式分类永真式，矛盾式,可满足式13字母表定义字母表包含下述符号：(1)个体常项：a,b,c,…,ai,bi,ci,…,i1(2)个体变项：x,y,z,…,xi,yi,zi,…,i1(3)函数符号：f,g,h,…,fi,gi,hi,…,i1(4)谓词符号：F,G,H,…,Fi,Gi,Hi,…,i1(5)量词符号：,(6)联结词符号：,,,,(7)括号与逗号：(,),，14项定义项的定义如下：(

7、1)个体常项和个体变项是项.(2)若(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则(t1,t2,…,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.个体常项、变项是项，由它们构成的n元函数和复合函数还是项15原子公式定义设R(x1,x2,…,xn)是任意的n元谓词，t1,t2,…,tn是任意的n个项，则称R(t1,t2,…,tn)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4))等均为原子公式16合式公式定义合式公式（简称公式）定义如下：(1)原子公

8、式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB