Содержание к диссертации
Введение
1 Основные определения 12
1.1 Двоичные представления 12
1.2 Двоичные перестановки 14
1.3 Операция двоичной суперпозиции 18
1.4 Эквивалентность -замыкания и -замыкания 23
1.5 Критерий полноты -замкнутых классов 25
2 Классы функций из2 28
2.1 Счетность семейства -замкнутых классов 28
2.2 Описание -замкнутых классов 34
3 Классы функций из 3 43
3.1 Континуальность семейства -замкнутых классов 43
3.2 Конечные семейства -замкнутых классов 463.2.1 Классы с булевым замыканием в 46
3.2.2 Классы с булевым замыканием в или 47
3.2.3 Классы с булевым замыканием в 49
3.2.4 Классы с булевым замыканием 2, 0, 1, 01, или 01 51
3.2.5 Классы с булевым замыканием 2 53
3.2.6 Классы с булевым замыканием в или 01 58
3.2.7 Множества 60
3.3 Семейство классов с булевым замыканием 3 62
3.4 Полная классификация 69
3.5 Случай с тремя фиксированными значениями 70
3.6 Подход к описанию классов 75
4 Классы функций из 4 77
4.1 Обобщение результатов из 3 77
4.2 Некоторые конечные семейства классов 81
4.3 Семейство классов с булевым замыканием 2 874.3.1 Случай = 4 87
4.3.2 Случай = 2, 3 88
4.4 Полная классификация 93
5 Все функции -значной логики 96
5.1 Обобщение результатов из 4 96
5.2 Классификация семейств -замкнутых классов 98
Литература
- Двоичные перестановки
- Критерий полноты -замкнутых классов
- Семейство классов с булевым замыканием
- Семейство классов с булевым замыканием 2 874.3.1 Случай = 4
Двоичные перестановки
Относительная простота некоторых классов функций из ,, достигнутые в этом направлении результаты и разработанные методы позволили в отдельных случаях исследовать задачи о сложности представления функций формулами. Д.А. Дагаевым [10, 11] для почти всех замкнутых классов булевых функций получены асимптотически совпадающие с «мощност-ными» нижними оценками верхние оценки функций Шеннона, характеризующих сложность множества всех функций из 3,2 с проекцией (булевым ограничением) в заданный класс булевых функций, при реализации формулами над некоторыми порождающими системами, а для почти всех замкнутых классов псевдолинейных функций (проекции которых совпадают с классом всех линейных булевых функций) из 3,2 установлен точный рост соответствующих функций Шеннона для некоторых порождающих систем.
Значительное число работ посвящено исследованиям функциональных систем (;+), в которых оператор + является усилением оператора суперпозиции. Использование такого подхода позволяет, как правило, получать семейства замкнутых классов с более обозримой структурой. Стоит отметить, что упомянутые выше работы Е. Слупецкого и Г.А. Бурле можно отнести к данному направлению исследований, поскольку задачи, рассматриваемые в данных работах, естественным образом можно переформулировать в терминах усиленной операции суперпозиции, допускающей в качестве тривиальных формул формулы, реализующие функции одной переменной.
С.С. Марченков и Нгуен Ван Хоа рассматривали [43, 45, 47, 64–67] -замкнутые классы функций -значной логики (классы, которые вместе с каждой функцией содержат функции, двойственные к ней относительно заданной группы перестановок) и показали, что семейство таких классов является конечным при любом 3, и при этом число таких классов растет сверхэкспоненциально с ростом .
В работе А. В. Кузнецова [32] введены понятия параметрической выразимости и оператора параметрического замыкания, а также установлены критерии параметической выразимости для -значных логик при 2 и найдены все параметрически замкнутые классы при = 2. В дальнейшем А.Ф. Данильченко установлена [12] конечность семейства параметрически замкнутых классов при = 3, а C. Баррисом и Р. Уиллардом — при 3 [95]. На основе понятия параметрической выразимости О.М. Касим-Заде определено [19, 20] понятие неявной выразимости. Им установлена эквивалентность параметрической и неявной выразимости при = 2 и, тем самым, установлена конечность множества классов неявно выразимых булевых функций. Критерии неявной полноты множеств функций -значной логики получены О.М. Касим-Заде [20] и Е. А. Ореховой [68] при = 2 и = 3 соответственно. При этом в [68] критерий неявной полноты для = 3 формулируется не в терминах предполных (те. максимальных неполных) классов, а в терминах минимальных полных классов.
Функционально-предикатные системы с операциями замыкания программного типа, определяемые своими множествами предикатов, рассматривались в работе Ю. В. Голункова [9], в которой исследовалась задача полноты таких систем. Работы В. А. Тайманова и В. Д. Соловьева [70-72] посвящены изучению функциональных систем функций -значной логики, 2, с операциями программного типа. В. А. Тайманов установил, что в зависимости от свойств множеств предикатов, семейства замкнутых классов могут быть конечными, счетными и континуальными. Примеры конечных описаний замкнутых классов для некоторых операций программного типа рассматривались В. Д Соловьевым.
К этому же направлению относятся и работы О. С. Тарасовой [73-75]. В них определены операторы замыкания относительно суперпозиции и перестановок, основанных на разбиении множеств %, и приведены примеры перестановок, при которых семейство замкнутых классов функций -значной логики является счетным при 3, а также пример оператора, для которого семейство замкнутых классов функций из к является счетным при = 3 и континуальным при 5.
Таким образом, при исследовании функциональных систем (к; +) в качестве оператора +, как правило, выбирается оператор, возникающий при решении других задач или представляющий практический интерес. Немаловажное значение при этом имеет наличие новых качественных «эффектов», выявляемых при изучении семейств классов, замкнутых относительно оператора +, и возможность использования полученных результатов для исследования классов, замкнутых относительно операции (обычной) суперпозиции.
В настоящей работе изучаются функции -значной логики при = 2т, 2. Каждое число из множества {0,1, ... ,—1} кодируется в двоичной системе счисления. Тем самым этому числу взаимно-однозначно сопоставляется двоичный вектор из множества {0,1}". На основе этого кодирования каждой функции из к сопоставляется булева вектор-функция, состоящая из компонент. Идея применения такого подхода для изучения функций многозначной логики была предложена, как уже говорилось, еще Э.Л. Постом [146] и часто используется в различных областях дискретной математики (см., например, [7,69,81,88]), а в отдельных случаях является настолько эффективной, что позволяет получать в некотором смысле окончательные результаты (см., например, [22,76]).
В диссертации на основе представления функций -значной логики в виде булевых вектор-функций определен оператор -замыкания, который является усилением оператора суперпо зиции. Основной целью работы является исследование свойств оператора /3-замыкания и /3-замкнутых классов функций fc-значной логики при к = 2т, т 2.
Диссертация состоит из введения, пяти глав, разделенных в совокупности на 19 разделов, и списка литературы. Основные утверждения работы формулируются в виде теорем. Утверждения нумеруются парой чисел, где первое означает номер главы, а второе — номер утверждения внутри главы.
Во введении кратко изложена история вопроса и описаны основные результаты работы.
В первой главе введены основные понятия и определены новые операторы замыкания. Каждая функция F из Рк, зависящая от п переменных, п 1, естественным образом кодируется в двоичной системе счисления. Тем самым ей сопоставляется булева вектор-функция F, содержащая т компонент, каждая из которых зависит от тп переменных, и называемая двоичным представлением функции F. В разделе 1.2 определена операция двоичной 5-суперпозиции, которая подобна операции (обычной) суперпозиции, но, в отличие от нее, позволяет при построении новых функций специальным образом переставлять компоненты двоичных представлений функций fc-значной логики между собой. Для оператора замыкания относительно операции двоичной 5-суперпозиции, который назван -замыканием, на основе примера замкнутых классов со счетным базисом, предложенного Ю. И. Яновым и А. А. Мучником11, установлена континуальность семейства -замкнутых классов функций из Рк\2 (теорема 1.1).
В разделе 1.3 для каждого множества Л из Рк определено его булево замыкание В (Л) — класс булевых функций, который равен замыканию всех компонент двоичных представлений функций из Л относительно операций суперпозиции и введения несущественной переменной. Также определено /3-замыкание множества Л как множество всех функций fc-значной логики с двоичным представлением F(g1, ... , дтп), где F є Л и д1, ... , дтп є В (Л) (здесь п — число переменных функции F). В этом разделе доказаны некоторые свойства такого оператора, а в разделе 1.4 установлено, что оператор /3-замыкания эквивалентен оператору замыкания относительно операций двоичной 5-суперпозиции и введения несущественной переменной (теорема 1.2). В разделе 1.5 приведен критерий полноты /3-замкнутых классов (теорема 1.3) и описаны все /3-предполные классов. Оказалось, что их число не завивисит от А; и равно шести. Пять из них соответствуют предполным классам булевых функций и состоят из всех функций fc-значной логики, компоненты которых принадлежат соответствующему предполному классу булевых функций. Шестым /3-предполным классом является множество всех функций из Рк, которые принимают не все значения.
Критерий полноты -замкнутых классов
Несложно показать, что операция двоичной суперпозиции является усилением операции (обычной) суперпозиции. Для этого достаточно при формировании новых вектор-формул использовать все т компонент ранее построенных вектор-формул.
Определение 1.15. Множество всех функций k-значной логики, которые можно получить из функций системы А при помощи операций двоичной суперпозиции и введения несущественной переменной, будем называть j3-замыканием множества А {обозначение [ДоОпределение 1.16. Множество А будем называть /3-замкнутым, если А = [А]р.
В следующем разделе будет показано, что оператор /3-замыкания эквивалентен оператору 5-замыкания. Поэтому для него тоже выполняются три свойства, которые являются необходимыми для операторов замыкания, из чего следует непротиворечивость введенных определений.
По построению компоненты каждой нетривиальной вектор-формулы над А реализуют функции из РаОпределение 1.17. Булевым замыканием множества А {обозначение В (А)) будем называть все функции из Р2, которые могут быть реализованы компонентами нетривиальных вектор-формул над А и получены из них при помощи операции введения несущественной булевой переменной.
Пусть В — множество функций из Р2. Обозначим через [В] замыкание множества В относительно операции суперпозиции и введения несущественной переменной. Тогда справедливы следующие утверждения. где /і, ... , jm — компоненты некоторой вектор-функции F из Л, а ф\, ... ,фтп являются компонентами вектор-формул над Лив них входят переменные из множества {хг , ... , x%J }. Для каждого числа t, 1 t van, рассмотрим компоненту i\)t. Если она не является тривиальной, то она реализует некоторую функцию gt из класса В (Л). Если данная компонента является тривиальной, то она имеет вид ж для i lиl j m. Рассмотрим два случая.
Пусть класс В (Л) содержит селекторные функции. Тогда компоненту фг можно заменить на нетривиальную компоненту, которая реализует булеву функцию gt{x%j) = ж . При этом новая вектор-формула будет реализовывать ту же функцию, что и вектор-формула Ф.
Пусть класс В {Л) не содержит селекторные функции. По свойствам классов булевых функций класс В (Л) содержит только константы (см., например, [78]). Так как для каждой функции F из множества Л справедливо соотношение b(F) С В (Л), то все компоненты функции F являются константами и функция F тоже является константой. Поэтому если заменить компоненту фг на компоненту, реализующую константную функцию gt = с, где с Є В (Л), то новая новая вектор-формула будет реализовывать ту же константу, что и вектор-формула Ф.
Таким образом можно считать, что для каждого t, 1 t van, верно включение gt Є В (Л). Поэтому, если вектор-формула Ф реализует некоторую функцию Н из Рк, то справедливы равенства:
Согласно определению 1.15 каждая функция Я из множества [А\р равна некоторой функции, которая реализуется вектор-формулой Ф над Л, либо получена из такой функции путем добавления несущественных переменных. В первом из данных случаев, как было показано выше, выполняется равенство Н = F для некоторых функций д1, ... ,дтп из множества В (Л). Но можно считать, что и во втором случае выполняется данное равенство, так как можно для каждого t, 1 t тп, вместо функции gt рассмотреть функцию g t, полученную из нее путем добавления всех компонент несущественных переменных для функции Н.
Покажем теперь, что каждая функция Н из Рк содержится в множестве [А]р, если найдутся функция F из множества Л и функции дг, ... , дтп из множества В (Л) (здесь п — число переменных функции F), такие, что выполняется следующее равенство
Пусть функции дг, ... , дтп реализуются соответственно компонентами фг, ... , фтп некоторых вектор-функций над Л или получены из них при помощи операции введения несущественной переменной. Рассмотрим вектор-формулу где F = (_/ !, ... , fm). Она реализует функцию Н , которая с точностью до несущественных переменных равна Н. Так как в множество [А]р входят все функции, полученные из функции Н при помощи операции введения несущественной переменной, то функция Я тоже содержится в /3-замыкании множества Л.
Таким образом доказано следующее утверждение.
Лемма 1.4. Пусть Л С Рк. Тогда множество [А]р содержит все функция Н из Р\., для которых найдутся функция F из множества А и функции д\, ... , дтп из множества В (Л) (здесь п —число переменных функции F), такие, что выполняется следующее равенство:
Замечание. При к = 2т, т 2, если произвольным образом закодировать все числа из множества Ек двоичными наборами длины т так, чтобы отображение из Ек в Е1, задаваемое данным кодированием, являлось биективным, то можно определить двоичные представления функций из Рк относительно этого способа кодирования аналогично тому, как это было сделано при стандартном кодировании (см. определение 1.1). Поскольку определение /3-замыкания основано исключительно на двоичном представлении функций fc-значной логики, то оператор /3-замыкания будет корректно определен и относительно нового способа кодирования. При этом существует изоморфизм между функциональными системами функций fc-значной логики с операторами /3-замыкания, которые основаны на различных способах кодирования. 1В некоторых случаях мы будем опускать скобки ( и } в такой записи Этот изоморфизм можно построить, если каждой функции из одной функциональной системы поставить в соответствие функцию из другой функциональной системы с таким же двоичным представлением.
Замечание. В том случае, когда к не является степенью двойки, если попытаться определить двоичные представления функций fc-значной логики на основе кодирования чисел из множества Ек в двоичной системе счисления, то эти двоичные представления не будут являться булевыми вектор-функциями. Так, если 2т 1 к 2т для некоторого то 2, то двоичное представление гг-местной функции из Pk, п 1, будет представлять собой вектор, компонентами которого являются то функций, определенных на некотором собственном подмножестве множества Еп и принимающих значения из множества Е2. Поэтому при рассмотрении функциональной системы Pk, где 2т 1 к 2т, то 2, с оператором, подобным оператору /3-замыкания, возникнет необходимость каким-либо образом доопределить компоненты функций этой системы до булевых функций. В этой связи появляется дополнительная вариативность при выборе способа такого доопределения, а также получается, что каждая из функций fc-значной логики доопределяется до функции 2т-значной логики, и, следовательно, задачу исследования /3-замкнутых классов функций из Pk можно свести к задаче исследования некоторых семейств /3-замкнутых классов функций из Р2т.
Семейство классов с булевым замыканием
Докажем сначала, что В (Л) = В. Так как по лемме 1.3 верно равенство В (Л) = B(S), то достаточно доказать равенство B(S) = В. По построению функций G\, ... ,Gr справедливо включение {G\, ... , Gr} С S, а значит, {д[, ... ,д г} С (J 6(F) иВС B(S). По построению функций из множества 5 и по лемме 2.10 если 0 ф U(B), то среди компонент функций из S не содержится функций, реализующих константу 0, если 1 ф U(B), то не содержится функций, реализующих константу 1, а если х U(B) — функций Щ и д г, ... ,д г. Поэтому независимо от множества U(B) получим, что для каждой функции F из S выполняется соотношение b(F) С В. А значит, выполняется соотношение B(S) С В, и, следовательно, В (Л) = В.
Теперь покажем, что имеет место равенство 1пс1(Д) = I. Включение / С 1пс1(Д) очевидно в силу определения класса Л. Перейдем к доказательству включения 1пс1(Д) С /. Рассмотрим произвольную пару индексов (p,q) ф 1 , р = q. По построению среди функций множества S не содержится функций, принимающих оба значения р и q, а значит, таких функций нет и в классе Л. Следовательно, верны соотношения (p,q) ф (1пс1(Д))(2) и (1пс1(Д))(2) С 1 .
Для доказательства включения (Ind(A)) С 1 рассмотрим сначала случай, когда {0,1} ф U(В). Предположим, что найдется такая пара (s, s) Є (Іпс(Д)) , что (s, s) ф I \ Тогда найдется функция Н из Л, такая, что D(H) = {s}. Если U(B) Р{0,1} = 0, то b(H) ф В, так как среди компонент функции Н содержатся только константы. Значит, В (Л) = В, что неверно. Если U(B) П{0,1} = {0}, то 1 = {(0, 0)}. Поскольку (s, s) ф I l\ то s = 0 и среди компонент функции Н содержится функция, реализующая константу 1. Значит, Ь(Н) ф В и В (Л) = В, что неверно. Случай, когда U(B)f]{0,1} = {1}, рассматривается аналогично предыдущему.
Таким образом, установлено, что если {0,1} ф U(B), то (1пс1(Д))(1-) С /W, и для завер шения доказательства теоремы осталось доказать включение (Ind(A)) С 1 в тех случа ях, когда {0,1,ж} С U(В). Для этого рассмотрим произвольную пару (s,s) Є (Іпсі(Л))(1), где s Є Ек, и произвольную функцию Н є Ass- Тогда выполняется равенство Н = Fy{g\, ... ,дт), ... , ((/m(ra_i)+i, ... ,дтп)) , где F — некоторая функция из S, которая зависит от п переменных, а д\, ... , дтп — функции из В. Если D(F) = {s}, то по определению множе ства S пара индексов (s, s) принадлежит Fl . Если D(F) = {s\, S2}, где S\, s2 Є Ек, S\ s2, то s Є {si,s2}. В силу определения множества S пара индексов (si,s2) принадлежит 1 2\ Поэтому s Є d(I ), а так как верно соотношение d(I ) С d(I ), то s Є d(/ ). Значит, па ра индексов (s,s) принадлежит множеству /W и для рассматриваемых случаев справедливо включение (lnd(A)) С /W, что и требовалось показать. Теорема доказана.
Теорема 2.3 утверждает, что для каждого класса В алгебры логики и множества индексов /, которые удовлетворяют приведенным в условии теоремы условиям, однозначным образом определяется /3-замкнутый класс А функций из Рц2, такой, что В (Л) = В и 1пс1(Д) = /. В свою очередь, для каждого /3-замкнутого класса функций из Рц2 однозначным образом определяются такой класс В и множество соответствующих индексов. Покажем, как используя данное утверждение можно описать решетку таких /3-замкнутых классов функций.
Лемма 2.11. Пусть Ы, V С Рщ2, [U]p = Ы и [У]р = V. Тогда для того, чтобы выполнялось соотношение Ы С V, необходимо и достаточно, чтобы выполнялись соотношения В(Ы) С B(V) и Ind(W) С Ind(V).
Доказательство. Пусть сначала имеет место вложение Ы С У. Тогда (J b(F) С (J 6(F), а значит, по определению 1.2, имеет место вложение В (U) С B(V). Также для каждых значений чисел рид, таких, что p,q Є Ek, р q, выполняется соотношение Ып С Vpq, и, поэтому, по определению множеств Ind(W) и Ind(W) верно включение Ind(W) С Ind(V).
Пусть теперь выполняются соотношения В (U) С В(V) и Ind(W) С Ind(V). Тогда для каждых значений чисел р я q, таких, что p,q Є Ek, р q, в силу утверждения лемм 2.6 и 2.7 выполняются соотношения Upq С Vpg, а следовательно, Ы С У. Лемма 2.12. Пусть W, V С Рк\2, [И]р = [У]р = V, Ы С V и U(B(U)) = U(B(V)). Тогда Ы является предполным в V тогда и только тогда, когда имеет место один из следующих случаев: 1) В (U) = В (V) и мощность множества Ind(V)\Ind(W) равна единице; 2) В(U) является предполным в B(V) и Ind(W) = Ind(V). Доказательство. Обозначим мощность множества Ind(V)\Ind(W) через N.
Сначала докажем необходимость приведенных в утверждении леммы соотношений. Пусть Ы является предполным в V. Тогда в силу утверждения леммы 2.11 справедливы вложения В (U) С В (V) и Ind(W) С Ind(V).
Рассмотрим случай, когда В(Ы) = B(V). Обозначим этот класс через В. Если N = 0, то Ind(W) = Ind(V), и в силу утверждения леммы 2.8 выполняется соотношение Ы = V, что неверно. Значит N 1.
Пусть теперь N 2. Тогда найдутся наборы (pbqi) Є Ind(V) и (р2,Фг) Є Ind(V) для которых (p\,qi) ф. Ind(W) и (rp2,Q2) ф Ind(W).
Пусть выполняется соотношение р\ = q\. Тогда рассмотрим функцию F є VP2q2 и /5-замкнутый класс [WlJjF }] , который обозначим через W. Так как F ф Ы, то Ы С W С V, а так как В(Ы) = B(V), то B(W) = В. Покажем, что W = 0. Для этого рассмотрим произвольную функцию Н из класса [Ы \J{F }]p. Она имеет вид где функция F принадлежит множеству Ы \ {F }, зависит от п переменных, а д\, ... , gmn — некоторые функции из В. Если F є U, то в силу утверждений лемм 2.6 и 2.7 функция Н принадлежит W, а следовательно, D(H) = {rp\, q\}. Если F = F , то функция Н может принимать только значения из множества {p2-,q_2}, и D(H) = {pi,qi}. Значит среди функций класса W нет функций, которые принимают значения р1 и дг, и поэтому Ы не является предполным в V. Случай, когда р2 = Q2, рассматривается аналогично.
Если р\ = gi и р2 = Q2, то рассмотрим функцию F є VP2P2 и /3-замкнутый класс [WlJjF }] . Рассуждениями, аналогичными предыдущему случаю, получим, что константа Р\ не принадлежит классу [WlJjF }] . Поэтому класс Ы не является предполным в V. Значит в рассматриваемом случае N = 1.
Теперь рассмотрим случай, когда В(Ы) С B(V). Покажем, что в этом случае В(Ы) является предполным B5(V) И Ind(W) = Ind(V). Предположим, что найдется класс В функций алгебры логики, такой, что В(Ы) С В С B(V). Тогда найдется функция / є Рг» такая, что / ф B(U) и / є Б. Так как равны основания классов В(Ы) и B(V), то функция / не может содержаться в множестве {0,1,х,х}. Поэтому по свойствам булевых функций х Є [ {/} ] С В(у) (см., например, [78]), и в силу утверждения теоремы 2.3 для класса V выполняется соотношение Incr (V) = 0.
Рассмотрим класс [W I J{F}1 я, который обозначим через W. Поскольку р о, то найдется, для которого р №, а следовательно / Є 6(F) w F f_ U. Если множество [/"(-?(V)) не содержит функцию 0, то в силу утверждения леммы 2.10 для каждого г, 1 г га, выполняется соотношение = 1; не содержит функцию 1 — соотношение Pi = 0; не содержит функцию х — соотношение Pi qi. В любом из этих случаев b(F) С В. Поэтому B(W) С Be B(V), и в силу утверждения леммы 2.1 /3-замкнутые классы W и V различны. Значит W не является предполным в V, что противоречит условию.
Поэтому В(Ы) является предполным в В (V). Предположим, что Ind(W) = Ind(V). Рассмотрим (p,q) ф Ind(V)\Ind(W). Определим одноместную функцию F є Рц2 через ее двоичное представление (/і, ... , fm). Для каждого г, 1 г га, положим: который обозначим через W. Если множество f/( (V)) не содержит функцию 0, то в силу утверждения леммы 2.10 для каждого і, 1 г га, выполняется соотношение = 1; не содержит функцию 1 — соотношение pi = 0; не содержит функцию х — соотношение pi qi. В любом из этих случаев b(F) С U(B(V)) = U(B(U)). Поэтому В(Ы) = В(Ы ) С B(V), и в силу утверждения леммы 2.1 /3-замкнутые классы W и V различны. Поэтому W не является предполным в V, что противоречит условию. Значит в рассматриваемом случае В(Ы) является предполным в В(V) и N = 0. Перейдем к доказательству достаточности приведенных в утверждении леммы соотношений. Пусть сначала В(Ы) = B(V) и N = 1. Тогда существует набор (р, q), такой, что Ып = 0 и Vpq = 0. Рассмотрим произвольную функцию F из V\U и /3-замкнутый класс [ и{ } ]я, который обозначим через W. Так как В(Ы) = B(V), то согласно утверждениям лемм 2.6 и 2.7 для всех (а, Ъ) Є Ind(W) справедливо равенство Ыаъ = Уаь. Поэтому D(F) = {p,q}. Из этого следует, что Ind(W) С Ind(W) С V. В рассматриваемом случае N = 1, а значит выполняется соотношение Ind(W) = Ind(V). Так как B(W) = B(V), то в силу утверждения леммы 2.8 имеет место равенство W = V. Поэтому класс Ы является предполным в
Пусть теперь В(U) является предполным в В(V) и N = 0. Рассмотрим произвольную функцию F из V\U и /3-замкнутый класс \U\]{F}\a, который обозначим через W. Тогда D(F) = {p,q} для некоторого набора (p,q) Є Ind(V), а следовательно, (p,q) Є Ind(W). По этому если b(F) С В(U), то согласно леммам 2.6 и 2.7 выполняется соотношение F є U. Значит среди функций множества 6(F) найдется булева функция /, которая не содержится в классе В(U). Поэтому B(W) = B(V) в силу предполноты класса В(Ы) в B(V). Так как Ind(W) = Ind(V), то в силу утверждения леммы 2.8 выполняется соотношение W = V, а значит, класс Ы является предполным в V. Полностью описание решетки /3-замкнутых классов функций из Рк\2 не приводится в этой работы, так как, несмотря на простоту, разбор всех случаев достаточно громоздок и, главное, при этом не выявляется никаких новых содержательных эффектов.
Семейство классов с булевым замыканием 2 874.3.1 Случай = 4
Для каждого числа і, 1 і тп, определим булеву функцию hi(xi,X2) следующим образом: если a.i = 1, то hi = Х\, а если a.i = 0, то hi = х2. Рассмотрим вектор-функцию (/і,..., fm)(hi,..., hmn). Она является двоичным представлением некоторой функции G из Pfc. Так как т 2, а функции hi, ... , /imra зависят от булевых переменных хі иЇ2, то функция G зависит от одной переменной, а поскольку все функции hi, ... , hmn являются селекторными, то они содержатся в множестве B({F}), а значит, функция G принадлежит множеству [{Р}]/з. Покажем, что она искомая.
Обозначим через {gi, ... , дт) двоичное представление функции G. Так как функции /з, ... , fm являются функционально зависимыми от функций _/ ! и /2, то по построению функции G ее компоненты 7з, . . . , 7т являются функционально зависимыми от функций д1 и д2. Причем данные функциональные зависимости могут быть заданы теми же функциями.
Докажем соотношение F = {дг, ... , gm)(fi, ... , fm). Так как функции /3, ... , fm являются функционально зависимыми от функций f\ и /2, а функции д3, ... ,дт от функций дг и д2, то достаточно доказать справедливость равенств /і = 7i(/i, ... , fm) и f2 = g2(fi, . . . , fm). А так как компоненты функции G существенно зависят только от переменных xi и х2, то достаточно показать, что /і = g[(fi, f2) и /2 = g 2(fi, /2), где функции (/ь получены удале нием несущественных переменных xs, ,хт из функций gi и д2 соответственно. Для этого рассмотрим произвольный набор 7 из Еп. Имеют место три случая.
В данном подразделе будут найдены некоторые классы булевых функций из множеств С(к, к) или С(к, 3) при к = 2т, т 2. Для этого докажем следующую лемму.
Лемма 3.10. Пусть В — замкнутый класс булевых функций. Тогда существует такое число г = г (В), что в любом /3-замкнутом классе Л с булевым замыканием В найдется множество R функций, каждая из функций которого зависит не более, чем от г переменных, и такое, что справедливо равенство B(R) = В.
Доказательство. Пусть Л — /3-замкнутый класс функций из Рь такой, что В (Л) = В. Если все функции из класса Л являются константами, то утверждение леммы очевидно, а в качестве г можно взять число 1.
Пусть теперь среди функций класса Л имеется хотя бы одна функция, принимающая не менее двух значений. Обозначим ее через F. Тогда по лемме 2.3 в классе [{Р}]/з существует функция Я, зависящая от одной переменной, и множество компонент которой содержит селекторную функцию. Так как F є Л и класс Л является /3-замкнутым, то Я Є Л.
Известно, что у класса В существует конечный базис. Пусть он состоит из функций gi, ... ,gs. Обозначим переменные, от которых зависят эти функции, через х\, ... ,х\, где г является максимальным числом переменных у данных функций. Для каждого j, 1 j s, определим функцию Gj из Pk через ее двоичное представление: Gj = H({gj, ... ,#.,)). Тогда функция Gj зависит не более, чем от г переменных, а так как {дг, ... ,gs} С В = В (Л) и класс Л является /3-замкнутым
Доказательство. Пусть В — один из классов булевых функций из формулировки теоремы. Рассмотрим произвольный /3-замкнутый класс Л функций из Рк, такой, что В (Л) = В. В силу утверждения леммы 3.10 в классе Л существует конечное множество R функций, такое, что B(R) = В и каждая из функций данного множества зависит не более, чем от г переменных, где г = г (В).
В силу утверждения леммы 3.2 (если В — один из классов U,SU,MU,Uo,Ui,Uoi,C,Co,C\), леммы 3.3 (если В — один из классов D, D0, D\, D0\ или двойственных им К,К\,Ко,Ко\), леммы 3.4 (если В — один из классов L,Lo,L\,SL,Lo\), леммы 3.5 (если В — один из классов Р2,Т0,Ті,Т0і, S, S0\) для каждой функции F из множества Л существует функция Gp из Л, которая зависит не более, чем от max(m, к, 2к, 2к) = 2к переменных, и такая, что F Є [{GF} (J R]p. Поэтому Л С [-RJ{GF F Є И.}]/З- НО каждая из функций множеств R и {GF F Є Л} содержится в Л. Поэтому справедливо равенство Л = [R\ ]{GF F Є И.}]/З Число функций из Л, зависящих не более чем от 2к переменных, конечно. Значит конечно и множество {GF F Є Л}. Следовательно у класса Л имеется конечный базис, все функции которого зависят не более, чем от max(r, 2к) переменных.
Доказательство. Пусть В — один из классов булевых функций из формулировки теоремы. Рассмотрим произвольный /3-замкнутый класс А функций из Рщ, такой, что В (Л) = В. В силу утверждения леммы в классе Л существует конечное множество R функций, такое, что B(R) = В и каждая из функций данного множества зависит не более, чем от г переменных, где г = г (В). Пусть сначала В = О2. Так как Л С Рщ, то в силу утверждения леммы 3.7 у каждой функции F из В найдется база, состоящая не более, чем из двух функций. Значит в силу утверждения леммы 3.8 для каждой функции F существует функция Gp из Л, которая зависит не более, чем от 16 переменных переменных, и такая, что F є [{Gi?} (J R]p. Аналогичное утверждение можно получить и для классов В булевых функций, которые содержатся в классе М или Т01, в силу леммы 3.9. Если же В = I2 то данное утверждение следует из двойственности классов І2 и О2.
В теоремах 3.2 и 3.3 найдены классы булевых функций, которые содержатся в множествах С(к, к) и С(к, 3). Так как С(к, к) С С(к, 3), то классами булевых функций, для которых еще не исследованы мощности семейств /3-замкнутых классов функций из Рц3 с соответствующим булевым замыканием, являются классы Iм и 0м при /і 3. Далее будет показано, что все данные классы принадлежат множеству Q(k, 3).
Функция ип является монотонной и на нулевом наборе принимает значение 0. Поэтому ип Є М0. Покажем, что ип Є Ога. Для этого рассмотрим произвольные п наборов из Е{2п+2\ на которых функция ип равна 0. Каждый из таких наборов содержит не более 2 единиц среди компонент под номерами 1, те + 1, ... , 2тегг + 1, пг(2п + 1) + 1 (данным компонентам соответствуют переменные Х\,х2, ... ,x2n+i,y соответственно), а значит общее число единиц среди рассматриваемых компонент не превышает 2гг. Поэтому в этих наборах как минимум две из рассматриваемых компонент будут равны 0. Значит ип є MOQ.
