Как выразить функцию через функцию

Полные системы функций. Теорема Поста о полной системе функций

Содержание

Полные системы функций [ править ]

Американский математик Эмиль Пост сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:

Замкнутые классы булевых функций [ править ]

Количество линейных функций от [math]n[/math] переменных равно [math]

Функция является линейной тогда, и только тогда, когда в ее полиноме Жегалкина присутствуют слагаемые, каждое из которых зависит не более чем от одной переменной. Построить полином Жегалкина можно с помощью преобразования Мебиуса.

Формулировка и доказательство критерия Поста [ править ]

Необходимость.

Заметим, что необходимость этого утверждения очевидна, так как если бы все функции из набора [math]K[/math] входили в один из перечисленных классов, то и все суперпозиции, а, значит, и замыкание набора входило бы в этот класс, и набор [math]K[/math] не мог бы быть полным.

Достаточность.

Докажем, что если набор [math]K[/math] не содержится полностью ни в одном из данных классов, то он является полным.

Таким образом, возможны четыре варианта:

Рассмотрим несколько вариантов:

Значит, полученные функции образуют полную систему, поскольку с их помощью можно выразить любую булеву функцию. Из этого следует, что K — полная система функций, что и требовалось доказать.[math]\triangleleft[/math]

Примеры [ править ]

В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера или стрелку Пирса.

Широко известны такие полные системы булевых функций:

Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

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

Теорема о максимальном числе функций в базисе: максимально возможное число булевых функций в базисе — четыре.

Иногда говорят о системе функций, полной в некотором замкнутом классе, и, соответственно, о базисе этого класса. Например, систему [math]\left\<\oplus,1\right\>[/math] можно назвать базисом класса линейных функций.

Источник

Суперпозиции

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

Содержание

Способы получения суперпозиций [ править ]

Тогда мы можем получить новую функцию из имеющихся двумя способами:

Подстановка одной функции в другую [ править ]

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

Отождествление переменных [ править ]

[math] f(a,b) = a \vee b [/math] — исходная функция

