Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


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


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


Можно заметить, используя тождества булевой алгебры, что g(x,y,z)=(x\lor y)(z\lor \overline{z}), а поскольку z\lor \overline{z}=1, то


g(x,y,z)=x\lor y=f(x,y).

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


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


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


f(x_1,\ldots,x_{i-1},0,x_{i+1},\ldots,x_n)= f(x_1,\ldots,x_{i-1},1,x_{i+1},\ldots,x_n).

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


Пусть дана булева функция y=f(x_1,\ldots,x_n) от n переменных. Пусть существенными переменными этой функции являются переменные x_{i_1},\ldots, x_{i_r}, где r\leqslant n и 1\leqslant i_1<\ldots<i_r\leqslant n. Присваивая каждому фиктивному переменному функции f произвольное значение, получим функцию \widetilde{f}, такую, что она есть функция от r переменных, т.е. есть отображение из \mathbb{B}^n в \mathbb{B}, и для любого набора \alpha_{i_1},\ldots,\alpha_{i_r} значений переменных x_{i_1}, \ldots,x_{i_r} имеет место равенство


\widetilde{f}(\alpha_{i_1},\ldots,\alpha_{i_r})= f(x_1,\ldots,\alpha_{i_1},\ldots, \alpha_{i_r},\ldots,x_n)

независимо от значений фиктивных переменных функции f (т.е. переменных, отличных x_{i_1}, \ldots,x_{i_r}). Тем самым функция \widetilde{f} оказывается уже функцией, определенной на некоторой r-мерной грани булева куба \mathbb{B}^n.


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


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


Вернемся к примеру 6.4. Удаляя фиктивное переменное z, вместо функции g получим либо функцию g(x,y,0), которая определена на (двумерной) грани \mathbb{B}_{0}^{3;3} булева куба \mathbb{B}^3, либо функцию g(x,y,1), определенную на грани \mathbb{B}_{1}^{3;3}. Направлением каждой из этих граней будет однокомпонентный кортеж (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, т.е. переменное x_1 существенное. Далее, f(1,0,0)=0, но f(1,1,0)=1, что означает существенность переменного x_2; для x_3 имеем f(1,0,0)=0, но f(1,0,1)=1, что означает существенность и этого переменного.


б. Ниже приведена таблица функции g от четырех переменных (табл. 6.5). Рекомендуется проверить, что переменное x_2 является фиктивным и что остальные переменные существенны. Более того, анализ таблицы показывает, что эта функция есть не что иное, как мажоритарная функция, существенно зависящая от переменных x_1,\,x_3 и x_4.


\begin{aligned} \mathit{Table~6.5}~&\\ \begin{array}{|c||c|c|c|c||c|} \hline & x_1& x_2& x_3& x_4& g(x_1,x_2,x_3,x_4) \\\hline \scriptstyle{\mathsf{0}}& 0& 0& 0& 0& 0\\ \scriptstyle{\mathsf{1}}& 0& 0& 0& 1& 0\\ \scriptstyle{\mathsf{2}}& 0& 0& 1& 0& 0\\ \scriptstyle{\mathsf{3}}& 0& 0& 1& 1& 1\\ \scriptstyle{\mathsf{4}}& 0& 1& 0& 0& 0\\ \scriptstyle{\mathsf{5}}& 0& 1& 0& 1& 0\\ \scriptstyle{\mathsf{6}}& 0& 1& 1& 0& 0\\ \scriptstyle{\mathsf{7}}& 0& 1& 1& 1& 1\\ \scriptstyle{\mathsf{8}}& 1& 0& 0& 0& 0\\ \scriptstyle{\mathsf{9}}& 1& 0& 0& 1& 1\\ \scriptstyle{\mathsf{10}}& 1& 0& 1& 0& 1\\ \scriptstyle{\mathsf{11}}& 1& 0& 1& 1& 1\\ \scriptstyle{\mathsf{12}}& 1& 1& 0& 0& 0\\ \scriptstyle{\mathsf{13}}& 1& 1& 0& 1& 1\\ \scriptstyle{\mathsf{14}}& 1& 1& 1& 0& 1\\ \scriptstyle{\mathsf{15}}& 1& 1& 1& 1& 1\\\hline \end{array}& \end{aligned}

Кроме процедуры удаления фиктивных переменных используют и процедуру добавления к множеству переменных булевой функции одной или нескольких фиктивных переменных. Так, если дана функция f(x_1,\ldots,x_n)\in \mathcal{P}_{2,n}, то можно ввести новое фиктивное переменное у, определив новую, равную исходной, согласно определению 6.2, функцию от n+1 переменного таким образом:


\widehat{f}(x_1,\ldots,x_n,y)= f(x_1,\ldots,x_n)\cdot (y\lor\overline{y}) (см. пример 6.4).

Следует заметить, что фиктивное переменное можно (в новой функции \widehat{f}) "поставить на любое место". Или, говоря точнее, можно определить семейство функций \widehat{f}_i,~i=\overline{1,n}, с фиктивным переменным y так, что


\widehat{f}_i(x_1,\ldots,y,x_i,\ldots,x_n)= f(x_1,\ldots,x_n)\cdot (y\lor \overline{y}).

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


Действительно, пусть функция f(x_1,\ldots,x_n) есть функция от n переменных, а функция g(y_1,\ldots,y_m) — функция от m переменных. Обозначим множества переменных функции f и g через X и Y соответственно. Расширим множество переменных функции f до X\cup Y, вводя переменные из Y\setminus Y (если они существуют) как фиктивные. Точно так же поступим с функцией g, добавляя фиктивные переменные из множества X\setminus Y (если, конечно, оно не пусто). Тогда получим функции f и g, равные, согласно определению 6.2, функциям f и g соответственно и определенные как функции от одного и того же числа переменных, составляющего мощность объединения множеств |X\cup Y|.


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




Проектирующая функция


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


Функцию \operatorname{pr}_i от n переменных, такую, что \operatorname{pr}_i(x_1,\ldots,x_i,\ldots,x_n)=x_i\,, называют (i-й) проектирующей функцией. В общем случае нумерация множества переменных может быть явно не задана, и тогда при определении проектирующей функции следует указывать не номер соответствующего переменного, а само переменное. В этом случае проектирующая функция \operatorname{pr}_x^X с множеством переменных X этой функции и выделенным переменным x\in X определяется так:


\operatorname{pr}_x^X(\ldots,x,\ldots)=x

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

Из определения следует, что проектирующая функция \operatorname{pr}_x^X имеет единственное существенное переменное, а именно переменное x. Все остальные переменные проектирующей функции являются фиктивными. Поэтому любые две проектирующие функции \operatorname{pr}_x^X и \operatorname{pr}_x^Y равны, согласно определению 6.2, при любых множествах переменных X и Y, содержащих переменное x.


Вместе с тем для двух различных переменных x и y проектирующие функции \operatorname{pr}_x^X и \operatorname{pr}_x^Y — разные функции. Так, \operatorname{pr}_1(x_1,x_2) — функция, отличная от функции \operatorname{pr}_2(x_1,x_2) поскольку, например, \operatorname{pr}_1(1,0)=1,~ \operatorname{pr}_2(1,0)=0.


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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2019 MathHelpPlanet.com. All rights reserved