离散数学-谓词演算基础永真性和可满足性省公开课一等奖全国示范课微课金奖课件

第三章谓词演算基础3.1谓词与个体3.2函数与量词3.3自由变元和约束变元3.4永真性和可满足性

3.4.1真假性3.4.2同真假性、永真性和可满足性3.4.3范式3.5唯一性量词与摹状词第1页

真假性：四个原因

(1)个体域

设A(e)表示e为偶数，考查

xA(x)

当个体域I为{1，2，3}时，公式值为假；

当个体域I为{2，4，6}时，公式值为真。第2页

真假性：四个原因

(2)自由变元设A(e)表示e为偶数，考查

A(x)

当x取2时，其值为T；

当x取为3时，其值为F。第3页

真假性：四个原因

(3)谓词变元

个体域I={2，4，6，8}.考查

xA(x)当A(e)表示e为偶数时，

xA(x)=T；当A(e)表示e为奇数时，

xA(x)=F；第4页

真假性：四个原因

(4)命题变元

个体域I={2，4，6，8}，A(e)表示e为偶数.

考查

xA(x)

P

当P=T时，公式值为真；当P=F时，公式值为假。第5页谓词演算公式

设

为任何一个谓词演算公式， 其中自由变元为x1，x2，…，xn； 谓词变元为X1，X2，…，Xm； 命题变元为P1，P2，…，Pk。此时

可表示为：

(x1，…，xn；X1，…，Xm；P1，…，Pk)第6页谓词演算公式解释

设个体域I解释为常个体域I0；

自由变元x1，…，xn解释为：

I0中个体a1，…，an；

谓词变元X1，…，Xm解释为：

I0上谓词A1，…，Am；

命题变元P1，…，Pk解释为：

P10，…，Pk0，其中Pi0=T或F(i=1，2，…，k)。第7页成真解释、成假解释给定公式

一个解释：

(I0；a1，…，an；A1，…，Am；P10，…，Pk0)公式

在该解释下值记为：

(a，A，P0)=

(a1，…，an；A1，…，Am；P10，…，Pk0)若(a，A，P0)=T，则称(I0；a；A；P0)为成真解释；若(a，A，P0)=F，则称(I0；a；A；P0)为成假解释。第8页含有量词谓词演算公式设个体域I中全部实体变元为a1，a2，…，an，则有：

x

(x)=(a1)(a2)…

(an)

x

(x)=(a1)(a2)…

(an)第9页含有量词谓词演算公式真假性

x

(x)为真

个体域I中每一个个体均使得

取为真

x

(x)为真

个体域I中有一个个体使得

取为真第10页例在给定解释下，求

x(F(x)

G(x,a))给定解释①I＝{2,3};②I中特定元素a=2；③函数为f(2)=3,f(3)=2;④谓词F(x)为F(2)=0,F(3)=1G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0解：原式=(F(2)

G(2,a))

(F(3)

G(3,a))=(00)

(1

0)=00=0第11页例在给定解释下，求x(F(f(x))G(x,f(x)))

给定解释①I＝{2,3};②I中特定元素a=2；③函数为f(2)=3,f(3)=2;④谓词F(x)为F(2)=0,F(3)=1G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=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

0)

(0

0)=0

0 =0第12页例在给定解释下，求

x

yL(x,y)给定解释①I＝{2,3};②I中特定元素a=2；③函数为f(2)=3,f(3)=2;④谓词F(x)为F(2)=0,F(3)=1G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0解：原式=(

yL(2,y))

(

yL(3,y))=(L(2,2)

L(2,3))

(L(3,2)

L(3,3)) =

(10)

(0

1)=11=1第13页例在给定解释下，求

y

xL(x,y)给定解释①I＝{2,3};②I中特定元素a=2；③函数为f(2)=3,f(3)=2;④谓词F(x)为F(2)=0,F(3)=1G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0解：原式=(

xL(x,2))

(

xL(x,3))=(L(2,2)

L(3,2))

(L(2,3)

L(3,3)) =(1

0)

(0

1)=00=0量词指导变元次序不能随意

第14页例(p31)已知

x

y((X(x，y)

Y(z))

Z(x，y))试求公式在解释(I；z；X(e1，e2)，Y(e)，Z(e1，e2))=({1，2，3，4}；2；e1

e2；e为偶数；e1

e2)之下值。解：将解释代入公式得：原式=

