5. Построение R-функций по заданной булевой функции

Как уже отмечалось, класс -функций к аргументов разделяется на ветвей К одной ветви относятся те -функции, которым соответствует одна и та же булева функция.

Таким образом, задача построения -функции по заданной булевой функции имеет бесчисленное множество решений.

Если требуется построить одну какую-нибудь Д-функцию из данной ветви, то задача может быть формально решена очень легко.

Пример 1. Пусть будет дана функция Тогда функция

есть -функция, соответствующая функции

В самом деле, функция равна нулю либо единице. Если она равна нулю, то функция (2.49)

равна отрицательна, если же она равна единице, то функция (2.49) равна единице, т. е. положительна. Следовательно

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

Наличие разрывов у -функций, построенных по такому правилу, создает известные неудобства при их практическом использовании. Однако, если бы основная трудность заключалась в наличии разрывов, то ее можно было бы легко устранить. В самом деле, умножая уравнение (2.49) на получим функцию, принадлежащую той же ветви, но уже непрерывную всюду. Если умножить эту же функцию на хтхп где целое число, и взять достаточно большим, можно получить многократно дифференцируемую Я-функ-цию из той же ветви.

Главный недостаток -функций, построенных по такому образцу, состоит в том, что они заданы в виде, неудобном с точки зрения применения к ним обычных аналитических методов исследования. Поэтому приходим к следующей задаче.

Пусть дана некоторая система базисных функций

и булева функция Требуется построить (если это возможно) -реализуемую функцию (гл. 1, 1), которая была бы -функцией, соответствующей заданной булевой функции

Если множество -реализуемых функций включает по крайней мере одну -функцию из каждой ветви класса 91, будем называть систему базисных функций полной относительно класса

Теорема 1. Система базисных функций является не полной по отношению к классу -функций

Достаточно показать, что с помощью сложения и умножения нельзя построить -функцию, соответствующую конъюнкции Предположим противное, что полином

соответствует конъюнкции.

Перейдем к полярным координатам

Тригонометрический полином

не равен тождественно нулю, так как по условию полином имеет степень.

Пусть где — произвольный угол, такой, что . В точках луча достаточно удаленных от начала координат, знак полинома совпадает со знаком величины Так как по предположению полином есть -функция, соответствующая конъюнкции, то функция должна быть неотрицательна в первой четверти, и неположительна — в остальных. Рассмотрим вначале случай, когда четное число. Пусть есть угол в первой четверти, такой что Так как то функция принимает положительные значения в третьей четверти. Приходим к противоречию.

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

Таким образом, есть такие ветви -функций, которые не содержат ни одной функции, представимой в виде целой рациональной функции.

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

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

Таблица 6

Из табл. 6 видно, что функция

соответствует операции Шеффера.

В гл. 1 было показано, что с помощью операции Шеффера можно построить любую булеву функцию. Следовательно, с помощью функции может быть построена -функция, принадлежащая любой наперед заданной ветви класса -функций. Это построение может быть осуществлено следующим образом.

Дана булева функция Эту функцию запишем с помощью одной лишь операции Шеффера (это возможно сделать, например, так: привести функцию к дизъюнктивной нормальной форме, а затем конъюнкцию, дизъюнкцию и отрицание выразить через операцию Шеффера). Затем заменим булевы переменные на непрерывные переменные а знак операции Шеффера знаком операции Полученная функция будет -функцией, соответствующей булевой функции

Пример 2. Построить R-функцию, соответствующую булевой функции

Перепишем данную булеву функцию в виде

Соответствующую -функцию запишем

или

Так как функция может быть построена с помощью функций

то система (2.59), если принять ее в качестве базисной, будет полной по отношению к множеству -функций.

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

Теорема 3. Всякая -реализуемая функция не имеет других нулей, кроме тех, в любой окрестности которых она принимает значения разных знаков.

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

поступают аргументы обязательно различные на разных входах). В точках соединения происходит обработка поступающих входных величин по формуле (2.55). На выходе графа получаем -функцию Таким образом,

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

Рис. 2.

Наконец окажется, что должен быть равен нулю один из аргументов, например, Величина поступает на один из входов функции (2.55), а на другой вход поступает какая-то неотрицательная величина Так как в окрестности точки аргумент принимает значения разных знаков, то функция в окрестности точки также принимает значения разных знаков. Функция поступает на один из входов функции (2.55), а на другой вход поступает некоторая неотрицательная величина Так как в окрестности точки принимает значения разных знаков, то функция также принимает значения разных знаков в окрестности точки и т. д. Наконец приходим к выводу, что функция принимает значения разных знаков в окрестности точки

Теорема 4. Если непрерывная -функция в окрестности своих нулей принимает значения разных знаков, то какова бы ни была принадлежащая той же зетви, что и функция

-функция , непрерывная в точках, принадлежащих координатным гиперплоскостям, найдется такая неотрицательная функция что имеет место тождество

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

Из теорем 2 и 3 следует, что умножая любую реализуемую функцию на соответствующим образом подобранную функцию можно получить любую непрерывную Д-функцию, принадлежащую той же ветви, что и функция

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