1、聯(lián)結(jié)詞全功能集,福建師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,回顧,命題符號化 （符號） 聯(lián)結(jié)詞 （運算） 等值演算 （運算律與化簡） 用等值演算法證明公式類型 用等值演算法證明等值式 求解實際問題,例 應(yīng)用題,在某次研討會的中間休息時間，3名與會者根據(jù)王教授的口音對他是哪個省市的人進(jìn)行了判斷： 甲說王教授不是蘇州人，是上海人。 乙說王教授不是上海人，是蘇州人。 丙說王教授既不是上海人，也不是杭州人。 聽完以上3人的判斷后，王教授笑著說，他們3人中有一人說的全對，有一人說對了一半，另一人說的全不對。試用邏輯演算法分析王教授到底是哪里人？,設(shè)命題 p：王教授是蘇州人。 q：王教授是上海人。 r：王教授是杭州

2、人。 p,q,r中或者全假; 或者有一個真命題，兩個假命題。 甲說王教授不是蘇州人，是上海人 A=pq 乙說王教授不是上海人，是蘇州人 B=pq 丙說王教授既不是上海人，也不是杭州人 C=qr,解答,列真值表：,根據(jù)王教授說，他們3人中有一人說的全對，有一人說對了一半，另一人說的全不對。 可知：A，恰有一個為真，于是可得 的賦值只能是或。 如果是，則甲、乙都說對了一半，與已知不符；所以的賦值為。即王教授是上海人。,聯(lián)結(jié)詞全功能集,復(fù)合聯(lián)結(jié)詞 排斥或 與非式 或非式 真值函數(shù) 聯(lián)結(jié)詞全功能集,排斥或（異或,排斥或） 兩個命題公式P和Q的排斥或是一個新命題公式， 記作P Q。當(dāng)且僅當(dāng)P、Q真值不同

3、時， P Q 為T， 其他情況下的真值都是F。,異或聯(lián)結(jié)詞的性質(zhì)： （1）P Q （PQ）（PQ） （2）P Q (PQ） （3）P P0，0 P P，1 P P （4）P QQ P 交換律 （5）（P Q） R P （Q R） 結(jié)合律 （6）P（Q R）（PQ） （PR）分配律 （課后習(xí)題）,與非 設(shè)P和Q是兩個命題公式， P和Q的與非是一個新命題公式，記作P Q。當(dāng)且僅當(dāng)P和Q的真值都為 T時， P Q 為F ，其他情況下P Q的真值都是T 。（ 讀為“豎”） 根據(jù)此定義，可知 P Q （PQ）,全真為假 見假為真,或非 設(shè)P和Q是兩個命題公式， P和Q的或非是一個新命題公式，記作P Q。

4、當(dāng)且僅當(dāng)P和Q的真值都為 F 時， P Q 為T ，其他情況下P Q的真值都是F 。（ 讀成“箭”） 根據(jù)此定義，可知 P Q （P Q）,全假為真 見真為假,問題：多少個聯(lián)結(jié)詞最合適？,真值函數(shù),問題：含n個命題變項的所有公式共產(chǎn)生多少個互 不相同的真值表？ 答案為 個，為什么？ 定義 稱定義域為000, 001, , 111，值域 為0,1的函數(shù)是n元真值函數(shù)，定義域中的元素是 長為n的0,1串. 常用F:0,1n0,1 表示F是n元真值 函數(shù). 真值函數(shù)共有 個。 例如 F:0,120,1，且F(00)=F(01)=F(11)=0， F(10)=1，則F為一個確定的2元真值函數(shù).,命題公

5、式與真值函數(shù),對于任何一個含n個命題變項的命題公式A，都存在 惟一的一個n元真值函數(shù)F為A的真值表. 等值的公式對應(yīng)的真值函數(shù)相同. 下表給出所有2元真值函數(shù)對應(yīng)的真值表, 每一個含 2個命題變項的公式的真值表都可以在下表中找到. 例如：pq, pq, (pq)(pq)q) 等都對應(yīng) 表中的,2元真值函數(shù)對應(yīng)的真值表（書上表1-6）,聯(lián)結(jié)詞的全功能集,定義 在一個聯(lián)結(jié)詞的集合中，如果一個聯(lián)結(jié)詞可 由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余 的聯(lián)結(jié)詞，否則稱為獨立的聯(lián)結(jié)詞. 例如,在聯(lián)結(jié)詞集, , , , 中，由于 pqpq, 所以，為冗余的聯(lián)結(jié)詞; 類似地，也是冗余的 聯(lián)結(jié)詞. 又在, ,

6、中，由于pq(pq) 所以，是冗余的聯(lián)結(jié)詞，但, 無冗余的聯(lián)結(jié)詞. 類似地，也是冗余的聯(lián)結(jié)詞，但, 無冗余的聯(lián)結(jié)詞.,聯(lián)結(jié)詞的全功能集(續(xù)),定義 設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1) 元 真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表 示，則稱S是聯(lián)結(jié)詞全功能集.如果聯(lián)結(jié)詞全功能集 不含冗余的聯(lián)結(jié)詞，則稱為極小功能集. 說明： 若S是聯(lián)結(jié)詞全功能集，則任何命題公式都可用S 中的聯(lián)結(jié)詞表示. 若S1, S2是兩個聯(lián)結(jié)詞集合，且S1 S2. 若S1是全 功能集，則S2也是全功能集.,聯(lián)結(jié)詞的全功能集實例,(1) S1=, , , , （最常用） (2) S2=, , （布爾代數(shù)系統(tǒng)） (3) S3=, （極小） (4) S4=, （極?。?(5) S5= , （極?。?(6) S6= （極小、大規(guī)模集成電路） (7) S7= （極小、大規(guī)模集成電路）,例 如已知, 是全功能集，證明, 也是全功能集 證： 因為, 是全功能集，任意一個真值函數(shù)可以用 , 聯(lián)結(jié)詞的命題公式表示。 對于任意的命題公式，A B A B,因此任意一個真值函數(shù)可以用, 聯(lián)結(jié)詞的命題公式表示。 例 p (p