北京大学：《离散数学》系列课程之三《数理逻辑》第26章 命题逻辑（26.5）推理形式

§5推理形式 前两节介绍了“命题”的形式。 本节介绍推理”的形式。 推理是逻辑的研究对象

§5 推理形式 ƒ 前两节介绍了“命题”的形式。 ƒ 本节介绍“推理”的形式。 ƒ 推理是逻辑的研究对象

什么是推理形式? 组前提,一个结论 ■前提、结论都是命题。 n若前提为a1,a2,…,∝n,结论为β, 则将这样的推理形式称为 Q1,a2,…,an推出B

什么是推理形式？ „ 一组前提，一个结论 „ 前提、结论都是命题。 „ 若前提为 α 1 ， α 2 ， … ， α n，结论为 β ， 则将这样的推理形式称为 α1， α2， … ， αn推出β

什么是正确的推理形式? ■直观上,正确的推理应该保证:如果前提 正确,则结论也应该正确。 定义12设α1,a2,…,Onβ都是命题形 式称推理“α1,(2,…,a推出β”是有效 的,如果对a1,α2,…,αnβ出现的命 题变元的任一指派,若1,α2,…,αn都 真,则β亦真;否则,称“α1,2,…,an 推出β”是无效的或不合理的

什么是正确的推理形式？ „ 直观上，正确的推理应该保证：如果前提 正确，则结论也应该正确。 „ 定义12 设 α 1 ， α 2 ， … ， α n, β都是命题形 式 ,称推理 “ α 1 ， α 2 ， … ， α n推出 β ” 是有效 的，如果对 α 1 ， α 2 ， … ， α n, β中出现的命 题变元的任一指派, 若 α 1 ， α 2 ， … ， α n 都 真, 则 β亦真；否则，称 “ α 1 ， α 2 ， … ， α n 推出 β ” 是无效的 或不合理的

例8 ■α→β、α推出β是有效的 nαB、-c推出β是有效的

例8 „ α → β、 α推出β是有效的。 „ α ∨ β、 ¬ α推出β是有效的

注记 推理形式是否有效与前提中命题形式的 排列次序无关。即: n若“a1,(2,…,an推出β”是有效的,则 对1,2,…,n的任一个排列1i2…,in a,a2推出”也是有效的。 ■所以前提是一个集合I,而不是一个序列。 若“α1;,02,…,n推出β”是有效的,则 记为rβ

注记 „ 推理形式是否有效与前提中命题形式的 排列次序无关。即： „ 若“α1，α2，…，αn推出β”是有效的，则 对1，2，…，n的任一个排列i1, i2, …, in, “ 推出β”也是有效的。 „ 所以前提是一个集合Γ，而不是一个序列。 „ 若“α1，α2，…，αn推出β”是有效的，则 记为Γ╞ β。 n αi αi αi , , , 1 2 L

例9下列推理形式是否有效? ∨q、-q、(p)q)推出r是无效的。 q0 q(D→q)>r 00 V00111111 011 10111 11 1 11010100 01011101

例9 下列推理形式是否有效？ p ∨ q、¬ q、(p →q) →r推出r是无效的。 ← 1 1 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 P q p ∨ q ¬ q (p →q) →r r

例10下列推理形式是否有效? (1)(-p1)vp2,p1→(p3^p4),p4→p2, p3→p推出p2Vp4 解:目的是看能否找到使前提为真、且结论为假的 指派。 使p2vp4为假的指派有(*,0,*,0), 其中使(-p)p2为真的指派有(0,0,*,0) 其中使p3→>p4为真的指派有(0,0,0,0), (0,0,0,0)使p1→>(p3∧p4和p4→p2都为真 从而这个推理是无效的

例10 下列推理形式是否有效？ (1) (¬p1) ∨ p2，p1 → (p3 ∧ p4)， p4 → p2， p3 → p4推出p2 ∨ p4 。 解：目的是看能否找到使前提为真、且结论为假的 指派。 使p2 ∨ p4为假的指派有（*，0，*，0）， 其中使 (¬p1) ∨ p2为真的指派有（0，0，*，0）， 其中使p3 → p4为真的指派有（0，0，0，0）， （0，0，0，0）使p1 → (p3 ∧ p4)和p4 → p2都为真。 从而这个推理是无效的

(2)p1→(p2→),p2推出p1→>p3 解: 使p1→3为假的指派有(1,*,0) 其中使p2为真的指派只有(1,1,0), 而(1,1,0)使p1→>(2→>p3)为假。 故没有使前提为真而结论为假的指派,从 而此推理有效

(2) p1 → (p2 →p3)，p2推出p1 →p3 解： 使p1 →p3 为假的指派有（1，*，0）， 其中使p2 为真的指派只有（1，1，0）， 而（1，1，0）使p1 → (p2 →p3) 为假。 故没有使前提为真而结论为假的指派，从 而此推理有效

充要条件 定理4推理形式“αx1,α2,…,αn推出β”有 效的充要条件是命题形式(u1^a2A…^an) →β是重言式。 意义:推理形式的有效性与命题形式的永真 性可以互相化约。 今后将建立带前提的证明系统和重言式证明 系统,并证明它们的等价性

充要条件 定理4 推理形式“α1，α2，…，αn推出β” 有 效的充要条件是命题形式(α1 ∧ α2 ∧ … ∧ αn) → β是重言式。 意义：推理形式的有效性与命题形式的永真 性可以互相化约。 今后将建立带前提的证明系统和重言式证明 系统，并证明它们的等价性

些有效推理 a若a}F",且{BFy, 则ravB}Fy n若I{-ax}Fβ,且{-a}-β, 则rFa

一些有效推理 „ 若Γ∪ { α } ╞ γ，且Γ∪ { β } ╞ γ ， 则Γ∪ { α ∨ β } ╞ γ „ 若Γ∪ {¬ α } ╞ β，且Γ∪ {¬ α } ╞ ¬ β ， 则 Γ ╞ α 。 „ …