стр. 1
(всего 2)

СОДЕРЖАНИЕ

>>

Московский Государственный Университет
имени М. В. Ломоносова
Факультет Вычислительной Математики и Кибернетики
Кафедра Математической Кибернетики




Дискретная математика
(II семестр)
лектор — профессор В. Б. Алексеев

составитель — А. Д. Поспелов




Москва 2002
Содержание
Глава I. Функции алгебры логики
§1. Функции алгебры логики. Равенство функций. Тождества для элементарных функций 3
§2. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной 5
дизъюнктивной нормальной форме
§3. Полные системы. Примеры полных систем 6
§4. Теорема Жегалкина о представимости функции алгебры логики полиномом 6
§5. Понятие замкнутого класса. Замкнутость классов T0, T1 и L 8
§6. Двойственность. Класс самодвойственных функций, его замкнутость 9
§7. Класс монотонных функций, его замкнутость 10
§8. Лемма о несамодвойственной функции 10
§9. Лемма о немонотонной функции 11
§10. Лемма о нелинейной функции 11
§11. Теорема Поста о полноте системы функций алгебры логики 12
§12. Теорема о максимальном числе функций в базисе алгебры логики 12
§13. Теорема о предполных классах 13
§14. k-значные функции. Теорема о существовании конечной полной системы в множестве 13
k-значных функций
Глава II. Основы теории графов
§15. Основные понятия теории графов. Изоморфизм графов. Связность 15
§16. Деревья. Свойства деревьев 16
§17. Корневые деревья. Верхняя оценка их числа 17
§18. Геометрическая реализация графов. 18
Теорема о реализации графов в трёхмерном пространстве
§19. Планарные (плоские) графы. Формула Эйлера 19
§20. Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского 20
§21. Теорема о раскраске планарных графов в пять цветов 21
Глава III. Основы теории управляющих систем
§22. Схемы из функциональных элементов. Реализация функций алгебры логики схемами 23
§23. Сумматор. Верхняя оценка сложности сумматора. Вычитатель 25
§24. Метод Карацубы построения схемы для умножения, верхняя оценка её сложности 26
§25. Дешифратор. Асимптотика сложности дешифратора. Верхняя оценка сложности 28
реализации произвольной функции алгебры логики
§26. Мультиплексор. Верхняя оценка сложности мультиплексора. Метод Шеннона 29
§27. Шифратор. Верхняя оценка сложности шифратора 31
Глава IV. Основы теории кодирования
§28. Алфавитное кодирование. 32
Теорема Маркова о взаимной однозначности алфавитного кодирования
§29. Неравенство Макмиллана 33
§30. Существование префиксного кода с заданными длинами кодовых слов 33
§31. Оптимальные коды, их свойства 34
§32. Теорема редукции 35
§33. Коды с исправлением r ошибок. Оценка функции Mr (n). 36
§34. Коды Хэмминга. Оценка функции M1 (n) 37
Глава V. Основы теории конечных автоматов
§35. Понятие ограниченно детерминированных (автоматных) функций, их представление 39
диаграммой Мура. Единичная задержка
§36. Схемы из функциональных элементов и элементов задержки. Автоматность 40
осуществляемых ими отображений
§37. Моделирование автоматной функции схемой из функциональных элементов и элементов 41
задержки
§38. Теорема Мура. Теорема об отличимости состояний двух автоматов 42




2
Глава I. Функции алгебры логики.
§1. Функции алгебры логики. Равенство функций.
Тождества для элементарных функций.
1°. Функции алгебры логики.
Определение 1. Пусть E2 = {0, 1} — основное множество (исходный алфавит значений
переменных), тогда E2 = {(?1, …, ?n) | ?i ?i?E2}. Тогда всюду определённой булевой функци-
n


ей назовём отображение f (x1, …, xn): E2 > E2. Такую функцию можно задать таблично, а
n


можно как суперпозицию других, более простых функций. Например, для n = 1:
x01xx
00101
10110
При этом функция 0 называется константой нулём, функция 1 — константой едини-
цей, функция x — тождественной, а функция x — отрицанием x. При этом для последней
функции допускается также иное обозначение: x ? ¬x .
Для n = 2:
x y f1 f2 f3 f4 f5 f6 f7
0 0 0 0 0 1 1 1 1
0 1 1 0 1 1 0 1 0
1 0 1 0 1 0 0 1 0
1 1 1 1 0 1 1 0 0
При заполнении таблицы столбцы переменных заполняются в лексикографическом по-
рядке (по возрастанию двоичных чисел).
f1 — дизъюнкция, функция «или», логическое сложение: f1 = x ? y.
f2 — конъюнкция: f2 = x · y = x & y = xy.
f3 — сложение по модулю 2 (исключающее «или»): f3 = x ? y = x + y.
f4 — импликация: f4 = x > y.
f5 — эквивалентность: f5 = x ˜ y = x ? y .
f6 — штрих Шеффера: f6 = x | y = xy .
f7 — стрелка Пирса: f7 = x v y = x ? y .
Лемма (о числе слов). В алфавите A = {a1, …, ar} из r букв можно построить ровно rm
различных слов длины m.
Доказательство. Проведём индукцию по m. Для m = 1 утверждение очевидно. Пусть
утверждение леммы верно для m – 1, то есть существует ровно rm – 1 различных слов длины
m – 1. Для каждого такого слова длины m – 1 существует ровно r возможностей добавить од-
ну букву в конец. Так как всего слов длины m – 1 — rm – 1, то различных слов длины m полу-
чится r · rm – 1 = rm. Лемма доказана.
Рассмотрим таблицу некоторой функции алгебры логики от n переменных.
x1 x2 ! xn f
?0 ?
?0 0 ! 0
?1 ? 2 n
?0 0 ! 1
n? ?
2? ?2
!?
!!!!
?
? 1 1 ! 1 ? 2n ?1 ?
? ?



3
Для её задания необходимо и достаточно определить её значения на 2n наборах. Таким обра-
зом, получаем, что всего различных функций от n переменных столько, сколько существует
n
различных наборов из нулей и единиц длины 2n, т.е. 2 2 .
Используя последний факт можно, например, получить оценку числа функций от 10 пе-
() > (1000 ) = 10300 . Таким об-
100
10 100
ременных. Всего таких функций будет 22 = 21024 > 21000 = 210
разом, при росте числа переменных число функций возрастает очень быстро, и их табличное
задание становится неудобным.
2°. Равенство функций. В обычной алгебре справедливо равенство x + y – y = x, не-
смотря на то, что в левой части записана функция от двух переменных, а в правой — от од-
ной. Таким образом, функции от разного числа переменных могут быть одинаковыми, что
даёт повод ввести понятие существенных и фиктивных переменных.
Определение 2. Переменная xi называется существенной переменной функции алгебры
логики f (x1, …, xn), если существуют такие ?1, …, ?i – 1, ?i + 1, …, ?n?E2, что
f (?1, …,?i – 1, 0, ?i + 1,…, ?n) ? f (?1, …, ?i – 1, 1, ?i + 1, …, ?n).
Такие наборы, отличающиеся лишь одной переменной xi, называются соседними по xi. В про-
тивном случае переменная xi называется фиктивной.
Если xi — фиктивная переменная функции f, то функция f однозначно определяется не-
которой функцией g (x1, …, xi – 1, xi + 1, …, xn). Таблицу любой функции можно расширить
введением любого числа фиктивных переменных.
Определение 3. Две функции алгебры логики называются равными, если одну из
них можно получить из другой путём добавления и изъятия любого числа фиктивных
переменных.
3°. Формулы.
Определение 4. Пусть имеется некоторое множество функций
A = {f1 (…), f2 (…), …, fn (…), …}.
Введем понятие формулы над A:
1) Любая функция из A называется формулой над A.
2) Если f (x1, …, xn) ? A и для любого i Hi — либо переменная, либо формула над A, то
выражение вида f (H1, H2, …, Hn) является также формулой над A.
3) Только те объекты называются формулами над A, которые можно построить с по-
мощью пунктов 1 и 2 данного определения.
Замечание. Среди H1, H2, …, Hn вполне могут быть одинаковые.
4°. Основные эквивалентности.
1. Коммутативность: 2. Ассоциативность:
x?y=y?x; (x ? y) ? z = x ? (y ? z) = x ? y ? z ;
xy = yx ; (xy) z=x (yz)=xyz ;
x?y=y?x; (x ? y) ? z = x ? (y ? z) = x ? y ? z.
x˜y=y˜x.
3. Дистрибутивность:
4. x = x ,
(x ? y) z = (xz) ? (yz) ;
правила де Моргана:
(x ? y) z = (xz) ? (yz) ;
x? y = x?y ,
(xy) ? z = (x ? z)·(y ? z).
x? y = x ? y .




4
5. Законы поглощения. 6. x y = x ? y
x?x=x
x v y = x? y
x·x=x
x> y=x? y
x ? x =1
x ? y = (x ? y ) ? (x ? y )
x?x = 0
x?1=1
x ˜ y = x ? y = (xy ) ? (x y )
x·1=x
x?0=x
x · 0 = 0.
Приоритет конъюнкции выше, чем приоритеты дизъюнкции и суммы по модулю 2. Благо-
даря этому, часто удаётся опустить ряд ненужных скобок. Имеют место следующие очевидные
утверждения:
x1 · x2 · … · xn = 1 ? ?i xi = 1,
x1 ? x2 ? … ? xn = 1 ? ?i: xi = 1.
? x, ? = 1 ?
Определение 5. x в степени сигма называется функция x? = ? ; x = 1 ? x = ?.
? x ,? = 0

