Представление функции алгебры логики (ФАЛ) математическим выражением.

Теоремы булевой алгебры.

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

Справедливость всех перечисленных теорем может быть доказана подстановкой.

При представлении ФАЛ математическим выражением используют два вида ее представления.

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

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

Например, пусть задана логическая функция 3х переменных, которая равна единице в случае, если хотя бы две из входных переменных равны «1». Требуется записать ДНФ этой функции.

Представим логическую функцию в виде таблицы истинности.

Для данной логической функции ДНФ имеет вид:

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

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

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

Например, КНФ для функции из предыдущего примера имеет вид:

КНФ также называется совершенной, т.к. каждая элементарная сумма содержит все переменные.

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

Например, для ФАЛ предыдущего примера СДНФ и СКНФ инверсной функции имеют вид:

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

Например, запись ФАЛ из предыдущего примера в виде последовательности чисел имеет вид: