Элементы дискретной математики


Серия «Учебные издания для бакалавров»





                А. И. Новиков




ЭЛЕМЕНТЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

Учебное пособие

З-е издание

Рекомендовано федеральным государственным бюджетным учреждением «Федеральный институт развития образования» (ФГБУ «ФИРО») в качестве учебного пособия для использования в образовательном процессе образовательных организаций, реализующих программы высшего образования по направлениям подготовки «Экономика», «Менеджмент» (уровень бакалавриата)

Регистрационный номер рецензии 529 от 04 февраля 2018 г.


Москва Издательско-торговая корпорация «Дашков и К°» 2021

УДК 510+519.1
ББК 22.12+22.176
    Н73


Автор:
     А.      И. Новиков — доктор физико-математических наук, профессор Российского университета кооперации.


Рецензенты:
    В.     А. Волочиенко — доктор экономических наук, профессор;
    И. И. Постников — доктор технических наук, профессор.




    Новиков А. И.

Н73 Элементы дискретной математики: Учебное пособие для бакалавров / А. И. Новиков. — 3-е изд. — М.: Издательско-торговая корпорация «Дашков и К°», 2021. — 209 с.
         ISBN 978-5-394-04430-4
          В учебном пособии рассмотрены основные методы и приемы дискретной математики, определяемые требованиями федеральных государственных образовательных стандартов высшего образования. В нем в краткой и доступной форме изложены основные разделы дискретной математики: алгебра логики, теория множеств, основные понятия теории графов и другие математические понятия, применяемые в экономике и вычислительной технике.
          Все излагаемые методы и подходы иллюстрируются примерами и упражнениями для закрепления знаний и формирования навыков их применения.
          Для студентов бакалавриата, обучающихся по направлениям подготовки «Экономика», «Менеджмент».






ISBN 978-5-394-04430-4

         © Новиков А.И.,2019
         © Новиков А. И., 2020, с изменениями
                               © ООО «ИТК «Дашков и К°», 2020,
                                  с изменениями

            СОДЕРЖАНИЕ



Глава 1. АЛГЕБРА ЛОГИКИ...............................6
   1.1. Логические функции............................6
   Основные понятия ..................................6
   Существенные и несущественные переменные...........9
   1.2. Элементарные булевы функции................. 11
   1.3. Логические формулы...........................14
     Порядок выполнения логических операций в сложном логическом выражении............................19
     Построение таблицы истинности...................20
   1.4. Законы логики................................27
   1.5. Упрощение логических формул. Правила преобразования формул............................................32
   1.6. Двойственные функции.........................37
   1.7. Полнота в логике высказываний................42
Глава 2. ПОСТРОЕНИЕ НОРМАЛЬНЫХ ФОРМ
ЛОГИЧЕСКИХ ФУНКЦИЙ...................................46
   2.1. Понятие нормальной формы.....................46
   2.2. Дизъюнктивная и конъюнктивная нормальные формы.46
   2.3. Алгоритмы построения ДНФ и КНФ...............49
   2.4. Алгоритмы переходов от одной нормальной формы к другой..........................................52
     Переход от ДНФ к КНФ............................52
     Переход от КНФ к ДНФ............................53
   2.5. Совершенные дизъюнктивные и конъюнктивные нормальные формы..................................56
   2.6. Способы приведения к совершенным нормальным формам............................................57
Глава 3. МИНИМИЗАЦИЯ НОРМАЛЬНЫХ ФОРМ.................66
   3.1. Проблема минимизации.........................66
   3.2. Минимизация дизъюнктивных нормальных форм....67
     Первый этап (получение сокращенной формы).......69
     Второй этап (получение минимальной формы).......72
   3.3. Минимизация конъюнктивных нормальных форм....80


3

   3.4. Минимизации функций в классе нормальных форм...85
   3.5. Минимизация частично определенных функций....86
   3.6. Минимизация логических функций по картам Карно.90
   3.7. Карты Карно при минимизации не полностью определенных функций.............................101
Глава 4. ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА..................104
   4.1. Базовые логические элементы (вентили). Функциональные схемы.............................104
   4.2. Виды задач на логические элементы...........107
