Множества.Отношения.

Оглавление ТЕМА 1 МНОЖЕСТВА ................................................................................. 2 1.1Основные понятия ................................................................................... 2 1.2. Операции над множествами.................................................................. 4 1.3. Геометрическое моделирование множеств. Диаграммы Венна ........ 5 1.4. Алгебра множеств. Основные тождества алгебры множеств ........... 6 ТЕМА 2. ОТНОШЕНИЯ ............................................................................. 9 2.1. Отношения. Основные понятия и определения .................................. 9 2.2. Операции над отношениями ............................................................... 11 2.3. Свойства отношений ........................................................................... 12 ТЕМА 4. БУЛЕВЫ ФУНКЦИИ.................................................................. 15 4.1. Определение булевой функции .............................................................. 15 4.2. Формулы логики булевых функций ....................................................... 16 4.3. Равносильные преобразования формул ................................................. 17 4.4. Двойственность. Принцип двойственности. ........................................ 19 4.5. Булева алгебра . Полные системы булевых функций .......................... 19 4.6. Нормальные формы ................................................................................. 20 4.7 Минимизация формул булевых функций ............................................... 25 Тема 3. ГРАФЫ ............................................................................................... 29 3.1. Основные характеристики графов ..................................................... 29 3.2. Матричные способы задания графов ..................................................... 31 3.3 Основные свойства матриц смежности и инцидентности .................... 32 3.4. Маршруты, циклы в неориентированном графе ................................... 33 3.5. Пути, контуры в ориентированном графе ............................................. 34 3.6 Связность графа ....................................................................................... 34 3.7. Экстремальные пути в нагруженных ориентированных графах ........ 36 3.8 Деревья ....................................................................................................... 37 Краткие сведения о математиках .................................................................. 42 1 ТЕМА 1 МНОЖЕСТВА 1.1Основные понятия Определение 1.1. Множеством называется совокупность каких-либо объектов, обладающим общим для всех характеристическим свойством. Это определение нельзя считать строгим, так как понятие множества является исходным понятием математики и не может быть определено через другие математические объекты. Один из основателей теории множеств Г. Кантор определял множество так: "Множество есть многое, мыслимое как целое". Пример 1.1. Следующие совокупности объектов являются множествами: множество деревьев в лесу, множество целых чисел, множество корней уравнения exsinx = 0.5. Всякое множество состоит из элементов. Множества обозначают большими буквами, например А. В, С, а элементы – маленькими буквами, например, а, b, c. Множество и его элементы обозначаются следующим образом: А = {a1, a2, a3} – множество, состоящее из трех элементов; А = {a1, a2, …} – множество, состоящее из бесконечного числа элементов. Множество может состоять из элементов, которые сами являются множествами. Нужно различать элемент a и множество, состоящее из единственного элемента a. Пример 1.2. Множество А = {1, 2} состоит из двух элементов 1, 2; но множество {А} состоит из одного элемента А. Если элемент a принадлежит множеству А, это записывается следующим образом: a А. Если элемент a не принадлежит множеству А, то записывают так: a А. Пример 1.3. Пусть А1 – множество простых чисел, А2 – множество целых чисел, a = 4. Тогда a А2, a А1. Если все элементы множества А являются элементами множества В и наоборот, т. е. множества А и В совпадают, то говорят, что А = В. Если каждый элемент множества А является элементом множества В, говорят, что множество А является подмножеством множества В, и записывают А В или В А. Отметим, что по определению само множество А является своим подмножеством, т.е. А А. Если А В и В А, то по ранее введенному определению А = В. Если А В и А В, то А есть собственное подмножество В, А В. Если А не является собственным подмножеством В, то записывают А В. 2 Пример 1.4. Пусть А – множество четных чисел, В – множество целых чисел, С – множество нечетных чисел. Тогда А В, С В, А С, В А. Не надо смешивать отношение принадлежности ( ) и отношение включения ( ). Пример 1.5. Пусть А = {2} – множество, состоящее из одного элемента, В = {{2}, {4}} – множество, состоящее из двух элементов, каждое из которых является одноэлементным множеством. Тогда имеют место следующие соотношения: 2 {2}; {2} {{2}, {4}}; 2 {{2}, {4}}. Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается . Принято считать, что пустое множество является подмножеством любого множества, А, где А – любое множество. Таким образом, всякое множество содержит в качестве своих подмножеств пустое множество и само себя. Пример 1.6. Множество корней уравнения sinx = 2 является пустым. Множество всех подмножеств данного множества А называется множествомстепенью и обозначается P(A). Множество P(A) состоит из 2n элементов (доказать самостоятельно). Пример 1.7. Пусть множество А = {1, 2} состоит из двух элементов 1, 2. Тогда множество P(A) включает в себя пустое множество , два одноэлементных множества {1} и {2} и само множество А = {1, 2}, т. е. P(A) = { , {1}, {2}, {1, 2}}. Мы видим, что множество P(A) состоит из четырех элементов (4 = 22). Существуют следующие способы задания множеств. 1. Перечислением элементов множества. Например: A = {1, 3, 5, 7, 9} – конечное множество; B = {1, 2, …, n, …} – бесконечное множество. 2. Указанием свойств элементов множества. Для этого способа пользуются следующим форматом записи: A = {a указание свойства элементов}. Здесь a является элементом множества A, a А. Например: A = {a a – простое число} – множество простых чисел; B = {b b2 – 1 = 0, b – действительное число} – множество, состоящее из двух элементов, B = {– 1, 1}; sin x Z = {x = 1}– множество, состоящее из одного числа, x = 0. x 3 1.2. Операции над множествами Рассмотрим основные операции над множествами. Объединением множеств А и В называется множество А В, все элементы которого являются элементами хотя бы одного из множеств А или В: А В = {x x А или x В}. Из определения следует, что А А В и В А В. Аналогично определяется объединение нескольких множеств Пример 1.8. а) Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда А В = {2, 4, 5, 6}. б) Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А В множество чисел, которые делятся на 2 или на 3: А В = {2, 3, 4, 6, 8, 9, 10, …}. Пересечением множеств А и В называется множество А В, все элементы которого являются элементами обоих множеств А и В: А В = {x x А и x В}. Из определения следует, что А В А, А В В и А В А В. Аналогично определяется пересечение нескольких множеств. Пример 1.9. Рассмотрим данные из примера 1.8. а) Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда А В = {4, 6}. б) Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А В множество чисел, которые делятся и на 2 и на 3: А В = {6, 12, 18, …}. Может оказаться, что множества не имеют ни одного общего элемента. Тогда говорят, что множества не пересекаются или что их пересечение – пустое множество. Пример 1.10. Пусть А = {1, 2}, В = {2, 3}, C = {3, 4}. Тогда А В C = . Относительным дополнением множества В до множества А называется множество А \ В, все элементы которого являются элементами множества А, но не являются элементами множества В: А \ В = {x x А и x В}. 4 Пример 1.11. Рассмотрим данные из примера 1.8. а) А = {4, 5, 6}, В = {2, 4, 6}. А \ В = {4, 5}, В \ А= {2}. б) А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А \ В – множество чисел, которые делятся на 2, но не делятся на 3, а В \ А – множество чисел, которые делятся на 3, но не делятся на 2: А \ В = {2, 4, 8, 10, 14, …}. В \ А= {3, 9, 15, 21, 27, …}. Симметрической разностью множеств А и В называется множество А + В: А + В = (А \ В) (В \ А). Пример 1.12. Рассмотрим данные из примера 1.11. а) А = {4, 5, 6}, В = {2, 4, 6}. А \ В = {4, 5}, В \ А= {2}, А + В = {2, 4, 5}. б) А = {2, 4, 6, …}, В = {3, 6, 9, …}, А \ В = {2, 4, 8, 10, 14, …}. В \ А= {3, 9, 15, 21, 27, …}, А + В = {2, 3, 4, 8, 9, …}. Универсальным множеством называется такое множество U, что все рассматриваемые в данной задаче множества являются его подмножествами. Абсолютным дополнением множества А называется множество A всех таких элементов x U, которые не принадлежат множеству А: A = U \ A. Пример 1.13. Пусть А – множество положительных четных чисел. Тогда U – множество всех натуральных чисел и A - множество положительных нечетных чисел. 1.3. Геометрическое моделирование множеств. Диаграммы Венна Для наглядного представления множеств и отношений между ними используется диаграммы Венна (иногда их называют кругами Эйлера или диаграммами Эйлера – Венна). Универсальное множество изображают в виде прямоугольника, а множества, входящие в универсальное множество, – в виде кругов внутри прямоугольника; элементу множества соответствует точка внутри круга (рис 1.1а)). С помощью диаграмм Венна удобно иллюстрировать операции над множествами. Рис.1.1 5 1.4. Алгебра множеств. Основные тождества алгебры множеств Множества вместе с определенными на них операциями образуют алгебру множеств. Последовательность выполнения операций задается с помощью формулы алгебры множеств. Например, A (В C), (А \ В) + C – формулы алгебры множеств. Для любых множеств A, B, C справедливы следующие тождества: 1. Коммутативность. а) A B B A (для объединения); б) A B = B A (для пересечения). 2. Ассоциативность. а) A (B C) = (A C) C (для объединения); б) A (B C) = (A B) C (для пересечения). 3. Дистрибутивность. а) A (B C) = (A B) (A C) (для объединения относительно пересечения); б) A (B C) = (A B) (A C) (для пересечения относительно объединения). 4. Закон де Моргана. а) A B B (дополнение к объединению есть пересечение A дополнений); б) A B A B (дополнение к пересечению есть объединение дополнений). 5. Идемпотентность. а) A A = A (для объединения); б) A A = A (для пересечения). 6. Поглощение. а) A (A B) = A; б) A (A B) = A. 7. Расщепление (склеивание). а) (A B) (A B ) = A; б) (A B) (A B ) = A. 8. Двойное дополнение. A = A. 9. Закон исключенного третьего. A A = U. 10. Операции с пустым и универсальным множествами. а) A U = U; б) A = A; в) A U = A; г) A = ; д) = U; е) U = . 11. А \ В = A B . 6 Чтобы доказать некоторое тождество A = B, нужно доказать, что, во-первых, если x А, то x В и, во-вторых, если x В, то x А. Докажем таким образом, например, свойство дистрибутивности для объединения (тождество 3а)): A (B C) = (A B) (A C). 1. Сначала предположим, что некоторый элемент x принадлежит левой части тождества, т.е. x A (B C), и докажем, что x принадлежит правой части, т.е. x (A B) (A C). Действительно, пусть x A (B C). Тогда либо x A, либо x B C. Рассмотрим каждую из этих возможностей. Пусть x A. Тогда x A B и x A C (это верно для любых множеств B и C). Следовательно, x (A B) (A C). 2. Предположим, что некоторый элемент x принадлежит правой части тождества, т.е. x (A B) (A C), и докажем, что x принадлежит левой части, т.е. x A (B C) . Действительно, пусть x (A B) (A C). Тогда x A B, и одновременно x A C. Если x A B, то либо x A, либо x B, если .x A C, то либо x A, либо x C. Пусть x A, Тогда x A (B C) и утверждение доказано. Если x A, то одновременно должны выполняться условия x B и x C, т.е. x B C. Но тогда x B C и x A (B C), что также доказывает наше утверждение. Доказательство тождеств можно проиллюстрировать с помощью диаграмм Венна. Основные тождества алгебры множеств можно использовать для доказательства других тождеств. Пример 1.14. Доказать тождество (A B) \ В = A B . Преобразуем левую часть тождества, используя тождество 11: (A B) \ В = (A B) B . Затем используем закон дистрибутивности (тождество 3б): (A B) B = A B B B . Используем закон исключенного третьего (тождество 9): B B= . Получим A B B B=A B . Используем свойство пустого множества (тождество 10б): A B =A B. Тождество доказано. 7 Пример 1.15. Доказать тождество: A \ (В \ C) = (A \ В) (A C). Множества, стоящие в левой и правой частях тождества, изобразим с помощью диаграмм Эйлера – Венна (рис. 1.2). Рис. 1.2 Рис. 1.2б) и рис. 1.2д) иллюстрируют равенство множеств A \ (В \ C) и (A \ В) (A C). Докажем тождество из нашего примера, воспользовавшись тождествами: А\В=A B, A Получим: B= A B , A = A, A (B C) = (A B) (A C). A \ (В \ C) = A ( B \ C ) = A B C = A ( B C ) = A ( B C) = (A B ) (A C) = (A \ В) (A C). Основные тождества алгебры множеств можно также использовать для упрощения формул алгебры логики. Пример 1.16. Упростить выражение: (A B) ( A B) (A B ). Используя закон коммутативности (тождество 1б), поменяем местами вторую и третью скобки: (A B) ( A B) (A B ) = (A B) (A B ) ( A B). Применим закон расщепления (тождество 7а) для первой и второй скобок: (A B) (A B ) ( A B) = A ( A B). Воспользуемся законом дистрибутивности (тождество 3б): A ( A B) = A A A B. Используем закон исключенного третьего (тождество 9): A A= . Получим A A A B= A B. Используем свойство пустого множества (тождество 10б): A B = A B. Итак, (A B) ( A B) (A B ) = A B. 8 ТЕМА 2. ОТНОШЕНИЯ 2.1. Отношения. Основные понятия и определения Определение 2.1. Упорядоченной парой x, y называется совокупность двух элементов x и y, расположенных в определенном порядке. Две упорядоченные пары x, y и u, v равны межу собой тогда и только тогда, когда x = u и y = v. Пример 2.1. a, b , 1, 2 , x, 4 – упорядоченные пары. Аналогично можно рассматривать тройки, четверки, n-ки элементов x1, x2, … xn . Определение 2.2. Прямым (или декартовым) произведением двух множеств A и B называется множество упорядоченных пар, таких, что первый элемент каждой пары принадлежит множеству A, а второй – множеству B: A B = { a, b , a А и b В}. В общем случае прямым произведением n множеств А1, А2,… Аn называется множество А1 А2 … Аn, состоящее из упорядоченных наборов элементов a1, a2, …, an длины n, таких, что i- ый ai принадлежит множеству Аi, ai Аi. Пример 2.2. Пусть А = {1, 2}, В = {2, 3}. Тогда A B = { 1, 2 , 1, 3 , 2, 2 , 2, 3 }. Пример 2.3. Пусть А = {x 0 x 1} и B = {y 2 y 3} Тогда A B = { x, y , 0 x 1 и 2 y 3}. Таким образом, множество A B состоит из точек, лежащих внутри и на границе прямоугольника, образованного прямыми x = 0 (ось ординат), x = 1, y = 2 и y = 3. Французский математик и философ Декарт впервые предложил координатное представление точек плоскости. Это исторически первый пример прямого произведения. Определение 2.3. Бинарным (или двуместным) отношением называется множество упорядоченных пар. Если пара x, y принадлежит , то это записывается следующим образом: x, y или, что то же самое, x y. Пример2.4. = { 1, 1 , 1, 2 , 2, 3 } Аналогично можно определить n-местное отношение как множество упорядоченных n-ок. Так как бинарное отношение – множество, то способы задания бинарного отношения такие же, как и способы задания множества (см. разд. 1.1). Бинарное отношение может быть задано перечислением упорядоченных пар или указанием общего свойства упорядоченных пар. 9 Пример 2.5. 1. = { 1, 2 , 2, 1 , 2, 3 } – отношение задано перечислением упорядоченных пар; 2. = { x, y x+ y = 7, x, y – действительные числа} – отношение задано указанием свойства x+ y = 7. Кроме того, бинарное отношение может быть задано матрицей бинарного отношения. Пусть А = {a1, a2, …, an} – конечное множество. Матрица бинарного отношения C есть квадратная матрица порядка n, элементы которой cij определяются следующим образом: cij = 1, если ai a j , 0 в противном случае. Пример 2.6. А = {1, 2, 3, 4}. Зададим бинарное отношение тремя перечисленными способами. 1. = { 1, 2 , 1, 3 , 1, 4 , 2, 3 , 2, 4 , 3, 4 } – отношение задано перечислением всех упорядоченных пар. 2. = { ai, aj ai < aj; ai, aj А} – отношение задано указанием свойства "меньше" на множестве А . 01 1 1 3. С 0 01 1 – отношение задано матрицей бинарного отношения C. 0 0 0 1 0 0 0 0 Пример 2.7. Рассмотрим некоторые бинарные отношения. 1. Отношения на множестве натуральных чисел. а) отношение выполняется для пар 1, 2 , 5, 5 , но не выполняется для пары 4, 3 ; б) отношение "иметь общий делитель, отличный от единицы" выполняется для пар 3, 6 , 7, 42 , 21, 15 , но не выполняется для пары 3, 28 . 2. Отношения на множестве точек действительной плоскости. а) отношение "находиться на одинаковом расстоянии от точки (0, 0)" выполняется для точек (3, 4) и (–2, 21), но не выполняется для точек (1, 2) и (5, 3); б) отношение "быть симметричным относительно оси OY" выполняется для всех точек (x, y) и (–x, –y). 3. Отношения на множестве людей. а) отношение "жить в одном городе"; б) отношение "учиться в одной группе"; в) отношение "быть старше". Определение 2.4. Областью определения бинарного отношения называется множество D = {x существует y, что x y}. Определение 2.5. Областью значений бинарного отношения называется множество R = {y существует x, что x y}. 10 Определение 2.6. Областью задания бинарного отношения называется множество M = D R . Используя понятие прямого произведения, можно записать: D R Если D = R = A, то говорят, что бинарное отношение задано на множестве A. Пример 2.8. Пусть = { 1, 3 , 3, 3 , 4, 2 }. Тогда D = {1, 3, 4}, R = {3, 2}, M = {1, 2, 3, 4}. 2.2. Операции над отношениями Так как отношения являются множествами, то все операции над множествами справедливы для отношений. Пример 2.9. 1 = { 1, 2 , 2, 3 , 3, 4 }. 2 = { 1, 2 , 1, 3 , 2, 4 }. 1 2 = { 1, 2 , 1, 3 , 2, 3 , 2, 4 , 3, 4 }. 1 2 = { 1, 2 }. 1 \ 2 = { 2, 3 , 3, 4 }. Пример 2.10. Пусть R – множество действительных чисел. Рассмотрим на этом множестве следующие отношения: "; 2 – " = "; 3 – " < "; 4 – " "; 5 – " > ". 1–" Тогда 1= 2 3; 2= 1 4; = \ ; 3 1 2 1= 5; Определим еще две операции над отношениями. Определение 2.7. Отношение называется обратным к отношению (обозначается –1), если –1 = { x, y y, x }. Пример 2.11. = { 1, 2 , 2, 3 , 3, 4 }. –1 = { 2, 1 , 3, 2 , 4, 3 }. Пример 2.12. = { x, y x – y = 2, x, y R}. –1 = { x, y y, x } = –1 = { x, y y – x = 2, x, y R} = { x, y – x + y = 2, x, y R}. Определение 2.8. Композицией двух отношений и называется отношение  = { x, z существует такое y, что x, y и y, z }. Пример 2.13. = { x, y y = sinx}. 11 = { x, y y = x}. и y, z } = { x, z  = { x, z существует такое y, что x, y существует такое y, что y = sinx и z = y} = { x, z z = sinx}. Определение композиции двух отношений соответствует определению сложной функции: y = f(x), z = g(y) z = g(f(x)). Пример 2.14. = { 1, 1 , 1, 2 , 1, 3 , 3, 1 }. = { 1, 2 , 1, 3 , 2, 2 , 3, 2 , 3, 3 }. Процесс нахождения  в соответствии с определением композиции удобно изобразить таблицей, в которой реализуется перебор всех возможных значений x, y, z. для каждой пары x, y нужно рассмотреть все возможные пары y, z (табл. 2.1). Таблица 2.1  x, y y, z x, z 1, 1 1, 2 1, 2 1, 1 1, 3 1, 3 1, 2 2, 2 1, 2 1, 3 3, 2 1, 2 1, 3 3, 3 1, 3 3, 1 1, 2 3, 2 3, 1 1, 3 3, 3 Заметим, что первая, третья и четвертая, а также вторая и пятая строки последнего столбца таблицы содержат одинаковые пары. Поэтому получим:  = { 1, 2 , 1, 3 , 3, 2 , 3, 3 }. 2.3. Свойства отношений Определение 2.9. Отношение называется рефлексивным на множестве X, если для любого x X выполняется x x. Из определения следует, что всякий элемент x, x . Пример 2.15. а) Пусть X – конечное множество, X = {1, 2, 3} и = { 1, 1 , 1, 2 , 2, 2 , 3, 1 , 3, 3 }. Отношение рефлексивно. Если X – конечное множество, то главная диагональ матрицы рефлексивного отношения содержит только единицы. Для нашего примера 1 1 0 C 0 1 0 . 1 0 1 б) Пусть X – множество действительных чисел и отношение равенства. Это отношение рефлексивно, т.к. каждое число равно самому себе. в) Пусть X – множество людей и отношение "жить в одном городе". Это отношение рефлексивно, т.к. каждый живет в одном городе сам с собой. 12 Определение 2.10. Отношение называется симметричным на множестве X, если для любых x, y X из x y следует y x. Очевидно, что симметрично тогда и только тогда, когда = –1. Пример 2.16. а) Пусть X – конечное множество, X = {1, 2, 3} и = { 1, 1 , 1, 2 , 1, 3 , 2, 1 , 3, 1 , 3, 3 }. Отношение симметрично. Если X – конечное множество, то матрица симметричного отношения симметрична относительно главной диагонали. Для нашего примера 1 1 1 C 1 1 0 . 1 0 1 б) Пусть X – множество действительных чисел и отношение равенства. Это отношение симметрично, т.к. если x равно y, то и y равно x. в) Пусть X – множество студентов и отношение "учиться в одной группе". Это отношение симметрично, т.к. если x учится в одной группе с y, то и y учится в одной группе с x. Определение 2.11. Отношение называется транзитивным на множестве X, если для любых x, y, z X из x y и y z следует x z. Одновременное выполнение условий x y, y z, x z означает, что пара x, z принадлежит композиции  . Поэтому для транзитивности необходимо и достаточно, чтобы множество  являлось подмножеством , т. е.  . Пример 2.17. а) Пусть X – конечное множество, X = {1, 2, 3} и = { 1, 1 , 1, 2 , 1, 3 , 2, 1 , 2, 3 , 3, 1 }. Отношение транзитивно, т. к. наряду с парами x, y и y, z имеется пара x, z . Например, наряду с парами 1, 2 , и 2, 3 имеется пара 1, 3 . б) Пусть X – множество действительных чисел и отношение (меньше или равно). Это отношение транзитивно, т.к. если x y и y z , то x z. в) Пусть X – множество людей и отношение "быть старше". Это отношение транзитивно, т.к. если x старше y и y старше z , то x старше z. Определение 2.12. Отношение называется отношением эквивалентности на множестве X, если оно рефлексивно, симметрично и транзитивно на множестве X. Пример 2.18. а) Пусть X – конечное множество, X = {1, 2, 3} и = { 1, 1 , 2, 2 , 3, 3 }. Отношение является отношением эквивалентности. б) Пусть X – множество действительных чисел и отношение равенства. Это отношение эквивалентности. в) Пусть X – множество студентов и отношение "учиться в одной группе". Это отношение эквивалентности. Пусть – отношение эквивалентности на множестве X. Определение 2.13. Пусть – отношение эквивалентности на множестве X и x X. Классом эквивалентности, порожденным элементом x, называется подмножество множества X, состоящее из тех элементов y X, для которых x y. Класс эквивалентности, порожденный элементом x, обозначается через [x]. 13 Таким образом, [x] = {y X x y}. Классы эквивалентности образуют разбиение множества X, т. е. систему непустых попарно непересекающихся его подмножеств, объединение которых совпадает со всем множеством X. Пример 2.19. а) Отношение равенства на множестве целых чисел порождает следующие классы эквивалентности: для любого элемента x из этого множества [x] = {x}, т.е. каждый класс эквивалентности состоит из одного элемента. б) Класс эквивалентности, порожденный парой x, y определяется соотношением: x u [ x, y ] = u, v . y v Каждый класс эквивалентности, порожденный парой x, y , определяет одно рациональное число. в) Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной группы. Определение 2.14. Отношение называется антисимметричным на множестве X, если для любых x, y X из x y и y x следует x = y. Из определения антисимметричности следует, что всякий раз, когда пара x, y принадлежит одновременно и –1, должно выполняться равенство x = y. –1 Другими словами, состоит только из пар вида x, x . Пример 2.20. а) Пусть X – конечное множество, X = {1, 2, 3} и = { 1, 1 , 1, 2 , 1, 3 , 2, 2 , 2, 3 , 3, 3 }. Отношение антисимметрично. Отношение = { 1, 1 , 1, 2 , 1, 3 , 2, 1 , 2, 3 , 3, 3 } неантисимметрично. Например, 1, 2 , и 2, 1 , но 1 2. б) Пусть X – множество действительных чисел и отношение (меньше или равно). Это отношение антисимметрично, т.к. если x y, и y x, то x = y. Определение 2.15. Отношение называется отношением частичного порядка (или просто частичным порядком) на множестве X, если оно рефлексивно, антисимметрично и транзитивно на множестве X. Множество X в этом случае называют частично упорядоченным и указанное отношение часто обозначают символом , если это не приводит к недоразумениям. Отношение, обратное отношению частичного порядка будет, очевидно, отношением частичного порядка. Пример 2.21. а) Пусть X – конечное множество, X = {1, 2, 3} и = { 1, 1 , 1, 2 , 1, 3 , 2, 2 , 2, 3 , 3, 3 }. Отношение есть отношение частичного порядка. б) Отношение А В на множестве подмножеств некоторого множества U есть отношение частичного порядка. в) Отношение делимости на множестве натуральных чисел есть отношение частичного порядка. 14 ТЕМА 4. БУЛЕВЫ ФУНКЦИИ 4.1. Определение булевой функции Определение 4.1. Булевой функцией f(x1, x2, ... , xn) называется произвольная функция n переменных, аргументы которой x1, x2, ... , xn и сама функция f принимают значения 0 или 1, т. е. xi {0, 1}, i = 1, 2, ... , n; f(x1, x2, ... , xn) {0, 1}. Одной из важнейших интерпретаций теории булевых функций является теория переключательных функций. Первоначально математический аппарат теории булевых функций был применен для анализа и синтеза релейно-контактных схем с операциями последовательного и параллельного соединения контактов. Подробнее это приложение теории булевых функций будет рассмотрено в разделе 4.9. Любая булева функция может быть представлена таблицей, в левой части которой перечислены все наборы переменных (их 2n), а в правой части – значения функции. Пример такого задания представлен в таблице 4.1. Таблица 4.1 x1 x2 x3 f(x1, x2, x3) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Для формирования столбца значений переменных удобен лексикографический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100 = 011+ 1. Всего существует 22 n различных булевых функций n переменных. Функций одной переменной – 4. Из них выделим функцию “отрицание x”(обозначается x). Эта функция представлена в таблице 4.2. Таблица 4.2 x x 1 1 Булевых функций двух переменных – 16 (22 n при n = 2). Те из них, которые имеют специальные названия, представлены в таблице 4.3. 15 Таблица 4.3 x1 x2 x1Vx2 x1& x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 В таблице 4.3 представлены следующие функции двух переменных: x1Vx2 – дизъюнкция; x1& x2 – конъюнкция; x1 x2 – импликация; x1 x2 – эквивалентность; x1 x2 – сложение по модулю 2; x1 x2 – стрелка Пирса; x1 x2 – штрих Шеффера. Остальные функции специальных названий не имеют и могут быть выражены через перечисленные выше функции. 4.2. Формулы логики булевых функций Определение 4.2. Формула логики булевых функций определяется индуктивно следующим образом: 1. Любая переменная, а также константы 0 и 1 есть формула. 2. Если A и B – формулы, то A, AVB, A&B, A B, A B есть формулы. 3. Ничто, кроме указанного в пунктах 1–2, не есть формула. Пример 4.1. Выражение ( xVy)&((y z) x) является формулой. Выражение x&y z x не является формулой. Часть формулы, которая сама является формулой, называется подформулой. Пример 4.2. x&(y z) – формула; y z – ее подформула. Определение 4.3. Функция f есть суперпозиция функций f1, f2, ... , fn если f получается с помощью подстановок этих формул друг в друга и переименованием переменных. Пример 4.3. f1 = x1&x2 (конъюнкция); f2 = x (отрицание). Возможны две суперпозиции: 1) f = f1(f2) = ( x1)&( x2) – конъюнкция отрицаний; 2) f = f2(f1) = (x1&x2) – отрицание конъюнкции. Порядок подстановки задается формулой. Всякая формула задает способ вычисления функции, если известны значения переменных. Пример 4.4. Построим таблицу значений функции f(x1, x2, x3) = (x2 x3) ( x1Vx2). Таблица 4.4 представляет последовательное вычисление этой функции. 16 Таблица 4.4 x1 x2 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 x3 1 1 1 1 x3 1 1 1 1 x2 x3 1 1 1 1 1 1 (x2 x3) 1 1 x1 1 1 1 1 x1Vx2 1 1 1 1 1 1 f(x1, x2, x3) 1 1 1 1 Таким образом, формула каждому набору аргументов ставит в соответствие значение функции. Следовательно, формула так же, как и таблица, может служить способом задания функции. В дальнейшем формулу будем отождествлять с функцией, которую она реализует. Последовательность вычислений функции задается скобками. Принято соглашение об опускании скобок в соответствии со следующей приоритетностью операций: , &, V, и . 4.3. Равносильные преобразования формул В отличие от табличного задания представление функции формулой не единственно. Например, две различные формулы x1V x2 и (x1&x2) реализуют одну функцию – штрих Шеффера. Две формулы, реализующие одну и ту же функцию, называются равносильными. Равносильность формул A и B будем обозначать следующтм образом: A B. Для того, чтобы установить равносильность формул, можно составить таблицы значений функции для каждой формулы и сравнить их. Для равносильных формул эти таблицы совпадают. Другой способ установления равносильности формул заключается в использовании некоторых установленных равносильностей булевых формул. Основные равносильности булевых формул. Для любых формул A, B, C справедливы следующие равносильности: 1. Коммутативность. а) A&B B&A (для конъюнкции); б) AVB BVA (для дизъюнкции). 2. Ассоциативность. а) A&(B&C) (A&C)&C (для конъюнкции); б) AV(BVC) (AVB)VC (для дизъюнкции). 3. Дистрибутивность. а) A&(BVC) A&BVA&C (для конъюнкции относительно дизъюнкции); б) AV(B&C) (AVB)&(AVC) (для дизъюнкции относительно конъюнкции). 17 4. Закон де Моргана. а) (A&B) AV B (отрицание конъюнкции есть дизъюнкция отрицаний); б) (AVB) A& B (отрицание дизъюнкции есть конъюнкция отрицаний). 5. Идемпотентность. а) A&A A (для конъюнкции); б) AVA A (для дизъюнкции). 6. Поглощение. а) A&(AVB) A (1– ый закон поглощения); б) AVA&B A (2– ой закон поглощения). 7. Расщепление (склеивание). а)A&B V A&( B) A (1–ый закон расщепления); б) (AVB) & (AV B) A (2–ой закон расщепления). 8. Двойное отрицание. ( A) A. 9. Свойства констант. а)A&1 A; б) A&0 0; в)AV1 1; г) AV0 A; д) 0 1; е) 1 0. 10. Закон противоречия. A& A 0. 11. Закон “исключенного третьего”. AV A 1. Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “ ”. Докажем, например, равносильность 4а. Для этого составим таблицу 4.5. A 1 1 B 1 1 A&B 1 (A&B) 1 1 1 A 1 1 B 1 1 Таблица 4.5 AV B 1 1 1 Из таблицы 4.5 видно, что (A&B) AV B, что и требовалось доказать. Следующие важные равносильности показывают, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания: 12. A B AVB (A& B). 13. A B (A B)&(B A) (A&B) V ( A& B) АV B)&( AVB). 14. A AV B) V ( A&B). 15. A B (AVB) A& B. 16. A B (A&B) AV B. Используя равносильности 3а и 3б и метод математической индукции, нетрудно получить также следующие равносильности (обобщенные законы дистрибутивности): 17. (A1VA2V...VAn)&(B1VB2V...VBm) 18 A1&B1VA1&B2V...VA1&BmV...VAn&B1VAn&B2V...VAn&Bm. 18. (A1&A2&...&An)V(B1&B2&...&Bm) (A1VB1)&(A1VB2)&...&(A1VBm)&...&(AnVB1)&(AnVB2)&...&(AnVBm). Используя равносильности 4а и 4б и метод математической индукции, можно получить также следующие равносильности (обобщенные законы де Моргана): 19. (A1&A2&...&An) A1V A2V...V An. 20. (A1VA2V...VAn) A1& A2&...& An В равносильностях 1 – 20 в качестве A, B, Ai, Bi могут быть подставлены любые формулы и, в частности, переменные. Приведем правило, с помощью которого можно переходить от одних равносильностей к другим. Правило равносильных преобразований Пусть для формул A и B справедливо утверждение A B. Пусть CA – формула, содержащая A в качестве своей подформулы. Пусть CB получается из CA заменой A на B. Тогда CA CB. Пример 4.5. Пусть A = x y, B = xVy. Равносильность 12 позволяет утверждать, что A B. Пусть CA = (x y) & z, т.е. A есть подформула CA. Тогда CB = ( xVy) & z и CA CB, т.е. (x y) & z ( xVy) & z. 4.4. Двойственность. Принцип двойственности. Символы &, V называются двойственными. Формула А* называется двойственной формуле A, если она получена из A одновременной заменой всех символов &, V на двойственные. Например, A = xV(y& z); A* = x & (yV z). Теорема 4.1. (Принцип двойственности). Если A B, то A* B Доказательство принципа двойственности можно найти, например, в [3]. Принцип двойственности можно использовать для нахождения новых равносильностей. Например, для 1-го закона поглощения (равносильность 6а) имеем: A&(AVB) A. Следуя принципу двойственности, получим новую равносильность: AVA&B A (2- ой закон поглощения). 4.5. Булева алгебра . Полные системы булевых функций Как известно, алгеброй называют систему, включающую в себя некоторое непустое множество объектов с заданными на нем функциями (операциями), результатами применения которых к объектам данного множества являются объекты того же множества. 19 Булевой алгеброй или алгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания. Система булевых функций {f1, f2, … , fn} называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей 12 – 16 (раздел 4.3) следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций { , &, V} является полной. Также полными являются следующие системы функций: а) { , V}; б) { , &}; в) { , }. Полнота систем { , V} и { , &} следует из полноты системы { , &, V}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A&B ( AV B); AVB ( A& B). Поэтому система { , &, V} может быть сокращена на одну функцию: Полнота системы { , } следует из полноты системы { , V} и равносильности 12 (раздел 4.3), позволяющую выразить импликацию через отрицание и дизъюнкцию: A B AVB. 4.6. Нормальные формы Определение 4.4. Элементарной конъюнкцией называется конъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных. Пример 4.6. x, y, x&y, x1&x2&( x3) – элементарные конъюнкции. xVy, x1& x2 V x1&x2 – не элементарные конъюнкции. Определение 4.5. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций (в вырожденном случае это может быть одна конъюнкция). Пример 4.7. x, x&y, x V x&( y), x1&x2&( x3) V x1&( x2)&x3 V x1&x2&( x3) – ДНФ. (xVy)& x – не ДНФ. Определение 4.6. Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, каждый конъюнктивный член которой содержит все переменные, либо их отрицания. Пример 4.8. x&y, x& y V x&y – СДНФ функции двух переменных. xV x&y, xVy – не СДНФ. Определение 4.7. Элементарной дизъюнкцией называется дизъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных. Пример 4.9. x, y, xVy, x1Vx2V( x3) – элементарные дизъюнкции. x&y, (x1V x2) & ( x1Vx2) – не элементарные дизъюнкции. 20 Определение 4.8. Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций (в вырожденном случае это может быть одна дизъюнкция). Пример 4.10. x, x&y, x & x&( y), ( x1Vx2)&( x3)&(x1V x2Vx3) – КНФ. x&y V x – не КНФ. Определение 4.9. Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, каждый дизъюнктивный член которой содержит все переменные, либо их отрицания. Пример 4.11. xVy, (xV y) &( xVy) – СКНФ функции двух переменных. x &( xVy), x&y – не СКНФ. Теорема 4.2. Для каждой формулы булевой функции A имеется равносильная ей дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ). Доказательство теоремы состоит просто в указании алгоритмов нахождения для любой формулы A равносильных ей ДНФ и КНФ. Процесс нахождения этих форм называется приведением формулы A соответственно к ДНФ и КНФ. Для каждой формулы A имеется, вообще говоря, бесконечное множество ДНФ и КНФ, но для решения задач, в которых эти формы нужны, требуется, как правило, найти по крайней мере одну из них. Алгоритм 4.1 (Алгоритм приведения формул булевых функций к ДНФ (КНФ)). Шаг 1. Все подформулы A вида B C (т.е. содержащие импликацию) заменяем на BVC или на (B& C) (в соответствии с равносильностью 12 раздела 4.3). Шаг 2. Все подформулы A вида B C (т.е. содержащие эквивалентность) заменяем на (A&B) V ( A& B) или на (AV B)&( AVB) (в соответствии с равносильностью 13). Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана (в соответствии с равносильностями 4, 19, 20). Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8). Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ (в соответствии с равносильностями 3б и 18). Шаг 6. для получения более простой формулы целесообразно использовать равносильности 5, 6, 7, 9, 10, 11. Очевидно, что в результате всех указанных операций формула имеет вид ДНФ или КНФ. Указанные операции, вообще говоря, могут осуществляться в любом порядке, однако целесообразно придерживаться изложенного выше, за исключением снятия двойных отрицаний (шаг 4), от которых следует избавляться по мере их появления. 21 Пример 4.12. Приведем к ДНФ и КНФ рассмотренную ранее в примере 4.4 формулу f(x1, x2, x3) = (x2 x3) ( x1Vx2). 1. Устранив импликацию, получим: ( x2 V x3) ( x1Vx2). 2. Применив закон де Моргана к первой скобке и сняв двойные отрицания, получим: (x2&x3) ( x1Vx2). 3. Устранив эквивалентность, получим: (x2&x3) & ( x1Vx2) V (x2&x3) & ( x1Vx2). 4. Применив закон де Моргана ко второму члену дизъюнкции, получим (x2&x3) & ( x1Vx2) V ( x2V x3) & (x1& x2). 5. Применив закон дистрибутивности 3а, получим (x2&x3& x1 V x2&x3&x2) V ( x2&x1& x2 V x3&x1& x2). 6. Применив законы идемпотентности 5а и 5б, и располагая переменные по возрастанию индексов, получим: x1&x2&x3 V x2&x3 V x1& x2 V x1& x2& x3. 7. Применив 2–ой закон поглощения (6б), вместо x1&x2&x3.V x2&x3 запишем x2&x3, а вместо x1& x2 V x1& x2& x3 запишем x1& x2 и в результате получим ДНФ нашей формулы: f(x1, x2, x3) x2&x3 V x1& x2 При приведении к КНФ применим закон дистрибутивности 3б и получим: x2&x3 V x1& x2 x2Vx1) & (x2V x2) & (x3Vx1) & (x3V x2). Учитывая, что. x2V x2 1 (равносильность 11) и применив свойство 9а, получим окончательно КНФ для f(x1, x2, x3) f(x1, x2, x3) x1Vx2) & (x1Vx3) & ( x2Vx3). Приведение некоторой формулы к ДНФ и КНФ не является однозначным. Количество равносильных ДНФ и КНФ, вообще говоря, бесконечно. Однако, совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ) или не существуют или единственны. Теорема 4.3. Каждая формула A, не равная тождественно нулю, может быть приведена к СДНФ, которая является единственной с точностью до перестановки дизъюнктивных членов. Теорема 4.4. Каждая формула A, не равная тождественно единице, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов. Доказательство этих теорем состоит в указании алгоритма приведения формулы А к СДНФ и СКНФ. Алгоритм 4.2. (Алгоритм приведения формулы булевой функции к СДНФ) Шаг 1. Используя алгоритм построения ДНФ, находим формулу В, являющуюся ДНФ формулы А. Шаг 2. Вычеркиваем в B все элементарные конъюнкции, в которые одновременно входят какая-нибудь переменная и ее отрицание. Это обосновывается равносильностями: A& A 0, B&0 0, СV0 С. 22 Шаг 3. Если в элементарной конъюнкции формулы B некоторая переменная или ее отрицание встречается несколько раз, то оставляем только одно ее вхождение. Это обосновывается законом идемпотентности для конъюнкции: A&A A. Шаг 4. Если в элементарную конъюнкцию С формулы В не входит ни переменная x, ни ее отрицание x, то на основании 1- го закона расщепления (равносильность 7а) заменяем С на (С&x) V (C& x). Шаг 5. В каждой элементарной конъюнкции формулы B переставляем конъюнктивные члены так, чтобы для каждого i (i = 1, ..., n) на i-ом месте была либо переменная xi, либо ее отрицание xi. Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: СVС С. Пример 4.13. Найдем СДНФ формулы из примера 4.4: f(x1, x2, x3) = (x2 x3) ( x1Vx2). 1. Найденная ранее в примере 4.12 ДНФ формулы f(x1, x2, x3) имеет вид: x2&x3 V x1& x2. 2. Шаги 2 и 3 алгоритма не требуются (они уже выполнены), поэтому переходим к шагу 4 и применяем 1-ый закон расщепления. В результате вместо каждого из двух конъюнктивных членов получим две элементарных конъюнкции (всего их будет четыре): f(x1, x2, x3) x2&x3&x1 V x2&x3& x1V x1& x2&x3 V x1& x2& x3). 3. После применения шага 5 получим: f(x1, x2, x3) x1&x2&x3 V x1&x2&x3 V x1& x2&x3 V x1& x2& x3. 4. Шаг 6 не требуется. Найденное выражение формулы f(x1, x2, x3) является СДНФ этой формулы. Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на V и V на &. Пример 4.14. Найдем СКНФ формулы из примера 4.4: f(x1, x2, x3) = (x2 x3) ( x1Vx2). 1. Найденная в примере 4.12 КНФ формулы f(x1, x2, x3) имеет вид: f(x1, x2, x3) x1Vx2) & (x1Vx3) & ( x2Vx3). 2. Шаги 2 и 3 алгоритма не требуются, поэтому переходим к шагу 4 и применяем 2-ой закон расщепления (равносильность 7б). В соответствии с этим законом: x1Vx2 x1Vx2Vx3) & (x1Vx2V x3). x1Vx3 (x1Vx3Vx2)&(x1Vx3V x2). x2 Vx3 ( x2Vx3Vx1) & ( x2Vx3V x1). Поэтому имеем: f(x1, x2, x3) x1Vx2Vx3)&(x1Vx2V x3)& x1Vx3Vx2)&(x1Vx3V x2)&( x2Vx3Vx1)&( x2 V x3V x1). 3. Применив шаг 5, получим: f(x1, x2, x3) (x1Vx2Vx3)&(x1Vx2V x3)&(x1Vx2Vx3)&(x1V x2Vx3)&(x1V x2Vx3)&( x1 V x2Vx3). 23 4. Замечаем, что 1-ый и 3-ий, а также 4-ый и 5-ый дизъюнктивные члены полученного выражения совпадают, применяем шаг 6 и получим окончательно СКНФ формулы f(x1, x2, x3): f(x1, x2, x3) (x1Vx2Vx3)&(x1Vx2V x3)&(x1V x2Vx3)&( x1V x2Vx3). Теорема 4.6 (о представлении булевой функции формулой в СДНФ), Всякая булева функция f(x1, x2, ... , xn), не равная тождественно 0, может быть представлена формулой в СДНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов. В силу изложенного для получения формулы булевой функции f(x1, x2, ... , xn) в СДНФ можно воспользоваться следующим алгоритмом. Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ). Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f равно 1, т. е. f (s1, s2, ... , sn) = 1. Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию s1 x1 &x2s2&...&xnsn, где xisi = xi, если si = 1 и xisi = xi, если si = 0, i = 1, 2, ... ,n. Шаг 3. Составляем дизъюнкцию всех полученных конъюнкций. В результате получится формула данной функции в СДНФ. Пример 4.15. Найдем формулу в СДНФ для функции f(x1, x2, x3), заданной таблицей 4.4. 1. Выберем в таблице строки, где f(x1, x2, x3) =1. Это 4-ая, 5-ая. 6-ая и 8-ая строки. 2. Для каждой выбранной строки составляем конъюнкции по правилу, указанному в шаге 2. Получим соответственно для четырех выбранных строк: x10&x21&x31 = x1 &x2&x3. x11&x20&x30 = x1& x2& x3. x11&x20&x31 = x1& x2&x3 . x11&x21&x31 = x1&x2&x3 . 3. Составляем дизъюнкцию всех полученных конъюнкций и находим СДНФ: f(x1, x2, x3) = x1&x2&x3V x1& x2& x3 V x1& x2&x3 V x1&x2&x3. Убеждаемся, что это выражение совпадает с полученным ранее в примере 4.13 представлением нашей формулы в СДНФ. Замечание. Если булева функция задана формулой в СДНФ, то, применяя алгоритм 4.3 в обратной последовательности, легко можем получить таблицу значений этой функции. Теорема 4.7 (о представлении булевой функции формулой в СКНФ), Всякая булева функция f(x1, x2, ... , xn), не равная тождественно 1, может быть представлена формулой в СКНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов. Для получения формулы булевой функции f(x1, x2, ... , xn) в СКНФ следует воспользоваться следующим алгоритмом. Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ) Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f (s1, s2, ... , sn) = 0. 24 Шаг 2. Для каждого такого набора (строки таблицы) составляем дизъюнкцию x1 s1Vx2 s2V...Vxn sn, где xi si = xi, если si = 0 и xi si = xi, если si = 1, i = 1, 2, ... , n. Шаг 3. Составляем конъюнкцию всех полученных дизъюнкций. В результате получится СКНФ. Пример 4.16. Найдем формулу в СКНФ для функции f(x1, x2, x3), заданной таблицей 4.4. 1. Выберем в таблице строки, где f(x1, x2, x3) = 0. Это 1-ая, 2-ая и 3-я и 7-ая строки. 2. Для каждой выбранной строки составляем дизъюнкции по правилу, указанному в шаге 2. Получим соответственно для трех выбранных строк: x11Vx21Vx31 = x1Vx2Vx3. x11Vx21Vx30 x1Vx2V x3. x11Vx20Vx31 = x1V x2Vx3. x10Vx20Vx31 = x1V x2V x3. 3. Составляем конъюнкцию всех полученных дизъюнкций и находим СКНФ: f(x1, x2, x3) = x1Vx2Vx3)&(x1Vx2V x3)&(x1V x2Vx3)&( x1V x2Vx3). Это выражение совпадает с полученным ранее в примере 4.14 представлением нашей формулы в СКНФ. Замечание. Т. к. всего строк в таблице функции 2n, то, если число дизъюнктивных членов в СДНФ равно p, а число конъюнктивных членов в СКНФ равно q, то p+q=2n. Так, для функции, рассмотренной в примерах 4.15 и 4.16, n = 3, p = 4, q = 4, p + q = 8 = 23. 4.7 Минимизация формул булевых функций Как было установлено выше, произвольная булева функция может быть представлена формулой в ДНФ и КНФ, причем такое представление неоднозначно. Равносильными преобразованиями можно получить формулу, содержащую меньшее число вхождений переменных. Например, две различные формулы: f1(x1, x2) = x1V x1&x2 V x2 и f2(x1, x2) = x1 V x2 равносильны, так как в силу 2-го закона поглощения (равносильность 6б из раздела 4.3) x1 V x1&x2 x1. Но в формуле f1(x1, x2) содержится четыре вхождений переменных, а в формуле f2(x1, x2) – два. Определение 4.10. ДНФ называется минимальной, если она содержит наименьшее общее число вхождений переменных среди всех равносильных ей ДНФ. Определение 4.11. Импликантом булевой функции f(x1, x2, ... , xn) называется элементарная конъюнкция С, не равная тождественно 0, такая что C V f f. Отметим, что любая конъюнкция любой ДНФ в силу закона идемпотентности (равносильность 5б) является импликантом этой функции. Определение 4.12. Импликант C функции f называется простым импликантом, если после отбрасывания любой переменной из C получается элементарная конъюнкция, не являющаяся импликантом функции f. Пример 4.17. 25 Для функции x&yVx&zVx&y&z x&(yVz) конъюнкции x&y и x&z – простые импликанты, а x&y&z – импликант, но не простой. Определение 4.13. Дизъюнкция всех простых импликантов булевой функции f называется сокращенной ДНФ функции f. Для нахождения сокращенной ДНФ используется следующий алгоритм, в основе которого лежит метод Квайна. Алгоритм 4.5. (Алгоритм Квайна построения сокращенной ДНФ). Шаг 1. Находим для данной булевой функции f ее формулу F, находящуюся в СДНФ. Шаг 2. Находим все простые импликанты функции f. Для этого все элементарные конъюнкции формулы F попарно сравниваем между собой. Если две элементарные конъюнкции таковы, что они имеют вид C&xi и C& xi, то выписываем конъюнкцию С. Это является следствием 1-го закона расщепления (склеивания) (равносильность 7а). Конъюнкция С содержит n - 1 вхождение переменных. Элементарные конъюнкции, для которых произошло склеивание, помечаем. После построения всех конъюнкций, включающих n - 1 вхождение переменных, вновь сравниваем их попарно, производим, если возможно, склеивание, выписываем полученные конъюнкции из n - 2 членов, помечаем склеивающиеся конъюнкции из n - 1 членов и т. д. Процесс заканчивается, когда дальнейшее склеивание невозможно. Все непомеченные элементарные конъюнкции являются простыми импликантами. Их дизъюнкция даст нам формулу F1, равносильную F, находящуюся в ДНФ и состоящую из простых импликантов, т.е. сокращенную ДНФ. Пример 4.18. Найдем сокращенную ДНФ функции из примера 4.4: f(x1, x2, x3) = (x2 x3) ( x1Vx2). 1. Шаг 1 был выполнен ранее (см. примеры 4.13, 4.15). СДНФ формулы f(x1, x2, x3) является формула F(x1, x2, x3) = x1&x2&x3V x1& x2& x3 V x1& x2&x3 V x1&x2&x3. 2. Попарно сравниваем все 4 трехчленные конъюнкции (всех сравнений C 24 = 6) и применяем, где это возможно, закон склеивания: x1&x2&x3V x1&x2&x3 = x2&x3. x1& x2& x3 V x1& x2&x3 = x1& x2. x1& x2&x3 V x1&x2&x3 = x1&x3. Итак, на первом этапе получили 3 двучленные конъюнкции: x2&x3, x1& x2, x1&x3. Все трехчленные конъюнкции оказались помеченными. Попарно сравниваем все 3 двучленные конъюнкции (всех сравнений 3) и замечаем, что склеивание невозможно. В результате получим сокращенную ДНФ формулы f: F1(x1, x2, x3) = x2&x3 V x1& x2 V x1&x3. На практике для построения сокращенной ДНФ удобнее пользоваться модифицированным методом Квайна – Мак-Класки. Этот метод состоит в автоматизации процесса склеивания. Разберем этот метод на конкретном примере. 26 Алгоритм 4.6. (Алгоритм Квайна - Мак-Класки построения сокращенной ДНФ). Шаг 1. Составим таблицу значений булевой функции (если функция задана формулой в СДНФ, то в силу замечания к алгоритму 4.3 это всегда можно сделать) Для нашего примера такая таблица уже составлена – это таблица 4.4. Очевидно, в силу алгоритма 4. 3 (см. также пример 4.15), эта функция имеет следующую формулу в СДНФ: f(x1, x2, x3) = x1&x2&x3V x1& x2& x3 V x1& x2&x3 V x1&x2&x3. Шаг 2. Выпишем наборы переменных, на которых функция принимает значение 1, причем эти наборы упорядочим по группам так, что в каждую группу входят наборы с одинаковым числом единиц. Пусть Ai – группа наборов переменных, таких, что каждый набор содержит i единиц, и функция на этом наборе переменных принимает значение, равное единице. Группы A0 (где все переменные нули, а значение функции равно 1) нет. Группа A1 (где одна переменная единица, остальные нули, и значение функции равно 1): 1 Группа A2: 1 1 1 1 Группа A3: 1 1 1 Шаг 3. Производим попарное сравнение наборов переменных, входящих в соседние группы. Если при этом сравнении обнаружатся два набора, которые отличаются только в одном разряде, то вместо них записывается один набор, в котором вместо несовпадающих разрядов ставится “ – “ (прочерк). После всех возможных сравнений из предшествующего списка вычеркиваются все наборы, которые участвовали в образовании хотя бы одного набора с прочерком. Формируются два массива наборов: наборы с прочерками (массив P) и невычеркнутые (массив R). Эти действия соответствуют склеиванию конъюнкций и уменьшению числа вхождений переменных. Для нашего примера при сравнении групп A1 и A2: вместо (1 0 0) и (1 0 1) получим (1 0 –); При сравнении групп A2 и A3: вместо (0 1 1) и (1 1 1) получим (– 1 1); вместо (1 0 1) и (1 1 1) получим (1 – 1); После этого этапа массив R пуст, т. к. все наборы участвовали в образовании наборов с прочерками, а массив P = P(1) включает следующие наборы: (1 0 –); (– 1 1); (1 – 1). Далее рассмотрим наборы с прочерками. Они вновь попарно сравниваются между собой. При этом имеет смысл сравнивать лишь наборы, в которых прочерк стоит в совпадающих разрядах. Если сравниваемые наборы отличаются друг от друга только в одном разряде, то выписываем набор с двумя прочерками (старым и новым). После всех попарных сравнений из множества наборов с одним 27 прочерком вычеркиваются все наборы, имеющие один прочерк и участвовавшие в образовании набора с двумя прочерками. Наборы с одним прочерком, не участвовавшие в образовании наборов с двумя прочерками, помещаются в массив R. Для нашего примера попарное сравнение наборов с одним прочерком не приводит к образованию наборов с двумя прочерками. Далее рассмотрим наборы с двумя прочерками и т. д. Процесс прекращается, если на очередном шаге все рассматриваемые наборы попадают в R. Нетрудно убедиться, что каждому набору из R соответствует простой импликант, причем единице соответствует переменная, взятая без отрицания, нулю – переменная, взятая с отрицанием, а прочерку – отсутствие соответствующей переменной. Сокращенная ДНФ есть дизъюнкция этих простых импликантов. Для нашего примера процедура сравнения заканчивается после формирования наборов с одним прочерком. Массив R после этого включает наборы: (1 0 –); (– 1 1); (1 – 1). Сокращенная ДНФ имеет вид: f(x1, x2, x3) = x2&x3 V x1& x2 V x1&x3. Далее процесс нахождения минимальной ДНФ сводится к отбрасыванию некоторых простых импликантов. 28 Тема 3. ГРАФЫ Первая работа по теории графов принадлежащая Эйлеру, появилась в 1736 году. Вначале эта теория была связана с математическими головоломками и играми. Однако впоследствии теория графов стала использоваться в топологии, алгебре, теории чисел. В наше время теория графов находит применение в самых разнообразных областях науки, техники и практической деятельности. Она используется при проектировании электрических сетей, планировании транспортных перевозок, построении молекулярных схем. Применяется теория графов также в экономике, психологии, социологии, биологии. 3.1. Основные характеристики графов Граф G - это математический объект, состоящий из множества вершин X = {x1, x2,..., xn} и множества ребер A = {a1, a2,..., an}. Таким образом, граф полностью определяется совокупностью множеств X, A: G = (X, A). Для многих задач несущественно, являются ли ребра отрезками прямых или криволинейными дугами; важно лишь то, какие вершины соединяет каждое ребро. Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом). Пример 3.1. На рис. 3.1 изображен неориентированный граф G =( X, A). X = {x1, x2, x3, x4}, A = {a1= (x1, x2), a2=(x2, x3), a3=(x1, x3), a4= (x3, x4)}. Рис. 3.1. Пример 3.2. На рис. 3.2. изображен ориентированный граф G = (X, A). X = {x1, x2, x3, x4}, A = {a1 = (x1 , x2 ), a2 = (x1 , x3 ), a3 = (x3 , x4 ), a4 = (x3 , x2 )}. 29 Рис. 3.2. Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным. Различные ребра могут соединять одну и ту же пару вершин. Такие ребра называют кратными. Граф, содержащий кратные ребра, называется мультиграфом. Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины. Ребро может соединять вершину саму с собой. Такое ребро называется петлей. Граф с кратными ребрами и петлями называется псевдографом. Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым. Пример 3.3. На рис. 3.3. изображен ориентированный граф G = (X, A). X = {x1 , x2 , x3 , x4 }, A= . Риc. 3.3. Как в случае ориентированного, так и в случае неориентированного ребра говорят, что вершины x и y инцидентны ребру a, если эти вершины соединены a. Две вершины называются смежными, если они инцидентны одному и тому же ребру. Два ребра называются смежными, если они имеют общую вершину. Степенью вершины графа называется число ребер, инцидентных этой вершине. Вершина, имеющая степень 0, называется изолированной, а степень 1 – висячей. Для ориентированного графа множество вершин, в которые ведут дуги, исходящие из вершины х, обозначают G(х), то есть G(х) = { y: ( x y ) G}. Множество G(x) называют образом вершины x. Соответственно G-1(у) – множество вершин, из которых исходят дуги, ведущие в вершину у, G-1(y) = {x: ( x , y ) G}. Множество G-1(у) называют прообразом вершины y. Пример 3.4. В графе, изображенном на рис. 3.1, концами ребра a1 являются вершины x1, x2; вершина x2 инцидентна ребрам a1, a2; степень вершины x3 равна 3; вершины x1 и x3 смежные; ребра a1 и a2 смежные; вершина x4 висячая. В ориентированном графе, изображенном на рис. 3.2, началом дуги a1 является вершина x1, а ее концом - 30 вершина x2; вершина x1 инцидентна дугам a1 и a2; G(x1) = {x2, x3}, G(x2) = , G1 (x3) = {x1}, G-1(x1) = . Подграфом неориентированного графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Аналогично определяется подграф ориентированного графа. Подграф называется собственным, если он отличен от самого графа, Граф G = (X, A) - полный, если для любой пары вершин xi и xj существует ребро (xi, xj). Граф G = (X, A) - симметрический, если для любой дуги (xi, xj) существует противоположно ориентированная дуга (xj, xi). Граф G = (X, A) - планарный, если он может быть изображен на плоскости так, что не будет пересекающихся дуг. Неориентированный граф G = (X, A) – двудольный, если множество его вершин X можно разбить на два такие подмножества X1 и X2, что каждое ребро имеет один конец в X1, а другой в X2. 3.2. Матричные способы задания графов Для алгебраического задания графов используются матрицы смежности и инцидентности. Матрица смежности A = (aij) определяется одинаково для ориентированного и неориентированного графов. Это квадратная матрица порядка n, где n - число вершин, у которой aij = 1, если ( xi x j ) 0, если ( xi , x j ) A, A. Пример 3.5. Матрица смежности графа, изображенного на рис. 3.1, имеет вид: 0 1 1 0 A = 1 0 1 0 1 1 0 1 0 0 1 1 Пример 3.6. Матрица смежности ориентированного графа, изображенного на рис. 3.2, имеет вид: 0 1 1 0 A = 0 0 0 0 0 1 0 1 0 0 0 0 Матрица смежности полностью задает граф. Матрицей инцидентности B = (bij) ориентированного графа называется прямоугольная матрица (n m), где n – число вершин, m – число ребер, у которой 31 1, если вершина xi является началом дуги a j ; bi = 1, если вершина xi является концом дуги a j ; 0, если вершина xi не инцидентна дуге a j ; Для неориентированного следующим образом: bi = графа матрица инцидентности B задается 1, если вершина xi инцидентна ребру a j ; 0, если вершина xi не инцидентна ребру a j . Пример 3.7. Матрица инцидентности графа, изображенного на рис. 3.1, имеет вид: 1 1 0 0 B = 1 0 1 0 0 1 1 1 0 0 0 1 Пример 3.8. Матрица инцидентности ориентированного графа, изображенного на рис. 3.2, имеет вид: 1 1 0 0 B= -1 0 0 -1 0 -1 1 1 0 0 -1 0 Матрица инцидентности, также, как и матрица смежности, полностью задает граф. Матрицы смежности и инцидентности удобны для задания графов на ЭВМ. 3.3 Основные свойства матриц смежности и инцидентности 1. Матрица смежности неориентированного графа является симметричной. Для ориентированного графа это, вообще говоря, неверно. 2. Сумма элементов i - ой строки или i -го столбца матрицы смежности неориентированного графа равна степени вершины xi. 3. Сумма элементов i - ой строки матрицы смежности ориентированного графа равна числу дуг, исходящих из xi.4. Сумма элементов i - го столбца матрицы смежности ориентированного графа равна числу дуг, входящих в вершину xi. 5. Сумма строк матрицы инцидентности ориентированного графа является нулевой строкой. Итак, возможны следующие различные способы задания графа: а) посредством графического изображения; б) указанием множества вершин и множества ребер (дуг); в) матрицей смежности; г) матрицей инцидентности. 32 3.4. Маршруты, циклы в неориентированном графе Пусть G - неориентированный граф. Маршрутом или цепью в G называется такая последовательность (конечная или бесконечная) ребер a1, a2,... an..., что каждые соседние два ребра ai и ai+1 имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a1,a2,...an) имеется первое ребро a1 и последнее ребро an. Вершина x1, инцидентная ребру a1, но не инцидентная ребру a2, называется началом маршрута, а вершина xn, инцидентная ребру an, но не инцидентная ребру an-1, называется концом маршрута. Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут. Пример 3.10. В изображенном на рис. 3.5 графе рассмотрим два маршрута из вершины x1 в вершину x4: M1 = (a1, a2, a4) и M2 = (a1, a2, a5, a6). Длина маршрута M1 равна 3, а длина маршрута M2 равна 4. Рис.3.5 Замкнутый маршрут называется циклом. Маршрут (цикл), в которой все ребра различны, называется простой цепью (циклом). Маршрут (цикл), в которой все вершины, (кроме первой и последней), различны, называется элементарной цепью (циклом). Пример 3.11. В приведенном на рис 3.6 графе выделим следующие маршруты: (a1,a3,a4) – простая элементарная цепь длины 3, т.к. все ребра и вершины попарно различны; (a2,a4,a3) – простой элементарный цикл, т.к. это замкнутый маршрут, у которого все ребра и вершины, кроме первой и последней, различны; (a1,a2,a4,a3) – цепь, которая является простой, но не элементарной, т.к. все ребра различны, но вершина x2 встречается дважды; (a1,a2,a2) –маршрут длины 3, не являющийся ни простой, ни элементарной цепью, т.к. ребро a2 и вершина x2 встречаются дважды. Рис.3.6 33 3.5. Пути, контуры в ориентированном графе Понятия пути, контура в ориентированном графе аналогичны понятиям маршрута, цикла в неориентированном графе. Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длиной пути. Путь называется контуром, если его начальная вершина совпадает с конечной вершиной. Путь (контур), в котором все дуги различны, называется простым. Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным. Следует усвоить, что понятиям ребра, маршрута, цепи, цикла в неориентированном графе соответствуют понятия дуги, пути, ориентированной цепи, контура в ориентированном графе. Для лучшего запоминания приведем эти термины в таблице. Неориентированный граф ребро маршрут цикл Ориентированный граф дуга путь контур Пример 3.12. В приведенном на рис 3.7 графе выделим следующие пути: (x1,x2,x3,x4) – простой элементарный путь, т.к. каждая вершина и каждая дуга используются не более одного раза; (x2,x5,x6,x7,x2) – простой элементарный контур, т.к. это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны. Рис. 3.7 3.6 Связность графа Неориентированный граф называется связным, если каждая пара различных вершин может быть соединена по крайней мере одной цепью. Ориентированный граф называется сильно связным, если для любых двух его вершин xi и xj существует хотя бы один путь, соединяющий xi с xj. 34 Ориентированный граф называется односторонне связным, если для любых двух его вершин по крайней мере одна достижима из другой. Компонентой связности неориентированного графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа (максимально связный подграф). Компонентой сильной связности ориентированного графа называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа данного графа (максимально сильно связный подграф). Компонентой одностронней связности неориентированного графа называется его односторонне связный подграф, не являющийся собственным подграфом никакого другого односторонне связного подграфа данного графа (максимально односторонне связный подграф). Пусть G = (X, A) неориентированный граф с множеством вершин X = {x1,...,xn}. Квадратная матрица S = (sij) порядка n, у которой sij = рой 1, если вершины xi и x j принадлежат одной компоненте связности, 0 в противном случае. называется матрицей связности графа G. Для ориентированного графа квадратная матрица T = (tij) порядка n, у котоtij = 1, если существуетпуть из xi в x j , 0, в противном случае. называется матрицей односторонней связности (достижимости). Квадратная матрица S = (sij) порядка n, у которой sij = 1, если существуетпуть из xi в x j и из x j в xi , 0, в противном случае. называется матрицей сильной связности. Пример 3.13. У неориентированного графа, изображенного на рис. 3.8 две компоненты связности. Первая компонента связности включает вершины x1, x2, x4, x5, а вторая состоит из одной вершины x3. Рис.3.8 Матрица связности этого графа имеет вид: S = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Мы видим, что 1-ая, 2-ая, 4-ая и 5-ая строки матрицы S одинаковы. 35 Пример 3.14 У ориентированного графа, изображенного на рис. 3.9 две компоненты сильной связности. Первая компонента связности включает вершины x1, x2, x3, x5, а вторая состоит из одной вершины x4. Действительно, для любой пары вершин из множества {x1, x2, x3, x5} существует хотя бы один путь, соединяющий эти вершины. Например, путь (x1, x2, x5, x3, x1) соединяет все эти вершины. Из вершины x4 нет пути ни в одну вершину графа. Рис. 3.9 Матрица сильной связности этого графа имеет вид: S = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Мы видим, что 1-ая, 2-ая, 3-ая и 5-ая строки матрицы S одинаковы. 3.7. Экстремальные пути в нагруженных ориентированных графах Ориентированный граф называется нагруженным, если дугам этого графа поставлены в соответствие веса, так что дуге (xi,xj) сопоставлено некоторое число c(xi,xj) = cij, называемое длиной (или весом, или стоимостью дуги). Длиной (или весом или стоимостью) пути s, состоящего из некоторой последовательности дуг (xi,xj), называется число l(s), равное сумме длин дуг, входящих в этот путь, т.е. l(s) = cij, причем суммирование ведется по всем дугам (xi, xj) s. Матрица C = (cij) называется матрицей длин дуг или матрицей весов. Рис. 3.10 Для графа, изображенного на рис. 3.10, матрица C имеет вид: 36 1 2 C= 4 5 3 6 Длина пути (x1, x2, x5, x4) равна 1 + 5 + 6 = 12. Для ненагруженного графа введем понятие кратчайшего пути. Это путь с минимальным общим числом дуг, причем каждая дуга считается столько раз, сколько она содержится в этом пути. Для нахождения минимального пути между двумя произвольными вершинами для случая, когда все cij 0 можно воспользоваться простым алгоритмом Дейкстры [2]. В общем случае задача решается с помощью алгоритмов Флойда, Форда, Беллмана и др. [2,3,5]. Алгоритмы нахождения минимального пути могут быть использованы для поиска кратчайших путей в ориентированном графе без контуров. Для этого нужно каждой дуге приписать вес, равный единице. 3.8 Деревья Неориентированным деревом (или просто деревом) называется связный граф без циклов. Этому определению эквивалентны, как легко показать, следующие определения: а) дерево есть связный граф, содержащий n вершин и n - 1 ребер; б) дерево есть граф, любые две вершины которого можно соединить простой цепью. Пример 3.17. Графы, изображенные на рис. 3.12, являются деревьями. Рис. 3.12 Если граф несвязный и не имеет циклов, то каждая его связная компонента будет деревом. Такой граф называется лесом. Можно интерпретировать рис. 6.1 как лес, состоящий из трех деревьев. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом. Пример 3.18. 37 Для графа, изображенного на рис. 3.13а), графы на рис. 3.13б) и 3.13в) являются остовными деревьями. Рис. 3.13 Пусть граф G имеет n вершин и m ребер Так как всякое дерево с n вершинами по определению (см. раздел 6.1) имеет n – 1 ребер, то любое остовное дерево графа G получается из этого графа в результате удаления m – (n – 1) = m – n + 1 ребер. Число = m – n + 1 называется цикломатическим числом графа. Теория графов 38 39 40 41 Краткие сведения о математиках Арнольд Владимир Игоревич – математик, академик Российской Академии наук. Беллман Ричард – американский математик. Буль Джордж (1815 – 1864) – английский математик. Основатель математической логики. Гильберт Давид (1862 – 1943) – немецкий математик. Его исследования оказали большое влияние на развитие многих разделов математики, особенно на развитие логических основ математики. Дейкстра Эдсгер (1930 – 2002) – голландский ученый, виднейший специалист в области программирования, лауреат премии Тьюринга. Декарт Рене (1596 – 1650) – французский математик и философ. Впервые ввел понятия переменной, функции, системы координат на плоскости. Кантор Георг (1845 – 1918) – немецкий математик. Разработал теорию бесконечных множеств. Идеи Кантора оказали большое влияние на развитие математики. Колмогоров Андрей Николаевич – советский математик, академике АН СССР. Основополагающее значение имеют работы в области теории вероятностей. Является автором фундаментальных работ по теории множеств, теории меры, конструктивной логике, топологии, механике, теории дифференциальных уравнений, функциональному анализу. Фибоначчи (Леонардо Пизанский) (1180 – 1240) – итальянский математик. Основные работы – трактаты об арифметике, алгебре и геометрии, которые являются первыми произведениями, содержащими задачи на приложения алгебры и геометрии. Эйлер Леонард (1707 – 1783) – математик, физик, механик, астроном. Родился в Швейцарии, с 1726 по 1741 г. и с 1776 по 1783 г. работал в России. 42