Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
§ 4. Некоторые свойства существенных функций.
Критерий полноты
Целью этого параграфа является доказательство одного критерия полноты. Однако для этого нам необходимо несколько подробнее изучить свойства функций f(x 1, ... ..., ад) из Рь, которые зависят существенно не менее чем от двух переменных. Данные функции мы будем называть существенными. Докажем три леммы.
Лемма 3. Пусть f(xи ..ад) — существенная функция, принимающая I {I 5= 3) значений. Пусть ад — ее существенная переменная. Тогда найдутся два таких набора (а, а2, ..а„) и (р, од од), что
/(а, аг ,..од)Ф /(Р, од, ..од)
и f(a, хг, ..., Хп) принимает значение, отличное и от /(а, од, . -од), и от /(р, од, ..., од).
Доказательство. Так как ад — существенная переменная функции /, то найдутся такие значения од,
..., од, что последовательность
/(О, од, - - -, од), /(1, од, ..од), ...
—, /(ft — 1, Ota сд) (*)
ГЛ. 2. fe-ЗНАЧНАЯ ЛОГИКА 57
содержит не менее двух различных значений. Возможны два случая.
1) В последовательности (*) содержатся не все I значений. Рассмотрим набор (a, ч2, .. 7*) такой, что
значение /(а, 7г, • • 7«) не встречается в (*). Очевид-
но, что
/(а, ос2, -.ап)Ф /(а, 7 г, .. 7«)-
Примем за р любое из значений, для которых /(р, а2, ..., а„)Ф / (а, аг, ..., а„).
Очевидно также, что
/(р, аг, ..., ап)*? /(а, 72, ..7П).
2) В последовательности (*) встречаются все I значении. Из существенности функции / вытекает, что существует а такое, что
/{а, хг, ..хп)Ф const
(иначе бы / зависела существенно только от одной переменной) . Отсюда следует, что найдутся наборы (сс, аа, - * -..а„) и (а, 72, -.7„) такие, что
/(а, аг, ..ап)Ф /(а, -уг, ..7„).
Так как последовательность (#) содержит I (1> 3) значений, то найдется такое р, что
/(Р, а2, а п)^=/(а, аг, ..ап),
/(р, а2, а„)^/(а, ^2, ..Tfn).
Лемма доказана.
Пусть G— конечное множество. Обозначим через |G| число элементов в G.
Лемма 4 (основная). Если f{xu ..хп)—существенная функция, принимающая не менее I (I 5s 3) значений, то найдутся п подмножеств Gu ..Gn множества Ek таких, что
1 < IGJ, \Gn\<l-i
и на множестве наборов (оц, ..aIV), где (?=*
= 1, . .n)t г. е. на GiXGzX ..,Х Gn, функция f принимает I значений.
Доказательство. Можно считать, что xt — сущв^ ственная переменная функции /. На основании предыду-
58 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
щей леммы найдутся три набора
(а, а2, ..а*), (р, а2, ..а„), (а, у2, ..уп),
па которых / принимает три различных значения. Добавим к этим наборам еще I — 3 набора
(а™ а« .... ей») «Г», а» .... аї-3>),
на которых / принимает остальные I — 3 значений. Положим
Сі={а, р, в'Д а?‘8>1,
П2=\я2,у2, бз0, •. - , б(2!-ЗУ},
— 1«п, V»! 6«1)> • • ? * бї‘"3)К
Построенные множества, очевидно, удовлетворяют условиям леммы. Лемма доказана.
Определение. Система наборов вида
(с?і, . • ССі— і, ОС-;, ССі+і) ? • *і ССї—її СЕ^, СІ^і, . . ССц) Г
(СС|, * * ?» 1> Ріі ОЕі+1» . . СЕ/—і, СЕ,, СЕ„),
(«і, * • *і і) Рь ОЕі+і, . . ., СЕ/—і, рї, ОЕ3-+1, * •-, ОЕп),
(оЕі, . • ОС/—і, а,-, а(+1, . • ОЕ/—і, р/, Ип)
называется квадратом, если Яі Ф Рі и се/ Ф р/.
Лемма 5. Пусть і{хи ..., хп)—существенная функция, принимающая І (І ^ 3) значений. Тогда найдется квадрат, на котором / принимает либо более двух значений, либо два значения, причем одно из них только в од-- ной его точке.
Доказательство. Можно считать, что — существенная переменная функции /. Тогда на основании леммы 3 найдутся наборы
(а, а2, ..а»), (р, а2, ..ап), (а, уг, - • •> ТГп),
на которых / принимает три различных значения. Эти наборы порождают куб размера 2, т. е. куб, имеющий проекцию на каждую ось не более чем\ из двух точек, а размерность куба не более п. Данный куб определяется как ?
{а, р} X {а2} у2ї X ... X {аР) учК
ГЛ. 2. &-ЗНАЧНАЯ ЛОГИКА
59
Рассмотрим в этом, кубе его гиперплоскости х1 = а и X! = р (см. рис. 2). В гиперплоскости XI = а соединим точку (а2, ..., а„) с точкой {'уг, • .., Ч*) цепочкой ребер, принадлежащих этой гиперплоскости (каждое ребро — пара соседних наборов, т. е. наборов, принадлежащих гиперплоскости и отличаю- - у,
щихся аначепием ровно в 2’"" п п*"'уа
квадратов. На ребре Рц пер- (аг,(Уг, вого квадрата функция принимает значения /(а, а2, ... Рпс. 2
а„) и /(р, а2, ..а„), а на ребре В( последнего квадрата функция / не принимает хотя бы одно из этих значений. В таком случае в цепочке найдется квадрат (пусть его номер ї) такой, что на ребре Ні функция принимает значения / (а, я2, ... ..., ап) и /(р, аг, ..., ап), а на ребре Яі+І не прнпимает по крайней мере одно из этих значений. Квадрат с номером і является искомым. Лемма доказана.
Доказанные леммы допускают простую геометрическую интерпретацию. Пусть }(хи .. ., хп)—существенная функция, принимающая I значений, где I > 3. Тогда:
1. Существует куб размера 2 такой, что на нем функция / принимает по крайней мер’е^ три значения (лемма 3).
2. Существует куб размера 1-і такой, что на нем функция / принимает все I значений (лемма 4).
3. Существует квадрат, на котором функция / принимает либо более двух значений, либо ровно два, из которых одно в одной точке (лемма 5).
