数理逻辑基础(侯嘉慧) 2025春 2024春  课程号:CS200201
2025春 2024春  课程号:CS200201
7.5(8人评价)
  • 课程难度:中等
  • 作业多少:中等
  • 给分好坏:一般
  • 收获大小:一般
选课类别:计划内与自由选修 教学类型:理论课
课程类别:本科计划内课程 开课单位:计算机科学与技术系
课程层次:专业基础   学分:2.0
课程主页:暂无(如果你知道,劳烦告诉我们!)
简介 最后更新:2024年2月7日 09:59

数理逻辑是计算机科学技术的重要数学基础之一,本课程是计算机科学技术专业本科教学的数理逻辑基础课程,主要介绍数理逻辑的基本理论和形式化技术,为后继课程奠定必要基础。主要内容包括:命题逻辑的(标准)形式公理系统(命题语言和形式推导)、语义学和元理论(命题演算的可靠性和完全性);一阶逻辑的(标准)形式公理系统(一阶语言和形式推导)、语义学和元理论(一阶谓词演算的可靠性和完全性)。

AI 总结 AI 总结为根据点评内容自动生成,仅供参考

考试与难度

侯嘉慧老师的《数理逻辑基础》课程考试难度有所挑战,某些题目较往年更加复杂,尤其是在应用题和判断题上可能会出现一些“坑点”。尽管如此,只要在平时对概念认真学习理解,考试仍然是可以应对的,比如从考试题目中可看出,题型包括判断题、推理题、命题证明、谓词演算等,设计上综合了理解与应用能力。

给分与作业

目前没有关于给分的详细信息,不过从学生的反馈看,自学能获得较高成绩,如有学生通过自主研读教材拿到了4分。教材习题后面附有答案,这对学生自学和完成作业有帮助。

教学水平

从评论来看,虽然部分学生选择自学,但课程内容本身是完整和系统的,老师讲解细致。课程探讨了命题逻辑与一阶逻辑的基本部分,结合了语法与语义的学习,整体上强调深度和严谨性。

课程内容

课程构架了命题逻辑和一阶逻辑的基础,探讨了Leibniz、Gödel等经典内容。尽管课时从三学分减少到两学分,删去了如Gödel不完备定理等内容,但仍系统地介绍了逻辑的完备性与可靠性理论,演绎和推理规则,及逻辑语法辩证关系等。命题逻辑讨论了语法游戏、重言式、内定理与外定理等,一阶逻辑探讨了变量、自由与约束、解释域等。这些内容充分展示了逻辑学的优雅与深邃,尽管学习过程繁琐,却为学生理解和应用逻辑提供了扎实基础。

课堂氛围

尽管部分学生选择自学,但课程的内容与深度吸引了包括大三学生的参与,一定程度上表明课程的吸引力和专业性。然而,也有人表示跟不上课程进度,需要依靠课外学习补充。因此,课程自学难度与参与课堂是相辅相成的,适合对逻辑有强烈兴趣和一定基础的学生选修。

课程被评价为是一门深邃的学问,相关内容的学习会让学生深入思考逻辑的本质。总体上给那些对数理逻辑有兴趣并愿意付出时间的学生提供了极佳的学习机会。

排序 学期

评分 评分 8条点评

Peanut_Tang 2024春
  • 课程难度:中等
  • 作业多少:很少
  • 给分好坏:一般
  • 收获大小:很多
  • 难度:中等
  • 作业:很少
  • 给分:一般
  • 收获:很多

不知道自己多少分,故也就无法评价给分好坏。

稍微评价一下今年期末考的卷子,比往年的会恶心一些,体现在两道应用题,和判断题的一些坑点。但反正理解了,而且概念之类的认真翻翻看看,这张考卷也没什么难的。


回忆一下考卷(如果还有记得更多的可以在评论区说一下):

第一题:判断题(每题 3 分)(不保证顺序)。

(1) 对于一个公式 p,若有 p,则对于任意公式集 Γ,都有 Γp

(2) 一个公式 p 是公式集 Γ 的语法推论,则每个让 p 为真的赋值都会让 Γ 里的所有公式为真。

(3) 用一个项 t 去替换原子公式 p 里的自由出现的变元 x,得到的新公式里会有约束出现的变元。

(4) 忘了。

(5) 忘了。

