54. Функционально полные системы (базисы). Булева алгебра логики. Функциональная полнота системы булевых функций. Примеры других алгебр логики.

Примеры функционально полных систем логических функций:

{o} (Функция Вебба),

{½} (штрих Шеффера);

{,® 0}, { ,® 1},

{ &, ,Å 1}

и другие.

Наиболее изученным является базис {&, Ú, Ø}. Формулы, содержащие кроме переменных и скобок знаки этих функций называются булевыми.

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

Следствие: система булевых функций функциональна полна.

Алгебра (Р2; &, Ú, Ø), основным множеством которой является множество всех логических функций Р2, а операциями дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических операций.

Примеры других алгебр логики:

• алгебра Вебба A = áMño ,;

• алгебра Шеффера A = áM, ñ½;

• импликативная алгебра A = áM,® , 0ñ;

• коимпликативная алгебра A = áM,® , 1ñ;

• алгебра Жегалкина A = áM, &, ,Å 1ñ.