我要投搞

标签云

收藏小站

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

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

【5A版】离散数学之谓词逻辑ppt

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

  2.1命题逻辑的局限性: 下列推理:凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 众所周知,这是真命题。但在命题逻辑中 ,难证其为重言式。原因:命题逻辑不考虑命题之间的内在联系 和数量关系。 办法:将命题再次细分。 2.1 在反映判断的句子中,用以刻划客体的性质或关系的即是谓词。 例:(1)3是有理数。 (2)x是无理数。 (3)阿杜与阿寺同岁。 (4)x与y有关系L。 其中,“是有理数”、“是无理数”、 “与…同岁”、“…与…有关系L”均为谓词。 前两个是指明客体性质的谓词,后两个是指 明两个客体之间关系的谓词。 2.1 将上述谓词分别记作大写字母F、G、H、L, 用小写字母表示客体名称,则上述可表示为: 单独一个谓词不是完整的命题,把谓词字母后填以客体所得的式子称为谓词 由n个客体插入到固定位置上的谓词填式。 例如:A(b)称作一元谓词,B(a, b)称作二元 谓词,L(a, )称作n元谓词。注意:代表客体名称的字母,它在多元谓词 中出现的次序是固定的,与事先约定的次序 有关,如L(a, a)代表两个不同的命题。 2.2 例:H是谓词“能够到达山顶”,t表示老虎, c表示汽车,z表示张三,那么H(t), 表示三个不同的命题,但它们有一个共同的形式H(x),当x分别取t, y)表示“x小于y”,那么L(2,3)表示了一 个线”。可以看出,L(x, y)本身不是一 个命题,只有当变元x, y取特定的客体时, 才是一个命题。 2.2 由一个谓词,一些客体变元组成的表达式称为简单命题函数。 n元谓词就是有n个客体变元的命题函数。 不带任何客体变元的谓词称为0元谓词。 由一个或n个简单命题函数以及逻辑联结词组合而成的表达式称复合命 题函数。 2.2 命题函数不是一个命题,只有客体变元取特定名称时,才能成为一个命题。 但客体变元在哪些范围内取特定的值,对是否成为命题及命题的真值极有影响。 例:R(x)表示“x是大学生”,如果x的讨论范 围是某大学里班级中的学生,则R(x)是永真式。 如果x的讨论范围是某中学里班级中的学生, 则R(x)是永假式。如果x的讨论范围为一剧场 中的观众,那么对某些观众,R(x)为真,对另 一些观众,R(x)为假。 2.2 个体常量:具体的或特定的,一般用a,b,c,…表示。 个体变元:抽象的或泛指的,一般用x,y,z,…表示。 把各种个体域综合在一起作为论述范围的域。 2.2 量词用来表示个体常量或变元之间数量 关系的词。量词分为两种: 有”,“凡”,“每一个”,“任意”等意的词称为全称量词,记作。 表示个体域内所有的x。存在量词 表示“某个”, “对于一 些”,“存在一些”,“至少有一个”等意的 词称为存在量词,记作。 表示个体域内存在一些y。2.2 例:用谓词表达式写出下列命题。 (1)凡是人都呼吸。 (2)有的人是左撇子。 呼吸。G(x):x是左撇子。 当个体域为人类集合时: xF(x)(2)xG(x) 当个体域为全总个体域时: 2.2约定:以后如不指定个体域,默认为全总个 特性谓词在讨论带有量词的命题函数时, 必须确定其个体域。当使用全总个体域时, 对客体变元的变化范围限制的词,称作特性 谓词。 如上例中,M(x)为F(x)和G(x)的特性谓词, 它限定了变元x的范围。 一般,对全称量词,特性谓词常作条件的前 件;对存在量词,特性谓词常作合取项。 2.2 例:将下列命题符号化,并讨论其线)所有的人都长头发。 线)有的人吸烟。 线)没有人登上过木星。 线)清华大学的学生未必都是高素质的。 可见,有些命题的符号化形式不止一种。2.2 至此,下列推理即可解决: 凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 一阶语言F的字母表定义如下: 的任意n元谓词,t )为谓词演算的原子公式。2.3 (1)原子公式是合式公式。(2)若A是合式公式,则(A) 也是合式公式。 (AB),(AB)也是合式公式。(4)若A是合式公式,x是A中出现的任何变元, 则xA和xA,也是合式公式。 (5)只有有限次应用规则(1)~(4)构成的符号串 才是合式公式。 2.3 约定:最外层的圆括号可以省略。但量词后 面若有括号则不能省略。 例:将下列命题符号化。 (1)没有不能表示为分数的有理数。 2.3(2)在北京买菜的人不全是外地人。 例:将下列命题符号化。(1)火车都比轮船快。 2.3(2)有的火车比有的汽车快。 给定A为一谓词公式,其中有一部分公式形为xP(x)或xP(x)。和后面所跟的x,称 为相应量词的 。P(x)称为相应量词 所有出现都称为x在公式A中的约束出现,所有约束出现的变元,叫做 x是指导变元,量词的辖域是F(x,y),其中,x是约束出现一次,y是自由出现一次;同时, y也是指导变元,量词的辖域是G(x,y),其 中,y是约束出现一次,x是自由出现一次。 2.4 ,其中x是约束出现一次,y是约束出现两次,z是 自由出现一次;后一个x也是指导变元,量 词的辖域为H(x,y,z),其中x是约束出现一 次,y、z是自由出现一次。 2.4 为了避免由于变元的约束与自由同时出现,引起概念上的混乱,故可对约束变元进行 。使得一个变元在一个公式中只呈一种形 式出现,即呈自由出现或呈约束出现。 一个公式的约束变元所使用的名称符号是无关紧要的,即xP(x)与yP(y)具有相同的意 义,xP(x)与yP(y)意义也相同。 2.4 对于约束变元可以换名,其更改的变元名称范围是量词中的指导变元,以及该量词 作用域中所出现的该变元,公式的其余部 分不变。 换名时一定要更改为作用域中没有出现的变元名称。 对于公式中的自由变元,也允许更改,这种更改叫做 对于谓词公式中的自由变元,可以作代入,代入时需对公式中出现该自由变元的每一 处进行。 用以代入的变元与原公式中所有变元的名称不能相同。 2.4 )是n元谓词,它有n个相互独立的自由变元。若对其中k个变元进行约束 k元谓词。若谓词公式中没有自由变元出现,则该式就成为一个命题。 当论域的元素有限时,可以消去公式中的量词。设论域元素为a 量词对变元的约束,往往与量词的次序有关。命题中的多个量词,我们约定从左到右的次 序读出。注意: 量词的次序不能颠倒,否则 将与原命题不符。 2.5 在谓词公式中常包含命题变元和客体变元,当客体变元由确定的客体所取 代,命题变元用确定的命题所取代时,就称 作对谓词公式赋值。一个谓词公式经过赋值 以后,就成为命题。 给定任何两个谓词公式wffA和wff 的任一组真值指派,所得真值均相同,则称谓词公式A和B在E上是等价的,并记作 给定任意谓词公式wffA,其个体域为E,对于A的任一组真值指派, wff A皆为1,则称公式A在E上是有效的/永 真的。 一个谓词公式wffA,如果至少 在一种赋值下为T,则称该wff A是可满足的。 2.5 谓词演算中的等价式和蕴涵式命题演算中 的等价公式表和蕴含公式表都可推广到谓词 演算中使用。 证明:(可在有限个体域上证明)2.5 设个体域中的客体变元为a 或含有与量词指导变元x 不同的变元, 后四种均不等价,故全称量词和存在量词在公式中出现的次序,不能随意更换。 2.5 2.6 一个公式如果量词均包含在全式的开头,它们的作用域延伸到整个公式的 末尾,则该公式叫做前束范式。其形式为 (i=1,2,…,n)是客体变元,A是没有量词的谓 词公式。 Th1(前束范式存在定理)任意一个谓词公 式,均和一个前束范式等价。 本定理说明任何公式的前束范式都是存在的,但一般不是唯一的。 利用对合律、德摩根律、量词转化律把否定深入到命题变元和谓词填式的前面; 利用换名和代入规则,量词作用域的扩张和收缩等价式,把量词提到前面。 2.6 解:xF(x)xG(x) xF(x)xG(x) (量词否定等价式) (量词分配等价式)或xF(x) yG(y) (换名规则) xF(x)yG(y) (量词否定等价式) (量词辖域扩张等价式)2.6 解:原式xF(x) yG(y) (换名规则) xF(x)yG(y) (量词否定等价式) 解:原式xF(x)yG(y) (换名规则) (量词辖域扩张等价式)2.6 解:原式xF(x)yG(y)(换名规则) (量词辖域扩张等价式)2.6 一个wffA如果具有如下形 式,则称为前束合取范式。 )…(Am1Am2…Amk (i=1,2,…,n)是客体变元,Ai j是原子公式或其否定。 Th2(前束合取范式存在定理)每一个wff 都可转化为与其等价的前束合取范式。2.6 一个wffA如果具有如下形 式,则称为前束析取范式。 )…(Am1Am2…Amk (i=1,2,…,n)是客体变元,Ai j是原子公式或其否定。 Th3(前束析取范式存在定理)每一个wff 都可转化为与其等价的前束析取范式。2.6 任一个wffA转换为等价的前束合(析)取范 式的步骤: 利用换名、代入规则使所有约束变元均不相同,并且使约束变元和自由变元不同; 利用对合律,德摩根律及量词转化律,将谓词公式中的 深入到命题变元和谓词填式 的前面; 利用量词作用域的扩张和收缩等价式,将量词推到左边,扩大量词作用域至整个公 命题演算中的推理规则,如P、T和CP规则等也可在谓词演算的推理理论中应用。 但在谓词推理中,某些前提与结论可能受量词限制,为了能使用命题演算中的等价式和 蕴含式,必须在推理过程中有消去和添加量 词的规则。 2.7 2.7例:构造下列推理的证明。 前提:x (5)EG注意:(1) (3)引入的顺序不可更改! 2.7 例:证明凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 2.7例:学术委员会的每个成员都是博士并且是 教授。有些成员是青年人。因而有的成员是 青年博士。 解:先将命题符号化. A(x):x是学术委员会成员。B(x):x是博士。 J(x):x是教授。 H(x):x是青年人。 前提: 2.7证明 合取(10) (9)EG2.7 例:有些病人相信所有的医生。但是病人都 不相信骗子。所以,医生都不是骗子。 解:先将简单命题符号化 A(x):x是病人。 B(x):x是医生。 J(x):x是骗子。 (1)ES2.7 (4)US(10) (8)US(11) (9)(10)假言三段论(12)

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