【正文】 18。 Q217。P218。Q218。R ，對(duì)n個(gè)命題原子P1，…，Pn，極小項(xiàng)有如下性質(zhì)：（1）n個(gè)命題原子P1，…，Pn有個(gè)不同的解釋?zhuān)總€(gè)解釋對(duì)應(yīng)P1，…，Pn的一個(gè)極小項(xiàng)。（3）任意兩個(gè)不同的極小項(xiàng)的合取式恒假：mi217。（4）所有極小項(xiàng)的析取式恒真：=1。（2）對(duì)P1，…，Pn的任意一個(gè)極大項(xiàng)M，有且只有一個(gè)解釋使M取0值，若使極大項(xiàng)取0的解釋對(duì)應(yīng)的二進(jìn)制數(shù)為i，則M記為Mi，于是關(guān)于P1，…，Pn的全部極大項(xiàng)為M0，M1，…。 Mj=1，i≠j。2. 主合取范式與主析取范式之間的關(guān)系由極小項(xiàng)和極大項(xiàng)的定義可知，二者有如下關(guān)系：mi=216。mi 由此可知，若P218。R為一公式G的主合取范式，則G =216。G =216。 M0 = 216。 M2217。 M6) = 216。216。…218。M6 = m1218?！?18。若（216。 Q）218。 P217。 Q）218。 Q）為一公式H的主析取范式，則H=216。H =216。(（216。 Q）218。 P217。 Q）218。 Q）) =216。（m0218。 m3））= 216。P218。一般地，若公式A中含n個(gè)命題原子，且A的主析取范式中含有k個(gè)極小項(xiàng)：，則216。A=。216。（） = =。（2）求出與（1）中極小項(xiàng)下標(biāo)相同的極大項(xiàng)。類(lèi)似地，從一公式A的主合取范式求其主析取范式的步驟為：（1）求出A的主合取范式中沒(méi)有包含的所有極大項(xiàng)。（3）將（2）求出的所有極小項(xiàng)析取起來(lái)，即得A的主析取范式。主析取范式恰好是使得公式為真的解釋所對(duì)應(yīng)的極小項(xiàng)的析取組成，主合取范式恰好是使得公式為假的解釋所對(duì)應(yīng)的極大項(xiàng)的合取組成。設(shè)命題公式G中所有不同原子為P1，…，Pn，則G的主析取范式的求法如下：(a) 將公式G化為析取范式。(c) 用等冪律將短語(yǔ)中重復(fù)出現(xiàn)的同一文字化簡(jiǎn)為一次出現(xiàn)，如，P217。(d) 對(duì)于所有不是關(guān)于P1，…，Pn的極小項(xiàng)的短語(yǔ)使用同一律，補(bǔ)進(jìn)短語(yǔ)中未出現(xiàn)的所有命題原子，并使用分配律展開(kāi)，即，如果短語(yǔ)Gi’不是關(guān)于P1，…，Pn的極小項(xiàng)，則Gi’中必然缺少原子，不妨設(shè)為P j1，…，Pjk，于是 Gi’= Gi’217。216?！?17。216。將相同的短語(yǔ)的多次出現(xiàn)化為一次出現(xiàn)，就得到了給定公式的主析取范式。由上面討論可知，只要求出一種范式，可立即得到另外一種范式。解：（1）使用真值表法。 P217。 Q217。R) 218。 P217。 Q217。 (216。Q217。R) 218。 P217。R) 218。216。216。 (P217。 Q217。 (P217。R) = m0218。 m2 218。 m4218。 m7根據(jù)真值表中使得公式為假的解釋?zhuān)鶎?duì)應(yīng)的極大項(xiàng)的合取即為其主合取范式：G= 216。 216。 R= M6（2）公式推導(dǎo)法G= P→(Q→R) =216。 216。 R=（216。（Q218。 Q）217。 216。（216。（P218。 P）217。 216。（R217。 216。（Q218。Q）） = (216。216。216。 (216。216。R) 218。 P217。216。(216。Q217。 (P217。 Q217。R) 218。Q217。 m1218。 m3218。 m5218。 P218。 Q 218。（2）證明等價(jià)式成立。 判斷P→(Q→R)與（P218。證明： 我們利用求主合取范式的方法來(lái)判斷。下面求（P218。 （P218。（P218。 R =（216。216。R =（216。R）217。Q218。 P218。216。R）217。216。216。R） =（216。Q218。（216。216。R） 217。216。R） = M2 217。 M6二者的主合取范式不相同，因此，這兩個(gè)公式不等價(jià)。（2）給出一個(gè)新的聯(lián)結(jié)詞的定義，要求證明其是全功能集，并用其表示某個(gè)命題公式。217。218?！鷠，{173。}都是全功能聯(lián)結(jié)詞集合，因此，若要證明新定義的聯(lián)結(jié)詞是全功能集，只需證明上面某個(gè)全功能集合（比如{216。}）中的每個(gè)聯(lián)結(jié)詞（如，216。）都可以用新聯(lián)結(jié)詞表示。217。）用給定的新聯(lián)結(jié)詞表示，然后按要求把原命題公式轉(zhuǎn)化成用新聯(lián)結(jié)詞表示的形式。一般用歸納法，證明在有限步內(nèi)，用這個(gè)聯(lián)結(jié)詞結(jié)合不可能表示所有的命題。但是，一般情況下，為了不至于因?yàn)槁?lián)結(jié)詞的減少而使得公式的形式變得復(fù)雜，我們?nèi)猿２捎谩?16。218。”這5個(gè)聯(lián)結(jié)詞。216。（216。Q）用僅含聯(lián)結(jié)詞216。的公式等價(jià)表示。216。（216。Q）=（216。（Q218。R））217。P217。P217。P217。（（Q218。R）217。P217。P217。（Q217。P217。（216。（216。Q）） =（216。Q）218。P217。（（216。Q）217。R） =216。Q =216。216。e1e2e3f(e1,e2,e3)00010011010001101001101111011110 三元聯(lián)結(jié)詞f(e1,e2,e3)的真值表（1）試證明{ f}是完備的，即，聯(lián)結(jié)詞集合{216。}或{216。}可由該聯(lián)結(jié)詞表示。Q。P=f(P,P,P)， P218。P, 216。Q)，所以聯(lián)結(jié)詞集合{216。}可由該三元聯(lián)結(jié)詞f表示。218。（2）解：因?yàn)镻218。P, 216。Q)，所以P→ Q=216。Q=f(P, P, 216。Q=216。P218。Q)= 216。Q218。P)=216。 f(Q, Q, P).因此 （P→R）217。R) 217。f(Q, Q, f(P, P, 216。f(Q, Q, f(P, P, f(R,R,R)))=f(f(Q, Q, f(P, P, f(R,R,R))), f(Q, Q, f(P, P, f(R,R,R))), f(Q, Q, f(P, P, f(R,R,R))))?！鷠是否是聯(lián)結(jié)詞的全功能集合？證明你的結(jié)論?？紤]217。和→時(shí)，則當(dāng)公式中出現(xiàn)的所有命題原子都取真值1時(shí)，公式也必然取真值1。和→的公式不能表示所有的命題公式，比如恒假式：A217。A。→}不是全功能集?！鷠不是聯(lián)結(jié)詞的全功能集。和→時(shí)，則當(dāng)公式中出現(xiàn)的所有命題原子都取真值1時(shí)，公式也必然取真值1。假設(shè)n≤k時(shí)，命題成立，即，如果一個(gè)公式中含有n個(gè)聯(lián)結(jié)詞217。當(dāng)n=k+1時(shí)，設(shè)任一含k+1個(gè)聯(lián)結(jié)詞的公式為A，則存在公式B和C，使得：A=B→C或A=B217。由歸納假設(shè)知，當(dāng)所有原子取真值1時(shí)，B和C在該解釋下的真值均為1，因此，A在該解釋下的真值亦為1。由該結(jié)論知，如果一個(gè)命題公式中只含有聯(lián)結(jié)詞217。因此，只含有聯(lián)結(jié)詞217。所以，{217。 綜合應(yīng)用題 綜合題主要是先符號(hào)化，再使用上面的知識(shí)進(jìn)行聯(lián)結(jié)詞的轉(zhuǎn)化、或求主合取范式、主析取范式、利用基本等價(jià)式化簡(jiǎn)、或進(jìn)行邏輯推理來(lái)論證或做邏輯判斷等。在同一時(shí)間內(nèi)只能有一個(gè)信號(hào)通過(guò)。例如，A，B，C同時(shí)輸入時(shí)，只能A有輸出。}中的表達(dá)式。然后根據(jù)已知條件，寫(xiě)出FA, FB, 。216。216。 (P217。 Q217。 (P217。216。(P217。R) =（（P217。 Q）217。R218。（（P217。（216。 R）） =（P217。 Q）218。Q） = P217。Q218。216。P) =216。P) =216。P)218。P)) =(P175。 (P175。P217。216。 (216。Q217。P217。（216。 R） =216。 Q =216。(216。 Q) =216。216。216。(Q175。P217。Q217。( P218。216。Q)175。R) =(216。( P218。 (216。 (P175。(216。 Q) 175。 Q)) 175。 R) 一一個(gè)公安人員審查一件盜竊案，已知的事實(shí)如下：（1） A或B盜竊了x（2） 若A盜竊了x，則作案時(shí)間不能發(fā)生在午夜前（3） 若B證詞正確，則在午夜時(shí)屋里燈光未滅（4） 若B證詞不正確，則作案時(shí)間發(fā)生在午夜前（5） 午夜時(shí)屋里燈光滅了（6） A并不富裕試用演繹法找出盜竊犯。 一甲、乙、丙、丁四個(gè)人有且僅有兩個(gè)人參加圍棋優(yōu)勝比賽。請(qǐng)推斷出哪兩個(gè)人參加了圍棋比賽。P217。 (P217。Q)（2）R→S（3）216。S）（4）216。P將（1）（4）式合取起來(lái)有：（(216。 Q) 218。216。（R→S）217。（Q217。（216。P）=（(216。 Q) 218。216。（216。S）217。Q218。S)217。216。216。 216。 S) 218。216。 S) 218。P217。 216。 216。P217。 216。 216。216。 216。 S) 218。216。 S)為真，即甲和丁參加了比賽。 第二章習(xí)題解答 1. 設(shè)P是命題“天下雪”；Q是命題“我上街”；R是命題“我有時(shí)間”。b． 我去上街，僅當(dāng)我有時(shí)間。d． 天正在下雪，我也沒(méi)去上街。P217。Q；b可表示為：Q174。P；d可表示為：P217。Q。 a．Q171。216。Q c．（Q174。（R174。（R218。2. 說(shuō)出下述每一命題的逆命題和逆否命題：（1） 如果天下雨，我將不去。（3） 如果n是大于2的正整數(shù)，則方程xn+yn=zn無(wú)正整數(shù)解。解： （1）逆命題為：如果我不去，那么天下雨；逆否命題為：如果我去，那么天不下雨。（3）逆命題為：如果方程xn+yn=zn無(wú)正整數(shù)解，則n是大于2的正整數(shù)；逆否命題為：如果方程xn+yn=zn有正整數(shù)解，則n是不大于2的正整數(shù)。逆否命題：如果我完成了任務(wù)，則我獲得了更多幫助。(Q217。216。Q)217。S))b) (216。Q)218。R)218。P217。216。S)c) (216。Q)218。R)218。216。(R218。S))d) (P218。(R217。P)))171。216。(Q217。216。Q)217。S)) 則：TI(G) = (1217。0))218。((1218。(0218。216。(P217。216。(((216。Q)218。R)217。(1217。216。(((216。1)218。0)217。0=1c) 令G =(216。Q)218。R)218。216。(R218。S)) =(216。Q)218。R)218。 ( (216。216。(P 218。(R218。S)) =(216。216。216。( (Q217。 (216。216。(R218。S))則：TI (G) =(216。216。216。( (1217。 (216。216。(0218。0)) = 1218。(Q174。216。(Q218。S) =(P218。(R217。P)))171。216。(216。(R217。P)))171。216。 (P218。Q218。216。 (Q218。S)) 21