§2. Теорема о разложении функции алгебры логики по переменным.
Теорема о совершенной дизъюнктивной нормальной форме.
Теорема 1 (о разложении функции алгебры логики по переменным). Для любой
функции алгебры логики f (x1, …, xn) и для любого k (1 ? k ? n) справедливо следующее
равенство:
f (x1 ,!, xn ) = x1 1 ? x2 2 ? ! ? xk k ? f (? 1 , ? 2 ,!, ? k , xk +1 ,! , xn ) .
? ? ?
?
( ) k
? 1 ,? 2 ,!,? k ?E2


Доказательство. Для любого набора ? = (?1 ,? 2 ,!,? n ) вычислим значение правой час-
˜
ти на этом наборе. Как только хотя бы один из сомножителей будет равен нулю, вся конъ-
юнкция обратится в нуль. Таким образом, из ненулевых конъюнкций останется лишь одна —
та, в которой ?i = ?i и
?1? 1 ? ? 2 2 ? ! ? ? k k f (? 1 , ? 2 ,!, ? k ,? k +1 ,!,? n ) = 0 ? ! ? 0 ? ?1 1 ? ? 2 2 "? k k f (?1 ,!,? n ),
? ? ? ? ?
?
(? 1 ,? 2 ,!,? k )?E2
k



а в силу того, что xx = 1, указанное выражение равно f (?1, ?2, …, ?n). Теорема доказана.
Следствие 1. Разложение произвольной функции алгебры логики по одной переменной
имеет вид f (x1 , x2 ,!, x n ) = x1 f (0, x2 ,!, x n ) ? x1 f (1, x2 ,!, xn ).
Следствие 2 (теорема о совершенной дизъюнктивной нормальной форме). Для лю-
бой функции алгебры логики f (x1, x2, …, xn), отличной от тождественного нуля, справедливо
следующее представление:
f (x1 ,!, xn ) = ?? ?
? x1 1 x2 2 " xn n .
(?1 ,!,? n ): f (?1 ,!,? n )=1

Доказательство. Пусть функция f (x1, x2,…, xn) отлична от тождественного нуля. Напи-
шем разложение этой функции по k = n переменным:
f (x1 ,!, xn ) = x1 1 x2 2 ! xn n f (? 1 , ? 2 ,!, ? n ),
?? ?
?
( )n
? 1 ,? 2 ,!,? n ?E2

что можно переписать в эквивалентном виде
x1 1 x2 2 ! xn n f (? 1 ,!, ? n ) ? x1 1 x2 2 ! xn n f (? 1 ,!, ? n ) .
? ?
?? ??
? ?
(?1 ,!,? n ): f (?1 ,!,? n )=1 (?1 ,!,? n ): f (?1 ,!,? n )=0




5
Учитывая, что в первой дизъюнкции все значения функции равны единице, а вторая об-
нуляется из-за того, что все значения функции в ней равны нулю, получаем утверждение
следствия. Следствие доказано.
Теорема 2 (о совершенной конъюнктивной нормальной форме). Для любой функции
алгебры логики f (x1, x2, …, xn), отличной от тождественной единицы, справедливо
представление
(x )
f (x1 ,!, xn ) = ?1 ? ?
? x2 2 ? ! ? xn n .
& 1
(? 1 ,? 2 ,!,? n )
f (? 1 ,? 2 ,!,? n )= 0




§3. Полные системы. Примеры полных систем (с доказательством полноты).
Определение. Множество функций алгебры логики A называется полной системой
(в P2), если любую функцию алгебры логики можно выразить формулой над A.
Теорема 3. Система A = {?, &, ¬} является полной.
Доказательство. Если функция алгебры логики f отлична от тождественного нуля, то f
выражается в виде совершенной дизъюнктивной нормальной формы, в которую входят лишь
дизъюнкция, конъюнкция и отрицание. Если же f ? 0, то f = x ? x . Теорема доказана.
Лемма 2. Если система A — полная, и любая функция системы A может быть выражена
формулой над некоторой другой системой B, то B — также полная система.
Доказательство. Рассмотрим произвольную функцию алгебры логики f (x1, …, xn) и две
системы функций: A = {g1, g2, …} и B = {h1, h2, …}. В силу того, что система A полна, функ-
ция f может быть выражена в виде формулы над ней: f (x1 ,!, xn ) = ?[g1 , g 2 ,!], где
g i = ? i [h1 , h2 ,!], то есть функция f представляется в виде f (x1 ,!, xn ) = ?[?1 , ? 2 ,!], иначе
говоря, может быть представлена формулой над B. Перебирая таким образом все функции
алгебры логики, получим, что система B также полна. Лемма доказана.
Теорема 4. Следующие системы являются полными в P2:
1) {x ? y, x };
2) {x ? y, x };
3) {x | y};
4) {x · y, x ? y , 1}.
Доказательство. 1) Известно (теорема 3), что система A = {x ? y, x ? y, x } полна. Пока-
жем, что полна система B = {x ? y, x}. Действительно, из закона де Моргана x ? y = x ? y по-
лучаем, что x ? y = x ? y , то есть конъюнкция выражается через дизъюнкцию и отрицание, и
все функции системы A выражаются формулами над системой B. Согласно лемме 2 система
B полна.
2) Аналогично пункту 1: x ? y = x ? y ? x ? y = x ? y и из леммы 2 следует истинность
утверждения пункта 2.
3) x | x = x , x ? y = x | y = (x | y ) | (x | y ) и согласно лемме 2 система полна.
4) x = x ? 1 и согласно лемме 2 система полна.
Теорема доказана.

§4. Теорема Жегалкина о представимости функции алгебры логики полиномом.
Определение 1. Монотонной конъюнкцией от переменных x1,…, xn называется любое
выражение вида xi1 ? xi2 ? xi3 " xis , где s ? 1, 1 ? ij ? n ?j = 1, 2, …, s, все переменные различны
(ij ? ik, если j ? k); либо просто 1.




6
Определение 2. Полиномом Жегалкина над x1, …, xn называется выражение вида
K1 ? K2 ? K3 ? … ? Kl,
где l ? 1 и все Kj суть различные монотонные конъюнкции над x1, …, xn; либо константа 0.
Теорема 5 (теорема Жегалкина). Любую функцию алгебры логики f (x1, …, xn) можно
единственным образом выразить полиномом Жегалкина над x1, …, xn.
Доказательство. 1) Докажем существование полинома. Система {x · y, x ? y, 1} полна,
следовательно, любую функцию алгебры логики f (x1, …, xn) можно реализовать формулой
над {x · y, x ? y, 1}.
a) Пользуясь дистрибутивностью, раскрываем все скобки в этой реализации и получа-
ем, что f (x1, …, xn) = K1? ? K2? ? … ? Kl?, где любая Ki? — конъюнкция переменных
и единиц.
b) Преобразуем все полученные конъюнкции в элементарные, пользуясь при этом
коммутативностью и соотношениями x · x = x, 1 · 1 = 1 и A · 1 = A. Очевидно, все
конъюнкции станут монотонными.
c) Преобразуем полученную сумму в полином Жегалкина, пользуясь при этом соот-
ношениями A ? A = A и A ? 0 = A. В результате получим либо
K i1 ? K i2 ? K i3 ? ! ? K im ,
либо константу 0.
Существование доказано.
2) Докажем единственность представления. Подсчитаем число различных всевозмож-
ных монотонных конъюнкций от n переменных. Для этого составим таблицу вида
x1 x2 x3 x4
x1 x2 x4 1 1 0 1
,
x2 x3 0 1 1 0
1 0 0 0 0
где каждой переменной соответствует единица, если она присутствует в монотонной конъ-
юнкции и ноль в противном случае. При этом константе единице поставим в соответствие
нулевой набор. Очевидно, что построенное отображение биективно. Следовательно, всего
различных монотонных конъюнкций от n переменных — 2n. Построим аналогичное биек-
тивное отображение между всевозможными суммами монотонных конъюнкций и векторами
длины 2n — числа конъюнкций. Для этого составим таблицу вида
xy x y 1
xy + 1 1 0 0 1 ,
0 0000
где под соответствующей монотонной конъюнкцией стоит единица, если она входит в дан-
ную сумму, и ноль, если не входит. При этом константе ноль ставится в соответствие нуле-
вой набор. Очевидно, такое отображение биективно. Всего таких различных сумм будет
n
столько, сколько существует различных булевых векторов длины 2n, то есть — 2 2 . Мы по-
лучили, что число различных полиномов Жегалкина совпадает с числом функций алгебры
логики. Поскольку отображение из множества полиномов во множество функций сюръек-
тивно, то оно и биективно, так как множества полиномов Жегалкина над n переменными и
функций алгебры логики от n переменных равномощны. Единственность доказана.




7
§5. Понятие замкнутого класса. Замкнутость классов T0, T1 и L.
1°. Понятие замкнутого класса.
Определение 1. Пусть A ? P2. Тогда замыканием A называется множество всех функ-
ций алгебры логики, которые можно выразить формулами над A.
Обозначение: [A].
Имеют место следующие свойства:
1) [A] ? A;
2) A ? B ? [A] ? [B], причём, если в левой части импликации строгое вложение, то из
него вовсе не следует строгое вложение в правой части — верно лишь
A ? B ? [A] ? [B];
3) [[A]] = [A].
Определение 2. Система функций алгебры логики A называется полной, если [A] = P2.
Определение 3. Пусть A ? P2. Тогда система A называется замкнутым классом, если за-
мыкание A совпадает с самим A: [A] = A.
Утверждение. Пусть A — замкнутый класс, A ? P2 и B ? A. Тогда B — неполная система
(подмножество неполной системы будет также неполной системой).
Доказательство. B ? A ? [B] ? [A] = A ? P2 ? [B] ? P2. Следовательно, B — неполная
система. Утверждение доказано.
2°. Примеры замкнутых классов.
Класс T0 = {f (x1, …, xn) | f (0, …, 0) = 0}.
Классу T0 принадлежат, например, функции 0, x, xy, x ? y, x ? y.
Классу T0 не принадлежат функции 1, x , x > y, x | y, x v y, x ˜ y.
Подсчитаем число функций в классе T0. Для этого построим следующую таблицу:
x1 ! xn
0! 00 .
! ! ! }2 n ? 1
Все функции, принадлежащие указанному классу, принимают на нулевом наборе нуле-
вое значение. Таким образом, всего функций в классе T0 столько, сколько существует буле-
вых векторов длины 2n – 1 (первый разряд вектора длины 2n необходимо равен нулю), то есть
n n
T0 = 2 2 ?1 = 1 2 2 .
2

