离散数学与组合数学汇总

文章目录

一 推理的形式结构1 推理的形式结构2 推理定律-重言蕴涵式 二 自然推理系统P推理规则直接证明法附加前提法归谬法（反证法）

一 推理的形式结构

1 推理的形式结构

判断推理是否正确的方法:

真值表法等值演算法主析取范式法

2 推理定律-重言蕴涵式

二 自然推理系统P

定义3.3 自然推理系统 P 定义如下:

字母表 (1) 命题变项符号：p, q, r, …, pi, qi, ri, … (2) 联结词符号：¬, ∧, ∨, →, ↔ (3) 括号与逗号：(, ), ，合式公式（同定义1.6）推理规则

推理规则

(1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 (5) 附加规则 (6) 化简规则 (7) 拒取式规则 (8) 假言三段论规则 (9) 析取三段论规则 (10) 构造性二难推理规则 (11) 破坏性二难推理规则 (12) 合取引入规则

直接证明法

(1) 设命题并符号化 (2) 写出证明的形式结构 (3) 证明

附加前提法

用于结论为蕴涵式 欲证 前提：A1, A2, …, Ak 结论：C→B 等价地证明 前提：A1, A2, …, Ak, C 结论：B

归谬法（反证法）

欲证 前提：A1, A2, … , Ak 结论：B 做法 在前提中加入¬B，推出矛盾. 理由