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

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

УЧЕБНОЕ ПОСОБИЕ

Рекомендовано УМО по образованию в области 
телекоммуникаций в качестве учебного пособия 

для студентов высших учебных заведений, обучающихся 

по специальностям «Физика и техника оптической связи»,

«Сети связи и системы коммутации», 

«Многоканальные телекоммуникационные системы», 

«Радиосвязь, радиовещание и телевидение», 
«Средства связи с подвижными объектами», 

«Защищенные системы связи»

Москва
РИОР

ИНФРА-М

В.В. КУЛИКОВ

УДК 519.1(075.8)
ББК 22.176я73
 
К90

Рецензенты:
директор регионального центра информатизации,
заведующий кафедрой организации и технологии защиты 
информации, д-р техн. наук, старший научный сотрудник 
В.В. Копытов; 
заведующая кафедрой высшей математики, канд. техн. наук, 
доцент С.В. Сподынюк

Куликов В.В.

Дискретная математика : учеб. пособие / В.В. Куликов. — М. : 

РИОР : ИНФРА-М, 2020. — 174 с. — (Высшее образование: 
Бакалавриат). — DOI: https://doi.org/10.12737/2686

ISBN 978-5-369-00205-6 (РИОР)
ISBN 978-5-16-103320-3 (ИНФРА-М, online)

В пособии рассмотрены элементы математической логики, теории 

множеств и теории графов, приведены основные принципы комбинаторики. Описаны алгоритмы, позволяющие решать различные задачи с 
помощью компьютера. Изложены основные понятия теории конечных 
автоматов.

Предназначено для студентов высших учебных заведений, обучающих
ся по направлениям подготовки «Телекоммуникации», «Информационные 
системы», «Информатика и вычислительная техника».

УДК 519.1(075.8)
ББК 22.176я73

ISBN 978-5-369-00205-6 (РИОР)
ISBN 978-5-16-103320-3 (ИНФРА-М, online) 
© Куликов В.В.

К90

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 4 ст. 11



Глава  1. Элементы математической  
 
лоГики

1.1.  
Логика высказываний

Логика — это фундамент, на котором построено все здание математики [2]. По сути, логика — это наука о рассуждениях, 
которая позволяет определить  и с т и н н о с т ь  или  л о ж н о с т ь 
того или иного математического утверждения, исходя из совокупности первичных предположений, называемых аксиомами. Логика 
применяется также в информатике для построения компьютерных 
программ и доказательства их корректности. Понятия, методы и 
средства логики лежат в основе современных информационных 
технологий. Рассмотрим основы математической логики.

Высказывание — это утверждение или повествовательное предложение, о котором можно сказать, истинно оно или ложно. 
Иными словами, утверждение об истинности или ложности высказывания должно иметь смысл. Будем обозначать высказывания буквами латинского алфавита  р, q, r, ... . Например,  р  может 
обозначать утверждение «Завтра будет дождь», а  q — утверждение «Квадрат целого числа есть число положительное».

Истинность или ложность, приписываемые некоторому утверждению, называются его значением истинности или истинностным 
значением. Значение истинности может обозначаться либо латинскими буквами Т (true) и F ( false) [2], либо русскими буквами И
(истина) и Л (ложь) [1], либо цифрами 1 и 0 [7].

Предложения, представляющие вопрос (Кто вы?), приказ или 

восклицание (Прочтите эту главу до следующего занятия) либо 
внутренне противоречивое утверждение (Это утверждение ложно),
не являются высказываниями.

В обыденной речи для образования сложного предложения из 

простых используются связки — особые части речи, соединяющие 
отдельные предложения. Высказывание, не содержащее связок, 
называется простым, а высказывание, содержащее связки, — 
сложным. Наиболее часто употребляются связки и, или, нет, если... 
то, только если и тогда и только тогда. В отличие от обыденной 
речи, в логике смысл таких связок должен быть определен однозначно. Истинность сложного высказывания однозначно определяется истинностью или ложностью составляющих его частей. 



