Логические функции и способы их записи

Для описания процессов в устройствах цифровой электроники и алгоритмов работы логических элементов, использующих для взаимодействия «высокий» и «низкий» уровни напряжения, применяют алгебру логики или булеву алгебру, разработанную в середине 19-го века ирландским математиком Дж. Булем. В ее основу положены три основные логические операции (логические функции): логическое отрицание или операция «НЕ» (инверсия), логическое сложение или операция «ИЛИ» (дизъюнкция) и логическое умножение или операция «И» (конъюнкция). После выполнения операции НЕ над переменной получается результат После выполнения операции ИЛИ над переменными и получается результат . После выполнения операции И над переменными и получается результат . Количество переменных над которыми производятся логические операции может быть произвольным (больше двух).

Логическая функция может быть задана в алгебраической форме (булево выражение) и в виде таблицы истинности.

Алгебраическая форма имеет вид выражения, в котором указаны операции над логическими переменными, например:

. (1)

Порядок выполнения действий над переменными в выражении (1) соответствует порядку выполнения операций над переменными в обычном алгебраическом выражении.

Таблицей истинности называется таблица, определяющая значении функции (выходной величины) для всех возможных комбинаций входных переменных. На рис.1. приведен примерный вид таблицы истинности для логической функции из переменных. Такая таблица состоит из 2ⁿ строк и n+1столбцов.

Рис. 1.

Таблицы истинности для логических функций НЕ, ИЛИ, И приведены на рис. 2.

Рис.2

Как таблица истинности может быть получена из алгебраической формы записи логической функции, так и алгебраическая форма записи логической функции может быть получена из таблицы истинности.

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

Например вычисление всех значений логической функции дает таблицу истинности, приведенную на рис. 3.

Рис. 3

Для получения алгебраической формы записи логической функции из таблицы истинности используются совершенно дизъюнктивная нормальная форма (СДНФ) или совершенно конъюнктивная нормальная форма (СКНФ) формы записи логической функции.

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

. (2)

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

Для таблицы истинности можно записать следующие минтериы:

, , , , , , , .

В соответствие с (2) и таблицей истинности, приведенной на рис.3 записывается СДНФ функции в виде:

.

Таким образом СДНФ содержит столько дезъюнктивных членов, сколько раз функция принимает значение 1.

Логическая функция в виде СКНФ является произведением (конъюнкцией) сумм (дизъюнкций) значений логической функции и макстермов , причем число произведений равно числу строк в таблице истинности.

. (3)

Макстерм – это логическая сумма всех переменных в которой переменные равные единице записаны с инверсией.

Макстермы для таблицы истинности (рис.3):

, , , , , , , .

В соответствие с (3) и таблицей истинности, приведенной на рис.3 записывается СКНФ функции в виде:

.

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