【正文】 ?設(shè) p：天冷； q：他穿外套； r：他穿襯衫。 ?設(shè) p：他學(xué)習(xí)； q：他將上清華大學(xué)； r：他將上北京大學(xué)。 6． 解 設(shè) p：張三說真話； q：李四說真話； r：王五說真話。 因此， p 為假， q 為真，所以 r 為假。 7． 解 設(shè) p：甲得冠軍； q：乙得亞軍； r：丙 得亞軍； s：丁得亞軍。 又 s??r 為真，其后件 ?r 為假，所以要求 s 為假，故 ?s 為真。命題符號(hào)化 qp? 。命題符號(hào)化 qp? 。 又 因?yàn)?qpqp ???? )()()()( pqqppqqpqp ??????????? 8 即含有 ??, 的公式均可以轉(zhuǎn)換為僅含 { ???, }中的聯(lián)結(jié)詞的公式。 故 { ???, }是功能完備聯(lián)結(jié)詞集。只有一個(gè)聯(lián)結(jié)詞，自然是極小功能完備集。 對(duì)于證明 }{? 是極小功能完備集，可類似證明。 )()( srqp ??? ? srqp ????? )( ? )()( srqsrp ???????? 即為其合取范式。 ?p?(q?r)??p?((q?r)?(?q??r)) ?(?p?q?r)?(?p??q??r) 即為其析取范式。 rqp ??? )( ? )()( rqrp ????? 為其析取范式。 3． 解 ? )( qpp ??? )())(( qpqqp ??????? ?????????? )2,1,0()()()( qpqpqp 即為其主合取范式。 ? )()( qpqp ?????? 1)()( ?????? qpqp 。 ? prqp ??? ))(( prqp ?????? ))(( prqp ????? ))(( )()( rpqp ????? 9 ))()(())()(( qqrprrqp ??????????? )()()()( rqprqprqprqp ???????????????? ?? )3,1,0( 即為其主合取范式。 ? )()( srqp ??? )()( srqp ??????? )()()()( srqsrpsrqp ??????????????? )()()()( srqpsrqpsrqpsrqp ?????????????????????????? )14,6,2( 即為其主合取范式。 4． 解 ?真值表如表 221 所示 , 所以其極小項(xiàng)是 p??q，極大項(xiàng)為 p?q， p??q， ?p??q。 ?真值表如表 2222 所示 , 所以其極小項(xiàng)是 ?p?q, p??q, p?q, 極大項(xiàng)為 p?q。 ?真值表如表 223 所示 ， 所以其極小項(xiàng)是 ?p?q?r,p??q??r, p??q?r, p?q??r,p?q?r, 表 223 p q r p? rqp ??? )( rqpp ???? 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 1 0 0 1 10 1 1 0 0 0 1 1 1 1 0 0 1 極大項(xiàng)為 p?q?r， p?q??r， p??q?r。 ?真值表如表 224 所示 ,所以其極小項(xiàng)為 ?p??q?r,?p?q?r,p??q??r,p??q?r,p?q?r, 而極大項(xiàng)分為 p?q?r， p??q?r， ?p??q? (p?q?r)?(p??q?r)?(?p??q?r), 主析取范式為 (?p??q?r)?(?p?q?r)?(p??q??r,)?(p??q?r)?(p?q?r)。 ? )())()(( rprqqp ????? ( ( ) ( ) ) ( )p q q r p r? ? ? ? ? ? ? ? ? ? ( ) ( ) ( )p q q r p 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? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) ( ) ( )p q r p q r p q r p q r? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( 0 ,1, 2 , 3 , 4 , 5 , 6 , 7 )? ? 故?為重言式。 故?為矛盾式。 6． 證明 ?右邊已經(jīng)是 主合取范式。 ? 右邊 (p? q)?(p??q)已經(jīng)是 主合取范式。 因此，)()( qpqpp ????? 。 習(xí)題 1． 解 設(shè) p：這里有演出； q：這里通行是困難的； r：他們按照指定時(shí)間到達(dá)。在①到②化簡時(shí)，只能對(duì)整個(gè)公式進(jìn)行而不是子公式。 ? P，? P 附加前提引入； ? T①②析取三段論； ? P； ? T③④假言推理； 13 ? P； ? T⑤⑥假言推理； ? T② ⑦ CP。 前提： p?q， q??r， ?r?s， ?s 結(jié)論： ?p 證明 ① p?q P ② q??r P ③ p??r ①②推理三段論 ④ ?r?s P ⑤ p?s ③④推理三段論 ⑥ ?s P ⑦ ?p ⑤⑥拒取式 復(fù)習(xí)題 1 1． 解 ? 設(shè) p： 3 是偶數(shù)， q：中國人的母語是漢語。 ? 設(shè) p：你抽煙， q：你很容易得病。 ? 設(shè) p：今天是星期一， q：明天才是星期二。 ? 設(shè) p：李春這個(gè)學(xué)期《離散數(shù)學(xué)》考了 100 分。命題符號(hào)化 qp? 。命題符號(hào)化 pq? 。 命題符號(hào)化 qp? 。命題符號(hào)化 qp? 。命題符號(hào)化 qp ??? 。 3． 解 設(shè) p：李剛會(huì)拳擊， q：李春會(huì)唱歌。而 (?p??q)??(p?q)?(?p??q)??(?p?q)?(?p??q)?p??q?p??q 因此， 李剛會(huì)拳擊并且李春不會(huì)唱歌 。成真賦值對(duì)應(yīng)二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)就是 A 的極小項(xiàng)的下標(biāo)。 相應(yīng)的， A 的極大項(xiàng)對(duì)應(yīng)于其真值表中的成假賦值，成假賦值對(duì)應(yīng)二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)就是 A 的極大項(xiàng)的下標(biāo)。 ?由問題 ?得到了 A 的極小項(xiàng)和極大項(xiàng)，于是 與 A 等值的主析取范式和主合取范式可以直接得到，分別為： (1, 6 , 8 , 9 ,1 0 ,1 2 ,1 3 ,1 5 )? ； ( 0 , 2 , 3 , 4 , 5 , 7 ,1 1,1 4 )? 。 (p??q)?(?q??p)?(?p??q)?(q??p)??(2,3)為其主合取范式，可見公式僅為可滿足式。 ? A=((p?q)?(q?r))?(p?r)真值表見習(xí)題 2?2 第 4(4)題。 7． ? 證明 ① p P 附加前提引入 16 ② p?(q?r) P ③ q?r T①②假言推理 ④ q P 附加前提引入 ⑤ q?(r?s) P ⑥ r?s T④⑤假言推理 ⑦ q?s T③⑥假言三段論 ⑧ p?(q?s) T①⑦ CP ? 證明 ① ?w P ② u?w P ③ ?u T①②拒取式 ④ ?s?u P ⑤ ?s T③④析取三段論 ⑥ ?r?s P ⑦ ?r T⑤ ⑥析取三段論 ⑧ (p?q)?r P ⑨ ?(p?q) T⑦⑧拒取式 ⑩ ?p??q) T⑨德 ?摩根律 ? 證明 ① p P 附加前提引入 ② p?q?r P ③ q?r T①②假言推理 ④ q??p P ⑤ ?q T①④拒取式 ⑥ r T③⑤析取三段論 ⑦ s??r P ⑧ ?s T⑥⑦拒取式 ⑨ p??s T①⑧ CP 8． 解 ① p?r P ② p T①化簡 ③ p?q P ④ q T②③假言推理 ⑤ ?(q?s) P ⑥ ?q??s T⑤德 ?摩根律 ⑦ ?q T⑥化簡 ⑧ ?q?q T④⑦合取 由⑧得到矛盾，可見 p?q， ?(q?s)， p?r 不能同時(shí)成立。符號(hào)化： (((p??q)?r)?p?(q?s)??s)?r。 表 229 由真值表可以看出：(((p??q)?r)?p?(q?s)??s)?r，所以，(((p??q)?r)?p?(q?s)??s)?r成立。 由此可以說明 (((p??q)?r)?p?(q?s)??s)?r 為重言式，即 (((p??q)?r)?p?(q?s)??s)?r 成立。因?yàn)?，兩個(gè)強(qiáng)盜一個(gè)總說真話，而另一個(gè)強(qiáng)盜一個(gè)總說假話，因此該問題符號(hào)化為： (?p?q)?r。所以， 當(dāng)被問強(qiáng)盜 A回答“否”，則邏輯學(xué)家開啟所指的門從容離去。 p q r s ?q ?s p??q (p??q)?r q?s A 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 18 第二章 謂詞邏輯 習(xí)題 1． 解 ?個(gè)體：離散數(shù)學(xué)；謂詞：?是一門計(jì)算機(jī)基礎(chǔ)課程。 ?個(gè)體：大學(xué)生；謂詞：?要好好學(xué)習(xí)計(jì)算機(jī)課程；量詞：所有。 2． 解 ?設(shè) )(xF ： x 是舞蹈演員； a：小芳。