资源描述：
《离散数学--2.4命题逻辑推理理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2.4命题逻辑推理理论2.4.1推理的形式结构推理的前提与结论,正确推理推理定律2.4.2自然推理系统P推理规则直接证明法,附加前提证明法,归谬法(反证法),归结证明法1有效推理定义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推理的形式结构形式(1)A1ÙA2Ù…ÙAk®B形式(2)前提:A1,A2,…,Ak结论:B推
2、理正确记作A1ÙA2Ù…ÙAkÞB判断推理是否正确的方法:真值表法等值演算法主析取范式法构造证明法3实例例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实例(续)(2)若今天是1号,则明天是5号.明天是5号.所以,今天是1号.解设p:今天是1号,q:明天是5号.推理的形式结构为(p®q)Ùq®p证明用主析
3、取范式法(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推理定律——重言蕴涵式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®
4、B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)破坏性二难6自然推理系统P自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,…,pi,qi,ri,…(2)联结词:,,,,(3)括号与逗号:(),,2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则7自然推理系统P(续)(7)拒取式规则A®BØBØA(8)假言三段论规则A®BB®CA®C(4)假言推理规则A®BAB(5)附加规则AAÚB(6)化简规则AÙBA8自然推理系统P(续)(11)破坏性二难推理规则A®BC®DØB
5、ÚØDØAÚØC(12)合取引入规则ABAÙB(9)析取三段论规则AÚBØBA(10)构造性二难推理规则A®BC®DAÚCBÚD9直接证明法例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实例例3构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必需备课.我今天下午没备课.所以,明天不是星期一
6、和星期三.解设p:明天是星期一,q:明天是星期三，r:我有课，s:我备课前提:(pÚq)®r,r®s,Øs结论:ØpÙØq11实例(续)前提:(pÚq)®r,r®s,Øs结论:ØpÙØq证明①r®s前提引入②Øs前提引入③Ør①②拒取式④(pÚq)®r前提引入⑤Ø(pÚq)③④拒取式⑥ØpÙØq⑤置换结论有效,即明天不是星期一和星期三12附加前提证明法欲证明等价地证明前提:A1,A2,…,Ak前提:A1,A2,…,Ak,C结论:C®B结论:B理由:(A1ÙA2Ù…ÙAk)®(C®B)ÛØ(A1ÙA2Ù…ÙAk)Ú(ØCÚB)ÛØ(A1
7、ÙA2Ù…ÙAkÙC)ÚBÛ(A1ÙA2Ù…ÙAkÙC)®B13实例例4构造下面推理的证明:前提:ØpÚq,ØqÚr,r®s结论:p®s证明①p附加前提引入②ØpÚq前提引入③q①②析取三段论④ØqÚr前提引入⑤r③④析取三段论⑥r®s前提引入⑦s⑤⑥假言推理推理正确,p®s是有效结论14归谬法(反证法)欲证明前提：A1,A2,…,Ak结论：B将ØB加入前提,若推出矛盾,则得证推理正确.理由:A1ÙA2Ù…ÙAk®BÛØ(A1ÙA2Ù…ÙAk)ÚBÛØ(A1ÙA2Ù…ÙAkÙØB)括号内部为矛盾式当且仅当(A1ÙA2Ù…ÙAk®B)为
8、重言式15实例例5构造下面推理的证明前提:Ø(pÙq)Úr,r®s,Øs,p结论:Øq证明用归缪法①q结论否定引入②r®s前提引入③Øs前提引入④Ør②③拒取式16实例(续)⑤Ø(pÙq)Úr前提引入⑥Ø(pÙq)④⑤析
