列表化簡邏輯函數(shù)技術(shù)

1、概述

在設(shè)計(jì)邏輯電路圖時(shí)，由真值表直接得到的函數(shù)往往比較復(fù)雜。代數(shù)法和卡諾圖法等方法對于變量數(shù)目較多的邏輯函數(shù)則效果不佳，本文介紹一種可以化簡復(fù)雜邏輯函數(shù)的方法──表格法，該方法可以對變量數(shù)目較多的邏輯函數(shù)也可以進(jìn)行化簡。

2、原理

在介紹化減法之前，先說明三個(gè)概念：

蘊(yùn)涵項(xiàng)──在函數(shù)的任何積之和式中，每個(gè)乘積項(xiàng)稱為該函數(shù)的蘊(yùn)涵項(xiàng)。對應(yīng)于卡諾圖中的任一標(biāo)1單元(最小項(xiàng))以及2m個(gè)相鄰單元所形成的圈都是函數(shù)的蘊(yùn)涵項(xiàng)。

素項(xiàng)──若函數(shù)的一個(gè)蘊(yùn)涵項(xiàng)不是該函數(shù)中其它蘊(yùn)涵項(xiàng)的一個(gè)子集，則此蘊(yùn)涵項(xiàng)稱為素蘊(yùn)涵項(xiàng)，簡稱素項(xiàng)。

實(shí)質(zhì)素項(xiàng)──若函數(shù)的一個(gè)素項(xiàng)所包含的某一最小項(xiàng)，不包括在該函數(shù)的其它任何素項(xiàng)中則此素項(xiàng)稱為實(shí)質(zhì)素蘊(yùn)涵項(xiàng)，簡稱實(shí)質(zhì)素項(xiàng)。

列表化簡法的基本原理是利用邏輯函數(shù)的最小項(xiàng)，通過對相鄰最小項(xiàng)的合并，消去多余變量因子，獲得邏輯函數(shù)的最簡式的。列表化簡法的思路是先找出給定函數(shù)F的全部素項(xiàng)，然后找出其中的實(shí)質(zhì)素項(xiàng)；若實(shí)質(zhì)素項(xiàng)不能覆蓋F的所有最小項(xiàng)，則進(jìn)一步找出所需素項(xiàng)，以構(gòu)成F的最簡素項(xiàng)集。

下面用列表化簡法將下列函數(shù)化簡為最簡與或表達(dá)式。

F(A,B,C,D)＝Σ(0,3,4,5,6,7,8,10,11)

3、建立素項(xiàng)表

首先，找出給定函數(shù)的全部素項(xiàng)。

(1)先將每個(gè)最小項(xiàng)所對應(yīng)的二進(jìn)制數(shù)按其“1”的個(gè)數(shù)分組得表1；

表1 最小項(xiàng)

(2)將表1中的相鄰兩個(gè)組之間二進(jìn)制數(shù)進(jìn)行比較、合并得到一次化簡結(jié)果，稱為一次乘積項(xiàng)，其項(xiàng)號記為i(j－i)，其中i為最小項(xiàng)中的小項(xiàng)號，j為最小項(xiàng)中的大項(xiàng)號，得表2；

表2 一次乘積項(xiàng)

(3)再將表2中的相鄰兩組內(nèi)的二進(jìn)制數(shù)進(jìn)行比較、合并、便得到第二次化簡結(jié)果，稱為二次乘積項(xiàng)，其項(xiàng)號記為i(n,m)，其中i為兩個(gè)一次乘積項(xiàng)中的小項(xiàng)號，n為原最小項(xiàng)的項(xiàng)號差，m為一次乘積項(xiàng)的項(xiàng)號差，得表3；

表3 二次乘積項(xiàng)

不能與其它一次乘積項(xiàng)合并的一次乘積項(xiàng)是素項(xiàng)，分別以a,b,c,d,e,f記之，不能合并的二次乘積項(xiàng)也是素項(xiàng)，以g記之。

4、實(shí)質(zhì)素項(xiàng)

建立實(shí)質(zhì)素項(xiàng)產(chǎn)生表，找出實(shí)質(zhì)素項(xiàng)。

先用×標(biāo)出每個(gè)素項(xiàng)覆蓋最小項(xiàng)的情況，再找出實(shí)質(zhì)最小項(xiàng)5、6，在×上標(biāo)括號以示區(qū)別，可找出對應(yīng)實(shí)質(zhì)素項(xiàng)g，在其前標(biāo)*，最后一行用“V”標(biāo)出實(shí)質(zhì)素項(xiàng)覆蓋最小項(xiàng)的情況，可看出還有最小項(xiàng)0、3、8、10、11未被覆蓋。如表4所示。

表4實(shí)質(zhì)素項(xiàng)產(chǎn)生式

5、素項(xiàng)產(chǎn)生式

第三步：建立所需素項(xiàng)產(chǎn)生表，找出所需素項(xiàng)，所需素項(xiàng)集應(yīng)覆蓋所有未被實(shí)質(zhì)素項(xiàng)覆蓋的最小項(xiàng)，得表5。再用行列消去法來找，選優(yōu)勢行b0(8)，e3(8)，劃去劣勢行a0(4)及d3(4)得表6，再選最小項(xiàng)為0、3的劣勢列，劃去最小項(xiàng)為8，11的優(yōu)勢列，得表7。找出新的實(shí)質(zhì)素項(xiàng)b，e，取該兩項(xiàng)作為所需素項(xiàng)后，尚有最小項(xiàng)10未被覆蓋，可選取c或f求得所需素項(xiàng)集為(b,e,c)或(b,e,f)，

表5

[!--empirenews.page--]

表6

　表7

得F＝g＋b＋c＋e＝AB＋BCD＋ABD＋BCD

或F＝g＋b＋e＋f＝AB＋BCD＋BCD＋ABC

6、結(jié)論

通過上面介紹可以看出，邏輯化簡能否以最快的速度進(jìn)行，從而得到最簡的邏輯表達(dá)式，與化簡者的經(jīng)驗(yàn)和對公式、方法掌握與運(yùn)用的熟練程度有密切關(guān)系；而列表化簡法思路清晰、準(zhǔn)確，有規(guī)律可循，可得到多種可能答案，但化簡過程比較繁瑣，適宜于用微機(jī)處理并實(shí)現(xiàn)。