Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 18

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 12 13 14 15 16 17 < 18 > 19 20 21 22 23 24 .. 104 >> Следующая

Замечание 1. Леммы 3 и 4 не имеют смысла для к — 2, лемма 5 имеет смысл, но неверна, так как функция
одной коордипатс). Данная цепочка ребер определяет цепочку ребер в гиперплоскости Х1= р, являющуюся ее проекцией. Пара соответствующих ребер этих цепочек образует квадрат. Следовательно, мы имеем цепочку
/Є,|4 И I !**?
і і I I I !
/(??і, Д?а) Х\ Х%
в своей области определения — а она есть квадрат,— принимает два значения, и оба с кратностью два.
Г,II 4.1. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Мнмечание 2. Леммы 4 и 5 не допускают усилении. В самом деле, пусть 3 < / ^ 1, п^З и
[г при хг — . .. = хп = г, I ^ / — 1,
/г .... а:») =
(0 в остальных точках.
Пусть б], .. — произвольные множества из Ец и
1^10.1, \0и\.<1-2.
Тогда на (Л X ... X функция /; не может принимать все I значений. Далее, па любом квадрате /* принимает не более двух значений.
При рассмотрении функций /{д;,, ..д;„) из Рк, обладающих определенными свойствами на некотором множестве <? = X ... X С?„, часто приходится переходить к функциям }'(х . .., хп), обладающим аналогичными свойствами, но, может быть, на другом множестве — = б1! X ... X Переход от функции / к функции
мы будем называть нормировкой. Следовательно, нормировка связана с преобразованием переменных и преобразованием значений функции вида
1’{хи .. #„)= яН/ОМ^), • • •. 'Ы^)))-В этих преобразованиях мы исходим из того, что
| I ?= I Сц | ? - •» | &п I = 1 &г, 1 = 1п. Обозначим через
Цо, ..., “П1-1 значения, которые принимает / на множестве ё>, и через г)о, * ? ? > т^_1 — набор из попарно различных чисел множества Ек. Таким образом, нормировка определяется указанием взаимно однозначных соответствий между множествами:
•• ч Пг-х} ~ Ыог - -1 вх~(?и
Оп ~ 0'п.
Эти взаимно однозначные соответствия могут быть подчинены дополнительному требованию, например, чтобы фиксированная точка (сЦ ..ап) из & соответствовала фиксированной точке (осД..., а«) из В' и чтобы тр соответствовало тр. Ясно, что эти соответствия могут быть осуществлены при помощи функций ^{з), ^(з),
ГЛ. 2. fe-ЗНАЧЦАЯ ЛОГИКА
61
..из Рк, которые всегда можно выбрать из множества подстановок; если Z, 1и ..., 1п < к — 1, то их можно выбрать из множества функций одной переменной, принимающих не более к — 1 значений. Очевидно, что при нормировке кратности значений функции /' на такие же, как кратности соответствующих значений функции / на <§. В дальнейшем нормировка используется в следующих видах:
1) {По» ? • ?» тц'-il. ф(я) = х,
G\ = {0 h — 1} (f = 1, ..п).
2) Gi = G'it if-i {x) = x (Z — 1, ..., n),
Ьъ “nl-i! ={°f Z — 1}.
3) {%, . ..л = {0, — , Z — 1},
G\ = {0, 1} (Z — 1, n).
Случаи 1 (преобразование переменных) и 2 (преобразование значений) — случаи неполной нормировки. В качестве фиксированных точек тр и (аь . ..,а[г) обычно берутся 0 и (0, .. 0).
Докажем теперь теорему, являющуюся обобщением известной теоремы Слупецкого {[50]).
Теорема 7. Пусть система $ функций из Ph, где & З5 3, содержит все функции одной переменной, принимающие не более к— 1 значений. Тогда для полноты системы ф необходимо и достаточно, чтобы $ содержала существенную функцию f{xu ..., хп), принимающую все к значений.
Доказательство. Необходимость. Пусть $ — полная система. Предположим, что !? не содержит существенной функции, принимающей все к значений. Очевидно, что тогда из $ нельзя получить существенной функции, принимающей все к значений. Мы пришли к противоречию. Значит $ содержит существенную функцию, принимающую все к значений.
Достаточность. Пусть $ удовлетворяет условию теоремы и содержит существенную функцию f(xu..хп), принимающую все к значений. Покажем, пользуясь индукцией, что S? полна.
1). Базис индукции. Покажем, что из ^ можно получить все функции из Рь, принимающие два значения.
(Ї2 Ч. І. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
На основании леммы 5 найдется квадрат
(«і, • • Яі—і, Ctj, Cij-)-i, • . >, Cij—і, Otj, OCj + i, • • •, OCn) ,
(tti, . . P(, яі+1, • ? -i я-я-і, . .Gn) j
(tti, . . (Xj_t, pt, ttf-i-i, . . ., ttj-t, Pj, Яj-f-і, ..ocn),
(gCl, . . ., Яі—j, Gif, CSf+1, . • CCj—i) Pj, Ctj+i, . .Яц) j
где at ?= р( и a} Ф pJs па котором функция / принимает не менее двух значений, причем ОДНО ИЗ НИХ, Г),— в одной точке. Возьмем функцию ф (сс) такую, что
[0 при х = цл
Ф W \ Л /
при хф Т|.
Очевидно, ЧТО ф(х) S ф. Пусть g{xи Хг) =
“ф(У(яі, • * ч *Гіі ? ч Gtj—і, х2) яп)).
Функция g(xi, ar2) на квадрате {(af, a}), (p1? a}), {p(, pj), (а(, Pj)} принимает два значения, 0 и 1, причем значение 0 в одной точке; обозначим ее (и®, о^). Осуществляя неполную нормировку так, чтобы (0, 0) отображалось в (а?! а"), а квадрат {(0, 0), (І, 0), (1.1), (1, О)} — в указанный выше квадрат, получим функцию g' (zi, xz), где
g'(Xi, X2) = g($l(x1), Ы^))
И фі, я)?2 <= ф. Функция g'{х 1, я2), очевидно, єсть максимум на множестве (0, 1} X (0, її. Обозначим ее через Хі V й%х2. Так как система $ содержит функции jt{x)t где
(і при х = ir
J г (^) — |q прИ хфІ%
ТО
Xi & mXz = UXh(Xi) V 01/0 (3:2) )
есть минимум на мпожестве {0, 1} X (0, 1). Пу^ть h (zit ..хт), h Ф const,— произвольная функция, принимающая два значения, 0 и 1; тогда
Предыдущая << 1 .. 12 13 14 15 16 17 < 18 > 19 20 21 22 23 24 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed