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

3. Системы функций алгебры логики

3.1 Функциональная полнота

Алгебра над множеством логических функций с двумя бинарными операциями  и  называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения:

а также соотношения булевой алгебры, относящиеся только к конъюнкции и константам (с конъюнкцией).

Отрицание и дизъюнкция в этой алгебре выражаются следующим образом:

Формулы, содержащие знаки  называют полиномами.

Полином вида: , где  есть либо 1, либо переменная, либо конъюнкция различных переменных,  при , называется полиномом Жегалкина.

Теорема.

Любая булева функция может быть представлена полиномом Жегалки- на

где k_i – коэффициенты, принимающие значения 0 или 1: .

3.2 Класс линейных функций (К _Л)

Булева функция называется линейной, если она представима полиномом первой степени

.

Количество линейных функций равно , где п – число перемен-ных.

Для п = 2 их 8:

3.3 Класс функций, сохраняющих ноль (К ₀)

Если булева функция на нулевом наборе переменных равна нулю, то говорят, что функция сохраняет ноль:

3.4 Класс функций, сохраняющих единицу (К ₁)

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

3.5 Класс монотонных функций (К _м)

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

3.6 Класс самодвойственных функций (К _с)

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

Например, конъюнкция и дизъюнкция двойственны друг другу, отрицание двойственно самому себе.

 Функция, совпадающая со своей двойственной, называется самодвойственной.

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

Распределение булевых функций двух переменных по классам