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

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

Пример 6.4. Рассмотрим булевы функции f(x,y) =x ∨ y и g(x,y,z) = xz ∨ xz ∨ yz ∨ yz.

Можно заметить, используя тождества булевой алгебры, что

g(x,y,z) = (x ∨ y)(z ∨ z),

а поскольку z ∨ z = 1, то

g(x,y,z) = (х ∨ y) = f(x,y),

и функции f и g естественно рассматривать как равные, несмотря на то что они зависят от разного числа переменных. #

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

Определение 6.1. Переменное x_i называют фиктивным переменным булевой функции f(x₁, ... ,x_n), если значение функции не зависит от значения этого переменного, т .е. если для любых значений переменных х₁, ... , x_i-1, х_i+1, ... , x_n

f(х₁, ... , x_i-1, 0, х_i+1, ... , x_n) = f(х₁, ... , x_i-1, 1, х_i+1, ... , x_n).

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

Пусть дана булева функция у = f(x₁, ... ,x_n) от n переменных. Пусть существенными переменными этой функции являются переменные x_i1, ... ,x_ir, где r ≤ n и 1 ≤ i₁<...r ≤ n. Присваивая каждому фиктивному переменному функции f произвольное значение, получим функцию f, такую, что она есть функция от r переменных, т.е. есть отображение из B^r в В, и для любого набора α_i1, ... , α_ir значенuй переменных x_i1, ..., x_ir имеет место равенство

f˜(α_i1 , ... ,α_ir) = f(x₁, ..., α_i1, ... ,α_ir,...,x_n)

независимо от значений фиктивных переменных функции f (т.е. переменных, отличных от x_i1 , ..., x_ir). Тем самым функция f оказывается уже функцией, определенной на некоторой r-мерной грани булева куба Bⁿ.

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

Замечание 6.2. В качестве упомянутой вьппе r-мерной грани может быть взята любая грань с направлением, заданным номерами фиктивных переменных. Фиксация грани означает фиксацию конкретного набора значений фиктивных переменных. Тогда соответствующая этой грани функция f получается из исходной функции f в результате подстановки вместо каждого фиктивного переменного того конкретного значения, которое задано указанным вьппе набором.

Вернемся к примеру 6.4. Удаляя фиктивное переменное z, вместо функции g получим либо функцию g(x,y,O), которая определена на (двумерной) грани B^3,30 булева куба В³ , либо функцию g(x,y,1), определенную на грани B^3,31 . Направлением каждой из этих граней будет однокомпонентный кортеж (3), определенный номером фиктивного переменного z. #

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

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

Чтобы распознать по таблице булевой функции, является ли переменное x_i фиктивным, нужно рассмотреть все наборы с фиксированным значением i-й компоненты (один раз фиксировав это значение как 0, другой раз - как 1). Из определения 6.1 ясно, что переменное x_i фиктивно тогда и только тогда, когда для любых двух наборов, отличающихся только значением i-й компоненты, функция принимает равные значения.

Пример 6.5. а. Из табл. 6.4 следует, что мажоритарная функция не имеет фиктивных переменных, так как, например, f(0,0,1) = 0, а f(1,0,1) = 1, т.е. переменное х₁ существенное. Далее, f(1,0,0) = 0, но f(1,1,0) = 1, что означает существенность переменного х₂; для х₃ имеем f(1,0,0) = 0, но f(1,0,1) = 1, что означает существенность и этого переменного.

б. Ниже приведена таблица функции g от четырех переменных (табл. 6.5). Рекомендуется проверить, что переменное х₂ являетеся фиктивным и что остальные переменные существенны. Более того, анализ таблицы показывает, что эта функция есть не что иное, как мажоритарная функция, существенно зависящая от переменных х₁, х₃ и х₄. #

Кроме процедуры удаления фиктивных переменных используют и процедуру добавления к множеству переменных булевой функции одной или нескольких фиктивных переменных. Так, если дана функция f(x₁, ... ,x_n) ∈ P_2,n, то можно ввести новоефиктивное переменное у, определив новую, равную исходной, согласно определению 6.2, функцию от n + 1 переменного таким образом:

(см. пример 6.4).

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

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

Действительно, пусть функция f(х₁, ..., x_n) есть функция от n переменных, а функция g(y₁, ..., y_m) - функция от m переменных. Обозначим множества переменных функции f и g че рез Х и У соответственно. Расширим множество переменных функции f до Х ∪ У, вводя переменные из У\Х ( если они существуют) как фиктивные. Точно так же поступим с функцией g, добавляя фиктивные переменные из множества Х\У (если, конечно, оно не пусто). Тогда получим функции и , равные, согласно определению 6.2, функциям f и g соответственно и определенные как функции от одного и того же числа переменных, составляющего |X ∪ Y|.

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

В заключение рассмотрим понятие проектирующей функции.

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

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

называют (i-й) проектирующей функцией. В общем случае нумерация множества переменных может быть явно не задана, и тогда при определении проектирующей функции следует указывать не номер соответствующего переменного, а само переменное. В этом случае проектирующая функция pr^Xx c множеством переменных Х этой функции и выделенным переменным х ∈ Х определяется так:

pr^Xx (...,х,...) = х

(за многоточиями "скрыты" переменные проектирующей функции, отличные от переменного х).

Из определения следует, что проектирующая функция pr^Xx имеет единственное существенное переменное, а именно переменное х. Все остальные переменные проектирующей функции являются фиктивными. Поэтому любые две проектирующие функции pr^Xx и pr^Yx равны, согласно определению 6.2, при любых множествах переменных Х и У, содержащих переменное х.

Вместе с тем для двух различных переменных х и у проектирующие функции pr^Xx и pr^Yx - разные функции. Так, pr₁(x₁,x₂) - функция, отличная от функции pr₂(x₁,x₂), поскольку, например, pr₁(1,0) = 1, pr₂(1,0) =0.

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

Замечание 6.3. Такое обозначение проектирующих функций есть условность и определенная вольность, состоящая в том, что проектирующая функция pr^Xx как бы отождествляется с самим переменным х. Однако отождествление функции и переменного недопустимо, так как понятие переменного, хоть и связано с понятием функции, никак не есть частный случай понятия функции. Переменное - только имя, некое обозначение, которое используется при аналитическом задании функции, но никак не сама функция. Тем не менее ради краткости, мы сохраним обозначение х как обозначение любой из проектирующих функций pr^Xx и будем использовать иногда даже выражение "функция х", понимая под этим любую из указанного семейства проектирующих функций.