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

 

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

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

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

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

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

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

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

 

x

f1(x)

f2(x)

f3(x)

f4(x)

1

1

1

0

0

0

1

0

1

0

 

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

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

 

x

Y

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

f16

1

1

1

1

1

1

0

1

1

0

0

0

1

0

0

0

1

0

1

0

1

1

1

0

1

1

0

0

1

1

0

0

0

1

0

0

0

1

1

1

0

1

1

0

0

1

1

0

1

0

1

0

0

0

0

0

1

0

1

1

1

0

1

1

0

1

0

1

0

0

0

0

 

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

,               ,            ,                    ,

,                  ,                   ,                                      ,

,                ,             ,                                      ,

,      ,                   ,                               .

Функция   называется функцией Пирса и обозначается  (стрелка Пирса), а функция называется функцией Шеффера и обозначается  (штрих  Шеффера). Каждая из двух последних функций обладает удивительной способностью порождать все множество булевых функций.