Глава 5. МНОЖЕСТВО..................................116
   5.1. Понятие множества...........................116
   5.2. Операции над множествами....................119
   5.3. Свойства операций над множествами...........125
   5.4. Формула включений и исключений..............133
   5.5. Отношения...................................135
     Декартово произведение множеств................135
     Отношение множеств.............................136
     Матрица отношения..............................136
     Обратное отношение.............................138
     Композиция отношений...........................139
     Свойства отношений.............................139
     Отношение эквивалентности......................144
     Отношение порядка..............................146
Глава 6. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ...................148
   6.1. Основные понятия............................148
   6.2. Способы задания графов......................153
     Матрица смежности..............................154
     Матрица инцидентности..........................155
   6.3. Маршруты, цепи, циклы.......................158
     Задача о кратчайшем пути между исходным узлом и любым другом узлом сети......................161
     Задача о кратчайшем пути между двумя пунктами..167
     Задача определения максимального потока........172
     Задача о назначениях...........................177
     Дерево решений.................................182

4

Глава 7. СЕТЕВОЕ ПЛАНИРОВАНИЕ И УПРАВЛЕНИЕ..............184
   7.1. Основные понятия сетевой модели..............184
   7.2. Метод критического пути......................186
     Основные временные параметры сетевых графиков . 187
     Построение предварительного временного графика .191
     Определение резервов (запасов) времени..........194
   7.3. Распределение ресурсов. Оптимизация сетевого графика ... 196
   7.4. Стоимость проекта. Оптимизация сетевого графика.200
   7.5. Сетевые модели в условиях неопределенности ..204
ЛИТЕРАТУРА...........................................208

5

            Глава 1. АЛГЕБРА ЛОГИКИ



        1.1. Логические функции

    Основные понятия

    Логика — наука о законах и формах правильного мышления. Различают формальную и математическую логику.
    Формальная логика связана с анализом наших обычных содержательных рассуждений, выражаемых разговорным языком. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления от его содержания.
    Математическая логика, являясь частью формальной логики, изучает только высказывания и рассуждения, для которых можно однозначно решить: истинны они или ложны. В математической логике расширяется класс логических операций, которые используются в логических преобразованиях высказываний (алгебра логики). Создателем алгебры логики является английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.
    Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучают логические операции над высказываниями.
    Высказывание — это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Истинность или ложность, приписываемые некоторому высказыванию, называются его значением истинности, или истинностным значением.
    В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно.
    Вопросительные, восклицательные предложения, а также определения не будем считать высказываниями, о них нельзя сказать, истинны они или ложны. Например, фразы: «куда ты пошел?», «стойте!», «результат сложения двух чисел называется их суммой» не являются высказываниями.
    Высказывания бывают простые и сложные.
    Простым называется высказывание, которое не содержит в себе других высказываний в качестве своих частей.


6

     Будем обозначать простые высказывания малыми буквами латинского алфавита a, b, c,..., которые называют логическими переменными . Значением логической переменной могут быть только истина и ложь. Обозначение: истинное высказывание — цифра 1, ложное — цифра 0.
     Например, высказывание a = «Луна является спутником Земли» — истинно (1), а высказывание b = «Москва — столица Германии» — ложно (0).
     Сложным называется высказывание, образованное из простых с помощью логических связок (или, и, н е и др.).
     Например, из простых высказываний: «На улице идет дождь», «На улице светит солнце», «На улице пасмурная погода» можно составить сложные высказывания: «На улице идет дождь и на улице светит солнце», «На улице светит солнце или на улице пасмурная погода», «Неверно, что на улице идет дождь».
     В алгебре логики простые высказывания заменяются логическими переменными, логические связки — логическими операциями над высказываниями, которые имеют свое название и обозначение. При этом сложное высказывание превращается в логическую функцию.
     Булевой, или логической, переменной называется переменная, принимающая одно из двух значений 0 и 1.
     Булевой, или логической, функцией (ЛФ) называют функцию F(x 1, x₂,..., xₙ), аргументы которой x1, x₂,..., xₙ (независимые переменные) и сама функция (зависимая переменная) принимают значения 0 или 1.
     Таким образом, сложное высказывание рассматривается как логическая функция F(x 1, x ₂,..., xₙ), аргументами которой являются логические переменные x 1, x₂,., xₙ (простые высказывания).
     Каждое из простых высказываний, входящих в сложное, может быть либо истинно, либо ложно. Значение истинности сложного высказывания зависит от истинности входящих в него простых высказываний и типа объединяющих их связок.
     Основная задача математической логики — на основании ложности или истинности простых высказываний определить значение сложного высказывания.
     Существуют два основных способа задания булевых функций — табличный и аналитический. При табличном способе булева функция

