XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 62
Текст из файла (страница 62)
6.5). Рекомендуется проверить, что переменное хз является фиктивным и что остальные переменные существенны. Более того, анализ таблицы показывает, что эта функция есть не что иное, как мажоритарная функция, существенно зависящая от переменных ям хз и ял. Кроме процедуры удаления фиктивных переменных используют и процедуру добавления к множеству переменных булевой функции одной или нескольких фиктивных переменных.
Так, если дана функция,1(ям...,я„) Е Рг,„, то можно ввести новое фиктивное переменное д, определив новую, равную исходной, согласно определению 6.2, функцию от и+ 1 переменного таким образом: у(ям...,х~,д) = У(ям...,я~). (дЧд) (см. пример 6.4). б.з. Фиктивные нереыенные. Равенство булевых функций 391 Таблица 6.5 Следует заметить, что фиктивное переменное можно (в новой функции у) „поставить на любое место".
Или, говоря точнее, можно определить семейство функций Уо е = 1, и, с фиктивным переменным у так, что Яхм " у,х " х ) =у(хм " хн) А(дЧу) Понятие фиктивного переменного позволяет также произвольные две булевы функции рассматривать как функции от одного и того же числа переменных. Действительно, пусть функция у(хм...,хв) есть функция от п переменных, а функция д(дм...,дн,) — функция от тп переменных.
Обозначим множества переменных функции у и д через Х и У соответственно. Расширим множество переменных функции у до Х О У, вводя переменные из У '1 Х (если они 392 В. БУЛЕВЫ ФУНКЦИИ существуют) как фиктивные. Точно так же поступим с функцией д, добавляя фиктивные переменные из множества Х» г' (если, конечно, оно не пусто). Тогда получим функции у и д, равные, согласно определению 6.2, функциям ~ и д соответственно и определенные как функции от одного и того же числа переменных, составляющего ~Х 0 У~. Нетрудно распространить описанную конструкцию на произвольное конечное множество булевых функций и считать тем самым все функции этого множества функциями от одного и того же числа переменных.
В заключение рассмотрим понятие проектирующей функции. Функцию рг; от и переменных, такую, что рг;(хп...,х;,...,х„) =х;, называют (г»й) проентпируюи»еб фуннииег2. В общем случае нумерация множества переменных может быть явно не задана, и тогда при определении проектирующей функции следует указывать не номер соответствующего переменного, а само переменное. В этом случае проектирующая функция рг'г с множеством переменных Х этой функции и выделенным переменным х Е Х определяется так: Ргх (" ° ~х~".) = х (за многоточиями „скрыты" переменные проектирующей функции, отличные от переменного х).
Иэ определения следует, что проектирующая функция рг~ имеет единственное существенное переменное, а именно переменное х. Все остальные переменные проектирующей функции являются фикгвивными. Поэтому любые две проектирующие функции рг» и рг~~ равны, согласно определению 6.2, при любых множествах переменных Х и г, содержащих переменное х. Вместе с тем для двух различных переменньпг х и д проектирующие функции рг» и рг~~ — разные функции.
Так, 393 6.4. Формулы я суперпозиция рг (хмхз) — функция, отличная от функции ргз(хихон), поскольку, например, ргг(1,0) = 1, ргз(1,0) = О. Впредь договоримся любую из множества равных между собой проектирующих функций рг~~ обозначать символом х ее единственного существенного переменного. Замечание 6.3. Такое обозначение проектирующих функций есть условность и определенная вольность, состоящая в том, что проектирующая функция рг» как бы отождествляется с самим переменным х. Однако отождествление функции и переменного недопустимо, так как понятие переменного, хоть и связано с понятием функции, никак не есть частный случай понятия функции.
Переменное — только имя, некое обозначение, которое используется при аналитическом задании функции, но никак не сама функция. Тем не менее ради краткости, мы сохраним обозначение х как обозначение любой из проектирующих функций рг» и будем использовать иногда даже выражение „функция х", понимая под этим любую из указанного семейства проектярующих функций. 6.4.
Формулы и суперпозиции Табличный способ задания булевой функции не является эффективным. Им практически нельзя воспользоваться при большом числе переменных. Помимо этого способа существует способ представления булевых функций в виде формул. Этот способ аналогичен аналитическому способу задания функций действительного переменного [1). Как известно, в математическом аналюе мы исходили иэ определенного множества элементарных функций и строили ю них сложные функции, записывая их в виде формул, например: у = вш(гбх), у = 1п(совх), у = е 'вв<*+»я*~ и т.п. Аналогично обстоит дело для булевых функций, но только вместо элементарных функций математического анализа мы используем зле- 394 б. БУЛЕВЫ ФУНКЦИИ ментарные булевы функции — главным образом, те функции от одной и от двух переменных, которые мы определили в 6.1.
Но в отличие от математического анализа в теории булевых функций ставится задача представления любой булевой функции такой формулой, которая содержала бы строго определенное конечное множество элементарных булевых функций. Эти функции назовем пока условно „базисными функциями". Множества таких базисных функций могут быть разными, но, так вли иначе, мы хотим иметь нечто вроде функционального базиса (или множества таких базисов), через элементы которого можно было бы выразить любую булеву функцию.
Аналогичная задача не может быть решена для функций действительного переменого. Для булевых же функций задача оказывается разрешимой, и это обусловлено прежде всего тем, что булеза функция является конечной функцией. Чтобы математически точно сформулировать и решить поставленную выше задачу, нам необходимо уточнить понятие формулы. В анализе, поскольку там не возникала задача подобного рода, мы могли ограничиться интуитивной идеей формулы как некоего способа представления функции.
В теории булевых функций мы хотим доказывать утверждения вида „любая булева функция может быть представлена формулой над заданным множеством базисных функций Р". Но тогда нам нужно дать математическое определение „формулы над заданным множеством базисных функций Р ", а также уточнить, что значит „булеза функция представлена некоторой формулой". Кроме того, формулы обретают „самостоятельную жизнь" еще и потому, что одну и ту же булеву функцию можно представить, вообще говоря, разными формулами (как над одним и тем же базисом, так и над разными базисами). Тогда необходимо иметь механизм эквивалентного преобразования формул, т.е. перехода от заданной формулы, представляющей некоторую булеву функцию, к новой, скажем, более простой формуле, которая представляет ту же самую функцию.
395 6.4. Формулы и суперпоэипии Определение формулы основано на понятии сложной функции, или суперпозиции. Пусть булева функция у есть функция от п переменных, а булевы функции ды ..., д„— произвольные (и не обязательно различные) функции от одного и того же числа переменных, которое обозначим гп.
Определим функцию Дды...,д„), называемую сдперпозицией фдикций У, дм ..., д„так, что для любого а Е В"' имеет место равенство Таким образом, суперпозиция у (дм...,д„) есть не что иное, как ко.ипозипил булевых оверашорое д и ~, где булез оператор д задается семейством координатных функций д;, 4 = 1, и. Для суперпозиции ~(дм...,д„) используется также обозначение 8(~,ды...,д„). Предположение о том, что все функции д;, 4 = 1, и, — функции от одного и того же числа переменных, не ограничивает общности, поскольку, как было показано (см. 6.3), любое конечное множество булевых функций всегда можно рассматривать как множество функций от одного и того же числа переменных. Замечание 6.4. Обратим внимание на то, что в общем случае „уравнивание" числа переменных функций д,, 4 = 1, и, связано с добавлением фиктивных вереиеииых, а его, как известно, можно осуществлять разными способами. Поэтому суперпозиция Яды...,д„), вообще говоря, определена однозначно лишь с точностью до равенства булевых функций согласно определению 6.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