Теорема 6. Класс T0 —замкнутый.
{ ( )}
( )
Доказательство. Пусть f (x1 ,!, xn ), g1 y11 ,!, y1m1 ,!, g n yn1 ,!, ynmn ? T0 . Рассмотрим
(( ( ))
)
функцию h( y1 ,!, y r ) = f g1 y11 ,!, y1m1 ,!, g n y n1 ,!, y nmn . Среди переменных функций gi
могут встречаться и одинаковые, поэтому в качестве переменных функции h возьмём все
различные из них. Тогда h (0, …, 0) = f (g1 (0, …, 0), …, gn (0, …, 0)) = f (0, …, 0) = 0 , следова-
тельно, функция h также сохраняет ноль. Рассмотрен только частный случай (без перемен-
ных в качестве аргументов). Однако, поскольку тождественная функция сохраняет ноль,
подстановка простых переменных эквивалентна подстановке тождественной функции, тео-
рема доказана.
Класс T1 = {f (x1, …, xn) | f (1, 1, …, 1) = 1}.
Классу T1 принадлежат функции 1, x, xy, x ? y, x > y, x ˜ y.
Классу T1 не принадлежат функции 0, x , x ? y, x | y, x v y.
Теорема 7. Класс T1 замкнут.
Доказательство повторяет доказательство аналогичной теоремы для класса T0.


8
Класс L линейных функций.
Определение 4. Функция алгебры логики f (x1, …, xn) называется линейной, если
f (x1, …, xn) = a0 ? a1 x1 ? … ? an xn, где ai ? {0, 1}.
Иными словами, в полиноме линейной функции нет слагаемых, содержащих конъюнкцию.
Классу L принадлежат функции 0, 1, x = x ? 1 , x ˜ y, x ? y.
Классу L не принадлежат функции xy, x ? y, x > y, x | y, x v y.
Теорема 8. Класс L замкнут.
Доказательство. Поскольку тождественная функция — линейная, достаточно (как и в
теоремах 6 и 7) рассмотреть только случай подстановки в формулы функций: пусть
f (x1, …, xn) ? L и gi ? L. Достаточно доказать, что f (g1, …, gn)?L. Действительно, если не учи-
тывать слагаемых с коэффициентами ai = 0, то всякую линейную функцию можно представить
в виде xi1 ? xi2 ? ! ? xik ? a0 . Если теперь вместо каждого xi j подставить линейное выражение,
то получится снова линейное выражение (или константа единица или нуль).

§6. Двойственность. Класс самодвойственных функций, его замкнутость.
1°. Двойственность.
Определение 1. Функцией, двойственной к функции алгебры логики f (x1, …, xn), назы-
( )
вается функция f ? (x1 ,!, xn ) = f x1 ,!, xn .
Теорема 9 (принцип двойственности). Пусть
(( ( ))
)
?( y1 ,!, ym ) = f g1 y11 ,!, y1k1 ,!, g n yn1 ,!, ynkn .

(( ),!, g (y ))
Тогда ? ? ( y1 ,!, ym ) = f ? g1? y11 ,!, y1k1 ?
,!, ynk n .
n n1

Доказательство. Рассмотрим
(( ) ( ))=
? ? ( y1 , ! y m ) = f g1 y11 , ! , y1k1 , ! , g n y n1 ,! , y nk n
(( )) ( ( ))=
) ( (
)
? ?
= f g1 y11 ,!, y1k1 ,!, g n yn1 ,!, ynkn = f g1 y11 , !, y1k1 ,!, g n yn1 ,!, ynkn
(g (y ,!, y ),!, g (y )).
= f? ? ?
,!, ynk n
1 11 1k 1 n1
n


Теорема доказана.
Следствие. Пусть функция ? (y1, …, ym) реализуется формулой над A = {f1, f2, …}. Тогда
если в этой формуле всюду заменить вхождения fi на fi*, то получится формула, реализующая
?* (y1, …, ym).
Утверждение. Для любой функции алгебры логики f (x1, …, xn) справедливо равенство
f (x1, …, xn)=f** (x1, …, xn).

)] = f (x ,!, x ) = f (x ,!, x ) , и утверждение доказано.
[( ?
Доказательство. f ?? = f x1 ,! , xn 1 1
n n

2°. Класс S самодвойственных функций.
Определение 2. Функция алгебры логики f (x1, …, xn) называется самодвойственной, если
f (x1, …, xn) = f* (x1, …, xn).
Иначе говоря, S = {f | f = f*}.
Классу S принадлежат функции
?1, x + y + z ? 2
x, x , x ? y ? z ? a, m(x, y, z ) = xy ? yz ? zx = ? .
0, x + y + z ? 1
?




9
Классу S не принадлежат функции
0 ( f (x ) ? 0 ? f ? (x ) = f (x ) ? 1 ), 1, x ? y (поскольку (x ? y ) = x ? y = x ? y ? x ? y ), xy.
?



Теорема 10. Класс S замкнут.
( )
Доказательство. Пусть f (x1, …, xn) ? S, ?i g i yi1 ,!, yiki ? S , i = 1, 2, …, n и

(( ( ))
)
? = f g1 y11 ,!, y1k1 ,!, g n yn1 ,!, ynkn .
Тогда из принципа двойственности следует, что
(( ( )) = f (g1 (…), …, gn (…)).
)
? ? = f ? g1? y11 ,!, y1k1 ,!, g n yn1 ,!, ynkn
?



Таким образом, мы получили, что ? = ?* и ? ? S. Теорема доказана.

§7. Класс монотонных функций, его замкнутость.
˜
Определение 1. Пусть ? = (?1 ,? 2 ,! ,? n ) и ? = (?1 , ? 2 ,!, ? n ) . Тогда
˜

˜˜
? ? ? ? ?i (? i ? ? i ) .
Замечание. Существуют наборы, для которых неприменимо отношение упорядоченно-
сти, определённое выше. Так, например, наборы (0, 0, 1) и (0, 1, 0) несравнимы.
Определение 2. Функция алгебры логики f (x1, …, xn) называется монотонной, если для
˜˜
любых двух сравнимых наборов ? и ? выполняется импликация

()
˜˜ ˜
? ? ? ? f (? ) ? f ? .
˜

Класс M всех монотонных функций.
Классу M принадлежат функции 0 , 1 , x , xy , x ? y, m (x, y, z) = xy ? yz ? zx.
Классу M не принадлежат функции x , x | y , x v y , x ? y , x ˜ y , x > y.
Теорема 11. Класс M замкнут.
Доказательство. Поскольку тождественная функция монотонна, достаточно проверить
лишь случай суперпозиции функций. Пусть f (x1, …, xn) ? M, для любого j gj (y1, …, ym)?M и
? (y1, …, ym) = f (g1 (y1, …, ym), …, gn (y1, …, ym)).
˜ ˜˜
Рассмотрим произвольные наборы ? = (?1 ,!,? m ), ? = (?1 ,!, ? m ) такие, что ? ? ? . Обозначим
˜

()
˜
gi (? ) = ? i , g i ? = ? i .
˜

()
˜
Тогда для любого i имеем gi ? M и g i (? ) ? gi ? , то есть ?i (? i ? ? i ) . Обозначим
˜
˜
? = (? 1 , ? 2 ,!, ? n ), ? = (? 1 , ? 2 ,!, ? n ).
˜

()
˜˜ ˜
Тогда по определению ? ? ? и, в силу монотонности функции f, f (? ) ? f ? . Но ˜

() ()
˜ ˜
?(? ) = f (? 1 ,!, ? n ) = f (? ) , ? ? = f (? 1 ,!, ? n ) = f ? ,
˜ ˜

() ()
˜ ˜
и неравенство f (? ) ? f ? ? ?(? ) ? ? ? , следовательно, Ф ? M. Теорема доказана.
˜ ˜

§8. Лемма о несамодвойственной функции.
Лемма (о несамодвойственной функции). Из любой несамодвойственной функции ал-
гебры логики f (x1, …, xn), подставляя вместо всех переменных функции x и x, можно полу-
чить ? (x) ? const.


10
( )
Доказательство. Пусть f ? S. Тогда f x1 ,!, xn ? f (x1 ,!, xn ) ? ?? = (? 1 ,!, ? n ):
˜

( ) ( )
f ? 1 ,!, ? n ? f (? 1 ,!, ? n ) ? f ? 1 ,!, ? n = f (? 1 ,!, ? n ).
Построим функцию ? (x) так: ? (x) = f (x ? ?1, …, x ? ?n). Действительно,
( )
? (0) = f (?1, …, ?n), ? (1) = f ? 1 ,!? n
и ? (0) = ? (1) ? ? (x) = const. Заметим, что подстановка удовлетворяет условию теоремы, так
? x, ? = 0
как x ? ? = ? . Лемма доказана.
x ,? = 1
?

§9. Лемма о немонотонной функции.
Лемма (о немонотонной функции). Из любой немонотонной функции алгебры логики
f (x1, …, xn), подставляя вместо всех переменных функции x, 0, 1, можно получить функцию
? (x ) ? x .
Доказательство. Пусть f ? M. Тогда существуют такие наборы ? = (?1 ,!,? n ) и ˜

()
˜ ˜˜ ˜˜ ˜
? = (?1 ,!, ? n ) , что ? < ? (то есть ?j (?j ? ?j) и ? ? ? ) и f (? ) > f ? . Выделим те разряды
˜
˜
˜ ˜
i1, …, ik наборов ? и ? , в которых они различаются. Очевидно, в наборе ? эти разряды
˜
равны 0, а в наборе ? — 1. Рассмотрим последовательность наборов
˜˜˜ ˜
? 0 ,?1 ,? 2 ,!,? k
˜
˜˜˜˜ ˜ ˜ ˜
таких, что ? = ? 0 < ?1 < ? 2 < ! < ? k = ? , где ? i +1 получается из ? i заменой одного из нулей,
˜ ˜
расположенного в одной из позиций i1, …, ik, на единицу (при этом наборы ? i и ? i +1 — со-
() ˜
седние). Поскольку f (? ) = 1 , а f ? = 0 , среди наборов ? 0 ,?1 ,? 2 ,!,? k найдутся два сосед-
˜ ˜˜˜ ˜
них ? i и ? i +1 , такие что f (? i ) = 1 и f (? i+1 ) = 0 . Пусть они различаются в r-ом разряде:
˜ ˜ ˜ ˜
? i = (?1 ,? 2 ,!,? r ?1 ,0,? r +1 ,!,? n ), ? i+1 = (?1 ,? 2 ,!,? r ?1 ,1,? r +1 ,!,? n ) . Тогда определим функцию
˜ ˜
? (x) так: ? (x) = f (?1, ?2, …, ?r – 1, x, ?r + 1, …, ?n). Действительно, тогда ? (0) = f (? i ) = 1 , ˜
? (1) = f (? i+1 ) = 0 и ? (x ) ? x . Лемма доказана.
˜

§10. Лемма о нелинейной функции.
Лемма (о нелинейной функции). Из любой нелинейной функции алгебры логики
f (x1, …, xn), подставляя вместо всех переменных x, x , y, y , 0, 1, можно получить ? (x, y) = x·y
или ? (x, y ) = x ? y .
Доказательство. Пусть f (x1, …, xn) ? L. Рассмотрим полином Жегалкина этой функции.
Из её нелинейности следует, что в нём присутствуют слагаемые вида xi1 ? xi2 ? ! . Не ограни-
чивая общности рассуждений, будем считать, что присутствует произведение x1 · x2 · …. Та-
ким образом, полином Жегалкина этой функции выглядит так:
f (x1, …, xn) = x1 · x2 · P1 (x3, …, xn) ? x1 · P2 (x3, …, xn) ? x2 · P3 (x3, …, xn) ? P4 (x3, …, xn),
причем P1 (x3, …, xn) ? 0.
Иначе говоря, ? a3, a4, …, an ? E2 = {0, 1} такие, что P1 (a3, a4, …, an) = 1. Рассмотрим вспомо-
гательную функцию f (x1, x2, a3, a4, …, an) = x1 x2 · 1 ? x1 · b ? x2 · c ? d. Тогда функция
f (x ? с, y ? b, a3, a4, …, an) = (x ? c)(y ? b) ? (x ? c)b ? (y ? b)c ? d =
? xy, bc ? d = 0
= xy ? x · b ? y · c ? b · c ? x · b ? b · c ? y · c ? b · c ? d = xy ? (bc ? d) = ? .
? xy, bc ? d = 1
Лемма доказана.


11
§11. Теорема Поста о полноте системы функций алгебры логики.
Теорема 12 (теорема Поста). Система функций алгебры логики A = {f1, f2, …} является
полной в P2 тогда и только тогда, когда она не содержится целиком ни в одном из следую-
щих классов: T0, T1, S, L, M.
Доказательство. Необходимость. Пусть A — полная система, N — любой из классов
T0, T1, S, L, M и пусть A ? N. Тогда [A] ? [N] = N ? P2 и [A] ? P2. Полученное противоречие
завершает обоснование необходимости.
Достаточность. Пусть A ? T0, A ? T1, A ? M, A ? L, A ? S. Тогда в A существуют функции
f0 ? T0, f1 ? T1, fM ? M, fL ? L, fS ? S. Достаточно показать, что [A] ? [f0, f1, fM, fL, fS] = P2. Разо-
бьём доказательство на три части: получение отрицания, констант и конъюнкции.
a) Получение x . Рассмотрим функцию f0 (x1, …, xn) ? T0 и введём функцию ?0 (x) =
= f0 (x, x, …, x). Так как функция f0 не сохраняет нуль, ?0 (0) = f (0, 0, …, 0) = 1. Воз-
можны два случая: либо ? 0 (x ) = x , либо ?0 (x) ? 1. Рассмотрим функцию
f1 (x1, …, xn) ? T1 и аналогичным образом введём функцию ?1 (x) = f1 (x, x, …, x). Так
как функция f1 не сохраняет единицу, ?1 (1) = f (1, 1, …, 1) = 0. Возможны также два
случая: либо ?1 (x ) = x , либо ?1 (x) ? 0. Если хотя бы в одном случае получилось ис-
комое отрицание, пункт завершён. Если же в обоих случаях получились константы,
то согласно лемме о немонотонной функции, подставляя в функцию fM ? M вместо
всех переменных константы и тождественные функции, можно получить отрицание.
Отрицание получено.
b) Получение констант 0 и 1. Имеем fS ? S. Согласно лемме о несамодвойственной
функции, подставляя вместо всех переменных функции fS отрицание (которое полу-
чено в пункте a) и тождественную функцию, можно получить константы:
[fS, x ] ? [0, 1]. Константы получены.
c) Получение конъюнкции x · y. Имеем функцию fL ? L. Согласно лемме о нелинейной
функции, подставляя в функцию fL вместо всех переменных константы и отрицания
(которые были получены на предыдущих шагах доказательства), можно получить
либо конъюнкцию, либо отрицание конъюнкции. Однако на первом этапе отрицание
уже получено, следовательно, всегда можно получить конъюнкцию:
[fL, 0, 1, x ] ? [xy, xy ]. Конъюнкция получена.
В результате получено, что [ f 0 , f1 , f M , f L , f S ] ? [x , xy ] = P2 . Последнее равенство следует
из пункта 2 теоремы 4. В силу леммы 2 достаточность доказана.

