Дискретно-непрерывная математика (стр. 50 )

существует лишь конечное число предполных классов М1, М2, .. ,Мq; при этом система функций F полна в Рn тогда и только тогда, когда она не содержится целиком ни в одном предполном классе Mi [Кузнецов 1956]. См. также [Яблонский 1958; 1986].

7.3.3.1. Предполные классы в Р2 и Р3

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

• Т0 - класс функций, удовлетворяющих условию

(сохраняющих 0);

• T1 — класс функций, удовлетворяющих условию

(сохраняющих 1);

• L — класс линейных функций, т. е. функций вида

где (полиномы Жегалкина,

не содержащие два и более сомножителей);

• М — класс монотонных функций:

• S - класс самодвойственных функций, т. е. таких, что

(это значит, что на противоположных наборах f принимает противоположные значения.

Классыявляются замкнутыми, что устанавливается индукцией по построению формул.

Малая теорема Поста. Классыявляются

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

Критерий функциональной полноты для Р2 можно записать в следующем виде. Пусть Тогда

Необходимость этого утверждения очевидна, так как если бы

все функции из F входили в один из перечисленных классов, то и

замыкание F входило бы в этот класс и тогда класс F не полон.

При доказательстве достаточности исходим из предположения, что

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

Эта теорема Поста является следствием из обзора всех замкну­тых классов булевых функций, т. е. следствием Большой теоремы Поста [Post 1941]. Первое непосредственное доказательство этой теоремы было получено в 1951 г. (независимо от результатов Э. Поста) и опубликовано в [Яблонский 1952]. Более простое и короткое доказательство опубликовано в [Яблонский 1958]. В [Кузнецов 1959] Малая теорема Поста называется теоремой "Поста-Яблонского". Из современных доказа­тельств см., например, [Марченков 2002].

Очень важным для дальнейшего изложения является понятие сохранения предиката ρ множеством функций из заданного класса, впервые введенное в 1951 г. (см. [Кузнецов 1959; 1961]). Пусть —k-местный предикат, — n-значная функ-

ция. Говорят, что функция сохранят предикат

(или соответствующее отношение), если для любых т наборов

удовлетворяющих предикату р, набор

также удовлетворяет предикату

Предикатное описание предполных классов в Р2 было получе­но в 1951 г. (см. [Кузнецов 1959]): Т0 сохраняет предикат х = 0, T1 сохраняет х = 1, М сохраняет S сохраняет и L = сохраняет.

(Заметим, что класс линейных функций может быть также охарактеризован как сохранение предиката (см. [Марченков 2000]).

Более того, как следует из [Марченков 2000], было известно предикатное описание замкнутых классов булевых функций (результат не опуб­ликован). Первой публикацией на эту тему явилась статья [Блохина 1970]. ,

Критерий функциональной полноты для Р3 был найден [Яблонский 1954; 1958], где полностью описыва­ются все 18 предполных в Р3 классов, сохраняющих соответст­вующие предикаты (см. также [Гиндикин 1972]).

По аналогии с классами Т0 и T1 в двузначной логике в Р3 име­ется шесть классов, сохраняющих собственные подмножества мно­жества {0, 1, 2}. Обратим внимание на класс Т{0,2} - функции, со­храняющие множество {0, 2}. Заметим, что этот класс функций соответствует классу функций трехзначной логики Лукасевича Имеется также класс L линейных функций. В трехзначной логике имеются три класса монотонных функций из-за того, что можно различными способами упорядочивать числа 0, 1; 2 (0<1<2, 1<2<0, 2<0<1). Остальные упорядочивания не приводят к новым классам. Имеется только один класс самодвойственных функций. Имеются еще три класса, являющихся более тонкими аналогами классов Т0 и T1 в Р2. Остается указать четыре класса, не имеющих аналогов при п = 2 (их точные аналоги совпадают с множеством всех функций Р2). Класс U0 состоит из функций, которые на любой совокупности наборов, у которых в некоторых фиксированных разрядах стоят нули, а в остальных их нет, либо не принимают значения нуль, ли­бо равны нулю на всех этих наборах. Класс U1 связан с 1 так же как U0 с 0. Класс U2 аналогичным образом связан с 2. Наконец С - класс, состоящий из всех функций, существенно зависящих не бо­лее чем от одной переменной, и функций, не принимающих, по крайней мере, одного значения (при п = 2 это класс функций от од­ной переменной).

В [Кузнецов 1959] указаны все 18 предикатов (определенных на множестве {0, 1, 2}), которые сохраняются указанными соответст­вующими предполными классами функций.

В работе [Захарова, Кудрявцев и Яблонский 1969] отмечается, что доказал, что Р4 имеет в точности 82 предполных класса.

7.3.3.2. Предполные классы в Рn

Теорема дает способ построения предполных клас­сов и говорит об их конечном числе, но этот способ не является ал­горитмом. Тем не менее она открывает перспективы для описания всех предполных классов в Рп для любогочто становится

фундаментальной проблемой п-значной логики.

Еще в 1951 г. доказал, что всякий предполный класс функций n-значной логики является классом сохранения не­которого предиката, зависящего (при п ≥ 3) от не более чем п аргу­ментов. Отсюда получается верхняя оценка: их меньше чем (неопубликовано) и был постро­ен ряд семейств предполных классов, обобщающих предыдущие примеры на n-значный случай. Первые результаты в этой области были опубликованы в статье [Яблонский 1958], например, в ней были описаны все предполные классы самодвойст­венных функций и все предполные классы, сохраняющие предикаты эквивалентности (разбиения). В [Мартынюк, I960] описаны все предполные классы монотонных функций. В [Lo Czu Kai 1963] описаны все предполные классы линейных функций. Количество найденных предполных классов стремительно росло и стали пола­гать, что число различных типов предполных классов должно расти с ростом п. Как отмечается в [Гиндикин 1972], имелась даже гипотеза, что нет описания множества предполных классов для лю­бого п, существенно более эффективного, чем описание, данное в теореме Кузнецова. Однако в [Rosenberg 1965] было анонсировано, а в книге [Rosenberg 1970] дано описание всех предполных классов в n-значной логике.

Множество всех функций сохраняющих предикат

обозначается посредством Множества являются

замкнутыми классами, которые называют также клонами.

( Множество называется клоном (clone), если F замкнуто относительно суперпозиции и ему принадлежит множество всех селекторных функций (проек­ции). Для любого и любого функцию равную значению переменной xi, называют селекторной функцией. При нали­чии всех селекторных функций значительно упрощаются многие технические выкладки. С другой стороны, клон или клон операций — это хорошо известный объект универсальной алгебры (см. [Коя 1968]).)