7

задается таблицей истинности, а при аналитическом способе — формулой, т. е. аналитическим выражением, построенным из операций булевой алгебры.
    Таблицу, показывающую, какие значения принимает логическая функция при всех сочетаниях (наборах) значений ее аргументов, называют таблицей истинности логической функции. Таблица истинности логической функции n аргументов содержит 2ⁿ строк, n столбцов значений аргументов и 1 столбец значений функции.
    Например, таблица истинности функции f (x 1, x₂, x₃) трех переменных имеет вид

Х1 Х2 Х3 f (x1, x2, x3)
0  0  0  f (0,0,0)     
0  0  1     f(0,0,1)   
0  1  0  f (0,1,0)     
0  1  1     f(0,1,1)   
1  0  0  f (1,0,0)     
1  0  1    f (1,0,1)   
1  1  0    f (1,1,0)   
1  1  1     f(1,1,1)   

    Таблица истинности состоит из двух частей. В левой части таблицы содержатся наборы значений переменных x1, x₂, x₃, а в правой — значения функции f (x1, x₂, x₃) на соответствующих наборах значений переменных.
    При перечислении наборов (x1, x ₂, x ₃) использован лексикографический порядок, который совпадает с порядком возрастания наборов, понимаемых как двоичные числа.
    Таблицы истинности, задающие булевы функции от одного числа аргументов, отличаются лишь последним столбцом. Поэтому, зафиксировав лексикографический порядок перечисления наборов, булеву функцию от одного числа переменных можно также задавать в виде вектора значений функции, который выписывается по правому столбцу ее таблицы истинности.


8

    Например, функцию f (x ₁, x₂) двух переменных можно задать в виде следующей таблицы истинности

Х1 Х2 f(*1 -х2 )
0  0      0     
0  1      1     
1  0      1     
1  1      0     

или в виде вектора значений функции f = (0110), т. е. ,/(0,0) = 0, f0,1) = 1, f(1,0) = 1, f(1,1) = 0.
     Булеву функцию, определенную на всех своих наборах, называют полностью определенной. Булеву функцию n переменных называют не полностью определенной или частичной, если она определена не на всех двоичных наборах.
     Две булевы функции от одного и того же числа переменных n равны, если совпадают их таблицы истинности.


    Существенные и несущественные переменные

     Переменная X. булевой функции f(x1,x₂,...,xₙ) называется несущественной (фиктивной), если

f ⁽x1,..., xₜ -1, 0 xₜ₊1,..., xn )= f ⁽x1,..., xₜ _1, ¹ xₜ₊1,..., xn ⁾

при любых значениях остальных переменных, т. е. изменение значения xf не изменяет значения функции; иначе переменная xi называется существенной.
     Чтобы определить по таблице истинности булевой функции, что переменная x f является несущественной, нужно проверить, что на всех парах наборов, у которых одинаковы все компоненты, кроме i-й (i -я компонента в одном наборе равна 0, а в другом — 1), функция принимает равные значения.


9

    Например, пусть функция f (x1, x₂, x₃) задана таблицей истинности

x 1 x2 x 3 f (X1 ,X2 ,x3)
0   0   0        0       
0   0   1        0       
0   1   0        1       
0   1   1        1       
1   0   0        0       
1   0   1        0       
1   1   0        1       
1   1   1        1       

Переменная x ₃ является несущественной для f (x1, x₂, x₃), так как f (x1,x2,0) = f (x1,x2,1).
    Удаляя ее, получим функцию f (x1, x₂):

x 1 x 2 f (X1 ,X2)
0   0       0     
0   1       1     
1   0       0     
1   1       1     

    Переменная x 1 также является несущественной, так как f (0, x₂) = = f (1,x₂). Удаляя ее, получим функцию f (x₂) = x₂.
    Булевы функции не изменяют свои значения путем введения (или удаления) несущественных переменных.
    Две функции f (x1,..., xₖ) и f (x1,..., xₘ) от разного количества переменных равны, если одна получается из другой путем удаления или введения несущественных переменных.
    Обозначим через Р₂ множество всех булевых функций. Число всех булевых функций от n переменными равно 2² . Число булевых функций при n = 1 равно 2² = 2² = 4, а при n = 2 равно 2² = 2⁴ = 16 .


