一阶谓词逻辑教材

1、离散数学一阶/谓词逻辑2021-12-161离散数学逻辑学中的三段论1 凡有理数都是实数2 1/3是有理数3 1/3是实数2021-12-162在命题逻辑中无法表示其推理过程因为如果我们用P,Q,R分别表示命题1，2，3则, 按照三段论法，PQ R 可表示上述推理这就是命题逻辑的局限性三段论的论断显然正确，但在命题逻辑中PQR并不是重言式。取P=0，Q=0，R=1，就可弄假PQR故其不能正确反映三段论的推理过程离散数学原 因q 在命题逻辑中无法将所有命题之间的内在联系反映出来。命题逻辑中描述的三段论，即PQR，使R是与命题P、Q无关的独立命题。但实际上R是与命题P、Q有关的，只是这种关系在命题

2、逻辑中得不到反映。2021-12-163q 要反映这种内在联系,就要对简单命题作进一步分析,分析出其中的个体词,谓词,量词,研究它们的形式结构及逻辑关系,总结出正确的推理形式和规则,这就是一阶逻辑所研究的内容.一阶逻辑也称谓词逻辑.离散数学谓词与量词2021-12-164研究对象的全体所构成的集合.又称个体域。一阶逻辑中论域中的元素.又称个体词。1.论域：2.个体： 令P(x)表示x为质数，则P(x)为一元谓词。 令H(x，y)表示“x高于y”。则H(x，y)为二元谓词。 将x代以个体“张三”，y代以个体“李四”， 则H(张三,李四)就是命题“张三高于李四”。 注意：注意： P(x.y)与H(

3、x,y)为命题函数.而P(2)与H(张三,李四)才是命题。例：例：3.量词:在命题中表示数量的词.分两类.即存在与全称量词.离散数学概念的讨论o谓词是用来刻划个体的性质或个体之间的关系的。2021-12-165v谓词如有n个变元则称为n元谓词. n元谓词反映了n元关系.v变元在谓词中的次序直接影响了谓词的取值.如:谓词P(x,y)为“x比y高”.而张三为170cm,李四为180cm.则:P(李四,张三)为真命题. P(张三,李四)为假命题.v个体是可以独立存在的实体,它既可以是一个具体的事物,也可以是一个抽象的概念用个体,谓词表示命题的例子:离散数学例子:o1,武汉位于重庆与上海之间.2021

