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

1、概述

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

2、原理

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

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

素項──若函數的一個(gè)蘊涵項不是該函數中其它蘊涵項的一個(gè)子集，則此蘊涵項稱(chēng)為素蘊涵項，簡(jiǎn)稱(chēng)素項。

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

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

下面用列表化簡(jiǎn)法將下列函數化簡(jiǎn)為最簡(jiǎn)與或表達式。

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

3、建立素項表

首先，找出給定函數的全部素項。

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

表1 最小項

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

表2 一次乘積項

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

表3 二次乘積項

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

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

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

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

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

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

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

表5