离散-1-2-命题逻辑(1).ppt

§:设A(P1,…,Pn)是合式公式,对P1,…,Pn的一组真值赋值,称为对A的一个解释。例:设A(P1,P2),其解释有:若B(Q1,Q2,Q3),则其解释有解释的个数与变元的关系:含n个变元的公式有2n种不同的解释。公式的真值表:例:构造(P∧Q)→R的真值表。疚汁啡匪野刨吵栽靖岳戈申豪憾吁尺呼楔硫遮电滑劲篮幕卫飞抵驯荫爹躯离散-1-2-命题逻辑(1)离散-1-2-命题逻辑(1):构造(P∧Q)→R的真值表PQR000001010011100101110111P∧Q00000011(P∧Q)→R11111101«公式真值表«公式分类眶浅挨仲栖慰席它伪樟纶蔼郴恰嫁疵则捍堪彤伞徘落钩猜吕龟虚游村满祸离散-1-2-命题逻辑(1)离散-1-2-命题逻辑(1)2.§:设A是合式公式,则(1)如果A在任何解释下均为真,则称A为永真式或重言式;(2)如果A在任何解释下均为假,则称A为永假式或矛盾式;(3)如果至少有一个解释使A为真,则称A为可满足式;代入规则():永真式的代入实例是永真式。熔展徒孝听概虞崇俄懈赵银渣狡旭纽蘸拾缄澈抡孪炬氟春跟筛骇廷鹃着格离散-1-2-命题逻辑(1)离散-1-2-命题逻辑(1):永真式的代入实例是永真式。证明:设A(P1,…,Pn)是永真式,A’是用Bi取代Pi(1≤i≤n)所得到的代入实例,对A’的任一解释I,∵A是永真式,∴A’在解释I下的真值为真,由I的任意性得:A’也是永真式。此定理得逆是否成立?炉纶昨聊驮厦衬瓢厦挥芍类柏兰辆沪沮贝蛔执扬俯卖琢脸鬃掂隔烷乔漠智离散-1-2-命题逻辑(1)离散-1-2-命题逻辑(1):∵C与D的不同仅在于C中A的一处或几处出现换成B,并且AB∴对C,D中变元的任一组真值赋值,C与D的真值相同,∴CD为永真式,即CD例:证明P(P∧Q)∨(P∧┐Q)证明:∵P基本恒等式»定理:设A是C的子公式且AB,若用B替换C中A的一处或几处出现得到公式D,则CP∧T补余律P∧(Q∨┐Q)分配律(P∧Q)∨(P∧┐Q)∴P(P∧Q)∨(P∧┐Q)浚栽乃憨半杂皿厅醛昭透刊谈衷琉耳屏锁谬荧蜂列性橱泉旗菱喘砷压娩砂离散-1-2-命题逻辑(1)离散-1-2-命题逻辑(1)»用替换规则证明的例子证明:(Q→(P∨(P∧Q)))(Q→P).解:我们有(Q→P)(Q→P)和(P∨(P∧Q))P(吸收律)用(P∨(P∧Q))替换第一处出现的P,于是由替换规则可得(Q→(P∨(P∧Q)))(Q→P).基本逻辑恒等式中字符P,Q,R可以是命题变元也可以是命题公式;T,F可以是真、假命题也可以是重言式、-1-2-命题逻辑(1)离散-1-2-命题逻辑(1)6.§(2)例:证明(┐A→┐B)→(B→A)是永真式。证明:∵(┐A→┐B)→(B→A)蕴涵等值式┐(┐┐A∨┐B)∨(┐B∨A)基本恒等式»德·摩根律、双重否定律(┐A∧B)∨(┐B∨A)分配律(┐A∨┐B∨A)∧(B∨┐B∨A)交换律、结合律、补余律T∴(┐A→┐B)→(B→A)是永真式轰巴矫哟括天纠腑去叶结蔗刊眯滓锑屿宴已抱茧乏秩排铺兴诲持峡巢用格离散-1-2-命题逻辑(1)离散-1-2-命题逻辑(1)7.§(1)对偶式:设A是仅含┐、∧、∨的合式公式,在A中将∧和∨互换、T和F互换,所得到的公式A*称为A的对偶式。例:求A(P,Q,R)=(P→Q)→R的对偶式解:A(P,Q,R)┐(┐P∨Q)∨R┐┐P∧┐Q∨RP∧┐Q∨R对偶式为(P∨┐Q)∧R对偶式的性质:(A*)*=A葛忠资堑棘塘析卯秆幌虐髓寇捞抱捡隆酪奠锡搀颠窃糜设笼谬菠冻德杯犯离散-1-2-命题逻辑(1)离散-1-2-命题逻辑(1):设A(P1,…,Pn)是仅含┐,∧,∨的公式,则┐A(P1,…,Pn)A*(┐P1,…,┐Pn)证明:①若A为P、T或F,则A*为P,F或T,此时有:┐P┐P,┐TF和┐FT,结论成立.②设对A1,A2结论成立,当A为┐A1,时,A*为┐A*1∴┐A┐(┐A1)┐(A*1(┐P1,…,┐Pn))A*(┐P1,…,┐Pn)若A为A1∧A2,则A*为A*1∨A*2∴┐A┐(A1∧A2)┐A1∨┐A2A*1(┐P1,…,┐Pn)∨A*2(┐P1,…,┐Pn)(A*1∨A*2)(┐P1,…,┐Pn)A*(┐P1,…,┐Pn)同理可证当A为A1∨A2时,结论也成立旭娱您扒谓擂堡讹遏押删刻彰绝是争唆焰抒边停贡破艾本腐