Logical Reasoning

邏輯推論 Logical Reasoning 陳鍾誠 2006 年於金門

問題 Question • 要幾條邏輯推論規則才能推出所有真理呢 ? p ∧T ⇔ p p ∨F ⇔ p p ∨T ⇔ T p ∧F ⇔ F p ∨p ⇔ p p ∧p ⇔ p ¬¬p ⇔ p p ∨q ⇔ q ∨p p ∧q ⇔ q ∧p (p ∨q) ∨r ⇔ p ∨(q ∨r) (p ∧q) ∧r ⇔ p ∧(q ∧r) p∨(q∧r) ⇔ (p∨q)∧(p∨r) p∧(q∨r) ⇔ (p∧q)∨(p∧r) ¬(p∧q) ⇔ ¬p ∨¬q ¬(p∨q) ⇔ ¬p ∧¬q

….

邏輯推論的歷史 History of Proof System • Aristotle • Boole • Hilbert • Gentzen • Robinson

亞里斯多德 Aristotle

• 三段論

– http://zh.wikipedia.org/wiki/%E9%A1%B9%E9%80

經典範例 1 這個例子是亞里士多德給出的經典的 "Barbara" 三段論 : 如果所有人 (M) 都是必死的 (P), ( 大前提 ) 並且所有希臘人 (S) 都是人 (M), ( 小前提 ) 那麼所有希臘人 (S) 都是必死的 (P). ( 結論 )

經典範例 2 還有， 所有人都是必死的 . ( 普遍原理 ) 蘇格拉底是人 . ( 特殊陳述 ) 蘇格拉底是必死的 . ( 把特殊 ( 小 ) 代換入一般 ( 大 ))

型式 1 PQ QR PR

型式 2 P PQ Q

Mr. 洪 Mr. Horn • Horn Clause

P1 ∧… ∧Pk Q P1 … Pk Q

布爾 George Boole • 真值表 • 從真值表可推出三段 論嗎 ?

P PQ Q

Hilbert • Modus Ponens

Hilbert’s Axiom

Gentzen • Axioms and Rules of Inference

Gentzen’s Rules (1) • Disjunction rules

• Conjunction rules

Gentzen’ Rules (2) • Implication rules

• Negation rule

Completeness • Gentzen’s Rules are complete – All logical theorem can be proofed from these rules.

Robinson • Resolution Proof :

P ∨Q

; Q ∨R

-P ∨R

Robinson – second form

-P  Q

; Q ∨R

PR

Completeness • Robinson’s Rule is Complete under the resolution procedure. • Refutation – Proof by contradiction

Example

Question

PQ QS

-PR RS

Is S true under these rules ?

Question in ∧∨-

-P ∨Q -Q ∨S

P ∨R -R ∨S

Proof -R ∨S

-Q ∨S

-S

-P ∨Q

P ∨R

-Q -P R S

Reference • Symbolic Logic – http://en.wikipedia.org/wiki/Symbolic_logic

• 三段論

– http://zh.wikipedia.org/wiki/%E4%B8%89%E6%AE