版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
陳瑜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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 事故處理的協(xié)議書
- 二手房購房協(xié)議書范例
- 重金屬中毒性腎病病因介紹
- 幼兒園食堂食品衛(wèi)生安全培訓(xùn)課件
- 《計算機文化基礎(chǔ) 》課件-第7章
- (參考資料)罐頭生產(chǎn)線環(huán)評報告表
- 工程材料概述-李子42課件講解
- 2023年天津市市區(qū)重點中學(xué)高考語文一模試卷
- 保潔保綠員例行培訓(xùn)課件
- 《軟體工程課程聯(lián)盟》課件
- GB 29216-2012食品安全國家標(biāo)準(zhǔn)食品添加劑丙二醇
- 齊魯工業(yè)大學(xué)信息管理學(xué)成考復(fù)習(xí)資料
- 公務(wù)員面試-自我認知與職位匹配課件
- 中頻電治療儀操作培訓(xùn)課件
- 柔弱的人課文課件
- 動物寄生蟲病學(xué)課件
- 電梯曳引系統(tǒng)設(shè)計-畢業(yè)設(shè)計
- 三度房室傳導(dǎo)阻滯護理查房課件
- 講課比賽精品PPT-全概率公式貝葉斯公式-概率論與數(shù)理統(tǒng)計
- 藥理學(xué)39人工合成抗菌藥課件
- 班會課件 勿以惡小而為之勿以善小而不為
評論
0/150
提交評論