§12. Теорема о максимальном числе функций в базисе алгебры логики.

Определение. Система функций алгебры логики A ? P2 называется базисом (в P2), если
1) [A] = P2;
2) ?f ? A ([A \ {f}] ? P2).
Теорема 13. Максимальное число функций в базисе алгебры логики равно 4.
Доказательство. 1) Докажем, что из любой полной системы можно выделить полную
подсистему, содержащую не более четырёх функций. Действительно, если A — полная сис-
тема ([A] = P2), то согласно теореме Поста в ней существуют пять функций f0 ? T0, f1 ? T1,
fS ? S, fM ? M, fL ? L. По теореме Поста система функций {f0, f1, fS, fM, fL} полна. Рассмотрим
функцию f0 (x1, …, xn) ? T0 (f0 (0, 0, …, 0) = 1). Возможны два случая:
a) f0 (1, 1, …, 1) = 1 ? f0 ? S ? [f0, f1, fL, fM] = P2 и система {f0, f1, fL, fM} полна.
b) f0 (1, 1, …, 1) = 0 ? f0 ? M, T1 ? [f0, fL, fS] = P2 и система {f0, fL, fS} полна.




12
2) Покажем, что существует базис алгебры логики из четырёх функций. Действительно,
рассмотрим систему функций {0, 1, x · y, x ? y ? z}. Эта система функций полная, так как
0 ? T1, S, 1 ? T0, x · y ? L, x ? y ? z ? M (0 ? 0 ? 1 = 1, 0 ? 1 ? 1 = 0). Однако, любая её под-
система не полна:
{0, 1, x · y} ? M
{0, 1, x ? y ? z} ? L
{0, xy, x ? y ? z} ? T0
{1, xy, x ? y ? z} ? T1.
Теорема доказана.

§13. Теорема о предполных классах.
1 . Предполные классы.
Определение. Пусть A ? P2. A называется предполным классом, если
1) [A] ? P2;
2) ?f?P2 ( f?A ? [A?{f}] = P2).
Теорема 14. В P2 предполными являются лишь следующие 5 классов: T0, T1, S, L, M.
Доказательство. 1) Покажем сначала, что ни один из этих пяти классов не содержится в
другом. Для этого достаточно для каждого из пяти вышеперечисленных классов указать че-
тыре функции, принадлежащие данному классу, но не принадлежащие остальным четырем:
?
T0 T1 L M S
?
x?y
T0 0 xy 0
x?y?1
T1 1 xy 1
x?y
L10 0
M10 xy 0
S x x xy ? yz ? zx x
2) Докажем, что все классы — T0, T1, S, L, M являются предполными. Действительно,
пусть N ? {T0 , T1 , L, M , S} и f ? N. Тогда система N ? {f} не содержится ни в одном из пяти
классов Поста (так как N не содержится в четырёх из них, а f не содержится в N). Следова-
тельно, система N ? {f} — полная и N — предполный класс.
3) Пусть A — предполный класс. Тогда [A] ? P2 ? ? N?{T0, T1, L, M, S}: A ? N. Если
A ? N, то ? f (f ? N, f ? A): A ? {f} ? N ? [A ? {f}] ? P2. Полученное противоречие заверша-
ет доказательство.
2 . Результаты Поста.
1) В P2 существует ровно счётное число замкнутых классов.
2) В любом замкнутом классе существует конечный базис.

§14. k-значные функции. Теорема о существовании конечной полной системы
в множестве k-значных функций.
1°. k-значные функции. Будем рассматривать конечный алфавит Ek = {0, 1, 2, …, k – 1}.
Функцией k-значной логики назовём отображение вида f (x1, x2, …, xn): Ekn > Ek .
Некоторые функции k-значной логики.
1) Константы 0, 1, 2, …, k – 1 (всего — k);
2) Тождественная функция f (x) = x;
3) Отрицания: f (x) = x = x + 1 (mod k) — отрицание Поста,
f (x) = ˜ x = (k – 1) – x — отрицание Лукасевича;
4) Сложение по модулю k: f (x, y) = x + y (mod k);
5) Умножение по модулю k: f (x, y) = xy (mod k);


