我要投搞

标签云

收藏小站

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

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

第2章 谓词逻辑(一)

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

  第2章 谓词逻辑(一)_数学_自然科学_专业资料。离 散 数 学 戎 玫 2005-9 第2章 谓词逻辑 2.1 个体、谓词与量词 2.2 谓词公式 2.3 谓词演算的等价式与蕴含式 2.4 前束范式 2.5 谓词逻辑的推理理论 2.1 个

  离 散 数 学 戎 玫 2005-9 第2章 谓词逻辑 2.1 个体、谓词与量词 2.2 谓词公式 2.3 谓词演算的等价式与蕴含式 2.4 前束范式 2.5 谓词逻辑的推理理论 2.1 个体、谓词与量词 2.1 .1 个体 苏格拉底推论 所有的人总是要死的 苏格拉底是人 苏格拉底总是要死的 将原子命题进一步细分,分解出个体、谓词和量词,以表 达个体与总体的内在联系和数量关系,即谓词逻辑研究的 内容。 2.1 .1 个体 考察下面的三个原子命题: ⑴ 李玲是优秀员。 ⑵ 张华比李红高。 ⑶ 小高坐在小王和小刘的中间。 个体是指所研究对象中可以独立存在的具体的或抽象的客 体。 个体常用小写英文字母或小写英文字母带下标表示,叫做 个体标识符。 表示具体或特定个体的标识符称个体常元。 例如:李玲、张华可如下表示: a:李玲 b:张华 2.1 .1 个体 将表示任意个体或泛指某类个体的标识符称为个体变元, 常表示为x、y、z、…等或这些英文字母带下标。 个体变元的变化范围称为个体域或论域。 个体域可以是有穷集合,也可以是无穷集合,包含任意个 体域的个体域称为全总个体域,它是由宇宙间一切对象组 成的集合。 在本书中,如无特别说明,所采用的都是全总个体域。 2.1.2谓 词 刻划个体性质或几个个体关系的模式叫做谓词。 谓词常用大写英文字母表示,叫做谓词标识符。 例如可以用F,G,H表示前面三个命题中谓词: F:…是优秀员。 ⑴可以分解成为个体“李玲”和“…是优秀员” 两部分。“…是优秀员”是用来描述个体“李玲” 的性质; G:…比…高。 H:…坐在…和…的中间。 2.1.2谓 词 把与一个个体相关联的谓词叫做一元谓词。 把与两个个体相关联的谓词叫做二元谓词。 把与三个个体相关联的谓词叫做三元谓词。 一般的,把与n个个体相关联的谓词叫做n元谓词。 F是一元谓词; G是二元谓词; H是三元谓词; 2.1.2谓 词 设F是一元谓词,a是个体常元,用F(a)表示个体常元a具有 性质F; 设G是二元谓词,a,b是个体常元,用G(a,b)表示个体常元a 和b具有关系G; 于是上面三个命题就表示为: F(a):李玲是优秀员。 G(b,c):张华比李红高。 H(d,e,f):小高坐在小王和小刘的中间。 将谓词后面填上相关联的个体常元所得的式子叫做谓词填 式。F(a),G(b,c),H(d,e,f)都是谓词填式。谓词填式表 示的是命题。 2.1.2谓 词 类似的,用F(x)表示个体变元x具有性质F ,F(x)叫做一元 命题函数; 用G(x, y)表示个体变元x和y具有关系G ,G(x,y)叫做二元 命题函数; 用P(x1,x2,…,xn)(n≥1)表示个体变元x1, x2, …,xn具有关系P。 P(x1,x2, …,xn) 为n元命题函数。 命题函数没有确定的真值,它不是命题。只要用个体常元 取代所有的个体变元,就得到了命题。 2.1.2谓 词 例,H(x,y):x+y≥0,此命题函数是否为命题? 令 a:5, H(a,b) b:-7 是否为命题?真值? 用个体常元取代命题函数的所有个体变元所得到的表达式 就是谓词填式,谓词填式也叫做0元命题函数。 F(a),G(b,c),H(d,e,f)都是0元命题函数,它们都是命题。 命题逻辑中的命题均可以表示为谓词逻辑中的0元命题函数 (谓词填式),命题成为命题函数的特例。 2.1.2谓 词 【例2.1】将下列命题符号化,并讨论它们的线。 解:⑴ 设F(x):x是偶数。 a:2,b:3 该命题符号化为: F(a)∧F(b) F(b)表示3是偶数,它是个假命题。所以F(a)∧F(b)为假。 ⑵ 设G(x,y): x大于y a:5,b:3,c:2,d:6 该命题符号化为:G(a,b)→G(c,d) G(a,b)表示5大于3,它是真命题。G(c,d)表示2大于6,这 是个假命题。所以G(a,b)→G(c,d)为假。 2.1.3 量词 量词分两种: ⑴ 全称量词 全称量词符号化为“?”。 即“一切的”,“所有的”, “每一个” 等。用(?x),(?y)等表示个体域里的所有个体, (?x)F(x) 表示个体域中的所有个体都有性质F。 ⑵ 存在量词 存在量词符号化为“?”。即“存在”,“有一个”,“有 些” 等。用(?x),(?y)等表示个体域里有些个体,用(?x)F(x) 表示在个体域中存在个体具有性质F。 全称量词与存在量词统称为量词。 2.1.3 量词 【例2.2】个体域是人类集合,对下列命题符号化。 ⑴ 凡人要死。 ⑵ 有的人是研究生。 解:⑴ 令F (x):x要死。 命题“凡人要死。”符号化为:(?x)F (x) ⑵ 令G(x):x是研究生。 命题“有的人是研究生。”符号化为:(?x)G(x) 在命题函数前加上量词(?x)和(?x)分别叫做个体变元x被全称 量化和存在量化。如果对命题函数中所有命题变元进行全称 量化或存在量化,该函数就变成了命题。 2.1.3 量词 【例2.3】对下列命题符号化,并在①,②,③三个个体域中 考察命题的真值。 命题:⑴ 所有数小于5。 ⑵ 至少有一个数小于5。 个体域: ① ?-1,0,1,2,4? ② ?3,-2,7,8? ③ ?15,20,24? 解:设L(x):x小于5。 ⑴ “所有数小于5。”符号化为:(?x) L(x) 在个体域①,②,③中,它们的真值分别为:真,假,假。 ⑵ “至少有一个数小于5。”符号化为:(?x)L(x) 在个体域①,②,③中,它们的真值分别为:线 量词 设个体域为D={-2,3,6},谓词P(x):x≤3,G(x):x>5, R(x):x≤7,求下列各谓词公式的线、 (?x)(P(x)∧ G(x)) 。 2、 (?x)(R(x)→ P(x))∨G(5) 3、 (?x)(P(x)∨G(x)) 解: 2.1.3 量词 命题函数中的个体变元量化以后变成命题,其真值与个体域 的选择有关,为了统一我们使用全总个体域,而对于其它个 体域用一个谓词来表示,即特性谓词。 特性谓词:用一个谓词来表示除全总个体域外的特殊的个体 域。 特性谓词加入的方法为: ⑴ 对全称量词,特性谓词作为条件命题的前件加入。 ⑵ 对存在量词,特性谓词作为合取项加入。 2.1.3 量词 【例2.4】对下列命题在①,②两个个体域中符号化。 命题:⑴ 所有老虎是要吃人。 ⑵ 存在一个老虎要吃人。 个体域: ① 所有老虎组成的集合。 ② 全总个体域。 解:设A(x):x是要吃人的。个体域为所有老虎的集合。 ⑴符号化为 (?x)A(x) ⑵符号化为 (?x)A(x) 个体域为全总个体域。设特性谓词T(x):x是老虎。 ⑴符号化为 (?x)(T(x)→A(x)) ⑵符号化为 (?x) (T(x)∧A(x)) 2.1.3 量词 有些自然数是素数。 金子是闪光的,但闪光的并不都是金子。 所有运动员都钦佩某些教练员。 解:设N(x):x是自然数。 P(x):x是素数。 (?x)(N(x)∧ P(x)) 解:设G(x):x是金子。 S(x):x是闪光的。 (?x)(G(x)→S(x))∧(?x)(S(x)∧? G(x)) 解:设L(x):x是运动员。 C(x):x是教练员。 A(x,y):x 钦佩y。 (?x)(L(x)→(?y)(C(y)∧A(x,y))) 2.2.1 谓词公式 定义2.2.1 按下列规则构成的表达式称为谓词演算的合式公 式,简称谓词公式。 ⑴谓词演算的原子公式是合式公式。 ⑵若A是合式公式,则? A是合式公式。 ⑶ 若 A 和 B 是 合 式 公 式 , 则 (A∧B) , (A∨B) , (A→B) 和 (A?B)是合式公式。 ⑷如果 A 是合式公式, x 是 A 中出现的任意个体变元,则 (?x)A,(?x)A是合式公式。 ⑸ 只有有限次地应用⑴、⑵、⑶、⑷所得的公式是合式公 式。 2.2.1 谓词公式 谓词公式也有以下约定: ⑴ 最外层的括号可以省略。 ⑵ 如果按? 、∧、∨、→、?在运算中的优先级别,省 略括号后不改变原来的运算次序,可以省略括号,但量 词后面括号不能省略。 2.2.1 谓词公式 【例2.5】并非每个实数都是有理数。 解:设R(x):x是实数 Q(x):x是有理数 该命题符号化为:? (?x)(R(x)→Q(x)) 【例2.6】没有不犯错误的人。 解:设M(x):x是人 F(x):x犯错误 符号化为:(?x) (M(x)→F(x)) 【例2.7】并不是所有的兔子都比所有的乌龟跑得快。 解:设F(x):x是兔子。 G(x):x是乌龟。 H(x,y):x比y跑得快。 该命题符号化为:? (?x) (?y) (F(x)∧G(y)→H(x,y)) 2.2.2约束变元与自由变元 定义2.2.2 如果A是谓词公式B的一部分且是谓词公式,则称 A是B的子公式。 定义2.2.3 紧接量词以后的最小子公式叫做该量词的辖域或 作用域。 定义2.2.4 量词(?x)和(?x)中的x叫做该量词的指导变元或作 用变元。 定义2.2.5 量词(?x)和(?x)的辖域内x的一切出现叫约束出现, x叫做约束变元;约束变元以外的其它变元的出现叫自由出 现,自由出现的变元叫自由变元。 2.2.2约束变元与自由变元 【例2.10】说明下列各式量词的辖域,找出约束变元和自由变元。 ⑴ (?x)P(x)→Q(y) ⑶ (?x) P(x)∧(?y)Q(x,y) ⑷ (?x)(?y)(P(x,y)∧Q(y,z))? (?x) R(x,y) ⑵ (?x) (P(x)∧(?y)Q(x,y)) 解:⑴(?x)的辖域为P(x),x是约束变元,y是自由变元。 ⑵(?x)的辖域为P(x)∧(?y)Q(x,y),(?y)的辖域为Q(x,y),x和y都是约 束变元,无自由变元。 ⑶(?x)的辖域为P(x),(?y)的辖域为Q(x,y),P(x)中的x和Q(x,y) 中的 y是约束变元,Q(x,y)中的x是自由变元。 ⑷(?x)的辖域为(?y)(P(x,y)∧Q(y,z)),(?y)的辖域为P(x,y)∧Q(y,z), (?x)的辖域为R(x,y),x是约束变元,z是自由变元,(P(x,y)∧Q(y,z))中的 y是约束变元,R(x,y)中的y是自由变元。 2.2.2约束变元与自由变元 换名规则: ⑴对约束变元可以换名,其更改变元名称的范围是量词 的指导变元,以及该量词辖域中的所有该变元,公式的其余 部分不变。 ⑵换名时一定要更改成辖域中没有出现的变元名,最好 是公式中没有的变量名。 代入规则是: ⑴ 对于谓词公式中的自由变元可以代入,代入时需对公 式中该变元自由出现的每处进行。 ⑵ 代入的变元与原公式中其他变元的名称不能相同。 2.2.2约束变元与自由变元 【例2.11】对(?x)(?y)(P(x,y)∧Q(y,z))?(?x) R(x,y)中的约束变 元y换名。 解:用u置换约束变元y。换名后为: (?x)(?u)(P(x,u)∧Q(u,z))?(?x) R(x,y) 不能换成: (?x)(?u)(P(x,u)∧Q(y,z))?(?x) R(x, y) 也不能换成:(?x)(?z)(P(x, z)∧Q(z,z))?(?x) R(x,y) 【例2.12】对(?x)(P(y)∧R(x,y))→(?y)Q(y) 中的自由变元y进 行代入。 解:用z代换y,代入后为: (?x)(P(z)∧R(x,z))→(?y)Q(y) 不能换成: (?x)(P(x)∧R(x,x))→(?y)Q(y) 或 (?x)(P(z)∧R(x,y))→(?y)Q(y) 2.2.2 约束变元与自由变元 自然数有以下三条公理: 1、每个数都有唯一的一个数是它的后继数。 2、没有一个数使数1是它的后继数。 3、每个不等于1的数都有唯一的一个数是它的直接先驱数。 解:设N(x):x是自然数。 S(x,y):y是x的后继(x是y的先 驱)。 1、 (?x)(N(x)→(?y)(N(y)∧S(x,y)∧? (?z)((z≠y)∧ N(z)∧S(x,z)))) 2、 ? (?x)(N(x)∧S(x,1)) 3、 (?x)(N(x)∧? S(x,2) →(?y)(N(y)∧S(y,x)∧ ? (?z)((z≠y)∧N(z)∧S(z,x)))) 2.3谓词演算的等价式与蕴含式 定义2.3.1 设A是谓词公式,如果对A的任何赋值,A都为真, 则称A是有效的或永线 设A是谓词公式,如果对A的任何赋值,A都为假, 则称A是不可满足的或永假的。 定义2.3.3 设A是谓词公式,如果至少有一组赋值使A为真, 则称A是可满足的。 定义2.3.4 设A、B是任意两个谓词公式,对A、B的任何赋 值,若其真值相同,则称A与B是等价的,记作A?B;若 A→B是有效的,则称A蕴含B,记作A?B。 2.3谓词演算的等价式与蕴含式 1.命题逻辑中的等价式的推广 ⑴命题演算中的所有等价式都是谓词演算中的等价式。 从定义2.2.1可以看出,命题演算的合式公式都是谓词演算 的合式公式。再根据定义2.3.4,命题演算中的所有等价式都 是谓词演算中的等价式。 ⑵命题逻辑中的等价式的推广 在命题逻辑中,重言式的同一分量出现的每一处都用同一 合式公式置换,其结果仍是重言式(定理1.4.2)。在谓词逻辑 中可以推广为:在永真的谓词公式中,命题变元出现的每一 处都用同一谓词公式置换,其结果仍是永线谓词演算的等价式与蕴含式 2.消去量词等价式 设个体域为有限集?a1,a2,…,an?,A(x)是含自由变元x 的任意谓词公式,有下列等价式成立: (?x)A(x)?A(a1)∧A(a2)∧…∧A(an) (?x)A(x)?A(a1)∨A(a2)∨…∨A(an) 3.量词否定等价式 设A(x)是含自由变元x的任意谓词公式。则 ? (?x)A(x)?(?x)? A(x) ? (?x)A(x)?(?x)? A(x) 约定,量词之前的否定联结词,不是否定该量词,而是 否定该量词及其辖域。 2.3谓词演算的等价式与蕴含式 4.量词作用域的扩展与收缩等价式 设 A(x) 是含自由变元 x 的任意谓词公式。 B 是不含变元 x 的 谓词公式,则 (?x)(A(x)∨B)?(?x)A(x)∨B (?x)(A(x)∧B)?(?x)A(x)∧B (?x)(A(x)∨B)?(?x)A(x)∨B (?x)(A(x)∧B)?(?x)A(x)∧B 利用上述四式可以得到以下四式: (?x)(A(x)→B)?(?x)A(x)→B (?x)(A(x)→B)?(?x)A(x)→B (?x)(B→A(x))?B→(?x)A(x) (?x)(B→A(x))?B→(?x)A(x) 2.3谓词演算的等价式与蕴含式 5.量词分配等价式 设A(x)和B(x)是含自由变元x的任意谓词公式,则 (?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) (?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x) 前者可以理解为:“所有的x有性质A和性质B”和“所有的 x有性质A且所有的x有性质B”是等同的。后者可以利用前者 来证明。 2.3谓词演算的等价式与蕴含式 6.量词与联结词的蕴含式 设A(x)和B(x)是含自由变元x的任意谓词公式。 (?x)A(x)∨(?x)B(x)?(?x) (A(x)∨B(x)) (?x) (A(x)∧B(x))?(?x)A(x)∧(?x)B(x) (?x) (A(x)→B(x))?(?x)A(x)→(?x)B(x) (?x) (A(x)?B(x))?(?x)A(x)? (?x)B(x) 2.3谓词演算的等价式与蕴含式 【例2.15】证明 (?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) 解: 由第一式可得: (?x)? A(x)∨(?x)?B(x)?(?x)(? A(x)∨? B(x)) 而 (?x)? A(x)∨(?x)? B(x)?? (?x)A(x)∨? (?x) B(x) ?? ((?x)A(x)∧(?x) B(x)) (?x)(? A(x)∨? B(x))?(?x)?(A(x)∧B(x)) ?? (?x)(A(x)∧B(x)) 故有 ? ((?x)A(x)∧(?x) B(x))?? (?x)(A(x)∧B(x)) 由双条件否定等价式有 (?x)(A(x)∧B(x))?(?x)A(x)∧(?x) B(x) 第三、四式可以类似推出。 2.3谓词演算的等价式与蕴含式 7.多个量词的使用 ⑴约定:(?x)(?y) A(x,y)表示(?x) ((?y) A(x,y)) ⑵一般地说,多个量词相连时,同名量词是无序的,即改 变它们的次序,命题真值不变。异名量词是有序的,即改变 它们的次序,命题真值发生变化。对后者作如下的说明: 令A(x,y)表示x+y=10,个体域为整数集合I。 (?x)(?y)A(x,y)表示对任一整数x,存在整数y,使x+y=10。 这是一个真命题。 (?y)(?x)A(x,y)表示存在整数y,对任一整数x,有x+y=10。 这是一个假命题。 2.3谓词演算的等价式与蕴含式 因为同名量词是无序的,所以有: (?x)(?y)A(x,y)?(?y)(?x)A(x,y) (?x)(?y)A(x,y)?(?y)(?x)A(x,y) 异名量词有下列的蕴含关系: (?y)(?x)A(x,y)? (?x)(?y)A(x,y) (?x)(?y)A(x,y)?(?y)(?x)A(x,y) ⑶具有两个量词的谓词公式还有下列的蕴含式: (?x)(?y)A(x,y)?(?y)(?x)A(x,y) (?y)(?x)A(x,y)?(?x)(?y)A(x,y) (?x)(?y)A(x,y)?(?y)(?x)A(x,y) (?y)(?x)A(x,y)?(?x)(?y)A(x,y)

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