笔记 逻辑学导论 Week3

课程地址 https://class.coursera.org/intrologic-003/class/index

3.1 证明 Proof

逻辑上的证明是对句子进行符号上的操作,而不是枚举所有可能的真值指派来进行判断。其结果必然与通过枚举真值指派的各种情况所得结果是相同的。

分两种类型:
  1. Linear Proof 线性证明
  2. Structured Proof 结构化的证明

3.2 Linear Proof

是从一系列前提出发,根据一系列的推演规则,推导出结论的过程
模式Schema
是一个使用元变量来对满足逻辑语言中语法规则的语句的表达
例:a=>b是模式φ=>ψ的一个实例(instance)
推演规则rule of inference
推演规则由一系列模式(Schema)所构成的推理模式(Pattern),这些模式包括一些前提和一个或更多个结论。
在横线之上写前提,在横线之下写结论:
如Implication Elimination(IE) 写作:
3-1
推演规则的实例是将句子中的元变量用具体的变量来替换掉后所得的结果,如:
3-2

3.3常用的公理集 Axiom Schemata

Mendelson 门德尔森公理集包括四条规则IE、IC、ID和CR
  1. Implication Elimination(IE)
    3-1
  2. Implication Creation schema (IC):
    IC
  3. The Implication Distribution schema (ID):
    ID
  4. The Contradiction Realization schema (CR):
    CR

3.4 Linear proof示例:

前提为p=>q和q=>r问是否能推导出p=>r?
Ex1

3.5结构化证明Structured Proofs

在Structured Proof中我们可以提出假设,但是每次提出假设都将使得假设和假设后得出的语句置于一个subproof的下位句组里,在句组里可以使用一般的推演规则,但是只有使用了结构化的推演规则(II)后才能将得到的结论用于上位句组中。
例:
Ex2

3.6 Fitch

Fitch是一个证明系统,包含了10条推演规则,其中9条是普通推演规则,1条(II)是结构化推演规则
  • AI 和 AE
    AIAE
  • OI 和 OE
    OIOE
  • NI 和 NE
    NINE
  • II 和 IE
    IIIE
  • EI 和 EE
    EIEE

3.7 可靠性和完备性 Soundness and Completeness

可靠性:
当且仅当所有可证明的结论都是逻辑上蕴含的,即
sound
时我们说一个证明系统是可靠的。
完备性:
当且仅当所有逻辑结论都是可被证明的,即
comp
时我们说一个证明系统是完备的。

Leave a Reply

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