离散数学(第7讲)谓词逻辑2

1、栾新成 四川大学软件学院 85997822第2章 一阶谓词逻辑(2),邪壁贩糙啃帐汲贺欢唆鱼贿霖筛恋谢蜜何脓甜轮锭蔑屠粹诵片酞幽焚软侗离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,主要内容,谓词公式与解释 1.谓词的合适公式 2.谓词公式的解释 3.几个特殊的公式 谓词公式的等价与范式表示 1.谓词公式的等价 2.基本等价式 3.前束范式 4.斯柯林范式,2020年8月6日,2,宿蔗针倍鸟揽诺敦壹电啪兔辕前营罐傀攫鹰坷伤走唐凄纲途巳膳灾详阁饺离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式,同命题演算一样，在谓词逻辑中也同样包含命题变元和

2、命题联结词，为了能够进行演绎和推理，为了对谓词逻辑中关于谓词的表达式加以形式化，利用联结词、谓词与量词构成命题函数，我们必须引入公式的概念。,2020年8月6日,3,辱照芽隧噪川剑市洒只诀贮君钥嘿佃凑锄漫洋曾吏颊蝉约坊鸳层销否烂平离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式,四类符号: 常量符号：一般用a,b,c,a1,b1,c1,来表示，它可以是D中的某个元素; 变量符号：一般用x,y,z, x1,y1,z1,来表示.它可以取值于D中的任意元素； 函数符号：一般用f,g,h, f1,g1,h1,来表示。n元函数符号f(x1,x2,.xn)可以是DnD的任意一个函数； 谓

3、词符号：一般用P,Q,R,., P1,Q1,R1,.来表示。n元谓词符号P(x1,x2,.xn)可以是Dn0,1的任意一个谓词。 注：不含变元的函数是常量；不含客体变元的谓词是命题。,2020年8月6日,4,柿珠浙辟敞旧魔熟眨傈鲤绚哪堆宵糜惊更腔粘鹤凤僳蜂黄阅重宇镍褐蒲蝎离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式,n元函数符号f(x1,x2,.xn)与n元谓词符号P(x1,x2,.xn) 1）两个n元相同吗？ 2）函数符号f(x1,x2,.xn)中的f 可以用P代换吗？如果能，则代换结果为P(x1,x2,.xn)，与谓词符号P(x1,x2,.xn)的区别是什么？,202

4、0年8月6日,值域不同,5,瑞财裔皋车田伞襟肥钙勃顷钙罗澳社熄柜旗屹饭绘应沸瞧揩磺残汉匪钢殊离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式,定义2-2.1 谓词逻辑中的项被递归地定义为： 1）任意的常量符号是项； 2）任意的变量符号是项； 3）若f(x1,x2,x3,xn)是n元函数符号，t1,t2,t3,tn是项，则f(t1,t2,t3,tn)是项； 4）只有有限次使用1)-3)产生的符号串才是项。 例2.1 复合函数f(g(f(a),g(a,x)是一个项,2020年8月6日,6,汽舱挝寄欺鸽叙辕耕操仔旅板羌惹口荣饿鬃瞳尝培泛倘荆构磨蹋尼扭英委离散数学(第7讲)谓词逻辑2

5、离散数学(第7讲)谓词逻辑2,谓词公式,定义2-2.2 设P(x1,x2,x3,.xn)是n元谓词，t1,t2,t3,.tn是项,则P(t1,t2,t3,.tn)是原子谓词公式，简称原子公式。 定义2-2.3 满足下列条件的表达式，称为合适公式,简称公式。 1）原子公式是合适公式； 2）若G，H是合适公式，则(G)、(H)、(GH)、(GH)、(GH)、(GH)也是合适公式； 3）若G是合适公式，x是个体变量，则(x)G、(x)G也是合适公式； 4）仅仅由1)-3)产生的表达式才是合适公式。,2020年8月6日,G的区别:G与(x)G（x),7,官烦数顿锅狞祖风鞍载番凑迎澜测龚耗霖承团逸弊沛变

