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

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

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

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

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

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

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

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

Из таблицы следует, что f₁(x)  1, f₄(x)  0, f₂(x)  x,

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

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