[math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами

Очевидно, в данном примере мы получили функцию [math]P_<1>[/math] — проектор единственного аргумента.

Источник

задан 5 Янв ’17 15:55

explicit
45 ● 2 ● 13
0&#037 принятых

@explicit: если ответ положительный, то явное выражение подбирается или угадывается. Типовой пример: выразить дизъюнкцию через конъюнкцию и отрицание. Достаточно знать закон де Моргана и закон двойного отрицания, чтобы сообразить, что xVy=not(not(x)&not(y)). Когда ответ отрицательный, техника применяется другая. Есть понятие замкнутого класса функций: это значит, что при подстановке мы всё время получаем функции из того же класса. Нужно знать «ходовые» примеры замкнутых классов. Пример: импликация невыразима через дизъюнкцию. Почему? Дизъюнкция сохраняет 0, а импликация не сохраняет.

@explicit: замкнутых классов больше, чем пяти перечисленных, хотя эти наиболее важны. Я не могу утверждать, что такая проверка обязательно необходима. Но если ответ отрицательный, то какой-то из этих пяти классов вполне может помочь. Если окажется, что мы хотим выразить, например, немонотонную функцию через заведомо монотонные, то это даёт решение. Только не надо здесь ничего пытаться «алгоритмизировать». Достаточно знать и уметь применять типовой набор приёмов.

Только что обратил внимание на самый верхний комментарий. Все критерии нужно брать из авторитетных источников. Если мы можем указать замкнутый класс K такой, что f не принадлежит K и g принадлежит, то f невыразима через g. Но это дело работает только в одну сторону. Если функции f и g не отличаются ни по одному из пяти признаков, то про выразимость нельзя сказать ничего определённого. Таких критериев нет.

В одной из работ Поста есть описание всех замкнутых классов. То есть такой алгоритм существует, но им непросто пользоваться.

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

Источник

ТЕМА: ПОЛНОТА МНОЖЕСТВА ФУНКЦИЙ.

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

3. Независимые системы. Базис замкнутого класса.

1. Полная система. Достаточное условие полноты.

Познакомясь с понятиями ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина выяснили, что любую булеву функцию можно выразить в виде формулы через элементарные функции : отрицание, конъюнкцию, дизъюнкцию, двоичное сложение и константу 0 или 1.

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

Возникает вопрос: в какой мере является случайным наличие таких систем элементарных функций?

Дадим определение таких систем.

Система булевых функций 1, f₂, …, f_m> называется полной, если любая булева функция может быть выражена через функции этой системы с помощью составления из них сложных функций.

Составление сложных функций из элементарных функций системы называется суперпозицией.

Познакомимся с достаточным условием полноты системы.

Полнота первой системы следует из того, что любую булеву функцию можно представить в виде ДНФ или КНФ.

С помощью той же полной системы докажем полноту <-, L>. Для этого нужно выразить дизъюнкцию:

Для доказательства полноты системы <-, ®>воспользуемся полной системой <-, V>. Выразим дизъюнкцию: Полнота доказана.

Для доказательства полноты системы за полную примем, например, <-, L>. Выразим отрицание и конъюнкцию через штрих Шеффера:

При доказательстве полноты системы за полную систему примем <-, V>. Выразим обе функции через стрелку Пирса:

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

Мы рассмотрели лишь достаточное условие полноты системы. Перейдем теперь к установлению критерия полноты. Прежде познакомимся с понятиями замыкания и замкнутого класса.

Пусть К – некоторое подмножество элементарных функций. Замыканием подмножества К называется множество булевых функций, представимых в виде формул через функции К. Обозначение замыкания : [K].

Можно теперь сформулировать еще одно определение полной системы:

Множество К называется функционально замкнутым (или просто замкнутым), если его замыкание – само множество К..

Дадим еще одно определение замкнутого множества (класса).

Класс К булевых функций называется замкнутым, если вместе с функциями из этого класса он содержит и все их суперпозиции, т.е. элементарные суперпозиции не выводят из этого класса. К элементарным суперпозициям относятся:

1. переименование некоторой переменной какой-нибудь функции рассматриваемой системы;

2. подстановка некоторой функции из этой системы вместо некоторой переменной любой из функции этой системы.

К замкнутым классам относятся: множество всех булевых функций Р₂; класс функций от одной переменной; класс, содержащий только тождественные функции вида f(X)=X.

Приведем следующее утверждение:

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

Рассмотрим некоторые функционально замкнутые классы функций, которые называются важнейшими замкнутыми классами. Они используются в критерии полноты.

Класс Т₀ – класс функций, сохраняющих 0, т.е. f(0,0,…0)=0.

Примеры функций, принадлежащих к Т₀: 0, х, ху=00=0, xvy=0v0=0, x+y=0+0=0.

Функции, не принадлежащие к Т₀: 1, x|y=0|0=1, x¯y=0¯0=1.

Класс Т₁— класс функций, сохраняющих 1, т.е. f(1,1,…,1)=1.

Примеры функций, не принадлежащих классу Т₁: 0, x|y=1|1=0, x¯y=1¯1=0.

Класс S – класс самодвойственных функций.

Самодвойственной функцией называется функция f(x₁, x₂, …,x_n), если f(x₁, x₂, …,x_n) º f*(x₁, x₂, …,x_n), где .

Функции ху, xvy, x®y не относятся к самодвойственным функциям.

Класс L – класс линейных функций.

Функция называется линейной, если равносильная ей функция, являющаяся полиномом содержит конъюнкции не выше первой степени, т. е.

К линейным относятся: 1, 0, х, , х+у.

Функции не линейные.

Класс монотонных функций M.

Введем отношение частичного порядка на множестве упорядоченных наборов (векторов).

Например, , т.к. 1£1, 0 £ 1, 1 £ 1. векторы (01) и (10) – не сравнимы.

Говорят так же, что a и b сравнимы.

Функция f(x₁, x₂, …,x_n) называется монотонной, если любых векторов a и b списка переменных таких, что , имеем f(a)£ f(b).

К монотонным относятся, например, функции : х, ху, xvy.

Проверим монотонность xy и xvy. Составим таблицы истинности :

По таблице истинности легко установить монотонность и этой функции.

Функция х®у не является монотонной, т.к. , но f(00)=1, a f(10)=0.

Любые элементарные суперпозиции не выводят из рассмотренных классов. Тем самым доказывается их функциональная замкнутость.

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

Для того, чтобы система булевых функций была полной, необходимо и достаточно, чтобы для каждого из классов Т₀, Т₁, S, L, M нашлась функция f_i из этой системы не принадлежащая этому классу.

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

Рассмотрим пример: докажем полноту системы <+, v, 1,0>.

Для 0 и 1 таблица заполняется тривиально. Не составляет труда проверить принадлежность х+у и xvy к Т₀ и Т₁. Более подробно покажем заполнение оставшихся ячеек.

S: , значит, х+уÏS;

M: составим таблицу истинности:

Функция не монотонная, т.к., например, , а f(01)>f(11).

S: для xvy двойственной является ху, следовательно, х+уÏS;

L: , значит, xvyÏL;

Принадлежность этой функции мы уже доказали в выше рассмотренном примере.

Итак, т.к. в каждом столбце есть хотя бы один минус, означает полноту данной системы.

3. Независимые системы. Базис замкнутого класса.

Система функций G называется независимой, если никакая функция fÎG не представима суперпозициями функций из G\f.

Примеры независимых систем:

Независимая система функций G называется базисом замкнутого класса К, если всякая функция из К есть суперпозиция функций из G.

Например, системы <-, V>, <-, L>являются базисом для класса Р₂, т.к. системы полные и независимые.

Система <+, v, 1,0>не является базисом для Р₂, т.к. хотя она полная, но не является независимой: можно удалить 0. значит базисом для Р₂ является система <+, v, 1>.

Функции, образующие базис во множестве всех булевых функций Р₂, называются шефферовыми функциями.

Например, функции x|y и х¯у – шефферовые, т.к. каждая из них образует полную систему (было доказано выше), причем, независимую.

Функция х®у не является шефферовой, т. к. не образует полную систему: 1®1=1, т.е. х®уÎТ₁.

Задачи для самостоятельного решения.

1. Выразить импликацию через функции системы <1, +, L>.

2. Выразить дизъюнкцию и конъюнкцию через функции системы <-, ®>.

3. С помощью достаточного условия полноты проверить на полноту систему а) <0, v, ®>; б) <-, «>; в) <0, +, L>.

