选课类别:计划内与自由选修 | 教学类型:理论课 |
课程类别:本科计划内课程 | 开课单位:计算机科学与技术系 |
课程层次:专业基础 | 学分:2.0 |
数理逻辑是计算机科学技术的重要数学基础之一,本课程是计算机科学技术专业本科教学的数理逻辑基础课程,主要介绍数理逻辑的基本理论和形式化技术,为后继课程奠定必要基础。主要内容包括:命题逻辑的(标准)形式公理系统(命题语言和形式推导)、语义学和元理论(命题演算的可靠性和完全性);一阶逻辑的(标准)形式公理系统(一阶语言和形式推导)、语义学和元理论(一阶谓词演算的可靠性和完全性)。
侯嘉慧老师的《数理逻辑基础》课程考试难度有所挑战,某些题目较往年更加复杂,尤其是在应用题和判断题上可能会出现一些“坑点”。尽管如此,只要在平时对概念认真学习理解,考试仍然是可以应对的,比如从考试题目中可看出,题型包括判断题、推理题、命题证明、谓词演算等,设计上综合了理解与应用能力。
目前没有关于给分的详细信息,不过从学生的反馈看,自学能获得较高成绩,如有学生通过自主研读教材拿到了4分。教材习题后面附有答案,这对学生自学和完成作业有帮助。
从评论来看,虽然部分学生选择自学,但课程内容本身是完整和系统的,老师讲解细致。课程探讨了命题逻辑与一阶逻辑的基本部分,结合了语法与语义的学习,整体上强调深度和严谨性。
课程构架了命题逻辑和一阶逻辑的基础,探讨了Leibniz、Gödel等经典内容。尽管课时从三学分减少到两学分,删去了如Gödel不完备定理等内容,但仍系统地介绍了逻辑的完备性与可靠性理论,演绎和推理规则,及逻辑语法辩证关系等。命题逻辑讨论了语法游戏、重言式、内定理与外定理等,一阶逻辑探讨了变量、自由与约束、解释域等。这些内容充分展示了逻辑学的优雅与深邃,尽管学习过程繁琐,却为学生理解和应用逻辑提供了扎实基础。
尽管部分学生选择自学,但课程的内容与深度吸引了包括大三学生的参与,一定程度上表明课程的吸引力和专业性。然而,也有人表示跟不上课程进度,需要依靠课外学习补充。因此,课程自学难度与参与课堂是相辅相成的,适合对逻辑有强烈兴趣和一定基础的学生选修。
课程被评价为是一门深邃的学问,相关内容的学习会让学生深入思考逻辑的本质。总体上给那些对数理逻辑有兴趣并愿意付出时间的学生提供了极佳的学习机会。
不知道自己多少分,故也就无法评价给分好坏。
稍微评价一下今年期末考的卷子,比往年的会恶心一些,体现在两道应用题,和判断题的一些坑点。但反正理解了,而且概念之类的认真翻翻看看,这张考卷也没什么难的。
回忆一下考卷(如果还有记得更多的可以在评论区说一下):
第一题:判断题(每题 3 分)(不保证顺序)。
(1) 对于一个公式
(2) 一个公式
(3) 用一个项
(4) 忘了。
(5) 忘了。
(6) 给定解释域
(7) 忘了。
第二题:忘记了,一个繁琐的推理题。
第三题:给出如下命题的直接与间接证明(18 分):
第四题:在谓词演算
(1)
(2)
第五题:将如下公式化为前束合取范式:
第六题:证明如下命题:
一位客人要么坐一等座,要么做二等座,而一位客人坐一等座当且仅当其富裕。并且存在客人不富裕,那么有人坐二等座。
优雅至极的一门学问,之后有空再来细讲。(仗着科大估计没人做正统的数理逻辑,发表自己拙劣的见解)
先写点课程内容,也算是给自己复习。我没去上课,自学主要看的书是复旦大学的教材:郝兆宽、杨睿之、杨跃《数理逻辑:证明及其限度》,下面的语言有的地方可能会和书上不一样。
数理逻辑最初的想法来自 Leibniz 构想的通用文字纲领。我们这门课主要学习了其中最基本的部分:命题逻辑 与 一阶逻辑。可惜的是,在 20 年培养方案改之后,数理逻辑从三学分变成两学分(估计是被量子物理给夺去了学分),删掉了数理逻辑的绝对高峰:Gödel 不完备定理。
命题逻辑以一个一个命题为基本单元,分为语义和语法两个部分。
语法这边,上来先给出了三条公理,然后马上就来了整个数理逻辑基础课里面让大家最头疼的 “直接证明”。“直接证明” 这件事本质上是在做语法游戏,它规定命题演算体系
说到 “直接证明” 为什么不能使用演绎定理,即使是在题目一开始直接当作引理证明完也不能用。本质上还是这个东西是不合规的,你这个玩意不符合那套语法规则。这里可以说一下 “内定理” 和 “外定理” 的区别:“内定理” 又叫 "元定理”,大概就是这套语法规则里可以玩出来的东西,比如 (否定前件律)
从本质上来说我们不能在直接证明里使用 “外定理”,是因为命题演算系统
所以其实我大部分时候,做直接证明题,最感到烦躁的不是不能用演绎定理,而是大致的逻辑链条已经清楚了,但每次用到 “内定理” 却要把其直接证明抄上去。
说了这么多,其实我们已经大致上把命题逻辑的语法部分讲完了,接下来再来看语义部分。这部分显得就特别直白了,可以直接列真值表了!熟悉的与或非也回来了!这部分整个下来是顺风顺水的,后面的合取析取范式,对偶公式等甚至数电就已经学过。
再来是命题逻辑
证明可靠性相对容易,只需要发现 (L1)、(L2)、(L3) 都是重言式,并且对 (MP) 也封闭即可。
而证明完全性,我们要先进行一个转化:
引理:下列命题等价:(1) 如果
依此我们可以将完全性定理的证明转化为去证明每一个一致集都是可满足的。而后者的证明又有:
Lindenbaum 引理:每一个一致的公式集
做法就是把可数多个公式一个一个尝试往里加。有了极大一致集,我们容易从中读出一种赋值:
书上还提到了别的一些杂项,如唯一读法引理,和其他的命题演算系统(极小系统和 Heyting 系统),由此引出直觉逻辑:否定排中律可以无限制地运用。Gödel 的另一个著名理论是:直接逻辑的真值种类必须有无穷多个。由此可见直觉逻辑与经典逻辑的不同。
接下来到了一阶逻辑(谓词逻辑),它是命题逻辑的扩充。命题逻辑以整个命题为基本单位,这无法接触到个体对象,使得量词无法介入。一阶逻辑定义项集,以原子公式为基本单位。
在语法部分,一阶逻辑比命题逻辑多了几条公理。我看的书里是没有 (Gen) 规则,科大的书里是有的。我暂且觉得没有 (Gen) 规则更好:一个是更加清楚,有 (Gen) 之后演绎定理和反正律都要额外加条件;另一个原因之后在语义部分会提及。这部分倒是没有 “直接证明” 题了,估计是太过复杂了。
语法这部分还要注意理解自由出现和约束出现,以及各种东西能不能替换,这个是一阶逻辑引入量词后必须注意的一部分(哑元的艺术)。
到了语义部分,和命题逻辑不一样,一阶逻辑的语义不再是 trivial 的真假赋值。为了细化一阶逻辑中个体对象的部分,我们必须引入解释域
有了这个那
当然每个人感受不一样,可能有的觉得科大书上的定义很自然。
接下来又到了可靠性与完备性的环节,同命题逻辑一样,一阶逻辑的语义和语法也是一致的。对于可靠性定理还是去证明各个公理和 (MP) 都可以,只不过花的工作更多一点。
而对于完备性,我们先把一阶逻辑
可以这么理解 Henkin 公理:对每一个存在性的语句都添加一个直接证据
我们记 Henkin 公理集为
(1) 论域
这样可以验证我们就找到了一个解释域和赋值,如果一阶逻辑中还包含等词,我们需要考虑由等词划分得到的商集。然后还是根据命题逻辑中的转化,我们由此得出完备性定理。
与命题逻辑很不一致的地方是,
PS:数院的陈卿老师说过:
不要碰数理逻辑和集合论这种形式化的东西,水太深。
由此可见数理逻辑的深邃。
中国科大 woc
害惨了我
我这学期几乎一节课没去(除了某次去交作业的时候听了半小时),全靠看书+写作业自学,最后拿了4。
温馨提示:课本后面是有习题答案的
点开课程群绷不住了,怎么这么多大三数院✌求佬们手下留情😇😭😭😭