【快乐离散数学】谓词与量词 | 您所在的位置:网站首页 › 联结词的性质 › 【快乐离散数学】谓词与量词 |
WEEK1:Propositional Logic, Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers. 写在前面:本系列博客为复习离散的学习笔记,内容主要参考自 Kenneth Rosen 的 《Discrete Mathematics and Its Applications》和重庆大学刘然老师的《离散数学及其应用》课程。 🔗 视频教程:【重庆大学】《离散数学及其应用》刘然_哔哩哔哩_bilibili 目录 Ⅰ. 谓词(Predicates) 0x00 引入:孙笑川,你坏事做尽! 0x01 谓词逻辑(Predicate logic) 0x02 命题函数(Propositional Function) 0x03 复合表达式 Ⅱ. 量词(Quantifiers) 0x00 引入:量化 0x01 全称量词(Full name quantifier) 0x02 存在量词(Existential quantifier) 0x03 惟一性量词 0x04 有限论域和无限论域 0x05 量词的性质 0x06 量词的优先级 0x07 变元的约束 Ⅲ. 谓词与量词(Predicates and Quantifiers) 0x00 谓词逻辑等价式 0x01 把量词看作析取或合取联结词 0x02 量化表达式的否定 0x03 狄摩根定律(De Morgan's laws) 0x04 命题公式的推广 0x05 量词辖域的扩张与收缩 0x06 量词分配等价式 0x07 语句到逻辑表达式的翻译 Ⅳ. 嵌套量词(Nested Quantifiers) 0x00 嵌套量词的概念 0x01 量词的顺序 0x02 嵌套量词到汉语的翻译 0x03 数学语句到嵌套量词的翻译 0x04 汉语语句到逻辑表达式的翻译 0x05 嵌套量词的否定 Ⅰ. 谓词(Predicates) 0x00 引入:孙笑川,你坏事做尽!
❓ 思考:这是否意味着 "孙笑川终有一死" ? "哈哈哈哈啊哈哈,开幕雷击" 💡 解读:不能用命题逻辑来表示,需要一种语言来谈论对象、它们的属性和它们的关系。 假设 这个式子很可惜不是一个永真式,当整个命题取 而我们知道这个确实是真的,人总有一死,那么问题出来哪里? 问题出来我们的描述能力还不够强,句子之间有内在联系。 即 "人皆有一死" 和 "孙笑川是个人" 之间有内在联系, 因此这个地方我们就不能用这种命题逻辑去表达,应该用更为精细的数学符号体系去表达。 因为命题逻辑并不足够,所以要学习谓词逻辑,本节我们将演示用谓词逻辑来进行命题的推论! 0x01 谓词逻辑(Predicate logic)能够表示客体的性质和关系的,我们称之为谓词。谓词逻辑 有以下特征: 变量(variable):像这里的 命题函数就是命题的概括: 它们包含变量和谓词,例如这里的 "论域" 可以理解为高中学的定义域,以 "变量来自于哪里" , 所以我们在明确命题函数时我们一般要谈论其论域才有意义。 0x02 命题函数(Propositional Function)❓ 思考:命题函数是命题吗?显然不是,因为命题函数的变量是不确定的。 但是,当命题函数的变量被域中的值替换时,命题函数就能变成命题。 (并且这个命题具有真值,当然还可以由 "量词绑定" 变成命题,这个我们后面再说) 这时候我们就称 谓词在 💬 假设 当这个命题函数可真可假,它不是命题,但是当用具体的变元(或变量被赋值时),它就变成了一个具体的、可判断真假的命题了。 我们通常定义域用 上面的命题函数只有一个元 比如下面的命题函数就有 …… n元谓词,n-ary predicate 💬 设 🔑 解析:2+(-1)=5 吗?No,所以选F;3+4=7,Yes,所以选T;x+3=z 还是有两个变元,我们无法判断真假,这样的一个式子不是命题(这里只有 x 和 z 都有具体的数时才能变成一个命题)。它就相当于 因为命题没有变量我们也称之为 零元谓词。通过上面这个例子我们不难发现,每确定一个变量就会少一个元,如果把所有的变量都用值代替的话,那就变成了零元谓词(即命题)。 相你信读到这里已经掌握了其中的奥妙,我们来练一题: 💬 现在让 我们可以通过命题逻辑的联结词 同样地,我们也可以用 💬 如果 不难看出,如果我们把值带进去再加上联结词我们就可以像命题公式一样得到它们的真值。 但是有些变量没有带入具体的值,我们知道,带有变量的表达式不是命题,因此没有真值: 当与量词一起使用时(我们下面会介绍量词),这些表达式(命题函数)就变成了命题。 因此,当和两次一起使用的时候,他反而就变成了命题。 Ⅱ. 量词(Quantifiers) 0x00 引入:量化我们需要量词来表达自然语言中的意思,包括所有和某些: 人皆有一死有些猫没有毛最重要的两个量词: 全称量词(Full name quantifier):符号为我们写成 量词在这些表达式中必须绑定变量
🔑 解析: 对于任意的整数都大于 0 显然是错的,比如 -1,任意🔺 总结:所以 "只要看到
核心就是 —— 只要找到一个满足的条件,这个表达式就为真。 若 若 如果 由此可见,存在量词和论域有着很大的关系,在取不同的论域时,它可真可假。 0x03 惟一性量词(Uniqueness quantifier)
(这里 (有无穷多的多 惟一性量词虽然是存在量词的一种,但并不是必要的。因为存在一个惟一的 💭 对量词的思考:当论域是有限的,我们可以认为量化是对论域中所有元素的循环。 比如对于任意的 评估 比如 "全班同学今天都来上课了" ,点名大家都到了,那就为真。 如果点名的时候哪怕只有一个人没到,比如孙笑川(所以坏事都是孙狗做的),那就为假。 评估 比如 "期末考试我们班有满分",只要有一个人是满分,这句话就能成为真。 但是如果一个满分都没有那这句话铁定是假的了,"期末考试我们班有满分" 就是胡说八道。 即使论域是无限的,我们仍然可以这样考虑量词,但是循环在某些情况下将不会终止。 一般情况下我们不需要去论证那么多,比如 📚 性质: 由此看来,它是依赖论域的。 0x06 量词的优先级量词 例如, 它和 这是 📌 注意:可是人们经常喜欢用 📚 定义:在谓词公式中,形如
在 最后, 老师就好比是指导变元,管理你们班,老师的管辖范围就是你们班所有同学,你作为被管的,就是约束变元。而自由变元就好比有个同学到去你们班旁听,他在你们班上就是自由的,他想来上课就来、作业想交就交,不交老师也管不了他,虽然形式上似乎能管,因为他人可以在这个班上,但实际上他不是你们班的人,老师是管不了他的,因为他是旁听的。 💭 例如:
一个公式的约束变元所使用的名称符号是无关紧要的,如 当且仅当由谓词和量词构成的语句具有相同的真值时,他们在逻辑上是等价的。 因为它有可能是无限的,所以我们就要求: 对于每一个被带入的这些语句的谓词。对每个论域中所使用的变量表达式。表示仍然使用三条杠,即符号
双重否定即肯定:¬¬ 如果论域是有限的,一个全称量化的命题等价于每个量词的合取,一个存在量化的命题等价于每个量词命题的析取。 如果 即使域是无限的,我们仍然可以以这种方式考虑量词,但是没有量词的等价表达式将是无限长的。 0x02 量化表达式的否定设 否定原来的陈述给出 "并不是班上的所有学生都上过Java课程",这意味着 "你们班有一个学生没有上过Java课程"。 则 ¬ 设 否定原来的说法就会得到 "这个班没有一个学生上过Java课程"。这意味着 "这个班的每个学生都没有上个Java课程"。 所以 ¬ 否定量词的狄摩根定律是: 📚 由表中推理可知: ¬ ¬ 可以将 ¬ 想象成一只青蛙,而这就是个青蛙跳,每跳一级任意变存在,存在变任意。 在命题公式中成立的式子,用谓词公式去替代换其中相应的命题变元,得到的公式依然成立。比如:
¬ 量词辖域中如果有合取或析取项,且其中有一个是命题, 则可以将该命题移至量词辖域之外,如: 💭 举个例子: 名义上 旁听生如果想站到教室外面(即收缩)上课,是可以的。 反过来,旁听生也可以进教室(即扩张),上课,也是可以的。 0x06 量词分配等价式设 💭 例一:把下面句子转换出谓词逻辑表达式:"这个班上的学生都上过Java课程。" 解1:如果 解2:但是如果 注意: 💭 例二:把下面的句子改成谓词逻辑:"这个班的一些学生上过Java课程"。 解1:如果 解2:但是如果 注意: 💭 例三:翻译 "这个班有学生去过蒙大拿" 、"这个班的每个学生都去过蒙大拿和理塘"。 解: ① 令 ② 增加 📌 注: 我们常常把表示客体某种性质的谓词称为特性谓词(例如上面的🔺 总结:一元谓词表性质,多元谓词表关系。特性谓词做合取项时用特性谓词做合取项,全称量词时特性谓词做前件。 💬 我们现在可以解决本章开头引入部分提到的孙笑川的例子了。 设命题函数 这两个前提是: 结论是: 💭 我们来做一道口碑不错的练习题: ① 翻译:"Everything is a fleegle." 解: ② 翻译: "Nothing is a snurd." 解: ③ 翻译:"All fleggles are snurds." 解: ④ 翻译:"Some fleegle are thingmabobs." (既是什么又是什么,两个都是,要翻译成合取) 解: ⑤ 翻译: "No snurd is a thingamabob" 解: ¬ ⑥ 翻译: "If any fleegle is a snurd then it is also a thingamabob." 解: 嵌套量词通常是表达句子意义以及计算机科学和数学中的重要概念中所必须的。 比如:"每个实数都有一个逆",可用其表达为:
想要表达这种数学概念,只用一个变元表示就不礼貌了,像这里用两个变元去表达就会很容易。 我们也可以考虑为嵌套命题函数:
理解嵌套量词: 如果
如果
📌 注意:如果变量的域使无限的,那么这个过程实际上使不能执行的。 0x01 量词的顺序可以随便换顺序:令 不能随便换顺序:令 例一:令
例二:令 两个变量的量化: 💭 翻译下列语句: 其中 解:学校的每个学生 (都有一台电脑或有一个朋友有一台电脑) 。
解:有某个学生,他的所有朋友都不是彼此的朋友。 0x03 数学语句到嵌套量词的翻译💭 将 "两个正整数的和总是正的",转换出逻辑表达式。 解: 重写语句,使隐含的量词和域显式表达。"对于每两个整数,如果这些整数都是正的,那么这些整数的和就是正的"。引入变量结果是: 💭 用量词来表示语句 "世界上有一个女人乘过所有航线上的航班"。 解: 令
则句子可以表示为: 关于一个女人搭乘过所有航线上的航班的逻辑表达式: 部分1:用量词来表达 "世界上没有哪位女人做过世界上每条航线的航班"。 解: ¬ 部分2:现在用狄摩根定律把否定移到尽可能远的地方。 部分3:把结果翻译成汉语 "对于每位女人,存在一条航线,使得对所有的航班,这些女人要么没有搭乘过这个航班,要么该航班不在这条航线上"。 📜 参考资料 Kenneth Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill 刘然老师. 重庆大学《离散数学及其应用》[EB/OL]. 2020.https://www.bilibili.com/video/BV1Hi4y1w7YA. 百度百科[EB/OL]. []. https://baike.baidu.com/. |
CopyRight 2018-2019 实验室设备网 版权所有 |