逻辑学导论

学习课程

Introduction to Logic - Stanford University - 课程信息 | Coursera

学习目标

• 熟悉逻辑学的基本术语、重要概念
• 逻辑训练： 自然语言和论点如何被形式化及分析

1. Introduction

key elements of Logic : logical sentences, logical entailment, and logical proofs

1.1 Interpersonal relationship 的例子

给定四个女孩，有 16 种可能的 likes relationship 实例 - Abby 喜欢 Abby，Abby 喜欢 Bess，Abby 喜欢 Cody，Abby 喜欢 Dana，Bess 喜欢 Abby，等等。这十六个中的每一个都可以是真或假。这些真假可能性有 2^16 (65,536) 种可能的组合，因此有 2^16 个可能的世界。

1.2 logical sentences

Dana likes Cody.
Abby does not like Dana.
Dana does not like Abby.
Bess likes Cody or Dana.
Abby likes everyone that Bess likes.
Cody likes everyone who likes her.
Nobody likes herself

这类的句子限制了世界的可能方式。每个句子将上述2^16种可能世界分为两个子集，其中句子为真和句子为假。

给定两个句子，我们知道世界必须在第一个句子为True的世界集合和第二个句子为True的世界集合的交集中。理想情况下，当我们有足够的句子时，我们就可以确切地知道事情的发展。

1.3 logical entailment

即使一组句子不能确定一个唯一的世界，但通常情况下，某些句子在满足给定句子的每个世界中都是正确的。这类句子被称为从给定句子中得出的逻辑结论 logical conclusion

检查一组句子在逻辑上是否包含结论的一种方法：检查给定句子为真的所有世界的集合。

1.4 logical proofs

然而，通过穷举并检查所有可能性来确定logical entailment通常是不切实际的。此外，在某些情况下，可能世界的数量是无限的。因此穷举法并不都是可行的。

另一种选择是逻辑推理 logical proofs，即。推理规则的应用得出逻辑结论和产生逻辑证明。(the application of reasoning rules to derive logical conclusions and produce logical proofs , ie sequences of reasoning steps that leads from premises to conclusions)

推理模式 reasoning patterns

for well-behaved logics, logical entailment and provability are identical - a set of premises logically entails a conclusion if and only if the conclusion is provable from the premises.

举例子：

All Accords are Hondas.
All Hondas are Japanese.
Therefore, all Accords are Japanese.

其推理模式则是

所有 x 都是 y。
所有 y 都是 z。
因此，所有 x 都是 z。

这种推理模式是逻辑的基础，但也有很重要的问题——哪些模式是正确的？

完全错误的推理模式如下

所有 x 都是 y。
一些 y 是 z。
因此，一些 x 是 z。

但是这种推理模式可能会得出正确的结论、也可能会得出错误的结论

因此，正确模式与不正确模式的区别在于，它必须始终得出正确的结论——即只要它们所基于的前提是正确的，它们就必须是正确的。这也是演绎(deduction)的定义标准。

推理模式的种类

• 演绎 Deduction 如上所述

有一些不符合这种严格的正确模式的定义，但是很好用：

• 归纳 Induction

• I have seen 1000 black ravens.
  I have never seen a raven that is not black.
  Therefore, every raven is black.
  Now try red Hondas.

• 溯因 Abduction

• If there is no fuel, the car will not start.
  If there is no spark, the car will not start.
  There is spark.
  The car will not start.
  Therefore, there is no fuel.
  What if the car is in a vacuum chamber?

• 类比 analogy

• The flow in a pipe is proportional to its diameter.
  Wires are like pipes.
  Therefore, the current in a wire is proportional to diameter.
  Now try price.

1.5 形式化 Formalization

自然语言存在局限性：复杂、暧昧、模糊、对语言的错误理解会导致推理上的错误
例如： There’s a girl in the room with a telescope. 我是说有一个女孩在一个装有望远镜的房间里吗？还是我说房间里有一个女孩，她拿着望远镜？

用自然语言句子推理时会出现错误的说明。
例子：利用关系的传递性规则

• 正确的情况
  • Champagne is better than beer.
    Beer is better than soda.
    Therefore, champagne is better than soda.
