Функций

Логическая функция [функция алгебры логики (ФАЛ)] – это выражение, представляющее собой сложное высказывание, состоящее из нескольких простых высказываний , связанных соединительными словами. Это сложное высказывание принимает значения 0 или 1 на всех наборах логических значений всех простых высказываний.

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

Набор логических переменных, или, иначе входной набор, – это определенная комбинация значений переменных в логической функции. Максимальное число различных входных наборов есть величина , где – число переменных.

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

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

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

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

НДФ – это дизъюнкция нескольких элементарных конъюнкций. Эта форма называется нормальной, так как все ее члены имеют вид элементарных конъюнкций. Вследствие того, что все члены соединены в одну функцию знаком дизъюнкции, форма носит название дизъюнктивной. И, наконец, форма называется совершенной, если её члены имеют высший ранг, являясь конституентами единицы или нуля.