Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Дискретная математика

Покупка
Новинка
Артикул: 896880.01.99
Учебное пособие подготовлено в соответствии с Федеральным государственным образовательным стандартом среднего профессионального образования по специальности 09.02.07 «Информационные системы и программирование», входящей в список 50 наиболее востребованных на рынке труда новых и перспективных профессий, требующих среднего профессионального образования (ТОП-50). Книга содержит 5 разделов. Материал изложен в доступной форме, содержит множество примеров, таблиц и рисунков. После каждой темы приведены вопросы и мини-игры для закрепления материала. Каждый раздел заканчивается практической работой, в которой приведены примеры решения задач и задачи для самостоятельного выполнения. Изучение содержания материала представленного учебного пособия предполагает использование средств современных образовательных технологий, в частности, применяются QR-коды, которые являются ссылками на тренировочные задания, расположенные на сайте http://learningapps.org/. Пособие адресовано студентам учреждений среднего профессионального образования, обучающимся по специальности 09.02.07 «Информационные системы и программирование», и является дидактической поддержкой учебной программы «Дискретная математика с элементами математической логики».
Щербина, И. А. Дискретная математика : учебное пособие / И. А. Щербина. – Ростов на Дону : Феникс, 2025. - 124 с. – (Среднее профессиональное образование). - ISBN 978-5-222-38588-3. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2286596 (дата обращения: 20.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Серия «Среднее профессиондльноЕ обрдзовдние»









И. А. Щербинл

ДИСКРЕТНАЯ МАТЕМАТИКА




Рекомендовано Научно-методическим советом Международного научного общественного объединения «МАИТ» для использования в качестве учебного пособия для студентов образовательных учреждений среднего профессионального образования, обучающихся по специальностям укрупненной группы 09.00.00 Информатика и вычислительная техника (рецензия № РЭЗ19-08 от 16.04.2019 г.)



Электронный ресурс










Ростов-на-Дону «Феникс»

ПРЕДИСЛОВИЕ





   В данной книге в сжатой форме изложены некоторые специальные разделы математики, которые предусмотрены требованиями ФГОС к содержанию курса «Дискретная математика» для среднего специального образования по специальности 09.02.07 «Информационные системы и программирование». Книга написана по программе «Дискретная математика с элементами математической логики», которая была разработана автором книги. Рабочая программа учебной дисциплины ЕН.02 «Дискретная математика с элементами математической логики» является частью основной образовательной программы в соответствии с ФГОС СПО по специальности 09.02.07 «Информационные системы и программирование», применяется в Государственном автономном профессиональном образовательном учреждении Свердловской области «Екатеринбургский экономико-технологический колледж» г. Екатеринбурга.
   Цель данной книги — дать необходимый теоретический минимум информации, рассмотреть возможные практические задачи и научиться решать задачи по дискретной математике.
   Согласно структуре программы весь материал разбит на разделы, а каждый раздел состоит из тем, в которые входят лекции и практические работы, вопросы для самопроверки, а также тренажеры-задачки для закрепления теоретического материала.
   По каждой теме:
   — приведены основные теоретические сведения;
   —    рассмотрены типовые задачи с подробными решениями;
   —    даны примеры и упражнения для самостоятельной работы;



з

Предисловие

   —    после каждой лекции приведены вопросы для самоконтроля;
   —    представлены задания для закрепления теории в виде различных игр: «Кто хочет стать миллионером?», «Установите соответствие», кроссворд и т. д.
   Стиль и объем изложения курса в предлагаемой книге таковы, что изучение дисциплины возможно без помощи преподавателя.
   Учебное пособие ориентировано на современные технологии. Применяются 07?-коды, которые являются ссылками на приложения, представляющими собой различные игры, расположенные на ресурсе https:// learningapps.org/. Игры позволяют закрепить теоретический материал без напряжения и с удовольствием.
   В результате изучения дисциплины обучающийся осваивает следующие элементы компетенций, представленные в таблице ниже.


Компетенции, которые осваивает обучающийся

 Код               Наименование компетенции             
      Выбирать способы решения задач профессиональ-     
ОК 01 ной деятельности применительно к различным кон-   
      текстам                                           
      Осуществлять поиск, анализ и интерпретацию ин-    
ОК 02 формации, необходимой для выполнения задач про-   
      фессиональной деятельности                        
ОК 04 Работать в коллективе и команде, эффективно взаи- 
      модействовать с коллегами, руководством, клиентами
      Осуществлять устную и письменную коммуника-       
ОК 05 цию на государственном языке с учетом особенно-   
      стей социального и культурного контекста          
ОК 09 Использовать информационные технологии в про-     
      фессиональной деятельности                        
ОК 10 Пользоваться профессиональной документацией на    
      государственном и иностранном языках              

   При изучении лекции осваиваются общие компетенции ОК 05, ОК 09, ОК 10 — работа с лекцией и источниками, решение упражнений для тренажа (закрепление


Предисловие

теоретического материала); при ответе на вопросы для самоконтроля можно использовать различные источники. При выполнении практических заданий осваиваются общие компетенции ОК 01, ОК 02, ОК 04.
   По окончании изучения курса «Дискретная математика» обучающиеся должны
   знать'.
   — основные понятия теории множеств;
   — основы математической логики и теории графов;
   — основы логики предикатов;
   — основные методы алгоритмов;
   уметь'.
   — упрощать логические формулы;
   — решать булевы уравнения;
   — решать задачи в теории графов;
   —    использовать алгоритм Дейкстры и Флорида при нахождении кратчайшего пути в задачах на графах;
   —    строить высказывания к высказываниям, содержащим кванторы.
   Вначале при изучении дискретной математики покажется, что слишком сложно, и захочется забросить. Но не нужно сдаваться. При постепенном углублении в нее начнет проявляться общий рисунок представления о данном разделе математики. Обязательно нужно прорешать все задания, которые позволяют закрепить формулы. Просто учить бесполезно. В математике нужно понимание. Для выполнения тренажеров на мобильных устройствах нужно установить 07?-сканер.
   В данном учебном пособии используются значки для обозначения различных действий как обучающихся, так и преподавателей (см. табл, на с. 6).
   В конце учебного пособия представлен словарь основных терминов, который поможет при выполнении заданий для тренажа.


Предисловие

Условные обозначения

Символ            Значение           
       Примеры решения задач         
и      Упражнения                    
       для самостоятельного решения  
       Основные понятия, определения,
       теоремы                       
       Вопросы для самоконтроля      
       Время тренажа                 
       Немного истории               
       Практическая работа           

   В тексте будут встречаться некоторые математические символы. Их значение приведено в таблице ниже.


Символы и обозначения

Символ            Значение           
       Знак включения                
  G    Принадлежит множеству         
  £    Не принадлежит множеству      
  N    Множество натуральных чисел   
  Z    Множество целых чисел         
  Q    Множество рациональных чисел  
  R    Множество действительных чисел
  С    Множество комплексных чисел   
  и    Универсальное множество       
  0    Пустое множество              


Предисловие

Окончание табл.

 Символ               Значение            
    и     Объединение множеств            
    п     Пересечение множеств            
    \     Разность множеств               
    Л     Конъюнкция                      
    V     Дизъюнкция                      
---1. --- Отрицание, инверсия             
  --->    Импликация                      
          Эквиваленция                    
    ©     Разделительное ИЛИ, сумма Жегал          кина                            
    1     Штрих Шеффера                   
    1     Стрелка Пирса                   
    V     Квантор (символ) общности       
    3     Квантор (символ) существования  
    =     Тождество                       

   Краткий обзор истории формирования и развития дискретной математики
   Дискретная математика — область математики, изучающая свойства структур конечного характера. В отличие от дискретной классическая математика изучает свойства непрерывного характера, например теорию пределов и производные.
   Развиваясь параллельно с другими разделами математики, элементы дискретной математики являлись их составной частью.
   Важнейшие примеры дискретных математических объектов: множество, конечный граф, слово, входящее в высказывание, отображение одного множества в другое, функции. Деление математики на дискретную и классическую условно, поскольку элементы дискретной математики используются для изучения непрерывных моделей.
   В широком смысле дискретная математика включает в себя такие разделы математики, как теория множеств, математическая логика, теория графов, логика пре7

Предисловие

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

Учим символы и обозначения Игра «Установите соответствие»

Желаем успехов в новых начинаниях!


                РАЗДЕЛ 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ








Тема 1.1. Основы теории множеств



  Лекция 1. Множества. Операции над множествами

     Множества и операции над ними. Мощность множеств. Отношения и функции. Основные тождества алгебры множеств.
   Понятие множества

   Теория множеств явилась основой для развития науки в XX в. Ее методы используются в различных математических дисциплинах: функциональном анализе, теории функций действительного переменного и т.д. В настоящее время с нее начинается серьезное изучение математики, поскольку многие математические дисциплины используют ее аппарат.
   В начальной школе изучение понятия «множества» начиналось с чисел, которые входили в семейство натуральных и обозначались N. Чуть позже были введены понятия целых чисел, которые обозначались Z, далее множество дробей, десятичных и обыкновенных, обозначали Q, а все эти множества входили в множество, которое называлось множеством действительных чисел и обозначалось R. Данные множества изо


Рис. 1.1.
Множества

бражены на рисунке 1.1. Чуть позже, в старших классах, ввели множество комплексных чисел, которое рассматривается как отдельное множество и обозначается С.



Раздел 1. Элементы теории множеств

Данное множество позволяло извлекать корни из отрицательных чисел. Введем основные понятия, связанные с множеством.
        Множество — это совокупность элементов, обладающих сходными свойствами или признаками. Обозначается большими латинскими буквами А, В, С, D и т.д.
        Все числа, входящие в эти множества, называются элементами множества. Например: числа 1, 2, 3, 4, 5 и так далее — элементы множества натуральных чисел N. Обычно элементы множества обозначаются следующим образом: лр п₂, п₃. Принадлежность элементов множеству записывается следующим образом: ир и₂, п₃ е N. Если элемент не принадлежит множеству, то запись выглядит следующим образом: л₄ g N.
   Множество считается заданным, если перечислены все его элементы или указано свойство, которым обладают те и только те элементы, которые принадлежат данному множеству.
   Множество будем записывать так: М = {т₃, т₂; т₃} — множество, состоящее из элементов. Если частный случай, то будет выглядеть так: М = {1; 2; 3}. Если множество обладает каким-либо свойством, то будем записывать следующим образом: М = {т\т е N, т < 8} — множество М, состоящее из всех натуральных чисел меньше восьми.
        Если каждый элемент множества А является множеством В, то пишут А с В или В с А и говорят, что множество А является подмножеством множества В. В этом случае также говорят, что А содержится в В или В содержит А. Множество, которое не содержит ни одного элемента, называется пустым множеством и обозначается 0. Два множества А и В называются равными, если каждый элемент множества А принадлежит множеству В, а каждый элемент множества В принадлежит множеству А. Обозначается так: А с В и В с А. Количество элементов конечного множества называется мощностью множества и обозначается |Л|.


Тема 1.1. Основы теории множеств

   Например: задано множество N = {1; 3; 4; 5}. Данное множество состоит из четырех элементов, значит, мощность этого множества равна 4, т.е. |Л| = 4.
        Теорема. Пусть Л₂, А₃, Ап — конечные множества, их мощности соответственно равны |>4J = kᵥ \А₂\ = к₂, |Л₃| = к₃, \Ап\ = кп. Тогда мощность множества А₃ х А₂ х А₃ х ... х Ап равна произведению мощностей множества Aᵥ А₂, А₃, ..., Ап.
        Операции над множествами
   Множество, состоящее из всех тех и только тех множеств элементов, которые принадлежат хотя бы одному из множеств А и В, называется объединением множеств А и Ви обозначается: А и В или А + В.
   Например: А = {1; 3; 5; 6} и В = {2; 3; 5; 8}, тогда А и В = {1; 2; 3; 5; 6; 8}.
   Множество, состоящее из всех тех и только тех множеств элементов, которые принадлежат как множеству А, так и множеству В, называется пересечением множеств А и В и обозначается: А п В или А ■ В. Если А п В = 0, то говорят, что множества А и В не пересекаются.
   Например: А = {1; 3; 5; 6} и В = {2; 3; 5; 8}, тогда А п В = {3; 5}.
   Множество, состоящее из всех элементов множества А, не принадлежащих множеству В, называется разностью множеств А и В и обозначается: А \ В.
   Например: А = {1; 3; 5; 6} и В = {2; 3; 5; 8}, тогда А \ В = {1; 6}.
   Универсальное множество — это такое множество, которое состоит из всех элементов, а также подмножеств множества объектов исследуемой области.
   Универсальное множество может выбираться самостоятельно в зависимости от рассматриваемого множества и решаемых задач. Обозначается U.
   Множество, состоящее из тех и только тех элементов, которые не принадлежат множеству А, т.е. дополняют его до универсального множества, называется дополнением к множеству. Обозначается А.