Фиктивные переменные дискретная математика

Фиктивные переменные дискретная математика

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

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

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

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

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

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

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

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

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

Пусть дана булева функция у = f(x1, . ,xn) от n переменных. Пусть существенными переменными этой функции являются переменные xi1, . ,xir, где r ≤ n и 1 ≤ i1 r в В, и для любого набора αi1, . , αir значенuй переменных xi1, . xir имеет место равенство

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

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

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

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

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

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

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

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

Читайте также:  Почему когда холодно часто хочется в туалет

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

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

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

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

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

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

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

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

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

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

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

Вместе с тем для двух различных переменных х и у проектирующие функции pr X x и pr Y x — разные функции. Так, pr1(x1,x2) — функция, отличная от функции pr2(x1,x2), поскольку, например, pr1(1,0) = 1, pr2(1,0) =0.

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

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

Читайте также:  Ru spbtv com мой профиль мои устройства

Определение. Говорят, что булева функция 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-ой) проектирующей функцией. В общем случае нумерация множества переменных может быть не задана, и следует указывать не номер, а саму переменную.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Ссылка на основную публикацию
Adblock detector