離散數(shù)學(xué)(第1.4)陳瑜

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

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

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

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

P↑Q～（P∧Q）;

P↓Q～（P∨Q）

PQP↑Q1101010110012/2/20236計算機科學(xué)與工程學(xué)院§1.4聯(lián)結(jié)詞的完備集根據(jù)聯(lián)結(jié)詞↑和↓的定義，不難證明下面的等價式:①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計算機科學(xué)與工程學(xué)院§1.4聯(lián)結(jié)詞的完備集根據(jù)聯(lián)結(jié)詞↑和↓的定義，不難證明下面的等價式:①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這些等價式告訴我們，↑可由∧和～表示出來，↓可由∨和～表示出來，反過來，↑和↓都可以單獨表示出所有已知聯(lián)結(jié)詞，他們的這一性能使得在邏輯電路設(shè)計中只用一種門式電路元件就能實現(xiàn)任何電路功能，當(dāng)然，元件的數(shù)量通常也顯得更多。

2/2/20238計算機科學(xué)與工程學(xué)院§1.4聯(lián)結(jié)詞的完備集條件否定:

二元聯(lián)結(jié)詞“c”,稱為條件否定聯(lián)結(jié)詞，可以用下面的真值表定義：

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

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

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

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