数学基础1.5推理理论

1.7

推理理论

定义若对于每组赋值，或者A1ÙA2Ù…Ù

Ak

均为假，或者当A1ÙA2Ù…ÙAk为真时,B也为真,则称由A1,A2,…,Ak推B的推理正确,否则推理不正确（错误）.“A1,A2,…,Ak

推B”的推理正确当且仅当(A1ÙA2Ù…ÙAk

)®B为重言式.推理的形式结构:(A1ÙA2Ù…ÙAk)®B或前提：A1,A2,…,Ak

结论：B

若推理正确，则记作：A1ÙA2Ù…ÙAkÞB.推理的形式结构可以写成如下两种形式：(1)A1ÙA2Ù…ÙAk®B(2)前提：A1,A2,…,Ak

结论：B

形式(1)用来判断推理是否正确：

真值表法；等值演算法；主范式法。形式(2)用来证明推理正确：构造证明法例判断下面推理是否正确

(1)若今天是1号，则明天是5号.今天是1号.所以明天是5号.

解设p：今天是1号，q：明天是5号.推理的形式结构为:(p®q)Ùp®q证明（用等值演算法）

(p®q)Ùp®q

Û

Ø((ØpÚq)Ùp)Úq

Û

ØpÚØqÚq

Û1得证推理正确(2)若今天是1号，则明天是5号.明天是5号.所以今天是1号.解设p：今天是1号，q：明天是5号.

推理的形式结构为:(p®q)Ùq®p

证明（用主析取范式法）

(p®q)Ùq®p

Û(ØpÚq)Ùq®p

Û

Ø((ØpÚq)Ùq)Úp

Û

ØqÚp

Û(ØpÙØq)Ú(pÙØq)Ú(pÙØq)Ú(pÙq)

Û

m0Úm2Úm3

结果不含m1,故01是成假赋值，所以推理不正确.重要的推理定律

A

Þ(AÚB)附加律

(AÙB)Þ

A

化简律

(A®B)ÙA

Þ

B

假言推理

(A®B)ÙØB

Þ

ØA

拒取式

(AÚB)ÙØB

Þ

A

析取三段论

(A®B)Ù(B®C)Þ(A®C)假言三段论

(A«B)Ù(B«C)Þ(A«C)等价三段论

(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)构造性二难(A®B)Ù(ØA®B)Þ

B

构造性二难（特殊形式）(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)破坏性二难

（1）前提引入规则：在证明的任一步骤都可以引入前提。（2）结论引入规则：在证明的任一步骤所得到的结论都可以作为后续证明的前提。（3）置换规则：在证明的任一步骤，命题公式中的子公式都可以用与之等值的公式代替。（4）附加规则：A⇒A∨B（5）化简规则：A,B⇒A；A,B⇒B（6）假言推理规则：A→B,A⇒B（7）拒取式规则：A→B,¬B⇒¬A（8）析取三段论规则：A∨B,¬B⇒A（9）假言三段论规则：A→B,B→C⇒A→C（10）等价三段论规则：A↔B,B↔C⇒A↔C（11）构造性二难规则：A→B,C→D,A∨C⇒B∨D（12）合取引入规则：A,B⇒A∧B推理规则

构造证明之一——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解

设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

证明①r®s

前提引入②Øs

前提引入③Ør①②拒取式④(pÚq)®r

前提引入⑤Ø(pÚq)③④拒取式⑥ØpÙØq⑤置换构造证明之二——附加前提证明法欲证明前提：A1,A2,…,Ak

结论：C®B等价地证明前提：A1,A2,…,Ak,C

结论：B

理由：(A1ÙA2Ù…ÙAk)®(C®B)

Û

Ø(A1ÙA2Ù…ÙAk)Ú(ØCÚB)

Û

Ø(A1ÙA2Ù…ÙAkÙC)ÚB

Û(A1ÙA2Ù…ÙAkÙC)®B前提：pÚq,p®r,r®Øs结论：s®q证明①s

附加前提引入②p®r

前提引入③r®Øs

前提引入④p®Øs②③假言三段论⑤Øp①④拒取式⑥pÚq

前提引入⑦q⑤⑥析取三段论

构造证明之三——归谬法(反证法)

欲证明前提：A1,A2,…,Ak

结论：B将ØB加入前提，若推出矛盾，则得证推理正确.理由:

A1ÙA2Ù…ÙAk®B

Û

Ø(A1ÙA2Ù…ÙAk)ÚB

Û

Ø(A1ÙA2Ù…ÙAkÙØB)括号内部为矛盾式当且仅当(A1ÙA2Ù…ÙAk®B)为重言式

例构造下面推理的证明前提：Ø(pÙq)Úr,r®s,Øs,p

结论：Øq证明（用归缪法）①q

结论否定引入②r®s

前提引入③Øs

前提引入

④

Ør

②③拒取式⑤Ø(pÙq)Úr

前提