x

y((x

y

2为偶数)x

y)=x

y(x

y

x

y)第15页解(续)

原式=

x

y(x

y

x

y)

(1)当x=1时 原式作用域=

y(1

y

1

y) ①当y=1时，(1

1)

(1

1)=T

T=T ②当y

2时，(1

y)

(1

y)=F

T=T(2)当x=2时 原式作用域=

y(2

y

2

y) ①当y=1时，(2

1)

(2

1)=T

F=F ②当y=2时，(2

2)

(2

2)=T

T=T ③当y

3时，(2

y)

(2

y)=F

T=T所以，得到：原式=(T

T

T

T)

(F

T

T

T)

(…)

(…)=TF

*

*=F第16页例(补充)考查新公式

x

y(x

y

x

y)在上例中考查了x=1,2情况，现在还需要继续考虑x=3,4情况。(3)当x=3时 新公式作用域=

y(3y

3

y) ①当y=1,2时，(3y)(3y)=T

F=F ②当y=3时，(33)(33)=T

T=T ③当y=4时，(34)(34)=F

T=T(4)当x=4时 新公式作用域=

y(4y

4

y) ①当y<4时，，(4

y)

(4

y)=T

F=F ②当y=4时，，(1

4)

(1

4)

=T

T=T所以，新公式=(T

T

T

T)

(F

T

T

T)

(F

F

T

T)

(FF

F

T)

=T

T

T

T=T第17页例(补充)四个公式比较考查新公式

x

y(x

y

x

y)=(T

T

T

T)

(F

T

T

T)

(F

F

T

T)

(FF

F

T)

=T

T

T

T

=T考查新公式

x

y(x

y

x

y)=(T

T

T

T)

(F

T

T

T)

(F

F

T

T)

(F

F

F

T)

=T

F

F

F=

T原公式=

x

y(x

y

x

y)=(T

T

T

T)

(F

T

T

T)

(F

F

T

T)

(F

F

F

T)

=T

F

F

F=F考查新公式

x

y(x

y

x

y)=(T

T

T

T)

(F

T

T

T)

(F

F

T

T)

(FF

F

T)

=T

T

T

T=

T第18页第三章谓词演算基础3.1谓词与个体3.2函数与量词3.3自由变元和约束变元3.4永真性和可满足性

3.4.1真假性

3.4.2同真假性、永真性和可满足性3.4.3范式3.5唯一性量词与摹状词第19页同真假性定义：设有两公式

和

,

假如对于个体域I上任何解释，公式

和

均取得相同真假值，则称

和

在I上同真假。假如

和

在每一个非空个体域上均同真假，则称

和

同真假。第20页关于否定等价公式

x

(x)=x

(x)

x

(x)=x

(x)设个体域I中全部实体变元为a1，a2，…，an，则有：

x

(x)=(

(a1)(a2)…

(an))=(a1)(a2)…

(an))=x

(x)

x

(x)=(

(a1)(a2)…

(an))=(a1)(a2)…

(an))=x

(x)第21页量词作用域收缩与扩张设公式

中不含有自由x，则:

x(

(x)

)=

x

(x)

x(

(x)

)=

x

(x)

x(

(x)

)=

x

(x)

x(

(x)

)=

x

(x)

第22页例试用等价公式判断两公式是否等价

x(

(x))

和

x

(x)

解：

x(

(x))

