01命题逻辑cnew

《01命题逻辑cnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主要内容范式析取范式合取范式主范式主析取范式主合取范式主析取范式的个数SEI1 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑析取范式和合取范式为叙述方便,把合取式称为积,析取式称为和。定义1命题公式中的一些命题变元和一些命题变元的否定范式之积,称为基本积;一些命题变元和一些命题变元的否定之和,称为基本和。例如：给定命题变元P和Q,则P,P∧Q,P∧Q,P∧P,主范式Q∧P∧Q等都是基本积；Q,Q∨P,P∨Q,P∨P,P∨Q∨Q等都是基本和。基本积(和)中的子公式称为此基本积(和)的因子。主析取范式的个数SEI2 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑析取范式和合取范式定义2一个由基本积之和组成的公式,如果与给定的命题公式A等价,则称它是A的析取范式,记为范式AA1∨A2∨…∨An,n≥1这里A1,A2,…,An是基本积。定义3一个由基本和之积组成的公式,如果与给定的命主范式题公式A等价,则称它是A的合取范式,记为AA1∧A2∧…∧An,n≥1这里A1,A2,…,An是基本和。主析取范式的个数SEI3 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑析取范式和合取范式对任意命题公式A，求其析取范式和合取范式的步骤：（1）将A中→，化成¬，∧，∨的等价形式；范式（2）利用德.摩根定律将否定词¬移到命题变元之前；（3）用结合律和分配律将公式规约为析取范式或合取范式注意：一个命题公式的析取范式（合取范式）不是唯一的,主范式我们把其中运算符最少的称为最简析取范式（最简合取范式）。主析取范式的个数SEI4 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑析取范式和合取范式例1：范式(a)求P∧(P→Q)的析取范式。解P∧(P→Q)P∧(¬P∨Q)P∧¬P∨P∧QF∨P∧Q主范式P∧QP∧Q是P∧(P→Q)的最简析取范式。主析取范式的个数SEI5 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑析取范式和合取范式例1(b)求¬(P∨Q)(P∧Q)的最简析取范式。范式解：¬(P∨Q)(P∧Q)(¬(P∨Q)→(P∧Q))∧((P∧Q)→¬(P∨Q))主范式((P∨Q)∨(P∧Q))∧(¬(P∧Q)∨¬(P∨Q))(¬(P∨Q)∧(P∧Q))∨((P∨Q)∧¬(P∧Q))(¬P∧¬Q∧P∧Q)∨((P∨Q)∧(¬P∨¬Q))主析取范式P∧¬Q∨Q∧¬P的个数SEI6 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑析取范式和合取范式例2求¬(P∨Q)(P∧Q)的最简合取范式。范式解：¬(P∨Q)(P∧Q)(¬(P∨Q)→(P∧Q))∧((P∧Q)→¬(P∨Q))主范式((P∨Q)∨(P∧Q))∧(¬(P∧Q)∨¬(P∨Q))(¬(P∨Q)∧(P∧Q))∨((P∨Q)∧¬(P∧Q))(P∨Q)∧¬(P∧Q)主析取范式(P∨Q)∧(¬P∨¬Q)的个数SEI7 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式定义在n个变元的基本积中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本范式积叫极小项。nn个变元可构成2个不同的极小项。例如3个变元P,Q,R可构造8个极小项。我们把命题变元看成1,命题变主范式元的否定看成0,那么每一极小项对应一个二进制数,因而也对应一个十进制数。主析取范式的个数SEI8 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式对应情况如下：¬P∧¬Q∧¬R——000——0范式¬P∧¬Q∧R——001——1¬P∧Q∧¬R——010——2¬P∧Q∧R——011——3主范式P∧¬Q∧¬R——100——4P∧¬Q∧R——101——5P∧Q∧¬R——110——6主析取范式的个数P∧Q∧R—111—7SEI9 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式我们把对应的十进制数当作足标,用mi表示极小项,即m0¬P∧¬Q∧¬Rm1¬P∧¬Q∧R范式m2¬P∧Q∧¬Rm3¬P∧Q∧Rm4P∧¬Q∧¬Rm5P∧¬Q∧Rm6P∧Q∧¬Rm7P∧Q∧R主范式一般地,n个变元的极小项是:m0¬P1∧¬P2∧¬P3…∧¬Pnm1¬P1∧¬P2∧¬P3…∧Pn主析取范式……的个数m2n-1P1∧P2∧P3…∧PnSEI10 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式定义一个由极小项之和组成的公式,如果与给定的命题公式A等价,则称它是A的主析取范式。范式任何一个命题公式都可求得它的主析取范式,这是因为任何一个命题公式都可求得它的析取范式,而析取范式可化为主析取范式。利用等价变换方法求公式的主析取范式过主范式程如下：1、化归为析取范式；2、除去析取范式中所有永假的析取项；3、将析取式中重复出现的合取项和相同的变元合并；主析取范式4、对合取项补入没有出现的变元。的个数SEI11 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式例：求P∧Q∨R的主析取范式。范式P∧Q∨RP∧Q∧(R∨¬R)∨(P∨¬P)∧(Q∨¬Q)∧RP∧Q∧R∨P∧Q∧¬R∨P∧¬Q∧R∨¬P∧Q∧R∨¬P∧¬Q∧Rm1∨m3∨m5∨m6∨m7主范式Σ1,3,5,6,7主析取范式的个数SEI12 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式每一极小项和它的足标的二进制数一一对应,因而和一种指派一一对应,例如三个变元时,范式极小项足标指派P∧Q∧R——111——1,1,1P∧Q∧¬R——110——1,1,0P∧¬Q∧R——101——1,0,1主范式¬P∧Q∧R——011——0,1,1¬P∧¬Q∧R——001——0,0,1定理：在真值表中，一个公式的真值为T的指派所对应主析取范式的个数的极小项的析取，即为此公式的主析取范式。SEI13 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式例：求用真值表求P∧Q∨R的主析取范式。范式P∧Q∨R¬P∧¬Q∧R∨¬P∧Q∧R∨P∧¬Q∧R∨主范式P∧Q∧¬R∨P∧Q∧Rm1∨m3∨m5∨m6∨m7Σ1,3,5,6,7主析取范式的个数SEI14 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题主析取范式和主合取范式逻辑极小项的性质:（1）每一个极小项当其真值指派与编码相同时,其真值才范式为1，在其余2n－1种指派情况下均为0。（2）任意两个不同的极小项的合取式永假。mi∧mjF,(i≠j)主范式（3）全体极小项的析取式永真。n21mTii0主析取范式的个数SEI15 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式在n个变元的基本和中,若每一个变元与其否定不同时存在,而二者之一必出现一次且仅出现一次,则这种基本和叫极范式n大项。n个变元可构成2个不同的极大项。类似于(但不同)极小项的记法,将命题变元对应于0,命题变元的否定对应于1,它们是:主范式M0P1∨P2∨…∨PnM1P1∨P2∨…∨¬PnM2P1∨P2∨…∨¬Pn-1∨Pn…主析取范式M2n-1P1∨¬P2∨…∨¬Pn的个数SEI16 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式定义一个由极大项之积组成的公式,如果与给定的命题公式A等价,则称它是A的主合取范式。范式任何一个命题公式都可求得它的主合取范式,这是因为任何一个命题公式都可求得它的合取范式,而合取范式可化为主合取范式。利用等价变换方法求公式的主合取范式过主范式程如下：1、化归为合取范式；2、除去合取范式中所有永真的合取项；3、将合取式中重复出现的析取项和相同的变元合并；主析取范式4、对析取项补入没有出现的变元。的个数SEI17 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式例5：求P∧Q∨R的主合取范式。范式解：P∧Q∨R(P∨R)∧(Q∨R)((P∨R)∨(¬Q∧Q))∧(Q∨R∨(¬P∧P))(P∨R∨¬Q)∧(P∨R∨Q))∧(Q∨R∨¬P)主范式(P∨¬Q∨R)∧(P∨Q∨R))∧(¬P∨Q∨R)M2∧M0∧M4∏0,2,4主析取范式的个数SEI18 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式例如:3个变元的极大项是这样对应的:极大项足标指派范式P∧¬Q∧R——010——0,1,0P∨Q∨R——000——0,0,0¬P∨Q∨R——100——1,0,0主范式定理：在真值表中，一个公式的真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。主析取范式的个数SEI19 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式例：求用真值表求P∧Q∨R的主合取范式。范式P∧Q∨RP∨Q∨R∧P∨¬Q∨R∧¬P∨Q∨R主范式∏0,2,4主析取范式的个数SEI20 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式极大项的性质:（1）每个极大项当其真值指派与编码相同时,其真值为0。范式（2）任意两个不同的极大项的析取式永真。Mi∨MjT,(i≠j)主范式（3）全体极大项的合取式永假。n21MFii0主析取范式的个数SEI21 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式一个命题公式的真值表是唯一的,因此一个命题公式的主合/析取范式也是唯一的。两个命题公式如果有相同的主范式合/析取范式,那么两个命题公式是逻辑等价的。一个命题公式的主析取范式和主合取范式紧密相关,在它们的简记式中,代表极小项和极大项的足标是互补的,即主范式两者一起构成0,1,2,…,2n-1诸数,例如P∧Q∨RΣ1,3,5,6,7P∧Q∨R∏0,2,4主析取范式的个数SEI22 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式和主合取范式例：求P→(（P→Q)∧¬(¬Q∨¬P))的主析取范式。范式解：P→(（P→Q)∧¬(¬Q∨¬P))¬P∨((¬P∨Q)∧(Q∧P))¬P∨((¬P∧Q∧P)∨(Q∧Q∧P))¬P∨(Q∧P)主范式¬P∧(Q∨¬Q)∨(Q∧P)¬P∧Q∨¬P∧¬Q∨P∧QΣ0,1,3主析取范式的个数SEI23 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式的个数1当n=1时,极小项有2=2个,即P,P。主析取范式有:范式主范式主析取范式的个数SEI24 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式的个数2当n=2时,极小项有2=4个,即P∧Q,P∧Q,P∧Q,P∧Q。主析取范式有：范式主范式主析取范式的个数SEI25 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑主析取范式的个数nn2假设有n个命题变元,共有2个极小项，可构造2个不同的主析取范式(包括F)。这个数字增长非常快,如n=3范式时223=256,n=4时224=65536。主合取范式和主析取范式是一一对应的,因此,n个命题主范式n变元,也可构造22个不同的主合取范式(包括T)。主析取范式的个数SEI26 hhzheng@mail.xidian.edu.cn程序设计基础高级语言程序设计离散数学•2007•春季秋季C++C++命题逻辑作业范式1.31,2,3(a),(c)主范式主析取范式的个数SEI27