ТАБЛИЧНОЕ И ЦЕПОЧНОЕ ЗАДАНИЕ ФУНКЦИЙ. ЭЛЕМЕНТАРНЫЕ ФУНКЦИИ. ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ

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

Элементы множества  часто называют логическими функциями или булевыми функциями.

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

.

Очевидно, что . Это отмечено в 1.3.

Любая функция из  может быть задана с помощью таблицы, состоящей из  строк и двух столбцов. В строке i, где , в первом столбце записывается набор значений переменных  такой, что , а во втором столбце записывается значение функции . Такое расположение элементов  в таблице называется стандартным, а вся последовательность наборов – стандартной последовательностью наборов значений и обозначается через . Если значения функции, заданной на , записать в строку в виде цепочки элементов из , то получим цепочку над  длины . Таким образом, функции из  можно задавать не только в виде таблицы, но и в виде цепочки над  длины . Отсюда следует, что .

Пример 3.1. Пусть функция  задана таблицей.

( , )
(0,0)	1
(0,1)	1
(1,0)	1
(1,1)	0

Тогда эта функция, заданная в виде цепочки, будет иметь вид .

Функция  существенно зависит от переменной , , если существуют такие значения  переменных , что

.

При этом переменная  называется существенной. Переменные не являющиеся существенными называются фиктивными.

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

Функции  и  называется равными, если функцию  можно получить из функции  путем добавления или изъятия фиктивных переменных.

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

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

Пусть , тогда . В множестве  две функции, не зависящие от переменных. Это элементы множества : константа  и константа .

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

Аргумент и функции	x
Значения функций на наборах	0	0	1	0	1
	1	0	0	1	1
Обозначение функций		0		x	1

Названия:  – константа 0;  – отрицание аргумента , читается «не »;  – тождественная функция;  – константа 1. Функции  являются константами из , так как переменная  в них является фиктивной.

Пусть , тогда . Функции из  представлены в следующей таблице.

( )
(0,0)	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
(0,1)	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
(1,0)	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
(1,1)	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
	0							|	&							1

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

Функции  и  – это константы 0 и 1 соответственно и , .

Функции  и  – функции одного переменного. Для них переменная  является фиктивной и , а .

Функции  и  – функции одного переменного. Для них переменная  является фиктивной и , а .

Все остальные функции не имеют фиктивных переменных.

Функция  называется стрелкой Пирса и обозначается .

Функция  не имеет названия и является отрицанием обратной импликации,  и обозначается .

Функция  не имеет названия и является отрицанием импликации,  и обозначается .

Функция  называется сложением  и  по модулю 2, обозначается  и читается «  плюс ».

Функция  называется штрихом Шеффера и обозначается .

Функция  называется конъюнкцией, обозначается  или , или , или  и читается «  и ».

Функция  называется эквивалентностью, обозначается  и читается «  эквивалентно ».

Функция  называется импликацией, обозначается  или  и читается «  влечет » или «  имплицирует ».

Функция  называется обратной импликацией, обозначается  и читается «  следует из ».

Функция  называется дизъюнкцией, обозначается  или  и читается «  или ».

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

Пусть  и .

1. Имена переменных будем называть формулами над .

2. Пусть ,  – формулы над , тогда выражение  есть формула над . Формулы  называются подформулами формулы .

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

Пример 3.2. Пусть . По определению формулы алгебры логики ,  и  являются формулами над множеством . В формуле  переименуем имена переменных. Вместо  запишем , а вместо  запишем . Получим . Возьмем  и подставим  и  в  вместо  и  соответственно. Получим формулу . В данной суперпозиции была использована префиксная запись функций. Для функций от двух переменных можно использовать инфиксную запись.
Тогда . Используя обозначения для элементарных функций, получим . Так как таблицы функций , ,  известны, то по формуле  можно вычислить значение функции, реализованной этой формулой на любом наборе значений имен переменных. Вычислим  на наборе , , . Получим , , . Если формулу вычислить на всех  наборах, то можно получить таблицу функции, которую данная формула реализует. Следовательно, формула может служить еще одним способом задания функций.