我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿玄机1站开奘结果 > 前束范式 >

chap6 一阶逻辑解析ppt

归档日期:07-14       文本归类:前束范式      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  * 离散数学 * 习题:符号化下列命题,并论证其结论: 每个大学生,不是文科学生就是理科学生,有的大学生是优等生,小张不是理工科学生,但他是优等生,因而如果小张是大学生,他就是文科生。 命题符号化:设G(x):x是大学生。L(x):x是文科学生。P(x):x是理工科学生。S(x):x是优秀生。c:小张。 * 离散数学 * 附加前提 前提 (2),US 假言推理,(1),(3) 前提 析取三段论,据(4),(5) 证明:推理如下: * 离散数学 * 3 量词作用域的收缩与扩张等值式 定理: 设G(x)是恰含一个自由变元x的谓词公式, H是不含变量x的谓词公式. 于是有: 证明 * 离散数学 * 证明:设D是论域,I是G(x)和H的一个解释. * 离散数学 * 4 量词分配等值式 定理: 设G(x),H(x)是恰含一个自由变元x的谓词公式,则有: 对不对? 证明 (×) (×) 原因 * 离散数学 * 原因 取解释I如下: D:=自然数集; G(x):=“x是奇数”; H(x):=“x是偶数”. 同理可证B. * 离散数学 * 证明 (改名规则) (定理6.3.2) (析取词交换律) (定理6.3.2) (析取词交换律) * 离散数学 * 前束范式 定义: 设G为一个谓词公式,如果G具有如下形式: Q1x1…QnxnM 则称G为前束范式, 例: F(x,y),?x?y?zP(x,y,z) 是前束范式 ?x?y(P(x,y)→Q(x,y)) 是前束范式 Q1x1…Qnxn称为首标,M称为母式。 * 离散数学 * 定理6.3.4: 对任意谓词公式G,都存在一个与其等值的前束范式。 证明: 对于公式G,可通过如下步骤得到等值于G的前束范式。 (1)使用基本等值式: (3)必要的话,将约束变量改名。 (4)使用定理6.3.1~定理6.3.3将所有量词都提到 公式的最左边。 注意: 一个公式的前束范式是不唯一的. 例子 * 离散数学 * 例子: 对公式 推导如下: y * 离散数学 * 习 题:将下式化成前束范式 解(1): * 离散数学 * 解(2): 前束范式对首标中量词的次序没有要求, 对母式中公式的形式也没作何种规定。 下面对前束范式作进一步规范,即保留 前束范式中的全称量词而消去存在量 词。 * 离散数学 * 一种特殊的前束范式: Skolem范式 定义:设G是一个谓词公式,Q1x1,…,QnxnM是与G等值的前束范式。其中M为合取范式。 (1)若Qr是存在量词(1≤r≤n),并且它左边没有全称量词,则取异于出现在M中所有常量符号的常量符号c,并用c代替M中所有的xr,然后在首标中消除Qrxr。 (2)若Qr1,…,Qrm是所有出现在Qrxr左边的全称量词,m≥1, 则取异于出现在M中所有函数符号的m元函数符号 f(xr1,…,xrm),用f(xr1,…,xrm)代替出现在M中的所有xr, 然后在首标中删除Qrxr。 (3)重复以上过程,直到该前束范式的首标中无存在量词。 由此得到的前束范式称为Skolem范式,其中用来代替xr的那 些常数符号和函数符号称为公式G的Skolem函数。 例子 * 离散数学 * 例子: 1)用a代替x;2)用f(y,z)代替u;3)用g(y,z,v)代替w。 于是,得Skolem范式: 注意:公式与其Skolem范式两者不一定等值。 例子: 令解释I为: D={1,2};P(1,1):=0;P(1,2):=1;P(2,1):=0;P(2,2):=1f(1):=1;f(2):=2 * 离散数学 * 定理6.3.5: 设S是谓词公式G的Skolem范式。于是,G是恒假的当且仅当S是恒假的。 证明:由定理6.3.4,不妨设G是前束范式:G=Q1x1…QnxnM(x1,…,xn),并且首标中至少有一个存在量词。 设Qr是首标中下标最小的存在量词,1≦r ≦n,令 G1=?x1…?xr-1Qr+1xr+1…QnxnM(x1,…xr-1, f(x1,…,xr-1),xr+1,…,xn) 其中f(x1,…,xr-1)是代替xr的Skolem函数。 * 离散数学 * 下面证明,G恒假当且仅当G1恒假。 设G恒假。若G1可满足,则存在一个解释I满足G1,于是,对任意值组(x01,…,x0r-1)∈Dr-1,都有f(x01,…,x0r-1)∈D,使得 Qr+1xr+1…QnxnM(x01,…,x0r-1,f(x01,…,x0r-1),xr+1…xn) 在I下为线的解释I也是满足G的解释。此与G恒假矛盾,故G1也恒假。 反之,设G1恒假,若G可满足,则存在一个解释I满足G。于是,对任意值组(x01,…,x0r-1)∈Dr-1, 都存在x0r∈D,使得 Qr+1xr+1…QnxnM(x01,…,x0r-1,x0r ,xr+1…xn) 在I下为真。 * 离散数学 * 今扩充解释I为I’,使其包含对函数符号f(x01,…,x0r-1)的如下指定: f(x01,…,x0r-1)=x0r,对任意值组(x01,…,x0r-1)∈Dr-1。 于是,I’满足G1,矛盾,故G也恒假。 设G中共有m(m≧1)个存在量词。 令:G0=G; Gk=(将Gk-1中下标最小的存在量词用Skolem函数代替所得的公式),k=1,…,m。 易知,Gm就是公式G的Skolem范式,即S=Gm 与上类似可证:G1恒假当且仅当G2恒假,…,Gk-1恒假当且仅当Gk恒假,…,Gm恒假。 因此,G0恒假当且仅当Gm恒假,即,G恒假当且仅当S恒假。 * 离散数学 * 推论6.3.1: 设公式S是公式G的Skolem范式,于是,满足S的解释必满足G,但反之不然。 一阶逻辑中公式G的Skolem范式,在定理的机器证明中非常有用。机器定理证明中著名的归结原理就是建立在Skolem范式基础上的。 * 离散数学 * 定义6.4.1 设G、H是两个谓词公式。如果G?H是恒真的,则称G蕴含H,或称H是G的逻辑结果,记为G?H。 显然,任意公式G,H,G?H的充分必要条件是:对任意解释I,若I满足G,则I必满足H。 §6.4 一阶逻辑的推理理论 定义6.4.2 设G1, … ,Gn, H是谓词公式,n≥1. 如果 因命题公式是谓词公式的特殊情形,由上述定义知,谓词演算的推理方法可看作是命题演算的推理方法的扩张。故在推理过程中,命题演算中的前提引入规则、结论引入规则、置换规则,8个基本蕴涵式以及对其中每个蕴涵式中的同一命题变元用同一谓词公式代入所得蕴涵式,都可使用。但由于量词的引入,某些前题与结论可能受量词的限制。因此,还需给出一些谓词演算中特有的蕴涵式和推理规则。 则称G1, … ,Gn共同蕴含H, 或称H是G1, … ,Gn的逻辑结果,记为 * 离散数学 * 谓词演算中的三个蕴涵式 定理:设G(x),H(x)是恰含一个自由变元x的谓词公式,于是, 证明: (1) (3)(?xG(x)→?xH(x))??x(G(x)→H(x)) 则存在x0∈D,使得G(x0) ∨H(x0)为假命题。此时, G(x0)与 H(x0)均为假命题,从而, 在解释I下为假。 矛盾!故 * 离散数学 * 证明: 因为?xG(x)→?xH(x)??(?xG(x))∨?xH(x) ? ?x(?G(x))∨?xH(x) 由(1)有:?x?G(x)∨?xH(x)??x(?G(x)∨H(x)) ??x(G(x)→H(x)) 故 (?xG(x)→?xH(x)) ? ?x(G(x)→H(x)) (3) ?xG(x)→?xH(x) ??x(G(x)→H(x)) (2) ?x(G(x) ∧H(x))? ?xG(x)∧ ?xH(x)) * 离散数学 * 谓词演算中的推理规则(US.UG.EG.ES) 全称指定规则 (US规则) 这两种形式可根据需要选用,两式成立的条件是: 1 x 是A(x)中的自由变元 2 在(1)式中,y是不在A(x)中约束出现的任何一个变量符号 3 在(2)式中,c为任意的常量符号 例子: 设论域D为实数集.谓词F(x,y)表示x>y,则 其原因在于,y在A(x)中是约束出现的. * 离散数学 * 全称推广与存在推广规则:(UG与EG) 成立条件: 1) y在A(y)中自由出现。 2) x不能在A(y)中约束出现。 例子: 在实数域中仍取F(x,y)为xy. 则A(y)是线)不满足。 成立条件: 1) c是特定的常量符号. 2) 取代c的x在A(c)中没有出现过. * 离散数学 * 错误使用EG规则的例子 其原因是使用EG规则的条件2)不满足。 * 离散数学 * 存在指定规则(ES规则): 成立条件: 1) c是使A(c)为线)A(x)中的自由变元只有x. 例如: 设D为自然数集, F(x)表示“x是奇数”,G(x)表示“x是偶数”. * 离散数学 * 但,若不注意使用条件,则有: 前提引入 化简,根据(1) ES规则,根据(2) 化简,根据(1) ES规则,根据(4) 合取,根据(3),(5) EG规则,根据(6) 于是得出: (×)违反了条件2) * 离散数学 * 例 1 证明: 推理过程如下: 前提引入 US规则,根据(1) 前提引入 ES规则,根据(3) 化简,根据(4) 化简,根据(4) 假言推理,根据(2),(6) 合取,根据(5),(7) EG规则,根据(8) 在推理过程中,y被指定 为论域中的任一个体, a被指定为论域中的某 一个体。对于(2)和(6), 在使用假言推理时,由 于y是任一个体,因此, 可以选为某一个体a,故 得(7)。 * 离散数学 * 本例也可作如下推理: 前提引入 ES规则,根据(1) 化简,根据(2) 前提引入 US规则,根据(4) 假言推理,根据(3),(5) 化简,根据(2) 合取,根据(6),(7) EG规则,根据(8) * 离散数学 * 例 2 证明: 苏格拉底三段论“凡人都是要死的,苏格拉底是人, 所以苏格拉底是要死的”。 证明: 结论: D(a) 首先将命题符号化: M(x):x是人. D(x):x是要死的. a:苏格拉底. 前提: 证明: 前提引入 US规则,(1) 前提引入 假言推理,(2),(3) * 离散数学 * 例 3 有些病人相信所有的医生,但是病人都不相信一个骗子。证明:医生都不是骗子。 证明: 命题符号化: P(x):x是病人;D(x):x是医生;Q(x):x是骗子;R(x,y):x相信y。 前提:?x(P(x)∧?y(D(y)→R(x,y))), ?x?y(P(x)∧Q(y)→?R(x,y)) 结论:?x(D(x)→?Q(x)) 推理: * 离散数学 * ?x(P(x)∧?y(D(y)→R(x,y))) 前提引入 P(c)∧?y(D(y)→R(c,y)) ES,(1) ?x?y(P(x)∧Q(y)→?R(x,y)) 前提引入 ?y(P(c)∧Q(y)→?R(c,y)) US,(3) P(c)∧Q(z)→?R(c,z) US,(4) ?(P(c)∧Q(z))∨R(c,z) 蕴涵等值式,(5) ?P(c)∨?Q(z)∨R(c,z) De Morgan律,(6) ?P(c)∨(Q(z)→?R(c,z)) 蕴涵等值式,(7) P(c) 化简,(2) Q(z)→?R(c,z) 析取三段论,(8),(9) R(c,z)→?Q(z) 等值演算,(10) ?y(D(y)→R(c,y)) 化简,(2) D(z)→R(c,z) US,(12) D(z)→?Q(z) 假言三段论,(11),(13) ?x(D(x)→?Q(x)) UG,(14) * 离散数学 * 例 4:指出下面推理的错误 ?x(F(x)→G(x)) 前提引入 F(y)→G(y) US,(1) ?xF(x) 前提引入 F(y) ES,(3) G(y) 假言推理,(2),(4) ?xG(x) UG,(5) × 没有满足ES规则的条件1 即: ?xA(x)?A(c) c是使A(c)为真的常量 符号。 F(c) ES,(3) G(c) 假言推理,(2),(4) ?xG(x) EG,(5) * 离散数学 * 习题:符号化下列命题,并论证其结论: 任何人如果他喜欢步行,他就不喜欢乘汽车,每一个人或 者喜欢乘汽车,或者喜欢骑自行车。有的人不爱骑自行车,因而有的人不爱步行。 命题符号化:设P(x):x喜欢步行。Q(x):x喜欢乘汽车. R(x):x喜欢骑自行车。 推理的形式结构: * 离散数学 * 结构形式: 前提引入 ES,(1) 前提引入 US ,(3) (5)Q(c) 析取三段论 (2),(4). 前提引入 (7) P(c)?﹁Q(c) US,(6) (8) Q(c) ?﹁P(c) 等值演算,(7). EG,(9). 证明:推理如下: (9) ﹁P(c) 假言推理 (5),(8). 10 离散数学 * 第六章 一阶逻辑 * 离散数学 * 逻辑学中的三段论 1 凡有理数都是实数 2 1/3是有理数 3 1/3是实数 在命题逻辑中无法表示其推理过程 因为如果我们用P,Q,R分别表示命题1,2,3 则, 按照三段论法,P∧Q? R 可表示上述推理 这就是命题逻辑的局限性 三段论的论断显然正确,但在命题逻辑中P∧Q?R并不是重言式。取P=0,Q=0,R=1,就可弄假P∧Q?R 故其不能正确反映三段论的推理过程 * 离散数学 * 原 因 在命题逻辑中无法将所有命题之间的内在联系反映出来。命题逻辑中描述的三段论,即P∧Q→R,使R是与命题P、Q无关的独立命题。但实际上R是与命题P、Q有关的,只是这种关系在命题逻辑中得不到反映。 要反映这种内在联系,就要对简单命题作进一步分析,分析命题的内部构造,分析出其中的个体词,谓词,量词,研究它们的形式结构及逻辑关系,总结出正确的推理形式和规则,这就是一阶逻辑所研究的内容.一阶逻辑也称谓词逻辑. * 离散数学 * §6.1 谓词与量词 研究对象的全体所构成的集合.又称个体域。 一阶逻辑中论域中的元素.又称个体词。 定义6.1.1 设D是非空个体集合。定义在Dn上取值于 {0,1 }上的n元函数称为n元命题函数或n元谓词。其中Dn表示D的n次笛卡尔积. 1.论域: 2.个体: 令P(x)表示x为质数,则P(x)为一元谓词。 令H(x,y)表示“x高于y”。则H(x,y)为二元谓词。 将x代以个体“张三”,y代以个体“李四”, 则H(张三,李四)就是命题“张三高于李四”。 注意: P(x.y)与H(x,y)为命题函数.而P(2)与H(张三,李四)才是命题。 例子: 3.量词: 在命题中表示数量的词.分两类.即存在与全称量词. * 离散数学 * 概念的讨论 谓词是用来刻划个体的性质或个体之间的关系的。 一元谓词描述了个体的性质, n元谓词反映了n个个体之间的某种关系。 变元在谓词中的次序直接影响了谓词的取值. 如:谓词P(x,y)为“x比y高”. 而张三为170cm,李四为180cm. 则:P(李四,张三)为真命题. P(张三,李四)为假命题. 个体是可以独立存在的实体,它既可以是一个具体的 事物,也可以是一个抽象的概念 用个体,谓词表示命题的例子: * 离散数学 * 例子: 1,武汉位于重庆与上海之间. 解:个体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). ﹁P?﹁(A(x)?B(x)) ? ﹁(﹁A(x) ∨B(x)) ?A(x) ∧ ﹁B(x) 这样, ﹁P译为“所有有理数都不是实数” 矛 盾 原 因 仅引进谓词还不足以确切地刻画命题,例如: 日常生活中,上述命题P为: “凡有理数都是实数”。 而命题P的否定﹁P,应理解成,“有些有理数不是实数” 但是 * 离散数学 * 原因: 命题P的确切意思为:“对任意x,如果x是有理数,则x是实数”。但是,A(x)?B(x)中并没有确切表达出“对任意x”这个意思。这说明, A(x)?B(x)还不是一个命题。因此,在一阶逻辑中,除了引进谓词外,还需要引进语句“对任意x”,以及与之对偶的语句“存在一个x”。 * 离散数学 * 定义 6.1.2: 当且仅当对任意x∈D,G(x)均为真。 当且仅当存在一个 x0∈D,使G(x0)为假。 当且仅当存在一个x0 ∈ D ,使G(x0) 为真; 当且仅当对任意x ∈ D , G(x)均为假。 语句“对任意x”称为全称量词,记为: 语句“存在一个x”称为存在量词,记为 : 设G(x)是一个一元谓词,D是论域。 其真值规定为: 其真值规定如下: * 离散数学 * 两个重要的式子: 则,三段论法中的命题P 及﹁P可符号化如下: 此时,﹁P确实是命题“凡有理数都是实数”的否定。 当论域D为有限集时,如D={a1,a2 ,…,an}, 对于任意一元谓词G(X),都有 即消去了量词,化成了命题逻辑中等值的命题公式。 注意: ??x(?(A(x) →B(x)) 至P24 * 离散数学 * 将命题符号化时,必须明确所涉及到的个体集合,即论域。 例子: 而我们约定,除非特别说明,所有论域均为由一切对象组成的个体集合。 论域的讨论: 令: M (x) : x 是人。 D (x) : x 要死。 对命题“人是要死的” 如果论域是全人类,可符号化为 如果论域是世界上一切生物,可符号化为 * 离散数学 * 命题符号化的例子: 例1:没有不犯错误的人 令H(x): x是人, M(x): x犯错误 例2:闪光的未必都是金子 令L(x): x是闪光的, G(x): x是金子 例3:存在着偶质数 令E(x):x是偶数, P(x):x是质数 则有:?x(E(x)∧P(x)) * 离散数学 * 例4:每个自然数都有后继数 令N(x):x 是自然数, H(x,y):y是x的后继数 例5:对平面上的任意两点,有且仅有一条直线通过这两点 令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指纹相同 * 离散数学 * 习 题 (1)任何金属都可以溶解在某种液体中. (2)每一个人的祖母都是他父亲的母亲. 解(1): 令J(x):x是金属; E(x):x是液体; S(x,y):x可以溶解在y中, (2): 令P(x):x是人; F(x,y):y是x的父亲; M(x,y):y是x的母亲; G(x,y)x是y的祖母; * 离散数学 * 习 题: 令P(x)为“x是质数”,E(x)为“x是偶数”,O(x)为“x是奇数”,D(x,y)为“x除尽y”.把下列各式译成汉语. 解: (a) 对所有x,若x是偶数,则对所有y,若x除尽y,则y是偶数. (b)对所有x,若x是质数,则存在y,y是偶数且x除尽y (c)对所有x,若x是奇数,则对所有y,y是质数,则x不能除尽y. (即所有质数能除尽某些偶数) (即任何奇数不能除尽任何质数). y * 离散数学 * §6.2 合式公式及解释 当论域D给出时,它可以是D中的某个元素。 当论域D给出时,它可以是D中的任何一个元素。 引进合式公式的概念,在形式化中使用的四种符号: 第一,常量符号: a,b,c,ai,bi,ci …i≥1 第二,变量符号: x,y,z ,xi,yi,zi …i ≥ 1 第三,函数符号: f,g,h ,fi,gi,hi …i ≥ 1 第四,谓词符号: P,Q,R ,Pi,Qi,Ri …i ≥ 1 当论域D给出时,n元函数符号f(x1,…xn)可以是D n到D的任意一个映射。 当论域D给出时,n元谓词符号P(x1,…xn) 可以是Dn到{0,1}的任意一个 谓词。 * 离散数学 * 项的定义(定义6.2.1): (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)=x·y是项, f(a,g(x,y))=a+x·y也是项。 * 离散数学 * 原子与公式(定义6.2.2,6.2.3): 6.2.2. 设P(x1,…xn)是n元谓词,t1,…,tn是项, 则称P(t1,…tn) 为原子公式,或简称原子。 6.2.3. 一阶逻辑中的合式公式,也称为谓词公式,简称为公式,其递归定义为: (1)原子是合式公式; (2)若A是合式公式,则(﹁A)也是合式公式; (3)若A,B是合式公式,则(A∧B), (A∨B), (A→B), (A?B)也是合式公式; (4)若A是合式公式,x是A中的变量符号, (5)只有有限次地使用(1)—(4)所生成的符号串 才是合式公式。 * 离散数学 * §6.1中各命题符号化的结果都是合式公式。 对于一个谓词,如果其中每一个变量都在一个量词的作用之下,则它就不再是命题函数而是一个命题了。但是,这种命题和命题逻辑中的命题还是有区别的。因为这种命题中毕竟还有变量,尽管这种变量和命题函数中的变量有所不同。因此,有必要区分这些变量。 * 离散数学 * 约束变量与自由变量(定义6.2.4): 1 在一个谓词公式中变量的出现说是约束的,当且仅当它出现在使用这个变量的量词作用域之内。 3 至少有一次约束出现的变量,称为约束变量。至少有一次自由出现的变量,称为自由变量。 2 变量的出现说是自由的,当且仅当它的出现不是约束的。 上例中的R(x)中x的出现是自由的,y和z的出现也是 自由的。 例子: 例子: 例子: 上例中的x既是自由变量,又是约束变量,而y和z则是自由变量。 * 离散数学 * 有关公式中变量的两条规则: 改名规则: 将谓词公式中出现的约束变量改为另一个约束变量。此改名必须在量词作用域内各处以及该量词符号中进行,且改成的新约束变量要与改名区域中的其它变量有别。 代替规则:对公式中某变量的所有自由出现,用另一个 与原公式中其它变量符号均不同的变量符号来代替。 例子: 例子: 因此,通过使用改名规则和代替规则,可使一阶逻辑中的 公式不出现某变量既是约束变量又是自由变量的情况。 * 离散数学 * 解释(定义6.2.4): 在一阶逻辑中,公式G的一个解释I,是由非空论域D和对G中常量符号、函数符号、谓词符号按下列规则进行的一组指定所组成。 1) 对每个常量符号,指定D中一个元素; 对每个n元函数符号,指定一个函数,即指定一个 Dn到D的映射; 对每个n元谓词符号,指定一个谓词,即指定一个 Dn到{0,1}上的映射。 注意:为统一起见,对以上定义中的公式规定:公式中 无自由变量,或将自由变量看作常量。于是,每个公式 在任何具体解释下总表示一个命题。 * 离散数学 * 例 子: 显然此公式在解释I下,取1值(为真)。因为: 给出论域 对公式中的常量符号a指定为2 指定函数f 另外x=3时,P(f(3))∧Q(3,f(2))为假,注意到对x 的约束是存在量词?x,故此公式在该解释下为真。 指定谓词P(x) 指定谓词Q(x,y) * 离散数学 * 习题 给定解释I如下: (1) Di:={2,3}; (2) a?=2; (3) 函数f(x)为f(2)=3,f(3)=2; (4) 谓词: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下,求下列各式的线)) ?(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)) ∧(L(3,2) ∨L(3,3)) ?1 ∧1?1. 注意 * 离散数学 * 谓词公式的分类: 定义6.2.5:设G是一个谓词公式 如果存在解释I,使G在I 下为真(I 满足G),则称G是可满足的。 如果所有解释I均不满足G(弄假),则称G是恒假的,或不可满足的。 如果G的所有解释I都满足G,则称G是恒真的。 定理:一阶逻辑的判定问题是不可解的,即不存在一个统一的算法A,对一阶逻辑中的任何谓词公式G,A能够在有限步内判定公式G的类型。 但,一阶逻辑是半可判定的,即如果谓词公式G是恒真 的,那么,存在算法在有限步内能检验出G的恒真性。 解释I依赖于非空个体集合D,而D可以是无穷集合,D的 数目也可是无穷的。故要考虑公式的所有解释是很难的。 * 离散数学 * 判断下列公式的类型: * 离散数学 * 解答: (1)无论对Q指派何种命题常元,Q∨﹁Q的线.而在I中对任意的x,总存在y=1使x-1x+1成立 (2)因为x-yx+y在I中的线时, x-yx+y取值为线时,x-yx+y取值为假. 故(2)为可满足式. * 离散数学 * §6.3 等值式与范式: 定义6.3.1:设A、B是谓词公式。若A?B是恒真公式,则称A与B是等值的,记为A?B,否则记为A?B,称A?B为等值式。 显然, A?B当且仅当对任何解释I,I同时满足A与B,或I同时弄假A与B。 分类给出一阶逻辑中一些重要的等值式: 1 命题公式的推广 2 量词否定等值式 3 量词作用域的收缩与扩张等值式 4 量词分配等值式 * 离散数学 * 1 命题公式的推广 由于命题逻辑中的公式都可看作特殊的谓词公式,因此,§14.2(P189) 给出的19个基本等值式,以及对其中每个等值中的同一命题变元用同一谓词公式代入,所得的关系式都是一阶逻辑中的等值式。 例1:由P?Q?﹁P∨Q可得 例2: 可得 * 离散数学 * 2 量词否定等值式 定理:设G(x)是恰含一个自由变元x的谓词公式,于是有: 证明:设D是论域 (1) 同理可证(2). 若I满足?(?xG(x)) G 离散数学

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

本文链接:http://scrinzoom.com/qianshufanshi/544.html