Как уже отмечалось, значение формулы
алгебры логики полностью зависит от значений входящих в эту формулу
высказываний. Поэтому формула алгебры логики является функцией входящих в нее
элементарных высказываний.
Например, формула
является функцией трех
переменных 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 |
Из рассмотрения значений этих функций
ясно, что их аналитические выражения могут быть записаны следующим образом:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
.
Функция
называется функцией Пирса и обозначается ![]()
(стрелка Пирса), а функция ![]()
![]()
называется
функцией Шеффера и обозначается
(штрих Шеффера). Каждая из двух последних функций обладает
удивительной способностью порождать все множество булевых функций.