Главная страница  Систематические методы минимизации 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [ 25 ] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128]

или в виде произведения основных сумм со значением 0: Fi = =П(2 35 6, 7) = (А+В + С)(А+В + С)(А+В + С)Х(А+В + + С)(А+В + С).

Можно доказать, что обе функции тождественны-. Используя законы и правила табл. 4.1, их можно постепенно упростить, получив одинаковые алгебраические выражения:

Е(0, 1, 4)=АВС+ШС-{-АШ=ВС+АВС==В(С+АС)=В(А-{-С),

П(2,3,5,6,7)=-(++С) (А+В+С) {А+В+С) (A+B+Q (Л-fB+Q= .

= {А+ЩА+В) {А+В+С)=В{А+В+С)=В (Л-f С),

поэтому справедливо, 4to..Fi = E(0, 1, 4) =П(2, 3, 5, 6, 7).

На рис. 4.4в представлена неполная истинностная таблица, в которой логическая функция iFz зависит только от комбинаций О-4. Остальные комбинации 5-7 (.избыточные) могут иметь любое значение 1 или О, которое обычно обозначается символом X. Эти избыточные комбинации используются для упрощения алгебраических выражений логических функций, как это будет показано в следующих главах.

Функцию ifi можно записать в конъюнктивной форме в карты Карно таким образом, что 1 записываются в поля, соответствующие основным произведениям ABC, ABC, ABC. Если это полная функция, то в остальные поля автоматически записываются 0.

Большее внимание нужно уделить записи функции Fi в дизъюнктивной форме. Функция Fi равна О, если каждая частичная сумма равна 0. Если, например, А+В + С=0, то должно быть Л = 0, т. е."Л = 1, В=0, т е. В = 1, и С=0, т. е. С=Л. Поэтому представленную основную сумму запишем в поле, соответствующее переменным ABC. Из всего этого видно, что запись в нормальной дизъюнктивной форме значительно упростится, если ее записать.Б инверсной форме. Это значит, что вмсто функции Fi = (А+В + С) (А+В + С) (А+В + С) (А+В + С) (А+В + С) запишем функцию Fi=ABC+ABC+ABC+ABC+ABC, которую можно написать, используя закон де Моргана.

4.3. СИСТЕМАТИЧЕСКИЕ МЕТОДЫ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ

Под минимизацией логической функции подразумевается преобразование ее алгебраического выражения с получением самой простой формы. В основу минимизации положены правила и законы, представленные в табл. 4.1. Метод последовательного упрощения с использованием этих правил трудоемок, требует большого опыта и интуиции, мало нагляден, и при этом легко может возникнуть ошибка. Он пригоден только для преобразования простых алгебраических выражений. Кроме этого метода, существует много других, использующих, например, диаграмму Венна, диаг-



рамму Вейча и карты Карно, метод Квайна - Мак-Класки и др. Для обычной технической практики наиболее пригодны последние методы, особенно минимизация функции с использованием карт Карно.

После записи логической функции в карту Карно обычно сразу видна минимальная форма функции и возможность ошибки уменьшается до минимума. Карты могут быть применены и для пяти-шести переменных, что вполне достаточно для использования в обычной практике.

Основной принцип минимизации функции трех переменных наглядно представлен в примере на рис. 4.5. Объединяются всегда

АВ А В АВ АВ АВ АВ АВ АВ

с\во 01 11 10 t\oo 0111 10 \во 01 11 10 Koooiiiw

-АС+АС

hBBfAB

АВ-Ю

В1 и 10 \0В

в! 11

С\ВВ 01 и 10

F=AC*B

FACtB

F = BH

F-ACjBC-AB = BC+AB+AC

Рис. 4.5. Примеры минимизации функций

два или четыре соседних поля, в которых записаны 1. Объединением двух полей исключается одна переменная, объединением четырех полей исключаются две переменные. Возможно также объединение крайних полей на противоположных сторонах карты. Простота определения минимизированной функции ясна из сравнения алгебраического выражения минимизированной функции F=B + C, которая была записана в карту (в нормальной форме

F=ABC+ABC+ABC+ABC+ABC+ABC.

В последнем примере (правая карта внизу) запись функции неоднозначна. Она может быть представлена в двух минимизированных формах.

На рис. 4.6 представлены примеры карт минимизации функции четырех переменных. Первая карта слева внизу - пример минимизации функции с избыточными переменными X, которые могут иметь значение 1 или 0. Если рассматривать вместо X значение 1, то минимизация значительно упрощается. Третья карта справа внизу - пример принципа запрета, который облегчает быструю минимизацию функции при почти полном объединении всех полей, за исключением одного, в котором записан 0. Это поле - ABCD. Принцип запрета заключается в отрицании произведения ACD, потому что переменная В уже соответствует объединенным полям.



Шоо СП т

со II

ей 10

АВ АВ АВ АВ 00 0111 10

01 11 10.

Си\00 01 11. IP

FABCD

С1!\0В 01 11 10 00 Ю 01

F=ACD+ABD

F=AB+fiB

11 10 Ш

F=En JO BI и 10

F=A+BCB ВО В1 11 10

F=AB*C OB 01 11 10

FA+C-i-CD РЕШЕАВтЕ F=S(ACr) Рис. 4.6. Примеры минимизации функций

во 01 и

01 и 10

00 В1 11 10 во 01

ю\ ! !

F=CE-tACnt

тАВЁМОЁС

--SC-ALUi-ASE-i-BEll

во 01 11 10 во 01 п iF

вс\вв

В1 11

ЮОО 01 11 10

и

F-ABEfACEi-.W+fiEE

+ACD+ABCB

Рис. 4.7. Примеры минимизации функций

На рис. 4.7 приведены примеры карт минимизации функций • ПЯТИ переменных.

4.4. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ФУНКЦИИ

Результатом комбинаций значений двух переменных ~ X а У - являются 16 логических функций, представленных в табл. А.2а, б. Не все из них имеют практическое значение. Напри-82




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [ 25 ] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128]

0.0198