4、-12-166解:个体a,b,c分别表示武汉,重庆和上海,谓词P(x,y,z)表示x位于y与z之间,则命题表示为P(a,b,c).2,如果王英坐在李洪的后面,则王英比李红高.令a:王英;b:李红;P(x,y):x坐在y的后面;G(x,y):x比y高.则命题表示为P(a,b)G(a,b).离散数学三段论基于谓词的符号化：A(x):x是有理数，B(x):x是实数，则三段论可表示为：P：A(x) B(x) Q：A(1/3) R：B(1/3).2021-12-167P(A(x)B(x) (A(x) B(x) A(x) B(x)这样， P译为“所有有理数都不是实数”矛矛 盾盾原原 因因仅引进谓词还不足以

5、确切地刻画命题，例如仅引进谓词还不足以确切地刻画命题，例如:日常生活中，上述命题P为: “凡有理数都是实数”。而命题P的否定P,应理解成，“有些有理数不是实数”但是离散数学原因： 命题P的确切意思为：“对任意x，如果x是有理数，则x是实数”。但是，A(x)B(x)中并没有确切表达出“对任意x”这个意思。这说明， A(x)B(x)还不是一个命题。因此，在一阶逻辑中，除了引进谓词外，还需要引进语句“对任意x”，以及与之对偶的语句“存在一个x”。2021-12-168离散数学定义2021-12-169当且仅当对任意xD，G(x)均为真。当且仅当存在一个 x0D,使G(x0)为假。当且仅当存在一个x0

6、 D ，使G(x0) 为真；当且仅当对任意x D ， G(x)均为假。语句语句“对任意对任意x”称为全称量词，记为称为全称量词，记为:xx语句语句“存在一个存在一个x”称为存在量词，记为称为存在量词，记为 :设G（x）是一个一元谓词，D是论域。其真值规定为:,)(. 1为真xxG.)(,)(均为真对任意表示命题则xGDxxxG.)(,)(为真使存在一个表示命题xGDxxxG其真值规定如下：,)(. 1为真xxG为假，)(. 2xxG为假，)(. 2xxG离散数学两个重要的式子：2021-12-1610则，三段论法中的命题P 及P可符号化如下：此时，P确实是命题“凡有理数都是实数”的否定。 )(

7、)(xGxxxG)()(xGxxxG)()(:xBxAxP)()(xBxAxP)()(xBxAx当论域D为有限集时，如D=a1,a2 ,an，对于任意一元谓词G(X)，都有即消去了量词，化成了命题逻辑中等值的命题公式。注意：注意：)(.)()()(21naGaGaGxxG)(.)()()(21naGaGaGxxGx(A(x) B(x)离散数学2021-12-1611将命题符号化时，必须明确所涉及到的个体集合，即论域。例子：而我们约定，除非特别说明，所有论域均为由一切对象组成的个体集合。论域的讨论：令：M (x) : x 是人。D (x) : x 要死。对命题“人是要死的”如果论域是全人类，可符

8、号化为)(xxD如果论域是世界上一切生物，可符号化为)()(xDxMx离散数学2021-12-1612命题符号化的例子：命题符号化的例子：例例1：没有不犯错误的人令H（x）： x是人,M（x）： x犯错误例例2：闪光的未必都是金子令L（x）： x是闪光的, G（x）： x是金子例例3：存在着偶质数令E(x)：x是偶数,P(x)：x是质数).()()()(:xMxHxxMxHx则有).()()()(:xGxLxxGxLx则有则有：x(E(x)P(x)离散数学2021-12-1613例例4：每个自然数都有后继数令N（x）：x 是自然数,H（x,y）：y是x的后继数例例5：对平面上的任意两点，有且仅

9、有一条直线通过这两点令P（x）： x是一个点,L（x）：x是一条直线,T（x,y,z）：z通过x,y,E（x,y）：x等于y命题符号化的例子：命题符号化的例子：例例6：所有的人指纹都不一样令M(x)：x是人,D(x,y)：x与y相同,S(x,y)：x与y指纹相同).,()()(:yxHyNyxNx则有).,(),()(),()()()(:zuEuyxTuLuzyxTzLzyPxPyx则有).,(),()()(:yxSyxDyMxMyx则有离散数学习 题o(1)任何金属都可以溶解在某种液体中.o(2)每一个人的祖母都是他父亲的母亲.2021-12-1614解(1):令J(x):x是金属; E(x

10、):x是液体;S(x,y):x可以溶解在y中,);,()()(:yxSyEyxJx则可以表示为(2):令P(x):x是人;F(x,y):y是x的父亲;M(x,y):y是x的母亲;).,(),()(),()()(:yzMzxFzPzxyGyPxPyx则可以表示为G(x,y)x是y的祖母;离散数学o令P(x)为“x是质数”,E(x)为“x是偶数”,O(x)为“x是奇数”,D(x,y)为“x除尽y”.把下列各式译成汉语.2021-12-1615).,()()()()(.();,()()()()(.();(),()()()(.(yxDyPyxOxcyxDyEyxPxbxEyxDyxExa解: (a)

11、对所有x,若x是偶数,则对所有y,若x除尽y,则y是偶数.(b)对所有x,若x是质数,则存在y,y是偶数且x除尽y(c)对所有x,若x是奇数,则对所有y,y是质数,则x不能除尽y.(即所有质数能除尽某些偶数)(即任何奇数不能除尽任何质数).y离散数学2 合式公式及解释合式公式及解释2021-12-1616当论域D给出时，它可以是D中的某个元素。当论域D给出时，它可以是D中的任何一个元素。引进合式公式的概念，在形式化中使用的四种符号：第一，常量符号：a,b,c,ai,bi,ci i1第二，变量符号：x,y,z ,xi,yi,zi i 1第三，函数符号：f,g,h ,fi,gi,hi i 1第四，

12、谓词符号：P,Q,R ,Pi,Qi,Ri i 1当论域D给出时，n元函数符号f(x1，xn)可以是D n到D的任意一个映射。当论域D给出时，n元谓词符号P(x1，xn)可以是Dn到0,1的任意一个 谓词。离散数学项的定义：项的定义：2021-12-1617(1) 常量符号是项；(3) 若f(x1,xn)是n元函数符号，t1,tn是项，则f(t1,tn)是项；(2) 变量符号是项；(4) 只有有限次地使用(1),(2),(3)所生成的符号串才是项。例如：a,b,x,y是项，f(x,y)=x+y,g(x,y)=xy是项，f(a,g(x,y)=a+xy也是项。离散数学2021-12-1618原子与公

13、式：原子与公式：2.2. 设P(x1,xn)是n元谓词，t1,tn是项， 则称P(t1,tn)为原子公式，或简称原子。2.3. 一阶逻辑中的合式公式，也称为谓词公式，简称为公式，其递归定义为：（1）原子是合式公式；（2）若A是合式公式，则(A)也是合式公式；（3）若A,B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式；（4）若A是合式公式，x是A中的变量符号，（5）只有有限次地使用（1）（4）所生成的符号串才是合式公式。.,也是合式公式则xAxA 离散数学o 各命题符号化的结果都是合式公式。o 对于一个谓词，如果其中每一个变量都在一个量词的作用之下，则它就不再是命题函数

14、而是一个命题了。但是，这种命题和命题逻辑中的命题还是有区别的。因为这种命题中毕竟还有变量，尽管这种变量和命题函数中的变量有所不同。因此，有必要区分这些变量。2021-12-1619离散数学约束变量与自由变量约束变量与自由变量：1 在一个谓词公式中变量的出现说是约束的，当且仅当它出现在使用这个变量的量词作用域之内。2021-12-1620.),(),(,)(),(),(的出现是约束的中和谓词中公式xzxQyxPxRzxQyxPx3 至少有一次约束出现的变量，称为约束变量。至少有一次自由出现的变量，称为自由变量。2 变量的出现说是自由的，当且仅当它的出现不是约束的。 上例中的R(x)中x的出现是自

15、由的，y和z出现也是自由的。例子：例子：例子：上例中的x既是自由变量，又是约束变量，而y和z则是自由变量。)()(),()(yyGxxGyyGxxG显然有离散数学有关公式中变量的两条规则：改名规则： 将谓词公式中出现的约束变量改为另一个约束变量。此改名必须在量词作用域内各处以及该量词符号中进行，且改成的新约束变量要与改名区域中的其它变量有别。2021-12-1621代替规则：对公式中某变量的所有自由出现，用另一个与原公式中其它变量符号均不同的变量符号来代替。例子：),(),(,),(),(zxQyuuPuxzxQyxxP得改成将公式例子：),(),(,zuQyxxPux得代替用的对上例，可将自

16、由出现因此，通过使用改名规则和代替规则，可使一阶逻辑中的公式不出现某变量既是约束变量又是自由变量的情况。离散数学解释： 在一阶逻辑中,公式G的一个解释I,是由非空论域D和对G中常量符号、函数符号、谓词符号按下列规则进行的一组指定所组成。2021-12-16221) 对每个常量符号，指定D中一个元素；2) 对每个n元函数符号，指定一个函数，即指定一个Dn到D的映射；3) 对每个n元谓词符号，指定一个谓词，即指定一个Dn到0,1上的映射。注意：为统一起见，对以上定义中的公式规定：公式中无自由变量，或将自由变量看作常量。于是，每个公式在任何具体解释下总表示一个命题。离散数学2021-12-1623例

17、 子:.1:)3,3(;0:)2,3(;1:)3,2(;1:)2,2(;1:)3(;0:)2(;2)3(;3)2(;2:;3,2:)(,()(QQQQPPffaDIafxQxfPx并给出解释给出公式显然此公式在解释I下，取1值（为真）。因为：为真时取当)2(,2()2(,2fQfPx给出论域给出论域对公式中的常量对公式中的常量符号符号a指定为指定为2指定函数f另外x=3时，P(f(3)Q(3,f(2)为假，注意到对x的约束是存在量词x，故此公式在该解释下为真。离散数学习题o给定解释I如下: (1) Di:=2,3； (2) a=2； (3) 函数f(x)为f(2)=3，f(3)=2； (4)

18、谓词：F(x)为F(2):=0,F(3):=1; G(x,y)为G(i,j):=1,i,j=2,3; L(x,y)为L(2,2)=L(3,3):=1, L(2,3)=L(3,2)=:0.2021-12-1624在解释I下,求下列各式的真值.).,() 3();(,()()2();,()() 1 (yxyLxxfxGxfFxaxGxFx解：(F(2) G(2,2)(F(3) G(3,2) (0 1) (1 1)0.解：(F(f(2) G(2,f(2) (F(f(3) G(3,f(3) (F(3) G(2,3) (F(2) G(3,2) (1 1) (0 1)1.解：(L(2,2) L(2,3)

19、(L(3,2) L(3,3) 1 11.注意离散数学谓词公式的分类：定义定义 设G是一个谓词公式1如果存在解释I,使G在I 下为真（I 满足G），则称G是可满足的。2如果所有解释I均不满足G（弄假），则称G是恒假的，或不可满足的。3如果G的所有解释I都满足G，则称G是恒真的。2021-12-1625定理：定理：一阶逻辑的判定问题是不可解的，即不存在一个统一的算法，对一阶逻辑中的任何谓词公式G，A能够在有限步内判定公式G的类型。但，一阶逻辑是半可判定的，即如果谓词公式G是恒真的，那么，存在算法在有限步内能检验出G的恒真性。 解释I依赖于非空个体集合D，而D可以是无穷集合，D的数目也可是无穷的。故

20、要考虑公式的所有解释是很难的。离散数学判断下列公式的类型:2021-12-1626.),(,.),(),()3();,()2();(),() 1 (yxyxGQIyxQyxGyxGyxyxyxGQQyxyxyGx表示为命题变元的个体域为整数集其中离散数学解答:o(1)无论对Q指派何种命题常元,QQ的真值总是1.而在I中对任意的x,总存在y=1使x-1x+1成立2021-12-1627(2)因为x-yx+y在I中的真值不确定,当指派x=1,y=1时,x-yx+y取值为真.当指派x=4,y=-1时,x-yy.),()(yxxFyA令则A(y)是真命题,),(是假命题规则后的式子：但使用xxxFxU

21、G是错误的。故)()(xxAyA原因是条件2)不满足。)()(:)(xxAcAEG规则成立条件：1) c是特定的常量符号.2) 取代c的x在A(c)中没有出现过.)()(:)规则(xxAyAUG离散数学错误使用EG规则的例子2021-12-1652.)2(,)2(),2 ,()2(.: ),(,中出现过已在且为真命题则取令在实数集合中AxAxxFAyxyxF),()2(, 2,xxxFxAxEG则得到代替若用规则时在使用.)()2(,.),(,),(),(是错误的推理因此是一个假命题显然而xxAAxxxFxxxFxxxFx其原因是使用EG规则的条件2)不满足。离散数学存在指定规则存在指定规则(

22、ES规则规则):2021-12-1653)()(cAxxA成立条件：成立条件：1) c是使A(c)为真的常量符号;),()(,)2acaBxxB则比如则在此之前也使用过该规若推理过程中3)A(x)中的自由变元只有x.例如：例如：设D为自然数集, F(x)表示“x是奇数”，G(x)表示“x是偶数”.)()(是真命题则xxGxxF离散数学2021-12-1654但，若不注意使用条件，则有：)()()1 (xxGxxF前提引入)()2(xxF化简，根据（1）)() 3(cFES规则，根据（2）)()4(xxG化简，根据（1）)()5(cGES规则，根据（4）)()()6(cGcF合取，根据（3），（

23、5）)()()7(xGxFxEG规则，根据（6）于是得出：)()()()(xGxFxxxGxxF（）违反了条件2）离散数学例 1 证明：2021-12-1655)()()()()()(xCxBxxAxcxxBxAx推理过程如下：)()() 1 (xBxAx前提引入)()()2(yByAUS规则，根据（1）)()() 3(xAxcx前提引入)()()4(aAaCES规则，根据（3）)()5(aC化简，根据（4）)()6(aA化简，根据（4）)()7(aB假言推理，根据（2），（6）)()()8(aCaB合取，根据（5），（7）)()()9(xCxBxEG规则，根据（8）在推理过程中，y被指定为论

24、域中的任一个体，a被指定为论域中的某一个体。对于(2)和(6)，在使用假言推理时，由于y是任一个体，因此，可以选为某一个体a，故得(7)。 离散数学本例也可作如下推理：2021-12-1656)()()1(xAxCx前提引入ES规则，根据（1）)()3(aA化简，根据（2）)()()4(xBxAx前提引入)()()5(aBaAUS规则，根据（4）)()6(aB假言推理，根据(3)，(5)()7(aC化简，根据（2）)()()8(aCaB合取，根据（6），（7）)()()9(xCxBxEG规则，根据（8）)()()2(aAaC离散数学2021-12-1657例例 2 证明： 苏格拉底三段论“凡人

25、都是要死的，苏格拉底是人，所以苏格拉底是要死的”。证明证明:结论: D(a)首先将命题符号化：M(x):x是人. D(x):x是要死的. a:苏格拉底.)(),()(aMxDxMx前提:证明:)()() 1 (xDxMx)()()2(aDaM)() 3(aM)()4(aD前提引入US规则，（1）前提引入假言推理，（2），（3）离散数学例例 3o 有些病人相信所有的医生，但是病人都不相信骗子。证明：医生都不是骗子。o 证明：v 命题符号化： P(x):x是病人；D(x):x是医生；Q(x):x是骗子；R(x,y):x相信y。v 前提：x(P(x)y(D(y)R(x,y)， xy(P(x)Q(y)

26、R(x,y)v 结论：x(D(x)Q(x)v 推理：2021-12-1658离散数学1)x(P(x)y(D(y)R(x,y) 前提引入2)P(c)y(D(y)R(c,y) ES，(1)3)xy(P(x)Q(y)R(x,y) 前提引入4)y(P(c)Q(y)R(c,y) US，(3)5)P(c)Q(z)R(c,z) US，(4)6)(P(c)Q(z)R(c,z) 蕴涵等值式，(5)7)P(c)Q(z)R(c,z) De Morgan律,(6)8)P(c)(Q(z)R(c,z) 蕴涵等值式，(7)9)P(c) 化简，(2)10)Q(z)R(c,z) 析取三段论，(8)，(9)11)R(c,z)Q(z) 等值演算，(10)12)y(D(y)R(c,y) 化简，(2)13)D(z)R(c,z) US，(12)14)D(z)Q(z) 假言三段论，(11)，(13)15)x(D(x)Q(x) UG，(14) 2021-12-1659离散数学例例 4：指出下面推理的错误：指出下面推理的错误1) x(F(x)G(x) 前提引入2) F(y)G(y) US，(1)3) xF(x) 前提引入4) F(y) ES，(3)5) G(y) 假言推理，(2),(4)6) xG(x) UG，(5)2021-12-1660没有满足ES规则的条件