(6) 给定解释域 M 后,对于一个给定的常元 c,存在两个不同项解释 φ,ψΦM,使得 φ(c)ψ(c)

(7) 忘了。

第二题:忘记了,一个繁琐的推理题。

第三题:给出如下命题的直接与间接证明(18 分):

(pq)((p(qr))(pr))

第四题:在谓词演算 K 中证明如下两个命题:

(1) (pxq)x(pq)

(2) x(pq)x¬qx¬p

第五题:将如下公式化为前束合取范式:

¬(x1R12(a,x1)x1(x2R13(x1,x2,b)x2x3R22(x2,x3)))

第六题:证明如下命题:

一位客人要么坐一等座,要么做二等座,而一位客人坐一等座当且仅当其富裕。并且存在客人不富裕,那么有人坐二等座。


优雅至极的一门学问,之后有空再来细讲。(仗着科大估计没人做正统的数理逻辑,发表自己拙劣的见解)


先写点课程内容,也算是给自己复习。我没去上课,自学主要看的书是复旦大学的教材:郝兆宽、杨睿之、杨跃《数理逻辑:证明及其限度》,下面的语言有的地方可能会和书上不一样。

数理逻辑最初的想法来自 Leibniz 构想的通用文字纲领。我们这门课主要学习了其中最基本的部分:命题逻辑 与 一阶逻辑。可惜的是,在 20 年培养方案改之后,数理逻辑从三学分变成两学分(估计是被量子物理给夺去了学分),删掉了数理逻辑的绝对高峰:Gödel 不完备定理。

命题逻辑以一个一个命题为基本单元,分为语义和语法两个部分。

语法这边,上来先给出了三条公理,然后马上就来了整个数理逻辑基础课里面让大家最头疼的 “直接证明”。“直接证明” 这件事本质上是在做语法游戏,它规定命题演算体系 L 下的一个内定理 φ 是而且只能是一个可以通过一列有限个字符串,里面的要么是 (L1)、(L2)、(L3) 三条公理,要么是可以使用分离规则 (MP),得出的。但是“直接证明”实在是过于繁琐,所以又有了演绎定理、反证律和归谬律来帮助大家简化证明。

说到 “直接证明” 为什么不能使用演绎定理,即使是在题目一开始直接当作引理证明完也不能用。本质上还是这个东西是不合规的,你这个玩意不符合那套语法规则。这里可以说一下 “内定理” 和 “外定理” 的区别:“内定理” 又叫 "元定理”,大概就是这套语法规则里可以玩出来的东西,比如 (否定前件律) ¬q(qp),以及大家在习题里看到的各种各样的神秘字符串;而 "外定理“ 大概就是人类通常理解的定理,比如在书上反复用到的归纳原理就算一种 “外定理”,当然演绎定理这些也是 “外定理”。

从本质上来说我们不能在直接证明里使用 “外定理”,是因为命题演算系统 L 它的语言没办法说明这样一个 “外定理”。比如说,L 连自然数都无法描述,怎么使用归纳法。“外定理” 实际上是我们在用自己熟知的语言和逻辑,去研究一个 “对象语言 / 逻辑”——命题演算系统 L。就比如说如果你用了演绎定理,你要怎么根据这个使用了演绎定理的间接证明来写出直接证明呢?至少我觉得反演回去的工作是 non-trivial 的,比你突然想要用 (否定前件律) 了,然后把 (否定前件律) (这个是 “内定理”)的证明抄一遍用上去要困难得多。更别说还要以演绎定理为基础的反证律等。

所以其实我大部分时候,做直接证明题,最感到烦躁的不是不能用演绎定理,而是大致的逻辑链条已经清楚了,但每次用到 “内定理” 却要把其直接证明抄上去。

说了这么多,其实我们已经大致上把命题逻辑的语法部分讲完了,接下来再来看语义部分。这部分显得就特别直白了,可以直接列真值表了!熟悉的与或非也回来了!这部分整个下来是顺风顺水的,后面的合取析取范式,对偶公式等甚至数电就已经学过。

再来是命题逻辑 L 的完备性和可靠性,这是一个小的高潮,它告诉我们:语义与语法是统一的。完备性指的是:每个在人看来很对的命题,也就是重言式,都可以在 L 中用那套语法规则玩出来。这个是对 L 表达能力的刻画,它可以推出我们想要的东西。而可靠性则更进一步要求了 L 别推出我们不想要的东西:每个 L 的 “内定理”(可以用语法玩出来的东西),都要是重言式。

