2014-02-12
397
Вступление........................................................................................ 4
1 Элементы теории множеств и отношений............................. 5
1.1 Условные обозначения, принятые в тексте.................................... 5
1.2 Множества. Способы задания множеств...................................... 5
1.3 Операции над множествами....................................................... 7
1.4 Действия с цепочками............................................................... 10
1.5 Число элементов множества...................................................... 11
1.6 Отношения................................................................................ 12
1.7 Свойства бинарных отношений.................................................. 13
1.8 Операции с бинарными отношениями........................................ 14
1.9 Упражнения и задачи к главе 1................................................... 16
2 Элементы алгебры логики........................................................ 18
2.1 Простые высказывания; логические связки................................. 18
2.2 Составные высказывания. Таблицы истинности......................... 19
2.3 Логические законы.................................................................... 21
2.4 Построение заданных составных высказываний......................... 22
2.5 Отношения между высказываниями.......................................... 23
2.6 Аргументы.................................................................................. 24
2.7 Задачи на построение таблиц истинности.................................. 24
3 Элементы теории графов........................................................... 25
3.1 Общие понятия и определения................................................... 25
3.2 Способы задания графов............................................................ 25
3.3 Элементы графов........................................................................ 26
3.4 Операции с частями графа.......................................................... 27
3.5 Диаметр, радиус и центр графа.................................................... 28
3.6 Диаметр протяженности, радиус протяженности и центр протяженности графа 30
3.7 Задачи к главе 3......................................................................... 32
4 Теория конечных автоматов.................................................... 33
4.1 Конечные автоматы – распознаватели....................................... 33
4.2 Эквивалентные состояния КА..................................................... 35
4.3 Недостижимые состояния КА..................................................... 36
4.4 Недетерминированный конечный автомат................................. 37
4.5 Задачи к главе 4......................................................................... 41
5 Автоматы с магазинной памятью......................................... 43
5.1 Автоматы-распознаватели с магазинной памятью..................... 43
5.2 Автоматы-трансляторы с магазинной памятью.......................... 48
5.3 Задачи к главе 5......................................................................... 51
6 Грамматики................................................................................. 53
6.1 Общие сведения......................................................................... 53
6.2 Классификация грамматик......................................................... 56
6.3 Эквивалентные преобразования грамматик................................ 57
6.3 1 Удаление или добавление бесполезных........................... 58
(непродуктивных и недостижимых) нетерминалов.................. 58
6.3.2 Добавление нетерминала................................................. 60
6.3.3 Подстановка правил.......................................................... 60
6.3.4 Изменение направления рекурсии................................... 60
6.4 Задачи к главе 6......................................................................... 61
7 Распознаватели для грамматик............................................. 62
7.1 Построение КА–распознавателей для автоматныхграмматик...... 62
7.2 Построение КА–распознавателей для праволинейных
грамматик................................................................................. 66
7.3 Построение МП–распознавателей для S – грамматик................. 67
7.4 Построение МП–распознавателей для q – грамматик................. 71
7.5 Задачи к главе 7......................................................................... 77
С п и с о к л и т е р а т у р ы........................................................... 78
Вступление
Любой природный процесс, которым человек пытается управлять(воздействовать на него с предсказуемыми последствиями), должен быть сначала представлен в виде модели той или иной степени сложности. Специалистам в области компьютерных технологий приходится брать такие модели или их фрагменты для последующего объединения из конкретных предметных областей, общих знаний и представлений об окружающем мире и создавать свою модель для решения поставленной задачи. После этого, учитывая особенности работы вычислительного устройства(компьютера) и выбранного языка программирования – разрабатывать алгоритм реализации модели, программировать(кодировать) этот алгоритм. Кроме реализации основной функции, необходимо подумать о вспомогательных функциях(контроль входных данных, проверка адекватности результата, представление результата, контекстная подсказка, справочная система и т.п.) и их корректном взаимодействии между собой.
Все перечисленные процессы (как, по глубокому убеждению автора, и большинство природных процессов в восприятии человека) имеют дискретную природу (дискретный (лат. diskretus) – разделенный, прерывистый).
Представление и процесс обработки информации в компьютере, независимо от его технических параметров, носят дискретный характер (алфавит машинного языка двухсимвольный, множество состояний процессора конечное), поэтому любая модель, реализованная в виде машинного кода, дискретна.
Курс лекций ставит своей целью познакомить студента с максимально широким кругом понятий дискретной математики, приобрести навыки в создании и программировании дискретных объектов при решении практических задач, причем для успешного освоения курса достаточно школьных знаний по математике. Дискретная математика – фундаментальная наука и нужна специалисту в области информационных технологий как метод мышления, как средство формулирования и организации понятий.
В конце курса приведен список литературы, в которой можно найти более подробное изложение этих и других разделов дискретной математики.
1 Элементы теории множеств и отношений
1.1 Условные обозначения, принятые в тексте
N – множество всех натуральных чисел (N = {1,2,3,...});
Nо – множество всех натуральных чисел и ноль (Nо={0,1,2,3,...});
R – множество действительных чисел;
Î – знак принадлежности (а Î А – элемент а принадлежит множеству А; а Ï В – элемент а Ï множеству В);
Ç – знак пересечения (А Ç В – пересечение множеств А и В);
È – знак объединения (А È В – объединение множеств А и В);
\ - знак разности (А \ В – из множества А вычесть множество В);
Ì – знак включения (В Ì А – множество В включено в множество А);
хn или An – элемент х или множество А в степени n (n Î No);
W – обозначение универсального множества – такого множества, по отношению к которому все рассматриваемые в примере или задаче множества являются подмножествами (A,B,C,D... Ì W).
1.2 Множества. Способы задания множеств
Язык множеств – универсальный язык математики. Любое математическое утверждение можно сформулировать как утверждение о некотором соотношении между множествами: о равенстве двух множеств, о не пустоте некоторого множества, о не принадлежности элементам множества. Понятие "множество" – одно из базовых понятий в математике и не может быть определено через другие понятия. Интуитивно множество можно определить как совокупность предметов, понятий, явлений, множеств,..., объединенных одним или несколькими свойствами. В множестве не может быть одинаковых элементов. Порядок следования элементов в множестве не важен.
Множества, подмножества будем обозначать большими буквами латинского алфавита (A, B, C, D...), а элементы множеств – малыми (a, b, c, d...).
Множество B называется подмножеством A, если любой элемент B является элементом A. Этот факт можно записать следующим образом:
В Ì А.
Множества могут быть конечными (состоять из конечного числа элементов) и бесконечными. Примеры бесконечных множеств – множество натуральных чисел N (N={1,2,3,4...}), множество натуральных чисел с включением нуля No (No={0,1,2,3...}). Примеры конечных множеств будут приведены ниже.
Число элементов в конечном множестве М называется мощностью множества и обозначается | М | или n (M). Множество мощностью 0 т.е. множество, не содержащее элементов, называется пустым и обозначается так: М = { } или М = 0. Принято считать, что пустое множество является подмножеством любого множества, в том числе и пустого.
1 Списком элементов: A = {a, b, c, d}; S = {Иванов, Петров, Сидоров}.
2 Порождающей процедурой:
M = {(x, y)| x2 + y2 = 1} (задана окружность радиуса R=1);
K = {(a,b)|, a Î А и b Î B } (задано произведение двух множеств);
D = A È B = { x |, x Î А или x Î В } (задано объединение двух множеств).
3 Описанием характеристических свойств, которыми должны обладать элементы множества:
· Все студенты ДГМА.
· Футбольная команда “Шахтер”.
· Жители города Краматорска.
1.3 Операции над множествами
1 Объединение множеств
Объединением множеств называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из объединяемых множеств:
A È B = { а | а Î A или а Î B}.
Операция "объединение" n-арная (т.е. применима к n множествам), коммутативная (при перестановке объединяемых множеств результат выполнения операции не изменится).
: A = {a, ab, ac, c}; B = {ac, ba, b, c}; C = {b, f};
D = A È B È C = C È B È A = {a, ab, ac, c, ba, b, f}.
2 Пересечение множеств
Пересечением множеств называется множество, состоящее из всех элементов, принадлежащих одновременно каждому из объединяемых множеств:
A Ç B = { a | aÎ A и a Ï B }.
Операция "пересечение" n-арная (т.е. применима к n множествам), коммутативная (при перестановке пересекаемых множеств результат выполнения операции не изменится).
A = {a, b, c, f}; B = {b, c, n}; C = {d, f, n};
D = A Ç B = {b,c}; B Ç C = { n };
Е = A Ç B Ç C = B Ç C Ç A = { }.
3 Разность множеств
Разностью двух множеств называется множество, состоящее из всех элементов, принадлежащих первому множеству и не принадлежащих второму множеству:
A \ B = { а | а Î A и а Ï В }.
Операция "разность" бинарная (т.е. применима к двум множествам), некоммутативная (при перестановке вычитаемых множеств результат изменяется):
A \ B ¹ B \ A.
Пример: A = {a, c, d, e, f}; B = {a, d, m};
D = A \ B = {c, e, f}; C = B \ A = { m }.
4 Дополнение множеств
Дополнением множества А (до универсального множества W 
) называется множество, состоящее из всех элементов множества W, которые не входят в множество А:
__
А = { a | a Î W и Ï A }.
Операция "дополнение" унарная (т.е. применима к одному множеству или части формулы, которую можно трактовать как одно множество). Операцию "разность" в формулах можно заменить:
__
A \ B = A Ç B.
Пример:
W = {a, c, d, e, f, k}; B = {c, e, f}; A = {a, c};
__ __
В È B = W; В Ç B = { } (пусто);
__
D = A \ B = A Ç B = { c }.
Используя множества, операции 1 – 4 и скобки, которые меняют порядок выполнения операций, можно составлять формулы. Наибольший приоритет при выполнении имеет операция "дополнение", затем "разность" после этого две операции одного приоритета – "объединение" и" пересечение"; операции одного приоритета выполняются в формуле по порядку слева направо; если в формуле есть скобки, то сначала выполняются операции в скобках в соответствии с их приоритетом; если знак дополнения стоит над частью формулы, то считают, что та часть взята в скобки (хотя скобки на самом деле могут отсутствовать). В задачах контрольных работ в формулах используются только три подмножества: А, В, С или P, Q, R универсального множества W.
Очень удобным является наглядное представление таких формул с помощью диаграмм Венна. Диаграмма в общем виде – это прямоугольник, представляющий универсальное множество W с тремя пересекающимися окружностями внутри; область, заключенная в каждой окружности, представляет соответственно множества А, В, С. В результате таких построений площадь прямоугольника разбивается (в самом общем случае) на восемь связных областей, каждая из которых или произвольная их комбинация может быть описана бесконечным множеством формул. Одним из способов упрощения формул при выполнении упражнений и задач контрольных работ является последовательное построение диаграмм Венна, соответствующих выполнению каждой операции в формуле, с целью определения того набора областей, которым соответствует формула, а затем их описания более простой формулой, если это возможно.
5 Прямое произведение множеств
Прямым или декартовым произведением множеств называется множество, элементами которого являются векторы, составленные из элементов перемножаемых множеств: первые компоненты векторов – элементы первого множества, вторые – второго и т.д. Для двух множеств процедура имеет вид:
A ´ В = {(а,b) | a Î A и b Î B}.
A = {a,b,c,.....,h}; B = {1, 2, 3,....., 8};
D = A ´ B = {(a,1); (a,2); (a,3);... (h,8)}.
Допускается запись D = A ´ B = {a1; a2; a3;... h8}.
Вектор – упорядоченный набор элементов. Элементы, образующие вектор называются координатами или компонентами вектора. Число координат называется длиной или размерностью вектора. В отличие от элементов множества координаты вектора могут быть одинаковыми.
Пример: B = (0,3,5,3) – вектор размерности 4;
С = (0,3,3,5) – вектор размерности 4.
Векторы В и С различны, т.к. порядок следования координат разный.
Операция 5 многоместна (перемножать можно несколько множеств) и некоммутативная. В качестве сомножителей может выступать одно и то же множество, т.е. множество можно возводить в n –ю степень.
В качестве примера рассмотрим случай, когда элементами множества являются символы, например: V = {a, b, c }. Такое множество будем называть алфавитом. При возведении этого множества в квадрат получим новое множество, состоящее из двухсимвольных цепочек или слов (элементы – векторы записываются без скобок и разделяющих запятых) V2 = V ´ V = {aa, ab, ac, ba,..., cc }. При возведении алфавита в куб (последнее множество умножаем на V) получаем трехсимвольные слова–цепочки и т.д. Алфавит в нулевой степени представляет собой множество, состоящее из одного элемента – пустой цепочки (обозначение e – эпсилон): V0 = { e }.
Длина цепочки равна количеству элементов, образующих эту цепочку. Пустую цепочку e можно вставить в любое место других цепочек, не изменяя их:
| а |= 1; | aba | = 3; | abea | = 3; | e | = 0.
1.4 Действия с цепочками
Для цепочек допустимы следующие действия:
· конкатенация (сцепление) цепочек:
x = aba, y = cab; xy = abacab;
· возведение цепочек в степень:
x = ab; x1 = ab; x2 = abab; x3 = (ab)3 = ababab;
любая цепочка в нулевой степени равна e: x0 = e
Нельзя отождествлять пустое множество C = { } и множество, содержащее один элемент - пустую цепочку В = { e }.
Все множество цепочек, которые могут быть созданы в заданном алфавите, можно представить таким понятием как, итерация алфавита.
Итерация – множество, полученное в результате объединения всех степеней алфавита, включая и нулевую:
V* = È Vi.
(i Î N0)
Усеченная итерация (обозначается V+) не включает нулевую степень алфавита т.е. пустую цепочку:
V+ = È Vi.
(iÎ N)
Итерацию и усеченную итерацию связывает следующая формула:
V+=V ´ V* = V* ´ V.
1.5 Число элементов множества
Для любого конечного множества М число элементов (мощность множества) будем обозначать n (M).
Пусть задано несколько множеств (подмножеств одного универсального множества W): А,В,С,... с числом элементов в каждом соответственно: n (A), n (B), n (C),.... Решим задачу о количестве элементов в множестве, записанном в виде формулы, т.е. состоящем из нескольких множеств, связанных операциями пересечения, объединения и дополнения.
Дано: A, B, n (A), n (B).
Определить: число элементов в объединении n (A È B).