13
6) Максимум: max (x, y);
7) Минимум: min (x, y);
?k ? 1, x = ?
8) J ? (x ) = ? .
0, x ? ?
?
Теорема 15. Система {0, 1, …, k – 1, max (x, y), min (x, y), J0 (x), J1 (x), …, Jk – 1 (x)} полна в Pk.
Доказательство. Утверждается, что для любой функции f (x1, …, xn) ? Pk справедливо
представление
{min(J (x ),", J (x ), f (? ,? )}
f (x1 ,!, xn ) = , !, ? n ) .
max ?1 ?n
1 1 2
n
(?1 ,!,? n )?Ekn

Действительно, для любого набора ? = (?1 ,? 2 ,!,? n ) ? Ekn рассмотрим значение правой час-
˜
ти: если существует такое i , что ?i ? ?i, то J? i (? i ) = 0 и весь минимум станет равным нулю.
Таким образом, правая часть станет равна
{ ( ) }
max 0,0,!,0, min J ?1 (?1 ), J? 2 (? 2 ),!, J ? n (? n ), f (?1 , ? 2 ,!, ? n ) ,0,!,0 ,
а учитывая то, что в Pk
Ja (a) = k – 1,
получим, что правая часть равна просто f (?1 ,? 2 ,!,? n ) . Теорема доказана.
Замечание. min (x1, x2, x3) = min (x1, min (x2, x3)); min (x1, x2, …, xn) = min (x1, min (x2, … ,xn)).
Аналогично определяется функция максимума от n переменных.
2°. Особенности k-значной логики.
1) В Pk существует континуум замкнутых классов (при k ? 3).
2) В Pk существуют замкнутые классы с бесконечным базисом (при k ? 3).
3) В Pk существуют замкнутые классы, не имеющие базиса (при k ? 3).




14
Глава II. Основы теории графов.
§15. Основные понятия теории графов. Изоморфизм графов. Связность.
Определение 1. Графом называется произвольное множество элементов V и произволь-
ное семейство E пар из V. Обозначение: G = (V, E).
В дальнейшем будем рассматривать конечные графы, то есть графы с конечным множе-
ством элементов и конечным семейством пар.
Определение 2. Если элементы из E рассматривать как неупорядоченные пары, то граф
называется неориентированным, а пары называются рёбрами. Если же элементы из E рас-
сматривать как упорядоченные, то граф ориентированный, а пары — дуги.
Определение 3. Пара вида (a, a) называется петлёй, если пара (a, b) встречается в се-
мействе E несколько раз, то она называется кратным ребром (кратной дугой).
Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть не-
ориентированным графом (или просто графом), граф без петель — мультиграфом, а муль-
тиграф, в котором разрешены петли — псевдографом.
Определение 5. Две вершины графа называются смежными, если они соединены ребром.
Определение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.
Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентных
данной вершине. Для псевдографа полагают учитывать петлю дважды.

2 5


.8
1

7



4 3 6


Утверждение 1. В любом графе (псевдографе) справедливо следующее соотноше-
p
ние: ? deg vi = 2q , где p — число вершин, а q — число рёбер.
i =1
Доказательство. Когда мы считаем степень одной вершины, мы считаем все рёбра, вы-
ходящие из неё. Вычисляя сумму всех степеней, мы получаем, что каждое ребро считается
дважды, так как оно инцидентно двум вершинам (петли по определению степени также по-
считаются дважды). Поэтому общая сумма будет равна удвоенному числу рёбер. Утвержде-
ние доказано.
Определение 8. Пусть множество вершин графа V = {v1, v2, …, vp}. Тогда матрицей
смежности этого графа назовём матрицу A = ||aij||, где aij = 1, если вершины vi и vj смежны
(2, 3, … для мультиграфа или псевдографа) и 0 в противном случае, aii при этом равно числу
петель в вершине vi.
Определение 9. Два графа (или псевдографа) G1 = (V1 , E1 ) и G2 = (V2 , E2 ) называют-
ся изоморфными, если существуют два взаимно однозначных отображения ?1 : V1 > V2 и
?2: E1 > E2 такие, что для любых двух вершин u и v графа G1 справедливо ?2 (u, v) =
= (?1 (u), ?1 (v)).
Определение 10 (изоморфизм графов без петель и кратных рёбер). Два графа G1 =
= (V1, E1) и G2 = (V2, E2) называются изоморфными, если существует взаимно однозначное
отображение ?1: V1 > V2 такое, что (u, v) ? E1 ? (? (u), ? (v)) ? E2.
Определение 11. Граф G1 = (V1 , E1 ) называется подграфом графа G = (V, E), если
V1 ? V, E1 ? E.


15
Определение 12. Путём в графе G = (V, E) называется любая последовательность вида
v0, (v0, v1), v1, (v1, v2), …, vn – 1, (vn – 1, vn), vn.
Число n в данных обозначениях называется длиной пути.
Определение 13. Цепью называется путь, в котором нет повторяющихся рёбер.
Определение 14. Простой цепью называется путь без повторения вершин.
Утверждение 2. Пусть в G = (V, E) v1 ? v2 и пусть P — путь из v1 в v2. Тогда в P можно
выделить подпуть из v1 в v2, являющийся простой цепью.
Доказательство. Пусть данный путь — не простая цепь. Тогда в нём повторяется неко-
торая вершина v, то есть он имеет вид: P1 = v0C1vC2vC3v2. Тогда он содержит подпуть P2 =
= v0C1vC3v2. Если в P2 повторяется некоторая вершина, то аналогично удалим ещё кусок и
так далее. Процесс должен закончиться, так как P1 — конечный путь. Утверждение доказано.
Определение 15. Путь называется замкнутым, если v0 = vn.
Определение 16. Путь называется циклом, если он замкнут, и рёбра в нём не
повторяются.
Определение 17. Путь называется простым циклом, если v0 = vn и вершины не повторяются.
Определение 18. Граф G = (V, E) называется связным, если для любых вершин vi, vj ? V
(vi ? vj) существует путь из vi в vj.
Рассмотрим отношение vi > vj существования пути из vi в vj. Оно
1) симметрично, так как (vi > vj) ? (vj > vi),
2) транзитивно, так как (vi > vj) & (vj > vk) ? (vi > vk),
3) рефлексивно, так как ?i (vi > vi).
Таким образом, получено, что vi > vj — отношение эквивалентности и множество вершин
разбивается на конечное число классов эквивалентности: V > V1 ? V2 ? … ? Vk, Vi ? Vj = ? ?
? i ? j. При этом граф G разбивается на связные подграфы, которые называются компонентами
связности.
V1 V2 Vk







Связные компоненты графа G


§16. Деревья. Свойства деревьев.
Определение 1. Деревом называется связный граф без циклов.
Определение 2. Подграф G1 = (V1, E1) графа G = (V, E), называется остовным деревом в
графе G = (V, E), если G1 = (V1, E1) — дерево и V1 = V.
Лемма 1. Если граф G = (V, E) связный и ребро (a, b) содержится в некотором цикле в
графе G, то при выбрасывании из графа G ребра (a, b) снова получится связный граф.
Доказательство. Это утверждение следует из того, что при выбрасывании из графа G
ребра (a, b) вершины a и b всё равно остаются в одной связной компоненте, поскольку из a в
b можно пройти по оставшейся части цикла. Лемма доказана.
Теорема 1. Любой связный граф содержит хотя бы одно остовное дерево.
Доказательство. Если в G нет циклов, то G является искомым остовным деревом. Ес-
ли в G есть циклы, то удалим из G какое-нибудь ребро, входящее в цикл. Получится неко-
торый подграф G1. По лемме 1 G1 — связный граф. Если в G1 нет циклов, то G1 и есть ис-
комое остовное дерево, иначе продолжим этот процесс. Процесс должен завершиться, так
как E — конечное множество. Теорема доказана.

16
Лемма 2. Если к связному графу добавить новое ребро на тех же вершинах, то появится цикл.
Доказательство. Рассмотрим произвольный связный граф G = (V, E). Пусть u ? V,
v ? V, (u, v) ? E. Так как G — связный граф, то в нём есть путь из v в u. Тогда в G есть и про-
стая цепь C из v в u. Поэтому в полученном графе есть цикл C, (u, v), v. Лемма доказана.
Лемма 3. Пусть в графе G = (V, E) p вершин и q рёбер. Тогда в G не менее p – q связных
компонент. Если при этом в G нет циклов, то G состоит ровно из p – q связных компонент.
Доказательство. Пусть к некоторому графу H, содержащему вершины u и v, добавляет-
ся ребро (u, v). Тогда если u и v лежат в разных связных компонентах графа H, то число связ-
ных компонент уменьшится на 1. Если u, v лежат в одной связной компоненте графа H, то
число связных компонент не изменится. В любом случае, число связных компонент умень-
шается не более чем на 1. Значит, при добавлении q рёбер число связных компонент умень-
шается не более чем на q. Так как граф G получается из графа G1 = (V, ?) добавлением q рё-
бер, то в G не менее p – q связных компонент. Пусть теперь в G нет циклов, и пусть в про-
цессе получения G из G1 добавляется ребро (u, v). Если бы u, v лежали уже в одной связной
компоненте, то в G, согласно лемме 2, возникал бы цикл. Следовательно, u, v лежат в разных
связных компонентах и при добавлении ребра (u, v) число связных компонент уменьшается
ровно на 1. Тогда G состоит ровно из p – q связных компонент. Лемма доказана.
Теорема 2 (о различных определениях дерева). Следующие пять определений эквива-
лентны (p — число вершин, q — число рёбер):
1) G — дерево;
2) G — без циклов и q = p – 1;
3) G — связный граф и q = p – 1;
4) G — связный граф, но при удалении любого ребра становится несвязным;
5) G — без циклов, но при добавлении любого ребра на тех же вершинах появляется цикл.
Доказательство. Докажем следующие переходы: 1) ? 2) ? 3) ? 4) ? 5) ? 1), откуда
будет следовать, что из любого условия вытекает любое другое.
1) ? 2): так как G — связный граф и G не содержит циклов, то p – q = 1 по лемме 3. От-
сюда q = p – 1.
2) ? 3): по лемме 3 в G число связных компонент равно p – q = 1, то есть G — связный граф.
3) ? 4): при удалении одного ребра p – q = 2. Тогда по лемме 3 число связных компо-
нент не менее чем p – q = 2.
4) ? 5): если G имеет цикл, то согласно лемме 1 можно выбросить одно ребро так, что
граф останется связным. Согласно лемме 2, если добавить любое новое ребро к связному
графу G на тех же вершинах, то появится цикл.
5) ? 1): если G не связный граф и вершины u, v лежат в разных связных компонентах
графа G, то добавление к G ребра (u, v), очевидно, не порождает циклов, что противоречит
5). Отсюда следует, что G — связный граф. Теорема доказана.

