离散数学标准讲义sy第2章

2020/1/24离散数学1第二章一阶逻辑2020/1/24离散数学2所有的人都是要死的。苏格拉底是人，所以苏格拉底是要死的。2020/1/24离散数学3命题逻辑的局限符号化：P:所有的人都是要死的。Q:苏格拉底是人，R:所以苏格拉底是要死的。P∧Q→R推理正确吗?说明：命题逻辑不能表现出简单命题中各部分的内在联系。2020/1/24离散数学4本章概要一阶逻辑，又称一阶谓词逻辑或谓词逻辑。对一阶逻辑的研究能够克服命题逻辑的局限性，对简单命题进行进一步的分解，以表达出个体和总体间的内在联系和数量关系。2020/1/24离散数学5一阶逻辑知识结构2.1一阶逻辑基本概念2.2一阶逻辑等值演算2.3一阶逻辑的推理理论第四次课第一、二次课第三次课2020/1/24离散数学6一阶逻辑基本概念知识点谓词和量词概念一阶逻辑命题的符号化（特性谓词）谓词公式基本概念谓词公式的解释谓词公式的分类2020/1/24离散数学7谓词和量词一个简单命题中表示研究对象即主体或客体(对应名词成分)的词称为个体词。表示一个个体词性质的或多个个体词之间关系的词称为谓词。例：小张是学生。小张在跑步。小张比小李高2cm。X是我的同学。2020/1/24离散数学8谓词和量词个体词个体常项表示具体的、特指的个体的词用a,b,c…表示个体变项表示抽象的、泛指的或在一定范围内变化的个体的词用x,y,z…表示个体域个体变项的取值范围全总个体域2020/1/24离散数学9谓词和量词谓词谓词常项：表示具体性质或关系的谓词谓词变项：表示抽象的或泛指的性质或关系的谓词用F,G,H…表示0元谓词：不包含有个体变项的谓词n元谓词：包含有n个体变项的谓词例：（1）3是整数。（2）x和y具有关系L。（3）小张和小李是同学。2020/1/24离散数学10全称量词和存在量词符号化:(1)所有的人都是要死的。(2)有的人活百岁以上。量词：表示个体常项或变项之间数量关系的词全称量词用∀表示，形成的命题形式为∀xF(x)，即“对所有的x，F(x)为真”。存在量词用∃表示，形成的命题形式为∃xF(x)，即“存在x值，使F(x)为真”。2020/1/24离散数学11一阶逻辑命题符号化例：在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡是人都要呼吸.(2)有的人用左手写字.其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域.解答2020/1/24离散数学12(1)凡是人都要呼吸.解：(a)个体域D1为人类集合(b)个体域D2为全总个体域.为将人从全总个体域中分离出来，令呼吸。xxF:)()(xxF))()((xFxMx是人。xxM:)(2020/1/24离散数学13(2)有的人用左手写字.解:(a)个体域D1为人类集合；(b)个体域D2为全总个体域.用左手写字。xxG:)()(xxG))()((xGxMx2020/1/24离散数学14一阶逻辑命题符号化例：在个体域限制为(a)和(b)条件时，将下列命题符号化:(1)对于任意的x，均有x2-3x+2=(x-1)(x-2).(2)存在x，使得x+5=3.其中:(a)个体域D1=N(N为自然数集合)(b)个体域D2=R(R为实数集合)解答2020/1/24离散数学15(1)对于任意的x，均有x2-3x+2=(x-1)(x-2)解：令(a)个体域D1=N(N为自然数集合)命题符号化为：)2)(1(23:)(2xxxxxF)(xxF)(xxF(b)个体域D2=R(R为实数集合)命题符号化为：TT)2)(1(23:)(2xxxxxF)(xxF真值：真值：2020/1/24离散数学16（2）存在x，使得x+5=3.解:令(a)个体域D1=N(N为自然数集合)命题符号化为：35:)(xxG(b)个体域D2=R(R为实数集合)命题符号化为：)(xxG)(xxG真值：真值：FT2020/1/24离散数学17一阶逻辑命题符号化例：将下列命题符号化，并讨论真值.(1)所有的人都长着黑头发.解：定义特性谓词M(x)：x是人。定义谓词F(x)：x长着黑头发。))()((xFxMx真值：F2020/1/24离散数学18(2)有的人登上过月球.解：定义特性谓词M(x)：x是人。定义谓词F(x)：x登上过月球。))()((xFxMx真值：T2020/1/24离散数学19(3)没有人登上过木星.解：定义特性谓词M(x)：x是人。定义谓词F(x)：x登上过木星。))()((xFxMx真值：T))()((xFxMx2020/1/24离散数学20(4)在美国留学的学生未必都是亚洲人.解：定义特性谓词M(x)：x是在美国留学的学生。定义谓词F(x)：x是亚洲人。))()((xFxMx真值：T))()((xFxMx2020/1/24离散数学21例：将下列命题符号化。(1)兔子比乌龟跑得快.解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。定义谓词H(x,y)：x比y跑得快。)),()()((yxHyGxFyx2020/1/24离散数学22(2)有的兔子比所有的乌龟跑得快.解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。定义谓词H(x,y)：x比y跑得快。)),()()((yxHyGxFyx))),()(()((yxHyGyxFx2020/1/24离散数学23(3)并不是所有的兔子都比乌龟跑得快.解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。定义谓词H(x,y)：x比y跑得快。)),()()((yxHyGxFyx2020/1/24离散数学24(4)不存在跑得同样快的两只兔子.解：定义特性谓词F(x)：x是兔子。G(y):y是乌龟。定义谓词L(x,y)：x和y跑得一样快。)),()()((yxLyFxFyx)),()()((yxLyFxFyx2020/1/24离散数学25几点说明：一般说来，多个量词出现时，它们的顺序不能随意调换.有些命题的符号化形式可不止一种.2020/1/24离散数学26谓词公式知识点谓词公式指导变元、辖域自由出现、约束出现谓词公式的解释谓词公式的分类2020/1/24离散数学27定义2.1.1一阶语言的字母表定义如下:(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)括号与逗号:(,),,一阶语言2020/1/24离散数学28定义2.1.2的项的定义如下:(3)有限次使用(1)，(2)所得到的符号串都是项.(1)个体常项和个体变项是项.(2)若(x1,x2,…,xn)是任意的n元函数,t1,t2,…,tn是任意的n个项，则(t1,t2,…,tn)是项.2020/1/24离散数学29例:1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式．定义2.1.3原子公式设R(x1,x2,…,xn)是任意的n元谓词,t1,t2,…,tn是的任意的n个项，则称R(t1,t2,…,tn)是的原子公式.2020/1/24离散数学30定义2.1.4的合式公式定义如下:(1)原子公式是合式公式.(2)若A是合式公式，则(┐A)也是合式公式.(3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A↔B)也是合式公式.(5)只有有限次的应用(1)～(4)构成的符号串才是合式公式.(4)若A是合式公式，则也是合式公式.,xAxA合式公式也称为谓词公式，简称公式.2020/1/24离散数学31定义2.1.5在公式和中，称x为指导变元，A为相应量词的辖域。在和的辖域中,x的所有出现都称为约束出现.A中不是约束出现的其他变项均称为是自由出现的.xAxAxx自由与约束2020/1/24离散数学32例指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项:(1)((,)(,))(2)(()())(()(,,))xFxyGxzxFxGyyHxLxyz2020/1/24离散数学33解：(1)x是指导变元.量词的辖域A=(F(x,y)→G(x,z))，在A中，x是约束出现的.而且约束出现两次，y和z均为自由出现的，而且各自由出现一次.(1)((,)(,))xFxyGxz2020/1/24离散数学34解：(2)公式中含有两个量词，前件上的量词的指导变元为x，的辖域A=(F(x)→G(y))，其中x是约束出现的，y是自由出现的.(2)(()())(()(,,))xFxGyyHxLxyz后件中的量词的指导变元为y，的辖域为(H(x)∧L(x,y,z))，其中y是约束出现的，x,z均为自由出现的.在整个公式中，x约束出现一次，自由出现2次，y自由出现一次，约束出现一次，z只自由出现一次.2020/1/24离散数学35则Δx1A(x1,x2,…,xn)是含有x2,x3,…,xn自由出现的公式，可记为A1(x2,…,xn)。类似的,Δx2Δx1A(x1,x2,…,xn)可记为A2(x3,x4,…,xn)，Δxn-1Δxn-2…Δx1A(x1,x2,…,xn)中只含有xn是自由出现的个体变项，可以记为An-1(xn)。而Δxn…Δx1A(x1,x2,…,xn)已经没有自由出现的个体变项了。为方便起见，用A(x1,x2,…,xn)表示含x1,x2,…,xn自由出现的公式，并用Δ表示任意的量词(或)。2020/1/24离散数学36定义2.1.6：设A是任意的公式,若A中不含有自由出现的个体变项，则称A为封闭的公式，简称闭式.闭公式要想使含有r(r≥1)个自由出现个体变项的公式变成闭式，至少要加上r个量词.))()((xGxFx)),()((yxGxFyx)),()((yxGxFx闭式不是闭式2020/1/24离散数学37换名规则将量词辖域中的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中没有出现的个体变项符号，公式中的其它部分不变。例：),()(yxGxxF),()(yxGzzF2020/1/24离散数学38代替规则对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。例：),()),(),((yxxHzyLyxRyx((,)(,))(,)xyRxyLyzxHxw2020/1/24离散数学39一阶公式的解释由以上讨论可知,按中合式公式的形成规则形成的符号串是中的公式,这种公式没有确定的意义。一旦将其中的变项(项的变项,谓词的变项）等用指定的常项代替后，所得公式化就具备一定的意义,有时就变成了命题.2020/1/24离散数学40例:将下列两个公式中的变项指定成常项使其成为命题:(1)x(F(x)→G(x))(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))2020/1/24离散数学41解：(1)指定个体变项的变化范围，并且指定谓词F,G的含义，下面给出两种指定法:(a)令个体域D1为全总个体域，F(x)为x是人，G(x)为x是黄种人，则表达的命题为“所有人都是黄种人”，这是假命题.(b)令个体域D2为实数集合R，F(x)为x是自然数，G(x)为x是整数，则表达的命题为“自然数都是整数”,这是真命题.(1)x(F(x)→G(x))2020/1/24离散数学42(2)式中含有函数变项，1元谓词变项，2元谓词变项。指定个体域为全总个体域,F(x)为x是实数,G(x,y)为x≠y，H(x,y)为xy，f(x,y)=x2+y2,g(x,y)=2xy，则上式表达的命题为“对于任意