离散数学命题逻辑.pptVIP

例3(续)(3)((p?q)?(p??q))?r)解((p?q)?(p??q))?r)?(p?(q??q))?r（分配律）?p?1?r（排中律）?p?r（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A?0A为重言式当且仅当A?1说明：演算步骤不惟一,应尽量使演算短些*第62页，共121页，星期日，2025年，2月5日第一章命题逻辑1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4联结词全功能集1.5对偶与范式1.6推理理论*第63页，共121页，星期日，2025年，2月5日1.4联结词全功能集一、联结词的扩展异或联结词∨与非联结词↑或非联结词↓二、真值函数三、联结词全功能集*第64页，共121页，星期日，2025年，2月5日一、复合联结词排斥或:p∨q?(p??q)?(?p?q)与非式:p?q??(p?q)或非式:p?q??(p?q)*第65页，共121页，星期日，2025年，2月5日二、真值函数问题：含n个命题变项的所有公式共产生多少个互不相同的真值表？定义称定义域为{00…0,00…1,…,11…1}，值域为{0,1}的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:{0,1}n?{0,1}表示F是n元真值函数.共有个n元真值函数.*第66页，共121页，星期日，2025年，2月5日2元真值函数对应的真值表pq0001101100000000000011110011001101010101pq0001101111111111000011110011001101010101*第67页，共121页，星期日，2025年，2月5日三、联结词的全功能集定义在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词.例如,在联结词集{?,?,?,?,?}中，p?q??p?q,所以，?为冗余的联结词;类似地，?也是冗余的在{?,?,?}中，p?q??(?p??q)，所以，?是冗余的联结词.*第68页，共121页，星期日，2025年，2月5日全功能集，极小功能集若任一真值函数都可以用含某一联结词集中的联结词的命题公式表示，则称该联结词集为全功能集。若一联结词的全功能集中不含冗余的联结词，则称它为极小全功能集。{┐,∧,V,?,→}，{┐,∧,V,?,→，↓，↑}，{┐,∧,V}，{┐，V}，{┐,∧}，{↑}，{↓}为全功能集。{┐,V}，{┐,∧}，{↑}，{↓}为极小全功能集。*第69页，共121页，星期日，2025年，2月5日用{↓}表示下列命题公式：极小功能集例题1.p∧q?┐┐p∧┐┐q?┐(┐p∨┐q)?┐((p↓p)∨(q↓q))?(p↓p)↓(q↓q)2.p∨q?┐┐(p∨q)?┐(p↓q)?(p↓q)↓(p↓q)p→q?┐p∨q?(p↓p)∨q?A∨q?(A↓