§17. Корневые деревья. Верхняя оценка их числа.
Определение 1. Любое дерево, в котором выделена одна вершина, называемая корнем,
называется корневым деревом.
Определение 2. 1) Граф, состоящий из одной вершины, которая выделена, называется
корневым деревом.
2) Пусть имеются корневые деревья D1, D2, …, Dm с корнями v1, v2, …, vm, Di = (Vi, Ei),
Vi ? Vj = ? (i ? j). Тогда граф D = (V, E), полученный следующим образом:
V = V1 ? V2 ? … ? Vm ? {v} (v ? Vi, ?i ), E = E1 ? E2 ? … ? Em ? {(v, v1), (v, v2), …,(v, vm)}
и в котором выделена вершина v, называется корневым деревом.
3) Только те объекты являются корневыми деревьями, которые можно построить со-
гласно пунктам 1) и 2).



17
При таком определении D1,D2,…,Dm называются поддеревьями дерева D.


v1 v2 vm

D1 D2 Dm





v
Утверждение. Определения 1 и 2 эквивалентны.
Определение 3. Упорядоченным корневым деревом называется корневое дерево, в
котором
1) задан порядок поддеревьев и
2) каждое поддерево Di является упорядоченным поддеревом.
Дерево с одной вершиной также является упорядоченным поддеревом.
Теорема 3. Число упорядоченных корневых деревьев с q рёбрами не превосходит 4q.
Доказательство. Рассмотрим алгоритм обхода упорядоченного дерева, называемого
«поиском в глубину». Этот обход описывается рекурсивно следующим образом:
1) Начать с корня. Пока есть поддеревья выполнять:
2) перейти в корень очередного поддерева, обойти это поддерево «в глубину».
3) Вернуться в корень исходного поддерева.
В результате обход «в глубину» проходит по каждому ребру дерева ровно 2 раза: один
раз при переходе в очередное поддерево, второй раз при возвращении из этого поддерева. В
соответствии с обходом «в глубину» будем строить последовательность из нулей и единиц,
записывая на каждом шаге нуль или единицу, причём нуль будем записывать, если происхо-
дит переход в очередное поддерево, а единицу, если мы возвращаемся из поддерева. Полу-
чим последовательность из 0 и 1 длины 2q, которую назовём кодом дерева. По этому коду
однозначно восстанавливается дерево, поскольку каждый очередной разряд однозначно ука-
зывает, начинать ли строить новое очередное поддерево или возвращаться на ярус ближе к
корню. Таким образом, упорядоченных корневых деревьев с q рёбрами не больше, чем по-
следовательностей из 0 и 1 длины 2q, а их число равно 22q = 4q. Теорема доказана.
Изоморфизм корневых деревьев определяется так же, как и изоморфизм графов, но с
дополнительным требованием: корень должен отображаться в корень. Для упорядоченных
корневых деревьев также требуется сохранение порядка поддеревьев.
Следствие. Число неизоморфных корневых деревьев с q рёбрами и число неизоморф-
ных деревьев с q рёбрами не превосходит 4q.
Доказательство. Выделяя в неизоморфных деревьях по одной вершине, мы получим
неизоморфные корневые деревья. Упорядочивая поддеревья в неизоморфных корневых де-
ревьях, мы получим различные упорядоченные корневые деревья. Поэтому число неизо-
морфных деревьев с q рёбрами не превосходит числа неизоморфных корневых деревьев с q
рёбрами, которое, в свою очередь, не превосходит числа различных упорядоченных корне-
вых деревьев с q рёбрами. Отсюда и из теоремы следует утверждение следствия. Следствие
доказано.

§18. Геометрическая реализация графов.
Теорема о реализации графов в трёхмерном пространстве.
Определение. Пусть задан некоторый неориентированный граф G = (V, E). Пусть лю-
бой вершине vi графа G сопоставлена некоторая точка ai: vi > ai, ai ? aj (i ? j), а любому ребру
e = (a, b) сопоставлена некоторая непрерывная кривая L, соединяющая точки ai и aj и не про-
ходящая через другие точки ak (k ? i, j). Тогда если все кривые, сопоставленные рёбрам, не


18
имеют общих точек, кроме концевых, то говорят, что задана геометрическая реализация
графа G.
геометрическая реализация графа K 4




не является геометрической реализацией графа K 4

Теорема 4. Для любого графа существует его реализация в трёхмерном пространстве.
Доказательство. Возьмём в пространстве любую прямую l и разместим на ней все вер-
шины графа G. Пусть в G имеется q рёбер. Проведём связку из q различных полуплоскостей
через l. После этого каждое ребро графа G можно изобразить линией в своей полуплоскости
и они, очевидно, не будут пересекаться. Теорема доказана.

§19. Планарные (плоские) графы. Формула Эйлера.
Определение 1. Граф называется планарным, если существует его геометрическая реа-
лизация на плоскости.
Определение 2. Если имеется планарная реализация графа и мы «разрежем» плоскость
по всем линиям этой планарной реализации, то плоскость распадётся на части, которые на-
зываются гранями этой планарной реализации (одна из граней бесконечна, она называется
внешней гранью).
Теорема 5 (формула Эйлера). Для любой планарной реализации связного планарного
графа G = (V, E) с p вершинами, q рёбрами и r гранями выполняется равенство: p – q + r = 2.
Доказательство. Докажем теорему при фиксированном p индукцией по q. Так как G —
связный граф, то q ? p – 1.
a) Базис индукции: q = p – 1. Так как G — связный и q = p – 1, то согласно пункту 3
теоремы 2 G — дерево, то есть, в G нет циклов. Тогда r = 1. Отсюда p – q + r =
= p – (p – 1) + 1 = 2.
b) Пусть для q: p – 1 ? q < q0 теорема справедлива. Докажем, что для q = q0 она также
справедлива. Пусть G — связный граф с p вершинами и q0 рёбрами и пусть в его
планарной реализации r граней. Так как q0 > p – 1, то G — не дерево. Следовательно,
в G есть цикл. Пусть ребро e входит в цикл. Тогда к нему с двух сторон примыкают
разные грани. Удалим ребро e из G. Тогда две грани сольются в одну, а полученный
граф G1 останется связным. При этом получится планарная реализация графа G1 с p
вершинами и q0 – 1 рёбрами и r – 1 гранями. Так как q0 – 1 < q0, то, по предположе-
нию индукции, для G1 справедлива формула Эйлера, то есть p – (q0 – 1) + (r – 1) = 2,
откуда p – q0 + r = 2. Что и требовалось доказать.
Следствие 1. Формула Эйлера справедлива и для геометрической реализации связных
графов на сфере.
Доказательство. Пусть связный граф G с p вершинами и q рёбрами реализован на сфе-
ре S так, что число граней равно r. Пусть точка A на сфере не лежит на линиях этой геомет-
рической реализации. Пусть P — некоторая плоскость. Поставим сферу S на плоскость P так,
чтобы точка A была самой удалённой от плоскости. Спроектируем S на P центральным про-
ектированием с центром в точке A. Тогда на плоскости P мы получим геометрическую реа-
лизацию связного графа с p вершинами и q рёбрами, причём число граней будет равно r
(грань на сфере, содержащая A, отображается на внешнюю грань на плоскости). По теореме
получаем p – q + r = 2. Следствие доказано.


19
Следствие 2. Для любого выпуклого многогранника справедливо равенство p – q + r = 2,
где p — число вершин, q — число рёбер, r — число граней.
Доказательство. Пусть выпуклый многогранник M имеет p вершин, q рёбер и r граней.
Пусть O — внутренняя точка многогранника. Разместим сферу S с центром в точке O на-
столько большого радиуса, чтобы M целиком содержался в S. Рассмотрим центральное про-
ектирование с центром в точке O, и спроектируем вершины и рёбра M на S. Тогда на S мы
получим геометрическую реализацию некоторого связного графа с p вершинами, q рёбрами
и r гранями. Отсюда согласно следствию 1 p – q + r = 2. Следствие 2 доказано.

§20. Доказательство непланарности графов K5 и K3,3.
Теорема Понтрягина-Куратовского (доказательство в одну сторону).
Определение 1. Графом K5 называется граф с пятью вершинами, в котором каждая пара
вершин соединена ребром.




K5

Теорема 6. Граф K5 не планарен.
Доказательство. Допустим, что для графа K5 существует планарная реализация. Так как
граф K5 связен, то для этой планарной реализации справедлива формула Эйлера p – q + r = 2.
Поскольку в графе K5 имеем p = 5 и q = 10, то число всех граней должно равняться r = 2 – p +
+ q = 7. Пусть грани занумерованы 1, 2, …, r и пусть при обходе i-ой грани по периметру (по
её краю) проходится qi рёбер. Так как при этом каждое ребро обходится дважды (оно являет-
ся стороной для двух граней), то ?i =1 qi = 2q = 20 . Но в каждой грани не менее трёх сторон.
r



