У нас уже
176407
рефератов, курсовых и дипломных работ
Сделать закладку на сайт
Главная
Сделать заказ
Готовые работы
Почему именно мы?
Ценовая политика
Как оплатить?
Подбор персонала
О нас
Творчество авторов
Быстрый переход к готовым работам
Контрольные
Рефераты
Отчеты
Курсовые
Дипломы
Диссертации
Мнение посетителей:
Понравилось
Не понравилось
Книга жалоб
и предложений
Название
О классан функций к—значной логики, замкнутык относительно операций суперпозиции и перестановки
Количество страниц
110
ВУЗ
МГИУ
Год сдачи
2010
Бесплатно Скачать
23602.doc
Содержание
Содержание
Оглавление
Введение 3
1. Определения, свойства, вспомогательные утверждения 8
2. Операция перестановки типа I
с множеством нулевых угловых наборов 19
2.1. Замкнутые классы в Р*... 19
2.2. Замкнутые классы в Р2 и Р3... 24
2.3. Ослабленная операция перестановки... 29
3. Операция перестановки типа I ...
с произвольным множеством угловых наборов 30
3.1. Ослабленная операция перестановки... 30
3.1.1. Замкнутые классы трехзначной логики... 30
3.1.2. Примеры континуальных семейств . . ... 78
3.2. Замкнутые классы вРц... 80
3.3. Замкнутые классы в Р2 и Рз... 81
4. Ослабленная операция перестановки типа II 98
4.1. Примеры континуальных семейств ... 98
4.2. Функции вида F?... 98
4.3. F-функции... 102
4.4. Основные утверждения... 108
Литература 110
Введение
Настоящая работа относится к теории функциональных систем — одного из основных разделов дискретной математики. В ней рассматривается задача об изучении свойств замкнутых классов функций Ахзначной логики.
Э. Пост описал все замкнутые (относительно операции суперпозиции) классы булевых функций и показал, что каждый замкнутый класс имеет конечный базис, а множество всех таких классов счетно [31, 32]. Описание множества замкнутых классов булевых функций содержится также в [8, 9, 23, 24, 30]. Многозначные логики во многом похожи на двухзначную логику и в них сохраняется ряд результатов, имеющих место в двухзначной логике. Среди таких результатов можно отметить решения проблемы функциональной полноты и задачи описания предполных классов (см. [2, 7, 10, 25, 26, 33-35]). В тоже время имеют место и существенные различия. К их числу относятся примеры Ю. И. Янова о существовании замкнутых классов в Р^ (множестве всех функций &-значной логики), не имеющих базиса, и А. А. Мучника о существовании замкнутых классов в Рк со счетным базисом для всякого к ^ 3 (см. [27, 28]). Из этих результатов, в частности, следует континуальность множества замкнутых классов в Рк при к^З, что делает труднообозримой структуру данного множества.
Поскольку при к ^ 3 проведение в /с-значной логике исследований по изучению множества замкнутых классов наталкивается на значительные трудности, многие авторы стали рассматривать задачу изучения классов, полученных в результате применения более сильных операций замыкания, которые позволяли бы получить множество замкнутых классов счетной или конечной мощности. В работах [1, 4-6,11-16, 20-22, 29] приведены классификации и свойства классов функций Ахзначной логики, к ^ 2, замкнутых относительно операций, являющихся усилениями операции суперпозиции. При этом в работах [11-16] изучается операция 5"-замыкания, в работах [5, 6, 29] — операция параметрического замыкания, в работах [1, 4, 20-22] — операции замыкания программного типа.
Идея операции 5-замыкания, где наряду с операцией суперпозицией разрешается применять операцию перехода к двойственным функциям относительно фиксированной группы подстановок, т.е. ^-замкнутый класс вместе с каждой функцией содержит двойственную относительно указанной группы подстановок функцию, высказывалась несколькими авторами. В настоящее время существуют две версии построения S-классификации множества функций А;-значной логики (к ^ 3), представленные в работах С. С. Марченкова [11-13] и Нгуен Ван Хоа [14-16], где в частности установлено, что множество классов в данной классификации конечно, хотя и зависит от к сверхэкспоненциальным образом.
Понятия параметрической выразимости и параметрического замыкания введены А. В. Кузнецовым в работе [6]. В этой же работе получены критерий параметрической выразимости в А;-значной логике для всех к ^ 2 и конечное описание параметрически замкнутых классов булевых функций. Конечность множества параметрически замкнутых классов при к = 3 показана в работе А. Ф. Данильченко [5], а при к > 3 в работе С. Барриса, Р. Уилларда [29]. Кроме того в [5] построены все предполные классы в Р3.
В работе Ю.В. Голункова [4] изучаются вопросы полноты функционально-предикатных систем с операциями замыкания программного типа (см. также [1]). В работах В.А. Тайманова [21, 22] и В.Д. Соловьева [20] исследуется семейство функци-
ональных систем Ахзначной логики (к ^ 2) с операциями программного типа. Каждая операция программного типа определяется своим множеством предикатов. В работах [21Г 22] показано, что в зависимости от свойств указанных множеств предикатов мощность множества замкнутых классов может быть конечной, счетной или равняться мощности континуума. В случае конечного множества замкнутых классов приведено его полное описание, в случае счетного множества замкнутых классов показано, что каждый класс обладает конечным базисом, в случае континуального множества замкнутых классов представлены примеры классов со счетным базисом и классов без базиса, причем эти примеры совпадают с соответствующими примерами из [27, 28]. В [20] рассматриваются примеры конечных описаний множества замкнутых классов для некоторых операций программного типа.
Следует также отметить подход, состоящий в разбиении множества замкнутых классов /с-значной логики на классы эквивалентности, которые формируются на основе свойств входящих в них функций. Такой подход рассматривался Нгуеном Ван Хоа в работах [17-19].
Из сказанного выше вытекает, что все перечисленные примеры операции замыкания, за исключением некоторых операций замыкания программного типа, приводят к конечному множеству замкнутых классов в Р* при к ^ 3. В связи с этим, представляется важным изучение таких усилений операции суперпозиции, которые, с одной стороны, не являются столь сильными, чтобы давать конечное множество замкнутых классов, а с другой стороны позволяют достаточно просто находить результат применения этих операций к функциям. К числу таких усилений операции суперпозиции можно отнести добавление к ней операции перестановки.
В настоящей работе исследуются классы &-значной логики, к ^ 2, замкнутые относительно операций суперпозиции и перестановки с множеством угловых наборов. То есть в каждом классе, замкнутом относительно этих операций вместе с каждой функцией содержатся и все функции получающиеся из исходной в результате применения к ней операции перестановки. Операция перестановки использует геометрическое представление функций и поэтому имеет достаточно простой способ вычисления по функции всех ее образов. Эта операция вводится при помощи понятия слоя. В работе изучается несколько модификаций операции перестановки.
Сначала рассматривается операция перестановки, при определении которой слой (слой типа I) задается как множество всех наборов одинаковой длины, содержащих фиксированное количество элементов равных 0,1,...,А; — 1. В результате применения этой операции к произвольной функции f(x\,..., хп), на наборах внутри каждого слоя происходит перестановка значений данной функции, определяемая по следующему правилу. Для каждого слоя выбирается перестановка чисел от 1 до п и для каждого набора слоя новое значение функции / на нем совпадает с исходным значением функции / на наборе, получающимся из данного соответствующей перестановкой его компонент. В работе показано (см. главу 2), что в этом случае множество классов в Рк, замкнутых относительно операций суперпозиции и перестановки, является конечным при всех к ^ 2. Таким образом, данная операция перестановки является слишком сильной. В связи с этим изучается ослабление этой операции за счет введения следующего ограничения. Операцию перестановки разрешается применять только к тем функциям, которые существенно зависят от всех своих переменных. Показано (см. главу 2), что при к = 2 мощность множества замкнутых классов конечна, а при к^-Ъ равна мощности континуума.
Далее в работе вводится понятие слоя относительно углового набора (т.е. набора, все компоненты которого принадлежат множеству {0,к — 1}), и изучается (ослаблен-
ная) операция перестановки для этого нового определения слоя. При этом рассматриваемое ранее понятие слоя в новых терминах — слой относительно нулевого углового набора. Установлено (см. главу 3), что при к = 3 для любых множеств угловых наборов, удовлетворяющих определенным условиям (такие множества называются правильными, см. стр. 9), множество замкнутых классов счетно, а при к ^ 5 для произвольных множеств угловых наборов множество замкнутых классов является континуальным.
Кроме того, в работе рассматривается разбиение всех наборов на такие подмножества (слои типа II), которые содержат все наборы, находящиеся на фиксированном расстоянии от заданного углового набора. Изучается (ослабленная) операция перестановки с указанными понятием слоя при произвольных перестановках значений функций на наборах внутри каждого такого слоя. Отметим, что каждый слой типа II представляется в виде объединения некоторых слоев типа I. Показано (см. главу 4), что при всех к ^ 3 для любого множества угловых наборов определенного вида (см. стр. 9) множество замкнутых классов А;-значной логики является счетным.
Дадим более точные определения понятия слоя и операции перестановки.
Положим Ек = {0,1,..., к — 1}, Щ = Ек х ... х Ек, к ^ 2, п ^ 1. Набор (а^,..., ап) из Е% называется угловым, если а* € {0, к — 1}, i = 1,... ,п. Слой определяется двумя способами.
I. Наборы (6i,...,Sn), (7ь--->7п) принадлежат одному слою типа I относительно углового набора (аь..., ап) тогда и только тогда, когда наборы (\5i — &i\,..., \5п—ап\), (\ъ — «i|» • • ч |7п — ап\) содержат одинаковое число элементов, равных 0,1,..., к — 1.
П. Наборы (5\,...,5п), (7г,• •.,7п) принадлежат одному слою типа II относительно углового набора («i,..., ап) тогда и только тогда, когда суммы элементов наборов (\Si - ai|,..., \дп - ап\), (|7i - «i|, •.., Ы - <*п\) совпадают.
Заметим, что для произвольного углового набора а = (а\,...,ап) любой слой типа I относительно а содержится в некотором слое типа II относительно а, при этом каждый слой типа II относительно а представляется в виде объединения слоев типа I относительно а. Вначале дадим общее определение операции перестановки в независимости от конкретного определения слоя, пользуясь лишь тем свойством, что любое разбиение на слои является разбиением множества Е% на непересекающиеся подмножества. Пусть у нас фиксированы функция f{x\,..., хп) из Рк, угловой набор и разбиение множества Е% на слои относительно этого углового набора. Тогда в результате действия на функцию f{x\,..., хп) операции перестановки с данным угловым набором и разбиением на слои можно получить функцию
Операцию перестановки, которую разрешается применять только к функциям существенно зависящим от всех переменных, будем называть ослабленной операцией
перестановки.
Дадим краткое описание содержания глав диссертации.
В главе 1 приведены основные определения, свойства и вспомогательные утверждения.
В главе 2 рассматривается операция перестановки типа I с множеством угловых наборов О = {(0), (0,0),...}. В параграфах 2.1, 2.2 доказывается (Теорема 2.1.1), что любой класс в Pjt, A; ^ 2, замкнутый относительно операции суперпозиции и такой операции перестановки, порождается функциями от к переменных. Отсюда вытекает следствие (Следствие 2.1.2) о конечности множества всех таких классов. В теоремах 2.2.1, 2.2.2 приводится полное описание замкнутых классов в Рг и Р3. В параграфе 2.3 операцию перестановки разрешается применять только к функциям существенно зависящим от всех переменных, т.е. рассматривается ослабленная операция перестановки. Показывается, что в этом случае в Р2 число замкнутых классов конечно (Теорема 2.3.1), а в Рк при к ^ 3 остается справедливым пример класса со счетным базисом из [27, 28], и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 2.3.2).
В главе 3 рассматривается операция перестановки типа I с произвольным множеством угловых наборов. При этом в параграфе 3.1 изучается ослабленная операция перестановки, а в параграфах 3.2, 3.3 операцию перестановки разрешается применять к произвольным функциям А;-значной логики.
В параграфе 3.1.1 исследуются классы трехзначной логики, замкнутые относительно операций суперпозиции и перестановки. Вначале доказывается, что существует множество О, С Р3, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех его подмножеств, замкнутых относительно этих операций, счетно (Теорема 3.1.1). Затем вводится понятие правильного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {%,5п\п ^ 2}, где % G {0,2}п\{0п,2П}, 5п € {0п, 2П} для всех п ^ 2. Устанавливается, что для любого правильного множества угловых наборов произвольный замкнутый класс 21 С Р3 представим в виде объединения двух классов: замыкания множества всех трехместных функций из 21 и пересечения Г2П21 (Теорема 3.1.2). Из теорем 3.1.1, 3.1.2 выводится основной результат параграфа 3.1.1 о счетности множества классов в Р3, замкнутых относительно операций суперпозиции и перестановки с произвольным правильным множеством угловых наборов (Теорема 3.1.3). В параграфе 3.1.2 доказывается (Теорема 3.1.4), что для произвольных множеств угловых наборов классы А;-значной логики, замкнутые относительно операций суперпозиции и перестановки, образуют континуальное множество при к ^ 5.
В параграфах 3.2, 3.3 обобщаются результаты параграфов 2.1, 2.2 на случай операции перестановки с произвольным множеством угловых наборов, которую разрешается применять ко всем функциям /с-значной логики. Показывается, что в Р* при к ^ 2 любой класс, замкнутый относительно операций суперпозиции и перестановки с произвольным бесконечным множеством угловых наборов, порождается функциями от к переменных (Теорема 3.2.1), а множество всех таких классов конечно (Следствие 3.2.3). Кроме того, для указанного множества угловых наборов приводится полное описание замкнутых классов в Рг и Р3 (Теоремы 3.3.1-3.3.4). Поскольку операция перестановки типа II сильнее операции перестановки типа I, указанное выше утверждение о конечности множества классов, замкнутых относительно операций суперпозиции и перестановки с произвольным бесконечным множеством угловых наборов, при к ^ 2 выполняется и для операции перестановки типа П.
В главе 4 рассматривается ослабленная операция перестановки типа II с произвольным множеством угловых наборов. Для произвольного подмножества множества угловых наборов ОНО, где О = {(к — 1), (к — 1, к — 1),...}, в Рк при к ^ 3 справедливы примеры классов со счетным базисом из [27, 28], и, следовательно, множество замкнутых классов имеет мощность континуума (Теорема 4.1.1). Заметим, что данное утверждение о континуальности множества замкнутых классов для множества угловых наборов О U О при к ^ 3 справедливо и для операции перестановки типа I, поскольку операция перестановки типа II является более сильной операцией.
Далее в главе 4 вводится понятие m-регулярного множества угловых наборов, т. е. произвольного множества угловых наборов, содержащего подмножество вида {8,72, • • •,7ш}, где 5 е {О2, (к-1)2}, % G {0, &-1}п\{0п, (к- 1)п} для всех п = 2,..., т. В параграфах 4.2-4.4 устанавливается, что для любого /^-регулярного множества угловых наборов множество классов в Рк, к ^ 3, замкнутых относительно операций суперпозиции и перестановки, является счетным. Доказательство этого факта проводится в три этапа. В параграфе 4.2 изучается множество F функций &-значной логики специального вида. Показывается, что F содержит некоторое подмножество Fo, которое при любом выборе множества угловых наборов замкнуто относительно операций суперпозиции и перестановки, а множество всех подмножеств .Fo» замкнутых относительно этих операций, счетно (Теорема 4.2.1). В лемме 4.2.3 представлено полное описание замкнутых подмножеств множества Fo. Кроме того, в параграфе 4.2 доказывается, что множество, состоящее из замыканий подмножеств множества F\ — F\Fq относительно операций суперпозиции и перестановки с произвольным множеством угловых наборов конечно, при этом указан способ построения конечных порождающих систем для каждого из этих замыканий (Теорема 4.2.2). В параграфе 4.3 исследуются свойства функций из множества Pk\F (такие функции называются F-функциями). Доказывается, что замыкание произвольной существенной ^-функции f{x\,...,xn) относительно операций суперпозиции и перестановки с произвольным /^-регулярным множеством угловых наборов совпадает с множеством всех функций, принимающих значения из множества значений функции / (Теорема 4.3.1). В параграфе 4.4 из теорем 4.2.1, 4.2.2, 4.3.1 выводится основной результат главы 4 о счетности множества классов в Рк, к ^ 3, замкнутых относительно операций суперпозиции и перестановки с произвольным /^-регулярным множеством угловых наборов (Теорема 4.4.1), а также описание указанных классов (Следствия 4.4.1, 4.4.2).
В диссертации принята следующая нумерация теорем, лемм, следствия, утверждений и замечаний. Теоремы нумеруются тройками чисел, где первое число — номер главы, второе — номер параграфа, третье — номер теоремы внутри параграфа. Леммы и следствия нумеруются аналогичным образом. Утверждения (замечания) имеют двойную нумерацию: первое число — номер главы, второе — номер утверждения (замечания) внутри главы.
Основные результаты диссертации опубликованы в работах [36-40].
Глава 1
Определения, свойства, вспомогательные утверждения
Пусть Рк — множество всех функций /г-значной логики, Е^ = {0,1,..., А; — 1}, Ап = Ах ... х А — n-ая декартова степень произвольного множества А, к ^ 2, п ^ 1. Сначала дадим общее определение операции перестановки, в котором под слоем понимается некоторое произвольное подмножество множества Е%, а разбиение на слои множества Е% есть произвольное разбиение на подмножества множества Е% с двумя ограничениями: объединение всех слоев разбиения есть множество Е%, пересечение любых двух различных слоев разбиения есть пустое множество.
Определение. Пусть f(xi,. ..,хп) — произвольная функция из Р*, п ^ 1, к ^ 2; % = {Hi, •.., %r\ — разбиение на слои множества Е%, где R — число слоев, "Hj — слой множества Е%, j = 1,...,R; ctj — взаимно однозначное отображение ножества всех наборов слоя %j на себя, j = 1,..., R, а = (сгь..., (Tr). Будем говорить, что функция fn'°(xi,..., хп) получена из f(xi,..., хп) при помощи операции перестановки, если для любого набора 8 — (8х,...,5п), принадлежащего слою 7ij, j = 1,... ,R, выполняется соотношение fH'a(8) = f(crj(8))-
Везде далее мы будем пользоваться только двумя частными определениями операции перестановки. Для их задания нам потребуются определения углового набора и два частных определения слоя. Положим ап = (а,...,а) для всех а из ?*, п ^ 1.
Определение. Набор [а.\,..., ап) из Щ будем называть угловым набором, если с^ принадлежит множеству {0, к—1} для всех i = 1,..., гг. Обозначим через Q% множество всех угловых наборов из Е%, Qk = U Ql, О = U (0"}. Vk = U {0"> (* - I)"}-
Определение. Назовем (г'о, г'х,..., г*_х)-м слоем типа I относительно углового набора 0™ множество наборов из Е%, каждый из которых содержит ij элементов, равных j, j = 0,1,..., к - 1, г0 + i'i + • • • 4- 4_i = п, п ^ 1.
Определение. Будем говорить, что множество наборов А С Е%, п ^ 1, к ^ 2, составляет один слой типа I относительно углового набора (а\,..., ап) из Q^, если существует такой слой В типа I относительно углового набора 0п, что набор (0i,...,f3n) из ?? принадлежит А тогда и только тогда, когда набор (|/?i — а\\,..., \fin — an\) принадлежит В.
Замечание 1.1. Легко видеть, что для любого углового набора а = (а1?..., ап) из Qz справедливы следующие утверждения. Любой слой типа I относительно а, содержащий наборы из множества {0,2}71, целиком содержится в этом множестве, а множество {1П} само является слоем типа I относительно а.
Обозначим через R\ = Ri(n, к) число слоев типа I относительно углового набора 0п в Е%. Нетрудно показать, что число слоев типа I относительно любого углового набора из Q? равно R\ и R\ = С^^_г Для каждого углового набора а из Q^ занумеруем слои относительно а числами 0,1,..., Ri — 1 в некотором порядке.
Определение. Пусть f(xi,...,xn) — функция из Р&, а = («i,... ,ап) — угловой набор из Q?, Uj — перестановка чисел 1,..., п, j = 0,..., Ri — 1, а = (<7о,..., 0h,_i), п^ 1, к ^2.
Будем говорить, что функция fa(x\,..., хп) получена из функции f(x\,..., хп) при помощи операции перестановки типа I с угловым набором а и набором перестановок а, если для любого набора (Si,..., Sn), принадлежащего j'-му слою типа I относительно a, j = 0,.. .,Ri — 1, выполняется соотношение fff(Si,...,Sn) = f(ji,...,jn), где |Т» - «t| = \6aj(i) - Ooj.^jI для всех i = 1,..., п.
Будем говорить, что функция g(xi,..., хп) получена из функции f(xi,..., хп) при помощи операции перестановки типа I с угловым набором а, если существует набор а = (<7о, • • ч ^Ki-i) перестановок чисел 1,..., п такой, что д получается из / при помощи операции перестановки типа I с угловым набором & и набором перестановок ст.
Определение. Назовем j-м слоем типа II относительно углового набора 0те множество наборов из Е%, сумма элементов которых равна j, 0 ^ j ^ п(к — 1), п ^ 1, к ^2.
Определение. Будем говорить, что множество наборов А С Е%, п ^ 1, к ^ 2, составляет один слой типа II относительно углового набора («i,..., ап) из Q%, если существует такой слой В типа II относительно углового набора 0п, что набор (j3i,...,/Зп) из Е% принадлежит А тогда и только тогда, когда набор (|/?i — аг|,..., \/Зп — ап\) принадлежит В.
Обозначим через Ru = Ru(n, к) число слоев типа II относительно углового набора 0п в Е%. Легко видеть, что число слоев типа II относительно любого углового набора из Q? равно Яц и Яц = п(к — 1) +1. Обозначим через S\\(j, а) множество всех взаимно однозначных отображений множества всех наборов j-ro слоя типа II относительно углового набора а из Qk на себя.
Определение. Пусть f(xi,...,xn) — функция из Р*, п ^ 1, к ^ 2, а = (ori,..., ап) —угловой набор из QJJ, Oj — отображение из Sn(j, a), j = 0,..., Яц — 1,
О = (cro,...,
Будем говорить, что функция fa(xi,..., хп) получена из f(xi,..., хп) при помощи операции перестановки типа II с угловым набором а и набором отображений а, если для любого набора 5 = (Si,...,Sn), принадлежащего j-му слою типа II относительно a, j = 0,..., Яц — 1, выполняется соотношение /"(S) = f(crj(S)).
Будем говорить, что функция g(xi,...,xn) получена из f(xi,...,xn) при помощи операции перестановки типа II с угловым набором а, если существует набор отображений а = (а0,..., сгдп_1), Oj € S\\(j, a), j = 0,..., Яц — 1, такой, что д получается из / при помощи операции перестановки типа II с угловым набором а и набором отображений а.
Определение. Пусть f(xi,... ,хп), g(xi,... ,хп) — функции из Р^, п ^ 1, к ^ 2, W — некоторое подмножество (конечное или бесконечное) множества угловых наборов Qk. Будем говорить, что функция д получена из / при помощи операции перестановки типа I (типа II) с множеством угловых наборов W, если существует набор а = (ai,...,an) из W такой, что функция д получается из функции / при помощи операции перестановки типа I (типа II) с угловым набором а.
Определение. Пусть 21 — некоторое подмножество функций из Рк, к ^ 2, W — некоторое подмножество (конечное или бесконечное) множества угловых наборов Qk.
Замыканием 21 относительно операций суперпозиции и перестановки типа I (типа II) с множеством угловых наборов W называется множество всех функций из Рк, получающихся из функций множества 21 применением операций суперпозиции и перестановки типа I (типа II) с множеством угловых наборов W.
Определение. Множество угловых наборов из Qk называется правильным, если оно содержит подмножество {?п»7п|гс ^ 2}, удовлетворяющее следующим условиям: 6п G {О", {к - 1)"}, 7» e Qnk\{0n, (к - 1)"} для всех п > 2.
Определение. Множество угловых наборов из Qk называется т-регулярным, т ^ 2, если оно содержит подмножество {5,72? • • • > 7т}. удовлетворяющее следующим условиям: 8 G {О2, (к - I)2}, % G Qk\{0n, (к - 1)п} для всех п = 2,...,т.
Пусть 21 С Рк, W С Qk. Через [21] будем обозначать замыкание множества 21 относительно операции суперпозиции, а через <2l>w — замыкание множества 21 относительно операций суперпозиции и перестановки с множеством угловых наборов W, при этом тип операции перестановки будет указан отдельно для каждого случая. Положим 2t(n) = {/(xi,..., xn)\f(xi,.. .,хп) 6 21}. Обозначим через 21(га> множество всех функций из 21, существенно зависящих от не более, чем п переменных, п ^ 1.
Пусть 21 С Рк, <В С Рк. Положим 2ИВ = 21П Ш.
Пусть к ^ 2, п ^ 1, ai,...,ara — элементы множества Ек, при этом среди этих элементов возможно встречаются одинаковые. Множество всех различных элементов, встречающихся среди ai,...,an, будем обозначать через {а\,... ,ап}.
Пусть f(xi,...,xn) — произвольная функция из Рк, А С Ек, В С Ек. Положим D{f{A)) = {/(ab...,an) ((«!,...,«„) € Л}, ?>(/) = D(f(E%)), H(f(B)) = D(/({(a,...,a)|a € В})), Я(/) = H(f(Ek)). Будем говорить, что ограничение функции /(xi,... ,хп) из Р& на множество Л является существенной функцией, если множество А содержит такие наборы а,- = (ац,. ..,ani), г = 1,2,3,4, что asi Ф "s2, «гз 7^ "г4 для некоторых s, r, I ^ s < г ^ п, ац = an, at3 = at4 для всех / = l,...,s - l,s + l,...,n, t = l,...,r — l,r + 1, ...,n, /(«0 7^ /(U2), /(аз) 7^ /(U4). Будем называть функцию /(xi,...,xn) из Р^ существенной функцией, если она существенно зависит по крайней мере от двух своих переменных (см. [27]), т.е. ограничение функции f{x\,... ,хп) на множество Ек является существенной функцией. Будем говорить, что функция f(xi,...,xn) из Рк является симметрической функцией, если для любой перестановки s чисел 1,...,тг выполняется равенство
f(xu .. ., Х„) = /(Xe(i),. . . , Х8(„)).
Через ~ х обозначим функцию к—1—х из Рк, через Рк — множество всех функций из Рк, существенно зависящих от не более, чем одной переменной, через Ркгд — множество всех функций из Рк, принимающих значения из А, А С Ек.
Замечание 1.2. Пусть А С Ек, 21 С Рк, [21] = 21, к ^ 2. Легко видеть, что класс PkfA замкнут относительно операций суперпозиции и перестановки типа I и типа II с произвольным множеством угловых наборов из Qk, а класс 21^ замкнут относительно этих же операций при условии, что операции перестановки можно применять только к функциям, существенно зависящим от всех их переменных.
Введем обозначения для следующих замкнутых относительно операции суперпозиции классов в Pi'- Ti — множество функций из Рг, сохраняющих г, г = 0, 1, От — множество функций из Рг, таких, что любые т наборов, на которых функция равна О, имеют общую нулевую компоненту, m ^ 2, /т — множество функций из Рг, таких, что любые га наборов, на которых функция равна 1, имеют общую единичную
компоненту, га ^ 2, М — множество всех монотонных функций, L — множество всех линейных функций, К — множество всех конъюнкций, D — множество всех дизъюнк-ций, С = [{О,1}], d = [{1}], Со = [{0}].
Пусть i,j € Е3, г Ф j. Введем обозначения для следующих замкнутых относительно операции суперпозиции классов в Р$: Тц — класс функций, принимающих значения из множества {i,j} на наборах, состоящих из г и j; Tj — класс функций, сохраняющих константу г; Nm>ij — класс функций, равных m на наборах, состоящих из г и j, m в {i, j}; G{j = P3,{i,jy, С = [{0,1,2}]; Су = [{*, j}]; Q = [{»}]. Очевидно, что все вышеперечисленные классы различны и Т^ = Tji, iVTOjy = Nmji, G^ = Gji.
Положим C73n = ??\({0,2}n U {I71}).
Рассмотрим некоторые свойства операции перестановки и функций из Р&.
1. Пусть f(xi,...,xn) — функция из Pk, 5 = (6i,...,Sn) — угловой набор из Qk, i), Pji = (Aji» • • • > Pnji) — наборы из Е%, принадлежащие j'j-му слою
типа I (типа II) относительно углового набора 5, г = 1,..., /, 0 ^ ji < ... < ji ^ R\ — 1 (0 ^ л < ... < ji ^ Rn - 1), 0 ^ / ^ Ri - 1 (0 ^ I ^ Rn - 1), 21 — замыкание / относительно операций суперпозиции и перестановки типа I (типа И) с угловым набором 6. Тогда 21 содержит функцию д{х\,...,хп), обладающую следующими свойствами: д{а^) = /Фи) для всех i = 1,...,/, д{х\,...,хп) = f(xi,...,хп) на всех слоях типа I (типа И) относительно углового набора 5, не содержащих наборы а^,..., а^.
2. Для любой функции f{x\,..., хп) из Pk, любого углового набора 5 = (5\,..., 5п) из Qk, любой перестановки s чисел l,...,n, n ^ 1, и любого типа операции перестановки справедливо следующее равенство
где 7 = №(i), • • •, 8*(п)), Д = (к - 1 - <5s(i), ...,к-1- ?,(„)).
Действительно, покажем, что <{/}>j^<{/}>7 Для любого типа операции перестановки. Согласно определению операции суперпозиции класс [{/}] содержит функцию g(xi,...,хп) = /(хя-1(1),...,х3-цп)). Обозначим через R, j2<{/}>7 для любого типа операции перестановки доказывается аналогично. Таким образом, мы показали справедливость первого равенства <{/}>j=<{/}>7- Второе равенство <{f}>i=<{f}>ti непосредственно следует из определения операции перестановки и того факта, что для любого углового набора (yi,...,yn) разбиения на слои множества Е% относительно угловых наборов {ух,...,уп) и (к — 1 — уъ...,к — 1 — уп) совпадают при любом выборе типа слоя. Тем самым свойство 2 доказано.
Во всех последующих свойствах и утверждениях в данной главе рассматривается операция перестановки типа И, поэтому тип операции перестановки будем опускать.
3. Если функция f(xx,x2) из Pk такова, что существует набор (?7i, 772)> значение на котором /(771,772) 4- #(/)> т0 Функция f(x\,X2) является существенной.
Далее, в свойствах 4-8, считаем, что f(x\,x2) ~ произвольная существенная функция из Рк- Будем говорить, что операция перестановки, примененная к функции f(xi,X2), переводит набор 6 = (61,62) в набор у = (7ъ72)> если в результате действия этой операции на функцию / полученная функция f'(xi,x2) удовлетворяет равенствам: f'(5) = /(7), /(7) = f($), /'(^ь^г) = f(x\,x2) для всех (хх,х2) отличных от 5, -у-
4. Пусть {bi,.. ,,br} — произвольное подмножество множества Ек, s(x) — произвольная перестановка чисел на {1,..., г}. Тогда класс <{/}>{(*-i,o)} содержит функцию
)А(1)), если (хих2) = (bi,bi);
9{xi,x2) - i f(bs(r),bs{r)), если (xux2) = (br,br); f(xi,x2) в противном случае.
В самом деле, свойство 4 сразу следует из определения операции перестановки, так как (к — 1)-й слой относительно углового набора (к — 1,0), т.е. множество наборов {(аи а2) \\ai- (к — 1)\+а2 = к — 1}, совпадает с множеством {(а, а) \ а € Ек}.
5. Пусть функция f(xi,x2) удовлетворяет соотношению D(f) = H(f), $(x) — произвольная перестановка на D(f). Тогда класс <{/}>{(jt-i,o)} содержит функцию д(х) такую, что д(х) совпадает с s(x) на D(f), D(g) = D(f).
В самом деле, свойство 5 непосредственно следует из свойства 4. Заметим, что любой набор вида (х, х) из Е\ принадлежит множеству E\Q.
6. Пусть для функции f(x\, x2) существует набор (771,772) такой, что f(r]i,r)2) ? H(f), Т = {(Tn,r2i),..., (rir,r2r)} — произвольное множество попарно различных наборов из Е\ такое, что тц Ф т%, I = 1,.. .,г, и либо Т С Е%0, либо Т С Е\х, s(x) — произвольная перестановка чисел на {1,...,г}. Тогда класс <{/}>{(o,o),(fc-i,o)} содерж;ит существенную функцию
если (хг,х2) = (т1Ьт21); если (xi,x2) = (г12,г22); д(хих2) =
если (хих2) = (rlr,r2r); f(xi,x2) в противном случае.
В самом деле, поскольку любая перестановка является произведением транспозиций, то для доказательства свойства б достаточно показать справедливость следующего утверждения. Если существует набор (771,772) такой, что /(771,772) ^ H(f), то для любых наборов (т\,т2) и (СьСг) из Щ таких, что Т\ ф т2, Ci ф Сг и либо (ti,t2), (СьСг) € Що, либо (тит2), (СьСг) е ?&, класс <{/}>{(o,o),(*-i,o)} содержит существенную функцию
{/(п,т2) при (хих2) = (СьСг); /(СьСг) при (Я1,х2) = (т"ьг2); f(xi,x2) в противном случае.
Без ограничения общности будем считать, что (ti,t2), (СьСг) ? -^fi- Положим т = (гь7"г), С = (Сь Сг), 2п + 1 = Ti + т2, 2тп + 1 = Ci + Сг- Применим к / следующие операции перестановки: сначала операцию перестановки с угловым набором (0,0), переводящую f в (п, п+ 1), затем операцию перестановки с угловым набором (Л; — 1,0),
переводящую (п, п + 1) в (m, m + 1) и, наконец, операцию перестановки с угловым набором (0,0), переводящую (т,т +1) в ?. Полученную функцию обозначим через ip. В силу свойства 3 функции, получающиеся на каждом шаге применения операций перестановки, являются существенными. Далее к функции ip(xi,x2) применяем обратные операции перестановки, а именно, сначала операцию перестановки с угловым набором (к — 1,0), переводящую (т, т +1) в (п, п +1), затем операцию перестановки с угловым набором (0,0), переводящую (п, п + 1) в f (здесь также по свойству 3 все промежуточные функции являются существенными). В результате получим искомую функцию g(xl,x2).
7. Пусть для функции f(xi,x2) существует набор (771, %) такой, что /(т/ъ ш) ? H(f), ? — произвольное подмножество Ек, Ш = ((?*х?)и(?х ?/0)^^*1» 91 = {/(6) \ 6 G Е^}. Тогда для любого г такого, что г ^ |9DT| иг ^ |9Ч|, любого множества {ri,...,fr} попарно различных наборов из ЯЛ и любого множества {ц,..., ir} попарно различных элементов из SH класс <{/}>{(o,o),(jfc-i,o)} содержит существенную функцию д(х\,х2) такую, что g(fj) = ij, j = 1,..., г, g(j) = /(7) для всех j е ?|0-
В самом деле, свойство 7 непосредственно следует из свойства 6.
8. Пусть функция /(х1,Хг) удовлетворяет соотношению D(f) = H(f). Тогда для произвольной функции т(х), D(t) С ?>(/), |{г(с*)|о; G D(f)}\ = \D(f)\ — 1, класс
< {/} >{(o,o),(fc—i,o)} содержит функцию g(xi,x2) такую, что ограничение g(xi,x2) на множество D(f) x D(f) является существенной функцией, принимающей все значения из D(f) и удовлетворяющей равенству д(а, а) = т(а) для всех а из D(f).
Покажем справедливость свойства 8. Пусть D(f) = {ii,...,is}, где i\ < ... < ia, А = D(f), В = D(f) x D(f). Возможны следующие случаи.
a) Существуют ц, ir, 1 ^ I < г ^ s, такие, что f(ii,ir) = f(h,ii)-Согласно свойству 4 класс < {/} >{(^_1>о)} содержит функцию ifi(xi,X2), удовлетворяющую следующим соотношениям: {(*-i,o)} принадлежит функция hx(x) такая, что hi(U) = гг, hi(ir) = it, hi(a) = а для всех а из A\{ii,ir}. Положим ^(яъ^г) = (Pi(xi,hi(x2)). Тогда Ы*1,*0 = 2(*Мг) = 2{ot,a) = ifi(a,a) для всех а из A\{ii,ir}. Поэтому ограничение ^(^ъ^г) на множество В. является существенной функцией, принимающей все значения из A, \H(
< {/} >{(fc-i,o)} содержит функцию h2(x), удовлетворяющую равенствам /^(ip) = ii, h2(iq) = ir, D(h2(A)) = А. Возьмем функцию <Рз(х1,х2) = V2{h2(xi),h2(x2)). Тогда (p3{ip,ip) =¦ <Рз(ц^я) = Рз(«рЛ) = V^(*J»»j) 7^ V2(*r,»0 = Vs{iq,iP), Н((рз(А)) = ^Г((^2(-4))- Следовательно, ограничение ^з^ъ^г) на множество В является существенной функцией, принимающей все значения из А, \Н(<р3(А))\ = s — 1. Поэтому согласно свойству 5 среди функций класса <{/}>{(k-i,o)} можно подобрать функцию 1гз(х) такую, что ограничение функции g(xi,x2) = 1гз(<рз(х1,х2)) на множество В является существенной функцией, принимающей все значения из А и удовлетворяющей равенству д(а, а) = т(а) для всех а: из А.
b) Для любых ц ,ir, 1 ^ / < г ^ s, выполняется неравенство /(г/,г'г) Ф f(ir,ii). Пусть т(х) — произвольная функция из Рк такая, что D(t) С A, \D(t(A))\ = s — 1. Если s = 2, то r(z'i) = r(i2)- По свойствам 2, 3 класс <{/}>{(^_1)0)} содержит функции <р(хих2), hi(x) такие, что ?>(»1,12) ф (*2,*i), v(*ii«i) = у(*2.*2). ^i(y(*b»i)) = т(гг), Z)(/ii(^)) = Л. Тогда ограничение функции д\{х\,Хг) = ^1(^(^1,^2)) на множество В является существенной функцией, принимающей все значения из Л и удовлетво-
ряющей равенству gi(a, a) = т(а) для всех а из А. Пусть s > 2. В силу свойства 4 классу <{/}>{(fc_i,o)} принадлежит функция (fi(xi,x2) такая, что (pi(h,ii) ф
Vl(*l,*l) 7^ Vl(*2.»l)i Vl(*2i*2) € {?>l(*l,»2), ?>l(»2,*l)}, yi(*2,*2) ^ Vl(*2 ~ l.*2 + l)i
#({(fc_i>0)} содержит функцию h2(x), удовлетворяющую равенствам h2{ip) = i2, h2(iq) = it, D(h2(A)) = A. Обозначим через iv, 1 ^ v ^ s, такое занчение функции /, что h2(iv) = i\. Возьмем функцию ip3{xux2) = 2{i2,i2), Уз(«•» «в) Ф ?>з(*1»*|»)| Уз(»«,»«) 7^ Уз(ь»»в). Я(у3(Л)) = Я(у2(Л)). Следовательно, ограничение функции срз на множество Л является существенной функцией, принимающей три значения, |Я(<^з(^))| = s — 1. Поэтому согласно свойству 5 среди функций класса <{/}>{(*—i,o)} можно подобрать функцию hs(x) такую, что ограничение функции д2(х\,х2) = /^(Уз^ъЯг)) на множество В является существенной функцией, принимающей все значения из Л и удовлетворяющей равенству д2{а,а) = т(а) для всех о; из А.
Рассмотрим некоторые вспомогательные утверждения.
Утверждение 1.1. Пусть f{xx,x2) — произвольная существенная функция из Рк, к^Ъ, такая, что H(f) ф {f(x)\x € ElQ), a = (0,0), Д = (к - 1,0). Тогда класс <{/}>{ар\ содержит существенную функцию g(xi,x2), обладающую свойствами: D(g) = D(f), H(f) С H(g) и H(g) ф H(f).
Доказательство. Пусть функция /, наборы а, р удовлетворяют условиям утверждения. Положим h(x) = f(x, x), {ix, ...,is} = {/(x) IX ^ Що}- Без ограничения общности можно считать, что D(h) = {ц,..., it}, t < s. Из условия следует, что существует набор 7 == (7ь Ъ) из -E'lo такой, что f(j) $ {н,..., it}. Положим 2т = Ъ+'у2,тп? Ек- Тогда 7i Ф lii m Ф 0- Так как функция h принимает не более к —Л значений (t < s ^ к), то найдется значение, которое h принимает по крайней мере на двух элементах из Ек. Обозначим один из этих элементов через d. Согласно свойствам 3 и 4 класс содержит существенную функцию
{f(m,m) при (x f(d,d) при (хих2) = (m,m); f(xi,x2) в противном случае.
Построим из функции у с помощью операции перестановки искомую функцию д. Если выполняется одно из условий а) для любого I из Ek\{m} справедливы соотношения ip(l,m) = ip(l,l),
{(р(0,гп), если (хьх2) = (m, 0); (р(т, 0), если {хих2) = (0, т); <р(х\,х2) в противном случае.
По свойству 6 класс <{(р}>{ар\ содержит функцию ф и она является существенной. Рассмотрим операцию перестановки с угловым набором а, переводящую -у в (т,т).
Применим ее к функции ф. Получим функцию
д{хъх2) =
f(m,m), если (xi,x2) = (d,d);
/(7), если (xux2) = (га, га);
f(d,d), если (11,12) = 75
/(0, m), если (яь^г) = (га, 0);
/(га, 0), если (жь х2) = (0, m);
f(xi,x2) в противном случае,
Если не выполняются оба условия а) и Ь), то применим к функции <р операцию перестановки с угловым набором а, переводящую 7 B (тп,т). Полученную функцию обозначим через д.
f(m,m), если (хх,х2) = (d,d); „л- „. \ _ J /(7), если (xi,ar2) = (m,m);
f(xi,x2) в противном случае,
Покажем, что во всех случаях функция д является существенной. Для этого достаточно установить существование таких г и I из Ek\{m}, что либо д(т, г) =
В случае выполнения условия а) г = 0, а в качестве Z можно взять любой элемент из ?fc\{0, m}, так как р(т, 0) = cp(0,m) = у?(0,0) = #(0,0) и при таких значениях / справедливы равенства д(1,т) = ср(1,т), д{1,1) =
Пусть не выполняются оба условия а) и Ь). Так как 71 Ф т> 72 Ф тп, то д(у,тп) = (р(у,тп), д(т,у) = (р(т,у), д(у,у) = (р(у,у) при всех у из Ек\{т}. Из ложности условия а) следует, что выполняется по крайней мере одно из соотношений ip(l',m) Ф ip(l',l') или ip(m,l') =
Из определения функции д получаем, что D(g) = D(f). Из выбора наборов (d, d) и 7 непосредственно следует, что Н{д) = H(f) U {/(7)} Ф H{f).
Тем самым утверждение полностью доказано.
Утверждение 1.2. Пусть f{xi,x2) — произвольная существенная функция из Рк, к ^ 3, такая, что f(x\,x2) отлична от функций F^(xl,X2), i,j G Ек, постоянна на множестве E\Q, а = (0,0), /? = (к — 1,0). Тогда класс <{/}>{&,$} содержит существенную функцию д{х\,х2), обладающую свойствами: D(g) = D(f), H(f) С H(g) и Н(д)фН(/).
Доказательство. Пусть функция /, наборы a, ft удовлетворяют условиям утверждения. Тогда \D(f)\ > 1, |Я(/)| = 1. Положим h(x) = f(x,x), {н} = Н(х), {h,...,i\} = D(f), где ц ф ij при I ф j. Тогда h(x) = г'ь А > 1. Возможны следующие случаи.
1. \D(f)\ > 2 и {г2,г3,...,гл} С {I e Ek\(l,ii) € Ек1}. Рассмотрим следующие множества ? = {гг}, Ш = ((Ек х ?) U (? х Ек)) П Щг, Ж = {f(S)\S e Е2к1}. Положим тх = (г'2,гг), fj = (ii,ij+i) при j = 2,..., А - 1. Тогда {fuf2,.. .,fX-i} С 9Я, {г2, г'з,..., гд} Я 91- Примененяя к функции / и множествам ?, 971, 91 свойство 7 нетрудно показать, что класс <{/}>{а,р} содержит существенную функцию (p(xi,x2), удовлетворяющую равенствам
2. \D(f)\ > 2 и {г2,г"з,_,г*л} % {I G Ек\(1,н) € -Е1^}. Тогда найдется значение
ij, 2 ^ j ^ А, такое, что (ii,ij) E Е%0. Без ограничения общности будем считать, что j = 2. Введем следующие обозначения: с — произвольный элемент из Ек, удовлетворяющий соотношению (с, ц) € .Е^, ^ = (r7i,^2) — произвольный набор из Ек, на котором /(?)) = г2. Из условия следует, что fj G Е1^. Поэтому, согласно свойству б, класс <{1}>{а,р} содержит функцию
v(xux2) = { f(c,h), если (xux2) = fj;
f(xi,x2) в противном случае.
Тогда функция w(x) = v(x,h(x)) удовлетворяет равенствам w(ii) = i\, w(c) = i2. Рассмотрим следующие множества ? = {ч,г2}, 9Л = ((Ек х ?) U (? х Ек)) П Ек1, <Я={/(6)\6еЕк*1},т1 = 9ЛП(?*х?). Тогда |9ЛХ| ^ к-l ^ А - 1, {г2,.. .,гА} С 91. Поскольку (с, ч), (с, г2) G Ек1, то (с, ч), (с, г2) G 9Яь Введем следующие обозначения: Ту = (с,г"х), т2 = (с,г2), тз,...,г\_1 — произвольные попарно различные наборы из 9ЛД{(с, г'х), (с, г2)}. Примененяя к функции / и множествам ?, 9Л, 91 свойство 7 нетрудно показать, что класс <{/}>{&,/)} содержит существенную функцию <р(х\,х2), удовлетворяющую равенствам (p(fj) = ij+i при j = 1,...,А — 1, ^(7) = /(7) при 7 € Ек0. Тогда {у?(7) 17 ^ -^lo) = {*i}- ^ силу соотношений (ц,н), (ii,i2) G EkQ получаем, что
3. |?)(/)| = 2. Поскольку по условию функция / отлична от функции F?li2 и постоянна на множестве Ек0, то на множестве Ек1 функция / принимает оба значения г'х и г2, т.е. {f(S) 16 ? Ekl} = D(f). Возможны следующие случаи.
3.1. («1» *г) ^ Eli- Рассмотрим следующие множества ? = {h}, 9Л = ((Ек х ?) U (? х Ек)) П Е2к1, 91 = {f(f)\S ? Е2к1). Положим п = (гьг2), Т2 = (^2>*i)- Тогда {fi,f2} С 9Л. Примененяя к функции / и множествам ?, 9Л, 91 свойство 7 нетрудно показать, что класс <{/}>{^М содержит существенную функцию (fi) = гь
существенной, D(g) = D(f), H(f) С {11,2*2} = H(g). Следовательно, для данного случая утверждение доказано
3.2. (ii,i2) G Е%0. Рассмотрим следующие множества ? = {«ь^г}, Ш = {(Ек х ?) U (? х Ек)) П Е2к1, Ж = {Щ \ 6 € Е2к1}. Положим n = {j, i2), f2 = (j, h), где j — произвольный элемент из {/|(Z, i'i) G Ек1]. Тогда {fi,T2} С 9Я. Примене-няя к функции / и множествам ?, 9Я, 9\ свойство 7 нетрудно показать, что класс <{/}>{а в} содержит существенную функцию
Тем самым утверждение полностью доказано.
Утверждение 1.3. Пусть f(xi,x2) — произвольная существенная функция из Pk, k>3, такая, что H(f) = {/(*) |х G E2k0}, H(f) ф ?>(/), |Я(/)| > 1, а = (0,0), /3 = (к — 1,0). Тогда класс <{/}>/йД> содержит существенную функцию д(х\,х2), обладающую свойствами: D(g) = D(f), H(f) С H(g) и H(g) ф H(f).
Доказательство. Пусть функция /, наборы а, /3 удовлетворяют условиям утверждения. Согласно свойствам 3 и 4 класс < {/} >/д\ содержит существенную функцию (р(х1,х2), удовлетворяющую условиям: (p(i, г) = г для всех i из H(f), H({УъУ2) = Дг/ъУг) для всех (уиу2) из El таких, что уг ф у2.
Покажем, что класс <{ip\ содержит функцию w{x) обладающую следующими свойствами: w(i) = г при г € H(f), w(t) = г'1 для некоторых i\ € H(f) и t € Ek\H(f), удовлетворяющих соотношению г + 1\ф 0(mod 2). Рассмотрим соотношение
х + (р(х,х) фО (mod 2) ' (1)
Так как ip(i, г) = г для всех i из H(f), то для всех х из H(f) соотношение (1) неверно. Если существует с из Ек такое, что при х = с выполняется соотношение (1), то w(x) = <р(х, х), t = с, i\ = ip(c,c). Если же соотношение (1) ложно для всех х из Ек, то найдутся элементы из #(/) разной четности. Действительно, пусть все элементы из H(f) имеют одинаковую четность. Тогда все элементы противоположной четности не принадлежат Н(/) и удовлетворяют соотношению (1). Тем самым получили противоречие. Обозначим через щ произвольный элемент из Ek\H(f). Положим п2 = 4>(щ, щ)- Обозначим через щ произвольный элемент из H(f) такой, что п2+щ ф 0 (mod 2). Следовательно, числа щ, п2, щ удовлетворяют равенствам <р(щ,щ) = п2, ?>(n2,n2) = n2, <р{пз,щ) = п3, щ + щ = п2 + п3 ф пх + п2 = 0(mod 2). По свойству 4 класс <{<р}>ш содержит функцию
{п3, если (xi,x2) = (п2,п2);
п2, если {хих2) = (п3,п3);
(p(xi,X2) в противном случае,
Тогда ги(х) = v(v(x)), где v(x) = и(х, х), t = щ, ц = щ. Таким образом функция w(x) построена.
Так как \H(f)\ > 1, то в H(f) содержится по крайней мере один элемент отличный от ii. Обозначим этот элемент через i2. Рассмотрим следующие множества ? = {«!, г2}, ЯЯ = ((Ек х ?) U (? х Ек)) П Е2Ш УК = {/(5) \ ~6 € Е2к1}, Шг = 9Л П (Ек х ?).
Список литературы
Цена, в рублях:
(при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)
1425
Скачать бесплатно
23602.doc
Найти готовую работу
ЗАКАЗАТЬ
Обратная
связь:
Связаться
Вход для партнеров
Регистрация
Восстановить доступ
Материал для курсовых и дипломных работ
29.04.24
Результаты оценки психологических детерминант гражданской идентичности учащихся старших классов
29.04.24
Программа формирования гражданской идентичности старшеклассников
29.04.24
Психологические основания для разработки программы формирования гражданской идентичности старшеклассников
Архив материала для курсовых и дипломных работ
Ссылки:
Счетчики:
© 2006-2022. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.