1Propositional Logic 命题逻辑
命题是一个对世界可能状况的描述，可以是真也可以是假
Roughly speaking, a proposition is a possible condition of the world that is either true or false
2语法syntax
命题逻辑包含两种语句
- 简单句 simple sentences
简单句在书写时由字符、数字和下划线构成，第一个字符需要小写
简单句采取的是原子符号（atomic symbol）的形式，又称为命题常量（proposition constants）
简单句表达了有关世界的简单事实 express simple facts about the world. - 复合句 compound sentences
复合句表达的是组成其的所有简单句之间的逻辑关系 express logical relationships between the simpler sentences of which they are composed.
逻辑连接符：
- negation
(¬p) ~p - conjunction
(p ∧ q) p % q - disjunction
(p ∨ q) p | q - implication
(p ⇒ q) p => q - equivalence
(p ⇔ q) p <=> q
运算符的优先级层次：
- ¬
- ∧∨
- ⇒ ⇔
命题词汇是一系列命题常量的集合A propositional vocabulary is a set of proposition constants.
命题语言是一个命题词汇所能组成的所有命题语句的集合A propositional language is the set of all propositional sentences that can be formed from a propositional vocabulary.
3语义semantic
truth assignment for Propositional Logic is a function assigning a truth value to each of the proposition constants of the language.
真值指派 truth assignment 赋予一个命题常量其真值，写时为上标的i
pi = 1
qi = 0
ri = 1
qi = 0
ri = 1
注 命题逻辑里没有=这个符号，这里是一种元层面(metalevel)的描述
真值表：
| φ | ¬φ |
|---|---|
| 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 |
| φ | ψ | φ ⇒ ψ |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
| φ | ψ | φ ⇔ ψ |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
evaluation method 求值方式：用0或1来替代
前提：
pi = 1
qi = 0
ri = 1
qi = 0
ri = 1
求值：
(p ∨ q) ∧ (¬ q ∨ r)
过程：
(1 ∨ 0) ∧ (¬ 0 ∨ 1)
1 ∧ (¬ 0 ∨ 1)
1 ∧ (1 ∨ 1)
1 ∧ 1
1
1 ∧ (1 ∨ 1)
1 ∧ 1
1
4 Satisfaction 满足
是求值的逆过程，从一个句子开始，试找出怎样的真值指派能够满足句子
Satisfaction is the opposite of evaluation.
5命题语句的逻辑属性Logical Properties of Propositional Sentences
一个语句可以是下面三种情况
- valid 对于所有的真值指派都满足语句
- unsatisfiable 一些真值指派可以满足语句，而另一些则不可以
- contingent 所有真值指派都不能满足语句
6 命题蕴含Propositional Entailment
命题蕴含是命题逻辑中的逻辑蕴含
当且仅当所有满足Δ（一系列语句的集合）的真值指派都同样满足φ时，我们才可以说Δ在逻辑上能够蕴含φ（写作Δ |= φ）
例：Δ为{p}，φ为（p ∨ q），Δ |= φ是否成立（hold or not hold）？
| p | q | p | p ∨ q |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 |
则知成立(hold)
真值表的蕴含判断方法的缺点在于计算的复杂性，16个命题常量的时候，可能的真值指派为2的16次方种
Unsatisfiability Theorem
不满足性定理：
当且仅当Δ 与 {¬φ}的交集是无法满足的时候Δ |= φ
Δ |= φ if and only if Δ ∪ {¬φ} is unsatisfiable.