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.