• 错误的情况
  • Bad dessert is better than nothing.
    Nothing is better than good dessert.
    Therefore, bad dessert is better than good dessert.

Formalization in reasoning

Logic eliminates these difficulties through the use of a formal language for encoding information. 例如代数应用问题。

考虑以下逻辑问题

If Mary loves Pat, then Mary loves Quincy. If it is Monday and raining, then Mary loves Pat or Quincy. If it is Monday and raining, does Mary love Quincy?

第一步：形式化

第二步：

第三步：

得出结论

即：如果是星期一下雨，那么玛丽爱昆西

1.6 自动化 Automation

主要是逻辑的应用

1.7 之后的课程内容

分为三个部分 命题逻辑、关系逻辑、功能逻辑

1. Propositional Logic is the logic of propositions. Symbols in the language represent “conditions” in the world, and complex sentences in the language express interrelationships among these conditions. The primary operators are Boolean connectives, such as and, or, and not.
2. Relational Logic expands upon Propositional Logic by providing a means for explicitly talking about individual objects and their interrelationships (not just monolithic conditions). In order to do so, we expand our language to include object constants and relation constants, variables and quantifiers.
3. Functional Logic takes us one step further by providing a means for describing worlds with infinitely many objects. The resulting logic is much more powerful than Propositional Logic and Relational Logic. Unfortunately, as we shall see, some of the nice computational properties of the first two logics are lost as a result.

2. 命题逻辑 Propositional Logic

2.1 Introduction

粗略地说，命题是世界的一种可能情况，既可以为真、也可以为假。 A proposition is a possible condition of the world that is either true or false, eg the possibility that it is raining, the possibility that it is cloudy, and so forth.

本章内容：命题逻辑语言的句法规则 the syntactic rules 、truth assignment、a mechanical method for evaluating sentences for a given truth assignment、a mechanical method for finding truth assignments that satisfy sentences

2.2 Syntax 语法

命题逻辑，包含两种类型的句子：

• 简单句 simple sentences：表示关于世界的简单事实
• 复合句 compound sentences：表示组成复合句的简单句之间的逻辑关系

简单句子经常被称为 命题常数proposition constants，有时被称为逻辑常数 logical constants 命题常数 写成由字母、数字、下划线组成的字符串：raining_or_snowing raining(类似变量取名)

复杂句子有简单句子组成，表达简单句子之间的逻辑关系。有五种类型 否定 negations, 合取 conjunctions, 析取 disjunctions, 蕴含 implications, and 双重条件 biconditionals.

• negations = negation operator ¬ + an arbitrary sentence，称为 target

• conjunction = sentences separated by occurrences of the ∧ operator and enclosed in parentheses，组成的句子称为conjuncts

• disjunction = sentences separated by occurrences of the ∨ operator and enclosed in parentheses，组成的句子称为disjuncts

• implication = sentences separated by the ⇒ operator and enclosed in parentheses，符号左边称为前件 antecedent，右边称为后件 consequent

• biconditional = a implication + a reverse implication

• 注意：上述的五个符号的优先级从上到下依次降低，即先计算上面的符号。例如

• 优先级一致的符号，从左往右计算

2.3 Semantics 语义

逻辑中对语义的处理，类似代数中的处理。逻辑同代数一样，不关心命题常数在现实世界中的意义，而关心简单句的真值和包含简单句的复杂句的真值之间的关系。

真值分配 a truth assignment： a truth assignment for a propositional vocabulary is a function assigning a truth value to each of the proposition constants of the vocabulary
虽然不关心现实世界中的意义，但是将真值分配明确并考虑各种分配是必要的。

真值与五种运算

φ	¬φ
1	0
0	1

φ	φ	φ ∧ φ
1	1	1
1	0	0
0	1	0
0	0	0

φ	φ	φ ∨ φ
1	1	1
1	0	1
0	1	1
0	0	0

实质蕴含 material implication: 当且仅当其前件为真且其后件为假时，implication的真值为假；否则，真值为true。
| φ | φ | φ ⇒ φ |
| ——- | ——- | ————- |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |

当且仅当其成分的真值一致时，biconditional 才是真的
| φ | φ | φ ⇔ φ |
| ——- | ——- | ————- |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |

2.4 Evaluation

Evaluation = 在给定命题常数真值的真值分配的情况下确定复合句子真值的过程