Если связка применяется только к  о д н о м у  высказыванию, то ее 
называют унарной. Если связка применяется к  д в у м  высказываниям, то ее называют бинарной.

Любое сложное высказывание, содержащее связки, представляет собой логическую функцию, которую можно отразить таблицей истинности. Таблица истинности перечисляет все возможные 
комбинации истинности и ложности сложного высказывания. 

Поскольку для  у н а р н о й  связки используется только один 

аргумент, он может принимать два различных значения (Т или F ), 
а для каждого из двух значений аргумента может быть два значения истинности сложного высказывания (Т или F ), следовательно, для унарной операции возможны четыре вида связок. Они 
представлены в табл. 1.1. 

Т а б л и ц а   1.1 

Случай
р
∼р
T
F
p

1
2
3
4
5
6

1
T
F
T
F
T

2
F
T
T
F
F

Для каждой унарной связки столбцы 1 и 2 в табл. 1.1 являются 

общими. Совокупность общих столбцов и столбца для соответствующего вида связки представляет таблицу истинности конкретной связки. Столбец 2 является аргументом. Столбцы 3–6 
характеризуют различные логические функции (связки). Одна из 
них называется опровержением или отрицанием высказывания р
(столбец 3 табл. 1.1), обозначается символом «∼» перед высказыванием (∼р) [2] или чертой сверху (р–) [1], а иногда символом «¬» 
перед высказыванием (¬р) или символом «′» после него (p′).

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

Высказывание, истинное во всех случаях (независимо от аргумента), называется логически истинным или тавтологией (столбец 4 табл. 1.1); высказывание, построенное так, что оно ложно в 
каждом случае (независимо от аргумента), называется логически 
ложным или противоречием (столбец 5 табл. 1.1). Четвертый случай (столбец 6 табл. 1.1) соответствует значению функции, которая повторяет значения аргумента.



У  б и н а р н ы х  связок возможны четыре случая, которые необходимо рассмотреть. Высказывание р может быть истинным 
(Т ) или ложным (F ) и независимо от того, какое истинностное 
значение принимает р, высказывание q может также быть истинным (Т ) или ложным (F ). Для каждого случая значение связки 
может быть либо истинным (Т ), либо ложным (F ). Таким образом, возможное число связок составляет 42 = 16. Только 10 из них 
имеют названия и условные обозначения.

К бинарным связкам относят конъюнкцию (∧), дизъюнкцию (∨), 

исключающее или (∨), импликацию (→), эквиваленцию (↔), а также 
связанные с импликацией конверсию, инверсию и контрапозицию. 
Кроме того, две связки носят имена ученых: так называемые 
штрих Шеффера () и стрелка Пирса (↓). Истинностные значения 
этих связок показаны в табл. 1.2, в которой столбцы 2, 3 являются 
аргументами.

Т а б л и ц а   1.2

Случай
р
q
p ∧ q
p ∨ q
p∨q
p → q
q → p
p ↔ q
pq
p ↓ q

1
2
3
4
5
6
7
8
9
1 0
1 1

1
T
T
T
T
F
T
T
T
F
F

2
T
F
F
T
T
F
T
F
T
F

3
F
T
F
T
T
T
F
F
T
F

4
F
F
F
F
F
T
T
T
T
T

В конъюнкции (conjunctio — лат. союз, связь) высказываний  р  и  q

(обозначается  р ∧ q) символ «∧» соответствует союзу  и на языке 
символических выражений. Высказывание  р ∧ q  истинно (столбец 4 табл. 1.2), когда истинны оба простых высказывания. Иногда 
для обозначения конъюнкции используют символ «&» (р&q) [8].

В дизъюнкции (disjunctio — лат. различие) высказываний  р и q 

(обозначается  р ∨ q) символ «∨» соответствует союзу  или.  Для того 
чтобы всё высказывание было истинным, достаточно, чтобы хотя 
бы одна из двух составляющих его компонент была истинной (столбец 5 табл. 1.2). Высказывание  р ∨ q  ложно только в случае 4, когда 
р  и  q  оба ложны.

