(第3讲)命题逻辑

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,C,S,|,S,W,U,S,T,XDC,1.3,范式,1.3.1,析取范式和合取范式,定义 命题公式中的一些命题变元和一些命题变元的否定之合取,称为基本积,;,一些命题变元和一些命题变元的否定之析取,称为基本和。,有限个基本积,的析取式,称为,析取范式,；,有限个基本和,的合取式,称为,合取范式,。,最简析取范式和最简合取范式：运算符号最少,1.,单个的命题变元和命题变元的否定是一个,基本和、基本积、析取范式、合取范式。,、是基本积、基本和、析取范式、合取范式。,2.,单个的,基本和,是,合取范式。,是基本和、析取范式、合取范式；,结论,根据上述定义以,A(P,Q,R),为例可得：,3.,单个的,基本积,是,析取范式,。,是基本积、析取范式；,4.,若省略最外层括号，单个的,基本和,是,析取范式,，单个的,基本积,是,合取范式,。,是析取范式,;,是合取范式,;,5.,析取范式、合取范式,仅含联结词,、,、,，且,仅出现在命题变元前。,（）（）是合取范式。,求一个命题公式的与之等价的析取范式和合取范式，其步骤如下：,（,1,）利用恒等式表，将公式中的、,用联结词、来取代；,（,2,）利用德,摩根定律将否定号移到各个命题变元的前端；,（,3,）利用结合律、分配律、吸收律、等幂律、交换律等将公式化成其等价的析取范式和合取范式。,求,P,(,P,Q,),的析取范式。,解：,P,(,P,Q,),P,(,P,Q,),(,P,P),(,P,Q),0,P,Q,P,Q,析取范式,最简析取范式,实际上它同时也是最简合取范式,定义,在,n,个变元的基本积中,若每一个变元与其否定不同时存在,而两者之一必出现一次且仅出现一次,则这种基本积叫,极小项,。,1.3.2,主析取范式和主合取范式,例如，若命题公式中含有,3,个命题变元,(P,Q,R),，则可形成,8,个极小项。,P/,P,Q/,Q,R/,R,对应情况如下,:,P,Q,R,P,Q,R,P,Q,R,P,Q,R,P,Q,R,P,Q,R,P,Q,R,P,Q,R,0 0 0,0,0 0 1,1,0 1 0,2,0 1 1,3,1 0 0,4,1 0 1,5,1 1 0,6,1 1 17,小非,m,0,m,1,m,2,m,3,m,4,m,5,m,6,m,7,一般地,n,个变元的极小项是,:,m,0,P,1,P,2,P,3,P,n,m,1,P,1,P,2,P,3,P,n,m,2,n,-1,P,1,P,2,P,3,P,n,定义,在,n,个变元的基本和中,若每一个变元与其否定不同时存在,而二者之一必出现一次且仅出现一次,则这种基本和叫,极大项,。,n,个变元可构成,2,n,个不同的极大项。类似于,(,但不同,),极小项的记法,它们是,:,M,0,00.00,P,1,P,2,P,n,M,1,00.01,P,1,P,2,P,n,M,2,00.10,P,1,P,2,P,n,-1,P,n,M,2,n,-1,11.11,P,1,P,2,P,n,极小项有以下,3,个性质：,(1),在极小项中，将命题变元记为,1,，命题变元的否定记为,0,（,小非,），则每个极小项对应一个二进制数。则该,二进制数,是该极小项唯一的,成真赋值,。,(2),任意两个不同的,极小项的合取式,的值永假。例如，,(3),全体,极小项的析取式,的值永真，即,定义：,由,有限个,极小项组成的析取范式,称为,主析取范式,。,定义：,由,有限个,极大项组成的合取范式,称为,主合取范式,。,定理：,任何命题公式的主析取范式、主合取范式都是存在的，并且是唯一的。,定理：,任何命题公式的主析取范式与主析取范式均可以互相转化。,主范式,利用公式的等价求,G,(PQ)R,的主析取范式和主合取范式。,解,：,G,(PQ)R,(PQ)R,(PQ(RR),(PP)(QQ)R),(PQR)(PQR),(PQR)(PQR),(PQR)(PQR),(PQR)(PQR)(PQR),(PQR)(PQR),M,0,M,2,M,4,M,5,M,6,主合取范式,NO.1,求主范式的公式转换法,G,(PQ)R,(PQ)R,(PR)(QR),(P(QQ)R)(PP)QR),(PQR)(PQR),(PQR)(PQR),(PQR)(PQR)(PQR),m,1,m,3,m,7,主析取范式,例（续）,注意,1,：,在求,A,的主析取范式中，若,A,的某简单合取式,B,中不含命题变元,p,i,或其否定,p,i,，则将,B,展成如下形式：,注意,2,：,在求,A,的主合取范式中，若,A,的某简单析取式,B,中不含命题变元,p,i,或其否定,p,i,，则将,B,展成如下形式：,主范式的性质,任何命题公式都存在唯一一个与之等价的,主析取范式,和主合取范式,；,命题公式是永真公式当且仅当,它的主析取范式包含所有的极小项，此时无主合取范式或者说主合取范式为,“,空,”,；,命题公式是永假公式,当且仅当,它的主合取范式包含所有的极大项，此时无主析取范式或者说主析取范式为,“,空,”,；,两个命题公式是相等的,当且仅当,它们的主析取范式相等,(,即含有相同的极小项,),和主合取范式相等,(,即含有相同的极大项,),。,例,设,G,(PQ)R,(PQR)(PQR)(PQR),(PQR)(PQR),M,0,M,2,M,4,M,5,M,6,(PQR)(PQR)(PQR),m,1,m,3,m,7,NO.2,求主范式的真值表法,P,Q,R,(PQ)R,P,Q,R,(PQ)R,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,0,0,1,0,0,1,1,0,0,0,1,1,1,1,1,1,1,解,：真,值表,为,求主析取范式和主合取范式的简要方法,（,a,）从真值表知，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一,个解释所对应的极大项，将这些极大项的合取即可得到相应的,主合取范式,。,（真值表中的,0,代表极大项）,（,b,）从真值表知，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项的析取即可得到相应的,主析取范式,。,P Q R,PQ,（,PQ,）,(PQ),R,0 0 0,1,0,0,0 0 1,1,0,1,0 1 0,1,0,0,0 1 1,1,0,1,1 0 0,0,1,1,1 0 1,0,1,1,1 1 0,1,0,0,1 1 1,1,0,1,解,：首先列出其真值表如下：,例,G=(,),，,求主析取和主合取范式。,(1).,求主析取范式,(a).,从真值表知，该公式,G,恰有五个解释使其公式取值为,“,真,”,。为此，选出已给公式取值为,“,1,”,所在行所对应的变元取值如下：,1.,001,3.,011,4.,1 0 0,5.,1 0 1,7.,111,例（续）,G,的主析取范式,G=,（）,=(P,)(P,)(P,)(P,)(P,),(2).,求主合取范式,(a).,从真值表知，该公式,G,恰有三个解释使其公式取值为,“,假,”,。为此，选出已给公式取值为,“,0,“,所在行所对应的变元之值如下：,1.,0 0 0,3.,0 1 0,7.,1 1 0,这些行所对应的极大项分别为：,P,、,P,、,将这些极大项的合取即为该公式,G,的主合取范式：,G=,（）,=(P,)(P,)(,),例（续）,NO.3,求主范式的对应法：,由于一个命题公式的主析取和主合取范式关系非常密切。因此，只要求出了命题公式,A,的主析取范式，就可求出了主合取范式,(,反之亦然,),。,首先注意极小项与极大项之间的关系：,例如,，,设命题公式,A,中含,n,个命题变元，且设,A,的主析取范式中含,k,个极小项 ，则,A,的主析取范式中必含 个极小项，设为,即,例如,，,A,中含,3,个命题变项，主析取范式为,则主合取范式为,1.3.3,主,析取,范式的,个数,一,般来说,，,n,个变元的命题公式，其数量是无限的，,且,每个命题公式都对应着一个与它等价的主析取范式。,两个命题公式有相同的主析取范式，我们称这两个命题公式属于一个,等价类,。,属于一个等价类的命题公式，显然是互相等价的,那么，,含,n,个命题变元的命题公式，有多少个等价类呢？,当,n,=1,时,极小项有,2,1,=2,个,即,P,、,P,。,主析取范式有,:,没有极小项,全部极小项,当,n,=2,时，极小项有,2,2,=4,个。即,P,Q,、,P,Q,、,P,Q,、,P,Q,。主析取范式有,含,n,个命题变元的命题公式，有多少个等价类呢？,极小项：个,等价类：,