笔记 逻辑学导论 Week2

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
运算符的优先级层次:
  1. ¬
  2. ∧∨
  3. ⇒ ⇔

命题词汇是一系列命题常量的集合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
注 命题逻辑里没有=这个符号,这里是一种元层面(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
求值:
(p ∨ q) ∧ (¬ q ∨ r)
过程:
(1 ∨ 0) ∧ (¬ 0 ∨ 1)
       1 ∧ (¬ 0 ∨ 1)
1 ∧ (1 ∨ 1)
1 ∧ 1
1

4 Satisfaction 满足

是求值的逆过程,从一个句子开始,试找出怎样的真值指派能够满足句子
Satisfaction is the opposite of evaluation.

5命题语句的逻辑属性Logical Properties of Propositional Sentences

一个语句可以是下面三种情况
  1. valid  对于所有的真值指派都满足语句
  2. unsatisfiable 一些真值指派可以满足语句,而另一些则不可以
  3. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *