Метод непосредственных преобразований

Непосредственное упрощение исходной логической функции, заданой в виде СДНФ, выполняется в следующем порядке

. Для каждой из возможных пар соседних конституент СДНФ применяется операция полного склеивания. При этом из них исключается по одной пе­ременной. Потом выполняется приведение подобных членов. Этот про-цесс повторяется до тех пор, пока в полученном выражении не останется конъюнкций, которые отличаются друг от друга значениями одной пере­менной. Полученная таким способом форма называется сокращенной нормальной формой. Конъюнкции, которые входят в сокращенную нор­мальную форму, называются простыми импликантами. Каждой логиче­ской функции отвечает лишь одна сокращенная форма.

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

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

Для исходной функции, заданной в виде СКНФ, минимизация методом непо­средственного упрощения выполняется таким образом.

1. Сначала к членам СКНФ применяют операцию полного склеивания.

2. Пользуясь законом дистрибутивности, раскрывают скобки в полученном
выражении.

3. Приводят подобные члены и применяют операцию поглощения.

4. Полученную таким способом ДНФ минимизируют в указанном выше по­
рядке.

Пример: Найти минимальную форму функции, заданной СДНФ F(a,b,c) =a c + с + + b + ab = abc.

Применяя операцию полного склеивания к сочетаниям каждой конституенты со всеми соседними и приводя подобные члены, получаем сокращенную нормальную форму:

F(a,b,c) = + c+ac+ab+b +

Применение операции обобщенного склеивания к импликантам можно осу­ществить в нескольких вариантах.

Каждому из них отвечает одна из следующих тупиковых форм:

F₁(a,b,c) = ac + c + b + ;

F₂ (a,b,c) = ac + b + ;

F3(a,b,c) = c + ab + .

Очевидно, что анализируемой функции отвечают две минимальных нормаль­ных формы F₂{a,b,c) и F₃(a,b,c).

Дата добавления: 2015-07-08