5. Является ли система <1,0,+,L>базисом множества всех булевых функций?

6. Являются ли функции х«у, ху, xvy, шефферовыми функциями?

1. Что называется замыканием множества булевых функций?

2. Перечислить свойства замыкания.

3. Что такое суперпозиция? Какие суперпозиции относятся к элементарным?

4. Сформулировать два определения функционально замкнутого класса.

6. Перечислить все важнейшие замкнутые классы. Привести примеры функций принадлежащих и не принадлежащих к каждому замкнутому классу.

7. Сформулировать теорему Поста. Что собой представляет таблица Поста?

8. Какая система булевых функций называется независимой?

Источник

Производящие функции — туда и обратно

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

Введение

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

Идея производящих функций достаточно проста: сопоставим некоторой последовательности — дискретному объекту, степенной ряд g₀ + g₁z + g₂z 2 +… + g_nz n +… — объект непрерывный, тем самым мы подключаем к решению задачи целый арсенал средств математического анализа. Обычно говорят, последовательность генерируется, порождается производящей функцией. Важно понимать, что это символьная конструкция, то есть вместо символа z может быть любой объект, для которого определены операции сложения и умножения.

История возникновения производящих функций

Известно, что начало методу производящих функций положил английский математик Абрахам де Муавр, а дальнейшему развитию и продолжению данного метода мы обязаны великому математику, имя которого Леонард Эйлер.

Метод производящих функций

Изучение этого мощного механизма позволяющего решать многие задачи, мы начнём с простенькой задачи: сколькими способами можно расположить в линию чёрные и белые шары, общее количество которых равно n?

