Бесплатно скачать, заказать диплом, курсовую, диссертацию О классан функций к—значной логики, замкнутык относительно операций суперпозиции и перестановки

У нас уже 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(2i2) € {?>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,22} = 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

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

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

15.04.24 Критерии качества преподавания

15.04.24 Категория нормы в обучающей деятельности

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2022. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.