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

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

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 104 >> Следующая

хп, равно 22"-1 = V22'1.
Докажем теперь, что класс 5 замкнут. Поскольку класс 5 содержит тождественную функцию, достаточно показать, что функция
Ф — /(А...../«)
является самодвойственной, если /, flt ../т самодвойственны. Последнее устанавливается непосредственно:
ф*=/*(/:..........................&)-/(/,...................м=ф.
Докажем теперь лемму о несамодвойственпой функции.
Лемма 1. Если /(х„ ..:?„)#?, то из нее путем подстановки функций х и х можно получить несамодвойственную функцию одного переменного, т. е. константу.
Доказательство. Так как }&5, то пайдется набор (а*, ..ап) такой, что
/ (®15 • • ч ОСп) /(с^, . • 0?п) •
Рассмотрим функции ф;(#) = (г = 1, ..п) и положим
ф(а:)=/(ф1(д:)) .. фп(я)).
3*
36 ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМ^
Мы имеем
ф (0) = / (ф! (0)...<р„ (0)) = / (о“1..о““) -
— /(с^, ...,а„)= /(а,, .= /(Г1, ..1“”) -
= /(91(1). • • •., Ф» (1)) = Ф (1)-
Лемма доказана.
4. Здесь мы будем употреблять векторную запись наборов:
сс = (а„ . •.) пп) , Р (Р* 1» • • ч Р»)
и т. п. и вместо /(аь ..ап) употреблять запись /(а).
Определение. Для двух наборов а — (аи ..., ап) и р=(р1, ..рп) выполнено отношение предшествования а р, если
^ рь ..., ап ^ р„.
Например, (0, 1, 0, 1К(1} 1,^0, 1). ^ ^
Очевидно, что если и р у, то а ^ у. Следует
отметить, что не любые пары наборов находятся в отношении предшествования, например, наборы (0, 1) и (1, 0) в таком отношении не находятся. Таким образом, множество всех наборов длины п по отношению к операции предшествования является частично упорядоченным.
Определение. Функция f (а?!, ..хп) называется монотонной, если для любых двух наборов аир таких, что а р, имеет место неравенство
/б)«/<й.
Нетрудно заметить, что функция, равная монотонной функции, также является монотонной.
Монотонными функциями, очевидно, будут 0, 1, X, X, & Х2 И X, V хг.
Обозначим через М множество всех монотонных фуцкций. Покажем, что класс монотонных функций замкнут. Поскольку тождественная функция принадлежит классу Ж, то для установления замкнутости Ж достаточно показать, что функция
Ф
ГЛ. 1. АЛГЕБРА ЛОГИКИ 37
является монотонной, если /, А, ..монотонны. Пусть х = (х15 . . *) хп) 1 х-1 — • 1 * ? ?, %
1=3 ^шь ? * •, ^трт )
— наборы пероменпых функций Ф, А» ../т, причем множество переменных функции Ф состоит из тех и только тех переменных, которые встречаются у функции /и .. /т. Пусть а и р — два набора длины п значений
переменных х, причем а (1. Эти наборы определяют наборы а1, Р\ ..ат, рл значений переменных х1, ..хт такие, что а1 р1, ..ат=^ Р’\ В силу монотонности функций А, . . /т
А (а1) < А (У), •.1ш(аГ) < Шт).
Поэтому
(А (а1) и&пхилп МП)',
и в силу монотонности / имеем
/(А(а1), •.ЫаПКДАОТ, . ., МП),
откуда получаем
Ф(“)— /(/| («*)...и(ап))< ШР’), /»№*))-
•= ф (р).
Будем называть наборы аир соседними (по г-й координате), если
а (0С1, ?«а^-ь а,, а^ц.1, ? •а^),
Р (®1, • ? •» 0Ск~1, ССь ®„) •
Докажем теперь лемму о немонотонной функции. Лемма 2. Если /(#?, ..хп)^Мл то из нее путем
подстановки констант 0 и 1 и функции х можно полу-
чить функцию х.
Доказательство. Сначала покажем, что найдется пара соседних наборов аир таких, что а р и
/й>/(р).
В самом деле, так как / Ф М, то существуют наборы
а1 и р1 такие, что а1 =^[ р1 и /(«*!>/(Р1). Если наборы
Л.ч Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
НЧІ ~ ,
а1 и р1 — соседпие, то пата цель достигнута. Если а и не являются соседними, то набор отличается от набора а1 в ( координатах, где і > 1, причем эти ^ координат в наборе а* имеют значеппе 0, а в наборе р1 — значение 1. Е силу этого между сс1 ^и р1 можно вставить і — 1 промежуточных наборов а2, а3, ..., а( таких, что
Очевидно, что наборы, стоящие в этой цепочке рядом, будут соседними. Так как /(«*)> /(?*), то по крайней меро па одной из этих нар соседних наборов — обозначил! их через а и р (а ^ р) — будет / (сс) > /(^>) - Предположим, что данные наборы имеют соседство по 1-й координате и, следовательно,
ОС • * ?» ОС;— 1, О, СС(+(, ? • ССп) ,
р = (сс.1, ..а< — 1, 1, • - ч СС„).
Рассмотрим функцпю
<р(я) = /(а„ ..ос,—1, х, ос<+1, ..ап).
Мы имеем
ф(0) =/(«!, ОС;-1, О, 0С;+?, . . СС„) = /(«)> /(?) =
= /(сеь ..., а;-,, 1, а;+1, ..к„)= ф(1).
Последнее означает, что ф(0)=1, а <р(1) = 0, т. е. ф (я) = х. Лемма доказана,
5. Последним классом является класс Ь всех линейных функций.
Он, очевидно, содержит константы 0, 1, тождественную функцию X, функции ?, XI+х2 и не содержит функций Хх& х, и х1 V Хг. Выше было показано, что этот класс также замкнут.
Докажем лемму о нелинейной функции.
Лемма 3. Если ..., хп)<? Ь, то из нее путем подстановки констант 0 и 1 и функций вида х и х, а также, быть может, путем навешивания отрицания над /, можно получить функцию х1&х2.
Доказательство. Возьмем полином Жегалкина Для /:
/ (*11 * * г 1 Хп) = 2 *Ц ? • * ^ia*
{*!«?• • Д*)
ГЛ. 1. АЛГЕБРА ЛОГИКИ 39
В силу нелинейности полинома в нем найдется член, содержащий не менее двух множителей. Без ограничения общности можно считать, что среди этих множителей присутствуют х1 и х2. Тогда можно преобразовать полином следующим образом:
Предыдущая << 1 .. 5 6 7 8 9 10 < 11 > 12 13 14 15 16 17 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed