王玉紅

（赤峰學院 計算機科學與技術系，內(nèi)蒙古 赤峰 024000）

數(shù)理邏輯與數(shù)字電路設計優(yōu)化

王玉紅

（赤峰學院 計算機科學與技術系，內(nèi)蒙古 赤峰 024000）

數(shù)理邏輯就是精確化、數(shù)學化的形式邏輯.它是現(xiàn)代計算機技術的基礎.數(shù)理邏輯包括兩個最基本的組成部分，就是“命題邏輯”和“一階謂詞邏輯”.其中命題邏輯又被稱為二值邏輯，它的運算特點同電路設計中的開與關、高電位與低電位等現(xiàn)象完全一樣，都只有“0”、“1”兩種不同的狀態(tài)，因此，它在電路設計分析中有著廣泛而重要的應用.

命題；命題公式；主合取范式；門電路；門延遲時間

1 命題邏輯

1.1 命題及命題聯(lián)結詞

命題是命題邏輯的基本概念.能唯一辨別真假的陳述句被稱作命題.

命題有唯一的真值“0”（假）或“1”（真）.在自然語言系統(tǒng)中，陳述句的標志是句號“.”，但并非所有的以句號結尾的句子都是命題.有兩種情況必須考慮到，第一種情況是一些不確定性的句子，如陳述句“x+5>8.”，是不能判斷詞句的正確與否；第二種情況是悖論，如著名的羅素悖論、理發(fā)師悖論和說謊者悖論等.在判斷一個語句是否是命題時，一般有兩個依據(jù)，首先看此句子是否是陳述句，其次是最關鍵的是否能唯一的給出此句子的真假值，有的陳述句雖然現(xiàn)在不能給出真假值，但將來能給出唯一的真假值的，也是命題.如“明年的今天是晴天.”，其真值到了明年是真是假二者必居其一.

在自然語言中，一個陳述句除了句尾有一個標點符號“句號”外，可能還包含多個分隔符“逗號”，由它們共同來表達一個完整的含義；而有的陳述句中可能含有一個或多個“連詞”，按照句子本來要表達的含義，也可以將一個陳述句分割成幾個子句.所以命題又可以分成原子命題和復合命題.原子命題又被稱為簡單命題，是不能再次分割的陳述句，它是命令邏輯最基本的單位，通常用單個的英文字母表示.如“p,q,r,s,…”，稱為命題符號化.復合命題由原子命題和命題聯(lián)結詞共同組成，基本的命題聯(lián)結詞有五個，分別是否定詞“┒”、合取詞“Λ”、析取詞“ⅴ”、蘊涵詞“→”以及等價詞“圮”.另外還有邏輯設計中常用的聯(lián)結詞異或詞“與非詞“↑”和或非詞“↓”.通過這些豐富的命題聯(lián)結詞，可以將任何命題進行符號化.

1.2 命題公式

命題公式也叫合式公式，簡稱為公式，常用大寫的英文字母表示，如“A,B,C,…”.一個公式中一般含有命題常項、命題變項、命題聯(lián)結詞、括號等組成.命題公式是有真值的，但命題公式的真值取決于公式中命題變項的值，若給公式中各個變項指定一組真值，就對應公式的一個指派.對含有n個命題變項的公式進行賦值，共有“2n”組不同的指派，可以形成一張表格，稱為此公式的真值表.

若有兩個公式A和B的真值表相同，我們稱這兩個公式是等值的，記作“A圳B”.在實際判斷中記住一些常見的等值式，用等值演算的方法判斷兩個公式是否等值.在進行等值演算時總可以得到一系列的等值式，也即說明了一個公式有無窮的等值式.所以就需要一個形式規(guī)范的、結構統(tǒng)一的公式，使得彼此等值的公式中的每一個公式都與之等值，這就是命題公式的的主范式.

1.3 命題公式的主析取范式

