Лабораторный практикум № 1. дискретка. Отображения. Обратные отображения эта тема является очень важной, терминами из этой темы мы будем пользоваться во многих других вопросах
 Скачать 86.29 Kb.
|
|
20. МАКСИМАЛЬНЫЕ КОНЪЮНКЦИИ У каждой конъюнкции 𝐾 есть какое-то своё множество 𝑁𝐾, которое содержит двоичные наборы, на которых конъюнкция 𝐾 истинна. Также существуют конъюнкции 𝐾𝑖 , у которых множество 𝑁𝐾𝑖 содержит множество 𝑁𝐾, а также какието свои элементы в виде двоичных наборов. Та из конъюнкций 𝐾𝑖 , которая содержит множество 𝑁𝐾 и при этом является минимальной в своей записи (а значит, (конец темы 19) имеет максимальную по размерности грань в геометрической интерпретации), и будет максимальной для 𝑁𝐾. Дадим определение максимальной конъюнкции. Пусть есть функция 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) ∈ 𝑃2 𝑛 . Элементарная конъюнкция 𝐾 называется максимальной для ФАЛ 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ), если для неё выполняются 2 условия: 1) 𝑁𝐾 ⊆ 𝑁𝑓 (то есть нет таких наборов, на которых бы конъюнкция принимала значение 1, а функция – 0. Проще говоря, это условие означает то, что эта конъюнкция содержится в ДНФ этой функции) 2) ∀𝐾1 (𝑁𝐾 ⊂ 𝑁𝐾1 → 𝑁𝐾1 ⊈ 𝑁𝑓). То есть если мы возьмём любую другую конъюнкцию 𝐾1 такую, что |𝑁𝐾| < |𝑁𝐾1 | (количество вершин множества 𝑁𝐾 меньше количества вершин множества 𝑁𝐾1), то у этой конъюнкции найдётся набор, на котором она будет принимать значение 1, а функция – 0 (то есть эта конъюнкция не будет содержаться в ДНФ этой функции). Из этого условия следует, что максимальная конъюнкция не может быть сокращена в своей записи в ДНФ функции. ТЕОРЕМА. Если 𝐷 = 𝐾1 𝐾2 … KS - минимальная ДНФ для 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ), то каждая элементарная конъюнкция в 𝐷 является максимальной конъюнкцией для ФАЛ 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ). ДОКАЗАТЕЛЬСТВО. Теорема доказывается методом от противного. Пусть есть хотя бы одна конъюнкция из минимальной ДНФ, не являющаяся максимальной (обозначим как 𝐾𝑖 ). Тогда для этой конъюнкции не выполняется определение максимальной конъюнкции. Напишем отрицание второго условия из определения максимальной конъюнкции: ∃𝐾 (𝑁𝐾𝑖 ⊂ 𝑁𝐾 & 𝑁𝐾 ⊆ 𝑁𝑓) (определение представляет собой импликацию из утверждений 𝑎 → 𝑏 = 𝑎 b, поэтому 𝑎 → 𝑏 = 𝑎&𝑏). То есть будем рассматривать соответствующую конъюнкции 𝐾𝑖 максимальную конъюнкцию 𝐾. Теперь рассмотрим новую ДНФ D1, получаемую из D заменой конъюнкции 𝐾𝑖 на максимальную конъюнкцию 𝐾. ДНФ D1 будет меньше по сложности, чем ДНФ D (так как максимальная конъюнкция будет меньше по записи, чем 𝐾𝑖 ). Казалось бы, на этом можно было уже получать противоречие, так как ДНФ D является минимальной. Но есть один момент: мы должны убедиться в том, действительно ли ДНФ D1 представляет нашу рассматриваемую функцию 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) (это одно из условий определения ДНФ). То есть мы должны убедиться в том, что 𝑁𝐷1 = 𝑁𝐷 = 𝑁𝑓. Для доказательства равенства 𝑁𝐷1 = 𝑁𝐷 мы должны доказать 2 вложения: 𝑁𝐷1 ⊆ 𝑁𝐷 и 𝑁𝐷 ⊆ 𝑁𝐷1. Мы будем опираться на ключевое соотношение 𝑁𝐾𝑖 ⊂ 𝑁𝐾 ⊆ 𝑁𝑓 или подругому 𝑁𝐾𝑖 ⊂ 𝑁𝐾 ⊆ 𝑁𝐷. 1) Доказываем 𝑁𝐷1 ⊆ 𝑁𝐷. Так как 𝑁𝐾 ⊆ 𝑁𝑓 (то есть 𝑁𝐾 ⊆ 𝑁𝐷, так как 𝑁𝑓 = 𝑁𝐷), то в ДНФ D после замены конъюнкций все двоичные наборы, на которых эта ДНФ истинна, остались (если на каком-то наборе ДНФ была истинна, то после замены конъюнкций на этом же наборе эта ДНФ останется всё равно истинной). 2) Доказываем 𝑁𝐷 ⊆ 𝑁𝐷1. Из ДНФ D мы получаем ДНФ D1, причём заменяется только конъюнкция 𝐾𝑖 на максимальную конъюнкцию 𝐾 (остальное всё осталось как прежде). Мы имеем вложение 𝑁𝐾𝑖 ⊂ 𝑁𝐾 . Из этого следует, что возможно два случая: либо 𝑁𝐷 ⊂ 𝑁𝐷1, либо 𝑁𝐷 ⊆ 𝑁𝐷1. Но если будет выполняться первое, то мы имеем два вложения 𝑁𝐷 ⊂ 𝑁𝐷1 и 𝑁𝐷1 ⊆ 𝑁𝐷, которые противоречат друг другу (из строгого вложения следует, к примеру, что 𝑁𝐷1 содержит хотя бы на один элемент больше, чем 𝑁𝐷, но в то же время 𝑁𝐷1 по нестрогому вложению должно быть подмножеством 𝑁𝐷). Поэтому всё же получаем, что 𝑁𝐷 ⊆ 𝑁𝐷1. На самом деле я немного не понял, как это доказывал Костенко, но кажется здесь всё логично. Мы получили, что 𝑁𝐷1 = 𝑁𝐷 = 𝑁𝑓, и значит, D1 представляет функцию 𝑓. Поэтому D1 – тоже ДНФ этой функции, причём её сложность (как мы выяснили ранее) меньше сложности минимальной ДНФ. Здесь и получаем противоречие. Теорема доказана. 21. ПОЛНЫЕ СИСТЕМЫ ФУНКЦИЙ. ТЕОРЕМА РЕДУКЦИИ. Теперь познакомимся с ещё одним важным понятием, которое пригодится в следующих вопросах – замыкание множеств. Но перед этим нужно повторить определение формулы над множеством элементарных функций (тема 14). Я лишь кое-что добавлю: одна и та же функция может представляться разными формулами. Но одна какая-то формула может реализовывать только одну функцию. Например: первая формула U1 = 𝑥1 → 𝑥2 , вторая формула U2 = 𝑥1&𝑥2. Если построить табличное задание для этих формул, то нетрудно убедиться, что они будут представлять одну и ту же функцию – отрицание импликации (поскольку столбец значений функции и там и там один и тот же). Нам также в последующих темах может понадобиться таблицы с табличным заданием функций от 1 и 2 переменных (Костенко давал под запись эти таблицы, где-то в начале лекций по алгебре логики). При подстановке вместо переменных в формуле произвольных двоичных наборов получаются некоторые значения (0 или 1). И то множество значений, которое получается при подстановке соответствующих этим значениям двоичных наборов, и является определённой функцией. В этом случае говорят, что формула реализует функцию. Пусть у нас есть система функций B ⊆ P2. Система функций является множеством, элементы которого – функции алгебры логики. Из функций мы можем составлять различные формулы. Например, пусть в B входят функции &, +, , →. Мы можем из этих функций составить, к примеру, формулу (𝑥1&𝑥2) → 𝑥1 (необязательно, чтобы все функции из множества В участвовали в записи формулы). А теперь строим табличное задание и смотрим, какую функцию f реализует эта формула. Эта функция f и будет элементом замыкания множества В. То есть замыкание состоит из функций, которые реализуются формулами над В. В данном примере формула реализует константу 1 (так как при подстановке всех двоичных наборов из двух переменных получаются значения 1, что является признаком того, что это функция-константа 1) и она принадлежит замыканию множества В. Если бы, например, при подстановке набора 00 и 11 выдавало бы значение 1, а при 01 и 10 – 0, то это была бы функция эквиваленции и данная формула реализовывала бы эквиваленцию. Если бы, например, при подстановке набора 00 выдавало бы значение 0, а при 01, 10 и 11 – 1, то это была бы дизъюнкция и данная формула реализовывала бы дизъюнкцию. Разберём ещё один пример. Мы прошли тему разложения ФАЛ по переменным. Из неё вы выяснили в итоге, что любую функцию алгебры логики можно представить в виде определённой совокупности трёх функций: отрицания, конъюнкции и дизъюнкции. То есть любая функция алгебры логики реализуется формулой, составленной из отрицания, конъюнкции и дизъюнкции. А это означает, что замыкание множества из отрицания, конъюнкции и дизъюнкции равно множеству P2 (множеству всех функций алгебры логики). Определение. Пусть B ⊆ P2. Замыканием множества В называется множество [B], составленное из всех функций, представимых формулами над В. Определение. B ⊆ P2 – полная система ФАЛ, если [B] = P2 (то есть можно получить все функции алгебры логики путём составления формул из функций множества В). Как раз множество из отрицания, конъюнкции и дизъюнкции является полной системой ФАЛ. Определение. B ⊆ P2 – замкнутая система, если [B] = B (Понятие замкнутой системы пригодится в темах про классы функций. Это понятие означает, что какую бы формулу мы бы не составили из функций множества В, эта формула всегда реализует функцию, принадлежащую множеству В). Примером такой системы будет система из двух функций: тождественной функции и отрицания (𝑥 и 𝑥). Из них никак, к примеру, дизъюнкцию, конъюнкцию, импликацию, эквиваленцию не получишь, можно получить из них только либо тождественную функцию, либо отрицание. 22. ПОЛИНОМЫ ЖЕГАЛКИНА Полиномы Жегалкина очень сильно напоминают обычные полиномы, которые изучались в школе. Только здесь идёт работа с выражениями, принимающими при определённых значениях переменных значения 0 или 1. Преобразования в полиномах Жегалкина тоже аналогичны преобразованиям обычных полиномов: 1) мы можем раскрывать скобки, приводить подобные слагаемые, и в итоге у нас получится произведение каких-то слагаемых с переменными и свободных членов (свободные члены тут могут быть только единицы и нули) 2) также здесь используются соотношения эквивалентности; например, может быть ситуация, когда мы получили слагаемое x&x, но по соотношению эквивалентности это просто х; если у нас х + х, то это равно 0 (по табличному заданию суммы по модулю 2) и эти слагаемые удаляются; также следует в каждом слагаемом писать переменные в порядке возрастания их индексов. Причём, так как эти преобразования являются эквивалентными, то любая функция представляется хотя бы одним полиномом Жегалкина (на самом деле единственным, это доказывается ниже). Если у нас, например, функция от 2 переменных, то полином Жегалкина для неё будет содержать 4 вида слагаемых: где есть произведение этих двух переменных, где есть только первая переменная, где есть только вторая переменная и где нет ни первой, ни второй переменной: 𝛼𝑥1𝑥2 + 𝛽𝑥1 + 𝛾𝑥2 + 𝛿 (𝛼, 𝛽, 𝛾, 𝛿 - просто коэффициенты, которые равны 0 или 1). ТЕОРЕМА. Всякая булева функция представляется единственным полиномом Жегалкина. ДОКАЗАТЕЛЬСТВО. Посчитаем сначала количество всевозможных полиномов Жегалкина от n переменных. Рассмотрим для наглядности сначала n = 4. В полиноме Жегалкина от 4 переменных будут следующие виды слагаемых: где есть произведение всех 4 переменных (таких слагаемых 𝐶4 4 = 1), где есть произведение трёх переменных (𝐶4 3 произведений), где есть произведение двух переменных (𝐶4 2 произведений), где есть просто одна какая-то переменная (𝐶4 1 слагаемых) и где нет никаких переменных, то есть просто свободный член (𝐶4 0 = 1 слагаемое). В итоге получаем 𝐶4 0 + 𝐶4 1 + 𝐶4 2 + 𝐶4 3 + 𝐶4 4 = 2 4 = 16 слагаемых (бином Ньютона). Также поступаем и в общем случае. Всего произведений (если переменных n штук) будет 𝐶𝑛 0 + 𝐶𝑛 1 +…+ 𝐶𝑛 𝑛 = 2 𝑛 . Но все эти произведения с какими-то коэффициентами (которые равны 0 или 1), а значит, для каждого из 2 𝑛 слагаемых есть два варианта: либо коэффициент при произведении переменных равен 0, либо он равен 1. Разберём для наглядности пример для n = 3. Полином Жегалкина для функции от 3 переменных выглядит следующим образом: 𝑎1𝑥1𝑥2𝑥3 + 𝑎2𝑥1𝑥3 + 𝑎3𝑥2𝑥3 + 𝑎4𝑥1𝑥2 + 𝑎5𝑥1 + 𝑎6𝑥2 + 𝑎7𝑥3 + 𝑎8 (здесь 𝑎1, …, 𝑎8 - коэффициенты, равные 0 или 1). Но может так случиться, что некоторые коэффициенты равны 0 (например 𝑎1, 𝑎4, 𝑎5 и 𝑎7) и тогда полином Жегалкина выглядит так: 𝑎2𝑥1𝑥3 + 𝑎3𝑥2𝑥3 + 𝑎6𝑥2 + 𝑎8. То есть у нас есть коэффициенты 2, 3, 6, 8. Но это на самом деле – подмножество множества {1, 2,…, 8}. В конечном итоге, каждое слагаемое имеет коэффициент либо 0, либо 1 при произведении какого-то числа переменных, а слагаемых 2 𝑛 , значит, полиномов Жегалкина 2*2*…*2 (2 𝑛 раз) = 2 2 𝑛 . Всякая функция представляется некоторым полиномом Жегалкина, причём одним (это можно доказать от противного, и получить противоречие в итоге по правилу птичьих гнёзд). 23. КЛАССЫ Т0 и Т1 Мы будем рассматривать 5 важных классов алгебры логики. Нам нужно будет знать их определение, уметь доказывать их замкнутость и знать 3 важные леммы (ну в некоторых классах там ещё есть некоторые свои вещи, которые давал Костенко, но здесь расписано только вышеперечисленное). Доказательства замкнутости всех 5 классов очень похожи между собой, и различаются, в принципе, только свойствами функций в зависимости от класса. Сначала рассмотрим классы Т0 и Т1. Класс Т0 – класс функций, которые принимают на нулевом наборе значение 0: f(0, …, 0) = 0. Класс Т1 – класс функций, которые принимают на единичном наборе значение 1: f(1, …, 1) = 1. Для доказательства замкнутости этих классов нужно лишь хорошо разбираться в определениях формулы, глубины формулы, замкнутости множества. Про глубину формулы уже была речь, но сейчас она как раз понадобится. Пусть U – формула над B ⊆ P2. Глубиной формулы U называется число, значение которого определяется по правилам: 3) Если x – символ переменной, то d(x) = 0 4) Если U = f(A1,…,An), то d(U) = max(d(Ai)) + 1, i = 1, 𝑛 Здесь можно привести аналогию, например, с обычными функциями. Например, есть функция g(f(x), h(r(t))). Здесь х, t – независимые переменные, поэтому их глубину принято считать за 0. Функция f же зависит от х, а функция r – от t, поэтому их глубина равна глубине аргумента + 1, то есть 0 + 1 = 1. Глубина h аналогично равна 1 + 1 = 2. Глубина g будет равна максимальной из глубин входящих в неё аргументов (то есть f и h) + 1. В данном случае максимальная глубина у h, поэтому глубина g равна 2 + 1 = 3. ТЕОРЕМА. [T0] = T0. ДОКАЗАТЕЛЬСТВО. Наша задача доказать, что любая функция, реализуемая формулой над Т0 любой глубины, принадлежит классу Т0. Доказательство проводится методом математической индукции по глубине формулы d. 1) Базис: d (U) = 1. Пусть есть формула глубины 1, которая имеет вид: U = «𝑓(𝑥1, … , 𝑥𝑛)» (является записью функции, принадлежащей классу Т0). Рассмотрим функцию, реализуемую этой формулой 𝑓𝑈(𝑥1, … , 𝑥𝑛 ). Подставим нулевой набор в функцию 𝑓𝑈(𝑥1, … , 𝑥𝑛 ): 𝑓𝑈(0, … , 0) = 𝑓(0, … , 0) = 0 (так как 𝑓(𝑥1, … , 𝑥𝑛) принадлежит классу Т0). Мы получили, что функция, реализуемая формулой глубины 1, на нулевом наборе даёт 0, а значит, она принадлежит классу Т0 и база (или базис) выполняется. 2) Индуктивное предположение и переход. Пусть функция, реализуемая формулой над Т0 глубины d (U) ≤ k (правильно писать «формула над каким-то множеством элементарных функций», в данном случае это множество – Т0), принадлежит классу Т0. Здесь именно знак ≤, а не =, то есть нам важно, чтобы индуктивное предположение выполнялось для формул глубин не только равных k, но и меньших k. Почему мы так можем писать? Для этого нужно понять, как работает метод математической индукции. Можно привести пример с фишками домино, которые стоят в ряд и начинают друг за другом падать, если сбить какую-то из них. Если мы гарантированно знаем, что первая фишка обязательно упадёт (базис индукции) и знаем, что если какая-то фишка упала, то упадёт и следующая за ней фишка (индуктивное предположение и переход), то упадут все фишки (то есть факт падения будет верен для всех фишек). То есть, зная то, что упадёт первая фишка (базис), упадёт и следующая, вторая (переход). Зная, что упадёт вторая, упадёт и третья, и тд. Но для того, чтобы упала третья, нужно, чтобы упала не только вторая, но и первая (если мы хотим, чтобы условие падения выполнялось для всех фишек). Поэтому можем говорить, что инд. предположение должно работать не только для d (U) = k, но и для d (U) < k. Вернёмся к доказательству. Докажем, что функция, реализуемая формулой над Т0 глубины k+1, принадлежит классу Т0. Рассмотрим эту формулу: 𝑈 = 𝑓(𝐴1, … , 𝐴𝑛 ), где 𝐴1, … , 𝐴𝑛 - символы переменных или формулы над Т0 глубины, не превосходящей k. Рассмотрим 2 возможных случая: 1) 𝐴𝑖 - переменная. Тогда 𝐴𝑖 равна какой-то переменной xj. Переменная является неким частным случаем формулы, а именно формулы, которая реализует функцию от одной переменной. То есть 𝑓𝐴𝑖 (𝑥𝑗) = 𝑥𝑗 (получается тождественная функция, то есть при подстановке 1 получается 1, а при подстановке 0 получается 0). Таким образом, 𝑓𝐴𝑖 (0) = 0. 2) 𝐴𝑖 – формула над Т0 глубины, не превосходящей k. В этом случае сразу можем сказать, что функция, представимая 𝐴𝑖 как формулой, принадлежит классу Т0, поскольку по индуктивному предположению формулы глубины, не превосходящей k, представляют функции из класса Т0. То есть 𝑓𝐴𝑖 (0, … , 0) = 0. В обоих случаях получили функции, которые при подстановке нулевого набора дают 0. Переходим к последнему этапу доказательства замкнутости класса Т0. Вернёмся к формуле над Т0 глубины d(U) = k+1: 𝑈 = 𝑓(𝐴1, … , 𝐴𝑛 ). Мы можем заменить аргументы 𝐴1, … , 𝐴𝑛 на функции 𝑓𝐴1 , … , 𝑓𝐴𝑛 , реализуемые ими. Получим тогда: 𝑈 = 𝑓(𝐴1, … , 𝐴𝑛 ) = 𝑓(𝑓𝐴1 (𝑥11 , … , 𝑥1𝑚1 ) , 𝑓𝐴2 (𝑥21 , … , 𝑥2𝑚2 ) , … , 𝑓𝐴𝑛 (𝑥𝑛1 , … , 𝑥1𝑚𝑛 ) ). Мы вводим m1,…, mn, так как не знаем, сколько аргументов у каждой из функций. Из двух вышерассмотренных пунктов следует, что при подстановке в эти функции нулевого набора будет получаться 0. Поэтому, 𝑓𝑈(0, … , 0) = 𝑓 (𝑓𝐴1 (0, … , 0), 𝑓𝐴2 (0, … , 0), … , 𝑓𝐴𝑛 (0, … , 0)) = 𝑓(0, … , 0) = 0. Таким образом, функция, реализуемая формулой над Т0 глубины k+1 также принадлежит классу Т0. Доказательство завершено. Замкнутость класса Т1 доказывается аналогично. Совершенно такая же логика доказательства замкнутости класса монотонных функций, только там используется определение не класса Т0, а класса М. Теперь про количество функций от произвольного числа переменных, которые содержит класс Т0. Так как переменных у нас n, то различных наборов от n переменных, на которых функция может принимать произвольные значения, будет 2 n – 1 (отнимаем строку, где одни нули; там всегда фиксированное значение 0). Причём, мы можем вспомнить, что в табличном задании функции 𝑓(𝑥1, … , 𝑥𝑛) содержится 2n строк, а в столбце значений функции в 2 n – 1 строках (так как на нулевом наборе всегда 0) могут быть произвольные значения. Поэтому число функций равно числу комбинаций нулей и единиц и равно 2*2*…*2 (2n – 1 раз) = 2 2 𝑛−1 . 24, 25. ДВОЙСТВЕННЫЕ И САМОДВОЙСТВЕННЫЕ ФУНКЦИИ Пусть 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) ∈ 𝑃2. Функция 𝑔(𝑥1, 𝑥2, … , 𝑥𝑛 ) называется двойственной к функции 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ), если 𝑔(𝑥1, 𝑥2, … , 𝑥𝑛 ) = 𝑓(𝑥1, … , 𝑥𝑛). Если у нас есть какая-то формула, то отрицание накладывается только на переменные и на всё выражение одновременно. Обозначается как 𝑓 ∗ (𝑥1, 𝑥2, … , 𝑥𝑛 ). Функция 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) называется самодвойственной, если 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) = 𝑓 ∗ (𝑥1, 𝑥2, … , 𝑥𝑛 ). Теорема о формуле для двойственной функции. Пусть функция 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) представляется формулой 𝑈(𝑔1, 𝑔2, … , 𝑔𝑛). Тогда функция 𝑓 ∗ (𝑥1, 𝑥2, … , 𝑥𝑛 ) представляется формулой 𝑈 ∗ = 𝑈(𝑔1 ∗ , 𝑔2 ∗ , … , 𝑔𝑛 ∗ ). ДОКАЗАТЕЛЬСТВО. Доказывается по определению и индукцией по глубине формулы. Здесь мы используем также соотношение 𝑤 = 𝑤. 1) База: d(U) = 1. Тогда мы имеем формулу U = 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ), которая представляет функцию ℎ(𝑥1, 𝑥2, … , 𝑥𝑛 ). Пользуясь одним определением, получаем, что база верна (извиняюсь, лень писать ). 2) Индуктивное предположение и переход. Здесь предположение и переход почти идентичны с теми, что были в доказательстве замкнутости класса Т0. Только мы просто здесь вводим функции, которые будут реализовываться формулами (или символами переменных) A1, …, Ak. Рассмотрим нашу функцию ℎ(𝑥1, 𝑥2, … , 𝑥𝑛 ) = 𝑓(𝐴1, … ,𝐴𝑘 ). Заменим формулы (или символы переменных) 𝐴1, … ,𝐴𝑘 на функции 𝑓𝐴1 , 𝑓𝐴2 , … , 𝑓𝐴𝑘 , которые ими реализуются. Для этих функций (так как они представляются формулами глубины ≤ k) по индуктивному предположению верно, что двойственные им функции представляются двойственными им формулами. Здесь будет большое разнообразие индексов у переменных, но с этим ничего не поделать. Вот, что мы получаем: ℎ ∗ (𝑥1, 𝑥2, … , 𝑥𝑛 ) = ℎ(𝑥1, … , 𝑥𝑛 ) = 𝑓 (𝑓𝐴1 (𝑥1,1, … , 𝑥1,𝑚1), … , 𝑓𝐴𝑘 (𝑥𝑘,1, … , 𝑥𝑘,𝑚𝑘)) = = 𝑓 (𝑓𝐴1 (𝑥1,1, … , 𝑥1,𝑚1), … , 𝑓𝐴𝑘 (𝑥𝑘,1, … , 𝑥𝑘,𝑚𝑘)) = 𝑓 (𝑓𝐴1 ∗ (𝑥1,1, … , 𝑥1,𝑚1), … , 𝑓𝐴𝑘 ∗ (𝑥𝑘,1, … , 𝑥𝑘,𝑚𝑘)) = (!) (!)=𝑓 ∗ (𝑓𝐴1 ∗ (𝑥1,1, … , 𝑥1,𝑚1), … , 𝑓𝐴𝑘 ∗ (𝑥𝑘,1, … , 𝑥𝑘,𝑚𝑘)) = 𝑓 ∗ (𝐴1 ∗ , … ,𝐴𝑘 ∗ ) = 𝑈(𝑓1 ∗ , 𝑓2 ∗ , … , 𝑓𝑛 ∗ ). В последних двух действиях мы заменили двойственные функции на формулы, которые их представляют (причём формулы – тоже двойственные). Объясню, почему равенство (!) верно, на примере. Пусть у нас есть выражение (𝑥1 𝑥2 )& (𝑥3𝑥4) . Тогда в роли 𝑓 здесь выступает конъюнкция, а в качестве 𝑓𝐴1 − дизъюнкция (здесь у нас формула 𝑓(𝑓𝐴1 (𝑥1, 𝑥2 ), 𝑓𝐴1 (𝑥3, 𝑥4 ))). Если мы снимем отрицание, то получим (𝑥1 𝑥2 ) (𝑥3 𝑥4). То есть было 𝑓(𝑓𝐴1 (𝑥1, 𝑥2 ), 𝑓𝐴1 (𝑥3, 𝑥4 )), а стало 𝑓 ∗ (𝑓𝐴1 (𝑥1, 𝑥2 ), 𝑓𝐴1 (𝑥3, 𝑥4 )) (так как функция, двойственная конъюнкции – дизъюнкция, это легко проверить). Поэтому мы можем пользоваться этим равенством. Доказательство завершено. Доказательство замкнутости класса самодвойственных функций доказывается с помощью этой теоремы. Теперь рассмотрим лемму о не самодвойственной функции. Всего лемм будет 3 (о не самодвойственной, немонотонной, нелинейной). Все они формулируются по одинаковому принципу. Рассмотрим сначала лемму о несамодвойственной функции. Лемма о несамодвойственной функции. Если функция 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) не самодвойственная, то подстановкой функций 𝑥, 𝑥 можно получить одну из функций констант. ДОКАЗАТЕЛЬСТВО. Вспомним сначала определение самодвойственной функции (начало темы) Соответственно, если функция (по нашей лемме) не самодвойственная, то найдётся такой набор 𝜎1, 𝜎2, … , 𝜎𝑛, на котором 𝑓 (𝜎1, 𝜎2, … , 𝜎𝑛) не равно 𝑓 (𝜎1, 𝜎2, … , 𝜎𝑛). То есть она будет равна 𝑓 (𝜎1, 𝜎2, … , 𝜎𝑛) (поскольку значение функции может быть либо 0, либо 1). Что означает утверждение «можно получить константу»? Это значит, что имея несамодвойственную функцию, мы можем составить функцию от одной переменной, при подстановке всех наборов в которую получается либо 0, либо 1. Но функция константы - это функция от одной переменной, а изначально нам функция дана от n переменных, поэтому нам необходимо получать функцию от одной переменной. Как эту функцию получить? Для этого рассмотрим нашу несамодвойственную функцию 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ). Так как она несамодвойственна, то существует набор, при котором 𝑓 (𝜎1, 𝜎2, … , 𝜎𝑛) = 𝑓 (𝜎1, 𝜎2, … , 𝜎𝑛). Этот набор может содержать какое-то количество нулей и единиц, в зависимости от самой функции. Вместо переменных (для получения новой функции) мы можем подставлять не только 0 и 1, но и другие функции (то есть если была функция ℎ(𝑦1, 𝑦2), то, к примеру, новая функция ℎ1(𝑦1, 𝑦2) = ℎ(𝑦1, 𝑦2) получена из h подстановкой функции отрицания на переменную 𝑦1). Так вот, определим для каждой переменной вспомогательную функцию, которая поможет нам получить функцию-константу: 𝑔𝑖(𝑥) = 𝑥 𝜎𝑖 . И будем рассматривать следующую функцию h, которая будет получена из f подстановкой вместо переменных функций 𝑔𝑖(𝑥). ℎ(𝑥) = 𝑓(𝑔1 (𝑥), . . . , 𝑔𝑛 (𝑥)) = 𝑓(𝑥 𝜎1, … , 𝑥 𝜎𝑛 ). Функция g(x) нам уже знакома из темы 14. Мы используем именно эту функцию, так как именно она при определенных значениях 𝜎 даёт либо 𝑥, либо 𝑥. Вспомним её определение: 𝑥 𝜎 = { 𝑥, 𝜎 = 1 𝑥, 𝜎 = 0 Исходя из этого мы можем подставить вместо икса 0 или 1 и тогда при 𝜎𝑖 = 1 1 𝜎𝑖 = 1 (подставили х = 1. Аналогично при нуле). Итак, мы имеем функцию ℎ(𝑥) = 𝑓(𝑔1 (𝑥), . . . , 𝑔𝑛 (𝑥)) = 𝑓(𝑥 𝜎1 , … , 𝑥 𝜎𝑛 ). Тогда ℎ(0) = 𝑓(0 𝜎1, … , 0 𝜎𝑛 ) = 𝑓 (𝜎1, 𝜎2, … , 𝜎𝑛) (последнее равенство выполняется, так как при 𝜎𝑖 = 1 0 𝜎𝑖 = 0 и 𝜎𝑖 = 1 также равно 0. Аналогично при 𝜎𝑖 = 0 0 𝜎𝑖 = 𝜎𝑖 ). ℎ(1) = 𝑓(1 𝜎1, … , 1 𝜎𝑛 ) = 𝑓 (𝜎1, 𝜎2, … , 𝜎𝑛) (по тем же причинам). Но так как функция несамодвойственна, то вспоминаем, что мы писали вначале: существует набор 𝜎1, 𝜎2, … , 𝜎𝑛, что 𝑓(𝑥1, 𝑥2, … , 𝑥𝑛 ) = 𝑓 (𝜎1, 𝜎2, … , 𝜎𝑛). В доказательстве теоремы мы использовали именно этот набор. Из этого следует, что ℎ(0) = ℎ(1), а это и означает, что мы получили константу (какую конкретно - не важно, главное - что константу), что и требовалось доказать. |