斯坦福《逻辑学导论》第五周学习笔记

斯坦福大学的《逻辑学导论》课程几乎是每个希望干出一番事业的有理性人类梦寐以求的课程,它不是教授自亚里士多德以来的逻辑学史内容,也不是简单的教授符号使用和逻辑思维方法,而是传授思想。这门课通过研究逻辑学方法,学习组织信息和系统的推理工具,生成合逻辑的结论,以启迪我们将其应用在数学、科学、工程、商业、法律等领域。1

同学们,兄弟姐妹,叔叔阿姨,舅姑姥爷婶婶们,我被Coursera这门课懵诈了。由于前两周的经验,导致我形成了一个习惯——根本不看那Video,因为跟题一点关系没有。更何况这周的导语写着 Phew. Not an easy week. Especially for those of you seeing formal proofs for the first time. 我就直接略过了视频,轻松习题过三关,然后就卡住了,因为没看视频。

周导语
不看视频

这周的课程相当简单,只要你熟悉公式(一定得看视频或者PPT)即可。另外,本周的讲义中,“诡异”的$|-$符号又再次出现:A sentence φ is provable from a set of sentences Δ by Propositional Resolution (written Δ |- φ) if and only if there is a resolution proof of φ from Δ.(当且仅当有一个从Δ到φ的归结证明可用时,句子是可证的(写作Δ|-φ)。)上周说到,讲义中这里的内容是为了告知学习者符号的写法。但,我们知道,按照徐明的书:如果不写明证明系统符号,是没有意义的。确实诡异。

答案一对一

按照honor code的原则,我不能直接写出答案,但,这一周其实每个答案相当于都有提示,所以我把一些答案直接解释出来也不算违禁。这周的所有练习都真的是在测试学习者对Video和讲义中概念的掌握,没法不“剧透”。

Problem 5.1

第一题

这一题,完全按照视频教程里面的规则来即可。这就是引入($=>$)表达式转换为句子表达(clausal sentence)的方法。

第一题解释

首先,我们转换第一步:

p ∧ q ⇒ r ∨ s

得到 ¬(p ∧ q)∨(r ∨ s)

然后进一步拆分,按照规则: ¬(φ ∧ ψ) → ¬φ ∨ ¬ψ。

得到 (¬p ∨ ¬q)∨(r ∨ s)

按照规则:

  1. φ1 ∨ ... ∨ φ → {φ1, ... , φn};φ1 ∧ ... ∧ φn → {φ1}, ... , {φn}
  2. φ ∨ (ψ ∧ χ) → (φ ∨ ψ) ∧ (φ ∨ χ);(φ ∧ ψ) ∨ χ → (φ ∨ χ) ∧ (ψ ∨ χ);φ ∨ (φ1 ∨ ... ∨ φn) → φ ∨ φ1 ∨ ... ∨ φn;(φ1 ∨ ... ∨ φn) ∨ φ → φ1 ∨ ... ∨ φn ∨ φ;φ ∧ (φ1 ∧ ... ∧ φn) → φ ∧ φ1 ∧ ... ∧ φn;(φ1 ∧ ... ∧ φn) ∧ φ → φ1 ∧ ... ∧ φn ∧ φ

再一次拆开

  • (¬p ∨ ¬q)∨r∨ s
  • {¬p,¬q,r,s}(答案)

Problem 5.2

第二题

这题还是考验学习者是否掌握如下规则:

第二题解释

因为多于一个命题互补的情况,该命题不能被消去,所以有三个结果,步骤如下:

{¬p, q, r} and {p, ¬q, ¬r}

  • 第一次消去p得到:{q, ¬q, r, ¬r}
  • 第二次消去q得到:{¬p, p, r, ¬r}
  • 第三次消去r得到:{¬p, p, q, ¬q}

Problem 5.3

学习者要注意本周教授这种证明方法的目的就在于简便。

Propositional Resolution is a powerful rule of inference for Propositional Logic. Using Propositional Resolution (without axiom schemata or other rules of inference), it is possible to build a theorem prover that is sound and complete for all of Propositional Logic. What's more, the search space using Propositional Resolution is much smaller than for standard propositional logic.

第三题解释

它的证明方法就是:如果没有前提,那么当所有命题最后得到运算矛盾时(计算得到{}),意味着,命题不能同时被满足(同时为真或为假);如果所有前提(将结论的否命题同样作为前提写入)成立,当结论不存在(为{}时),那么结论命题(原来被写为否命题放在前提里了)一定成立。

这一题就使用“没有前提”的证明方法即可。

Problem 5.4

这一题还是使用上面的方法,使用“有前提”的证明方法。

把所有题给前提和结论的否命题写入“前提”(Premise),如图:

第四题

提示,直接“前提”写入 ~ (p | r => q | s) ,系统可自动拆分成3个前提命题。

另外,有个很有趣的现象:直接将{}写入前提,也可以得到本题完成(Complete)的标志,如图:

第四题解释

吐槽

本周的课程时间结束前,按照惯例,下一周的课程进行了更新,但本周教授可能忘记了更新Video。

WTF

吐槽


  1. MOOC果壳中文站:http://mooc.guokr.com/course/359/Introduction-to-Logic/  

2015-10-28 23:10 intrologic
Comments
Write a Comment