=x(

∨

(x)=∨x(x)=x

(x)

所以两公式等价。第23页例(p33)试用等价公式判断两公式是否等价

x

(x)

和

x(

(x)

)解：

x

(x)=(

x

(x))

=(x

(x))

=x((x)

)=x((x)

)

x((x))所以两公式不等价。第24页量词作用域收缩与扩张(续)设公式

中不含有自由x，则下面公式成立:

x(

(x)→

)=(

x

(x)→

)

x(

→

(x))=(

→

x

(x))

x(

(x)→

)=(

x

(x)→)

x(

→

(x))=(

→

x

(x))第25页考查

xF(x)I={2,3}I={2,4}F(x):x为偶数FTF(x):x为奇数FFF(x):x<5TTF(x):x是质数TF第26页考查

xF(x)xF(x)I={2,3}I={2,4}F(x):x为偶数FT=TTT=TF(x):x为奇数FT=TF

F=TF(x):x<5TT=TTT=TF(x):x是质数TT=TFT=T第27页永真、永假定义：给定一个谓词演算公式

，其个体域为I，对于I中任意一个解释,(1)若

均取为真，则称公式

在I上为永真；

(2)若

均取为假，则称公式

在I上为永假，也称为公式在I上不可满足。第28页例讨论公式类型

xF(x)xF(x)

证实设E为任意一个解释，其个体域为I，

若对于任意x∊I,F(x)均为真,则

xF(x)与xF(x)都为真，从而该公式也为真。

若存在x0∊I,使得F(x0)为假，则

xF(x)为假，从而该公式为真。 故在解释E下该公式为真。 因为E任意性，所以该公式是永真式。第29页可满足、非永真定义：给定一个谓词演算公式

，其个体域为I,(1)假如在个体域I上存在一个成真解释,则称公式

在I上为可满足公式；

(2)假如在个体域I上存在一个成假解释，则称公式

在I上为非永真公式。第30页例讨论类型

xyF(x,y)xyF(x,y)证实

取解释E以下： 个体域为自然数集N，谓词解释F(x,y)：x

y。在解释E下，该公式前、后件均为真，所以该公式为真，这说明该公式不是矛盾式；

再取解释E：个体域依然为N，谓词F(x,y)：x=y。 在解释E下，该公式前件为真，后件为假，故该公式为假，这又说明该公式不是永真式。 总而言之，该公式是非永真式可满足式。第31页考查

xF(x)xF(x)I={2,3}I={2,4}I={a,b}F(x):x为偶数FT=TTT=TFF=TF(x):x为奇数FT=TF

F=TFF=TF(x):x<5TT=TTT=TFF=TF(x):x是质数TT=TFT=TFF=T第32页定理1(p33)假如I，J是个含有相同个数个体域(个体本身可不相同)，则任意一个公式

，若在I中永真当且仅当其在J中永真；若在I中可满足当且仅当其在J中可满足。证实：要证实该问题，首先要在两个个体域I和J上建立个体、谓词、解释等元素间一一对应关系。第33页定理1证实(p33)结构一一对应关系以下：(1)因为I和J含有相同个数个体域，所以可在二者之间建立一一对应关系，即在I中有一个个体a，总能在J中找到一个个体与之对应，反之亦然。(2)现作个体域I和J上谓词一一对应关系设X(x1，x2，…，xn)是I上n元谓词，令满足以下性质J中n元谓词X’(x1’，x2’，…，xn’)是其对应谓词:

X(x1，…，xn)为真当且仅当X’(x1’，…，xn’)为真,

其中x1，…，xn在I中取值，x1’，…，xn’在J中取值。第34页定理1证实(p33-34)(3)把I中解释与J中解释作一一对应关系：设有I中一个解释(x1，…，xn；X1，…，Xm；P1，…，Pk)=(a1，…，an；A1，…，Am；P10，…，Pk0)记为：(x；X；P)=(a；A；P0)

则令J中以下解释为其对应解释(a1’，…，an’；A1’，…，Am’；P10，…，Pk0)记为：(a’；A’；P0)利用归纳法可证实

(见下页)

(a；A；P0)=

(a’；A’；P0)第35页定理1证实(p34)利用归纳法能够证实

(a；A；P0)=

(a’；A’；P0)假如

为命题变元，命题显然成立。假如为谓词填式X(x1，x2，…，xn)

则有…，故命题成立。假如为以下五种情形之一

1，1

2，1

2，1

2，1

2，

则有…，故命题成立。假如为

y

1(x；X；P，y)之形，则有…，故命题成立。假如为

y

1(x；X；P，y)之形，同理可证。第36页定理1证实(p34)利用归纳法可证实

(见上页)

(a；A；P0)=

(a’；A’；P0)(3.1)设

在I中可满足，即在I中存在一个解释(a；A；P0)使得

取真值，由解释一一对应关系和式(3.1)知，在J中也存在一个解释(a’；A’；P0)使得

取为真，故

在J中可满足。反之亦然。同理可证，

在I中永真当且仅当

在J中永真。第37页K域定义：把个体域{1，2，3，…，k}称为k域， 即由k个个体组成个体域。当k=1时，就称为1域，依这类推。第38页永真性和可满足性定理2：假如一公式在k域上永真，则其在h(h<k)域上永真。定理3：假如一公式在h域上可满足，则其在k(k>h)域上可满足。第39页例(p35)试讨论公式永真性和可满足性

x(X(x)

(

y(Y(y)

Z(z))

xY(x)))解：(1)讨论1域即个体域{1}情形

公式=X(1)((Y(1)Z(1))Y(1))=X(1)T=T所以公式在1域上永真。(2)讨论2域上情形此时个体域I={1，2}，于公式在1域上永真，由定理3知公式在2域上可满足。第40页例(p35)(2)讨论2域上情形公式在2域上可满足。下面考查是否在2域上永真。公式在解释(I；z；X，Y，Z)=({1，2}；2；X1，X2，X2)下,原式=

x(X1(x)(

y(X2(y)X2(2))xX2(x)))=x(X1(x)(

y(X2(y)T)xX2(x)))=x(X1(x)(

yX2(y)xX2(x)))=x(X1(x)(T

xX2(x)))=x(X1(x)xX2(x))=x(X1(x)F)=x

X1(x)=F

F=F故公式在2域上可满足但非永真。

eX1X2X3X41TFTF2TTFF图3.32域上一元谓词第41页例(p35)(3)

讨论k域(k>2)上情形(3)讨论k域(k>2)上情形

因为公式在2域上可满足，依据定理3知，公式在k域上可满足；设公式在k域上永真，依据定理2知，公式在2域上永真，与公式在2域上非永真矛盾。故公式在k域上可满足但非永真。第42页命题

x(A(x)B(x))

(

xA(x)

xB(x))在k域上永真。证实：在k域上，此时个体域

I={1，2，…，k}原式=((A(1)∧B(1))∧(A(2)∧B(2))

∧…∧((A(k)∧B(k))

((A(1)∧A(2)∧…∧A(k))∧(B(1)∧B(2)∧…∧B(k)))

=T所以公式在k域上永真。第43页例试符号化“鱼我所欲，熊掌亦我所欲”。解：F(e)表示“e为鱼”,P(e)表示“e为熊掌”, W(e1,e2)表示“e1要e2”，

a表示“我”，则原句译为

(∀x(F(x)W(a,x)))∧(∀x(P(x)W(a,x)))∀x((F(x)∨P(x))

W(a,x))?第44页第三章谓词演算基础3.1谓词与个体3.2函数与量词3.3自由变元和约束变元3.4永真性和可满足性

3.4.1真假性3.4.2同真假性、永真性和可满足性

3.4.3范式

3.5唯一性量词与摹状词第45页一、前束范式定义：假如一谓词演算公式

中一切量词均在公式最前面(量词前不含否定词)且其作用域一直延伸到公式末端，则称公式

为前束形公式。前束形公式普通形式为：

Q1x1Q2x2…QnxnM(x1，x2，…，xn)其中，Qi为或

，M称为公式母式且其中不含有量词。第46页定理任意一个谓词演算公式都有一前束范式与之等价。第47页求前束范式普通步骤利用等值公式消去“”和“

”

否定深入

更名

前移量词第48页例求前束范式：xX(x)xY(x)解：(1)利用等值公式消去“

”得：

(xX(x)xY(x))(

xX(x)xY(x))(2)否定深入得：

(x

X(x)xY(x))(

xX(x)x

Y(x))(3)更名：

(x

X(x)yY(y))(

uX(u)v

Y(v))(4)前移量词得：

x

y

u

v((X(x)Y(y))(X(u)Y(v)))

x

v

y

u((X(x)Y(y))(X(u)Y(v)))?第49页例有一个液体可熔化任何金属解：L(e)表示“e是液体”, M(e)表示“e是金属”，

A(e1,e2)表示“e1熔化e2”，则原句译为

x(L(x)∧(∀y(M(y)A(x,y)))x∀y((L(x)∧M(y))A(x,y))?第50页例全部学生都佩服一些高兴女声设S(x)：x是学生，G(x)：x是高兴女声，A(x,y)：x佩服y。下面哪个答案正确？ (A)

xS(x)A(x,y)

(B)

x(S(x)y(G(y)∧A(x,y))) (C)

xy(S(x)∧G(y)∧A(x,y)) (D)

xy((S(x)∧G(y))A(x,y))(E)xS(x)∧yG(y)A(x,y)(F)x(S(x)y(G(y)A(x,y)))第51页二、SKOLEM标准形定义：仅含有全称量词前束范式称为SK