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

2011-10-21 05:08:10王玉紅

赤峰學(xué)院學(xué)報·自然科學(xué)版 2011年2期

王玉紅

（赤峰學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，內(nèi)蒙古赤峰 024000）

王玉紅

（赤峰學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，內(nèi)蒙古赤峰 024000）

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

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

1 命題邏輯

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

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

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

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

1.2 命題公式

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

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

1.3 命題公式的主析取范式

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

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

2 數(shù)字電路

2.1 門電路

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

2.2 電路設(shè)計(jì)中存在的問題

在電路設(shè)計(jì)中存在的主要問題是門電路延遲和電路太復(fù)雜.

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

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

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

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

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

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