?
r
Поэтому qi ? 3 для всех i. Отсюда qi ? 3r = 21 . Получаем 20 ? 21 — противоречие. Зна-
i =1
чит, для графа K5 не существует планарной реализации.
Определение 2. Графом K3,3 называется граф с шестью вершинами a1, a2, a3, b1, b2, b3, в
котором каждая вершина ai соединена ребром с каждой вершиной bj и других рёбер нет.
a1 a2 a3




b1 b2 b3

K3,3

Теорема 7. Граф K3,3 не планарен.
Доказательство. Допустим, что для графа K3,3 существует планарная реализация. Так
как граф K3,3 связен, то для этой планарной реализации справедлива формула Эйлера p – q +
+ r = 2. Поскольку в графе K3,3 имеем p = 6 и q = 9, то число всех граней должно равняться
r = 2 – p + q = 5. Так же, как в доказательстве предыдущей теоремы, получаем, что
?i =1 qi = 2q = 18 , где qi — число сторон в i-ой грани. Но в графе K3,3 нет циклов длины 3. По-
r




20
этому в каждой грани не менее 4 сторон. Следовательно, qi ? 4 для всех i. Отсюда
?i=1 qi ? 4r = 20 . Получаем 18 ? 20 — противоречие. Значит, для графа K3,3 не существует
r


планарной реализации.
Определение 3. Подразделением ребра (a, b) называется операция, состоящая в сле-
дующих действиях:
1) удаление (a, b),
2) добавление новой вершины c,
3) добавление рёбер (a, c) и (c, b).
Определение 4. Граф H называется подразделением графа G, если H можно получить из
G путём конечного числа подразделений своих рёбер.
Определение 5. Два графа называются гомеоморфными, если существуют их подразде-
ления, которые изоморфны.
Теорема 8 (Понтрягина-Куратовского). Граф является планарным тогда и только то-
гда, когда он не содержит ни одного подграфа, гомеоморфного графам K5 или K3,3.
Доказательство. Необходимость. Пусть G — планарный. Допустим, что он содержит
подграф G1, гомеоморфный графу K5 или K3,3. Рассмотрим планарную реализацию графа G.
Удалив лишние вершины и рёбра, мы получим планарную реализацию подграфа G1. Но G1
геометрически — это граф K5 или K3,3 с точками на рёбрах. Если проигнорировать эти точки,
то мы получим планарную реализацию графа K5 или K3,3. Но это невозможно в силу теорем 1
и 2. Необходимость доказана.
Достаточность без доказательства.

§21. Теорема о раскраске планарных графов в пять цветов.
Лемма 1. Для любой геометрической реализации на плоскости связного планарного гра-
фа с q рёбрами выполняется равенство:
r

?q = 2q ,
i
i =1

где суммирование ведётся по всем граням (включая внешнюю).
Доказательство. Равенство следует из того, что у каждого ребра две стороны и при
суммировании qi каждое ребро учитывается дважды: либо оно входит в границы двух сосед-
них граней, либо оно дважды учитывается в одной грани. Лемма доказана.
Теорема 9. Если в связном планарном графе G = (V, E) с p вершинами и q рёбрами, от-
личном от дерева, нет циклов длины меньше k (k ? 3), то q ? k ?2 ( p ? 2) .
k


Доказательство. Так как по условию qi ? k, то из леммы получаем 2q ? kr и r ? 2q
. Из
k

формулы Эйлера r = 2 – p + q. Отсюда 2 ? p + q ? 2kq . Далее (k – 2)q ? k(p – 2) и q ? k ?2 ( p ? 2) .
k


Теорема доказана.
Следствие. В любом связном планарном графе G = (V, E) без петель и кратных рёбер с
p ? 3 вершинами и q рёбрами справедливо неравенство: q ? 3( p – 2).
Определение 1. Подмножество V1 ? V вершин графа G = (V, E) называется независи-
мым, если никакие две вершины из V1 не соединяются ребром.
Определение 2. Пусть есть некоторое множество C = {C1, C2, …, Cm} — множество
цветов. Тогда раскраской графа G = (V, E) (вершинной) называется любое отображение
?: V > C. Раскраска называется правильной, если для любого цвета вершины этого цвета об-
разуют независимое множество.
Лемма 2. В планарном графе без петель и кратных рёбер существует вершина v:
deg v ? 5.



21
Доказательство. Пусть G — планарный граф с p вершинами и q рёбрами. Пусть в G нет
вершин степени 0 и 1. Тогда q ? 3(p – 2) < 3p. Пусть dmin — минимальная степень вершин в
G. Тогда получаем
p
6 p > 2q = ? deg vi ? pd min .
i =1

Отсюда dmin < 6, то есть dmin ? 5. Лемма доказана.
Теорема 10. Вершины любого планарного графа можно правильно раскрасить в не бо-
лее чем 5 цветов.
Доказательство. Проведём индукцию по числу вершин p.
1) Базис индукции: p = 1 — очевидно.
2) Пусть для p < p0 утверждение справедливо и пусть G = (V, E) — планарный граф с
|V| = p0. Согласно лемме 2 в G есть вершина v степени не более 5. Рассмотрим укладку на
плоскости графа G без пересечения рёбер. Удалим из G вершину v и все инцидентные ей
рёбра. Получим планарный граф G1 с числом вершин p0 – 1. По предположению индукции
его вершины можно правильно раскрасить в 5 цветов C1, C2, C3, C4, C5. Пусть в G вершина v
смежна с v1, v2, …, vk, где k ? 5. Возможны два случая:
a) Среди цветов вершин v1, v2, …, vk в G нет цвета Ci (1 ? i ? 5). Тогда вершине v
припишем цвет Ci и получим правильную раскраску графа G в 5 цветов.
b) Степень вершины v равна 5 и среди вершин v1, v2, …, v5 в G1 есть все 5 цветов.
Без ограничения общности будем считать, что в укладке графа G рёбра (v, v1),
(v, v2), (v, v3), (v, v4), (v, v5) выходят из v в порядке по часовой стрелке и что
C (vi) = Ci, i = 1, …, 5. Пусть A — множество всех вершин в G1, до которых можно
дойти из v1 по рёбрам графа G1, используя только вершины цветов C1 и C3. Воз-
можны два варианта:
i) v3?A. Тогда в A поменяем цвета C1 > C3, C3 > C1. Так как вершины из A не
смежны с другими вершинами цветов C1 и C3, то останется правильная рас-
краска и среди v1, v2, v3, v4, v5 не будет цвета C1. Тогда вершине v припишем
цвет C1.
ii) v3?A. Это значит, что в A есть цепь из v1 в v3, все вершины которой имеют
цвета C1 и C3. Эта цепь вместе с рёбрами (v3, v) и (v, v1) образует цикл в G,
причём вершины v2 и v4 лежат по разные стороны от этого цикла. Это значит,
что из v2 нельзя пройти в v4 в графе A только по вершинам цветов C2 и C4.
Пусть B — множество всех вершин в G, до которых можно дойти из v2 по
рёбрам графа G, используя только вершины цветов C2 и C4. Тогда v4?B и да-
лее поступаем как в i).
В любом случае вершины графа G можно правильно раскрасить в не более чем 5 цветов,
и теорема доказана.




22
Глава III. Основы теории управляющих систем.
§22. Схемы из функциональных элементов.
Реализация функций алгебры логики схемами.
Определение 1. Вершины орграфа, в которые не входит ни одной дуги, называются
истоками.
Определение 2. Орграф называется ациклическим, если в нем нет ориентированных
циклов.
Определение 3. В ациклическом орграфе глубиной вершины v называется максимальное
число дуг в ориентированном пути из какого-нибудь истока в вершину v.
Если в ациклическом орграфе есть дуга (v1, v2), то глубина v2 больше глубины v1.
Определение 4. Орграф называется упорядоченным, если для каждой вершины vi, в ко-
торую входит ki дуг, задан порядок e1 , e2 ,!, eki этих дуг.
Определение 5. Систему Б = {g1, g2, …, gm}, где все gi — функции алгебры логики, бу-
дем называть базисом функциональных элементов.
Определение 6. Схемой из функциональных элементов в базисе Б называется ацикличе-
ский упорядоченный орграф, в котором:
1) каждому истоку приписана некоторая переменная, причем разным истокам приписа-
ны разные переменные (истоки при этом называются входами схемы, а приписанные им пе-
ременные — входными переменными);
2) каждой вершине, в которую входят k ? 1 дуг, приписана функция из базиса Б, зави-
сящая от k переменных (вершина с приписанной функцией при этом называется функцио-
нальным элементом);
3) некоторые вершины выделены как выходы (истоки одновременно могут являться
выходами).
Индукцией по глубине q вершины v определяется функция fv, реализуемая в данной
вершине. Если q = 0, то есть v — исток, и v приписана переменная xi, то fv ? xi. Пусть реали-
зуемые функции уже определены для всех вершин глубины меньшей, чем q0, и глубина v
равна q0. Пусть в v входят дуги e1, e2, …, ek из вершин v1, v2, …, vk и в них реализуются функ-
ции f1, f2, …, fk. Пусть вершине v приписана функция g (x1, …, xk). Тогда в v реализуется
функция fv = g (f1, f2, …, fk).
Определение 7. Будем говорить, что схема реализует систему функций, реализуемых в
ее выходах.
Определение 8. Сложностью схемы из функциональных элементов называется число
функциональных элементов в схеме.
В дальнейшем по умолчанию будем подразумевать под базисом функциональных эле-
{ }
ментов систему Б 0 = ?,&, . Так как все эти функции симметричны относительно своих пе-
ременных, то дуги, входящие в каждую вершину, можно не упорядочивать.
Пример. Полусумматор. Пусть v и v1 — выходы на рисунке, f v = xy & (x ? y ) = x ? y ;
f v1 = xy . Сложность (число элементов) полусумматора равна 4.
x y



