离散数学命题逻辑等值演算.pptVIP

4.解实际问题例9某单位要从A,B,C三人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)p?r,(2)q??r,(3)(p??q)?(?p?q)求下式的成真赋值A=(p?r)?(q??r)?((p??q)?(?p?q))主范式的应用*第31页，共64页，星期日，2025年，2月5日求A的主析取范式A=(p?r)?(q??r)?((p??q)?(?p?q))?(?p?r)?(?q??r)?((p??q)?(?p?q))?((?p??q)?(?p??r)?(r??q)?(r??r))?((p??q)?(?p?q))?((?p??q)?(p??q))?((?p??r)?(p??q))?((r??q)?(p??q))?((?p??q)?(?p?q))?((?p??r)?(?p?q))?((r??q)?(?p?q))?(p??q?r)?(?p?q??r)成真赋值:101,010结论:方案1派A与C去,方案2派B去主范式的应用*第32页，共64页，星期日，2025年，2月5日由主析取范式确定主合取范式例10设A有3个命题变项,且已知A=m1?m3?m7,求A的主合取范式.解A的成真赋值是1,3,7的二进制表示,成假赋值是在主析取范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示,它们恰好是A的主合取范式的极大项的下角标,故A?M0?M2?M4?M5?M6用成真和成假赋值确定主范式说明：1)由主合取范式确定主析取范式2)用真值表确定主范式*第33页，共64页，星期日，2025年，2月5日2.3联结词的完备集定义2.6称F:{0,1}n?{0,1}为n元真值函数。{0,1}n={00…0,00…1,…,11…1}，包含个长为n的0,1符号串.共有个n元真值函数。1元真值函数p0001110101*第34页，共64页，星期日，2025年，2月5日真值函数pq0001101100000000000011110011001101010101pq00011011111111110000111100110011010101012元真值函数*第35页，共64页，星期日，2025年，2月5日公式与真值函数任何一个含n个命题变项的命题公式A都对应惟一的一个n元真值函数F,F恰好为A的真值表。等值的公式对应的真值函数相同。例如：p?q,?p?q都对应说明：真值函数与主