Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике

УДК 519.95 (075.8) ББК 518 Г12 Гаврилов Г. П., Сап оженко А. А. Задачи и упражнения по дискретной математике: Учеб. пособие. — 3-е изд., перераб. — Мл ФИЗМАТЛИТ, 2005. — 416 с. — 18В!Ч 5-9221-0477-2. В пособие включены задачи и упражнения по конечнозначным логикам (в том числе по алгебре логики), по теории автоматов, теории алгоритмов, теории графов и сетей, теории кодирования, комбинаторике, минимизации булевых функций и синтезу схем и формул, реализующих булевы функции. Имеются задачи, предназначонные для первоначальной проработки и освоения методов дискретной математики, а также задачи для углубленного изучения предмета. Второе издание — 1992 г. Для студентов и преподанателей университетов и технических вузов, в которых изучается дискретная математика.

Табл. 41. Ил. 129. Библиогр. 37 назв. Учебное издание ГАВРИЛОВ Гарий Петрович СА ПОЖЕНКО Александр Антонович ЗАДА»4И И УПРАЖНЕНИЯ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Редактор Е.Ю. Хода н Корректор 7'.Ю. Вайсберг Орип«нал-макет Е.А. Королевой Оформление переплета А.Ю. Алехиной ЛР №071930 от 06.07.99. Подписано в печать 15,П.04. Формат 60х90/16.

Бумага офсетная. Печать офсетная. Угл. печ. л. 26. У «.-нзл. к. 28,6. Заказ № 13ВН 5-9221-04 Издательская фирма «Физико-математнческая литература» МАЯК Наука/Интерперноднка» 117997, Москва, ул. Профсоюзная, 90 Е-та!1: бзп«а!мп«а1к.ги бсср:0ккгл!т1.»о Отпечатано с диапозитивов в ОАО «Чебоксарская типография № 1» 428019, г. Чебоксары, пр. И. Яковлева, 15 9 765922 104777 © ФИЗМАТЛИТ, 2004, 2005 ® Г. Н.

Гаврилов, А. А. Сапоженко, 2004, 2005 18В5! 5-9221-0477-2 ОГЛАВЛЕНИЕ Предисловие к третьему изданию Предисловие ко второму изданию Глава 1 Способы задания и простейшие свойства функций алгебры логики Глава П Замкнутые классы и полнота систем функций алгебры логики 3 1. Понятия функдиональной замкнутости и полноты 3 2.

Класс самодвойственных функций 3 3. Кто: линейных функций 3 4. Классы функций, сохраняющих константы 2 5. Класс монотонных функций 3 6. Полнота и замхнутые классы 60 64 68 72 75 81 Глава 1П й-злачные логики 3 1. Представление функций й-значных логик формулами ............. 88 1. Элементарные функции й-значных логик и соотношения между ними (88). 2. Разложение функций lс-значных логик в первую и вторую формы (91).

3 1. Функции алгебры логики и способы их задания. Операция супер- позиции . 9 1. Основные понятия и факты, связанные с булевым кубом и булевыми функциями (9). 2. Элементы булева куба. Первичные представления о булевых функциях (15). 3. Формулы. Реализация булевых функций формулами (23). 4. Двойственные функции. Принцип двойственности (31). 5. Фиктивные и существенные переменные. Отождествление переменных у булевых функций (33). гЗ 2. Специальные представления булевых фунхций ....................

39 1. Разложения булевых функций по переменным. Совершенные дизъюнктивная и конъюнктивная нормальные формы (39). 2. Дизьюнктивные и конъюнктивные нормальные формы (47). 3. Полиномы Жегалкнна (52). Оглавление 3 2. Замкнутые классы и полнота в й-значных логиках ............... 1. Некоторые замкнутые классы к-значных логик. Представление функций из Рг полиномами по модулю й (92). 2.

Исследование систем функций к-значной логики на полноту (97). 92 Глава 1Ъ' Ограниченно-детерминированные функции 9 1. Отображения последовательностей 1. Основные понятия и факты, связанные с заданием детерминированных функций (102). 2.

Типовые примеры (105). 3. Выявление свойства детерминированности функции. Эквивалентность детерминированных функций. Остаточные функции (111). 4. Выявление свойства ограниченной детерминированности функции. Порожденные и автономные функции. Строение классов эквивалентности. Мошности некоторых множеств отображений (119). '3 2. Диаграммы, таблицы, канонические уравнения, схемы ........... 1. Диаграммы Мура, канонические таблицы и канонические уравнения (126). 2. Операции над детерминированными функциями (145). 3.

Реализация ограниченно-детерминированных функций схемами (159). 4. Замкнутые классы и полнота в множествах детерминированных и ограниченно-детерминированных функций (171). 102 126 Глава Ъ' Элементы теории алгоритмов з г1. Машины Тьюринга и операции над ними. Функции, вычислимые на машинах Тьюринга 178 1. Простейшие свойства машин Тьюринга (178). 2. Операции над машинами Тьюринга (186). 3. Вычислимые функции (190).

8 2. Классы вычислимых и рекурсивных функций 1. Операции суперпозиции, примитивной рекурсии и минимизации (195). 2. Некоторые специальные свойства рекурсивных функций (201). Глава Ч1 Графы и сети 9 1. Основные понятия теории графов 1. Простейшие свойства графов. Изоморфизм графов (203). 2.