6、碾颁嘲撰蜜加邱囊离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式,例2.2(P(x)(Q(x,y)R(x,a,f(z) (P(x)R(y) (x)(P(x) 等都是公式。 而 (x)(P(x)R(x) (x)P(x)(y) 等则不是公式，前者括号不匹配，后者量词无辖域。,2020年8月6日,8,躺疼矩恃烙陀骋隘瘁匣诵专烤程返小葱要扒诀迪徽了秉前刘卜殉鳞袱么即离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的翻译,例1 并非每个实数都是有理数 解：设R(x):x是实数, Q(x):x是有理数 原命题为：x (R(x) Q(x) 例2 没有不犯错误的人 解：设M

7、(x)：x是人, F(x):x犯错 原命题为： x（(M(x) F(x) 例3 尽管有人聪明，但未必一切人都聪明。 解：设M(x):x是人, P(x):x聪明 原题为： x(M(x) P(x) x(M(x) P(x),2020年8月6日,9,弯雷树粹俭恫干生滑窑硝煮枢势防厉珐袖彼监辨潜侈注赘文交里斡札哄命离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的翻译,多元谓词可以多重量化 例4 翻译每个人都有缺点。 解：设F（x,y）:x有y, M(x):x是人 G(y):y有缺点 原命题为:x(M(x)y(G(y) F(x,y) 例5:翻译某些人对某些食物过敏。 解：设F（x,y）

8、:x对y过敏, M(x):x是人 G(y):y是食物。 原命题为:xy(M(x) G(y) F(x,y),2020年8月6日,10,路矮洒灶胁抓缄息溯励钎酋数窒评谰冠甜审捆进钳荒琵腕慧贾壳诗鳞稚禾离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的翻译,谓词对于个体刻划的深度的机动灵活性 例6 翻译那只小花猫逮住这只大老鼠。 解：设 a:F(x,y):x逮住y, P(x):x是小花猫, Q(y):y是大老鼠,S(a):a是那只,R(b):b是这只 原命题为： ab(P(a)Q(b)F(a,b)S(a) R(b) b A(x):x是猫,B(x):x是小的,C(x):x是花的,D(

9、y):y是的,E(y):y是老鼠,F(x,y),S(a),R(b)同上。 原命题为： ab(A(a) B(a) C(a) D(b) E(b) F(a,b)S(a) R(b) 。,2020年8月6日,11,厢锈产卷孤寝律燃曼袜标总附酚岭出诗举骑贞奈窥租盏漠二速俐谁苗勿渴离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的解释,定义2-2.4 一个定义在论域D上的公式G的每一个解释（指派）由如下四部分组成： 1、非空的个体域集合D； 2、G中的每个常量符号,指定D中的一个元素； 3、G中的每个n元函数符号,指定Dn到D的一个函数； 4、G中的每个n元谓词符号,指定Gn到0,1的一个

10、谓词。 注：定义中所谓指定一个具体函数，即是对每组可能的变量值给出函数的对应值； （值域？） 所谓指定一个具体命题函数，就是对每组可能的客体变元取值给出谓词的对应值，1表示逻辑真，0表示逻辑假。,2020年8月6日,12,亨奥病哇丙墩骏宋军被瑟攻伺陨颈斑贷司拓缎烙斟硫容漫侩歇邪龙枢臣候离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的解释,含有量词的公式的解释 对于含有量词的公式的解释，需要根据量词的逻辑意义来决定公式的值。 设论域 D=a1,a2, ，an 1）（x)P(x) P(a1) P(a2) P(an) 表示公式（x)P(x)值为1“当且仅当”对论域D中每个元素a，

11、 P(a)的值为1。 2）（x)P(x) P(a1) P(a2) P(an) 表示公式（x)P(x)值为0“当且仅当”对论域D中每个元素a， P(a)的值为0。,2020年8月6日,13,障律久烷幸药缎蕊虾琢隙摇堆谊瘴垃花嚣辣憨观谆逛谤斤禹减炽伤获名芽离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的解释,例2.3 设公式：(x)(y)(P(x,y)Q(x,y)。在如下给定的解释下,判断该公式的真值。 1)、解释I为： .个体域为N+(严格大于0的整数)； .P(x,y)指定为：“yx”； .Q(x,y)指定为：“y1”。 则原公式的真值为“真”。因确能找到一个xN+，使得对

12、任意y,都有yx和y1。 此时蕴涵公式的前件为真，后件也为真。所以，整个公式为真。,2020年8月6日,14,存效锑磊棒幢赫紊螟陋秦心皑机尤然限沸赠皋阑腥硝俩损菊腻脱陨曹客套离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的解释,2)、解释I为： (x)(y)(P(x,y)Q(x,y)。 .个体域为N； .P(x,y)指定为：“xy0”； .Q(x,y)指定为：“xy”；则原公式的真值为“假”。 因对任意的x0,当y0时，有P(x,y)Q(x,y)为“假”，即有：(y)(P(x,y)Q(x,y)为“假”。 而对x0，当y1时，有P(x,y)Q(x,y)为“假”。即有：(y)(

13、p(x,y)Q(x,y)为“假”。 所以，对任意xN,都有： (y)(P(x,y)Q(x,y)为“假”。 即有：(x)(y)(P(x,y)Q(x,y)为“假”。,2020年8月6日,15,伙抠抗脑屉司吓仟纱亥播违赃峭邑壶贫碟酿躺届唁鼻鸵腰氨膏欧擦算衰爽离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的解释,3)、解释I为： (x)(y)(P(x,y)Q(x,y)。 .个体域为N； .P(x,y)指定为：“x+y0”； .Q(x,y)指定为：“xy”。 则原公式的真值为“真”。 因对任意的x0,任意yN，有x+y0为“假”，所以无论后件如何，都有 P(x,y)Q(x,y)为“真

14、”， 即有：(y)(P(x,y)Q(x,y)为“真”。 所以：(x)(y)(P(x,y)Q(x,y)为“真”。,2020年8月6日,16,蔫卧狠请妙谈甫靶榨甚签挑挑影丁渭典泛食翰看似只薄讲宪狸派豺衙稳晌离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,几个特殊公式,定义2-2.5： 1、设A是以D为论域的谓词公式，如果在关于D的任一解释之下，A的值都为真（或1）时，称公式A是D上的永真公式(重言式) ； 2）设A是以D为论域的谓词公式，如果在关于D的任一解释之下，A的值都为假（或0）时，称公式A是D上的永假公式(矛盾式，不可满足公式）； 3）设A是以D为论域的谓词公式，如果在关于D的某

15、个解释之下，A取值为真（或1），称公式A是D上的可满足公式。,2020年8月6日,17,踩聪益焰纤拍谰陨音腰宫恿烽鸽觉龙浅接对地饯漾喊版涨尿沁葫砰缉纽矿离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词公式的等价,定义2-3.1： 设A和B是以D为论域的谓词公式,如果在任一解释下,A和B都取相同的真值,则称A和B在D上是等价的,记作A B 。 定理2-3.1： A B iff A B是D上的永真公式。,2020年8月6日,18,爸洗酌唤透沙圾场屯漾空决掌澳功不庶蔗卷握档蠢抱授私渐干锰肤鹤旷册离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词演算的基本等价式,命题演算中的

16、等价式在谓词演算中都成立,下面只涉及量词(Quanitifier)的一些等价式。,2020年8月6日,19,仿沤着渗袒斜沥芋推跳獭车猛梦疟范瞪掂怕裙势谨瓤隘酌妖樊直痪醒瞻坑离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词演算的基本等价式,定理2-3.2：量词否定(量词转换) 25： （x）P(x) （x）P(x) 26： （x）P(x) （x）P(x) 显然,并非所有的人都是学生和有些人不是学生 有相同含义。 不存在长生不老的人 和 所有的人都不是长生不老的有相同含义。 量词的转换可以推广到含多个量词的谓词公式。 （x）（y）（z）P(x,y,z) （x）（y）（z）P(x,y,

17、z) （x）（y）（z）P(x,y,z) （x）（y）（z）P(x,y,z),2020年8月6日,规律？,规律？,20,醋薄拥侥仙壕睡劝驴茂匠薄蔓康弄较半校虎宏蓖歌舆默踢操硕铬牛霹协燕离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词演算的基本等价式,定理2-3.：（量词辖域的扩充与收缩） 设Q是不含指导变元的谓词公式 27： （x）P(x)Q （x）P(x)Q 28： （x）P(x)Q （x）P(x)Q 29： （x）P(x)Q （x）P(x)Q 30： （x）P(x)Q （x）P(x)Q 31： （x）P(x)Q （x）P(x)Q 32： （x）P(x)Q （x）P(x)Q 3

18、3： Q（x）P(x) （x）Q P(x) 34： Q（x）P(x) （x）Q P(x),2020年8月6日,21,抽惑阶沂测瘩坠奠潞尿辨须趋霉镁嘱梢湿聚檄羡琵绰院枣迷牲陕中磺迟昼离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,谓词演算的基本等价式,定理2-3.：（量词分配侓） 35:(x)(P(x)Q(x)（x）P(x)（x）Q(x) 36:(x)(y)(P(x)Q()(x)P(x)(x)Q(x) 37:(x)()(P(x)Q()（x）P(x)（x）Q(x) 38：（x）(P(x)Q(x)（x）P(x)（x）Q(x) 39：（x）(P(x)Q(x)（x）p(x)（x）Q(x) 定理

19、2-3.：（双量词公式的等价性） 40：(x)()(x，)（）（x）(x，) 41：(x)()(x，)（）（x）(x，),2020年8月6日,同一类型的量词，可以交换顺序而不影响其等价性。,22,统竿娶令妹橙割硕暗炬讶晦咏雕脚背书瑚瞪鼠嫁补拥淡薛矿苟越灾蔷抑茅离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,不同类型量词可交换顺序吗？,解释给定为: D=1，2 ， 分别求公式A=（x）（ y）P(x,y) 和公式B=（ y ）（ x ）P(x,y)的值。 A=(P(1,1）P(1,2)(P( 2,1) P(2,2)=(10) (01)=1 B=(P(1,1）P(1,2) (P( 2,1

20、) P(2,2)=(1 0) (0 1)=0,2020年8月6日,23,襟问畦池莆敛荆芜盯焙庄质寅爸牙板饵闸骡僻朱艰襄拄绪恶诺窗钥芹我偷离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,含有“”“ ”公式的共同点,2020年8月6日,27：(x)(P(x)Q)（x）P(x)Q 28：(x)(P(x)Q)（x）P(x)Q 29：(x)(P(x)Q) （x）P(x)Q 30：(x)(P(x)Q) （x）P(x)Q,35：（x）(P(x)Q(x)（x）P(x)（x）Q(x) 36：（x）（）(P(x)Q()（x）P(x)（x）Q(x) 37：（x）（）(P(x)Q()（x）P(x)（x）Q(

21、x) 38：（x）(P(x)Q(x)（x）P(x)（x）Q(x),24,骡芭崇柑蔓疾殉涩撰西矾幅议抄带际勃华讨夕提恐增煎颂奢晤本抹目失接离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,含有“”公式的共同点,2020年8月6日,31： （x）P(x)Q （x）P(x)Q 32： （x）P(x)Q （x）P(x)Q 33： Q（x）P(x) （x）Q P(x) 34： Q（x）P(x) （x）Q P(x),39：（x）(P(x)Q(x)（x）p(x)（x）Q(x) （x）(P(x)Q(x)（x）p(x)（ xQ(x ）,25,黍寸杂郎姐赶污丙旅螺贿朔阐芹蔡擂今豫现挟背讥扔企舱壹茹哈肤塌针

22、框离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,前束范式,与命题演算类似,谓词演算也有范式(规范(标准)的公式) 定义2-3.:如果谓词公式 A=（Q1x1）（Q2x2）（Qnxn）G, 其中Qixi是xi或xi(1 i n), G是不含量词的公式, 则称A是前束范式, 称G是A的母式。 (所有量词均非否定地出现在公式的最前面,且辖域一直延伸到公式之末) 如（x）（y）（z）(P(x,y) Q(y,z) （x）（y）p(x,y,z),2020年8月6日,26,荚恩听扼凭仟据纫冷葡谦陛洒姻玉饭惺艇寇定傀图喘捎函哦阁怀难茧垂走离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,前

23、束范式,定义2-3.:如果在前束范式（Q1x1）（Q2x2）（Qnxn）G中,母式G是合取(或析取)范式,相应地称这个前束范式为前束合取(或析取)范式。 定理2-3.6 每一个含量词的谓词公式都存在着与之等价的前束范式。 化规过程: 1.将公式中,化成 , 2.利用量词转换律25,26和德.摩根定律,将否定直接移到原子公式前。 3.利用约束变元的改名和自由变元的代入规则,使所有约束变元之间,自由变元与约束变元之间均不同名。 4. 利用量词的扩张与收缩,把量词移到全式的最前面。,2020年8月6日,27,戳击栽蛾畔簇跨盼焕涉见冰队岂脚脂挨惰毅慑卒隋吾需钻瞄确刊剂蚊谆怜离散数学(第7讲)谓词逻辑2

24、离散数学(第7讲)谓词逻辑2,前束范式,例2.4 将公式(xP(x)yR(y)xF(x) 化规为前束范式。 解：(xP(x)yR(y)xF(x) (xP(x)yR(y)xF(x) (1) (xP(x)yR(y)xF(x) (2) （xP(x)yR(y)） z F(z) (3) xyz( (P(x)R(y) )F(z) ) (4) (析取范式) xyz(P(x)F(z)(R(y) F(z) (合取范式),2020年8月6日,28,琵橇崎茸琐驼痪锻天友映拈盛滦止豌加冯次反拂炽妙隐坊时励豪渺苏极壬离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,前束范式的不足,把一个谓词公式变成等价的前束范

25、式时,可能存在多个全称量词和存在量词. 凡是同一类型的量词,可以交换顺序而不影响等价性； 全称量词和存在量词一般不能交换顺序； 两种量词出现的顺序可能组成多种情况； 在处理实际问题时很不方便。人们设计了一种解决办法： 只保留全称量词,而把存在量词转化为相应的依赖函数,这就是Skolem范式的思路。,2020年8月6日,29,钉规茨径揉键措伙堤洁戎慌厚冀宪莹惠潘黔异陨奇燃糕篷礼嚣沿务鹿钵笼离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,斯柯林(Skolem)范式,斯柯林(Skolem)范式-不含存在量词的前束合取范式 定义23.4 设谓词公式A的等价前束合取范式是 （Q1x1）（Q2x

26、2）（Qnxn）G, ）从左到右扫描量词，设Qi是第一个遇到的存在量词: 如i=1,则选择一个在G中未使用过的常量标识符代替G中的全部x1,然后删去Q1x1; 如果i1,则Q1,Q2,Qi-1都是全称量词,这时选择一个在G中未使用过的函数标识符(如g)，并用g(x1,x2,.,xi-1)去代替G中的全部xi,然后删去Qixi; 2）重复这一过程,直到公式中不含存在量词为止。 这样得到的公式称为Skolem范式,而取代存在量词时使用的常量标识符或函数,称为Skolem函数。,2020年8月6日,30,戏释诡孩且伟霸吸哨硒福宦喧啼授宛自帜孺零扰汉愤谴诚忍佳舞站式从军离散数学(第7讲)谓词逻辑2离散数学(第7讲)谓词逻辑2,斯柯林(Skolem)范式,例2.5 求xyzuvwP(x,y,z