Информатика и вычислительная техника

Настенные полки купите полки настенные.

Преобразование и минимизация логических выражений - часть 2


С этой целью в ДСНФ исходной логической функции выявляются соседние минтермы, т.е. такие, в которых имеется по одной несовпадающей переменной, например, х1 & х2 & х3 и х1 & х2 & х3;

113

х1 & х2 & х3 и х1 & х2 & х3. При вынесении за скобки общих множителей в

таких минтермах происходит исключение одной переменной, и они склеиваются в одну конъюнкцию. Например:

x1 & x2 & x3 ? x1 & x2 & x3 = x1 & x3 & (x2 ? x2) = x1 & x3.

Конъюнкции, образованные в результате склеивания, называются импликантами. Полученные после склеивания импликанты склеиваются повторно и так до тех пор, пока склеивание возможно. Например:

Проиллюстрируем метод непосредственных преобразований еще одним примером. Пусть задана логическая функция трех переменных F(х, у, z)табл. 5.3.

Таблица 5. 3

Логическая функция трех переменных

x y z F x y z F
0 0 0 1 1 0 0 0
0 0 1 1 1 0 1 0
0 1 0 1 1 1 0 0
0 1 1 1 1 1 1 0

Образуем ДСИФ данной функции:

F = х & у & z ? х & у & z ? х & у & z ? х & у & z

Здесь первая и вторая, а также третья и четвертая конъюнкции являются соседними. Склеивая эти конъюнкции, получим:

F = x & y & (z ? z) ? x & y (z ? z) = x & y ? x & y.

К полученным импликантам применим повторное склеивание:

F = x & y ? x & y = x & (y ? y) = x.

Таким образом, в результате выполнения преобразований исходная функция трех переменных оказалась инверсией лишь одной переменной х. В этом также можно убедиться, проанализировав табл. 5.3.

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


Начало  Назад  Вперед