Еще одна бинарная связка — исключающее или, обозначаемое 

«∨» (столбец 6 табл. 1.2). Когда говорят, что р и q либо истинно, 
либо ложно, то предполагают, что это не выполняется одновременно. В логике исключающее или используется довольно редко.



Символ «→» называется импликацией (implico — лат. тесно 

связаны) высказываний р и q или условной связкой, обозначается 
p → q (столбец 7 табл. 1.2). Иногда импликацию обозначают символом  «⊂»  (p  ⊂  q) [7]. В переводе на символический язык импликация может выражаться в виде различных языковых конструкций (обозначать фразу):

если р, то q;
р достаточно для q;
р является достаточным условием для q;
q необходимо для р;
q является необходимым условием для р;
р, только если q (или: только если q, то р).
Может показаться, что  p → q  носит характер причинно­следственной связи, но это не является необходимым. Нужно помнить, 
что истинность или ложность бинарного сложного высказывания 
зависит только от истинности составляющих его частей и не зависит от наличия или отсутствия между ними какой­либо связи. 
Важен не порядок, в котором  р  и  q  присутствуют во фразе, а то, 
какая часть предложения является частью «если», а какая частью 
«то». При замене «если  р, то  q»  на  «q,  если р» с логической точки 
зрения последнее высказывание совпадает с исходным.

С условным высказыванием — импликацией  p → q  связаны 

еще три типа высказываний: конверсия, инверсия и контрапозиция
высказывания  p → q. Они определяются следующим образом:

p → q — импликация высказываний р и q;
q → p — конверсия высказывания p → q;
∼p → ∼q — инверсия высказывания p → q;
∼q → ∼p — контрапозиция высказывания p → q.
Истинность конверсии показана в столбце 8 табл. 1.2. Таблица 

истинности инверсии совпадает с конверсией, а контрапозиции — 
с импликацией. В то же время импликация и ее инверсия имеют 
различные таблицы истинности. Непонимание этого факта — 
источник распространенных ошибок.

Высказывание вида  (p → q) ∧ (q → p)  обозначается p ↔ q.  Символ «↔» [2] называется эквиваленцией высказываний р и q. В некоторых источниках используются другие символы [1, 7]. Очевидно, 
что таблица истинности для  (p → q) ∧ (q → p)  определяет таблицу 
истинности для p ↔ q (столбец 9 табл. 1.2). Непосредственно из 
определения вытекает, что эквиваленция истинна только в случае, когда  р  и  q  имеют одинаковые истинностные значения.



Следующие языковые конструкции, выражающие эквиваленцию высказываний  р ↔ q, равносильны:

p тогда и только тогда, когда q;
p необходимо и достаточно для q;
р есть необходимое и достаточное условие для q.
Штрих Шеффера (столбец 10 табл. 1.2) имеет значение истинности, противоположное операции конъюнкции, в связи с чем эту 
связку можно определить как двойную не-и. Стрелка Пирса (столбец 11 табл. 1.2) имеет значение истинности, противоположное 
операции дизъюнкции, в связи с чем эту связку можно определить 
как двойную не-или.

Приведем примеры сложных высказываний. Для этого обозначим:

р: Петров водит автомобиль;
q: У Смирнова русые волосы.
Сложное высказывание «Петров водит автомобиль и у Смирнова 

русые волосы» может быть символически записано в виде  р ∧ q.

Рассмотрим выражение  р  ∧  q.  Если некто говорит: «Петров 

водит автомобиль, и у Смирнова русые волосы», то мы, естественно, представляем себе Петрова за рулем автомобиля и русоволосого Смирнова. В любой другой ситуации (например, если 
Смирнов не русоволос или Петров не водит автомобиль) мы скажем, что говорящий не прав.

Точно так же высказывание «Петров водит автомобиль или