Обозначим белый шар символом ○, чёрный — ●, T_n — искомое количество расположений шаров. Символом Ø — обозначим нулевое количество шаров. Как и любое решение комбинаторной задачи начнём с тривиальных случаев:

Если n=1, то очевидно имеется 2 способа — взять либо белый шар ○, либо взять чёрный шар ●, таким образом, T₂ = 2.

Если n=2, то имеется 4 способа расположений: ○○, ○●, ●○, ●●.

Рассмотрим случай для n=3. Мы можем начать белым шаром и продолжить 4-мя комбинациями, описанными выше ○○○, ○○●, ○●○, ○●●, или же мы можем начать чёрным шаром и аналогично продолжить 4-мя шарами ●○○, ●○●, ●●○, ●●●.

В итоге количество шаров удвоилось, то есть T₃ = 2T₂. Аналогично T₄ = 2T₃, то есть, обобщая для всех n, получаем рекуррентное уравнение T_n = 2T_n-1 которое и является решением для данной задачи. Решение такого уравнения можно легко угадать — T_n = 2 n (так как 2⋅2 n-1 = 2 n ).

А что если у нас плохо с угадыванием? И что делать, если уравнение будет сложнее? А вообще причём здесь производящие функции?

«Просуммируем» все возможные комбинации расположений шаров:

Вопрос о допустимости такой нелепой на первый взгляд суммы опустим. Будем складывать и умножать последовательности шаров. Со сложением всё понятно, но что значит умножить одну последовательность шаров на другую? Перемножив ○● на ●○ мы получим не что иное как ○●●○. Заметим, однако, что произведение шаров в отличие от произведения чисел не является коммутативным, так как ○●⋅●○ ≠ ●○⋅○●. Символ Ø — в произведении играет роль мультипликативной единицы, то есть Ø ⋅ ○○● = ○○● ⋅ Ø = ○○● и коммутирует с любой последовательностью шаров.

Производя с рядом G последовательность манипуляций, а именно вынося за скобки левый белый и чёрный шары

получим уравнение G = Ø + ○G +●G.

Несмотря на то, что умножение некоммутативно, и мы фактически не различаем левое и правое деление, попробуем всё же «решить» это уравнение, на свой страх и риск. Получим,

Учитывая формулу суммы геометрической прогрессии , имеем

.

В этой сумме так же учтены все возможные варианты разбиения в точности по одному разу. Далее воспользуемся формулой бинома Ньютона: , где — число сочетаний из n по k. Тогда с учетом этого имеем:

Коэффициент при ○ k ● n-k равный числу сочетаний из n по k, показывает общее количество последовательностей из n шаров содержащих ○ шары в количеств k штук и ● шары в количестве n-k штук. Таким образом, общее количество расположений n шаров есть сумма по всем возможным значениям k. Как известно .

Обсуждение метода

Так что же позволяет данному методу быть работоспособным при решении различных задач?

Алгоритм решения задачи можно описать примерно следующим образом: рассматривается некоторая бесконечная сумма, которая в конечном итоге представляет собой формальный степенной ряд G(z) = g₀ + g₁z + g₂z 2 +… + g_nz n +… причем коэффициенты g_k (не заданные в явном виде) — являются ключом к решению исходной задачи. То, что ряд является формальным, говорит о том, что z — является просто символом, то есть вместо него может быть любой объект: число, шар, кость домино и т.д. В отличие от степенных рядов в анализе формальным степенным рядам не придается числовых значений и, соответственно, нет смысла говорить о сходимости таких рядов для числовых аргументов.

Затем производя различные преобразования с бесконечной суммой G(z) мы преобразуем её к замкнутому (компактному) виду. То есть у производящей функции есть 2 представления: бесконечное и замкнутое и, как правило, для решения задачи необходимо бесконечный вид преобразовать к замкнутому, а затем замкнутый вид разложить в степенной ряд, и тем самым получить значения для коэффициентов g_k.

А теперь вооружившись знаниями, вернемся к задаче, которую решал Эйлер.

