离散数学：第二章2-2 一阶逻辑合式公式及解释

1第2章一阶逻辑2.1一阶逻辑基本概念2.2一阶逻辑合式公式及解释2.3一阶逻辑等值式第二章一阶逻辑22.2一阶逻辑公式及解释合式公式(简称公式)个体变项的自由出现和约束出现解释与分类3一阶逻辑合式公式采用字母表

定义2.1字母表个体常项：a,b,c,…,ai,bi,ci,….,

i≥1;个体变项：x,y,z,…,xi,yi,zi,….,

i≥1;函数符号：f,g,h,…,fi,gi,hi,….,

i≥1;谓词符号：F,G,H,…,Fi,Gi,Hi,i≥1;量词符号：，；联结词：┐，∧，∨，→，↔；括号和逗号:(,).4项的递归定义

定义2.2个体常项和变项是项；若

（x1,x2,….,xn）是任意的n元函数，t1,t2,….,tn是项，则

（t1,t2,….,tn）是项。只有有限次地使用①、②生成的符号串才是项。个体常项、变项是项，由它们构成的n元函数和复合函数还是项.5原子公式

定义2.3

设R(x1,x2,…,xn)是任意的n元谓词，t1,t2,…,tn是任意的n个项，则称R(t1,t2,…,tn)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4))等均为原子公式6合式公式的递归定义定义2.4:合式公式原子公式是合式公式；若A是合式公式，则(┐A)是合式公式；若A,B是合式公式，则(A∧B),(A∨B),(A→B),(AB)也是合式公式；若A是合式公式，则

xA，xA也是合式公式；只有有限次地应用－构成的符号串才是合式公式。7二、个体变项的自由出现与约束出现

定义2.5

在公式

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均为自由出现.例指出下列各合式公式中的指导变项、辖域、个体变项的自由出现和约束出现。

x(F(x)→H(x,y))

xF(x)∧G

(x,y)

x

y(R(x,y)∨L(y,z))∧

xH(x,y)变项既约束出现，又自由出现！89封闭的合式公式

闭式：不含自由出现的个体变项的公式.

x(F(x)→G(x)),x

y(F(x)∨G(x,y))

是闭式。

x(F(x)→G(x,y)),zyL(x,y,z)

不是闭式。

xF(x)∨G(x)

不是闭式。10换名规则换名规则：将量词辖域中出现的某个约束出现的个体变项及对应的指导变项,改成另一个辖域中未曾出现的个体变项符号,公式其余部分不变.例：在

xF(x)∧G(x,y)中,将约束出现的x改成z,得到的公式为:

zF(z)∧G(x,y)11代替规则代替规则:对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替,且处处代替.如：在

xF(x)∧G(x,y)中,利用代替规则,将自由出现的x用z代替,得

xF(x)∧G(z,y)12定义2.7一个解释I由下面4部分组成非空个体域D;D中一部分特定元素;D上一些特定的函数;D上一些特定的谓词;

在使用一个解释I解释一个公式A时,将A中的个体常项用I中特定常项代替,函数和谓词用I中的特定函数和谓词代替.

三、公式的解释与分类

13解释给定公式A=

x(F(x)

G(x))成真解释:个体域N,F(x):x>2,G(x):x>1

代入得A=

x(x>2

x>1)真命题成假解释:个体域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)有成假解释吗？14解释I如下:DI={2,3};DI中特定元素a=2;函数f(x)为f(2)=3,f(3)=2;谓词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.在解释I下,求下列各式的真值.(1)x(F(x)∧G(x,a))(2)x(F(f(x))∧G(x,f(x)))(3)xyL(x,y)例15例解释N个体域为自然数集合DN;DN中特定元素a=0;DN上特定函数f(x,y)=x+y,g(x,y)=x·y;DN上特定谓词F(x,y)为x=y.在解释N下,下面那些公式为真?那些公式为假?(1)xF(g(x,a),x);(2)xy(F(f(x,a),y)→F(f(y,a),x));(3)F(f(x,y),f(y,z))16公式的分类

设A为一公式(谓词公式)

如果A在任何解释下都是真的,称A为逻辑有效式(或永真式);

如果A在任何解释下都是假的,称A为矛盾式(或永假式);

若至少存在一个解释使A为真,则称A是可满足式.17代换实例

设A0是含命题变项p1,p2,…,pn的命题公式,A1,A2,…,An是n个谓词公式,用Ai(1≤i≤n)处处代替pi,所得公式A称为A0的代换实例.例如：F(x)→G(X),xF(x)→

xG(x)都是p→q的代替实例.代换实例应用：命题公式中永真式的代换实例在谓词公式中的永真式(逻辑有效式).命题公式中矛盾式的代换实例仍是矛盾式.18例题2.9判断哪些是永真式,哪些是矛盾式?xF(x)→xF(x)xF(x)→(xyG(x,y)→xF(x))解：设I为任意的解释,其个体域为D。

若存在x0

D,使得F(x0)为假,xF(x)为假,所以xF(x)→xF(x)为真.

对于任意x

D，F(x)为真,则xF(x),xF(x)同时为真.

所以xF(x)→xF(x)是永真式