у Смирнова русые волосы» символически выражается как   р ∨ q.

Примером, который подтверждает таблицу истинности для 

импликации (см. столбец 7 табл. 1.2), является высказывание 
«Если целое число равно 3, то его квадрат равен 9».

Конечно, желательно, чтобы это высказывание было истинным всегда. Пусть р — высказывание «Целое число равно 3», а  q — 
высказывание «Квадрат целого числа равен 9». Если р и q истинны, 
то целое число равно 3 и его квадрат равен 9. Это соответствует 
первой строке таблицы истинности. Если целое число равно -3, 
то его квадрат по­прежнему равен 9. В этом случае  р  ложно и  q 
истинно, что совпадает со случаем 3 и подтверждает правильность третьей строки таблицы. Если целое число равно 4, то ложны и  р и q, что соответствует случаю 4. Этим подтверждается 
правильность четвертой строки таблицы. Заметим, что случай 2 
здесь не имеет места, но во всех других случаях эта таблица истинности обеспечила нам желаемый результат.



Может возникнуть вопрос, как интерпретировать выражения, 

в которых отсутствуют скобки. Во избежание неоднозначности 
лучше всегда использовать скобки. Однако здесь, как и в алгебре, 
имеется следующий порядок выполнения операций:  ∼; ∧ , ∨ ; →;  ↔. 
Поэтому такие выражения, как  ∼р ∨ q, р ∧ q ∨ r, р ∧ q → r  и
р ∧ q ↔ q → r, можно интерпретировать как  (∼р) ∨ q, (р ∧ q) ∨ r,
(р ∧ q) → r   и  (р ∧ q) ↔ (q → r).

Рассмотрим пример построения таблицы истинности сложного 

высказывания, состоящего из трех простых (функция от трех аргументов): «Попов уплатит налог за машину или Попов останется 
без машины и будет ходить на работу пешком». Пусть р обозначает 
высказывание «Попов уплатит налог за машину», q — высказывание «Попов останется при своей машине», а  r — высказывание 
«Попов будет ходить на работу пешком». Тогда наше сложное высказывание можно представить в виде  р ∨ ((∼q) ∧ r),  где скобки 
использованы, чтобы показать, какие именно высказывания являются компонентами каждой связки.

Таблица истинности дает возможность однозначно указать те 

ситуации, когда высказывание является истинным; при этом необходимо быть уверенным, что учтены все случаи. Поскольку 
сложное высказывание содержит три основных высказывания  р,
q  и  r,  то возможны восемь случаев (табл. 1.3).

Т а б л и ц а   1.3

Случай
р
q
r
∼q
(∼q) ∧ r
р ∨ ((∼q) ∧ r)

1
2
3
4
5
6
7

1
T
T
T
F
F
T

2
T
T
F
F
F
T

3
T
F
T
T
T
T

4
T
F
F
T
F
T

5
F
T
T
F
F
F

6
F
T
F
F
F
F

7
F
F
T
T
T
T

8
F
F
F
T
F
F

При нахождении значений истинности для столбца  (∼q) ∧ r

используем столбцы для  (∼q)  и  r,  а также таблицу истинности 
для ∧ .  Таблица истинности для  ∧   (см. столбец 4 табл. 1.2) показывает, что высказывание  (∼q) ∧  r  истинно лишь в том случае, 
когда истинны оба высказывания  (∼q)  и  r.  Это имеет место лишь 
в случаях 3 и 7 (см. табл. 1.3).



Заметим, что при определении значений истинности для

столбца  р ∨ ((∼q) ∧ r) играет роль только истинность высказываний  р и (∼q) ∧ r.  Таблица истинности для  ∨   (см. столбец 5 
табл. 1.2) показывает, что единственный случай, когда высказывание, образованное с помощью связки или, ложно, — это случай, 
когда ложны обе части этого высказывания. Такая ситуация имеет
место только в случаях 5, 6 и 8 (см. табл. 1.3). Если Попов не уплатит 
налог за машину (т.е. р ложно, или имеет значение F ), останется без 
машины (q  имеет значение F ) и будет ходить на работу пешком 
(r  имеет значение F ), то будет иметь место случай 7. Тот, кто скажет: «Попов уплатит налог за машину или Попов останется без машины и будет ходить на работу пешком», будет абсолютно прав.

