离散数学对偶和范式.ppt

*主范式的用途(续)例某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？第31页,共35页，星期六，2024年，5月*例(续)解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式第32页,共35页，星期六，2024年，5月*例(续)解①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.②(1)(p?q)(2)(s?u)(3)((q??r)?(?q?r))(4)((r?s)?(?r??s))(5)(u?(p?q))③(1)~(5)构成的合取式为A=(p?q)?(s?u)?((q??r)?(?q?r))?((r?s)?(?r??s))?(u?(p?q))第33页,共35页，星期六，2024年，5月*例(续)④A?(?p??q?r?s??u)?(p?q??r??s?u)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:A?(?p?q)?((q??r)?(?q?r))?(s?u)?(?u?(p?q))?((r?s)?(?r??s))（交换律)B1=(?p?q)?((q??r)?(?q?r))?((?p?q??r)?(?p??q?r)?(q??r))（分配律）第34页,共35页，星期六，2024年，5月感谢大家观看第35页,共35页，星期六，2024年，5月关于离散数学对偶和范式*对偶式和对偶原理定义在仅含有联结词?,∧,∨的命题公式A中，将∨换成∧,∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)*还原成A显然，A也是A*的对偶式。可见A与A*互为对偶式。第2页,共35页，星期六，2024年，5月*对偶式和对偶原理定理设A和A*互为对偶式，p1,p2,…,pn是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则(1)?A(p1,p2,…,pn)?A*(?p1,?p2,…,?pn)(2)A(?p1,?p2,…,?pn)??A*(p1,p2,…,pn)(1)表明，公式A的否定等价于其命题变元否定的对偶式；(2)表明，命题变元否定的公式等价于对偶式之否定。第3页,共35页，星期六，2024年，5月*对偶式和对偶原理定理（对偶原理）设A，B为两个命题公式，若A?B，则A*?B*.有了等值式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等值式，使化简命题公式更为方便。第4页,共35页，星期六，2024年，5月*判定问题真值表等值演算范式第5页,共35页，星期六，2024年，5月*析取范式与合取范式文字:命题变项及其否定的总称如p,?q简单析取式:有限个文字构成的析取式如p,?q,p??q,p?q?r,…简单合取式:有限个文字构成的合取式如p,?q,p??q,p?q?r,…注意：一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如p，?q等。第6页,共35页，星期六，2024年，5月*析取范式与合取范式定理：简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。定理：简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。第7页,共35页，星期六，2024年，5月*析取范式与合取范式简单析取式:有限个文字构成的析取式如p,?q,p??q,p?q?r,…简单合取式:有限个文字构成的合取式如p,?q,p??q,p?q?r,…析取范式:由有限个简单合取式组成的析取式A1?A2???Ar,其中A1,A2,?,Ar是简单合取式合取范式:由有限个简单析取式组成的合取式A1?A2???Ar,其中A1,