?
xy & v1 v2 x?y
_
xy
v&
Полусумматор ??



23
В дальнейшем при построении схем ячейку полусумматора будем обозначать просто
x y

??


?
&
Ячейка полусумматора ??

Пусть есть 2 n-разрядных числа, и требуется найти их сумму (в дальнейших обозначе-
ниях xi, yi — разряды чисел, а qi — единицы переноса).
q0 q1 q2 qn?1
!
x1 x2 xn?1 xn
!
+ y1 y2 yn?1 yn
!
z0 z1 z2 z n?1 zn
!
При i = 1, 2, …, n – 1 задача решается системой функций
zi = xi ? yi ? qi ,
?
?
?qi?1 = m(xi , yi , qi ) = xi yi ? yi qi ? qi xi .
Таким образом, ячейку сумматора можно построить следующим образом:
x y q

?? ??

? ?
· ·
v??

?

v?
Ячейка сумматора ?1

где fv?? = (x ? y) ? q, fv? = xy ? (x ? y) · q = xy ? (x ? y) · q = m (x, y, q). Ячейку сумматора будем
обозначать ?1 и в дальнейшем в схемах подставлять вместо ячейки сумматора символ ?1 с
тремя входами (x, y, z) и двумя выходами (z, q?).
x y q

?1

z q?
Ячейка сумматора ?1

Заметим, что сложность схемы, реализующей ячейку сумматора равна L (?1) = 9. Очевидно,
zn = xn ? yn, qn – 1 = xnyn, z0 = q0.




24
§23. Сумматор. Верхняя оценка сложности сумматора. Вычитатель.

Для набора ? = (?1 ,? 2 ,! ,? n ) будем обозначать ? = (?1? 2 !? n )2 .
˜
˜
Определение 1. Сумматором Sn порядка n называется схема с 2n входами x1, x2, …, xn,
y1, y2, …, yn и n + 1 выходом z0, z1, z2, …, zn такая, что ˜ = S n (˜, ˜ ) = ˜ + ˜ .
z xy xy
Теорема 1. Существует схемный сумматор порядка n в базисе {?, &, } с числом эле-
ментов 9n – 5.
Доказательство. Построим искомый схемный сумматор. Для этого возьмём одну ячей-
ку полусумматора, содержащую четыре элемента и n – 1 ячейку сумматора, каждая из кото-
рых содержит девять элементов. Построим из этих частей сумматор.
xn yn xn – 1 yn – 1 xn – 2 yn – 2 x1 y1

?? ?1 ?1 ?1


zn zn – 1 zn – 2 z1 z0

Сумматор Sn


Вычислим сложность построенной схемы: L (Sn) = 9L (?1) + L (??) = 9(n – 1) + 4 = 9n – 5. Тео-
рема доказана.
Определение 2. Вычитателем Wn порядка n называется схема с 2n входами x1, x2, …, xn,
y1, y2, …, yn и n выходами z1, z2, …, zn такая, что при ˜ ? ˜
xy
˜ = W (˜, ˜ ) = ˜ ? ˜ .
z xy x y

Теорема 2. Существует схемный вычитатель порядка n в базисе {?, &, } с числом
элементов 11n – 5.
Доказательство. Заметим предварительно, что
? = (?1? 2 !? n ) = 2n ? 1 ? ? .
˜ ˜

Действительно,
(?1? 2 !? n )2
(?1? 2 !? n )2
+ .
(1 1 ! 1 )2 = 2n ? 1
Тогда вычитатель реализуется схемой
x1 … xn y1 … yn
– –

Sn

– –

z0 z1 zn
Вычитатель Wn




25
(( ) )
Wn (˜, ˜ ) = ˜ ? ˜ = 2 n ? 1 ? 2 n ? 1 ? ˜ + ˜
xy xy x y
и его можно построить, используя 2n отрицаний и 1 сумматор порядка n. При этом L (Wn) =
( )
= 2n + L (Sn) = 2n + (9n – 5) = 11n – 5. Так как ˜ ? ˜ , то 2n ? 1 ? ˜ + ˜ ? 2n ? 1 , и выход вы-
xy xy
читателя определен. Теорема доказана.

§24. Метод Карацубы построения схемы для умножения,
верхняя оценка её сложности.
Определение 1. Умножителем Mn порядка n называется схема с 2n входами x1, x2, …,
xn, y1, y2, …, yn и 2n выходами z1, …, z2n такая, что ˜ = M n (˜, ˜ ) = ˜ ? ˜ . При этом
z xy xy
˜ ? 2n ? 1 < 2 n
?0 ? x
? ˜ ? ˜ < 22 n .
xy
? ˜ ? 2n ? 1 < 2n
?0 ? y

Определение 2. Через M (n) обозначим наименьшую сложность умножителя порядка n
в базисе {?, &, }.
Утверждение. Существует схема из функциональных элементов для умножения n-
разрядного числа X на 1-разрядное число y с числом элементов n.
Доказательство. Действительно, если X = |(x1, x2, …, xn)| и Xy = Z = |(z1, z2, …, zn)|, то zi =
= xiy для всех i = 1, 2, …, n. Следовательно, для реализации такой схемы понадобится ровно n
элементов, реализующих конъюнкцию. Утверждение доказано.
При умножении двух n-разрядных чисел X и Y «в столбик» можно n раз умножить X на
1-разрядное число (всего n2 конъюнкций) и затем n – 1 раз сложить числа длиной не более
2n. Для реализации такой схемы необходим также n – 1 сумматор порядка 2n. Согласно тео-
реме 1, сложность сумматора порядка 2n равна L (S2n) = 9 · 2n – 5 = 18n – 5, и сложность по-
добного умножителя составит n2 + (n – 1) · (18n – 5) = 19n2 – 23n + 5. Такой алгоритм (схема)
имеет сложность по порядку n2. Следующая теорема показывает, что такой алгоритм умно-
жения «в столбик» не оптимален по порядку.
Лемма 1. Существует такая константа C1 > 0, что M (n + 1) ? M (n) + C1 n для всех n.
Доказательство. Пусть требуется перемножить два (n + 1)-разрядных числа
˜ = (x x ! x ) и ˜ = ( y y ! y ) . Тогда
x y
01 01
n n


? ?? ?
˜˜ = ? x ? 2 n + x ! x ?? y ? 2 n + y ! y ? = x y ? 2 2 n + (x ? Y + y ? X )? 2 n + X ? Y .
xy
?0 &%$ ?? 0 &%$ ?
1 1 00 0 0
# #n # #n
? ?? ?
X Y

Поэтому для вычисления ˜˜ достаточно использовать умножитель Mn со сложностью M (n)
xy
для вычисления XY, 2n элементов конъюнкции для вычисления x0Y и y0X, 1 элемент конъ-
юнкции для вычисления x0y0 и 3 сумматора порядка не более 2n + 2, так как ˜˜ < 22 n + 2 . От-
xy
метим, что числа x0y0, x0Y и y0X надо подавать на сумматоры со сдвигом, одновременно пода-
вая на младшие разряды 0. При этом 0 можно предварительно получить подсхемой с 2 эле-
ментами, реализующей x0 x0 = 0 . Так как сложность каждого сумматора можно сделать не
более 9(2n + 2), а сложность Mn равна M (n), то сложность полученной схемы будет не боль-
ше, чем M (n) + C1n для некоторой константы C1. Лемма доказана.
Лемма 2 (основная) [Карацуба А. А.]. Существует константа C2 такая, что
M (2n) ? 3M (n) + C2n
для всех n.
Доказательство. Пусть нужно перемножить два 2n-разрядных числа ˜ и ˜ . Разобьём
y
x
их на части, содержащие по n разрядов:


26
? ? ? ?
˜ = ? x x !x x !x ? , ˜ = ? y y ! y y ! y ? .
x ?12 y ?12
& %#n & 1%#n ? & %#n &+1%# n ?
+ 2 2
# $ n# $ # $ n# $
? ? ? ?
X1 X2 Y1 Y2


Тогда ˜ = X1·2n + X2, ˜ = Y1·2n + Y2 и
y
x
˜˜ = X Y · 22n + (X Y + X Y ) · 2n + X Y = X Y · 22n + [(X + X )(Y + Y ) – X Y – X Y ] · 2n + X Y .
xy 11 12 21 22 11 1 2 1 2 11 22 22

Так как X1Y2 + X2Y1 ? 0, то при вычитании в квадратной скобке не возникнет отрицательных
чисел. Таким образом, схему для умножения ˜˜ можно построить, используя два умножите-
xy
ля Mn с числом элементов M (n) в каждом для вычисления X1Y1 и X2Y2, умножитель Mn+1 с
числом элементов M (n + 1) для вычисления (X1 + X2)(Y1 + Y2), 4 сумматора порядка не более
4n (так как ˜˜ < 24 n ) и два вычитателя порядка 2n + 2. В некоторых сумматорах опять на
xy
младшие разряды надо подавать 0, который реализуем подсхемой с 2 элементами: 0 = xx ,
где x — любая входная переменная. Для построения схемы M2n с учётом леммы 1 получим
для некоторых констант C и C2:
M (2n) ? 2 M (n) + M (n + 1) + Cn ? 3 M (n) + C1n + Cn = 3 M (n) + C2n.
Лемма доказана.
Лемма 3. Существует такая константа C3 > 0, что для любого натурального k верно
M (2k) ? C33k.
Доказательство. Положим f (k ) = M3(2 ) . Тогда из леммы 2 имеем

стр. 1
(всего 2)

СОДЕРЖАНИЕ

>>