Другой, эквивалентный способ построения таблицы истинности

состоит в том, чтобы записывать истинностные значения выражения под связкой. Снова рассмотрим выражение  р ∨ ((∼q) ∧ r). 
Сначала записываем истинностные значения под переменными 
р,  q  и  r  (табл. 1.4).  Единицы под столбцами истинностных значений (см. строку «Очередность действий» в табл. 1.4) указывают 
на то, что этим столбцам истинностные значения присваиваются 
в первую очередь. В общем случае число под столбцом будет показывать номер шага, на котором выполняются вычисления соответствующих истинностных значений.

Затем мы записываем под символом «∼» (столбец 7) истинностные значения высказывания  ∼q.  Далее записываем истинностные 
значения ∼q ∧ r под символом «∧» (столбец 9). Наконец записываем 
значения высказывания р ∨ ((∼q) ∧ r) под символом «∨» (столбец 6).

Т а б л и ц а   1.4

Случай
р
q
r
p
∨ 
((∼
q)
∧ 
r)

1
2
3
4
5
6
7
8
9
1 0

1
T
T
T
T
T
F
T
F
T

2
T
T
F
T
T
F
T
F
F

3
T
F
T
T
T
T
F
T
T

4
T
F
F
T
T
T
F
F
F

5
F
T
T
F
F
F
T
F
T

6
F
T
F
F
F
F
T
F
F

7
F
F
T
F
T
T
F
T
T

8
F
F
F
F
F
T
F
F
F

Очередность действий
1
4
2
1
3
1

1.2.  
ЭквиваЛентность высказываний

Особый интерес представляют сложные высказывания, 

имеющие различное строение, но являющиеся истинными в одних 
и тех же случаях. Такие высказывания называются логически эквивалентными. Эквивалентность обозначается символом «≡» [2]. 
Используются и другие символы, например «=». Эквивалентность 
двух высказываний легко установить, сравнивая их таблицы истинности.

Пример. Пусть  р  и  q  обозначают следующие высказывания:
р: Сегодня шел дождь;
q: Сегодня шел снег.
Рассмотрим сложные высказывания: «Неверно, что сегодня шел 

дождь или снег», или символически ∼(р ∨ q), и «Сегодня не шел 
дождь и сегодня не шел снег», или символически  ∼р  ∧ ∼q.

Построим таблицы истинности для обоих высказываний 

(табл. 1.5).

Т а б л и ц а   1.5

Случай
р
q
∼
(p
∨ 
q)
(∼
p)
∧ 
(∼
q)

1
2
3
4
5
6
7
8
9
1 0
1 1
1 2

1
T
T
F
T
T
T
F
T
F
F
T

2
T
F
F
T
T
F
F
T
F
T
F

3
F
T
F
F
T
T
T
F
F
F
T

4
F
F
T
F
F
F
T
F
T
T
F

Номер шага
3
1
2
1
2
1
3
2
1

Итак, во всех четырех строках истинностные значения для 

∼(р ∨ q) (действие 3, столбец 4) и для  ∼р ∧ ∼q (действие 3, столбец 10) совпадают. Это означает, что два рассматриваемых высказывания логически эквивалентны, т.е.  ∼(р ∨ q)  ≡  ∼р ∧ ∼q.   p

Используя это свойство, можно строить отрицание высказываний с «или», осуществляя отрицание каждой из его частей и меняя 
«или» на «и».

С помощью таблиц истинности можно доказать следующие 

логические эквивалентности:
Законы идемпотентности:   
р ∨ p ≡ p; 
р ∧ p ≡ p.

Закон двойного отрицания:   
∼(∼р) ≡ p.