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

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

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

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

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


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

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


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


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


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


[math]g(x,y,z)=x\lor y=f(x,y).[/math]

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


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


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


[math]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).[/math]

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


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


[math]\widetilde{f}(\alpha_{i_1},\ldots,\alpha_{i_r})= f(x_1,\ldots,\alpha_{i_1},\ldots, \alpha_{i_r},\ldots,x_n)[/math]

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


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


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


Вернемся к примеру 6.4. Удаляя фиктивное переменное [math]z[/math], вместо функции [math]g[/math] получим либо функцию [math]g(x,y,0)[/math], которая определена на (двумерной) грани [math]\mathbb{B}_{0}^{3;3}[/math] булева куба [math]\mathbb{B}^3[/math], либо функцию [math]g(x,y,1)[/math], определенную на грани [math]\mathbb{B}_{1}^{3;3}[/math]. Направлением каждой из этих граней будет однокомпонентный кортеж (3), определенный номером фиктивного переменного [math]z[/math].


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


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


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




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


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


[math]\begin{array}{|c||c|c|c|c||c|} \multicolumn{6}{r}{\mathit{Table~6.5}} \\\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}[/math]

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


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

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


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

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


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


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




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


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


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


[math]\operatorname{pr}_x^X(\ldots,x,\ldots)=x[/math]

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

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


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


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


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


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


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

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