Функции алгебры логики

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

Определение 1. Функцией алгебры логики f(x1,x2,…,xn) от n переменных x1,x2,…,xn (или функцией Буля) называется функция n переменных, принимающая значения 0, 1, аргументы которой также принимают значения 0 и 1.

2.2.1)Способы описания функций алгебры логики: словесное описание, в виде таблиц истинности, в виде алгебраического выражения, в виде последовательности десятичных чисел.

СЛОВЕСНОЕ ОПИСАНИЕ ФАЛ.

Проиллюстрируем словесное описание ФАЛ на примере.

Логическая функция трех переменных равна единице, если хотя бы две входные переменные равны единице.

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

ОПИСАНИЕ ФАЛ В ВИДЕ ТАБЛИЦЫ ИСТИННОСТИ.

Таблица, содержащая все возможные комбинации входных переменных xn-1... x1x0 и соответствующие им значения выходных переменных zi называется таблицей истинности или комбинационной таблицей. В общем случае таблица истинности содержит 2n строк и m+n столбцов. Проиллюстрируем построение таблицы истинности на примере.

ОПИСАНИЕ ФАЛ В ВИДЕ АЛГЕБРАИЧЕСКОГО ВЫРАЖЕНИЯ.

При описании ФАЛ алгебраическим выражением используются две стандартные формы ее представления.1) Дизъюнктивной нормальной формой (ДНФ) называется логическая сумма элементарных логических произведений, в каждое из которых аргумент или его инверсия входит один раз.2) Конъюнктивной нормальной формой (КНФ) называется логическое произведение элементарных логических сумм, в каждую из которых аргумент или его инверсия входят один раз.

ОПИСАНИЕ ФАЛ В ВИДЕ ПОСЛЕДОВАТЕЛЬНОСТИ ДЕСЯТИЧНЫХ ЧИСЕЛ.

Иногда для сокращения записи ФАЛ представляют в виде последовательности десятичных чисел. При этом последовательно записывают десятичные эквиваленты двоичных кодов соответствующих конституент единицы или нуля.

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

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

Получена ДНФ может быть из таблицы истинности с использованием следующего алгоритма:

· для каждого набора переменных, на котором функции алгебры логики равна единице, записывают элементарные логические произведения входных переменных, причем переменные, равные нулю, записывают с инверсией. Полученные произведения называют конституентами единицы;

· логически суммируют все конституенты единицы.

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

2) Конъюнктивной нормальной формой (КНФ) называется логическое произведение элементарных логических сумм, в каждую из которых аргумент или его инверсия входят один раз.

Получена КНФ может быть из таблицы истинности с использованием следующего алгоритма:

· для каждого набора переменных, на котором ФАЛ равна нулю, записывают элементарные логические суммы входных переменных, причем переменные, значения которых равны единице, записывают с инверсией. Полученные суммы называют конституентами нуля;

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

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

Рассмотренные методики позволяют получить математическую форму записи для самой функции. Иногда удобнее применять не саму ФАЛ, а ее инверсию. В этом случае при использовании вышеописанных методик для записи СДНФ необходимо выбирать нулевые, а для записи СКНФ — единичные значения функции.