Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 2
Текст из файла (страница 2)
Материал этих глав используется в главе 22 при изучении приложений теории чисел. В остальном они вполне самостоятельны и при желании могут быть опущены. С главы 8 начинается изучение широкого круга вопросов комбинаторики, которое затем продолжается во многих других частях книги, включая главы 12, 13 и 17. В той же главе 8 приводятся некоторые сведения из теории вероятностей, что само по себе весьма необычно для книг по дискретной математике.
Главы 9 и 20 охватывают основные понятия алгебры, включающие полу- группы, группы, кольца, решетки, полурешетки, области целостности и поля. При построении примеров групп и колец в этих главах используется материал разделов 3.6 и 4.3. Материал главы 9 используется далее в приложениях, рассматриваемых в главах 17-21. По многим причинам главы !1, 12 и 13 можно выделить в отдельную группу. В главе 11 продолжается изучение рекурсии. Кроме обычных линейных рекуррентных отношений, включаемых, как правило, в учебные курсы по дискретной математике, глава содержит сведения по теории конечных разностей. Если читатель не имеет хотя бы поверхностного представления о рекурсии, то для понимания этой главы ему необходимо ознакомиться с материалом главы 6. В главе 12 продолжается изучение комбинаторики, начатое в главе 8.
Здесь рассматриваются такие вопросы, как включение-исключение и задача о размещении. Кроме того, вводится понятие разупорядочения н ладейного полинома. Главы 11 и 12 тесно взаимосвязаны; в них многие темы рассматриваются с различных точек зрения, Одним из объектов такого разностороннего рассмотрения являются числа Стирлинга. Тем не менее, каждая из этих глав вполне самостоятельна. В главе 13 вводится понятие производящей функции, и на его основе продолжается изучение материала глав 11 и 12. В частности, производящие функции используются для построения эффективного метода решения задач о размещении.
В главах 14-16 продолжается изучение графов и деревьев, начатое в главе 6. Содержание этих глав очевидным образом зависит от материала главы 6, но с материалом большинства предыдущих глав практически не связано, Исключение составляет использование матриц в одном из рассматриваемых алгоритмов. Здесь изучаются стандартные для теории графов и деревьев объекты: плоские графы, циклы Гамильтона, бинарные деревья, остовные деревья, минимальные остовные деревья, алгоритмы нахождения кратчайшего пути и потоки в сетях. Еше одну группу составляют главы 17-22, посвященные прикладным вопросам теории чисел, алгебры и комбинаторики. Глава 17 посвящена теории вычис- Предисловие 13 лений; в ней рассматриваются коды, регулярные языки, автоматы, грамматики и связь между ними.
Здесь используются полугруппы, введенные в разделе 9.2. В главе 18 вводятся специальные коды, такие как коды с обнаружением ошибок и коды с исправлением ошибок. Для понимания материала этой главы требуется знание теории групп в объеме раздела 9.4 и теории матриц в объеме глав 4 и 5. Совершенно иное применение теория кодов получает в главе 22, где рассматриваются вопросы криптографии.
Эта глава требует знаний по теории чисел на уровне, выходящем за пределы данной книги. В главе 19 при изложении теорем Бернсайда и Пойя для перечисления цветов используются как алгебра, так и комбинаторика. Здесь, главным образом, требуется знание перестановок в объеме раздела 9.4. Глава 21 посвящена простейшим приложениям групп и полугрупп, а также их отображениям на комплексную плоскость. Необходимые предварительные сведения содержатся в разделах 9.2 и 9.5. Глава 22 содержит три важных приложения теории чисел.
Изучение функций хеширования и криптографии является для информатики весьма актуальным. При чтении вводного курса автор, как правило, полностью излагает материал глав 1-5, разделов 8.1-8.3, а также старается изложить первые три раздела главы 6. Как отмечалось ранее, материал первых восьми глав составлен так, чтобы обеспечить максимальную гибкость. В следующей таблице указано, какие предварительные сведения требуются для усвоения материала каждой из глав: Глава Необходимые главы или разделы Глава ! Глава 2 Глава 3 Глава 4 Глава 5 Глава б Глава ? Глава 8 Глава 9 Глава 10 Глава !! Глава !2 Глава 13 Глава 14 Глава 15 Глава !7 Глава 18 Глава 19 Глава 20 Глава 21 Глава 22 Никакие Никакие Разделы !.1-1.4 и 2.1 Никакие Разделы 4.1-4.3 Никакие Глава 3 Никакие Раздел 3.6 Глава 7 Разделы 5.1-5.3 Глава 8 Главы 11 и 12 Главы 5 и 6 Главы 5 и б Глава 9 Главы 5 и 9 Глава 9 Глава 9 Глава 9 Глава 10 14 ПреДислоеие ПОДДЕРЖКА Имеется подробное руководство к решению всех задач, рассмотренных в этой книге, которое можно заказать в издательстве Ргепйсе На!!.
Книга имеет свою страницу в Интернете; ее адрес: шгвш.ргепйаГдсот//ал~егзоп. Здесь вы найдете ссылки на другие интересные сайты, посвященные дискретной математике, в том числе содержащие контрольные задания и формулировки интересных проблем дискретной математики, не вошедшие в данное издание. БЛАГОДАРНОСТИ В первую очередь мне хочется поблагодарить Джорджа Лобелла, руководившего разработкой этой книги, и Барбару Мэк, координировавшую наши усилия. Я благодарю Кристиана и Филиппа Мусик за мастерски выполненное художественное оформление.
Особую благодарность я приношу Джеймсу Беллу, внесшему огромный вклад в написание данной книги. Очень жаль, что он не смог выступить в роли моего соавтора. Мне очень не хватает его партнерской поддержки. Кроме того, я хочу поблагодарить за помощь моих коллег Дэна Кука, Эда Вайлда, Рика Чоу, М. Б. Ульмера и Джерома Льюиса. Я благодарен своей студентке Соледад Шугаи за усилия, приложенные ею при изучении моего курса. Также хочу поблагодарить студентов Джоди Дина, Джессику Данс, Грейса Эллисона, Винни Чин Фай Ип, Присциллу Лапьер, Эстер Лай, Бадрала Мадани, Джулию Норрис, Трейси Квина и Роберта Вигерта, бывших первыми, кто прослушал данный материал, Пожалуйста, присылайте по электронной почте свои замечания и предложения по дальнейшему улучшению книги. Джеймс А. Андерсон !апбегзопйдтч.изсз.ебц 16 ГЛяВА 1.
Таблииы истинности, логика, доказательства Мы будем обозначать высказывания буквами латинского алфавита р, д, г, ... Например, р может обозначать утверждение Завгара будет дождь, а д — утверждение Квадрат целого числа есть число положительное. В обыденной речи для образования сложного предложения из простых используются связки — особые части речи, соединяющие отдельные предложения. Наиболее часто употребляются связки и, или, нет, если ... то, только если, и тогда и только тогда. В отличие от обыденной речи, в логике смысл таких связок должен быть определен однозначно.
Истинность сложного высказывания однозначно определяется истинностью или ложностью составляющих его частей. Высказывание, не содержащее связок, называется простым. Высказывание, содержащее связки, называется сложным. Пусть р и ц обозначают высказывания р: Джейн водит автомобиль, у: У Боба русые волосы. Сложное высказывание Джейн водит автомобиль и у Боба русые волосы состоит из двух частей, объединенных связкой и. Это высказывание может быть символически записано в виде рид или просто как р до, где символ л обозначает слово и на языке символических выражений. Выражение р л д называется конъюнкцией высказываний р и д.
Точно так же высказывание Джейн водит автомобиль или у Боба рыжие волосы. символически выражается как р или о или где ъ' обозначает слово или в переводе на символический язык. Выражение р м у называется дизъюнкцией высказываний р и д. Опровержение, или отрицание высказывания р обозначается через Таким образом, если р есть высказывание Джейн водит автомобиль, то р— это утверждение Джейн не водит автомобиль. Если г есть высказывание Джо нравится информатика, то Джейн не водит автомобиль и у Боба русые волосы или Джо любит информатику символически запишется как И р) л д) ъ'г.
И наоборот, выражение рл ( д) лг — это РКЗДЕЛ 1.1. Высказывания и логические связки 17 символическая форма записи высказывания Джейн водит автомобиль, у Боба волосы не русые и Джо нравится информатика. Рассмотрим выражение рлдн. Если некто говорит: "Джейн водит автомобиль и у Боба русые волосы", то мы, естественно, представляем себе Джейн за рулем автомобиля и русоволосого Боба. В любой другой ситуации (например, если Боб не русоволос или Джейн не водит автомобиль) мы скажем, что говорящий не прав. Возможны четыре случая, которые нам необходимо рассмотреть.
Высказывание р может быть истинным (Т) или ложным (с ) и независимо от того, какое истинностное значение принимает р, высказывание 4 может также быть истинным (Т) или ложным (с). Таблица истинности перечисляет все возможные комбинации истинности и ложности сложных высказываний. Случай р ц рЛц 1 Т Т 2 Т г 3 Р Т 4 с Г Джейн водит автомобиль или у Боба русые волосы, которое символически выражается как р ч'д. Если некто скажет: "Джейн водит автомобиль или у Боба русые волосы", то он будет не прав только тогда, когда Джейн не сможет управлять автомобилем, а Боб не будет русоволосым.
Для того чтобы все высказывание было истинным, достаточно, чтобы одна из двух составляющих его компонент была истинной. Поэтому р ч о имеет таблицу истинности Случай р ц р '/ ц 1 Т Т 2 Т Г 3 Г Т 4 с с Т Т Т с Высказывание р ч у ложно только в случае 4, когда р и д оба ложны. Если р — высказывание Джон богат, а д — высказывание Джон красив, и не знакомая с Джоном девушка уверена в истинности высказывания Джон богат или Джон красив, или Джон богат или красив, то она вправе ожидать, что Ранее мы убедились, что только в первом случае высказывание равд истинно. В остальных же мы имеем ложное значение р л д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