命題公式的主范式包括主析取范式和主合取范式.主析取范式是極小項的析取式，含有n個命題變項的極小項是這樣的簡單合取式：每個命題變項與其否定二者之一必按字典順序出現(xiàn)且僅出現(xiàn)一次，而且公式中只能出現(xiàn)的命題聯(lián)結詞是合取詞.n個命題變項可形成2n個極小項,規(guī)定將命題變項看成1，其否定看成是0，每個極小項對應的二進制就是成真賦值，對應的十進制記作極小項m的下標.主合取方式是極大項的合取式，極大項的定義類似于極小項，只不過允許出現(xiàn)的命題聯(lián)結詞是析取詞.

命題公式的主析取范式的求解常用真值表法.即列出命題公式的真值表，找出其中的極小項，則此命題公式的主析取范式就是這些極小項的析取.

2 數(shù)字電路

2.1 門電路

眾所周知，所有數(shù)字電路的基礎是門電路，基本的門電路包括：非門（反向門）、與門和或門，并由它們組成與非門、或非門和異或門等復合門電路.假設門電路的兩個輸入信號是p和q，對應的邏輯符號分別是

2.2 電路設計中存在的問題

在電路設計中存在的主要問題是門電路延遲和電路太復雜.

一般來說，由門電路組成的數(shù)字電路，從信號建立到通過一級門電路，總會有一段時間的延遲.把經(jīng)過一個反向門、與門和或門的延遲時間稱作一級標準門延遲，一個組合電路的延遲時間是信號從輸入端到輸出端所經(jīng)過的各級門電路延遲時間之和.很顯然，這個延遲時間越短越好，換句話說就是用等價的、延遲時間短的數(shù)字電路代替延遲時間長的組合電路.

考慮到實際情況，在完成相同功能的前提下，設計的電路越簡單越好.這就要求在設計電路時使用的門電路個數(shù)越少越好.

3 利用命題公式優(yōu)化數(shù)字電路設計

從上面的敘述可知，命題公式聯(lián)結詞的否定詞、合取詞和析取詞，恰好對應三個基本的門電路：反向門、與門和或門.要解決電路設計中的問題，就可以利用命題公式的等值公式，從而找到符合要求的電路設計.首先根據(jù)要求列出幾個輸入信號的真值表，并把它們看做是命題變項；然后從真值表中得到組合數(shù)字電路公式的主析取范式；最后對主析取范式進行等值演算，直到得到延遲時間最小的等價電路或是復雜度小的電路.

例 設計一個由三方參與的投票器.要求是如果有兩個或兩個以上的投票人投出贊成票時，決議通過，用“1”來表示；否則決議不能通過，用“0”來表示.

這里我們假設最后投票結果用F表示，投票的三方分別是 p、q、r，且“0”表示投反對票，“1”表示投贊成票.則可以得到如下的投票結果F關于三方p、q、r的真值表.如表 1所示.

表1 投票器F的真值表

圖1 三方投票器的電路圖a

從表1得到投票結果F的主析取范式：

很顯然，從公式F的等值演算過程可以看出，如果直接用F的主析取范式對應的電路實現(xiàn)，有三級電路延遲（如圖1所示）；而用等值演算后的電路，電路延遲減少為二級（如圖2所示）.

圖2 三方投票器的電路圖b

對于任何復雜的組合邏輯電路，都可以利用命題公式和各種邏輯元件所共有的二值特性，將其轉(zhuǎn)換為命題邏輯問題，通過命題公式的等值變換，得到最優(yōu)化的數(shù)字邏輯電路.因此，此理論是在自動控制方面有重要的應用.

〔1〕耿素云，屈婉玲，張立昂.離散數(shù)學（第四版）.清華大學出版社，2008.

〔2〕馬叔良.離散數(shù)學（第三版）.電子工業(yè)出版社，2009.

〔3〕邵學才.離散數(shù)學.清華大學出版社，2001.

〔4〕李盤林，李麗雙，李洋，王春立.離散數(shù)學.高等教育出版社，1999.

〔5〕王成華，王友仁，胡志忠.電子線路基礎.清華大學出版社，2008.

〔6〕高衛(wèi)斌.電子線路（第3版）.電子工業(yè)出版社，2009.

〔7〕梁明理.電子線路（第五版）.高等教育出版社，2008.

TN79

A

1673-260X（2011）02-0066-02