陳瑜Email：chenyu.inbox@g2/2/2023離散數學計算機學院2/2/20231計算機科學與工程學院主要內容掌握3個新的聯結詞掌握：功能完備集、最小功能完備集等概念2/2/20232計算機科學與工程學院§1.4聯結詞的完備集前面我們已經介紹了最常見的6種邏輯聯結詞。他們都和自然語言中使用的關聯詞緊密相關，易于理解。不同聯結詞產生的真值表是互不相同的。根據對含兩個命題變元的公式的解釋方式看，共有2*2=4種不同的選擇性，因而公式的真值表相應有24=16種可能結果。對其中每一種真值表都應該存在相應的聯結詞。下面從真值表取值情況的角度定義幾個新的聯結詞。2/2/20233計算機科學與工程學院§1.4聯結詞的完備集定義1-4.1：設P和Q是命題公式，分別稱P↑Q和P↓Q為“與非”和“或非”命題公式。其相應的真值表如下所示：

PQP↑Q1101010110012/2/20234計算機科學與工程學院§1.4聯結詞的完備集定義1-4.1：設P和Q是命題公式，分別稱P↑Q和P↓Q為“與非”和“或非”命題公式。其相應的真值表如下所示：

PQP↓Q1101000100012/2/20235計算機科學與工程學院§1.4聯結詞的完備集定義1-4.1：設P和Q是命題公式，分別稱P↑Q和P↓Q為“與非”和“或非”命題公式。其相應的真值表如下所示：

PQP↓Q110100010001由真值表可以看出:

P↑Q～（P∧Q）;

P↓Q～（P∨Q）

PQP↑Q1101010110012/2/20236計算機科學與工程學院§1.4聯結詞的完備集根據聯結詞↑和↓的定義，不難證明下面的等價式:①P↑P～（P∧P）～P②(P↑Q)↑(P↑Q)～(P↑Q)P∧Q③(P↑P)↑(Q↑Q)～P↑～Q～（～P∧～Q）

P∨Q④P↓P～（P∨P）～P⑤(P↓Q)↓(P↓Q)～(P↓Q)P∨Q⑥(P↓P)↓(Q↓Q)～P↓～Q～（～P∨～Q）

P∧Q2/2/20237計算機科學與工程學院§1.4聯結詞的完備集根據聯結詞↑和↓的定義，不難證明下面的等價式:①P↑P～（P∧P）～P②(P↑Q)↑(P↑Q)～(P↑Q)P∧Q③(P↑P)↑(Q↑Q)～P↑～Q～（～P∧～Q）

P∨Q④P↓P～（P∨P）～P⑤(P↓Q)↓(P↓Q)～(P↓Q)P∨Q⑥(P↓P)↓(Q↓Q)～P↓～Q～（～P∨～Q）

P∧Q這些等價式告訴我們，↑可由∧和～表示出來，↓可由∨和～表示出來，反過來，↑和↓都可以單獨表示出所有已知聯結詞，他們的這一性能使得在邏輯電路設計中只用一種門式電路元件就能實現任何電路功能，當然，元件的數量通常也顯得更多。

2/2/20238計算機科學與工程學院§1.4聯結詞的完備集條件否定:

二元聯結詞“c”,稱為條件否定聯結詞，可以用下面的真值表定義：

PQPcQ000010101110顯然，“c”是條件聯結詞“→”的否定形式，即：PcQ～(P→Q)2/2/20239計算機科學與工程學院§1.4聯結詞的完備集至此我們定義了9個聯結詞，其中1個一元聯結詞，8個二元聯結詞。那么，還能不能定義出新的聯結詞呢？讓我們來看看含兩個命題變元的所有公式所能取得的情況。2/2/202310計算機科學與工程學院§1.4聯結詞的完備集PQ12345678910111213141516111001001011101110000001101101100110001010101101010101001001110010111000包含2個命題變元的所有公式可能的取值情況：永真式矛盾式2/2/202311計算機科學與工程學院§1.4聯結詞的完備集PQ12345678910111213141516111001001011101110000001101101100110001010101101010101001001110010111000包含2個命題變元的所有公式可能的取值情況：永真式矛盾式……P∧Q2/2/202312計算機科學與工程學院§1.4聯結詞的完備集PQ12345678910111213141516111001001011101110000001101101100110001010101101010101001001110010111000包含2個命題變元的所有公式可能的取值情況：永真式矛盾式……P∧Q可見，已定義的9個聯結詞就是全部可以定義的聯結詞。

