《离散数学课件：第2章 一阶逻辑1》由会员分享，可在线阅读，更多相关《离散数学课件：第2章 一阶逻辑1（30页珍藏版）》请在金锄头文库上搜索。
1、1第第2章章一阶逻辑一阶逻辑2.1一阶逻辑基本概念一阶逻辑基本概念2.2一阶逻辑合式公式及解释一阶逻辑合式公式及解释2.3一阶逻辑等值式与前束范式一阶逻辑等值式与前束范式 22.1一阶逻辑基本概念一阶逻辑基本概念 个体词个体词 谓词谓词 量词量词 一阶逻辑中命题符号化一阶逻辑中命题符号化 命题逻辑的局限性命题逻辑的局限性苏格拉底三段格拉底三段论：凡是人都要死的凡是人都要死的.苏格拉底是人格拉底是人.所以所以苏格拉底是要死的格拉底是要死的.在命在命题逻辑中，只能用中，只能用p、q、r表示以上表示以上3个命个命题，上述推理上述推理的的形式形式结构构是：是：(pq)r但但这不是重言式不是重言式，无法
2、用命无法用命题逻辑来来证明明这个推个推理的正确性理的正确性34基本概念基本概念个体词、谓词、量词个体词、谓词、量词个体词（个体）个体词（个体）:所研究对象中可以独立存在的具所研究对象中可以独立存在的具体或抽象的体或抽象的客体客体具体的，称具体的，称个体常项个体常项，用，用a,b,c表示表示抽象的，称抽象的，称个体变项个体变项，用，用x,y,z表示表示个体域个体域:个体变项的取值范围个体变项的取值范围有限个体域有限个体域，如，如a,b,c,1,2元素有限元素有限无限个体域无限个体域，如，如N,Z,R,元素无限元素无限全总个体域全总个体域:宇宙间的一切宇宙间的一切5基本概念基本概念(续续)谓词谓词
3、:表示表示个体性质或或个体间相互关系的词的词谓词常项谓词常项：如：如F(a)，表示，表示“a是人”具体具体谓词变项谓词变项：F(x)，表示，表示“x具有性质F”抽象抽象表示事物的性质，以表示事物的性质，以一元谓词一元谓词表达；表达；表示事物间关系，以表示事物间关系，以多元谓词多元谓词(n元谓词元谓词,n 2)表达表达如如L(x,y)：x与与y有关系有关系L，L(x,y)：x y，还有不含个体变项的还有不含个体变项的0元谓词（常项或变项）元谓词（常项或变项）,这时这时就退化为就退化为命题常项或命题变项命题常项或命题变项6基本概念基本概念( (续续) )量词量词:陈述中表示数量的词陈述中表示数量的
4、词全称量词全称量词 表示任意的、所有的、表示任意的、所有的、一切的，等等一切的，等等 x 对（个体域中）所有的对（个体域中）所有的x 而言而言存在量词存在量词 表示存在、有的、表示存在、有的、至少一个，等等至少一个，等等 x（在个体域中）存在（在个体域中）存在x7一阶逻辑中命题符号化一阶逻辑中命题符号化 例例用用0元谓词元谓词将命题符号化将命题符号化要求要求(1)在命题逻辑中符号化；在命题逻辑中符号化；(2)在一阶逻辑中符号化在一阶逻辑中符号化(1)墨西哥位于南美洲墨西哥位于南美洲在命题逻辑中在命题逻辑中,设设p: 墨西哥位于南美洲墨西哥位于南美洲 符号化为符号化为 p在在一一阶阶逻逻辑辑中中
5、,设设a：墨墨西西哥哥，F(x)：x位位于于南美洲南美洲,符号化为符号化为F(a)8例例(续续)(2)是无理数仅当是无理数仅当是有理数是有理数在命题逻辑中在命题逻辑中,设设p：是无理数，是无理数，q：是有理数是有理数.符号化为符号化为p q在一阶逻辑中在一阶逻辑中,设设F(x):x是无理数是无理数,G(x):x是有理数是有理数符号化为符号化为在命题逻辑中在命题逻辑中,设设p：23，q：3y，G(x,y)：x3，则，则3y 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是有理数是
6、有理数, L(x,y)：xy x(F(x) y(G(y) L(x,y)（或（或 x y(F(x) G(y) L(x,y)两者等值）两者等值）11一阶逻辑中命题符号化一阶逻辑中命题符号化( (续续) )几点注意：几点注意：n一一元元谓谓词词（表表单单个个性性质质）与与多多元元谓谓词词（表表多多个个关关系系）使使用的区分用的区分n无特别指定无特别指定, ,视作用视作用全总个体域全总个体域, ,需引入需引入特性谓词特性谓词n使用全称量词使用全称量词 x 、存在量词、存在量词 x 的符号化的符号化句式不同句式不同;有限个体域有限个体域时，量词表达时，量词表达可转换为列举表达可转换为列举表达n量词顺序一
7、般不能颠倒量词顺序一般不能颠倒n否定句式的等价表达否定句式的等价表达，如如“没有不呼吸的人没有不呼吸的人”等同于等同于“所有的人都呼吸所有的人都呼吸”“不不是是所所有有的的人人都都喜喜欢欢吃吃糖糖”等等同同于于“存存在在不不喜喜欢欢吃吃糖糖的的人人”122.2一阶逻辑公式及解释一阶逻辑公式及解释合式公式合式公式( (简称公式简称公式) )个体变项的自由出现和约束出现个体变项的自由出现和约束出现解释与赋值解释与赋值公式分类公式分类 永真式，矛盾式永真式，矛盾式, , 可满足式可满足式 13字母表字母表 一阶逻辑公式用到的字母表一阶逻辑公式用到的字母表包含下述符号：包含下述符号：(1)个体常项：个
8、体常项：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项项 项项定义如下：定义如下：(1)个体常项和个体变项是项个体常项和个体变项是项.(2)若若 (x1,x2,xn)是任意的是任意的n元函数，元函数，t1,t2,tn是任意的是任意的n个项，则个项，则 (t1,t2,tn)是项是项.(3)所有的项都是有限
9、次使用所有的项都是有限次使用(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合式公式合式公式 定义定义合式公式
10、合式公式（简称（简称公式公式）定义如下：）定义如下：(1)原子公式是合式公式原子公式是合式公式.(2)若若A是合式公式，则是合式公式，则( A)也是合式公式也是合式公式(3)若若A,B是合式公式，则是合式公式，则(A B),(A B),(AB),(AB)也是合式公式也是合式公式(4)若若A是合式公式，则是合式公式，则 xA, xA也是合式公式也是合式公式(5)只有有限次地应用只有有限次地应用(1)(4)形成的符号串是合形成的符号串是合式公式式公式.如如x 0, x (F(x)G(x), x y(x+y=1)17个体变项的自由出现与约束出现个体变项的自由出现与约束出现 定义定义2.5在在公公式式
11、 xA和和 xA中中，称称x为为指指导导变变元元，A为为相相应应量词的量词的辖域辖域.在在 x和和 x的的辖域中，辖域中，x的所有出现都的所有出现都称称为为约约束束出出现现，A中中不不是是约约束束出出现现的的其其他他变变项项均均称称为是为是自由出现自由出现.例如例如, , 在公式在公式 x(x( F( F(x x, y), y)G(G(x x, z) , z) ) ) 中中, , x x的辖域为的辖域为( ( F(F(x x, y), y)G(G(x x, z) , z) ) ) 记为记为A A， x x为指导变元为指导变元, A, A中中x x的两次出现均为的两次出现均为约束出现约束出现，
12、y y与与z z均为均为自由出现自由出现. . 闭式闭式:不含自由出现的个体变项的公式不含自由出现的个体变项的公式.18换名和代入规则换名和代入规则当当公公式式中中同同一一个个变变项项符符号号既既有有约约束束出出现现又又有有自自由由出出现现时时，容容易易造造成成混混乱乱。这这时时可可采采用用换换名名或或代代入入，公式的意义不变。公式的意义不变。换换名名: : 将将某某指指导导变变项项及及其其在在辖辖域域中中所所有有约约束束出出现现替替换为公式中未曾出过的变项符号换为公式中未曾出过的变项符号( (字母）字母）代代入入：也也可可将将公公式式中中自自由由出出现现的的同同一一种种个个体体变变项项符符号
13、号 改改为为未未出出现现过过的的变变项项符符号号（字字母母），其其余余部部分分不变，所得公式与原公式等值不变，所得公式与原公式等值19公式的解释与分类公式的解释与分类 给定给定闭式闭式A= x(F(x)G(x)给定个体域给定个体域为为N,确定谓词确定谓词：F(x):x2,G(x):x1代入得代入得A= x(x2x1)成为命题（真）成为命题（真）给定给定非闭式非闭式B= xF(x,y)取个体域取个体域为为N,确定谓词确定谓词F(x,y):x y代入得代入得B= x(x y)还不是命题还不是命题当当对自由变项赋值对自由变项赋值：令：令y=1, 则则B= x(x 1)成为命题成为命题（假）（假）20
14、解释和赋值解释和赋值 一般地，只要一般地，只要给定解释和赋值给定解释和赋值,任何公式都成为命题任何公式都成为命题.解释解释I：由下面由下面4部分组成：部分组成：(a)非空个体域非空个体域DI(b)对公式中每一个体常项对公式中每一个体常项a指定一个指定一个 DI(c)对公式中每一个函数符号对公式中每一个函数符号f指定一个指定一个DI上的函数上的函数(d)对公式中每一个谓词符号对公式中每一个谓词符号F指定一个指定一个DI上的谓词上的谓词赋值赋值 ：对个体变项对个体变项x指定个体域中的值指定个体域中的值 (x) DI“公公式式A在在解解释释I和和赋赋值值 下下”指指：取取个个体体域域DI,并并将将公
15、公式式中中出出现现的的a、f、F分分别别解解释释成成具具体体的的、,把把自自由由出出现现的的x换成换成 (x)后所得到的命题后所得到的命题.21实例实例例例 给定给定解释解释I I 如下如下: : (a)个体域个体域D=N(b)(c)(d)谓词谓词以及以及赋值赋值 ： (x)=0, (y)=1, (z)=2.说明下列公式在说明下列公式在I 与与 下的涵义下的涵义,并讨论真值并讨论真值(1) xF(g(x,a),y) x(2x=1)假命题假命题22例例(续续)(2) xF(f(x,a),y)yF(x,f(y,a) x(x+2=1)y(0=y+2)真命题真命题 x y z (x+y=z)真命题真命
16、题(3) xF(f(x,y),g(x,z) x(x+1=2x)真命题真命题(5) x y zF(f(y,z),x) x y z (y+z=x)假命题假命题(4) x y zF(f(x,y),z)如果是闭式，只需要解释，不需赋值如果是闭式，只需要解释，不需赋值,如如(4),(5)23公式的分类公式的分类 永真式永真式( (逻辑有效式逻辑有效式) ): :在任何解释和赋值下为真命题在任何解释和赋值下为真命题矛盾式矛盾式( (永假式永假式) ): :在任何解释和赋值下为假命题在任何解释和赋值下为假命题可满足式可满足式：存在成真的解释和赋值：存在成真的解释和赋值说明：说明：永真式为可满足式，但反之不真
17、永真式为可满足式，但反之不真谓谓词词公公式式的的可可满满足足性性（永永真真性性, ,永永假假性性) )一一般般是是不不可判定的可判定的24代换代换 定义定义设设A0是含是含命题变项命题变项p1,p2,pn的的命题公式命题公式， A1,A2,An是是n个个谓词公式谓词公式，用，用Ai处处代替处处代替A0中的中的pi (1 i n) ，所得公式，所得公式A称为称为A0的的代换实例代换实例.如如F(x)G(x), xF(x)yG(y)是是pq的的代换实例代换实例定定理理重重言言式式的的代代换换实实例例都都是是永永真真式式，矛矛盾盾式式的代换实例都是矛盾式的代换实例都是矛盾式.实例实例例例判断下列公式
18、判断下列公式的的类型型(1)xF(x)xF(x)；25设I为任意的解任意的解释，若，若xF(x)为假，假，则xF(x)xF(x)为真真.若若xF(x)为真，真，则xF(x)也也为真，所以真，所以xF(x)xF(x)也也为真真.是是逻辑有效式有效式.(2)xF(x)(xyG(x,y)xF(x)；这是重言式是重言式p(qp)的代的代换实例，是例，是逻辑有效式有效式.例例(续)(3)xF(x)(xF(x)yG(y)；26重言式重言式p(pq)的代的代换实例例,是是逻辑有效式有效式.(4) (F(x,y)R(x,y)R(x,y)；矛盾式矛盾式 (pq)q的代的代换实例例,是矛盾式是矛盾式.例例(续)(
19、5)xyF(x,y)xyF(x,y).27取解取解释I：个体域：个体域N,F(x,y)为x=y.公式被解公式被解释为xy(x=y)xy(x=y)，其，其值为假假.解解释I:个体域个体域N,F(x,y)为x y,得到一个新的得到一个新的在在I下下,公式被解公式被解释为xy(x y)xy(x y)，其，其值为真真.于是，可判定于是，可判定这是是非非逻辑有效式的可有效式的可满足式足式.例例(续)(6)xF(x,y)28取解取解释I：个体域：个体域N,F(x,y)为xy.赋值 1： 1(y)=1.在在I和和 1下下,有有x(x1)，真命，真命题.(此此处自然数包括自然数包括0)在相同的解在相同的解释I下，取下，取赋值 2： 2(y)=0.在在I和和 2下下,有有x(x0，存在0，使得当0|x-a| 时，有|f(x)-b| .30
