资源描述：
《离散数学第二章一阶逻辑知识点总结.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数理逻辑部分第2章一阶逻辑2.1一阶逻辑基本概念个体词（个体）:所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a,b,c表示个体变项：抽象的事物，用x,y,z表示个体域:个体变项的取值范围有限个体域，如{a,b,c},{1,2}无限个体域，如N,Z,R,…全总个体域:宇宙间一切事物组成谓词:表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词:表示事物的性质多元谓词(n元谓词,n³2):表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：x³y，…0
2、元谓词:不含个体变项的谓词,即命题常项或命题变项量词:表示数量的词 全称量词":表示任意的,所有的,一切的等如"x表示对个体域中所有的x存在量词$:表示存在,有的,至少有一个等如$x表示在个体域中存在x一阶逻辑中命题符号化例1用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1)墨西哥位于南美洲在命题逻辑中,设p:墨西哥位于南美洲符号化为p,这是真命题在一阶逻辑中,设a：墨西哥，F(x)：x位于南美洲符号化为F(a)例2在一阶逻辑中将下面命题符号化(1) 人都爱美;(2)有人用左手写字分别取(a)D
3、为人类集合,(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))这是两个基本公式,注意这两个基本公式的使用.例3在一阶逻辑中将下面命题符号化(1)正数都大于负数(2)有的无理数大于有的有理数解注意:题目中没给个体域,一律用全总个体域 (1)令F(x):x为正数,G(y):y为负数,L(x,y):x>y"x(F(x)®"y(G(y)®L(x,y)
4、))或"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))两者等值几点注意：1元谓词与多元谓词的区分无特别要求，用全总个体域量词顺序一般不能随便颠倒否定式的使用思考：①没有不呼吸的人②不是所有的人都喜欢吃糖③不是所有的火车都比所有的汽车快以上命题应如何符号化？2.2一阶逻辑合式公式及解释字母表定义字母表包含下述符号：(1)个体常项：a,b,c,…,ai,bi,ci,
5、…,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)括号与逗号：(,),，定义项的定义如下：(1)个体常项和个体变项是项.(2)若j(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则j(t1,t2,…,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.个体常项、变项是项，由它们构成的n元函
6、数和复合函数还是项定义设R(x1,x2,…,xn)是任意的n元谓词，t1,t2,…,tn是任意的n个项，则称R(t1,t2,…,tn)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4))等均为原子公式定义合式公式（简称公式）定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(ØA)也是合式公式(3)若A,B是合式公式，则(AÙB),(AÚB),(A®B),(A«B)也是合式公式(4)若A是合式公式，则"xA,$xA也是合式公式(5)只有有限次地应用(1)~(4)形成的符
7、号串是合式公式.请举出几个合式公式的例子.定义在公式"xA和$xA中，称x为指导变元，A为相应量词的辖域.在"x和$x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.例如,在公式"x(F(x,y)®G(x,z))中,A=(F(x,y)®G(x,z))为"x的辖域，x为指导变元,A中x的两次出现均为约束出现，y与z均为自由出现.闭式:不含自由出现的个体变项的公式.给定公式A="x(F(x)®G(x))成真解释:个体域N,F(x):x>2,G(x):x>1代入得A="x(x>2®x>1)真命题成假
8、解释:个体域N,F(x):x>1,G(x):x>2代入得A="x(x>1®x>2)假命题问:"xF(x)Ù$xØF(x)有成真解释吗？$xF(x)Ú"xØF(x)有成假解释吗？被解释的公式不一定全部包含解释中的4部分.闭式在任何解释下都是命题，注意不是闭式的公式