证明可靠性相对容易,只需要发现 (L1)、(L2)、(L3) 都是重言式,并且对 (MP) 也封闭即可。

而证明完全性,我们要先进行一个转化:

引理:下列命题等价:(1) 如果 Σ 一致,则 Σ 可满足;(2) 如果 Σα,则 Σα

依此我们可以将完全性定理的证明转化为去证明每一个一致集都是可满足的。而后者的证明又有:

 Lindenbaum 引理:每一个一致的公式集 Σ 都可以扩张成一个极大一致集 Δ

做法就是把可数多个公式一个一个尝试往里加。有了极大一致集,我们容易从中读出一种赋值:v¯(φ)=1φΔ,这样我们就证明了完全性定理。这两个定理给出一个附属结果:命题逻辑 L 是可判定的,你想要判定是否有 Σα,只需要列真值表就可以了,虽然这样很慢。

书上还提到了别的一些杂项,如唯一读法引理,和其他的命题演算系统(极小系统和 Heyting 系统),由此引出直觉逻辑:否定排中律可以无限制地运用。Gödel 的另一个著名理论是:直接逻辑的真值种类必须有无穷多个。由此可见直觉逻辑与经典逻辑的不同。

接下来到了一阶逻辑(谓词逻辑),它是命题逻辑的扩充。命题逻辑以整个命题为基本单位,这无法接触到个体对象,使得量词无法介入。一阶逻辑定义项集,以原子公式为基本单位。

在语法部分,一阶逻辑比命题逻辑多了几条公理。我看的书里是没有 (Gen) 规则,科大的书里是有的。我暂且觉得没有 (Gen) 规则更好:一个是更加清楚,有 (Gen) 之后演绎定理和反正律都要额外加条件;另一个原因之后在语义部分会提及。这部分倒是没有 “直接证明” 题了,估计是太过复杂了。

语法这部分还要注意理解自由出现和约束出现,以及各种东西能不能替换,这个是一阶逻辑引入量词后必须注意的一部分(哑元的艺术)。

到了语义部分,和命题逻辑不一样,一阶逻辑的语义不再是 trivial 的真假赋值。为了细化一阶逻辑中个体对象的部分,我们必须引入解释域 U,让常元对应集合上的一个元素,函数对应集合上的函数,谓词对应集合上的关系。而有解释域还不够,因为变元的值还没有被确定,所以还要再来项解释 s,并扩充成整个公式集的解释 s¯

有了这个那 Σα 怎么定义呢?我看的书和科大的书定义是不同的:

当然每个人感受不一样,可能有的觉得科大书上的定义很自然。

接下来又到了可靠性与完备性的环节,同命题逻辑一样,一阶逻辑的语义和语法也是一致的。对于可靠性定理还是去证明各个公理和 (MP) 都可以,只不过花的工作更多一点。

而对于完备性,我们先把一阶逻辑 K 进行扩充,添加可数个新常元,变成 Kc。并且添加 Henkin 公理:xφφcx,其中 c 是新的常元,而 φcx 表示把 φ 中所有自由出现的 x 替换成 c 得到的公式。

可以这么理解 Henkin 公理:对每一个存在性的语句都添加一个直接证据 c,所以扩充 K 和添加 Henkin 公理的目的都是 “消去量词”,使得从中可以比较容易的读出一个可能的解释域和项解释。

我们记 Henkin 公理集为 Θ,可以证明 ΣΘ 还是一致的,这时候我们在和命题逻辑一样,运用 Lindenbaum 引理,将 ΣΘ 扩充成极大一致集 Δ,从这一公式集中容易读出一种解释域和项解释:

(1) 论域 U 为 Kc 上所有项的集合;(2) 一个谓词 P,其对应 P¯ 为:(t1,t2,,tn)P¯P(t1,t2,,tn)Δ;(3) 函数对应和谓词类似;(4) 常元 c 直接对应于自身。

这样可以验证我们就找到了一个解释域和赋值,如果一阶逻辑中还包含等词,我们需要考虑由等词划分得到的商集。然后还是根据命题逻辑中的转化,我们由此得出完备性定理。