Ориентированные графы (210). '3 2. Планарность и раскраска графов . 8 3. Деревья и сети 1. Корневые деревья (219). 2. Двухполюсные сети (223). 203 215 219 Глава ЧП Элементы теории кодирования '8 1. Алфавитное кодирование. Критерий однозначности кодирования . 230 8 2. Коды с минимальной избыточностью .............................. 235 Оглавление 3 3. Самокорректирующиеся коды 1.

Расстояние Хэмминга, шары, сферы и циклы в и-мерном кубе (241). 2. Коды, обнаруживаютцие и испрввляютдие ошибки (244). 3 4. Линейные коды Глава 1Х Минимизация булевых функций 3 1. Структура граней и-мерного куба. Покрытия и тесты для таблиц 290 3 2. Методы построения сокращенной д. н. ф ........................... 296 3 3. Методы построения тупиковых, минимальных н кратчайших д. н.

ф. 301 Глава Х Реализация булевых функций схемами и формулами 3 1. Схемы из функциональных элементов 3 2. Контактные схемы и формулы 306 312 Ответы, указания, решения Список литературы Предметный указатель . 324 412 414 Глава ЧШ Элементы комбинаторики 3 1.

Перестановки и сочетания. Свойства биномнвльных козффициентов ............................................................ 253 3 2. Формула включений н исключений 262 3 3. Возвратные последовательности, производящие функции, рекуррентные соотношения . 265 3 4. Теория Пойа .............. 273 3 5. Асимптотические оценки и неравенства ...........................

277 '3 6. Оценки в теории графов и сетей 284 ПРЕДИСЛОВИЕ К ТРЕТЬЕМ'У ИЗДАНИК) Третье издание сборника задач выходит спустя четыре года после того как ушел из жизни Гарий Петрович Гаврилов. Со времени предыдущего издания про|ила 11 лет. Необходимость переиздания ощущалась давно, поскольку сборник активно используется во многих вузах для проведения упражнений по дискретной математике. Отличия этого издания от предыдущего незначительны. Исправлены опечатки и некоторые ошибки. Некоторым изменениям подверглись теоретические введения к главам. Существенных изменений нс потребовалось, поскольку материал книги по-прежнему соответствует программе по дискретной математике для университетов России.

Некоторые изменения назревают. Например, в главе, посвященной теории алгоритмов, следовало бы, видимо, поместить задачи по сложности алгоритмов и сводимости. Это направление бурно развивается и находит все большие приложения. В комбинаторике и теории графов все более значительную роль находят вероятностные методы. Алгебраические методы теории кодирования находят все большее применение в криптографии. Эти тенденции ощущаются и, по-видимому, скоро найдут свое отражение в вузовских программах и учебниках. Пользуясь случаем, выражаю признательность всем коллегам., активно использующим книгу в своей преподавательской и научной деятельности и высказавшим свои замечания и предложения, а также студентам и аспирантам, оказавшим помощь в подготовке нового издания.

А. А. Савоженкв ПРЕДИСЛОВИЕ КО ВТОРОМог ИЗДАНИНЭ Это пособие является существенной переработкой нашего «Сборника задач по дискретной математике», вышедшего в 1977 г. В предлагаемой вниманию читателя книге значительно расширен набор задач тренировочного характера (упражнений) и задач среднего уровня трудности. Пособие предназначено в основном для студентов младших курсов университетов и технических вузов, но может быть полезно также студентам старших курсов и аспирантам, применяющим методы и конструкции дискретной математики и желающим углубить свои знания в этой области.

Преподаватели могут использовать его при подготовке упражнений для семинарских занятий. Основным теоретическим руководством по разделам дискретной математики, представленным в данном сборнике, является книга С. В. Яблонского «Введение в дискретную математику» (М.: Наука, 1986). Другие библиографические источники, могущие оказаться полезными при работе над различными главами, указаны в списке литературы, помещенном в конце данного пособия. В сборнике десять глав. Первые пять глав посвящены алгебре логики, к-злачным логикам, теории автоматов и теории алгоритмов.

На материале этих глав читатель познакомится с такими важными понятиями дискретных функциональных систем, как булева и к-значная функции, дискретный преобразователь 1автомат), вычислимая и рекурсивная функции, функционально полная система, операции супер- позиции, обратной связи, примитивной рекурсии и минимизации, а также составит достаточно четкое представление о различных способах задания дискретных функций (табличном, с помощью полиномов и нормальных форм, с помощью диаграмм, канонических уравнений и схем), об эквивалентных преобразованиях формул, эффективной вычислимости и некоторых конкретных формах определения алгоритма (машинах Тьюринга и рекурсивных функциях).

В главе Ч1 содержатся задачи по теории графов, сетей и схем. Цель этой главы -- познакомить читателя с языком и основополагающими понятиями и методами теории графов, широко применяемыми при описании и исследовании структурных свойств объектов в различных областях науки и техники. Приводятся задачи для закрепления основных понятий теории графов, на выявление планарности и по раскраске графов, на подсчет объектов с заданной геометрической структурой Предисловие но второму изданию и т.п. Авторы надеются, что преподаватель найдет здесь и такие задачи, с помощькв которых удастся обучить студента математически строгому доказательству геометрически «очевидных» утверждений.

В главе ЧП представлены задачи о свойствах алфавитных кодов, кодов с минимальной избыточностью и самокорректирующихся кодов. Глава Ъ'П1 посвящена комбинаторике. При изучении дискретной математики часто приходится сталкиваться с вопросами существования, подсчета и оденки числа различных комбинаторных объектов.