10

        1.2. Элементарные булевы функции

    Среди булевых функций особо выделяются так называемые элементарные булевы функции двух и менее аргументов, посредством которых можно описать любую булеву функцию от любого числа переменных.
    Отрицанием (инверсией) называется булева функция одной переменной x, которая определяется следующей таблицей истинности:

X f(X)
0  1  
1  0  

     Обозначение: —x, или x . Читается «неверно, что x» или просто «не x».
     Инверсия (отрицание) логической переменной истинна, если сама переменная ложна, и, наоборот инверсия ложна, если переменная истинна.
     Например, если высказывание a = «Амазонка — великая река» — истинно, то отрицание — a = «Неверно, что Амазонка — великая река» — ложно; если высказывание a = «Петр водит автомобиль» — ложно, то a = «Петр не водит автомобиль» — истинно.
     Конъюнкцией (логическим произведением) называется булева функция двух переменных x и у, которая определяется следующей таблицей истинности:

X у f(X, у)
0 0 0      
0 1 0      
1 0 0      
1 1 1      

     Обозначение: xлу, x-у, xy, x&y, min(x,у). Читается: «x и у» или «х умножить на у». Логическая связка «и» указывает на одновременность нескольких событий, их последовательность.
     Конъюнкция двух логических переменных истинна тогда и только тогда, когда обе переменные истинны.


11

    Например, для высказываний a = «Саша играет на гитаре», b = «Саша играет на фортепиано» их конъюнкцией будет высказывание а л b = «Саша играет на гитаре и фортепиано», которое истинно, если оба высказывания а, b — истинны.
    Дизъюнкцией (логической суммой) называется булева функция двух переменных x и у, которая определяется следующей таблицей истинности:

X у f (X, у)
0 0    0    
0 1    1    
1 0    1    
1 1    1    

    Обозначение: xvу, x+у, max(x, у). Читается: «x или у» или «х плюс у». Логическая связка «или» указывает, что высказывания x, у могут существовать как раздельно, так и вместе.
    Дизъюнкция двух логических переменных ложна тогда и только тогда, когда обе переменные ложны.
    Например, для высказываний а = «Число 9 делится на 3», b = «Число 9 делится на 4» их дизъюнкцией будет высказывание a vb = = «Число 9 делится на 3 или 4», которое истинно.
    Сложением по модулю 2 (исключающее или) называется булева функция двух переменных x и у, которая определяется следующей таблицей истинности:

X у f (X, у)
0 0    0    
0 1    1    
1 0    1    
1 1    0    

    Обозначение: x ©у. Читается: «либо x, либо у». Логическая связка «либо, либо» указывает, что высказывания x, у могут существовать только раздельно, т. е. только одно из двух. Эту операцию еще называют строгой дизъюнкцией.


12

    Сложение по модулю 2 двух логических переменных истинно, когда значения истинности переменных различаются.
    Например, высказывание: «Сегодня понедельник или вторник» состоит из двух простых: а = «сегодня понедельник»; b — «сегодня вторник». Поскольку одновременное выполнение условий не допускается, то данное высказывание есть a © b.
    Импликацией (логическим следованием) называется булева функция двух переменных x и у, которая определяется следующей таблицей истинности:

X У f (x, У)
0 0    1    
0 1    1    
1 0    0    
1 1    1    

    Обозначение: x^у. Читается: «из х следует у», «если x, то у».
    Импликация x^у двух переменных истинна всегда, кроме случая, если первая переменная (x) истинна, а вторая (у) ложна. Порядок следования членов импликации х, у имеет значение.
    Первая часть импликации (x) называется основанием, а вторая (у) — следствием. При этом из основания обязательно вытекает следствие, но из следствия не вытекает основание.
    Например, высказывание a ^ b = «Если вещество является металлом (a), то оно электропроводно (b)».
    Эквивалентностью (логической равнозначностью) называется булева функция двух переменных x и у, которая определяется следующей таблицей истинности

X У f (x, У)
0 0    1    
0 1    0    
1 0    0    
1 1    1    

    Обозначение: xоу, x~у. Читается: «x равносильно у», «x эквивалентно у» или «если и только если x, то у». Логический связка «если и

13