与命题逻辑很不一致的地方是,Σα 这件事在一阶逻辑中变得不好弄了。命题逻辑只需要列真值表,但是一阶逻辑中解释域和项解释都是无穷多的,也就是解释个数的区别。实际上,一阶逻辑是不可判定的。


PS:数院的陈卿老师说过:

不要碰数理逻辑和集合论这种形式化的东西,水太深。

由此可见数理逻辑的深邃。

2024年5月26日 08:17 (最后修改于 2024年7月11日 02:31 8 2 复制链接
Eastwind_ 2024年5月26日 10:48
TheBunniestForever 2024年5月26日 12:36
立即登录,说说你的看法
  • 课程难度:简单
  • 作业多少:很少
  • 给分好坏:超好
  • 收获大小:很多
  • 难度:简单
  • 作业:很少
  • 给分:超好
  • 收获:很多

????????????

2024年7月3日 06:54 (最后修改于 2024年7月3日 09:38 4 16 复制链接
Memmataria柯南别太离谱 2024年7月3日 07:11
地空首陀罗唉,性压抑 2024年7月3日 07:22
加菲学不会数学󠁅逆天 2024年7月3日 07:31
Breaking_Dawn逆天 2024年7月3日 07:32
呃呃呃逆天 2024年7月3日 07:34
zkdjwc逆天 2024年7月3日 07:34
plump&chubby呃,别太逆天 2024年7月3日 07:54
你是真饿了 2024年7月3日 07:59
Yiran逆天 2024年7月3日 08:19
Kyle逆天 2024年7月3日 08:39
萌萌哒mmddinner 2024年7月3日 08:40
苏和杨合影! 2024年7月3日 08:49
阿笠博士😅 2024年7月3日 09:16
煞笔咋了? 2024年7月3日 09:50
嗨嗨嘿快把老师真漂亮换回来! 2024年7月3日 10:06
青橙之前评课已截图😋 2024年7月3日 10:43
立即登录,说说你的看法
匿名用户 2024春
  • 课程难度:中等
  • 作业多少:中等
  • 给分好坏:一般
  • 收获大小:一般
  • 难度:中等
  • 作业:中等
  • 给分:一般
  • 收获:一般

中国科大 woc

害惨了我

2024年6月12日 10:14 3 0 复制链接
lsy 2024春
  • 课程难度:中等
  • 作业多少:中等
  • 给分好坏:超好
  • 收获大小:一般
  • 难度:中等
  • 作业:中等
  • 给分:超好
  • 收获:一般

我这学期几乎一节课没去(除了某次去交作业的时候听了半小时),全靠看书+写作业自学,最后拿了4。

2024年8月1日 09:58 2 3 复制链接
TheBunniestForever 2024年8月1日 11:11
先天智力不足强👍 2024年8月2日 12:42
φφ这个课有点名吗 2025年3月3日 15:44
立即登录,说说你的看法
匿名用户 2024春
  • 课程难度:中等
  • 作业多少:中等
  • 给分好坏:一般
  • 收获大小:一般
  • 难度:中等
  • 作业:中等
  • 给分:一般
  • 收获:一般

温馨提示:课本后面是有习题答案的

2024年3月21日 14:18 2 1 复制链接
逸文好人一生平安 2024年3月23日 08:23
立即登录,说说你的看法
匿名用户 2025春
  • 课程难度:中等
  • 作业多少:很少
  • 给分好坏:一般
  • 收获大小:一般
  • 难度:中等
  • 作业:很少
  • 给分:一般
  • 收获:一般

点开课程群绷不住了,怎么这么多大三数院✌求佬们手下留情😇😭😭😭

2025年3月6日 01:44 (最后修改于 2025年3月6日 01:48 0 1 复制链接
IceOfLunar听说有数院老师在某会上跟数院人推荐了这门课()不过我是当年大一的时候选的 2025年3月6日 02:12
立即登录,说说你的看法

侯嘉慧

教师主页: 戳这里

其他老师的「数理逻辑基础」课

许杨 9.9 (8) 2025春 2023春
许杨, 刘建春 9.8 (6) 2024春
刘贵全 7.3 (27) 2023春 2022春
周熠 2025春

侯嘉慧老师的其他课

计算机应用数学 5.4 (19) 2025春 2024春...
“科学与社会”研讨课 2025春 2024秋...