Составление логических функций

Совершенная дизъюнктивная нормальная форма (СДНФ)

Задача: торговый автомат по продаже чего-либо, стоимостью 3 у.е., принимает монеты, достоинством 1, 2 и 5 у.е., необходимо разработать логический автомат таким образом, чтобы аппарат смог выдать что-либо только лишь при необходимой и достаточной сумме, т.е. ³3 у.е. (выдача сдачи не предусмотрена).

Решение:

Способ первый.

1. Таблица истинности нашего логического элемента должна иметь следующий вид:

3. Эти конъюнкции: 1. Выделяются строки, в которых вых. переменные

х₁х₂х₃ = А; принимают значения лог. 1

х₁х₂х₃ = В; 2. Для этих строк составляются конъюнкции вх.

х₁х₂х₃ = С; переменных, причем если вх. переменная при-

х₁х₂х₃ = D; нимает значение лог. 1, то она обозначается как x

х₁х₂х₃ = Е. если лог 0, то она обозначается как x.

4. После чего конъюнкции объединяются общей дизъюнкцией.
Выполняем минимизацию:

у = х₁х₂х₃ + х₁х₂х₃ + х₁х₂х₃ + х₁х₂х₃ + х₁х₂х₃ = (х₁х₂х₃ + х₁х₂х₃) + (х₁х₂х₃ + х₁х₂х₃) + х₁х₂х₃ =

= х₁х₂ + х₁х₃ + х₁х₂х₃ + х₁х₂х₃ = х₁х₂ + х₁х₃ + х₂х₃ = х₁х₂ + х₁х₂х₃ + х₁х₂х₃ =

= х₁х₂ + х₃(х₁х₂ + х₁х₂) = х₁х₂ + х₃ .

Способ второй.

Минимизация логических функций с помощью карты Карно.

Примечание: аналогично производится минимизация логических функций с помощью диаграмм Вейча.

Карта Карно — это исходная таблица алгоритма работы цифрового устройства, в которой половина входных переменных размещается по горизонтали, а половина — по вертикали. Поле карты Карно при четном количестве переменных представляет собой квадрат, при нечетном — прямоугольник. При размещении входных переменных от строки к строке и от столбца к столбцу изменяется только одна переменная. В образовавшиеся клетки поля карты Карно заносятся выходные значения функции, расположенные рядом по вертикали или горизонтали. Единичные значения выходных функций объединяются с тем, чтобы их количество в объединении было равно 2ⁿ, где n=1,2,3,… В заключении выписываются в форме конъюнкций координаты полученных объединений, после чего они объединяются общей дизъюнкцией.

Таким образом, для нашего примера карта Карно будет иметь следующий вид:

х3\х1х2
0
	А	В

Карту Карно и по горизонтали, и по вертикали можно свернуть в цилиндр, продолжив в соответствующем направлении перебор входных переменных.

В том случае, если выходная переменная чаще принимает значение лог. 1,чем лог. 0, имеет смысл составлять СДНФ для “нулевых ” значений выходных переменных , а затем проинвертировать результат.