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

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

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

Решение:

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

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

2. Выписываем эти конъюнкции:

х₁х₂х₃ = А;

х₁х₂х₃ = В;

х₁х₂х₃ = С;

х₁х₂х₃ = D;

х₁х₂х₃ = Е.

3. Выполняем минимизацию:

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

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

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

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

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

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

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

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

х3\х1х2
0
	А	В

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