Я не знаю, как долго Эйлер придумывал решение для этой задачи, но оно поражает своей неожиданностью. Посудите сами. Эйлер рассматривает произведение G(z) = (1+z)(1+z 2 )(1+z 4 )… которое после раскрытия скобок представляется в виде бесконечного ряда G(z) = 1 + g₁z + g₂z 2 + g₃z 3 +….

Следующий шаг Эйлера поражает не менее предыдущего. Он умножает обе части равенства на (1-z).

(1-z)G(z) = (1-z)(1+z)(1+z 2 )(1+z 4 )(1+z 8 )…
(1-z)G(z) = (1-z2)(1+z 2 )(1+z 4 )(1+z 8 )…
(1-z)G(z) = (1-z 4 )(1+z 4 )(1+z 8 )…
(1-z)G(z) = 1

С одной стороны G(z) = 1 + g₁z + g₂z 2 + g₃z 3 +… с другой стороны мы только что получили . Последнее равенство есть не что иное, как сумма геометрической прогрессии, которая равна . Сопоставляя эти два равенства, получаем g₁ = g₂ = g₃ =… = 1, то есть любой груз в k грамм можно взвесить гирями в 1, 2, 4, 8,… грамм притом единственным способом.

Решение рекуррентных соотношений

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

Начнем со всеми знакомой последовательностью чисел Фибоначчи. Каждый из нас знает её рекуррентный вид: F₀ = 0, F₁ = 1, F_n = F_n-1 + F_n-2, n ≥ 2. Однако не каждый знает вид этой формулы в замкнутом виде и это не удивительно, ведь она содержит иррациональное число(«золотое сечение») в своём составе.

Просуммируем эти равенства:

Обозначим левую часть

Рассмотрим каждое из слагаемых в правой части:

Имеем следующее уравнение G(z) = z + z G(z) + z 2 G(z) решая которое относительно G(z) находим

— производящая функция для последовательности чисел Фибоначчи.

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

Следующим шагом является нахождение коэффициентов a и b. Для этого умножим дроби на общий знаменатель:

Подставляя в это уравнение значение z = z₁ и z = z₂, находим

Напоследок немного преобразуем выражение для производящей функции

Теперь каждая из дробей представляет собой сумму геометрической прогрессии.

По формуле находим

Но ведь мы искали G(z) в виде . Отсюда делаем вывод, что

Эту формулу можно переписать в другом виде не используя «золотое сечение»:

что достаточно трудно было ожидать, учитывая красивое рекуррентное уравнение.

Давайте запишем общий алгоритм решения рекуррентных уравнений, используя производящие функции. Он записывается в 4 шага:

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

Дифференцирование и интегрирование производящих функций

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

Пусть G = G(z) – производящая функция. Производной этой функции называется функция . Дифференцирование, очевидно, линейная операция, поэтому для того, чтобы понять, как оно действует на производящих функциях, достаточно посмотреть на его действие, на степенях переменной. Имеем

Тем самым, действие дифференцирования на произвольной производящей функции
G (z) = g₀ + g₁z + g₂z 2 + g₃z 3 +… дает G΄(z) = g₁ + 2g₂z + 3g₃z 2 + 4g₄z 3 +….

Интегралом называется функция

Операция дифференцирования обратна операции интегрирования:

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

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

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

Будем следовать вышеописанному алгоритму. Первое условие алгоритма выполнено. Умножим обе части всех равенств на z в соответствующей степени и просуммируем:

z 0 ⋅ g₀ = 1,
z 1 ⋅ g₁ = z,
z n ⋅ g_n = z n ⋅ g_n-1 + 2z n ⋅ g_n-2 + (-1) n ⋅ z n

Левая часть представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через G(z). Рассмотрим каждое слагаемое:

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений z), получаем:

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

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

С одной стороны мы искали G(z) в виде , с другой стороны .

Значит, .

Вместо заключения

Возводя в квадрат обе части этого равенства получим

Приравнивая коэффициенты при x n в левой и правой частях, получаем

Эта формула имеет прозрачный комбинаторный смысл, но доказать её непросто. Еще в 80-е годы XX века появились публикации, посвященный этому вопросу.

Источник