【正文】 ??? ))()(( pqpqp ???????? ))(( pqp ????? )( qp??? qp ???? ? rqp ?? )( ))(( rqp ???? ))(( rqp ????? rqp ???? 3． 證明 因?yàn)椋?{ ????? , }是功能完備聯(lián)結(jié)詞集，所以， 含有 { ????? , }外的其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含 { ????? , }中的聯(lián)結(jié)詞的公式。 又 因?yàn)?qpqp ???? )()()()( pqqppqqpqp ??????????? 8 即含有 ??, 的公式均可以轉(zhuǎn)換為僅含 { ???, }中的聯(lián)結(jié)詞的公式。 因此，含 { ???, }外其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含 { ???, }中的聯(lián)結(jié)詞的公式。 故 { ???, }是功能完備聯(lián)結(jié)詞集。 4． 證明 },{?? 是極小功能完備集，因而只需證明 },{?? 中的每個(gè)聯(lián)結(jié)詞都可以用 ? 表示，就說明 }{? 是功能完備集。只有一個(gè)聯(lián)結(jié)詞，自然是極小功能完備集。事實(shí)上， ?p??(p?p)?p?p， p?q???(p?q)??(p?q)?(p?q)?(p?q)。 對(duì)于證明 }{? 是極小功能完備集，可類似證明。 習(xí)題 1． 解 ? )()( qpqp ?????? ； ? prprqp ???????? ))()((( 2． 解 ? )()( srqp ??? ? )()( srqp ?????? ? srqp ????? )( 即為其析取范式。 )()( srqp ??? ? srqp ????? )( ? )()( srqsrp ???????? 即為其合取范式。 ? )( rqp ??? ? )()( qrrqp ??????? 即為其合取范式。 ?p?(q?r)??p?((q?r)?(?q??r)) ?(?p?q?r)?(?p??q??r) 即為其析取范式。 ? rqp ??? )( 即為其合取范式。 rqp ??? )( ? )()( rqrp ????? 為其析取范式。 ? )( rqp ?? ? rqp ???? 即為其析取范式和合取范式。 3． 解 ? )( qpp ??? )())(( qpqqp ??????? ?????????? )2,1,0()()()( qpqpqp 即為其主合取范式。 其主析取范式為 ?3?p?q。 ? )()( qpqp ?????? 1)()( ?????? qpqp 。 故其主析取范式為 ?(0,1,2,3)=(?p??q)?(?p?q)?(p??q)?(p?q)。 ? prqp ??? ))(( prqp ?????? ))(( prqp ????? ))(( )()( rpqp ????? 9 ))()(())()(( qqrprrqp ??????????? )()()()( rqprqprqprqp ???????????????? ?? )3,1,0( 即為其主合取范式。 其主析取范式為 ?(2,4,5,6,7) ? (?p?q??r)?(p??q??r)?(p??q?r)?(p?q??r)?(p?q?r)。 ? )()( srqp ??? )()( srqp ??????? )()()()( srqsrpsrqp ??????????????? )()()()( srqpsrqpsrqpsrqp ?????????????????????????? )14,6,2( 即為其主合取范式。 其主析取范式為 ? )15,13,12,11,10,9,8,7,5,4,3,1,0( 。 4． 解 ?真值表如表 221 所示 , 所以其極小項(xiàng)是 p??q，極大項(xiàng)為 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)。 ?真值表如表 2222 所示 , 所以其極小項(xiàng)是 ?p?q, p??q, p?q, 極大項(xiàng)為 p?q。 表 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。 ?真值表如表 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。 其主析取范式 是： (?p?q?r)?(p??q??r)?(p??q?r) ?(p?q??r)?(p?q?r)， 主合取范式為： (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)。 表 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)， 故 ? 為可滿足式。 ? )())()(( 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 )? ? 故?為重言式。 ? ?(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。 故?為矛盾式。 ? ( ( ) ( ) ) ( ( ) ( ) )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 )? ? 故僅為可滿足式。 6． 證明 ?右邊已經(jīng)是 主合取范式。而左邊主合取范式 已是 ?p??q，因此， ?(p? q)??p??q， 證畢。 ? 右邊 (p? q)?(p??q)已經(jīng)是 主合取范式。 p?p?(q??q)? (p? q)?(p??q)。 因此，)()( qpqpp ????? 。 ?左邊 p?(q?r)??p?(?q?r)??p??q?r，而右邊 rqp ?? )( ??(p?q)?r ??p??q?r， 因此， )( rqp ?? ? rqp ?? )( 。 習(xí)題 1． 解 設(shè) p：這里有演出； q：這里通行是困難的； r：他們按照指定時(shí)間到達(dá)。 前提： 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