【正文】 p q r s? ? ? ? ； 8m p q r s? ? ? ? ? ? ?；9m p q r s? ? ? ? ? ?； 10m p q r s? ? ? ? ? ?； 12m p q r s? ? ? ? ? ?；13m p q r s? ? ? ? ?； 15m p q r s? ? ? ?。 14 4． 解 ? A 的極小項對應于其真值表中的成真賦值 0001， 0110， 1000， 1001， 1010， 1100， 1101， 1111。命題符號化 (?p??q)??(p?q)。 2. 解 命題中的“或”是不可兼或，因此，可以直接用 “ qp? ”符號化；根據(jù)聯(lián)結(jié)詞的性質(zhì)及其之間的轉(zhuǎn)換關(guān)系，可知 命題 “李春生于 1979 年或生于 1980 年 ”的本意是 “李春生于 1979 年（但不能生于 1980年） 或生于 1980 年（但不能生于 1979 年） ”，因此，也可以轉(zhuǎn)化為 “ )()( qpqp ????? ”對其進行符號化。 ? 設(shè) p：以物喜， q：以己悲。 ? 設(shè) p：一朝被蛇咬， q：十年怕井繩。 ? 設(shè) p：經(jīng)一事， q：長一智。 ? 設(shè) p：下雪路滑， q：他遲到了。 q：李春這個學期《數(shù)據(jù)結(jié)構(gòu)》考了 100 分。命題符號化 pq? 。命題符號化 qp? 。命題符號化 qp? 。 5． 解 設(shè) p：張三努力工作， q：李四高興， r：王五高興， s：劉六高興 前提： p?(q?r)， q??p， s??r 結(jié)論： p??s 證明：① 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 6． 解 設(shè)： p：天下雪； q：馬路結(jié)冰； r：汽車開得快； s：馬路塞車。 4． 解 正確。 前提： p?q, r??q,r 結(jié)論： ?p 證明 ① r P ② r??q P ③ ?q T①②假言推理 ④ p?q P ⑤ ?p T③④拒取式 2． ? 證明 ① s P ② s?p P ③ p T① ②假言推理 ④ p?q P ⑤ q T③④假言推理 ? 證明 12 ① r P 附加前提引入 ② r?q P ③ q T①②假言推理 ④ p??q P ⑤ ?p T③④拒取式 ⑥ ?p?s P ⑦ s T⑤⑥假言推理 ⑧ r?s T①⑦ CP ? 證明 ① p P 否定結(jié)論引入 ② p?q P ③ q T①②假言推理 ④ q?r P ⑤ r T③④假言推理 ⑥ ?r?s P ⑦ ?r T⑥化簡 ⑧ r??r T⑤⑦合取 ? 證明 ① p P 附加前提引入 ② ?p?q P ③ q ①②析取三段論 ④ r??q P ⑤ ?r ③④拒取式 ⑥ p??r ①⑥ CP ? 證明 ① p P 附加前提引入 ② p?(q?r) P ③ q?r T①②假言推理 ④ q P 附加前提引入 ⑤ r T③④假言推理 ⑥ (r?s)?t P ⑦ ?r??s?t T⑥蘊涵等價式 ⑧ ?s?t T⑤⑦析取三段論 ⑨ ?h?(s??t) P ⑩ ?s?t ?h T⑨假言易位 ⒒ h T⑧⑩假言推理 ⒓ q?h T④⒒ CP 13. p?(q?h) T①⒓ CP 3． 解 推理不正確。 ?左邊 p?(q?r)??p?(?q?r)??p??q?r，而右邊 rqp ?? )( ??(p?q)?r ??p??q?r， 因此， )( rqp ?? ? rqp ?? )( 。 p?p?(q??q)? (p? q)?(p??q)。而左邊主合取范式 已是 ?p??q，因此， ?(p? q)??p??q， 證畢。 ? ( ( ) ( ) ) ( ( ) ( ) )p q r s p r q s? ? ? ? ? ? ? 11 ( ( ) ( ) ) ( )p q r s p r q s? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ( ) ( ) ) ( )p q r s p r q s? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) ( )p q r s p q r s p q r s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) ( )p q r s p q r s p q r s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) ( )p q r s p q r s p q r s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) ( )p q r s p q r s p q r s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) ( )p q r s p q r s p q r s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) ( )p q r s p q r s p q r s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) ( )p q r s p q r s p q r s? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( 0 , 1 , 3 , 4 , 5 , 6 , 7, 9 , 10 , 11 , 12 , 13 , 14 , 15 )? ? 故僅為可滿足式。 ? ?(p?(q?r))?((p?q)?(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)?(?q??r)?0。 表 224 p q r qp? rqp ?? )( 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 5． 解 ? (?p?q)?(?(?p??q))?(?p?q)?(p?q) ? q? (?p?q)?(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) 。 表 222 p q qp? qp? )( qp?? )()( qpqp ???? 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 其主析取范式 是： (?p?q)?(p??q)?(p?q)， 主合取范式為： p?q。 表 221 p q qp? )( qp?? 0 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 其主析取范式是： p??q， 主合取范式為： (p?q)?( p??q)?(?p??q)。 其主析取范式為 ? )15,13,12,11,10,9,8,7,5,4,3,1,0( 。 其主析取范式為 ?(2,4,5,6,7) ? (?p?q??r)?(p??q??r)?(p??q?r)?(p?q??r)?(p?q?r)。 故其主析取范式為 ?(0,1,2,3)=(?p??q)?(?p?q)?(p??q)?(p?q)。 其主析取范式為 ?3?p?q。 ? )( rqp ?? ? rqp ???? 即為其析取范式和合取范式。 ? rqp ??? )( 即為其合取范式。 ? )( rqp ??? ? )()( qrrqp ??????? 即為其合取范式。 習題 1． 解 ? )()( qpqp ?????? ； ? prprqp ???????? ))()((( 2． 解 ? )()( srqp ??? ? )()( srqp ?????? ? srqp ????? )( 即為其析取范式。事實上， ?p??(p?p)?p?p， p?q???(p?q)??(p?q)?(p?q)?(p?q)。 4． 證明 },{?? 是極小功能完備集，因而只需證明 },{?? 中的每個聯(lián)結(jié)詞都可以用 ? 表示，就說明 }{? 是功能完備集。 因此，含 { ???, }外其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含