Способы записи функций алгебры логики

Рассмотрим некоторое параллельное логическое устройство (рисунок 3), на входе которого присутствует n-разрядный двоичный код, а на выходе m- разрядный двоичный код, причём n ¹ m.

Рисунок 3 – Логическое устройство, содержащее n входов и m выходов

 

Чтобы описать поведение логического устройства необходимо определить зависимость каждой из m выходных переменных y_i от всех входных сигналов х_n-1,…x₁, x₀.

Зависимость выходных переменных y , выраженная через совокупность входных переменных (х_n-1,…x₁, x₀), записанная с помощью операций алгебры логики, называется функцией алгебры логики (ФАЛ). Задать ФАЛ – это определить значения y_i для всех возможных сочетаний входных переменных (х_n-1,…x₁, x₀). Очевидно, что для n-разрядного входного кода существует 2ⁿ различных значений y_i.

ФАЛ называется полностью определённой, если заданы все 2ⁿ её значений y_i. Если часть значений y_i не задана, то ФАЛ называется частично определённой (недоопределённой).

Для описания ФАЛ могут быть использованы различные способы, например:

1) словесная форма;

2) таблица истинности;

3) алгебраические выражения.

Наиболее наглядно ФАЛ представляется таблицей истинности, пример которой для y = f (x₂, x₁, x₀) представлен в таблице 4.

 

Таблица 4 – ФАЛ, заданная таблицей истинности для трёх входных переменных

Х2	Х1	Х0	Y
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

 

Чтобы записать ФАЛ в виде алгебраического выражения можно использовать две стандартные формы представления: ДНФ – дизъюнктивно нормальная функция; КНФ – конъюнктивно нормальная функция.

ДНФ – это логическая сумма элементарных логических произведений, в каждое из которых аргумент x или его инверсия входит один раз. ДНФ получают из таблицы истинности по следующему правилу:

- для каждого набора переменных, на котором y = 1, записываются элементарные логические произведения входных переменных, причем переменная x = 0 записывается с инверсией;

- логически суммируются все элементарные логические произведения.

Из заданной таблицы истинности получается следующая ДНФ:

         (1.2)

КНФ – это логическое произведение элементарных логических сумм, в каждую из которых аргумент x или его инверсия входят один раз. КНФ получают из таблицы истинности по правилу:

- для каждого набора переменных, на котором y = 0, записываются элементарные логические суммы входных переменных, причём переменная х = 1, записывается с инверсией;

- логически перемножаются все элементарные логические суммы.

Из заданной таблицы истинности получается следующая КНФ:

(1.3)

Полученные алгебраические выражения (1.2) и (1.3) равносильны. Представление ФАЛ в виде ДНФ или КНФ выбирают с целью получить возможно более короткую запись алгебраического выражения. Для этого анализируют таблицу истинности: если у выходной переменной y больше нулей, чем единиц, проще записать ДНФ; если больше единиц, чем нулей, проще записать КНФ.