2/2/202313計算機科學與工程學院§1.4聯結詞的完備集這9個聯結詞之間還有著內在的聯系。例如:→可用～和∨表達，可用～,∨和∧表示,可用～、∨和∧表達,↑可用∧和～表達,↓可用～和∨表達,c可用～和∧表達。這就是說，全部9個聯結詞都可以用～，∨和∧這三個聯結詞表達出來，即{～，∨，∧}構成了邏輯聯結詞的一個功能完備集。此外，根據↑和↓滿足的恒等式來看,↑或↓都能單獨表達～,∨和∧,從而{↑}和{↓}也是功能完備集。2/2/202314計算機科學與工程學院§1.4聯結詞的完備集定義1-4.2設S是由某些聯結詞構成的集合，如果每個邏輯聯結詞的功能都能夠由S中的聯結詞實現，則稱S是聯結詞的一個功能完備集；進一步，如果去掉S中的任何一個聯結詞后，至少有一個聯結詞的功能不能由S中剩余的聯結詞實現時，則稱S是邏輯聯結詞的一個最小功能完備集。少一個也不成2/2/202315計算機科學與工程學院§1.4聯結詞的完備集根據定義,我們知道{↑}、{↓}是最小的功能完備集。那么{～，∨，∧}是不是最小功能完備集？由于P∨Q～(～P∧～Q)，可見∨可由{～，∧}表達；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表達，這說明{～，∨，∧}不是最小功能完備集。對于{～，∨}和{～，∧}，是否還可以去掉其中的聯結詞？答案是否定的。因為根據“～”的功能,其真值表含2個1和2個0，∨對應的真值表含3個1和1個0，∧對應的真值表含1個1和3個0。所以，既不能代替∧也不能代替∨，同樣∧和∨都不能代替～。因此，{～，∧}和{～，∨}都是最小功能完備集。2/2/202316計算機科學與工程學院§1.4聯結詞的完備集根據定義,我們知道{↑}、{↓}是最小的功能完備集。那么{～，∨，∧}是不是最小功能完備集？由于P∨Q～(～P∧～Q)，可見∨可由{～，∧}表達；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表達，這說明{～，∨，∧}不是最小功能完備集。對于{～，∨}和{～，∧}，是否還可以去掉其中的聯結詞？答案是否定的。因為根據“～”的功能,其真值表含2個1和2個0，∨對應的真值表含3個1和1個0，∧對應的真值表含1個1和3個0。所以，既不能代替∧也不能代替∨，同樣∧和∨都不能代替～。因此，{～，∧}和{～，∨}都是最小功能完備集。

2/2/202317計算機科學與工程學院§1.4聯結詞的完備集根據定義,我們知道{↑}、{↓}是最小的功能完備集。那么{～，∨，∧}是不是最小功能完備集？由于P∨Q～(～P∧～Q)，可見∨可由{～，∧}表達；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表達，這說明{～，∨，∧}不是最小功能完備集。對于{～，∨}和{～，∧}，是否還可以去掉其中的聯結詞？

答案是否定的。因為根據“～”的功能,其真值表含2個1和2個0，∨對應的真值表含3個1和1個0，∧對應的真值表含1個1和3個0。所以，既不能代替∧也不能代替∨，同樣∧和∨都不能代替～。因此，{～，∧}和{～，∨}都是最小功能完備集。2/2/202318計算機科學與工程學院§1