x本科数理逻辑-命题3-8.ppt

,复习,1、逻辑等值定义给定两个命题公式A和B，设A和B含有共同的n个命题变元。若对于这n个命题变元的所有可能的赋值，命题公式A与B的真值均相同，则称命题公式A逻辑等值于命题公式B。并记作AB。逻辑等值的另外的形式定义：给定两个命题公式A和B，设A和B含有共同的n个命题变元。若由A和B构成的等价式AB为重言式（永真式），则称命题公式A逻辑等值于命题公式B注：“”不是连接词，仅表示两个公式具有等值关系传递性：若A，则A,2、判断两个公式是否等值的方法真值表方法：列出两个公式的真值表，看其真值是否相同（最基础的方法）演算法：以经过验算的等值式为基础（乘法公式定律）利用置换规则（等值代换）及其等值的性质得到其他的等值式,二、等值定律1.双重否定律AA2.等幂律AAAAAA3.结合律(AB)CA(BC)(AB)CA(BC)4.交换律ABBAABBA5.分配律A(BR)(AB)(AR)A(BR)(AB)(AR)6.吸收律A(AB)AA(AB)A7.德摩根律(AB)AB(AB)AB8.同一律AFAATA9.零律ATTAFF10.排中律AAT11矛盾律AAF12蕴涵等值式ABAB13等价等值式AB（AB）（BA）AB（AB）（BA）AB（AB）（AB）同真同假14假言易位（逆否命题）ABBA15等价否定等值式ABAB16归谬论（AB）（AB）A,三、置换规则：设（A）是含公式A的命题公式，（B）是用公式B置换了（A）中所有出现的A所得到的命题公式，则若AB有（A）（B）注：置换规则类似于代数中的变量替换如：公式(pq)r因为pq与pq等值故可用pq置换pq所得到的公式与原式是等值的即：(pq)r（pq）r(pq）r与（pq）r等值故有（pq）r（pq）r（pq）r,例：证明下列等值式(PQ)(P（PQ)(PQ)解：(PQ)(P(PQ)(PQ)(P(PQ)蕴涵等值(PQ)(PQ)等幂律(PQ)PQ结合律(PP)(QP)Q分配律T(QP)Q同一律QP等幂律PQ交换律,四、利用等值演算可确定公式的类型判断(pq)pq的类型若能得到A则可得到公式A为重言式A则可得到公式A为矛盾式因为(pq)pq公式(p（q)）r的类型公式（q)p）的类型利用等值演算还可以化简一个命题公式命题公式的等值演算是数理逻辑中的最基本运算。,.析取范式与合取范式(公式的标准型式）一简单析取式和简单合取式1）“文字”定义命题变项及其否定统称作文字2）仅由有限个文字构成的析取式称作简单析取式pq、pqrq3）仅由有限个文字构成的合取式称作简单合取式(项）qppqrp4)简单析取式和简单合取式的性质：一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式,二析取范式和合取范式1、定义(1)由有限个简单合取式构成的析取式称为析取范式(代数式）pqrqppqp(2)由有限个简单析取式构成的合取式称为合取范式(pq)qppqrq(3)析取范式与合取范式统称为范式Ai(i=1,2n)为简单合取式，A=A1A2.An为析取范式pqrpqqprq是含三个简单合取式的析取范式Bi(i=1,2n)为简单析取式，B=B1B2.Bn为合取范式pqr(pq)qp（pq）（qpr）q是含三个简单析取式的合取范式,2、性质：1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式pPqq000（pp）（qq）111,确定公式(pq)r的析取范式和合取范式3、范式存在定理任一命题公式都存在着与之等值的析取范式与合取范式利用等值定律可将任何公式化成与之等值的析取范式和合取范式确定析取范式和合取范式(pq)（pr)(pq)（pr)总可以通过以下方法步骤：1消去联结词(若存在)2否定号的消去(利用双重否定律)或内移(利用德摩根律)3利用分配律：利用对的分配律求析取范式，对的分配律是否唯一?,例:确定(pq)r)p的析取范式及合取范式(pq)r)p(pq)r)p(pq)r)p(pqp)(rp)(pqp)(rp)合取范式(pq)(rp)合取范式(pq)r)p（r)(pq)r)p(pq)r)p(pq)r)p(pr)(qr)p析取范式p(pr)(qr)p(qr)析取范式(4）析取范式和合取范式的不唯一性,三、主析取范式析取范式和合取范式的不唯一性主要是由于：构成的元素是因为简析取式和简单合取式的不唯一性将其约束为极小项和极大项1、极小项在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，称这样的简单合取式极小项。极小项与所含变元的个数有关含二个变元p,q的极小项：,两个变元p,q的所有极小项为pq、pq、pq、pq按字母标记为m0m1m2m3相应极小项的成真赋值为(0,0)、（0，1）、（1，0）、（1，1）,三个变元的所有极小项为：pqr、pqr、pqr、pqr、按字母排序为m0、m1、m2、m3、相应极小项的成真赋值为(0,0，0)、（0，0,1）、（0,1，0）、（0,1，1）pqr、pqr、pqr、pqrm4、m5、m6、m7(1,0，0)、（1，0,1）、（1,1，0）、（1,1，1）2）n个变元的所有极小项共有2n,(pq)（pr)(pq)(pr)(qr)仅是析取范式，并不是主析取范式（简单合取式不是极小项，三个变元）,2、主析取范式1）定义设由n个命题变项构成的析取范式中所有的简单合取式都是极小项，则称该析取范式为主析取范式。2）主析取范式的唯一性定理25任何命题公式都存在着与之等值的主析取范式，并且是惟一的a)析取范式的存在性b)简单合取化为极小项得到存在性c)通过真值表得到唯一性3)公式的主析取范式中的极小项所对应的赋值均为成真赋值,也是该公式的全部成真赋值(由真值表得出）公式的主析取范式包含全部极小项,则该公式为重言式,(pq)rpqr仅是析取范式，并不是主析取范式（简单合取式不是极小项，三个变元）,3、主析取范式的确定方法：（1）等值演算法(pq)（pr)(pq)(pr)(qr)(pq)ra)先确定公式的析取范式b)将简单合取式化为极小项（不断合取所缺变元的永真式）c)将相同极小项去掉（2）真值表法列出公式的真值表pqr将真值表中真值为真的相应赋值所对应的极小项进行析取（3）利用主析取范式与主合取范式的关系若已知公式A的主析取范式首先写出A的主析取范式对A的主析取范式取否定可得到A的主合取范式,4、主析取范式的应用a.确定公式的成真赋值b.判断公式的类型若公式的主析取范式包含所含变元的全部极小项则该公式为永真式若公式的主析取范式包含所含变元的若干极小项则该公式为可满足式若公式的主析取范式不包含所含变元的任何极小项则该公式为永假式c.判断两个公式是否等值,前面所介绍的：二析取范式和合取范式1、定义(1)由有限个简单合取式构成的析取式称为析取范式(代数式）pqrqppqp(2)由有限个简单析取式构成的合取式称为合取范式(pq)qppqrq(3)析取范式与合取范式统称为范式Ai(i=1,2n)为简单合取式，A=A1A2.An为析取范式pqrpqqprq是含三个简单合取式的析取范式Bi(i=1,2n)为简单析取式，B=B1B2.Bn为合取范式pqr(pq)qp（pq）（qpr）q是含三个简单析取式的合取范式,2合取范式1)定义:(2)由有限个简单析取式构成的合取式称为合取范式2)性质：(1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式,3）范式存在定理任一命题公式都存在着与之等值的析取范式与合取范式利用等值定律可将任何公式化成与之等值的析取范式和合取范式总可以通过以下方法步骤：1消去联结词(若存在)2否定号的消去(利用双重否定律)或内移(利用德摩根律)3利用分配律：利用对的分配律求合取范式，对的分配律公式的合取范式表示不唯一（主要是由于构成合取范式中的简单析取式表示不唯一）将简单析取式给予限制为极大项,四、主合取范式极大项：在含有n个命题变项的简单析取式中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，称这样的简单析取式极大项。2.极大项与所含变元的个数有关两个变元p,q的所有极大项为pq、pq、pq、pq按字母排序为M0、M1、M2、M3相应极大项的成真假值为(0,0)、（0，1）、（1，0）、（1，1）三个变元的所有极大项为：pqr、pqr、pqr、pqr、M0（0,0,0)、M1(0,0,1)、M2(0,1,0)、M3(0,1,1)、pqr、pqr、pqr、pqrM4(1,0,0)、M5(1,0,1)、M6(1,1,0)、M7(1,1,1)3.n个变元的所有极大项共有2n4.主合取范式1）定义设由n个命题变项构成的合取范式中所有的简单合取式都是极大项，则称该合析取范式为主合取范式。,2.主合取范式1）定义设由n个命题变项构成的合取范式中所有的简单析取式都是极大项，则称该合析取范式为主合取范式。例(pq)r(pr)(qr)(pqr)先确定相应的合取范式，再将简单析取式化为极大项（通过析取F）注：该式的极大项所对应的赋值均为该公式的成假赋值，也是该公式的全部成假赋值（可从真值表得出）3、主合取范式的确定方法：（1）等值演算法例：p（pq)a)先确定公式的合取范式b)将简单析取式化为极大项（不断析取所缺变元的永假式）c)将相同极大项去掉（2）真值表法列出公式的真值表将真值表中真值为假的相应赋值所对应的极大项进行合取（3）利用主析取范式与主合取范式的关系若已知公式A的主析取范式首先写出A的主析取范式(从全部极小项去掉A式包含的极小项得到）对A的主析取范式取否定可得到A的主合取范式,例：（pq)r确定主析取范式和主合取范式4、主合取范式的唯一性（可从真值表的唯一性得到）定理25任何命题公式都存在着与之等值的主合取范式，并且是惟一的证明：1）合取范式的存在性2）将合取范式中的简单合取式化为极大项即可得到存在性唯一性可从极大项的不同得出其成假赋值的不同得到5、应用a.确定公式的全部成假赋值.A(p,q)M0M3(pq)(pq)全部成假赋值为（0，0）与（1，1）b.判断公式的类型若公式的主合取范式包含所含变元的全部极大项则该公式为永假式若公式的主合取范式包含所含变元的若干极大项则该公式为可满足式c.判断两个公式是否等值p与（pq)(pq）,2.3连接词的完备集一、联接词的扩充1)异或联接词Pq(pq)(pq)2)与非联接词定义设p、q为两个命题，复合命题“p与q的否定式”称作p，q的与非式，记作pq，符号)称作与非联结词，pq为真当且仅当p与q不同时为真。pq(pq)3)或非联接词定义设p、q为两个命题，复合命题“p或q的否定式”称作p，q的或非式，记作pq符号或非联结词。pq为真当且仅当p与q同时为假。pq(pq),4)几种连接词的关系（1)p(pp)ppp(pp)pp(2）pq(pq)(pp)(pp)(pp)（3）(pq)(pq)(pq)(pq)(