Функции алгебры логики.

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

Например, формула является функцией трех переменных f(x,y,z). Особенностью этой функции является то обстоятельство, что ее аргументы принимают одно из двух значений: ноль или единицу, и при этом функция также принимает одно из двух значений: ноль или единицу.

Определение.

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

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

Выясним, каково число функций n переменных. Очевидно, каждую функцию алгебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать 2ⁿ строк. Следовательно, каждая функция n переменных принимает 2ⁿ значений, состоящих из нулей и единиц. Таким образом, функция n переменных полностью определяется набором значений из нулей и единиц длины 2ⁿ. Общее же число наборов, состоящих из нулей и единиц, длины 2ⁿ равно 2²ⁿ. Значит, число различных функций алгебры логики n переменных равно 2²ⁿ.

В частности, различных функций одной переменной четыре, а различных функций двух переменных шестнадцать. Выпишем все функции алгебры логики одной и двух переменных.

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

Из этой таблицы следует, что две функции одной переменной будут постоянными: f₁(x)=1, f₄(x)=0, а.

Таблица истинности для всевозможных функций двух переменных имеет вид:.

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

, , , ,

, , , ,

, , , ,

, , , .