МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Я.П. Романчук ДИСКРЕТНА МАТЕМАТИКА Конспект лекцій Розглянутий на засіданні кафедри АСУ як навчальний посібник для студентів базового напрямку 050101 «Комп’ютерні науки» денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.) Львів − 2010 УДК 519.1+519.6 Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с. У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування. Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів. Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій. Рецензент: І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ. Відповідальна за випуск: З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ. ВСТУПНІ ЗАУВАЖЕННЯ Математика – наука молодих. Н. Вінер Основою сучасних швидкісних і якісних технологій опрацювання інформації є комп’ютери – від персональних (ПК) до надпотужних ЕОМ. Інформація, як правило, поступає в ЕОМ дискретно, а саме опрацювання її складається з послідовності окремих елементарних перетворень певних інформаційних одиниць (слів, літер, цифр тощо). Отже, дискретизація досліджуваних об’єктів, процесів і явищ є фундаментальною щодо їх відображення як реального світу в комп’ютері на основі певних моделей і їх перетворень. Досить часто такими моделями можуть бути конструкції дискретної математики, зокрема, такі як алгебра, формула, автомат, граф, алгоритм і ін. Більше того, динамічний розвиток дискретної математики останніми роками зумовлений також потребами комп’ютерних технологій, їх стрімким поширенням у багатьох галузях господарювання, науці, при вивченні та дослідженні складних систем. Дискретна математика – наука про способи побудови та ефективного опрацювання послідовностей цілих об’єктів, у окремих випадках літер
, породжуваних деяким алфавітом
, які можна розглядати як слова. Використання при цьому вербальної (словесної) інформації не накладає обмежень на застосування дискретних пристроїв для опрацювання неперервної інформації, оскільки її можна як завгодно точно апроксимувати дискретними сигналами, які, в свою чергу, можуть бути подані у вигляді слів. На практиці найчастіше використовують дворівневі (0 і 1) дискретні пристрої, що опрацьовують двійкову інформацію – слова алфавіту В. Взагалі, переваги дискретних пристроїв над неперервними стосовно застосування для подання, опрацювання та зберігання інформації зумовили їх домінуюче становище в галузі опрацювання інформації цифровими ЕОМ, при звуко- та відеозаписі, на радіо та телебаченні. Дискретна математика, крім її застосування до задач електронних цифрових пристроїв і систем, широко використовується також для створення та експлуатації комплексних автоматизованих систем управління, пакетів прикладних програм, банків (сховищ) даних, мікропроцесорних систем, мереж передавання даних тощо. Відповідно до робочої навчальної програми з дисципліни конспект лекцій відображає такі розділи дискретної математики як теорія множин і відношень, основні поняття загальної алгебри, елементи математичної логіки, комбінаторики та теорії графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування. В основу пропонованого конспекту покладено електронний посібник, який був доопрацьований, доповнений окремими розділами, задачами та прикладами. Завдання, вирішення яких досягається при вивченні дисципліни, полягають у тому, щоб: сформувати в студентів теоретичні основи методів моделювання об’єктів і процесів скінченної структури на основі системного підходу; навчити їх методів знаходження та оцінки розв’язків із залученням математичних моделей дискретних структур. Одним із вирішуваних у конспекті завдань є спроба зробити його зміст доступним для широкого кола читачів, які не мають спеціальної математичної підготовки. Це досягається тим, що поряд із висвітленням засадничих питань у конспекті наведена значна кількість прикладів із розв’язками та вправ, а в додатки винесені контрольні задачі та запитання для перевірки та самоперевірки знань студентів.