已知，

$$p^i = 0 \\ q^i = 1 \\ r^i = 0$$

在这种情况下，j 不满足 ( p ∨ q ) ∧ (¬ q ∨ r )，推导过程：

$$(p ∨ q) ∧ (¬q ∨ r)$$ $$(0 ∨ 1) ∧ (¬1 ∨ 0)$$ $$1 ∧ 0$$ $$0$$

2.5 Satisfaction 可满足性

Satisfaction is the opposite of evaluation.
我们从一个或多个复合句子开始，并试图找出哪些真值分配满足这些句子。
本节使用truth tables的方法

考虑 p ∨ q ⇒ q ∧ r，为p q r构建一个真值表来满足这个句子的所有真值分配

p	q	r	p ∨ q ⇒ q ∧ r
1	1	1	1
1	1	0	0
1	0	1	0
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	1
0	0	0	1

3. 命题分析 Propositional Analysis

本章内容：

• 单个句子的逻辑属性 logical properties（并非句子之间的关系）：validity, contingency, and unsatisfiability 有效性、偶然性、不满足性
• 句子之间的逻辑关系 logical relationship：logical entailment, logical equivalence, and logical consistency. 包含、等价、一致
• 单个句子的逻辑属性、句子之间的逻辑关系 之间的关系

3.2 逻辑属性 logical properties

三个不相交的类别

3.2.1 valid

1. valid：A sentence is valid if and only if it is satisfied by every truth assignment. $$( p ∨ ¬ p )$$

以上句子为valid，p = true or false，结果都为true

3.2.2 unsatisfiable

1. unsatisfiable：A sentence is unsatisfiable if and only if it is not satisfied by any truth assignment.

   $$( p ∧ - p )$$

以上句子为unsatisfiable，p = true or false，结果都为false

3.2.3 contingent

1. contingent ：a sentence is contingent if and only if there is some truth assignment that satisfies it and some truth assignment that falsifies it. $$( p ∧ q )$$

以上句子为contingent，p 、q = true or false，true false都有可能

3.2.4 satisfiable

将以上三中类别再合并成两组：

1. satisfiable = valid + contingent
2. unsatisfiable

3.3 逻辑关系 logical relationship

3.3.1 等价关系 Logical Equivalence

a sentence φ is logically equivalent to a sentence ψ if and only if every truth assignment that satisfies φ satisfies ψ and every truth assignment that satisfies ψ satisfies φ.
每个满足 φ 的真值赋值都满足 ψ并且每个满足 ψ 的真值赋值都满足 φ

例如 ：句子 ¬( p ∨ q ) 在逻辑上等价于句子 (¬ p ∧ ¬ q )。如果p和q都为真，那么这两个句子都是假的。如果p为真或q为真，则第一句为假。同样，如果p为真或q为真，则第二个句子为假。由于两个句子都满足相同的真值分配，因此它们在逻辑上是等价的。

substitutability 可替代性

• 等价关系的一个重要特性
• 如果一个句子 φ 在逻辑上等价于一个句子 ψ，那么我们可以在任何命题逻辑句子中用 φ 代替 ψ，结果将在逻辑上等价于原句。（但是这在 Relational Logic 并不完全正确）

3.3.2 蕴含关系 Logical Entailment

$$Δ ⊨ ψ$$

满足 Δ 中所有句子的每个真值分配也满足 ψ
a set of sentences Δ logically entails a sentence ψ (written Δ ⊨ ψ) if and only if every truth assignment that satisfies all of the sentences in Δ also satisfies ψ.

例子：p在逻辑上包含句子 ( p ∨ q )。因为只要其中一个为真，( p ∨ q )就为真，因此，只要p为真，( p ∨ q ) 就必须为真。另一方面，句子p在逻辑上不包含 ( p ∧ q )。一个连词当且仅当它的两连词都为真且q可能为假时才为真。因此可以写作

$$p ⊨ ( p ∨ q )$$

3.3.3 逻辑一致性 Logical Consistency

a sentence φ is consistent with a sentence ψ if and only if there is a truth assignment that satisfies both φ and ψ.

