Булевые функции и их свойства

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

Булевая функция имеет следующие свойства:

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

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

ПРИМЕР

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

3. Линейность . Функция является линейной, если её можно представить в виде:

где - булевая переменная

ПРИМЕР

Эквивалентность является линейной функцией:

4. Монотонность . Функция является монотонной, если для любых произвольных наборов a и b выполняются следующие неравенства:

5. Самодвойственность . Функция называется самодвойственной, если она равна двойственной ей функции.

Двойственной функцией называется функция:

Тогда свойство самодвойственности может представлено:

ПРИМЕР

Отрицание является самодвойственной функцией: