Фиктивные переменные. Равенство булевых функций

В вышеприведённых таблицах выделена графа «фиктивные переменные», т.е. переменные, от которых функция на самом деле не зависит. Остановимся на этом понятии подробнее.

Пример: Рассмотрим булевы функции f(x,y) = xÚy и g(x,y,z) = (xÙy)Ú(хÙ )Ù(yÙz)Ú(yÙ ). Можно заметить, что в силу тождеств алгебры Буля g=(xÚy)Ù(zÚ ), а поскольку zÚ =1, то g = xÚy = f.

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

Определение: Переменная х является существенной переменной для функции f(x, x₁,…, x_n-1), если существует хотя бы один набор (x₁,…, x_n-1) такой, что f(0, x₁,…, x_n-1) ≠ f(1, x₁,…, x_n-1)

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

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

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

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

В результате понятие фиктивной переменной позволяет любые две функции рассматривать как функции от одних и тех же переменных. Для этого надо рассмотреть объединение множеств переменных XUY и дополнить множества X и Y до объединения, вводя соответствующие переменные как фиктивные.

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

Введём понятие проектирующей функции.

Функцию pr_i от n переменных, такую, что

pr_i(x₁, …, x_i,…, x_n)= x_i

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

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