例如：句子 ( p ∨ q) 与句子 (¬ p ∨ ¬ q ) 一致，与 (¬ p ∧ ¬ q)不一致。第2、3行的赋值使 p ∨ q 与 ¬p ∨ ¬q 真值相同，而不存在赋值使得 p ∨ q 与 ¬p ∧ ¬q* 真值相同。

p	q	p ∨ q	¬p ∨ ¬q	¬p ∧ ¬q
1	1	1	0	0
1	0	1	1	0
0	1	1	1	0
0	0	0	1	1

两个句子在逻辑上一致，不等同于两个句子在逻辑上等价，也不等同于一个句子在逻辑上包含另一个

如果一个句子是不可满足的，那么就没有满足它的真值分配。因此，根据定义，满足 该不可满足的句子的每个真值分配（当然这并不存在）都可以满足另一个句子。
any unsatisfiable sentence or set of sentences logically entails everything
这也就是为什么要在逻辑推理中避免unsatisfiable的句子集

3.4 属性和关系之间的联系 Connections Between Properties and Relationships

3.4.1 等价定理 Equivalence Theorem

当且仅当句子 (φ ⇔ ψ) 有效时，句子 φ 和句子 ψ 在逻辑上是等价的。

3.4.2 演绎定理 Deduction Theorem

当且仅当 (φ ⇒ ψ) 有效时，一个句子 φ 在逻辑上包含一个句子 ψ。

更一般地，当且仅当复合句 (φ 1 ∧ … ∧ φ n ⇒ φ) 有效时，一组有限的句子 在逻辑上包含 φ

3.4.3 不可满足定理 Unsatisfiability Theorem

当且仅当句子集合 Δ ∪ {¬φ} 不可满足时，一组句子 Δ 在逻辑上包含一个句子 φ。

3.4.4 一致性定理 Consistency Theorem

当且仅当句子 (φ ∧ ψ) 可满足时，句子 φ 与句子 ψ 逻辑上一致。

更一般地，当且仅当复合句 (φ 1 ∧ … ∧ φ n ∧ φ) 是可满足的时，句子 φ 与有限的句子集 {φ 1 , … , φ n } 在逻辑上是一致的。

3.5 等价重写 Equivalence Rewritings

$$¬¬φ ⇔ φ$$ $$¬¬φ ⇔ φ ¬(φ ∧ ψ) ⇔ (¬φ ∨ ¬ψ)$$ $$(φ ⇒ ψ) ⇔ (¬φ ∨ ψ)$$ $$(φ ⇔ ψ) ⇔ (φ ⇒ ψ) ∧ (ψ ⇒ φ)$$

4. 直接证明 Direct Proofs

4.1 本章内容

• axiom schemas 公理, rules of inference 推理规则, direct proofs 直接证明
• 证明系统：the Hilbert system ；判断证明系统的标准： soundness and completeness 健全性、完整性
• hierarchical proofs and meta-theorems about proofs. 层次证明与证明的元定义

4.2 公理模式 axiom schemas

公理模式是个在公理系统的语言中的一个合式公式，其中有一个以上的模式变数出现。这些模式变数属于元语言的一种，代表系统内的任一项或任一公式。这些变数通常需要有部分是自由的，亦即有些不出现在公式或项中的变数。

$$φ ⇒ (ψ ⇒ φ)$$

当且仅当模式中每个实例都有效时，公理模式才有效。

$$Reflexivity\\ φ ⇒ φ$$ $$Negation Elimination \\ ¬¬φ ⇒ φ$$ $$Negation Introduction \\ φ ⇒ ¬¬φ$$ $$Tautology \\ φ ∨ ¬φ$$

4.3 推理规则 rules of inference

推理规则是一种推理模式。由一些模式（称为 前提premises ），和一个或多个附加模式（称为结论conclusions）组成。推理规则可写成下面这种形式，线以上的属于前提，线以下的属于结论。

$$\begin{align} &φ ⇒ ψ \\\\ &φ\\\\ \hline &ψ\\\\ \end{align}$$

• 蕴含消除 Implication Elimination (or IE)

eliminates the implication from the first premise

$$\begin{align}&φ ⇒ ψ \\\\&φ\\\\\hline&ψ\\\\\end{align}$$

• 蕴含分布 Implication Distribution (ID)

