1.1 Overview:

本课程所思考的内容有：有哪些问题是可以被routine mechanical calculation方式而解决的，换句话说，即采用可遵循的算法和effective procedure。而这又实际上等于说存在一种解决此问题的编程方式。

 

莱布尼茨曾发明过一种能做四则运算的计算器，他曾说“让一群杰出的人像奴隶一样付出劳力，去浪费时间做机器就能解决的运算，是毫无意义的”。

 

为此，莱布尼茨还有过更加宏大的想法：建立这样一种机制，它由字符（Alphabet）)和一套规则（Mechanical routine）而组成。这些字符代表现实中的意义而不是音义【注：is Concepts not sounds, 也就决定了它们能组成具有真值的语句】，而规则即是所能够遵行而去判定某种语言语句的真值和继承关系的机械方法。【注：Alphabet, Language, Sentence的定义，此处可以稍提一下】。这样一来，人们就可安坐下来，写出要解决问题的语句表达式【注：编辑输入】，然后放心地套用即有规则于输入上，坐等结果的诞生。

 

可惜莱布尼茨并没有在这项目上大展宏图，但以此为基，后人发展了很多东西。在逻辑学导论的课程中【注：悉大的PHIL1012，逻辑学课程的pre-request】，我们已学了诸如命题逻辑和一般谓词逻辑等等的精确的逻辑语言。它们的共同特征即都是精确和机械性的，因此我们都能为此编写程序来精确模拟/描述此类语言的规则。

 

但是莱布尼茨所构思的解决问题的‘规则’到底有多神通广大？这是一个可行可证的方法还是华而不实的幻想？在本课程中，我们就将尝试检验机械程式的实用范围（scope and limits of such rules），尤其是关注于以下逻辑问题：

1、给定一个命题逻辑的表达式以及它在真值表中的某一行（等价于是给这段表达式的一种赋值方式），判定该表达式在这一行是否为真。

2、给定一个命题逻辑的表达式，判定其是否是可满足的（等价于问它的真值表是否存在结果为真的一行）。

3、给定一个谓词逻辑的表达式，判定其是否是可满足的（等价于问它是否在某模型上是真的）。

4、给定一个算数表达式，判定其真值。

 

本课的计划如下：（每一小点是四个课时）

PartI – Foundations:

1. introduction; notions from set theory

2. enumerability and non-enumerability

3. eectiveprocedures and computable functions; logical languages and proofs

PartII – uncomputability and undecidability:

1. models of computation, including automata andTuring machines

2. Turing-uncomputable functions

3. the undecidability of first-order logic (cf.problem 3 above)

PartIII – computational complexity:

1. the class P

2. the class NP

3. model-checking vs satisfiability forpropositional logic (cf. problems 1 and 2 above); NP-completeness

PartIV – incompleteness:

1. formal arithmetic

2. representability of computable functions

3. Godel’s first incompleteness theorem and relatedresults such as Tarski’s theorem on the indefinability of truth (cf. problem 4above).

 

1.2 集合论

参考《Logic:The Laws of Truth》一书的Pg438~460（就是授课教授NickSmith自己的著作。。）

【注：在NOTES上教授没给出详细讲解，回头翻了下上课的笔记，大概介绍的是一些非常基础的集合概念：

       Set,Subset

Proper set （即S属于T，但T不属于S的归属关系)

Extensionality （判定等价关系）

Null Set   （属于任意集合的集，证明：这个表达式是恒真的forAll x (x is in NULL => x is in S)，因为xis in NULL是恒假，Null set不含任何元素）

Power Set （该集展示了某集合的元素的所有排列可能，包含NullSet）

Function  （F: S→T是一个function当且仅当每一个x∈S只对应最多一个的y∈T，F不是totalfunction如果存在x∈S suchthat f(x) is not given）

Composite Function （(g·f)(x)= g(f(x)) ）】

 

1.3 自然数和整数

以下是我们将来主要探讨的数集

N = {0 , 1, 2, 3, …..} 自然数集

Z = {…., -3, -2, -1 ,0, 1, 2, 3, …}  整数集

Z⁺ = {1, 2, 3, …} 正整数集