数理逻辑 第26章§6 命题演算自然推理形式系统N 王捍贫 北京大学信息科学技术学院软件研究所
26 §6 N ✁✂ ✄☎✆✝✞✟✠✝✡☛✝☞✌✍✎✏✑
6命题演算的自然推理形式系统N 怎么在计算机上实现如下有效推理: {p→q,q→r}+p→r 识别符号p,q,r, 别公式p→q,q→r, ●推理方法
§6 N ✒ {p → q, q → r} ` p → r • p, q, r, . . . • p → q, q → r, . . . • 1
计算机上实现有效推理需要建立: 字母表(符号库)一非空集合 ●公式集合一字母表中符号的有限序列 ●公理集合一公式集合的子集 规则集合一公式集合的部分多元运算
✓ • ✔✕— • — • — • — 2
形式系统 符号库(字母表) ·(形式)公式 推理 (形式)公理 (形式)推理规则 符号库和形式公式统称为形式语言。 形式公理和形式推理规则统称为形式推理。 命题演算的自然推理形式系统N
• ✔✕ • ( ) • ( ) • ( ) ✖ ✖ ✗✘N 3
N的符号库 p1,P2, (可数个命题符号) V,∧ (5个联结词符号) (3)) (2个辅助符号)
N (1) p1, p2, . . . ( ) (2) ¬, ∨, ∧, →, ↔ (5 ) (3) ), ( (2 ) 4