Implication can be distributed over other implications. If (φ ⇒ (ψ ⇒ χ)) is true, then we can infer ((φ ⇒ ψ) ⇒ (φ ⇒ χ)).

$$\begin{align} &φ ⇒ (ψ ⇒ χ)\\\\ \hline &(φ ⇒ ψ) ⇒ (φ ⇒ χ)\\\\ \end{align}$$

• 蕴含反转Implication Reversal (IR)

allows us to infer an implication if we have an implication with the arguments reversed and negated. If we know (¬ψ ⇒ ¬φ), we can infer (φ ⇒ ψ).

$$\begin{align} &¬ψ ⇒ ¬φ\\\\ \hline &φ ⇒ ψ \\\\ \end{align}$$

也可以用复杂句代替普通变量

$$\begin{align} &(p ⇒ q) ⇒ (q ⇒ r)\\\\ &(p ⇒ q)\\\\ \hline &(q ⇒ r)\\\\ \end{align}$$

4.4 直接证明 Direct Proofs

同一组前提的结论的直接证明。是一系列以结论结尾的句子，其中每一项要么是

• (1) a premise, 前提
• (2) an instance of an axiom schema, 公理模式的实例
• (3) the result of applying a rule of inference to earlier items in sequence. 前项的推理结果

例子如下

$$\begin{align} &1. \\; p &Premise\\\\ &2.\\; p ⇒ q &Premise\\\\ &3.\\; (p ⇒ q) ⇒ (q ⇒ r) &Premise\\\\ &4.\\; q &Implication Elimination: 2, 1\\\\ &5.\\; q ⇒ r &Implication Elimination: 3, 2\\\\ &6.\\; r &Implication Elimination: 5, 4\\\\ \end{align}$$

另举一例

$$\begin{align} &1.\\; p ⇒ q &Premise\\\\ &2.\\; q ⇒ r &Premise\\\\ &3.\\; p ⇒ (q ⇒ r) &Implication Creation: 2\\\\ &4.\\; (p ⇒ q) ⇒ (p ⇒ r) &Implication Distribution: 3\\\\ &5.\\; p ⇒ r &Implication Elimination: 4, 1\\\\ \end{align}$$

令 R 为一组推理规则。如果使用 R 中的推理规则在一组 Δ 的前提中存在一个句子 φ 的证明，我们说 φ 可以使用 R 从 Δ证明。我们通常使用可证明算子 ⊢ (有时称为单闸门 turnstile），将其写为

$$Δ ⊢ R_φ$$

如果从上下文中可以清楚地看到规则集，我们通常只写

$$Δ ⊢ φ$$

4.5 证明系统 Proof Systems：Hibert System

此处只讨论 有效公理模式和健全的推理规则的证明系统

Hibert System属于命题逻辑证明系统，它有一个推理规则 为 Implication Elimination

$$\begin{align}&φ ⇒ ψ \\\\&φ\\\\\hline&ψ\\\\\end{align}$$

Hibert System有三个公理模式

$$\begin{align} &Implication Creation (IC) &φ &⇒ (ψ ⇒ φ)\\\\ &Implication Distribution (ID) &(φ ⇒ (ψ ⇒ χ)) &⇒ ((φ ⇒ ψ) ⇒ (φ ⇒ χ))\\\\ &Implication Reversal (IR) &(¬ψ ⇒ ¬φ) &⇒ (φ ⇒ ψ)\\\\ \end{align}$$

举个例子，前提：（p⇒q）和（q⇒r）；目标：证明（p⇒r）

$$\begin{align} &1.\\; p ⇒ q &Premise\\\\ &2.\\; q ⇒ r &Premise\\\\ &3.\\; (q ⇒ r) ⇒ (p ⇒ (q ⇒ r)) &Implication Creation\\\\ &4.\\; p ⇒ (q ⇒ r) &Implication Elimination: 3, 2\\\\ &5.\\; (p ⇒ (q ⇒ r)) ⇒ ((p ⇒ q) ⇒ (p ⇒ r)) &Implication Distribution\\\\ &6.\\; (p ⇒ q) ⇒ (p ⇒ r) &Implication Elimination: 5, 4\\\\ &7.\\; p ⇒ r &Implication Elimination: 6, 1\\\\ \end{align}$$