Содержание
Определение. Говорят, что булева функция f(x1, …, xi, …, xn) существенно зависит от переменной xi, если выполняется условие
В этом случае также говорят, что переменная xi существенная, в противном случае ее называют фиктивной переменной.
Пример. Рассмотрим булеву функцию f(x1, x2, x3) и исследуем ее переменные x1 и x3.
Из таблиц истинности видно, что переменная x1 функции f(x1, x2, x3) существенная, так как f(0,x2, x3) ≠ f(1,x2, x3). Переменная x3 фиктивная, так как f(x1, x2, 0) = f(x1, x2, 1). •
Очевидно, что для выявления фиктивных переменных можно не строить в явном виде таблиц истинности левой и правой частей неравенства, а сравнивать соответствующие части вектора-столбца значений функции.
Алгоритм распознавания фиктивной переменной по таблице истинности.
– Для переменной x1 сравниваются половины столбца значений функции: верхняя и нижняя, так как именно в верхней половине x1=0, а в нижней x1=1, если они совпадают, то переменная x1 фиктивна;
– для переменной x2 сравниваются четвертины столбца в каждой половине, так как именно в верхних четвертинах x2 =0, а в нижних x2 =1, если четвертины в каждой половине совпадают, то переменная x2 фиктивна;
– и так далее (за четвертинами следуют 1/8, 1/16, … ).
Пример. Для булевой функции из предыдущего примера переменная x1 существенна, так как верхняя половина столбца значений функции (0011) не равна нижней половине (1100). Переменная x2 существенна, так как четвертины уже в первой половине различаются (00 и 11). Переменная x3 фиктивна, так как осьмушки во всех четвертинах равны (0 и 0, 1 и 1, 1 и 1, 0 и 0). •
Выявление фиктивных переменных можно ускорить, используя следующее очевидное утверждение.
Достаточное условие отсутствия фиктивных переменных. Если вес вектора-столбца значений функции нечетен, то функция не может содержать фиктивных переменных.
Алгоритм удаления фиктивной переменной xi состоит в вычеркивании из таблицы истинности всех строк, в которых xi = 0 (или всех строк, в которых xi = 1), и столбца xi.
Пример (функция та же). Применив алгоритм для удаления фиктивной переменой x3 (таблица слева), получаем результат (таблица справа).
Если переменная xi функции f(x1, …, xn) фиктивна, то на наборах, соседних по i компоненте, функция принимает одинаковые значения. Отсюда следует способ выявления и удаления фиктивной переменной функции, заданной матрицей Грея.
Алгоритм распознавания фиктивной переменной по матрице Грея (основан на свойстве симметрии кода Грея).
Переменная фиктивна тогда и только тогда, когда точки на матрице расположены симметрично относительно осей этой переменной. Упрощенная матрица – это одна из ее симметричных половин.
Пример (функция та же и представлена на левой матрице). Переменная x3 функции фиктивна. Справа показан результат ее удаления.
Определение. Булевы функции назовем равными с точностью до фиктивных переменных, если равны (в смысле, определенном ранее) функции, полученные из исходных удалением фиктивных переменных (и именно это расширенное толкование равенства функций мы будем иметь в виду во всех дальнейших рассуждениях).
Пример. Рассмотрим функции f1(x1, x2) и f2(x1, x2). Удалив фиктивную переменную x1 функции f1(x1, x2) и фиктивную переменную x2 функции f2(x1, x2), получим равные функции f1(x2)=f2(x1)=f(x). Значит, исходные функции равны с точностью до фиктивных переменных.
В вышеприведённых таблицах выделена графа «фиктивные переменные», т.е. переменные, от которых функция на самом деле не зависит. Остановимся на этом понятии подробнее.
Пример: Рассмотрим булевы функции 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, x1,…, xn-1), если существует хотя бы один набор (x1,…, xn-1) такой, что f(0, x1,…, xn-1) ≠ f(1, x1,…, xn-1)
В противном случае переменная называется фиктивной, или несущественной. Понятно, что в определении переменную можно ставить на любое место, и фиктивных переменных может быть несколько.
Ключевым понятием в теории булевых функций является понятие равенства функций. Для функций от одного и того же числа переменных нет необходимости рассматривать какое-то специальное определение равенства, ибо такие функции равны, если они совпадают как отображения одного о того же булева куба. Существование фиктивных переменных усложняет ситуацию, и проблема состоит в том, чтобы определить равенство булевых функций в целом, независимо от числа переменных.
Булевы функции f и g равны, если их существенные переменные совпадают и на каждом наборе значений этих переменных функции f и g принимают равные значения.
Кроме процедуры удаления фиктивных переменных используют и процедуру добавления к множеству переменных булевой функции одной или нескольких переменных.
В результате понятие фиктивной переменной позволяет любые две функции рассматривать как функции от одних и тех же переменных. Для этого надо рассмотреть объединение множеств переменных XUY и дополнить множества X и Y до объединения, вводя соответствующие переменные как фиктивные.
Нетрудно распространить описанную конструкцию на произвольное конечное множество функций и считать тем самым все функции этого множества функциями от одного и того же числа переменных.
Введём понятие проектирующей функции.
Функцию pri от n переменных, такую, что
называют (i-ой) проектирующей функцией. В общем случае нумерация множества переменных может быть не задана, и следует указывать не номер, а саму переменную.
Из определения следует, что проектирующая функция имеет единственную существенную переменную, а все остальные переменные проектирующей функции являются фиктивными. Далее мы всегда будем обозначать проектирующую функцию её символом – х, имея в виду возможность расширения на любое число переменных. Такое обозначение есть, конечно вольность, т.к. функция как бы отождествляется с аргументом. Отождествление функции и аргумента недопустимо, т.к. понятие переменной, хоть и связано с понятием функции, никак не есть частный случай понятия функции. Переменная – это имя, некий символ, но никак не функция. Тем не менее мы будем использовать это обозначение ради краткости.
Не нашли то, что искали? Воспользуйтесь поиском:
Вход в систему
Навигация
Последние комментарии
- ПСЗ
5 недель 4 дня назад - Наверное вот так вот ?
6 недель 5 дней назад - Спасибо
6 недель 5 дней назад - Эльдар
7 недель 4 дня назад - Умножение двух положительных чисел в Ассемблере МиК
7 недель 4 дня назад - Да
8 недель 16 часов назад - А вот почему, ВЛАД, .
8 недель 1 день назад - Почему? Я когда писал код,
8 недель 1 день назад - Продолжу.
8 недель 1 день назад - Снова Влад
8 недель 1 день назад
О существенных и фиктивных переменных булевых функций
Воспроизведём данное на лекции определение существенности переменной БФ.
Определение. Пусть задана некоторая БФ f(x1, x2, …,xk, …,xn).
Переменная xk этой функции называется существенной, если найдётся набор ДВОИЧНЫХ значений такой, что:
Рассмотрим пример. Пусть БФ f( x1, x2, x3) задана таблицей:
f( x1, x2, x3)
Исследуем переменные этой функции на существенность.
- x1– существенна, т.к., например, при f(x1, 0, 1), имеем f(0, 0, 1)=0, f(1, 0, 1)=1. Т.е. f(0, 0, 1) <>f(1, 0, 1). Здесь нашлись двоичные значения = такие, что f(0,a2,a3) <>f(1,a2,a3).
- x2– не существенна, т.к. f(a1, 0,a3) = f(a1, 1,a3)на любых наборах двоичных значениий (проверьте это по таблице!).
- x3– существенна, т.к., например, при f(0, 0,x3), имеем f(0, 0, 0)=1, f(0, 0, 1)=0. Т.е. f(0, 0, 0) <>f(0, 0, 1). Здесь нашлись двоичные значения = такие, что f(a1,a2, 0) <>f(a1,a2, 1).
Если в таблично заданной функции f( x1, x2, …,xk, …,xn), например, переменная xk — не существенна, то для исключения её из таблицы и, соответственно, уменьшения арности указанной функции, необходимо:
- вычеркнуть из таблицы столбец несущественной переменной xk;
- вычеркнуть из таблицы все строки, в пересечении которых с вычеркнутым столбцом стоят нули.
Так как x2 в выше приведённом примере – не существенна (фиктивна), то действуя так, как описано выше, её из таблицы можно исключить.
В результате получим таблицу:
f(x1, x3)
При желании, в полученной таблице, переменные, для удобства, можно переименовать, например, в x1, x2, или в x, y. На функцию, как на отображение, такие переименования никакого влияния не окажут.
Ясно, что выполняя описанные операции в обратном порядке, фиктивные переменные можно в таблицу включать, формально увеличивая, тем самым, арность задаваемой этой таблицей БФ.
Определение . Две булевы функции f1 и f2 будем называть равными (эквивалентными), если таблицу f2 можно получить из таблицы f1 путём добавления и/или изъятия фиктивных переменных, а также, возможно, переименования (любых) переменных.
В дальнейшем, БФ рассматриваются с точностью до их равенства (т.е. равные функции нами различаться не будут).
Если функции f1 и f2 равны, то этот факт будем обозначать как f1 = f2.
Замечание. Возможность добавления фиктивных переменных позволяет считать что БФ, образующие любое рассматриваемое конечное множество всегда имеют одну и ту же арность.
Критерий фиктивности переменной БФ.
Пусть БФ f(x1, x2, …,xk, …,xn) определена таблично. Для выявления фиктивности её переменной xk, удобно использовать следующий критерий:
- Вычислим величину L=2 n- k+1 ;
- Разобьём столбец значений функции (он последний в таблице) на равные отрезки длины L;
- Если в каждом из полученных на шаге 2 отрезке верхняя половина отрезка совпадает с нижней его половиной, то проверяемая переменная xk – фиктивна, иначе, она не фиктивна, т.е. существенна.
Задание. Убедитесь в том, что приведённый критерий работает, применив его к переменным x1, x2, x3 рассмотренного выше примера табличного задания БФ f( x1, x2, x3).