ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 15257
Скачиваний: 187
6
Ответы ........................................................................................................... 217
Предметный указатель .............................................................................. 220
7
Введение
Цель дисциплины «Дискретная математика» состоит в изучении студен-
тами основ математического аппарата, применяемого для решения задач из
сферы цифровых структур, а также из области управления и алгоритмизации
процессов обработки информации дискретного характера.
Главная задача курса: развить логическое, алгоритмическое и комбина-
торное мышление студентов, доведя его до уровня, необходимого для освоения
методов решения задач на дискретных структурах и достаточного для умения
самостоятельно расширять свои математические знания, обеспечивающие
дальнейший рост в профессиональной деятельности.
В пособии изложены следующие темы: теория множеств, комбинаторика,
теория графов, алгебра логики и теория конечных автоматов. Все они отлича-
ются выраженной прикладной значимостью. Подбор материала пособия осу-
ществлялся в пределах требований ФГОС и рабочих программ таких направле-
ний, как 11.03.01, 11.03.02, и др.
Изучив дисциплину, студент получит четкое представление о содержании
основных понятий, характерных для прикладной дискретной математики, осво-
ит методы решения задач из таких областей, как минимизация логических фор-
мул, дифференцирование и интегрирование булевых функций, синтез комбина-
ционных и многотактных устройств дискретного действия (автоматов с
памятью). Кроме того, учащийся ознакомится с комбинаторными конфигура-
циями, представлением задач в виде граф-схем и решением их методами теории
графов.
Первым четырём темам, т. е. теории множеств, комбинаторике, теории
графов и алгебре логики, отведено пять первых глав. Среди них отдельной гла-
вой, ввиду её особо важного прикладного значения, представлена тема миними-
зации булевых формул в дизъюнктивных и конъюнктивных формах с учётом
неопределённых состояний. Здесь же некоторое внимание уделено алгебре Же-
галкина, симметрическим функциям и вопросам дифференцирования булевых
функций. Остальные главы относятся к теории конечных автоматов. В них
освещены вопросы практического применения булевой алгебры на примере
комбинационных электронных схем, контактных структур и автоматов с памя-
тью (многотактные триггерные схемы).
8
Большинство параграфов содержат задачи и упражнения для самостоя-
тельной работы. Всего их 380. Для самоконтроля принята система открытых
ответов, они помещены в конце пособия. Большей частью задачи и упражнения
просты, лишь некоторые из них отличаются повышенной сложностью.
В данном пособии представлена вся та информация, которую студент
должен освоить при изучении курса дискретной математики. Сведения о том,
как выполнять контрольные задания, представлены в методических указаниях,
являющихся приложением к данной книге. В них содержатся образцы выпол-
нения контрольных заданий, которые помогут подготовиться к решению ком-
пьютерной контрольной работы.
Соглашения, принятые в учебном пособии
Для улучшения восприятия материала в данном учебном пособии исполь-
зуются пиктограммы и специальное выделение важной информации.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Эта пиктограмма означает определение или новое понятие.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Эта пиктограмма означает задание. Здесь автор может дать
указания для выполнения самостоятельной работы или упражнений,
сослаться на дополнительные материалы.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
В блоке «На заметку» автор может указать дополнительные
сведения или другой взгляд на изучаемый предмет, чтобы помочь
читателю лучше понять основные идеи.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Эта пиктограмма означает теорему.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · ·
Пример
· · · · · · · · · · · · · · · · · · · · · · · · · ·
Эта пиктограмма означает пример. В данном блоке автор может привести
практический пример для пояснения и разбора основных моментов, отражен-
ных в теоретическом материале.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
9
1 Элементы теории множеств
1.1 Понятие множества
Содержание понятия множества ясно интуитивно. У него нет точной
формулировки. Например, Ф. А. Новиков пишет: «Понятие множества принад-
лежит к числу фундаментальных неопределяемых понятий математики. Можно
сказать, что множество – это любая определенная совокупность объектов» [35,
с. 20]. Эти объекты в теории множеств называются элементами.
При аналитической записи множеств их элементы принято отделять один
от другого запятыми. При этом всю последовательность элементов и запятых
заключают в фигурные скобки. Например:
{
}
, , ,
.
P
a b c d
=
(1.1)
Читается данное выражение следующим образом: «множество P состоит
из четырех элементов вида , , ,
a b c d
».
Из выражения (1.1) видно, что a является элементом множества P . Ко-
ротко это записывается в виде формулы:
,
a
P
∈
(1.2)
где знак
∈
обозначает принадлежность элемента множеству.
Читается запись (1.2) так: « a есть элемент множества P », либо – «эле-
мент a принадлежит множеству P », либо – « a является элементом множе-
ства P ». Если требуется указать, что множеству P принадлежит элемент b, то
пишут аналогично: b P
∈ . Точно так же записывается утверждение о принад-
лежности множеству P элементов c и d : c P
∈ ; d P
∈ .
Подобным образом указывается принадлежность множеству нескольких
элементов. Например, согласно (1.1):
, ,
.
a c d
P
∈
Читается: «множеству P принадлежат элементы a , c и d », либо – « a , c
и d являются элементами множества P ».
Если требуется указать, что те или иные элементы не принадлежат задан-
ному множеству P , то применяется знак ∉. Например, среди всех элементов
множества P , как показано в формуле (1.1), нет буквы m . Коротко это записы-
вается следующим образом:
.
m P
∉
Читается: «элемент m не принадлежит множеству P ».
10
Нет в множестве P и таких элементов, как k и n . Это записывается так:
,
.
k n
P
∉
Читается: «элементы k и n не принадлежат множеству P ».
Множества делятся на конечные и бесконечные. В конечном множестве
содержится конечное число элементов, в бесконечном – бесконечное. Приме-
ром бесконечного множества является множество целых чисел.
Множество, содержащее точно один элемент, называется синглетоном
(от английского single – одиночный), например:
{ }
{ }
{ }
{ }
{
}
1
2
3
4
5
10 ,
1 ,
,
00 ,
.
P
P
P
P
P
ddd
=
=
= =
=
=
Множество называется пустым, если в нём нет ни одного элемента. Пу-
стое множество обозначается знаком
∅ . Необходимо различать записи
{ }
1
2
и
.
B
B
= ∅
= ∅
Здесь
1
B
– пустое множество, в нем нет элементов, а множество
B
2
со-
держит один элемент, указанный в фигурных скобках.
Задают множества двумя основными способами [14, с. 5]:
а) прямым перечислением элементов (как показано выше), при этом
по-
рядок записи элементов значения не имеет
. Например, множество (1.1) можно
записать многими способами:
{
} {
} {
} {
}
, , ,
, , ,
, , ,
, , ,
=
=
=
=
P
a b c d
b a c d
c d b a
d c a b
и т. д., всего 24 варианта;
б) описанием свойств элементов на основе правила, при помощи которого
однозначно можно установить, является данный объект элементом заданного
множества или не является (согласно [33, c. 6], в этом заключается интуитив-
ный принцип абстракции):
( )
{
}
|
,
=
A
x P x
где x – переменная, она может принимать любые значения,
( )
P x
– правило,
указывающее, какие значения x принадлежат множеству
A
, например:
{
}
| 0
7
целое число ,
=
≤ ≤ ∧ −
A
x
x
x
где справа от вертикальной черты указано правило
( )
P x
. Читается запись так:
«множество
A
образуют все те значения x , которые больше нуля или равны
ему, но не превышают 7 и являются целыми числами». Знак
∧
обозначает со-
юз И. Вместо него можно ставить точку, букву «и», а также знак
& (ампер-
санд).