第3章命题逻辑-2..ppt

-1(1)命题变元或命题变元的否定称为文字。(2)有限个文字的析取式称为子句;有限个文字的合取式称为短语。例1(1)P,┐P是文字。(2)P,┐P,P∨Q∨R,┐P∨P,┐P∨┐Q∨┐R等都是子句。(3)P,┐P,P∧Q∧R,┐P∧P,┐P∧┐Q∧┐R等都是短语。-2(3)有限个短语的析取式称为析取范式;有限个子句的合取式称为合取范式。例2(1)P,┐P,P∨Q∨R,P∧Q∧R,(P∧Q)∨(┐P∧Q),等都是析取范式。(2)P,┐P,P∧Q∧R,P∨Q∨R,(P∨Q)∧(┐P∨Q),等都是合取范式。结论:任意的命题公式都可通过下列步骤化为等价的范式:(1)用联结词集“┐,∧,∨”取代公式中的“→,”;(2)将┐移到各命题变元之前;(3)用相应的运算“律”将公式化为要求的范式。Date2例3求公式(P∨┐Q)→R的析取范式和合取范式。解(P∨┐Q)→R =┐(P∨┐Q)∨R───析取范式=(┐P∧Q)∨R=(┐P∨R)∧(Q∨R)───合取范式注:公式的析(合)取范式不唯一。-1(1)设P1、P2、…、Pn是n个命题变元,一个短语或子句如果恰好包含所有这n个命题变元或命题变元的否定,且排列顺序与P1、P2、…、Pn的顺序一致,则称此短语或子句为关于P1、P2、..、Pn的一个极小项或极大项。,Q,R而言,P∧Q∧R,┐P∧Q∧R,┐P∧┐Q∧┐R等都是极小项而P∧P∧R,┐P∧P∧Q,P∧┐Q,┐R∧┐Q∧┐P都不是关于P,Q,(1)对于n个命题变元,共有2n个不同的极小项和2n个不同的极大项,分别记为m0,m1,…,m2n-1和M0,M1,…,M2n-1。例如关于P,Q,R有:解释对应的十进制数极小项mi极大项MiPQR0000m0=┐P∧┐Q∧┐RM0=P∨Q∨R0011m1=┐P∧┐Q∧RM1=P∨Q∨┐R0102m2=┐P∧Q∧┐RM2=P∨┐Q∨R…………1117m7=P∧Q∧RM7=┐P∨┐Q∨┐RDate5(2)含有n个命题变元的极小项mi和极大项Mi,作为命题公式,共有2n个不同的解释。在这2n个不同的解释中,有且仅有一个解释使得mi为1,有且仅有一个解释使得Mi为0,。PQP∧Q┐P∨Q00010**********例如:Date6(3)mi=┐Mi,Mi=┐mi;i=0,1,2,…,2n-1mi∧mj=F;Mi∨Mj=T;i≠j;i,j∈{0,1,2,…,2n-1}(4)每个不为永假式的短语,均可表示为与之等价的极小项或极小项的析取;每个不为永真式的子句,-2(2)由有限个极小项组成的析取范式称为主析取范式;(3)由有限个极大项组成的合取范式称为主合取范式。:永假式无主析取范式或者说主析取范式为“空”;永真式无主合取范式或者说主合取范式为“空”.Date8证明对任意的命题公式G,若G为永假式,由注释G的主析取范式为“空”。若G不为永假式,则先将G化为析取范式,再去掉其中为永假式的短语,并将其中不为永假式的短语用与之等价的极小项的析取取代,合并相同项即得G的主析取范式。类似可求得G的主合取范式。唯一性(略)(1) 求G=P→Q的主析取范式和主合取范式。解G=P→Q=┐P∨Q=(┐P∧(┐Q∨Q))∨((┐P∨P)∧Q)(=M2--主合取范式)=((┐P∧┐Q)∨(┐P∧Q))∨((┐P∧Q)∨(P∧Q))=(┐P∧┐Q)∨(┐P∧Q)∨(P∧Q)(=m0∨m1∨m3---主析取范式)例3 求P∧┐Q的主合取范式。解P∧┐Q=(P∨(┐Q∧Q))∧((┐P∧P)∨┐Q)Date10