演绎推理

　　在传统的亚里士多德逻辑中，演绎推理(英语：deductive reasoning）是“结论，可从叫做前提的已知事实，“必然的”得出的推理”。如果前提为真，则结论必然为真。这区别于溯因推理和归纳推理，它们的前提可以预测出高概率的结论，但是不确保结论为真。


　　“演绎推理”还可以定义为结论在普遍性上不大于前提的推理，或“结论在确定性上，同前提一样”的推理。

常用的基本论证形式　　演算的基本论证形式


　　名字 相继式 描述


　　肯定前件论式 (p → q) ∧ p ├ q 如果 p 则 q; p; 所以, q


　　否定后件论式 (p → q) ∧ ¬q ├ ¬p 如果 p 则 q; 非 q; 所以, 非 p


　　假言三段论式 (p → q) ∧ (q → r) ├ (p → r) 如果 p 则 q; 如果 q 则 r; 所以, 如果 p 则 r


　　选言三段论式 (p ∨ q) ∧ ¬p ├ q 要么 p 要么 q; 非 p; 所以, q


　　创造性二难论式 (p → q) ∧ (r → s) ∧ (p ∨ r) ├ (q ∨ s) 如果 p 则 q; 并且如果 r 则 s; 但是要么 p 要么 r; 所以, 要么 q 要么 s


　　破坏性二难论式 (p → q) ∧ (r → s) ∧ (¬q ∨ ¬s) ├ (¬p ∨ ¬r) 如果 p 则 q; 并且如果 r 则 s; 但是要么非 q 要么非 s; 所以，要么非 p 要么非 r


　　简化论式 (p ∧ q) ├ p p 与 q 为真; 所以，p 为真


　　合取式 p, q ├ (p ∧ q) p 与 q 分别为真; 所以，它们结合起来是真


　　增加论式 p ├ (p ∨ q) p 是真; 所以析取式(p 或 q)为真


　　合成论式 (p → q) ∧ (p → r) ├ p → (q ∧ r) 如果 p 则 q; 并且如果 p 则 r; 所以，如果 p 是真则 q 与 r 为真


　　德·摩根定律(1) ¬(p ∧ q) ├ (¬p ∨ ¬ q) (p 与 q)的否定等价于(非 p 或非 q)


　　德·摩根定律(2) ¬(p ∨ q) ├ (¬p ∧ ¬ q) (p 或 q)的否定等价于(非 p 与非 q)


　　交换律(1) (p ∨ q) ├ (q ∨ p) (p 或 q)等价于(q 或 p)


　　交换律(2) (p ∧ q) ├ (q ∧ p) (p 与 q)等价于(q 与 p)


　　结合律(1) p ∨ (q ∨ r) ├ (p ∨ q) ∨ r p 或(q 或 r)等价于(p 或 q)或 r


　　结合律(2) p ∧ (q ∧ r) ├ (p ∧ q) ∧ r p 与(q 与 r)等价于(p 与 q)与 r


　　分配律(1) p ∧ (q ∨ r) ├ (p ∧ q) ∨ (p ∧ r) p 与(q 或 r)等价于(p 与 q)或(p 与 r)


　　分配律(2) p ∨ (q ∧ r) ├ (p ∨ q) ∧ (p ∨ r) p 或(q 与 r)等价于(p 或 q)与(p 或 r)


　　双重否定律 p ├ ¬¬p p 等价于非 p 的否定


　　换位律 (p → q) ├ (¬q → ¬p) 如果 p 则 q 等价于如果非 q 则非 p


　　实质蕴涵律 (p → q) ├ (¬p ∨ q) 如果 p 则 q 等价于要么非 p 要么 q


　　实质等价律(1) (p q) ├ (p → q) ∨ (q → p) (p 等价于 q) 意味着, 要么(如果 p 是真则 q 是真)要么(如果 q 是真则 p 是真)


　　实质等价律(2) (p q) ├ (p ∧ q) ∨ (¬q ∧ ¬p) (p 等价于 q) 意味着, 要么(p 与 q 都是真)要么(p 和 q 都是假)


　　输出律 (p ∧ q) → r ├ p → (q → r) 从(如 p 与 q 为是真则 r 是真)我们可以证明(如果 q 是真则 r 为真的条件是 p 为真)


　　输入律 p → (q → r) ├ (p ∧ q) → r


　　重言式 p ├ (p ∨ p) p 是真等价于 p 是真或 p 是真


　　排中律 ├ (p ∨ ¬p) p 或非 p 是真

公理化　　更加形式化的说，演绎是陈述的序列，每个陈述都可以从它前面的陈述推导出来。本质上，这导致了如何证明第一个句子的公开问题(因为它不能从任何事物得到)。公理化命题逻辑通过要求证明满足下列条件来解决这个问题:


　　来自 wff 的全体 Σ 的证明 α 是一个 wff 的有限序列:


　　β1,...,βi,...,βn


　　这里的


　　βn = α


　　并且对于每个 βi (1 ≤ i ≤ n)， 要么


　　* βi ∈ Σ


　　要么


　　* βi 是一个公理。


　　要么


　　* βi 是两个前面的 wff βi-g 和 βi-h 的肯定前件的输出。


　　不同版本的公理化命题逻辑都包含一些公理，通常是三个或多于三个，除了一个或更多的推理规则之外。例如弗雷格公理化的命题逻辑，它也是这种尝试的第一个实例，有六个命题公理和两个规则。伯特兰·罗素和阿弗烈·诺夫·怀海德也提议了有五个公理的一个系统。


　　例如扬·武卡谢维奇(Jan Łukasiewicz，1878年-1956年)版本的公理化命题逻辑有接受如下公理的公理集合 A:


　　* [PL1] p → (q → p)


　　* [PL2] (p → (q → r)) → ((p → q) → (p → r))


　　* [PL3] (¬p → ¬q) → (q → p)


　　并且它有有一个规则的推理规则的集合 R，这个规则就是下面的肯定前件:


　　* [MP] 从 α 和 α → β, 推出 β。


　　推理规则允许我们从公理或给定的全体 Σ 的 wff 推导出陈述。


自然演绎逻辑　　在 E.J. Lemmon 提出的我们称为系统 L 的一个版本的自然演绎逻辑中，我们首先没有任何公理。我们只有支配证明的语法的九个基本规则。


　　系统 L 的九个基本规则是:


　　1. 假定规则 (A)


　　2. 肯定前件规则 (MPP)


　　3. 双重否定规则 (DN)


　　4. 条件证明规则 (CP)


　　5. ∧-介入规则 (∧I)


　　6. ∧-除去规则 (∧E)


　　7. ∨-介入规则 (∨I)


　　8. ∨-除去规则 (∨E)


　　9. 反证法规则 (RAA)


　　在系统 L 中，证明的定义有下列条件:


　　1. 有一个 wff(合式公式)的有限序列


　　2. 它的每行都被系统 L 的一个规则所证明


　　3. 证明的最后一行是想要的(Q.E.D, quod erat demonstrandum, 是拉丁语: 这就是要证明的)，并且证明的最后一行只使用给出的前提；或者没有前提如果什么都没有给出的话。


　　如果没有前提给出，则相继式叫做定理。所以在系统 L 中定理的定义是:


　　* 定理是在系统 L 中使用空的假定集合能证明的相继式。


　　或者换句话说:


　　* 定理是在系统 L 中从假定的空集可以证明的相继式。


　　相继式的证明的一个例子(这里是否定后件):


　　p → q, ¬q ├ ¬p [否定后件(MTT)]


　　假定号 行号 公式(wff) 使用的行和理由


　　1 (1) (p → q) A


　　2 (2) ¬q A


　　3 (3) p A (for RAA)


　　1,3 (4) q 1,3,MPP


　　1,2,3 (5) q ∧ ¬q 2,4,∧I


　　1,2 (6) ¬p 3,5,RAA


　　Q.E.D


　　相继式证明的一个例子(这里是一个定理):


　　├p ∨ ¬p


　　假定号 行号 公式(wff) 使用的行和理由


　　1 (1) ¬(p ∨ ¬p) A (for RAA)


　　2 (2) ¬p A (for RAA)


　　2 (3) (p ∨ ¬p) 2, ∨I


　　1, 2 (4) (p ∨ ¬p) ∧ ¬(p ∨ ¬p) 1, 2, ∧I


　　1 (5) ¬¬p 2, 4, RAA


　　1 (6) p 5, DN


　　1 (7) (p ∨ ¬p) 6, ∨I


　　1 ( (p ∨ ¬p) ∧ ¬(p ∨ ¬p) 1, 7, ∧I


　　(9) ¬¬(p ∨ ¬p) 1, 8, RAA


　　(10) (p ∨ ¬p) 9, DN


　　Q.E.D


　　系统 L 的每行都有自己对输入或进入的类型的要求，它可以接受并拥有它自己的处理和计算于是它的输入使用的假定的方式。