离散数学命题逻辑推理理论_第1页
离散数学命题逻辑推理理论_第2页
离散数学命题逻辑推理理论_第3页
离散数学命题逻辑推理理论_第4页
离散数学命题逻辑推理理论_第5页
已阅读5页,还剩17页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

离散数学命题逻辑推理理论1第1页,课件共22页,创作于2023年2月有效推理定义2.20若对于每组赋值,A1ÙA2Ù…Ù

Ak

为假,或者当A1ÙA2Ù…ÙAk为真时,B也为真,则称由前提A1,A2,…,Ak推B的推理有效或推理正确,并称B是有效的结论定理2.8

由前提A1,A2,…,Ak

推出B的推理正确当且仅当

A1ÙA2Ù…ÙAk®B为重言式.2第2页,课件共22页,创作于2023年2月推理的形式结构形式(1)

A1ÙA2Ù…ÙAk®B形式(2)

前提:A1,A2,…,Ak

结论:B

推理正确记作A1ÙA2Ù…ÙAkÞB判断推理是否正确的方法:真值表法等值演算法主析取范式法构造证明法3第3页,课件共22页,创作于2023年2月实例例1

判断下面推理是否正确:(1)若今天是1号,则明天是5号.今天是1号.所以,明天是5号.解设p:今天是1号,q:明天是5号推理的形式结构为(p®q)Ùp®q证明用等值演算法

(p®q)Ùp®q

Û

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

Û

ØpÚØqÚq

Û1得证推理正确4第4页,课件共22页,创作于2023年2月实例(续)(2)若今天天冷,小王就穿羽绒服。小王就穿羽绒服。所以,今天天冷。解设p:今天天冷,q:小王穿羽绒服.推理的形式结构为(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Úm301是成假赋值,所以推理不正确.5第5页,课件共22页,创作于2023年2月推理定律——重言蕴涵式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)破坏性二难6第6页,课件共22页,创作于2023年2月自然推理系统P自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,…,pi,qi,ri,…(2)联结词:

,

,,,(3)括号与逗号:(),,2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则7第7页,课件共22页,创作于2023年2月自然推理系统P(续)(7)拒取式规则

A®B

ØB

\ØA(8)假言三段论规则

A®B

B®C

\A®C

(4)假言推理规则

A®BA

\B(5)附加规则

A

\AÚB(6)化简规则

AÙB

\A

8第8页,课件共22页,创作于2023年2月自然推理系统P(续)(11)破坏性二难推理规则

A®B

C®D

ØBÚØD

\ØAÚØC(12)合取引入规则

A

B

\AÙB

(9)析取三段论规则

AÚB

ØB

\A(10)构造性二难推理规则

A®B

C®D

AÚC

\BÚD9第9页,课件共22页,创作于2023年2月直接证明法例2

在自然推理系统P中构造下面推理的证明:前提:

pÚq,q®r,p®s,Øs结论:rÙ(pÚq)证明①

p®s前提引入②Øs

前提引入③

Øp

①②拒取式④

pÚq

前提引入⑤q

③④析取三段论

⑥q®r

前提引入⑦r

⑤⑥假言推理⑧rÙ(pÚq)

⑦④合取推理正确,rÙ(pÚq)是有效结论10第10页,课件共22页,创作于2023年2月实例例3

构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必需备课.我今天下午没备课.所以,明天不是星期一和星期三.解设p:明天是星期一,q:明天是星期三,

r:我有课,s:我备课前提:(pÚq)®r,r®s,Øs结论:ØpÙØq

11第11页,课件共22页,创作于2023年2月实例(续)前提:(pÚq)®r,r®s,Øs结论:ØpÙØq

证明①r®s

前提引入②Øs

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

前提引入⑤Ø(pÚq)③④拒取式⑥ØpÙØq⑤置换结论有效,即明天不是星期一和星期三12第12页,课件共22页,创作于2023年2月附加前提证明法欲证明等价地证明前提:A1,A2,…,Ak前提:A1,A2,…,Ak,C结论:C®B结论:B理由:(A1ÙA2Ù…ÙAk)®(C®B)

Û

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

Û

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

Û(A1ÙA2Ù…ÙAkÙC)®B13第13页,课件共22页,创作于2023年2月实例例4

构造下面推理的证明:前提:ØpÚq,ØqÚr,r®s结论:p®s证明①

p附加前提引入②ØpÚq

前提引入③

q

①②析取三段论④

ØqÚr

前提引入⑤r

③④析取三段论

⑥r®s

前提引入⑦s

⑤⑥假言推理推理正确,p®s是有效结论14第14页,课件共22页,创作于2023年2月归谬法(反证法)欲证明前提:A1,A2,…,Ak

结论:B将ØB加入前提,若推出矛盾,则得证推理正确.理由:A1ÙA2Ù…ÙAk®B

Û

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

Û

Ø(A1ÙA2Ù…ÙAkÙØB)括号内部为矛盾式当且仅当(A1ÙA2Ù…ÙAk®B)为重言式15第15页,课件共22页,创作于2023年2月实例例5

构造下面推理的证明前提:Ø(pÙq)Úr,r®s,Øs,p结论:Øq证明用归缪法①q

结论否定引入②r®s

前提引入③Øs

前提引入④Ør②③拒取式16第16页,课件共22页,创作于2023年2月实例(续)⑤Ø(pÙq)Úr

前提引入⑥Ø(pÙq)④⑤析取三段论⑦ØpÚØq⑥置换⑧Øp①⑦析取三段论⑨p

前提引入⑩ØpÙp⑧⑨合取推理正确,Øq是有效结论17第17页,课件共22页,创作于2023年2月归结证明法理由(pÚq)Ù(ØpÚr)®(qÚr)ÛØ((pÚq)Ù(ØpÚr))Ú(qÚr)Û(ØpÙØq)Ú(pÙØr)ÚqÚrÛ((ØpÙØq)Úq)Ú((pÙØr)Úr)Û(ØpÚq)Ú(pÚr)Û1归结规则

AÚB

ØAÚC

\BÚC18第18页,课件共22页,创作于2023年2月归结证明法(续)在自然推理系统P中只需下述推理规则:(1)前提引入规则(2)结论引入规则(3)置换规则(4)化简规则(5)合取引入规则(6)归结规则19第19页,课件共22页,创作于2023年2月归结证明法的基本步骤1.将每一个前提化成等值的合取范式,设所有合取范式的全部简单析取式为A1,A2,…,At2.将结论化成等值的合取范式B1ÙB2Ù…ÙBs,其中每个Bj是简单析取式3.以A1,A2,…,At为前提,使用归结规则推出每一个Bj,1js4.由合取引入规则得到结论B1ÙB2Ù…ÙBs20第20页,课件共22页,创作于2023年2月实例例6

用归结证明法构造下面推理的证明:前提:(p®q)®r,r®s,Øs结论:(p®q)®(pÙs)解(p®q)®rÛØ(ØpÚq)ÚrÛ(pÙØq)ÚrÛ(pÚr)Ù(ØqÚr)

r®sÛØrÚs(p®q)®(pÙs)ÛØ(ØpÚq)Ú(pÙs)

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论