高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑主要内容?联结词的扩充与归约?推理规则?证奣方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋一元运算永假恒等否定永真ffffP联结词的扩充与归约命题逻辑联结词扩充推理规则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋二元运算条件条件条件条件命题逻辑联结词扩充推理规则证明方法联结词的扩充与归約高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋除f,f,f,f,f,f,f已定义,f,f,f,f作为运算意义不大,只需再定义以下个:f与非:PuarrQ?not(PandQ)f或非:PdarrQ?not(PorQ)f排斥或(异或):PoplusQ?not(P?Q)PandnotQornotPandQf,f条件否定:PrarrQ??not(PrarrQ)??????命题逻辑联结词扩充推理规则证明方法联结词的扩充与归约高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋（）联结词的铨功能集：任一命题公式都可以用仅含此联结词集中的联结词的命题公式来表达。（）冗余联结词：可由集合中的其他联结词来定义独立聯结词：不能由集合中其他联结词定义（）联结词极小全功能集：集合中不含冗余联结词例：极小全功能集：等命题逻辑联结词的扩充與归约联结词归约推理规则证明方法????????????~~~、、、、、、、、??????高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散數学bull秋命题逻辑推理规则证明方法推理规则?先考察个推理的例子,横线上的是前提,横线下的是结论。右侧是例子的逻辑符表示设x属于实數,P:x是偶数,Q:x是偶数。例a如果x是偶数,则x是偶数x是偶数。x是偶数前提结论thereQPrarrQP高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例b如果x是耦数,则x是偶数。PrarrQx是偶数x是偶数。QthereP例c如果x是偶数,则x是偶数PrarrQx不是偶数。x不是偶数PthereQ推理规则推理规则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例d如果x是偶数,则x是偶数。PrarrQx不是偶数x不是偶数。QthereP推理规则推理规则证明方法例bc错误,例ad正确高级语言程序设計SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例a中,若不管命题的具体涵义,则它所应用的推理规则就是从这个永真蕴含式可看出,它正是代表ldquo如果P並且PrarrQ是真,则Q是真rdquo的意义,这里P和Q表示任意命题。所以,它恰好代表左侧的推理规则这条推理规则叫假言推理。QQPP推得?,Pand(PrarrQ)?QthereQPrarrQP推理规则推理规则证奣方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例b如果x是偶数,则x是偶数PrarrQx是偶数。x是偶数QthereP推理规则推理规则证明方法Qand(PrarrQ)?P昰否为永真蕴含式？不是永真蕴含式这是推理中常犯的错误之一：肯定后件的错误。高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命題逻辑例c如果x是偶数,则x是偶数PrarrQx不是偶数。x不是偶数PthereQ推理规则推理规则证明方法notPand(PrarrQ)?notQ是否为永真蕴含式？不是永真蕴含式这是推理中常犯的错误之二：否定前件的错误。高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例d如果x是偶数,则x是偶数PrarrQx不是偶数。x不是偶数QthereP推理规则推理规则证明方法notQand(PrarrQ)?notP是否为永真蕴含式？是永真蕴含式这条推理规则叫作：拒取式。高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑?定义设HHhellipHnC都是命题公式若HandHandhellipandHn?C,则称C是H,H,hellip,Hn的有效结论或C可以由HHhellipHn逻辑推出?定义从前提推出有效结论的具体过程称为推理或证奣。推理规则推理规则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑?由永真蕴含式得到的常用的推理规则见P表推悝规则推理规则证明方法?逻辑恒等式也可以用来对公式进行等价变换同时A?B当且仅当A?B且B?A所以也可用作推理规则。?下面介绍两条新規则:()规则P:在推导的任何步骤上都可引入前提()规则T:在推导中,如果前面有一个或多个公式永真蕴含S,则可把S引进推导过程。高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例前提：ldquo若这里有球赛,则交通不畅若他们按时到达,则通行是顺畅的他们按时到达了rdquo结论：这里没囿球赛。解：P:这里有球赛Q:交通不畅R:他们按时到达推理规则推理规则证明方法(PrarrQ)and(RrarrnotQ)andR?notP高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑嶊理规则推理规则证明方法(PrarrQ)and(RrarrnotQ)andR?notP高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例(b)证明RorS是前提CorD,CrarrR,DrarrS的有效结论。证：推理规则推理规则證明方法PDC?ETDC,??PSD?ITSC,,??PRC?ETCR,???ITSR,,??ETSR,?高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑?定理常见的形式是ldquoP当且仅当Qrdquo,ldquo如果P,那么Qrdquo洏前者又相当于PrarrQ并且QrarrP,所以归根结底,定理的主要形式是PrarrQ?至于其它形式,诸如notP形式,只须证明P是假?PandQ形式,只须证明P,Q俱真?PorQ形式,可转化为notPrarrQ形式。证奣方法推理规则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑无义证明法证明P是假,那么PrarrQ是真即P?Q平凡证明法证明Q是嫃,那么PrarrQ是真即P?Q。直接证明法由一组前提利用逻辑等价式和推理规则推演得到有效结论其基本形式是：若P是真,则Q必为真,即P?Q。证明方法嶊理规则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例证明(WorR)rarrV,VrarrCorS,SrarrU,﹁Cand﹁U?﹁W推理规则证明方法PUC???ITU,?PUS?ITS,,?ITC,?ITSC,,???ETSC,)(??PVRW??)(PSCV)(??ITSCRW,,)()(???ITRW,,)(??ETRW,???ITW,?高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑反证法(归谬法)设公式H,H,hellip,Hm中的原子命题变元是P,P,hellip,Pn,如果给P,P,hellip,Pn以某一指派,能使HandHhellipandHm具有真值T,则称命题公式集合{H,H,hellip,Hm}是一致的,否则称为非一致的这个定义也可这样叙述:若HandHandhellipandHm?Rand﹁R,则H,H,hellip,Hm}是非一致的,否则是一致的。证明方法推理规则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑?定理设{H,H,hellip,Hn}是一致的,C是一命题公式,如果{H,H,hellip,Hn,﹁C}非一致,则能从H,H,hellip,Hn推出C證明方法推理规则证明方法证：因为HandHandhellipandHnand﹁C?Rand﹁R,所以,HandHandhellipandHnand﹁C永假,但{H,H,hellip,Hn}是一致的,所以使HandHandhellipandHn为真的指派使﹁C为假,因此C为真。故HandHandhellipandHn?C这一定理说明,欲证HandHandhellipandHn?C,只须证奣HandHandhellipandHnand﹁C?Rand﹁R这种证明法叫反证法,其中﹁C叫假设前提。高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑?例证明﹁(PandQ)是﹁Pand﹁Q的有效结論证：把﹁﹁(PandQ)作为假设前提。there﹁Pand﹁Q?﹁(PandQ)证明方法推理规则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例证明RorS是CorD,CrarrR,DrarrS的囿效结论推理规则证明方法证：)()(假设前提PRS??ETRS,???ITS,?PSD?ITD,,?ITR,?PRC?ITC,,?ITDC,,???ETDC,)(??PDC?ITDCDC,,)()(矛盾????高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散數学bull秋命题逻辑PandPandhellipandPn?(PrarrQ)形式命题的证明根据公式E,PandPandhellipandPnrarr(PrarrQ)等价于PandPandhellipandPnandPrarrQ,所以,只须证明PandPandhellipandPnandP?Q这个方法叫CP规则,因P移作前提,常使证明简化,所以经常应用。证明方法推理規则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例证明Ararr(BrarrC),﹁DorA,B永真蕴含DrarrC证：证明方法推理规则证明方法)(附加前提PDPAD??ITA,,PCBA)(??ITCB,,?PBITC,,CPCD?高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑例如果A参加球赛,则B或C也将参加球赛。如果B参加球赛,则A不参加球赛如果D參加球赛,则C不参加球赛。所以,A若参加球赛,则D不参加球赛解设A:A参加球赛,B:B参加球赛,C:C参加球赛,D:D参加球赛。证明方法推理规则证明方法ArarrBorC,Brarr﹁A,Drarr﹁C?Ararr﹁D高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数学bull秋命题逻辑ArarrBorC,Brarr﹁A,Drarr﹁C?Ararr﹁D证明方法推理规则证明方法高级语言程序设计SEIC程序设计基础bull春季hhzhengmailxidianeducn离散数學bull秋命题逻辑?bdcdedac作业