Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 2
Текст из файла (страница 2)
В. Яблонского «Введение в дискретную математику» (М.: Наука, 1986). Другие библиографические источники, могущие оказаться полезными при работе над различными главами, указаны в списке литературы, помещенном в конце данного пособия. В сборнике десять глав. Первые пять глав посвящены алгебре логики, к-злачным логикам, теории автоматов и теории алгоритмов. На материале этих глав читатель познакомится с такими важными понятиями дискретных функциональных систем, как булева и к-значная функции, дискретный преобразователь 1автомат), вычислимая и рекурсивная функции, функционально полная система, операции супер- позиции, обратной связи, примитивной рекурсии и минимизации, а также составит достаточно четкое представление о различных способах задания дискретных функций (табличном, с помощью полиномов и нормальных форм, с помощью диаграмм, канонических уравнений и схем), об эквивалентных преобразованиях формул, эффективной вычислимости и некоторых конкретных формах определения алгоритма (машинах Тьюринга и рекурсивных функциях).
В главе Ч1 содержатся задачи по теории графов, сетей и схем. Цель этой главы -- познакомить читателя с языком и основополагающими понятиями и методами теории графов, широко применяемыми при описании и исследовании структурных свойств объектов в различных областях науки и техники. Приводятся задачи для закрепления основных понятий теории графов, на выявление планарности и по раскраске графов, на подсчет объектов с заданной геометрической структурой Предисловие но второму изданию и т.п. Авторы надеются, что преподаватель найдет здесь и такие задачи, с помощькв которых удастся обучить студента математически строгому доказательству геометрически «очевидных» утверждений.
В главе ЧП представлены задачи о свойствах алфавитных кодов, кодов с минимальной избыточностью и самокорректирующихся кодов. Глава Ъ'П1 посвящена комбинаторике. При изучении дискретной математики часто приходится сталкиваться с вопросами существования, подсчета и оденки числа различных комбинаторных объектов. Поэтому полезно бывает знать основные принципы и методы комбинаторного анализа. В главу згП1 включен не только традиционный комбинаторный материал (перестановки, сочетания, свойства биномиадьных коэффициентов, принцип включения-исключения, возвратные последовательности, рекуррентные соотношения, производящие функции), но и современные разделы комбинаторной математики (теория Пойа, асимптотические оценки и неравенства).
В главе 1Х затронуты вопросы, относящиеся к минимизации булевых функций. Здесь представлены задачи о свойствах булева куба, характеризациях дизъюнктивных нормальных форм, алгоритмах на множествах д.н.ф. Глава Х содержит задачи по реализации булевых функций схемами из функциональных элементов, контактными схемами и формулами. Для удобства читателя авторы сочли целесообразным поместить в каждом параграфе необходимые теоретические справки.
Многие задачи снабжены ответами и указаниями. К сожалению, ограниченный объем не позволил включить подготовленные нами подробные указания и решения задач среднего и высокого уровней трудности. По происхождению материал, включенный в задачник, весьма разнообразен. Есть и «фольклорные» задачи., есть задачи, возникшие при обработке журнальных статей, отдельные задачи заимствованы из других руководств. Основная часть задач придумана авторами при подготовке к семинарским занятиям и проведению экзаменов по дискретной математике, а также при написании данного пособия и ранее вышедшего сборника задач.
При написании настоящего пособия мы пытались учесть все замечания, которые были высказаны нам коллегами и читателями, приславшими свои отзывы о содержании «Сборника задач по дискретной математике». Всем им мы выражаем искреннюю бла|юдарность. В заключение отметим, что работа над пособием распределялась следующим образом: главы 1, П1-У, а также у 1, 2 главы У1 и ответы ко всем этим главам и параграфам написаны Г.П. Гавриловым, главы П, Ъ'П Х, а также з 3 главы Ъ'1 и ответы к ним написаны А. А.
Сапоженко. Г. П. Гаврилов, А. А. Сапоженко Глана 1 СПОСОБЫ ЗАДАНИЯ И ПРОСТЕЙШИЕ СВОЙСТВА ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ З 1. Функции алгебры логики и способы их задания. Операция суперпозиции 1. Основные понятия и факты, связанные с булевым кубом и булевыми функциями. Набор (а!, оз, ..., оп), где о! Е (О, Ц, 1 < ! < и, называется булевым или двоичным набором (вектором). Элементы набора часто называют компонентами или координатами. Кратко набор 1аз, ав, ..., оп) обозначают через а" или а.
Число и называется длиной набора а". Весом (или нормой) набора б" (обозначение йб" (~) называют число его координат, рави ных 1, т.е. йб" (! = 2 аь !=! Множество всех двоичных наборов длины и образует и-мерный йулее 1или двоичный) куб, который называют также единичным п-мерным кубом и обычно обозначают В~ (а иногда Езп). Применяя геометрическую терминологию, наборы а" е В" называют вершинами куба В".
Множество всех вершин куба В", имеющих вес к, называется к-м слоем кдйа В" (обозначение Вг). Каждому двоичи ному набору а" можно сопоставить число и1а") = 2 о, 2"' ' !=1 помер набора а". Набор о" является двоичным разложением своего номера и(а"). Расстоянием (Хэмминга) между вершинами а и В куба В" па.- п зывается число р(о, !э) = 2 )а! — В!); оно равно числу координат, в г=! которых наборы а и 11 отличаются друг от друга. Расстояние Хэннинга являотся метрикой, а куб В" метрическим пространством.
Наборы а = 1аз, аз, ..., а„) и,З = (В!, Вз,...,,9„) из В" называются соседними, если р(а, В) = 1, и протиеополоэкными, если р1Н,,З) = и, т.е. соседние наборы различаются только в одной координате, а противоположные во всех координатах. Говорят, что 1О Гл. 1. Способы задания и свойства функций алгебры логики 1111 111 1110 110 011 11 10 01 00 0011 001 100 0001 000 В4 вг Рис. 1.1 порядком на множестве В". На рис. 1Л приведены диаграммы частично упорядоченных множеств В, В и В . Функция У'(ты ..., т„), определенная на множестве В" = 10, 1)" и принимающая значения из множества 10, 1), называется функцией алгебры логики (а также булевой или булевской функцией). Набор символов переменных (ты ..., т„) будет обозначаться также через й" или х, а множество тех же символов переменных через Х". Множество всех булевых функций, зависящих от переменных ть, ..., та, будем обозначать через Рд(Ха).
При этом обычно полагают, что н > О. Нульместными булевыми функциями (т.е. соответствующими и = 0) являются константы 0 и 1. Булеву функцию 1" 1й") при и > 1 можно задать таблицей Т(Г) (табл. 1.1)., в которой наборы Н = (оы ог, ..., о„ы о„) выписываТаблица 1.1 ются в порядке возрастания их номеров (сверху вниз). Имея в виду такое стандартное расгщлолвенив наборов, булеву функцию у(ть) набор Н" предшествует набору )3" (или не больше набора Вл), и применяют обозначение Н" 4 В", если сн < Д для всех 1 = 1,..., и. Если 5„4 р„и Н" ~ Д", то говорят, что набор На строго предшесгпвует набору 13" (или строго меньше, или меньше набора )3"), и используют обозначение Н" -~ В".
Наборы Н" и Д" называются сравнимыми, если либо На < р'ь, либо Дь 4 Н". В случае, когда ни одно из этих отношений не выполняется, наборы Н" и 13" называются несравнимыми. Говорят, что набор На непосредственно иредиьествувт набору Д", если Н" -~ Д" и р(о", Д") = 1. Отношение 4 (его часто называют отношением нрвдшествования) является частным у 1. Функции алгебры логики. Операцию суперпогиции удобно задавать вектором ее значений: й~~ = (ое, оы ..., ог г), где координата о, равна значения> функции 1(х") на наборе й, имеющем номер 1 (1 = О, 1,..., 2" — 1). Символом Ху обозначают множество (й" ~ (й" Е В") аг (1(й") = = 1)), т.е.
множество всех наборов йп из В", на которых функция 1" (х") обращается в 1. Булеза функция 1(хп) при п > 2 может быть задана прямоугольной таблицей Пап ь(() (табл. 1.2), в которой значение Дом ..., оя, Таблица 1.2 хй»1 хь-;-г функции у(х") помещается на пересечении «строки» (оы ..., оь) и «столбца» (овьы ..., оп), 1 ( к < и. Булевы функции, задаваемые табл. 1.3 и табл. 1.4, будут считаться элементарными. Таблица 1.4 Т аблица 1.3 Приведем обозначения и названия этих функций. 1. Функции О и 1 называются соответственно (пюждественнььм) нулем и (тождественной) единицей. 2. Функция ~г называется тождественной функцией и обозначается через х.
З.Функция уг называется огприцанием х, обозначается х или Зх (читается «не х»). 4.Функция (з называется коньюнкцией хг и хг, обозначается хг аг хг или хг хг, или хгхг, или шш (хы тг) (читается «хг и хг»). 12 Гл, 1. Способы задания и ввойсгпва функций алгебры логики 5.
Функция Д называется дизъюнкцией хз и хг, обозначается хг М хг или хз + хг, или щах(хы хг) (читается «хг или хг»). 6. Функция 1ь называется суммой по модулю 2 хз и хг, обозначается хз Ю тг или хз + хг (читается «хг плюс хг»). 7. Функция 1в называется эквнваленцией (или эквивалентностью) хз и хг, Обозначается хз хг или хз = хг, или хз (-) тг (читается «хг эквивалентно хг»). 8. Функция 1г называется импликацией хз и хг, обознютется хг — э хг или хз Э хг (читается «хз имплицирует хг» или «из хг следует хг»). 9.
Функция гв называется штрихом Шеффера хз а хг, обозначается хз ~ хг (читается «не хг или не хг» или «хз и хг не совместны»). В технической литературе функция хг ~ хг называется обычно анти- конъюнкцией или «нс — и». 10. Функция 1э называется стрелкой Пирса хз и хг, обозначается хз 1 хг (читается «ни хы ни хг» или «не хг и не хг»). В технической литературе функция хг ь хг обычно называется антидизъюнкцией или «не — али» (а также функцией Даеевра и функцией Бебба).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
