Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ДИСКРЕТНАЯ МАТЕМАТИКА
Москва 2002
АННОТАЦИЯ
Методические указания соответствуют программе курса “Дискретная математика” для студентов специальности 230400 Рассматриваются следующие понятия: множества, отношения, функции, графы, булевы (переключательные) функции. Эти понятия иллюстрируются многочисленными примерами. Целью методических указаний является помощь студентам при выпол нении лабораторных и контрольных работ.
Тема 1. Множества
1.1. Основные понятия
1.2. Операции над множествами
1.3. Геометрическое моделирование множеств. Диаграммы Эйлера – Венна.
1.4. Алгебра множеств. Основные тождества алгебры множеств
1.5. Эквивалентность множеств
1.6. Счетные множества
1.7. Множества мощности континуума
Контрольные вопросы к теме 1
Тема 2. Отношения. Функции.
2.1. Отношения. Основные понятия и определения
2.2. Операции над отношениями
2.3. Свойства отношений
2.4. Функции. Основные понятия и определения
Контрольные вопросы к теме 2
Тема 3. Графы.
3.1. Основные характеристики графов
3.2. Матричные способы задания графов
3.3. Изоморфизм графов
3.4. Маршруты, циклы в неориентированном графе
3.5. Пути, контуры в ориентированном графе
3.6. Связность графа
3.7. Экстремальные пути в нагруженных ориентированных графах
3.8. Алгоритм Форда – Беллмана нахождения минимального пути
3.9. Алгоритм нахождения максимального пути
3.10. Деревья. Основные определения
3.11. Минимальные остовные деревья нагруженных графов
Контрольные вопросы к теме 3
Тема 4. Булевы функции
4.1. Определение булевой функции
4.2. Формулы логики булевых функций
4.3. Равносильные преобразования формул
4.4. Двойственность. Принцип двойственности.
4.5. Булева алгебра (алгебра логики). Полные системы булевых функций
4.6. Нормальные формы
4.7. Разложение булевой функции по переменным
4.8. Минимизация формул булевых функций в классе дизъюнктивных
нормальных форм
4.9. Применение алгебры булевых функций к релейно-контактным схемам
Контрольные вопросы к теме 4
Ответы на контрольные вопросы
Указания к выполнению лабораторных работ
Вопросы к экзамену по дисциплине «Дискретная математика»
Список литературы
Краткие сведения о математиках
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.
Если все элементы множества А являются элементами множества В и наоборот, т. е. множества А и В совпадают, то говорят, что А = В.
Если каждый элемент множества А является элементом множества В, говорят, что множество А является подмножеством множества В, и записывают А В или В А. Отметим, что по определению само множество А является своим подмножеством, т.е. А А.
Если А В и В А, то по ранее введенному определению А = В.
Если А В и А В, то А есть собственное подмножество В, А В. Если А не является собственным подмножеством В, то записывают А В.
Пример 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};
Z = {x = 1}– множество, состоящее из одного числа, x = 0.
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В}.
Пример 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, что все рассматриваемые в данной задаче множества являются его подмножествами.
Абсолютным дополнением множества А называется множество всех таких элементов x U, которые не принадлежат множеству А: = U \ A.
Пример 1.13.
Пусть А – множество положительных четных чисел.
Тогда U – множество всех натуральных чисел и - множество положительных нечетных чисел.
1.3. Геометрическое моделирование множеств. Диаграммы Венна
Для наглядного представления множеств и отношений между ними используется диаграммы Венна (иногда их называют кругами Эйлера или диаграммами Эйлера – Венна).
Универсальное множество изображают в виде прямоугольника, а множества, входящие в универсальное множество, – в виде кругов внутри прямоугольника; элементу множества соответствует точка внутри круга (рис 1.1а)).
С помощью диаграмм Венна удобно иллюстрировать операции над множествами.
Рис.1.1
1.4. Алгебра множеств. Основные тождества алгебры множеств
Множества вместе с определенными на них операциями образуют алгебру множеств. Последовательность выполнения операций задается с помощью формулы алгебры множеств. Например, (В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 (BC) = (AB) (AC) (для объединения относительно пересечения);
б) A(BC) = (AB)(AC) (для пересечения относительно объединения).
4. Закон де Моргана.
а) = (дополнение к объединению есть пересечение дополнений);
б) = (дополнение к пересечению есть объединение дополнений).
5. Идемпотентность.
а) A A = A (для объединения);
б) A A = A (для пересечения).
6. Поглощение.
а) A (A B) = A;
б) A (A B) = A.
7. Расщепление (склеивание).
а) (A B) (A ) = A;
б) (A B) (A ) = A.
8. Двойное дополнение.
= A.
9. Закон исключенного третьего.
A = U.
10. Операции с пустым и универсальным множествами.
а) A U = U;
б) A = A;
в) A U = A;
г) A = ;
д) = U;
е) = .
11. А \ В = A .
Чтобы доказать некоторое тождество A = B, нужно доказать, что, во-первых, если x А, то xВ и, во-вторых, если xВ, то x А. Докажем таким образом, например, свойство дистрибутивности для объединения (тождество 3а)):
A (BC) = (AB) (AC).
1. Сначала предположим, что некоторый элемент x принадлежит левой части тождества, т.е. x A (BC), и докажем, что x принадлежит правой части, т.е. x(AB) (AC).
Действительно, пусть x A (BC). Тогда либо x A, либо x BC. Рассмотрим каждую из этих возможностей.
Пусть x A. Тогда x A B и x A C (это верно для любых множеств B и C). Следовательно, x(AB) (AC).
2. Предположим, что некоторый элемент x принадлежит правой части тождества, т.е. x (AB) (AC), и докажем, что x принадлежит левой части, т.е. x A (BC) .
Действительно, пусть x (AB) (AC). Тогда xAB, и одновременно x AC. Если x AB, то либо x A, либо x B, если .x AC, то либо x A, либо x C. Пусть x A, Тогда x A (BC) и утверждение доказано. Если x A, то одновременно должны выполняться условия x B и x C, т.е. x BC. Но тогда x BC и x A (BC), что также доказывает наше утверждение.
Доказательство тождеств можно проиллюстрировать с помощью диаграмм Венна.
Основные тождества алгебры множеств можно использовать для доказательства других тождеств.
Пример 1.14.
Доказать тождество (AB) \ В = A .
Преобразуем левую часть тождества, используя тождество 11:
(AB) \ В = (AB) .
Затем используем закон дистрибутивности (тождество 3б):
(AB) = A B .
Используем закон исключенного третьего (тождество 9):
B = .
Получим
A B = A .
Используем свойство пустого множества (тождество 10б):
A = A .
Тождество доказано.
Пример 1.15.
Доказать тождество:
A \ (В \ C) = (A \ В) (A C).
Множества, стоящие в левой и правой частях тождества, изобразим с помощью диаграмм Эйлера – Венна (рис. 1.2).
Рис. 1.2
Рис. 1.2б) и рис. 1.2д) иллюстрируют равенство множеств A \ (В \ C) и (A \ В) (A C).
Докажем тождество из нашего примера, воспользовавшись тождествами:
А \ В = A , = , = A, A(BC) = (AB)(AC).
Получим:
A \ (В \ C) = A = A = A ( ) = A (C) = (A ) (A C) = (A \ В) (A C).
Основные тождества алгебры множеств можно также использовать для упрощения формул алгебры логики.
Пример 1.16.
Упростить выражение:
(AB) (B) (A).
Используя закон коммутативности (тождество 1б), поменяем местами вторую и третью скобки:
(AB) (B) (A) = (AB) (A) (B).
Применим закон расщепления (тождество 7а) для первой и второй скобок:
(AB) (A) (B) = A (B).
Воспользуемся законом дистрибутивности (тождество 3б):
A (B) = A A B.
Используем закон исключенного третьего (тождество 9):
A = .
Получим
A A B = A B.
Используем свойство пустого множества (тождество 10б):
A B = A B.
Итак,
(AB) (B) (A) = A B.
1.5. Эквивалентность множеств
Определение 1.2. Если каждому элементу множества A сопоставлен единственный элемент множества B и при этом всякий элемент множества B оказывается сопоставленным одному и только одному элементу множества A, то говорят, что между множествами A и B существует взаимно однозначное соответствие. Множества A и B в этом случае называют эквивалентными или равномощными.
Эквивалентность множеств обозначается следующим образом: A B.
Эквивалентность множеств обладает следующим свойством транзитивности.
Если A B и B C, то A C.
Докажем это свойство. Так как A B, то для всякого элемента a А существует единственный элемент b B. Но так как B C, то для всякого элемента b B существует единственный элемент c C. Сопоставим этот элемент элементу a А. Значит, для всякого элемента a А существует единственный элемент c C и для всякого элемента c C существует единственный элемент a А. Следовательно, A C.
Очевидно, что два конечных множества эквивалентны тогда и только тогда, когда количество элементов в них одинаково. Например, множества А = {4, 5, 6} и В = {x, y, z} эквивалентны, A B. Взаимно однозначное соответствие может быть установлено между элементами 4 и x, 5 и y, 6 и z.
Мощностью конечного множества А (обозначается А) называется число элементов этого множества. Например, мощность множества А = {1, 2} равна А= 2.
Пример 1.17.
Ранее (разд. 1.1) мы рассматривали множество всех подмножеств данного множества А, которое называется множеством-степенью и обозначается P(A). Множество P(A) состоит из 2n элементов. Таким образом, P(A) = 2n.
Рассмотрим задачу определения мощности объединения n конечных множеств.
Пусть n = 2 и A и B – два пересекающихся множества. Докажем с помощью диаграммы Эйлера – Венна следующее соотношение:
АB = А + B – АB . (1.1)
Из рис. 1.3 видим, что
АB = n1+n2+n3;
А = n1+n2;
B = n2+n3;
АB = n2.
Рис. 1.3
Очевидно, что n1+n2+n3 = (n1+n2) +(n2+n3) – n2, что и доказывает формулу ().
Формула (1.1) справедлива и для случая, если множества A и B не пересекаются. В этом случае
АB = А + B .
Пусть n = 3 и A, B и С – три пересекающихся множества. В этом случае справедливо следующее соотношение:
АB С= А + B + C – АB – АC – BC + АB C . (1.2)
Из рис. 1.4 видим, что
АB С= n1+n2+n3+n4+n5+n6+n7;
А = n1+n2+n4+n5;
B = n2+n3+n5+n6;
С=n4+n5+n6+n7;
АB = n2+n5;
АC = n4+n5;
BC = n5+n6;
АB C = n5.
Рис. 1.4
Очевидно, что
n1+n2+n3+n4+n5+n6+n7 =(n1+n2+n4+n5) + (n2+n3+n5+n6) +(n4+n5+n6+n7) – (n2+n5) – (n4+n5) – (n5+n6) + n5,
что и доказывает формулу (1.2).
Формула (1.2) справедлива и для случая, если множества A, B и С попарно не пересекаются. В этом случае
АB С= А + B + C .
В общем случае мощность объединения n множеств определяется по формуле:
А1 А2 …Аn= А1+А2+…+ Аn– (А1 А2+ А1 А3+ … +Аn–1Аn)+ АB C + (А1 А2 А3 + … + Аn–2Аn–1Аn) – … + (–1)n – 1 А1А2 …Аn. (1.3)
Эта формула выводится индукцией по n, [3].
Если множества Аi попарно не пересекаются, т.е. Аi Аj = , i j, то получим частный случай формулы (1.3):
А1 А2 …Аn= А1+А2+…+ Аn.
В общем случае справедливо неравенство
А1 А2 …Аn А1+А2+…+ Аn.
Понятие эквивалентности годится и для бесконечных множеств. Пусть, например, A = {1, 2, 3, …, n,…}, B = {– 1, –2, …, –n, …}. Тогда A B. Взаимно однозначное соответствие устанавливается по правилу: элементу n A соответствует элемент – n B, т.е. n – n.
Пример 1.18.
A = {1, 2, 3, …, n,…}, B = {2, 4 …, 2n, …}. Тогда A B. Взаимно однозначное соответствие устанавливается по правилу: n 2 n.
Пример 1.19.
A = {1, 2, 3, …, n,…} – множество натуральных чисел, B = {…, –n, …– 2, –1, 0, 1, 2, …, n, …} – множество всех целых чисел.
Перепишем множество B следующим образом:
B = {0, –1, 1, – 2, 2, …, –n, n, …}, так, что 0 будет на первом месте, –1 на втором, 1 на третьем, –2 на четвертом и т.д. Нетрудно заметить, что отрицательные числа будут стоять на местах с четными номерами, а 0 и положительные числа – на местах с нечетными номерами. Поэтому взаимно однозначное соответствие между множествами A и B устанавливается по правилу: для всякого n 0 элементу a = 2n +1 из множества A (т.е. нечетному элементу) соответствует элемент b = n из множества B; элементу a = 2n из множества A (т.е. четному элементу) соответствует элемент b = –n из множества B. Таким образом, реализуется взаимно однозначное соответствие между множествами A и B: 1 0, 2 –1, 3 1, 4 –2 и т.д.
Примеры 1.18 и 1.19 показывают, что множество может быть эквивалентно своему подмножеству. Так, в примере 1.18 B A, а в примере 1.19 A B. И в том, и в другом случае A B.
Установить эквивалентность множеств, т.е. установить взаимно однозначное соответствие между их элементами можно различными путями. На рис. 1.5 показано, что множества точек двух отрезков [a, b] и [c, d] эквивалентны.
Рис.1.5
Таким же образом можно установить эквивалентность множеств точек двух интервалов. На рис.1.6 показано, что множества точек любого интервала (a, b) эквивалентно множеству точек всей прямой.
Рис. 1.6
Для установления эквивалентности двух множеств можно применять следующую теорему.
Теорема Бернштейна. Если множество A эквивалентно части множества B, а множество B эквивалентно части множества A, то множества A и B эквивалентны.
Применим теорему Бернштейна для доказательства того, что множество точек любого отрезка эквивалентно множеству точек любого интервала.
Пусть A = [a, b] – произвольный отрезок, а B = (c, d) – произвольный интервал.
Пусть A1 = [a1, b1] – любой внутренний интервал отрезка [a, b], A1 A. Тогда A1 B.
Пусть B1 = (c1, d1) – любой внутренний отрезок интервала (c, d), B1 B. Тогда B1 A.
Таким образом, выполняются условия теоремы Бернштейна. Поэтому A B.
Итак, все интервалы, отрезки и вся прямая эквивалентны между собой.
1.6. Счетные множества
Определение 1.3. Множество, эквивалентное множеству натуральных чисел N = {1, 2, 3, …, n,…}, называется счетным.
Можно сказать также, что множество счетно, если его элементы можно перенумеровать.
Пример 1.20.
Следующие множества являются счетными.:
1. A1 = {–1, –2, …, – n, …};
2. A2 = {2, 22, …, 2n,…};
3. A3 = {2, 4, …, 2n,…};
4. A4 = {…, – n, …, – 1, 0, 1, …, n,…};
Чтобы установить счетность некоторого множества, достаточно указать взаимно однозначное соответствие между элементами данного множества и множества натуральных чисел. Для примера 1.19 взаимно однозначное соответствие устанавливается по следующим правилам: для множества A1: –n n; для множества A2: 2n n; для множества A3: 2n n; счетность множества A4 установлена в примере 1.19;
Установить счетность множеств можно также, используя следующие теоремы о счетных множествах (приводятся без доказательств).
Теорема 1. Всякое бесконечное подмножество счетного множества счетно.
Пример 1.21.
Множество A = {3, 6, …, 3n,…} счетно, т.к. A – бесконечное подмножество множества натуральных чисел, A N.
Теорема 2. Объединение конечной или счетной совокупности счетных множеств счетно.
Пример 1.22.
Множество A = {0, 1, …, n,…} неотрицательных целых чисел счетно, множество B = {0, –1, …, –n,…} неположительных целых чисел тоже счетно, поэтому множество всех целых чисел С = АB = {…, –n, …– 2, –1, 0, 1, 2, …, n, …} тоже счетно.
Теорема 3. Множество всех рациональных чисел, т.е. чисел вида , где p и q целые числа, счетно.
Теорема 4. Если А = {a1, a2, …} и B = {b1, b2, …} – счетные множества, то множество всех пар С = {(ak, bn), k = 1, 2,…; n = 1, 2, …} счетно.
Пример 1.23.
Геометрический смысл пары (ak, bn) – точка на плоскости с рациональными координатами (ak, bn). Поэтому можно утверждать, что множество всех точек плоскости с рациональными координатами счетно.
Теорема 5. Множество всех многочленов P(x) = a0 + a1x + a2x2 + … + anxn любых степеней с рациональными коэффициентами a0, a1, a2, … an счетно.
Теорема 6. Множество всех корней многочленов любых степеней с рациональными коэффициентами счетно.
1.7. Множества мощности континуума
Существуют бесконечные множества, элементы которых нельзя перенумеровать. Такие множества называются несчетными.
Теорема Кантора. Множество всех точек отрезка [0, 1] несчетно.
Доказательство.
Пусть множество точек отрезка [0, 1] счетно. Значит, эти точки можно перенумеровать, т. е. расположить в виде последовательности x1, x2 … xn, … .
Рис. 1.7
Разобьем отрезок [0, 1] на три равные части. Где бы ни находилась точка x1, она не может принадлежать всем отрезкам , , . Поэтому среди них есть отрезок 1, не содержащий точку x1 (рис. 1.7). Возьмем этот отрезок 1 и разделим его на три равные части. Среди них всегда есть отрезок 2, не содержащий точку x2. Разделим этот отрезок на три равные части и т. д. Получим последовательность отрезков 1 2 3 …n … . В силу аксиомы Кантора сходится к некоторой точке x при n . По построению эта точка x принадлежит каждому отрезку 1, 2, 3,…, n, …, т. е. она не может совпадать ни с одной из точек x1, x2, … xn, …, т. е. последовательность x1, x2 … xn, …не исчерпывает всех точек отрезка [0, 1], что противоречит первоначальному предположению. Теорема доказана.
Множество, эквивалентное множеству всех точек отрезка [0, 1] называется множеством мощности континуума.
Так как множества точек интервалов, отрезков и всей прямой эквивалентны между собой, то все они имеют мощность континуума.
Чтобы доказать, что данное множество имеет мощность континуума, достаточно указать взаимно однозначное соответствие между данным множеством и множеством точек отрезка, интервала или всей прямой.
Пример 1.24.
Из рис. 1.8 следует, что множество точек параболы y = x2 эквивалентно множеству точек прямой – < x < и, следовательно, имеет мощность континуума.
Рис.1.8
Установить мощность континуума можно также, используя следующие теоремы о множествах мощности континуума (приводятся без доказательств).
Теорема 1. Множество всех подмножеств счетного множества счетно.
Теорема 2. Множество иррациональных чисел имеет мощность континуума.
Теорема 3. Множество всех точек n-мерного пространства при любом n имеет мощность континуума.
Теорема 4. Множество всех комплексных чисел имеет мощность континуума.
Теорема 5. Множество всех непрерывных функций, определенных на отрезке [a, b] имеет мощность континуума.
Итак, мощности бесконечных множеств могут различаться. Мощность континуума больше, чем мощность счетного множества. Ответ на вопрос, существуют ли множества более высокой мощности, чем мощность континуума, дает следующая теорема (приводится без доказательства).
Теорема о множествах высшей мощности. Множество всех подмножеств данного множества имеет более высокую мощность, чем данное множество.
Из этой теоремы следует, что множеств с максимально большой мощностью не существует.
Контрольные вопросы к теме 1
1. Пусть a А. Следует ли отсюда, что {a} А?
2. В каком случае ААÇВ?
3. Назовите множество, которое является подмножеством любого множества.
4. Может ли быть множество эквивалентно своему подмножеству?
5. Мощность какого множества больше: множества натуральных чисел или множества точек отрезка [0, 1]?
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). Бинарное отношение может быть задано перечислением упорядоченных пар или указанием общего свойства упорядоченных пар.
Пример 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 =
Пример 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 А} – отношение задано указанием свойства "меньше" на множестве А .
3. – отношение задано матрицей бинарного отношения C.
Пример 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}.
Определение 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 – множество действительных чисел. Рассмотрим на этом множестве следующие отношения:
1 – " "; 2 – " = "; 3 – " < "; 4 – " "; 5 – " > ".
Тогда
1 = 2 3;
2 = 1 4;
3 = 1 \ 2;
1 = ;
Определим еще две операции над отношениями.
Определение 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}.
= {x, y y = x}.
= {x, z существует такое y, что x, y и y, z } = {x, z существует такое 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, 1 1, 2 1, 3 1, 3 3, 1 3, 1 |
1, 2 1, 3 2, 2 3, 2 3, 3 1, 2 1, 3 |
1, 2 1, 3 1, 2 1, 2 1, 3 3, 2 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 – конечное множество, то главная диагональ матрицы рефлексивного отношения содержит только единицы. Для нашего примера
.
б) Пусть X – множество действительных чисел и отношение равенства. Это отношение рефлексивно, т.к. каждое число равно самому себе.
в) Пусть X – множество людей и отношение "жить в одном городе". Это отношение рефлексивно, т.к. каждый живет в одном городе сам с собой.
Определение 2.10. Отношение называется симметричным на множестве X, если для любых x, y X из xy следует y x.
Очевидно, что симметрично тогда и только тогда, когда = –1.
Пример 2.16.
а) Пусть X – конечное множество, X = {1, 2, 3} и = {1, 1, 1, 2, 1, 3, 2, 1, 3, 1, 3, 3}. Отношение симметрично. Если X – конечное множество, то матрица симметричного отношения симметрична относительно главной диагонали. Для нашего примера
.
б) Пусть X – множество действительных чисел и отношение равенства. Это отношение симметрично, т.к. если x равно y, то и y равно x.
в) Пусть X – множество студентов и отношение "учиться в одной группе". Это отношение симметрично, т.к. если x учится в одной группе с y, то и y учится в одной группе с x.
Определение 2.11. Отношение называется транзитивным на множестве X, если для любых x, y, z X из xy и y z следует x z.
Одновременное выполнение условий xy, y z, x z означает, что пара x, z принадлежит композиции . Поэтому для транзитивности необходимо и достаточно, чтобы множество являлось подмножеством , т. е. .
Пример 2.17.
а) Пусть X – конечное множество, X = {1, 2, 3} и = {1, 1, 1, 2, 2, 3, 1, 3}. Отношение транзитивно, т. к. наряду с парами 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, для которых xy. Класс эквивалентности, порожденный элементом x, обозначается через [x].
Таким образом, [x] = {y X xy}.
Классы эквивалентности образуют разбиение множества X, т. е. систему непустых попарно непересекающихся его подмножеств, объединение которых совпадает со всем множеством X.
Пример 2.19.
а) Отношение равенства на множестве целых чисел порождает следующие классы эквивалентности: для любого элемента x из этого множества [x] = {x}, т.е. каждый класс эквивалентности состоит из одного элемента.
б) Класс эквивалентности, порожденный парой x, y определяется соотношением:
[x, y] = .
Каждый класс эквивалентности, порожденный парой x, y, определяет одно рациональное число.
в) Для отношения принадлежности к одной студенческой группе классом эквивалентности является множество студентов одной группы.
Определение 2.14. Отношение называется антисимметричным на множестве X, если для любых x, y X из xy и 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 есть отношение частичного порядка.
в) Отношение делимости на множестве натуральных чисел есть отношение частичного порядка.
2.4. Функции. Основные понятия и определения
В математическом анализе принято следующее определение функции.
Переменная y называется функцией от переменной x, если по некоторому правилу или закону каждому значению x соответствует одно определенное значение y = f(x). Область изменения переменной x называется областью определения функции, а область изменения переменной y – областью значений функции. Если одному значению x соответствует несколько (и даже бесконечно много значений y), то функция называется многозначной. Впрочем, в курсе анализа функций действительных переменных избегают многозначных функций и рассматривают однозначные функции.
Рассмотрим другое определение функции с точки зрения отношений.
Определение 2.16. Функцией называется любое бинарное отношение, которое не содержит двух пар с равными первыми компонентами и различными вторыми.
Такое свойство отношения называется однозначностью или функциональностью.
Пример 2.22.
а) {<1, 2>, <3, 4>, <4, 4>, <5, 6>} – функция.
б) {<x, y>: x, y R, y = x2} – функция.
в) {<1, 2>, <1, 4>, <4, 4>, <5, 6>} – отношение, но не функция.
Определение 2.17. Если f – функция, то Df – область определения, а Rf – область значений функции f.
Пример 2.23.
Для примера 2.22 а) Df – {1, 3, 4, 5}; Rf – {2, 4, 6}.
Для примера 2.22 б) Df = Rf = (–, ).
Каждому элементу x Df функция ставит в соответствие единственный элемент y Rf. Это обозначается хорошо известной записью y = f(x). Элемент x называется аргументом функции или прообразом элемента y при функции f, а элемент y значением функции f на x или образом элемента x при f.
Итак, из всех отношений функции выделяются тем, что каждый элемент из области определения имеет единственный образ.
Определение 2.18. Если Df = X и Rf = Y, то говорят, что функция f определена на X и принимает свои значения на Y, а f называют отображением множества X на Y (X Y).
Определение 2.19. Функции f и g равны, если их область определения – одно и то же множество D, и для любого x D справедливо равенство f(x) = g(x).
Это определение не противоречит определению равенства функций как равенства множеств (ведь мы определили функцию как отношение, т. е. множество): множества f и g равны, тогда и только тогда, когда они состоят из одних и тех же элементов.
Определение 2.20. Функция (отображение) f называется сюръективной или просто сюръекцией, если ля любого элемента y Y существует элемент x X, такой, что y = f(x).
Таким образом, каждая функция f является сюръективным отображением (сюръекцией) Df Rf.
Если f – сюръекция, а X и Y – конечные множества, то .
Определение 2.21. Функция (отображение) f называется инъективной или просто инъекцией или взаимно однозначной, если из f(a) = f(b) следует a = b.
Определение 2.22. Функция (отображение) f называется биективной или просто биекцией, если она одновременно инъективна и сюръективна.
Если f – биекция, а X и Y – конечные множества, то =.
Определение 2.23. Если область значений функции Df состоит из одного элемента, то f называется функцией-константой.
Пример 2.24.
а) f(x) = x2 есть отображение множества действительных чисел на множество неотрицательных действительных чисел. Т.к. f(–a) = f(a), и a –a, то эта функция не является инъекцией.
б) Для каждого xR = (–, ) функция f(x) = 5 – функция-константа. Она отображает множество R на множество {5}. Эта функция сюръективна, но не инъективна.
в) f(x) = 2x + 1 является инъекцией и биекцией, т.к. из 2x1 +1 = 2x2 +1 следует x1 = x2.
Определение 2.24. Функция, реализующая отображение X1 X2 ... Xn Y называется n-местной функцией.
Пример 2.25.
а) Сложение, вычитание, умножение и деление являются двуместными функциями на множестве R действительных чисел, т. е. функциями типа R2 R.
б) f(x, y) = – двуместная функция, реализующая отображение R (R \ ) R. Эта функция не является инъекцией, т.к. f(1, 2) = f(2, 4).
в) Таблица выигрышей лотереи задает двуместную функцию, устанавливающую соответствие между парами из N2 (N – множество натуральных чисел) и множеством выигрышей.
Поскольку функции являются бинарными отношениями, то можно находить обратные функции и применять операцию композиции. Композиция любых двух функций есть функция, но не для каждой функции f отношение f–1 является функцией.
Пример 2.26.
а) f = {1, 2>, <2, 3>, <3, 4>, <4, 2>} – функция.
Отношение f–1 = {<2, 1>, <3, 2>, <4, 3>, <2, 4>} не является функцией.
б) g = {<1, a>, <2, b>, <3, c>, <4, D>} – функция.
g-1 = {<a, 1>, <b, 2>, <c, 3>, <D, 4>} тоже функция.
в) Найдем композицию функций f из примера а) и g-1 из примера б). Имеем g-1f = {<a, 2>, <b, 3>, <c, 4>, <d, 2>}.
fg-1 = .
Заметим, что (g-1f)(a) = f(g-1(a)) = f(1) = 2; (g-1f)(c) = f(g-1(c)) = f(3) = 4.
Элементарной функцией в математическом анализе называется всякая функция f, являющаяся композицией конечного числа арифметических функций, а также следующих функций:
1) Дробно-рациональные функции, т.е. функции вида
a0 + a1x + ... + anxn
b0 + b1x + ... + bmxm.
2) Степенная функция f(x) = xm, где m – любое постоянное действительное число.
3) Показательная функция f(x) = ex.
4) логарифмическая функция f(x) = logax, a >0, a 1.
5) Тригонометрические функции sin, cos, tg, ctg, sec, csc.
6) Гиперболические функции sh, ch, th, cth.
7) Обратные тригонометрические функции arcsin, arccos и т.д.
Например, функция log2(x3 +sincos3x) является элементарной, т.к. она есть композиция функций cosx, sinx, x3, x1 + x2, logx, x2.
Выражение, описывающее композицию функций, называется формулой.
Для многоместной функции справедлив следующий важный результат, полученный А. Н. Колмогоровым и В. И. Арнольдом в 1957 г. и являющийся решением 13-ой проблемы Гильберта:
Теорема. Всякая непрерывная функция n переменных представима в виде композиции непрерывных функций двух переменных.
Способы задания функций
1. Наиболее простой способ задания функций – это таблицы (табл. 2.2):
Таблица 2.2
|
x |
x1 |
x2 |
... |
xn |
|
f(x) |
f(x1) |
f(x2) |
... |
f(xn) |
Пример 2.27.
Бросается игральная кость. Пусть k – число выпавших очков, а p(k) – вероятность того, что при случайном бросании кости выпадет k очков, k = 1, 2, ..., 6.
В этом случае функция p(k) может быть задана следующей таблицей (табл. 2.3):
Таблица 2.3
|
k |
1 |
2 |
3 |
4 |
5 |
6 |
|
p(k) |
1/6 |
1/6 |
1/6 |
1/6 |
1/6 |
1/6 |
Однако, таким образом могут быть заданы функции, определенные на конечных множествах.
Если функция, определенная на бесконечном множестве (отрезке, интервале), задана в конечном числе точек, например, в виде тригонометрических таблиц, таблиц специальных функций и т.п., то для вычисления значений функций в промежуточных точках пользуются правилами интерполяции.
2. Функция может быть задана в виде формулы, описывающей функцию как композицию других функций. Формула задает последовательность вычисления функции.
Пример 2.28.
f(x) = sin(x + x) является композицией следующих функций:
g(y) = y; h(u, v) = u + v; w(z) = sinz.
3. Функция может быть задана в виде рекурсивной процедуры. Рекурсивная процедура задает функцию, определенную на множестве натуральных чисел, т. е. f(n), n = 1, 2,... следующим образом: а) задается значение f(1) (или f(0)); б) значение f(n + 1) определяется через композицию f(n) и других известных функций. Простейшим примером рекурсивной процедуры является вычисление n!: а) 0! = 1; б) (n + 1)! = n!(n + 1). Многие процедуры численных методов являются рекурсивными процедурами.
4. Возможны способы задания функции, не содержащие способа вычисления функции, а только описывающие ее. Например:
fM(x) =
Функция fM(x) – характеристическая функция множества M.
Итак, по смыслу нашего определения, задать функцию f – значит задать отображение X Y, т.е. определить множество XY, поэтому вопрос сводится к заданию некоторого множества. Однако можно определить понятие функции, не используя языка теории множеств, а именно: функция считается заданной, если задана вычислительная процедура, которая по заданному значению аргумента находит соответствующее значение функции. Функция, определенная таким образом, называется вычислимой.
Пример 2.29.
Процедура определения чисел Фибоначчи, задается соотношением
Fn = Fn-1 + Fn-2 (n ³ 2) (2.1)
с начальными значениями F0 = 1, F1 = 1.
Формула (2.1) вместе с начальными значениями определяет следующий ряд чисел Фибоначчи:
|
n |
0 1 2 3 4 5 6 7 8 9 10 11 … |
|
Fn |
1 1 2 3 5 8 13 21 34 55 89 144 … |
Вычислительная процедура определения значения функции по заданному значению аргумента есть не что иное, как алгоритм.
1. Укажите способы задания бинарного отношения.
2. Главная диагональ матрицы какого отношения содержит только единицы?
3. Для какого отношения всегда выполняется условие = –1?
4. Для какого отношения всегда выполняется условие .
5. Ввести отношения эквивалентности и частичного порядка на множестве всех прямых на плоскости.
6. Укажите способы задания функций.
7. Какое из следующих утверждений справедливо?
а) Всякое бинарное отношение есть функция.
б) Всякая функция есть бинарное отношение.
Первая работа по теории графов принадлежащая Эйлеру, появилась в 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 )}.
Рис. 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, а ее концом - вершина x2; вершина x1 инцидентна дугам a1 и a2; G(x1) = {x2, x3}, G(x2) =Æ, G-1(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 =
Пример 3.5.
Матрица смежности графа, изображенного на рис. 3.1, имеет вид:
A =
Пример 3.6.
Матрица смежности ориентированного графа, изображенного на рис. 3.2, имеет вид:
A =
Матрица смежности полностью задает граф.
Матрицей инцидентности B = (bij) ориентированного графа называет ся прямоугольная матрица (n ´ m), где n – число вершин, m – число ребер, у которой
bi =
Для неориентированного графа матрица инцидентности B задается следующим образом:
bi =
Пример 3.7.
Матрица инцидентности графа, изображенного на рис. 3.1, имеет вид:
B =
Пример 3.8.
Матрица инцидентности ориентированного графа, изображенного на рис. 3.2, имеет вид:
B =
Матрица инцидентности, также, как и матрица смежности, полностью задает граф.
Матрицы смежности и инцидентности удобны для задания графов на ЭВМ.
Основные свойства матриц смежности и инцидентности
1. Матрица смежности неориентированного графа является симметрич ной. Для ориентированного графа это, вообще говоря, неверно.
2. Сумма элементов i - ой строки или i -го столбца матрицы смежности неориентиро ванного графа равна степени вершины xi.
3. Сумма элементов i - ой строки матрицы смежности ориентиро ванного графа равна числу дуг, исходящих из xi.
4. Сумма элементов i - го столбца матрицы смежности ориентиро ванного графа равна числу дуг, входящих в вершину xi.
5. Сумма строк матрицы инцидентности ориентированного графа явля ется нулевой строкой.
Итак, возможны следующие различные способы задания графа:
а) посредством графического изображения;
б) указанием множества вершин и множества ребер (дуг);
в) матрицей смежности;
г) матрицей инцидентности.
3.3. Изоморфизм графов
Графы G1 = (X1, A1) и G2 = (X2, A2) изоморфны, если существует взаимно однозначное соответствие между множествами вершин X1 и X2, та кое, что любые две вершины одного графа соединены тогда и только тог да, когда соответствующие вершины соединены в другом графе.
Пример 3.9
Графы, изображенные на рис. 3.4 являются изоморфными.
Рис. 3.4
Изоморфные графы отличаются только нумерацией вершин. Матрицы смежности двух изоморфных графов могут быть получены одна из другой перестановкой строк и столбцов. Чтобы узнать, являются ли два графа изоморфными, нужно произвести все возможные перестановки строк и столбцов матрицы смежности одного из графов. Если после какой-нибудь перестановки получится матрица смежности второго графа, то эти графы изоморфны. Чтобы убедиться, что графы неизоморфны, надо выполнить все n! возможных перестановок строк и столбцов.
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
3.5. Пути, контуры в ориентированном графе
Понятия пути, контура в ориентированном графе аналогичны понятиям маршрута, цикла в неориентированном графе.
Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги.
Число дуг пути называется длиной пути.
Путь называется контуром, если его начальная вершина совпадает с конечной вершиной.
Путь (контур), в котором все дуги различны, называется простым.
Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным.
Следует усвоить, что понятиям ребра, маршрута, цепи, цикла в неориентированном графе соответствуют понятия дуги, пути, ориентированной цепи, контура в ориентированном графе. Для лучшего запоминания приведем эти термины в таблице.
|
Неориентированный граф |
Ориентированный граф |
|
ребро маршрут цикл |
дуга путь контур |
Пример 3.12.
В приведенном на рис 3.7 графе выделим следующие пути:
(x1,x2,x3,x4) – простой элементарный путь, т.к. каждая вершина и каждая дуга используются не более одного раза;
(x2,x5,x6,x7,x2) – простой элементарный контур, т.к. это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны.
Рис. 3.7
3.6. Связность графа
Неориентированный граф называется связным, если каждая пара различных вершин может быть соединена по крайней мере одной цепью.
Ориентированный граф называется сильно связным, если для любых двух его вершин xi и xj существует хотя бы один путь, соединяющий xi с xj.
Ориентированный граф называется односторонне связным, если для любых двух его вершин по крайней мере одна достижима из другой.
Компонентой связности неориентированного графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа (максимально связный подграф).
Компонентой сильной связности ориентированного графа называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа данного графа (максимально сильно связный подграф).
Компонентой одностронней связности неориентированного графа называется его односторонне связный подграф, не являющийся собственным подграфом никакого другого односторонне связного подграфа данного графа (максимально односторонне связный подграф).
Пусть G = (X, A) неориентирован ный граф с множеством вершин X = {x1,...,xn}. Квадратная матрица S = (sij) порядка n, у которой
sij =
называется матрицей связности графа G.
Для ориентированного графа квадратная матрица T = (tij) порядка n, у кото рой
tij =
называется матрицей односторонней связности (достижимости).
Квадратная матрица S = (sij) порядка n, у которой
sij =
называется матрицей сильной связности.
Пример 3.13.
У неориентированного графа, изображенного на рис. 3.8 две компоненты связности. Первая компонента связности включает вершины x1, x2, x4, x5, а вторая состоит из одной вершины x3.
Рис.3.8
Матрица связности этого графа имеет вид:
S =
Мы видим, что 1-ая, 2-ая, 4-ая и 5-ая строки матрицы S одинаковы.
Пример 3.14.
У ориентированного графа, изображенного на рис. 3.9 две компоненты сильной связности. Первая компонента связности включает вершины x1, x2, x3, x5, а вторая состоит из одной вершины x4. Действительно, для любой пары вершин из множества {x1, x2, x3, x5} существует хотя бы один путь, соединяющий эти вершины. Например, путь (x1, x2, x5, x3, x1) соединяет все эти вершины. Из вершины x4 нет пути ни в одну вершину графа.
Рис. 3.9
Матрица сильной связности этого графа имеет вид:
S =
Мы видим, что 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 имеет вид:
C =
Длина пути (x1, x2, x5, x4) равна 1 + 5 + 6 = 12.
Для ненагруженного графа введем понятие кратчайшего пути. Это путь с минимальным общим числом дуг, причем каждая дуга считается столько раз, сколько она содержится в этом пути.
Для нахождения минимального пути между двумя произвольными верши нами для случая, когда все cij ³ 0 можно воспользоваться простым алгоритмом Дейкстры [2]. В общем случае задача решается с помощью ал горитмов Флойда, Форда, Беллмана и др. [2,3,5].
Алгоритмы нахождения минимального пути могут быть использованы для поиска кратчайших путей в ориентированном графе без контуров. Для этого нужно каждой дуге приписать вес, равный единице.
3.8 Алгоритм Форда – Беллмана нахождения минимального пути
Алгоритм 3.1 (Алгоритм Форда – Беллмана).
Основными вычисляемыми величинами этого алгоритма являются величины lj(k), где i = 1, 2, … , n (n – число вершин графа); k = 1, 2, … , n – 1. Для фиксированных i и k величина lj(k) равна длине минимального пути, ведущего из заданной начальной вершины х1 в вершину хi и содержащего не более k дуг.
Шаг 1. Установка начальных условий.
Ввести число вершин графа n и матрицу весов C = (cij).
Шаг 2. Положить k = 0. Положить li(0) = ¥ для всех вершин, кроме х1; положить l1(0) = 0.
Шаг 3. В цикле по k, k = 1,..., n – 1, каждой вершине xi на k-ом шаге приписать индекс li(k) по следу ющему правилу:
li(k) = {lj(k – 1) + cji} (3.1)
для всех вершин, кроме х1, положить l1(k) = 0.
В результате работы алгоритма формируется таблица индексов li(k), i = 1, 2, … , n, k = 0, 1, 2, … , n – 1. При этом li(k) определяет длину минимального пути из первой вершины в i-ую, содержащего не более k дуг.
Шаг 5. Восстановление минимального пути.
Для любой вершины xs предшествующая ей вершина xr определяется из соотношения:
lr(n – 2) + crs = ls(n – 1), xrÎ G-1(xs), (3.2)
где G-1(xs) - прообраз вершины xs.
Для найденной вершины xr предшествующая ей вершина xq определяется из соотношения:
lq(n – 3) + cqr = lr(n – 2), xqÎ G-1(xr),
где G-1(xr) - прообраз вершины xr, и т. д.
Последовательно применяя это соотношение, начиная от последней вершины xi , найдем минимальный путь.
Пример 3.15.
С помощью алгоритма 3.1 найдем минимальный путь из верши ны х1 в вершину х3 в графе, изображенном на рис. 3.10.
Рассмотрим подробно работу алгоритма Форда – Беллмана для этого примера. Значения индексов li(k) будем заносить в таблицу индексов (табл. 3.1).
Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа имеет вид:
C = .
Шаг 2. Положим k = 0, l1(0) = 0, l2(0) = l3(0) = l4(0) = l5(0) = ¥. Эти значения занесем в первый столбец табл. 3.1.
Шаг 3.
k = 1.
l1(1) = 0.
Равенство (7.1) для k = 1 имеет вид:
li(1) = {lj(0) + cji}.
l2(1) = min{l1(0) + c12; l2(0) + c22; l3(0) + c32; l4(0) + c42; l5(0) + c52;} = min{0 + 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = 1.
l3(1) = min{l1(0) + c13; l2(0) + c23; l3(0) + c33; l4(0) + c43; l5(0) + c53;} = min{0 + ¥ ; ¥ + 8; ¥ + ¥; ¥ + 2; ¥ + ¥} = ¥ .
l4(1) = min{l1(0) + c14; l2(0) + c24; l3(0) + c34; l4(0) + c44; l5(0) + c54;} = min{0 + ¥ ; ¥ + 7; ¥ + 1; ¥ + ¥; ¥ + 4} = ¥ .
l5(1) = min{l1(0) + c15; l2(0) + c25; l3(0) + c35; l4(0) + c45; l5(0) + c55;} = min{0 + 3; ¥ + 1; ¥ – 5; ¥ + ¥; ¥ + ¥} = 3.
Полученные значения li(1) занесем во второй столбец табл. 3.1. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин li(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги.
k = 2.
l1(2) = 0.
Равенство (3.1) для k = 2 имеет вид:
li(2) = {lj(1) + cji}.
l2(2) = min{0 + 1; 1 + ¥; ¥ + ¥; ¥ + ¥; 3 + ¥} = 1.
l3(2) = min{0 + ¥ ; 1 + 8; ¥ + ¥; ¥ + 2; 3 + ¥} = 9 .
l4(2) = min{0 + ¥ ; 1 + 7; ¥ + 1; ¥ + ¥; 3 + 4} = 7 .
l5(2) = min{0 + 3; 1 + 1; ¥ – 5; ¥ + ¥; 3 + ¥} = 2.
Полученные значения li(2) занесем в третий столбец табл. 3.1. Величины li(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг.
k = 3.
l1(3) = 0.
Равенство (3.1) для k = 3 имеет вид:
li(3) = {lj(2) + cji}.
l2(3) = min{0 + 1; 1 + ¥; 9 + ¥; 7 + ¥; 2 + ¥} = 1.
l3(3) = min{0 + ¥ ; 1 + 8; 9 + ¥; 7 + 2; 2 + ¥} = 9 .
l4(3) = min{0 + ¥ ; 1 + 7; 9 + 1; 7 + ¥; 2 + 4} = 6 .
l5(3) = min{0 + 3; 1 + 1; 9 – 5; 7 + ¥; 2 + ¥} = 2.
Полученные значения li(3) занесем в четвертый столбец табл. 3.1. Величины li(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг.
k = 4.
l1(4) = 0.
Равенство (3.1) для k = 4 имеет вид:
li(4) = {lj(3) + cji}.
l2(4) = min{0 + 1; 1 + ¥; 9 + ¥; 6 + ¥; 2 + ¥} = 1.
l3(4) = min{0 + ¥ ; 1 + 8; 9 + ¥; 6 + 2; 2 + ¥} = 8 .
l4(4) = min{0 + ¥ ; 1 + 7; 9 + 1; 6 + ¥; 2 + 4} = 6 .
l5(4) = min{0 + 3; 1 + 1; 9 – 5; 6 + ¥; 2 + ¥} = 2.
Полученные значения li(4) занесем в пятый столбец табл. 3.1. Величины li(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг.
|
I (номер вершины) |
li(0) li(1) li(2) li(3) li(4) |
|
1 2 3 4 5 |
0 0 0 0 0 ¥ 1 1 1 1 ¥ ¥ 9 9 8 ¥ ¥ 7 6 6 ¥ 3 2 2 2 |
Шаг 5. Восстановление минимального пути.
Для последней вершины x3 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =3:
lr(3) + cr3 = l3(4), xrÎ G-1(x3), (3.3)
где G-1(x3) - прообраз вершины x3.
G-1(x3) = {x2, x4}.
Подставим в (3.3) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется:
l2(3) + c23 = 1 + 8 ¹ l3(4) = 8,
l4(3) + c43 = 6 + 2 = l3(4) = 8.
Таким образом, вершиной, предшествующей вершине x3, является вершина x4.
Для вершины x4 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4:
lr(2) + cr4 = l4(3), xrÎ G-1(x4), (3.4)
где G-1(x4) - прообраз вершины x4.
G-1(x4) = {x2, x3, x5}.
Подставим в (3.4) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется:
l2(2) + c24 = 1 + 7 ¹ l4(3) = 6,
l3(2) + c34 = 1 + 1 ¹ l4(3) = 6,
l5(2) + c54 = 2 + 4 = l4(3) = 6,
Таким образом, вершиной, предшествующей вершине x4, является вершина x5.
Для вершины x5 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =5:
lr(1) + cr5 = l5(2), xr G-1(x5), (3.5)
где G-1(x5) - прообраз вершины x5.
G-1(x5) = {x1, x2}.
Подставим в (3.5) последовательно r = 1 и r = 2, чтобы определить, для какого r это равенство выполняется:
l1(1) + c15 = 0 + 3 ¹ l5(2) = 2,
l2(1) + c25 = 1 + 1 = l5(2) = 2,
Таким образом, вершиной, предшествующей вершине x5, является вершина x2.
Для вершины x2 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2:
lr(0) + cr2 = l2(1), xr G-1(x2), (3.6)
где G-1(x2) - прообраз вершины x2.
G-1(x2) = {x1}.
Подставим в (3.6) r = 1, чтобы определить, выполняется ли это равенство:
l1(0) + c12 = 0 + 1 = l2(1) = 1.
Таким образом, вершиной, предшествующей вершине x2, является вершина x1.
Итак, найден минимальный путь – x1, x2, x5, x4, x3, его длина равна 8.
3.9. Алгоритм нахождения максимального пути
При решении некоторых практических задач возникает необходимость поиска максимального пути (пути с наибольшей суммой длин дуг). Такая задача сводится к задаче нахождения минимального пути заменой знаков при длинах дуг (в матрице весов C) на противоположные. При этом необходимым является требование отсутствия в ориентированном графе контуров положительной длины.
Пример 3.16.
С помощью модифицированного алгоритма 3.1 найдем максимальный путь из верши ны х1 в вершину х3 в графе, изображенном на рис. 3.11.
Рис. 3.11
Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа после замены знаков при длинах дуг на противоположные имеет вид:
C = .
Шаг 2. Положим k = 0, l1(0) = 0, l2(0) = l3(0) = l4(0) = l5(0) = . Эти значения занесем в первый столбец табл. 3.2.
Шаг 3.
k = 1.
l1(1) = 0.
Равенство (3.1) для k = 1 имеет вид:
li(1) = {lj(0) + cji}.
l2(1) = min{l1(0) + c12; l2(0) + c22; l3(0) + c32; l4(0) + c42; l5(0) + c52;} = min{0 – 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = –1.
l3(1) = min{l1(0) + c13; l2(0) + c23; l3(0) + c33; l4(0) + c43; l5(0) + c53;} = min{0 + ¥ ; ¥ – 8; ¥ + ¥; ¥ – 2; ¥ + ¥} = ¥ .
l4(1) = min{l1(0) + c14; l2(0) + c24; l3(0) + c34; l4(0) + c44; l5(0) + c54;} = min{0 + ¥ ; ¥ – 7; ¥ + ¥; ¥ + ¥; ¥ – 4} = ¥ .
l5(1) = min{l1(0) + c15; l2(0) + c25; l3(0) + c35; l4(0) + c45; l5(0) + c55;} = min{0 – 3; ¥ – 1; ¥ + 5; ¥ + ¥; ¥ + ¥} = –3.
Полученные значения li(1) занесем во второй столбец табл. 3.2. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин li(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги.
k = 2.
l1(2) = 0.
Равенство (3.1) для k = 2 имеет вид:
li(2) = {lj(1) + cji}.
l2(2) = min{0 – 1; –1 + ¥; ¥ + ¥; ¥ + ¥; –3 + ¥} = –1.
l3(2) = min{0 + ¥ ; –1 – 8; ¥ + ¥; ¥ – 2; –3 + ¥} = –9 .
l4(2) = min{0 + ¥ ; –1 – 7; ¥ + ¥; ¥ + ¥; –3 – 4} = –8 .
l5(2) = min{0 – 3; –1 – 1; ¥ + 5; ¥ + ¥; –3 + ¥} = –3.
Полученные значения li(2) занесем в третий столбец табл. 3.2. Величины li(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг.
k = 3.
l1(3) = 0.
Равенство (3.1) для k = 3 имеет вид:
li(3) = {lj(2) + cji}.
l2(3) = min{0 – 1; – 1 + ¥; – 9 + ¥; –8 + ¥; – 3 + ¥} = – 1.
l3(3) = min{0 + ¥ ; – 1 – 8; – 9 + ¥; –8 – 2; – 3 + ¥} = – 10 .
l4(3) = min{0 + ¥ ; – 1 – 7; – 9 + ¥; –8 + ¥; – 3 – 4} = – 8 .
l5(3) = min{0 – 3; – 1 – 1; – 9 + 5; –8 + ¥; – 3 + ¥} = – 4.
Полученные значения li(3) занесем в четвертый столбец табл. 3.2. Величины li(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг.
k = 4.
l1(4) = 0.
Равенство (3.1) для k = 4 имеет вид:
li(4) = {lj(3) + cji}.
l2(4) = min{0 – 1; – 1 + ¥ ; – 10 + ¥; – 8 + ¥; – 4 + ¥} = – 1.
l3(4) = min{0 + ¥ ; – 1 – 8; – 10 + ¥; – 8 – 2; – 4 + ¥} = – 10 .
l4(4) = min{0 + ¥ ; – 1 – 7; – 10 + ¥; – 8 + ¥; – 4 – 4} = – 8 .
l5(4) = min{0 – 3; – 1 – 1; – 10 + 5; – 8 + ¥; – 4 + ¥} = – 5.
Полученные значения li(4) занесем в пятый столбец табл. 3.2. Величины li(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг.
|
i(номер вершины) |
li(0) li(1) li(2) li(3) li(4) |
|
1 2 3 4 5 |
0 0 0 0 0 ¥ – 1 – 1 – 1 1 ¥ ¥ – 9 – 10 – 10 ¥ ¥ – 8 – 8 – 8 ¥ – 3 –3 – 4 – 5 |
Заменив в табл. 3.2 отрицательные числа положительными, получим таблицу индексов максимальных путей (табл. 3.3). При этом li(k) определяет длину максимального пути из первой вершины в i-ую, содержащего не более k дуг.
|
i(номер вершины) |
li(0) li(1) li(2) li(3) li(4) |
|
1 2 3 4 5 |
0 0 0 0 0 ¥ 1 1 1 1 ¥ ¥ 9 10 10 ¥ ¥ 8 8 8 ¥ 3 3 4 5 |
Шаг 5. Восстановление максимального пути производится по тому же правилу, что и для минимального пути.
Длина максимального пути равна 10. Этот путь состоит из трех дуг, т. к. li(3) = li(4) = 10. Поэтому в соотношении (3.2) будет выполнено, начиная с n – 1.
Учитывая это замечание, для последней вершины x3 предшествующую ей вершину xr определим из соотношения (3.2) полученного при s =3:
lr(2) + cr3 = l3(3), (3.7)
xrÎ G-1(x3), где G-1(x3) - прообраз вершины x3.
G-1(x3) = {x2, x4}.
Подставим в (3.7) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется:
l2(2) + c23 = 1 + 8 ¹ l3(4) = 10,
l4(2) + c43 = 8 + 2 = l3(4) = 10.
Таким образом, вершиной, предшествующей вершине x3, является вершина x4.
Для вершины x4 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4:
lr(1) + cr4 = l4(2), xrÎ G-1(x4), (3.8)
где G-1(x4) - прообраз вершины x4.
G-1(x4) = {x2, x5}.
Подставим в (3.8) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется:
l2(1) + c24 = 1 + 7 = l4(3) = 8,
l5(1) + c54 = 3 + 4 ¹ l4(3) = 8,
Таким образом, вершиной, предшествующей вершине x4, является вершина x2.
Для вершины x2 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2:
lr(0) + cr2 = l2(1), xr G-1(x2), (3.9)
где G-1(x2) - прообраз вершины x2.
G-1(x2) = {x1}.
Подставим в (3.9) r = 1, чтобы определить, выполняется ли это равенство:
l1(1) + c12 = 0 + 1 = l2(1) = 1.
Таким образом, вершиной, предшествующей вершине x2, является вершина x1.
Итак, найден максимальный путь – x1, x2, x4, x3, его длина равна 10.
3.10. Деревья.. Основные определения
Неориентированным деревом (или просто деревом) называется связный граф без циклов. Этому определению эквивалентны, как легко показать, следующие определения:
а) дерево есть связный граф, содержащий n вершин и n - 1 ребер;
б) дерево есть граф, любые две вершины которого можно соединить простой цепью.
Пример 3.17.
Графы, изображенные на рис. 3.12, являются деревьями.
Рис. 3.12
Если граф несвязный и не имеет циклов, то каждая его связная компонента будет деревом. Такой граф называется лесом. Можно интерпретировать рис. 6.1 как лес, состоящий из трех деревьев.
Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пример 3.18.
Для графа, изображенного на рис. 3.13а), графы на рис. 3.13б) и 3.13в) являются остовными деревьями.
Рис. 3.13
Пусть граф G имеет n вершин и m ребер Так как всякое дерево с n вершинами по определению (см. раздел 6.1) имеет n – 1 ребер, то любое остовное дерево графа G получается из этого графа в результате удаления m – (n – 1) = m – n + 1 ребер. Число g = m – n + 1 называется цикломатическим числом графа.
3.11. Минимальные остовные деревья нагруженных графов
Граф G = (X, A) называется нагруженным, если для каждого ребра (xi,xj) определена его длина (или вес) cij.
Пусть G - связный нагруженный граф. Задача построения минимально го остовного дерева заключается в том, чтобы из множества остовных де ревьев найти дерево, у которого сумма длин ребер минимальна.
Приведем типичные случаи, когда возникает необходимость построе ния минимального остовного дерева графа.
а) Нужно соединить n городов железнодорожными линиями (автомобиль ными дорогами, линиями электропередач, сетью трубопроводов и т.д.) так, чтобы суммарная длина линий или стоимость была бы минимальной.
б)Требуется построить схему электрической сети, в которой клеммы должны быть соединены с помощью проводов наименьшей общей длины.
Зада чу построе ния минимального остовного дерева можно решить с помощью следующего алгоритма.
Алгоритм 3.2 (Алгоритм Краскала).
Шаг 1. Установка начальных значений.
Вводится матрица длин ребер C графа G.
Шаг 2. Выбрать в графе G ребро минимальной длины. Построить граф G2, состоящий из данного ребра и инцидентных ему вершин. Положить i = 2.
Шаг 3. Если i = n, где n - число ребер графа, то закончить работу (задача решена), в противном случае перейти к шагу 4.
Шаг 4. Построить граф Gi +1, добавляя к графу Gi новое ребро мини мальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно какой-нибудь вершине графа Gi и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в Gi. Вместе с этим ребром включаем в Gi +1 и инцидентную ему вершину, не содержащуюся в Gi. Присваиваем i:= i +1 и переходим к шагу 3.
Пример 3.19.
Найдем минимальное остовное дерево для графа, изображенного на рис. 3.14.
Рис. 3.14
Шаг 1. Установка начальных значений.
Введем матрицу длин ребер C:
С =.
Шаг 2. Выберем ребро минимальной длины. Минимальная длина ребра равна единице. Таких ребер три: (x1, x2), (x1, x4), (x2, x4). В этом случае можно взять любое. Возьмем (x1, x2). Построим граф G2, состоящий из данного ребра и инцидентных ему вершин x1 и x2. Положим i = 2.
Шаг 3. Так как n = 5, то i ¹ n, поэтому переходим к шагу 4.
Шаг 4. Строим граф G3, добавляя к графу G2 новое ребро мини мальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно одной из вершин x1, x2 и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в G2 т. е. одной из вершин x3, x4, x5. Таким образом, нужно выбрать ребро мини мальной длины из ребер (x1, x4), (x1, x5), (x2, x3), (x2, x4), (x2, x5). Таких ребер длины единица два: (x1, x4) и (x2, x4). Можно выбрать любое. Возьмем (x1, x4). Вместе с этим ребром включаем в G3 вершину x4, не содержащуюся в G2. Полагаем i = 3 и переходим к шагу 3.
Шаг 3. Так как i ¹ n, поэтому переходим к шагу 4.
Шаг 4. Строим граф G4, добавляя к графу G3 новое ребро мини мальной длины из ребер (x1, x5), (x2, x3), (x2, x5), (x4, x5). Такое ребро длины два одно: (x2, x3). Вместе с этим ребром включаем в G4 вершину x3, не содержащуюся в G3. Полагаем i = 4 и переходим к шагу 3.
Шаг 3. Так как i ¹ n, поэтому переходим к шагу 4.
Шаг 4. Строим граф G5, добавляя к графу G3 новое ребро мини мальной длины из ребер (x1, x5), (x2, x5), (x4, x5). Таких ребер длины три два: (x2, x5) и (x4, x5). Возьмем (x2, x5). Вместе с этим ребром включаем в G5 вершину x5, не содержащуюся в G4. Полагаем i = 5 и переходим к шагу 3.
Шаг 3. Так как i = n, то граф G5 – искомое минимальное остовное дерево. Суммарная длина ребер равна 1 + 1 + 2 + 3 = 7.
Процесс построения минимального остовного дерева изображен на рис. 3.15.
Рис. 3.15
Контрольные вопросы к теме 3
1. Какое из двух утверждений верно: а) ориентированный граф яв ляется частным случаем неориентированного графа; б) неориентированный граф является частным случаем ориентированного графа?
2. Перечислите все возможные способы задания графов.
3. Что характеризует сумма элементов столбца матрицы смежности неориентированного графа?
4. Что характеризует сумма элементов строки матрицы смежности неориентированного графа?
5. Что характеризует сумма элементов столбца матрицы смежности ориентированного графа?
6. Что характеризует сумма элементов строки матрицы смежности ориентированного графа
7. Всегда ли матрица смежности симметрична относительно главной диагонали?
8. Как по матрице смежности определить число ребер неориентиро ванного графа?
9. Как по матрице инцидентности, не рисуя граф, определить его матрицу смежности?
10. Может ли матрица быть матрицей смежности неориентированного графа?
11. Какие из следующих утверждений являются правильными: а) если матрица смежности несимметричная, то граф ориентированный; б) если граф неориентированный, то матрица смежности симметричная; в) если диагональные элементы матрицы смежности – нули, то граф неориентированный?
12. Может ли вершина, входящая в цикл графа, иметь степень, мень шую двух?
13. Как называется путь, у которого начало первой дуги совпадает с концом последней?
14. Как называется маршрут, у которого первая вершина совпадает с последней?
15. Можно ли утверждать, что сильно связный граф всегда содержит контур?
16. Какие из следующих матриц полностью задают граф:
а) матрица инцидентности; б) матрица од носторонней связности; в) матрица связности; г) матрица сильной связности; д) матрица смежности?
17. По какой матрице можно без дополнительных вычислений определить число компонент связности неориентированного графа: а) матрице смежности; б) матрице инциденций; в) матрице расстояний; г) матрице связности?
18. Может ли число компонент связности графа превосходить число его вершин?
19. Верно или неверно утверждение, что в ориентированном графе с контурами минимальный путь может содержать контуры?
20. Как называется связный граф без циклов?
21. Пусть n - число вершин, а m - число ребер в связном графе без циклов. Какие из следующих соотношений возможны:
а) n = m; б) n < m; в) n m; г) n > m; д) n m?
22. Сколько ребер имеет связный граф без циклов с n вершинами?
23. Чему равно наименьшее и наибольшее число ребер в связном гра фе без петель и кратных ребер с n вершинами?
24. Чему равно наименьшее и наибольшее число ребер в графе без петель и кратных ребер с n вершинами?
25. Верно или неверно следующее утверждение: Минимальное остовное дерево может содержать циклы?
26. Постройте дерево наименьшей общей длины, ребра которого соеди няют вершины правильного шестиугольника.
27. Сколько компонент связности может иметь дерево?
28. Можно ли построить дерево, все вершины которого имеют сте пень больше, чем единица?
29. Какая модель теории графов адекватна следующей задаче:
Различные организации x1, ... , xn обмениваются некоторой информаци ей (при этом связи могут быть направленными). Если между организациями xi и xj возможен непосредственный обмен информацией, то затраты на не го составляют rij рублей. Возможен ли обмен информацией между двумя организациями? Если возможен, то как осуществить этот обмен с наимень шими затратами?
30. Какая модель теории графов адекватна следующей задаче:
Имеется схема городских дорог с перекрестками и, возможно, однос торонним движением. Необходимо найти маршрут, соединяющий две точки на карте. Как найти такой маршрут при условии, что его длина минимальна?
31. Какая модель теории графов адекватна следующей задаче: Требуется построить схему электрической сети, в которой клеммы должны быть соединены с помощью проводов наименьшей общей длины.
32. Какая модель теории графов адекватна следующей задаче:
Имеется сеть связи, соединяющая n узлов. Если выйдут из строя не которые каналы, то связь между узлами может быть нарушена. Какие кана лы можно удалить без нарушения связи? Какие каналы нужно удалить, что бы связь не нарушалась, а общая стоимость всех каналов была минималь ной?
33. Какая модель теории графов адекватна следующей задаче:
Разрабатывается проект газопровода, соединяющего буровые скважины в Мексиканском заливе с находящейся на берегу приемной станцией. Сле дует выбрать проект, в котором строительство газопровода имеет мини мальную стоимость.
34. Какая модель теории графов адекватна следующей задаче:
Пусть имеется n изолированных городов. Какое минимальное коли чество дорог между некоторыми городами надо построить, чтобы иметь возможность попасть из любого города в любой другой? Если заданы расс тояния между городами, то как выбрать сеть дорог с минимальной общей длиной?
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) |
|
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
0 0 0 1 0 1 1 1 |
Для формирования столбца значений переменных удобен лексико-графический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100 = 011+ 1.
Всего существует 22 различных булевых функций n переменных.
Функций одной переменной – 4. Из них выделим функцию “отрицание x”(обозначается Øx). Эта функция представлена в таблице 4.2.
Таблица 4.2
|
x |
Øx |
|
0 1 |
1 0 |
Булевых функций двух переменных – 16 (22при n = 2). Те из них, которые имеют специальные названия, представлены в таблице 4.3.
Таблица 4.3
|
x1 x2 |
x1Vx2 |
x1& x2 |
x1x2 |
x1~x2 |
x1 Å x2 |
x1¯ x2 |
x1ï x2 |
|
0 0 0 1 1 0 1 1 |
0 1 1 1 |
0 0 0 1 |
1 1 0 1 |
1 0 0 1 |
0 1 1 0 |
1 0 0 0 |
1 1 1 0 |
В таблице 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 представляет последовательное вычисление этой функции.
Таблица 4.4
|
x1 x2 x3 |
Øx3 |
x2 Øx3 |
Ø(x2 Øx3) |
Øx1 |
Øx1Vx2 |
f(x1, x2, x3) |
|
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
1 0 1 0 1 0 1 0 |
1 1 1 0 1 1 1 0 |
0 0 0 1 0 0 0 1 |
1 1 1 1 0 0 0 0 |
1 1 1 1 0 0 1 1 |
0 0 0 1 1 1 0 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) (для дизъюнкции относительно конъюнкции).
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.
Таблица 4.5
|
A |
B |
A&B |
Ø(A&B) |
ØA |
ØB |
ØAVØB |
|
0 0 1 1 |
0 1 0 1 |
0 0 0 1 |
1 1 1 0 |
1 1 0 0 |
1 0 1 0 |
1 1 1 0 |
Из таблицы 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ÅB º (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) º
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. Булева алгебра (алгебра логики). Полные системы булевых функций
Как известно, алгеброй называют систему, включающую в себя некоторое непустое множество объектов с заданными на нем функциями (операциями), результатами применения которых к объектам данного множества являются объекты того же множества.
Булевой алгеброй или алгеброй логики называется двухэлементное множество 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) – не элементарные дизъюнкции.
Определение 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), от которых следует избавляться по мере их появления.
Пример 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 º С.
Шаг 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).
После применения шага 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).
4. Замечаем, что 1-ый и 3-ий, а также 4-ый и 5-ый дизъюнктивные члены полученного выражения совпадают, применяем шаг 6 и получим окончательно СКНФ формулы f(x1, x2, x3):
f(x1, x2, x3) º (x1Vx2Vx3)&(x1Vx2VØx3)&(x1VØx2Vx3)&(Øx1VØx2Vx3).
4.7. Разложение булевой функции по переменным
Пусть s принимает значения 0 или 1, т.е. s {0, 1}.
Введем обозначение:
xs = Øx, если s = 0, xs = x, если s = 1.
Т.е. x0 = Øx, x1 = x.
Очевидно, что xs = 1, если x = s и xs = 0, если x s.
Теорема 4.5 (о разложении булевой функции по переменным).
Каждая булева функция f(x1, x2, ... , xn) может быть представлена в виде:
f(x1, x2, ... , xn) = f(x1, x2, ... , xm, xm+1, ... , xn) =
V x1s1&x2s2&...&xmsm& f(s1, s2, ... sm, xm+1, ... , xn), (4.1)
mn, где дизъюнкция берется по всем наборам (s1, s2, ... , sm) (их 2m).
Например, для m = 2, n = 4 разложение (4.1) включает в себя четыре (2m = 22 =4) конъюнкции и имеет вид:
f(x1, x2, x3, x4) = x&x&f(0, 0, x3, x4) V x&x&f(0, 1, x3, x4) V x& x&f(1, 0, x3, x4) V x& x&f(1, 1, x3, x4) = Øx1&Øx2&f(0, 0, x3, x4) V Øx1&x2&f(0, 1, x3, x4) V x1&Øx2&f(1, 0, x3, x4) V x1&x2&f(1, 1, x3, x4).
Доказательство теоремы 4.5.
Теорема будет доказана, если показать, что равенство (4.1) выполняется для произвольного набора переменных (y1, y2, ... , ym, ym+1, ... , yn) .
Подставим этот произвольный набор переменных в левую и правую части равенства (4.1).
В левой части получим f (y1, y2, ... , yn) .
Т. к. ys = 1 только, когда y = s, то среди 2m конъюнкций y1s1&y2s2&...&ymsm в правой части (4.1) только одна обратится в 1 – та, в которой y1 = s1,…, ym = sm. Все остальные конъюнкции равны 0. Поэтому в правой части (4.1) получим:
y1y1&y2y2&...&ymym&f(y1, y2, ... , ym, ym+1, ... , yn) = f(y1, y2, ... , yn) .
Теорема 4.5 доказана.
Теорема 4.6 (о представлении булевой функции формулой в СДНФ),
Всякая булева функция f(x1, x2, ... , xn), не равная тождественно 0, может быть представлена формулой в СДНФ, которая определяется однозначно с точностью до перестановки дизъюнктивных членов.
Доказательство.
При m = n получим важное следствие теоремы 4.5:
f(x1, x2, ... , xn) = V x1s1&x2s2&...&xnsn, (4.2)
f(s1, s2, ... , sn) = 1
где дизъюнкция берется по всем наборам (s1, s2, ... , sn), на которых f = 1.
Очевидно, что разложение (4.2) есть не что иное, как СДНФ формулы f, которая содержит столько конъюнкций, сколько единиц в таблице значений f. Следовательно, СДНФ для всякой булевой функции единственна с точностью до перестановки ее дизъюнктивных членов.
Очевидно также, что для булевой функции f(x1, x2, ... , xn), тождественно равной 0, разложение (2) не существует.
В силу изложенного для получения формулы булевой функции f(x1, x2, ... , xn) в СДНФ можно воспользоваться следующим алгоритмом.
Алгоритм 4.3. (Алгоритм представления булевой функции, заданной таблицей, формулой в СДНФ).
Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f равно 1, т. е. f (s1, s2, ... , sn) = 1.
Шаг 2. Для каждого такого набора (строки таблицы) составляем конъюнкцию x1s1&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.6, если она не равна тождественно 0, существует ее формула в СДНФ. Обозначим эту формулу F1. Очевидно, условие, что функция Øf(x1, x2, ... , xn) не равна тождественно 0, равносильно условию, что функция f(x1, x2, ... , xn) не равна тождественно 1. Кроме того, по закону де Моргана формула F2 º ØF1 находится в СКНФ (отрицание конъюнкции есть дизъюнкция отрицаний). По закону двойного отрицания
F2 º ØF1 º ØØf(x1, x2, ... , xn) º f(x1, x2, ... , xn),
что и доказывает теорему.
Для получения формулы булевой функции f(x1, x2, ... , xn) в СКНФ следует воспользоваться следующим алгоритмом.
Алгоритм 4.4. (Алгоритм представления булевой функции, заданной таблицей, формулой в СКНФ)
Шаг 1. Выбираем в таблице все наборы переменных s1, s2, ... , sn, для которых значение f (s1, s2, ... , sn) = 0.
Шаг 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.8. Минимизация формул булевых функций в классе дизъюнктивных
нормальных форм
Как было установлено выше, произвольная булева функция может быть представлена формулой в ДНФ и КНФ, причем такое представление неоднозначно. Равносильными преобразованиями можно получить формулу, содержащую меньшее число вхождений переменных. Например, две различные формулы: 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.
Для функции 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= 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.
На практике для построения сокращенной ДНФ удобнее пользоваться модифицированным методом Квайна – Мак-Класки. Этот метод состоит в автоматизации процесса склеивания. Разберем этот метод на конкретном примере.
Алгоритм 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 0 0
Группа A2:
0 1 1
1 0 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).
Далее рассмотрим наборы с прочерками. Они вновь попарно сравниваются между собой. При этом имеет смысл сравнивать лишь наборы, в которых прочерк стоит в совпадающих разрядах. Если сравниваемые наборы отличаются друг от друга только в одном разряде, то выписываем набор с двумя прочерками (старым и новым). После всех попарных сравнений из множества наборов с одним прочерком вычеркиваются все наборы, имеющие один прочерк и участвовавшие в образовании набора с двумя прочерками. Наборы с одним прочерком, не участвовавшие в образовании наборов с двумя прочерками, помещаются в массив R.
Для нашего примера попарное сравнение наборов с одним прочерком не приводит к образованию наборов с двумя прочерками.
Далее рассмотрим наборы с двумя прочерками и т. д. Процесс прекращается, если на очередном шаге все рассматриваемые наборы попадают в R. Нетрудно убедиться, что каждому набору из R соответствует простой импликант, причем единице соответствует переменная, взятая без отрицания, нулю – переменная, взятая с отрицанием, а прочерку – отсутствие соответствующей переменной. Сокращенная ДНФ есть дизъюнкция этих простых импликантов.
Для нашего примера процедура сравнения заканчивается после формирования наборов с одним прочерком. Массив R после этого включает наборы:
(1 0 –);
(– 1 1);
(1 – 1).
Сокращенная ДНФ имеет вид:
f(x1, x2, x3) = x2&x3 V x1&Øx2 V x1&x3.
Далее процесс нахождения минимальной ДНФ сводится к отбрасыванию некоторых простых импликантов.
Определение 4.14. Простой импликант называется существенным (ядровым) импликантом, если его удаление из сокращенной ДНФ функции приводит к ДНФ, которая не равносильна исходной ДНФ.
Построение минимальной ДНФ сводится к отбрасыванию несущественных импликантов из сокращенной ДНФ.
Определение 4.15. Будем говорить, что элементарная конъюнкция A покрывает элементарную конъюнкцию В, если она является частью этой конъюнкции, т.е. целиком входит в нее.
Пример 4.19.
Элементарная конъюнкция x1&Øx2 покрывает элементарные конъюнкции x1&Øx2&x3 и x1&Øx2&Øx3, но не покрывает элементарные конъюнкции x1&x2&x3 и Øx1&Øx2&Øx3.
Нахождение минимальной ДНФ состоит в выборе таких простых импликантов из сокращенной ДНФ, которые в совокупности покрывают все элементарные конъюнкции СДНФ и содержат минимальное число вхождений переменных. Такая ДНФ равносильна СДНФ, т. к. в силу определения 4.15 ее значения на некотором наборе переменных совпадают со значениями СДНФ.
Рассмотрим следующий алгоритм нахождения минимальной ДНФ.
Алгоритм 4.7. (Алгоритм построения минимальной ДНФ с помощью таблицы покрытий).
Шаг 1. Составление таблицы покрытий.
Для данной функции
f(x1, x2, ... , xn) = Ai º Bj, m k,
где Ai –элементарные конъюнкции, входящие в СДНФ, i = 1, 2, ..., k, k n, а Bj – простые импликанты сокращенной ДНФ, j = 1, 2, ... ,m, m k, построим таблицу покрытий, число строк которой равно числу полученных простых импликантов, а число столбцов – числу элементарных конъюнкций в СДНФ. Если в некоторую элементарную конъюнкцию входит какой-либо простой импликант, то на пересечении соответствующего столбца и строки ставится метка (например, “ * “).
Шаг 2. Выделение столбцов, содержащих одну метку.
Если в каких-нибудь столбцах составленной таблицы имеется только одна метка, то строки, в которых стоят эти метки, определяют простые импликанты, которые не могут быть исключены из сокращенной ДНФ, т. к. без них не может быть получено покрытие всех элементарных конъюнкций СДНФ. Они являются существенными и обязательно входит в минимальную ДНФ. Поэтому из таблицы покрытий исключаются строки, соответствующие существенным импликантам, и столбцы элементарных конъюнкций СДНФ, покрывемые этими существенными импликантами.
Шаг 3. Вычеркивание лишних столбцов.
Если в таблице есть столбцы, в которых имеются метки в одинаковых строках, то оставляем только один из них (все равно, какой), так как покрытие элементарных конъюнкций, соответствующих выброшенным столбцам, осуществляется за счет простого импликанта, соответствующего оставшемуся столбцу.
Шаг 4. Вычеркивание лишних существенных импликантов.
Если после выбрасывания некоторых столбцов в результате шага 3, в таблице появляются строки, в которых нет ни одной метки, то простые импликанты, соответствующие этим строкам, исключаются из дальнейшего рассмотрения, т. к. они не покрывают оставшиеся в рассмотрении элементарные конъюнкции СДНФ.
Шаг 5. Выбор минимального покрытия существенными импликантами.
Выбирается такая совокупность строк (т. е. существенных импликантов), чтобы они покрывали все оставшиеся столбцы (элементарные конъюнкции СДНФ). При нескольких возможных вариантах предпочтение отдается варианту покрытия с минимальным общим числом вхождения переменных.
Пример 4.20.
Продолжим предыдущий пример.
1. Составляем таблицу покрытий. Для формулы, булевой функции с СДНФ:
f(x1, x2, x3) = Øx1&x2&x3V x1&Øx2&Øx3 V x1&Øx2&x3 V x1&x2&x3
мы получили равносильную ей сокращенную ДНФ:
F1(x1, x2, x3) = x2&x3 V x1&Øx2 V x1&x3.
Каждой элементарной конъюнкции x1s1&x2s2&...&xnsn, (xi si = xi, если si = 0 и xisi = Øxi, если si = 1, i = 1, 2, ... ,n), входящей в СДНФ, можно сопоставить набор переменных из нулей и единиц. Этот наборы идентифицируют столбцы. Каждому простому импликанту из сокращенной ДНФ также можно сопоставить набор из нулей, единиц и прочерков, где 0 означает, что переменная берется с отрицанием, 1 – переменная берется без отрицания, “ – ” – переменная отсутствует. Для нашего примера получим следующую таблицу (таблица 4.6) из 4 столбцов, соответствующих 4 элементарным конъюнкциям СДНФ F(x1, x2, x3, x4) и 3 строк, соответствующих 3 простым импликантам сокращенной ДНФ F1(x1, x2, x3, x4).
Таблица 4.6
|
011 |
100 |
101 |
111 |
|
|
–11 |
* |
* |
||
|
10– |
* |
* |
||
|
1–1 |
* |
* |
2. Выделяем столбцы, содержащие одну метку – это 1-ый и 2-ой столбцы. Импликант x2&x3 (ему соответствует 1-ая строка) является существенным. Он покрывает две элементарные конъюнкции СДНФ: Øx1&x2&x3 и x1&x2&x3 (им соответствуют 1-ый и 4-ый столбцы). Импликант x1&Øx3 (ему соответствует 2-ая строка) тоже является существенным. Он покрывает две элементарные конъюнкции СДНФ: x1&Øx2&Øx3 и x1&Øx2&x3 (им соответствуют 2-ой и 3-ий столбцы).
Все указанные строки (1-ую и 2-ую) и столбцы (1-ый, 2-ой, 3-ий и 4-ый) вычеркиваем из таблицы покрытий. После этого все элементы таблицы окажутся вычеркнутыми. Следовательно, два существенных импликанта x2&x3 и x1&Øx3 покрывают все элементарные конъюнкции СДНФ.
Итак, минимальная ДНФ для нашей функции имеет вид:
F2(x1, x2, x3) = x2&x3 V x1&Øx2 .
Рассмотрим еще один пример нахождения минимальной ДНФ булевой функции.
Пример 4.21.
Пусть булева функция задана таблицей
Таблица 4.7
|
x1 x2 x3 x4 |
f(x1, x2, x3, x4) |
|
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 |
0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 0 |
Применим вначале алгоритм Квайна - Мак-Класки для нахождения сокращенной ДНФ.
Очевидно, в силу алгоритма 4.3, данная функция имеет следующую формулу в СДНФ:
F(x1, x2, x3, x4) = Øx1&Øx2&x3&x4 V Øx1&x2 &Øx3 &x4 V Øx1&x2&Øx3&Øx4 V
Øx1&x2&x3&x4Vx1&Øx2&Øx3&x4Vx1&Øx2&x3&x4Vx1&x2&Øx3&Øx4Vx1&x2&Øx3&x4.
Выпишем наборы переменных, на которых функция принимает значение 1, причем эти наборы упорядочим по группам так, что в каждую группу входят наборы с одинаковым числом единиц.
Группы A0 нет.
Группа A1:
0 1 0 0
Группа A2:
0 0 1 1
0 1 0 1
1 0 1 0
1 1 0 0
Группа A3:
0 1 1 1
1 0 1 1
1 1 0 1
Группы A4 нет.
Производим попарное сравнение наборов переменных, входящих в соседние группы.
При сравнении групп A1 и A2:
вместо (0 1 0 0) и (0 1 0 1) получим (0 1 0 –);
вместо (0 1 0 0) и (1 1 0 0) получим (– 1 0 0);
При сравнении групп A2 и A3:
вместо (0 0 1 1) и (0 1 1 1) получим (0 – 1 1);
вместо (0 0 1 1) и (1 0 1 1) получим (– 0 1 1);
вместо (0 1 0 1) и (0 1 1 1) получим (0 1 – 1);
вместо (0 1 0 1) и (1 1 0 1) получим (– 1 0 1);
вместо (1 0 0 1) и (1 0 1 1) получим (1 0 – 1);
вместо (1 0 0 1) и (1 1 0 1) получим (1 – 0 1);
вместо (1 1 0 0) и (1 1 0 1) получим (1 1 0 –).
После этого этапа массив R пуст, т. к. все наборы участвовали в образовании наборов с прочерками, а массив P = P(1) включает следующие наборы:
(0 1 0 –);
(– 1 0 0);
(0 – 1 1);
(– 0 1 1);
(0 1 – 1);
(– 1 0 1);
(1 0 – 1);
(1 – 0 1);
(1 1 0 –).
Теперь попарно сравниваются между собой наборы с прочерками. Наборы с одним прочерком, не участвовавшие в образовании наборов с двумя прочерками, помещаются в массив R.
Для нашего примера
вместо (0 1 0 –) и (1 1 0 –) получим (– 1 0 –);
вместо (– 1 0 0) и (– 1 0 1) получим (– 1 0 –)
После этого этапа в массив R попадают наборы, не участвовавшие в образовании наборов с двумя прочерками:
(0 – 1 1);
(– 0 1 1)
(0 1 – 1);
(1 0 – 1);
(1 – 0 1);
Массив P(2) состоит из набора с двумя прочерками:
(– 1 0 –).
Набор с двумя прочерками один и процедура сравнения заканчивается. Поэтому все наборы из P(2) попадают в массив R, который после этого включает наборы:
(0 – 1 1);
(– 0 1 1)
(0 1 – 1);
(1 0 – 1);
(1 – 0 1);
(– 1 0 –).
Сокращенная ДНФ имеет вид:
F1(x1, x2, x3, x4) = Øx1&x3&x4 V Øx2&x3&x4 V Øx1&x2&x4 V x1&Øx2&x4 V x1&Øx3&x4 x2&Øx3.
Найдем теперь минимальную ДНФ с помощью таблицы покрытий (алгоритм 4.7).
Составляем таблицу покрытий.
Для нашего примера получим следующую таблицу (таблица 4.8) из 8 столбцов, соответствующих 8 элементарным конъюнкциям СДНФ F(x1, x2, x3, x4) и 6 строк, соответствующих 6 простым импликантам сокращенной ДНФ F1(x1, x2, x3, x4).
Таблица 4.8
|
|
0011 |
0100 |
0101 |
0111 |
1001 |
1011 |
1100 |
1101 |
|
0-11 |
* |
|
* |
|||||
|
-011 |
* |
|
* |
|||||
|
01-1 |
* |
* |
||||||
|
10-1 |
|
|
* |
* |
||||
|
1-01 |
|
* |
|
* |
||||
|
-10- |
* |
* |
|
|
* |
* |
Выделяем столбцы, содержащие одну метку – это 2-ой и 7-ой столбцы. Оба этих столбца определяют один и тот же импликант x2&Øx3 (ему соответствует 6-ая строка), который является существенным. Он покрывает следующие четыре элементарные конъюнкции СДНФ: Øx1&x2&Øx3&x4, Øx1&x2&Øx3&Øx4, x1&x2&Øx3&Øx4, x1&x2&Øx3&x4 (им соответствуют 2-ой, 3 - ий, 7 - ой и 8 - ой столбцы). Все указанные строки и столбцы вычеркиваем из таблицы покрытий. После этого таблица примет вид:
Таблица 4.9
|
0011 |
0111 |
1001 |
1011 |
|
|
0-11 |
* |
* |
||
|
-011 |
* |
* |
||
|
01-1 |
* |
|||
|
10-1 |
* |
* |
||
|
1-01 |
* |
В полученной таблице нет одинаковых столбцов. В полученной таблице нет пустых строк. Выбираем такую совокупность существенных импликантов, которая покрывает все столбцы и содержит наименьшее количество букв. Для нашей таблицы это импликанты Øx1&x3&x4 и x1&Øx2&x4 (1 - ая и 4 - ая строки таблицы 4. 9), т. к. они покрывают все оставшиеся столбцы.
Итак, минимальная ДНФ для нашей функции имеет вид:
F2(x1, x2, x3, x4) = Øx1&x3&x4 V x1&Øx2&x4 V x2&Øx3 .
4.9. Применение алгебры булевых функций к релейно-контактным схемам
Рассмотрим электрические релейно-контакные схемы, главный элемент которых – электромагнитное реле.
Пусть x1, x2, ... , xn – набор контактов в схеме. Контакты могут быть размыкающими и замыкающими. Контакт называется замыкающим, если он замыкается при подаче напряжения. Контакт называется размыкающим, если он размыкается при подаче напряжения. Один и тот же контакт в схеме может быть как замыкающим, так и размыкающим.
Каждой последовательно- параллельной схеме сопоставим функцию проводимости:
f(x1, x2, ... , xn) =
Функция проводимости схемы, состоящей из одного элемента x, для замыкающего контакта есть f(x) = x, а для размыкающего контакта f(x) = Øx.
Функция проводимости схемы, состоящей из двух последовательно соединенных контактов x и y (рис. 4. 1) есть f(x, y) = x&y.
Рис. 4. 1
Функция проводимости схемы, состоящей из двух параллельно соединенных контактов x и y (рис. 4. 2) есть f(x, y) = x V y.
Рис. 4. 2
Каждой последовательно-параллельной схеме можно поставить в соответствие формулу логики булевых функций, реализующую функцию проводимости этой схемы. Две схемы считаются эквивалентными, если они имеют одинаковую функцию проводимости. Применяя равносильные преобразования, можно упрощать релейно-контактные схемы, заменяя их эквивалентными, с меньшим числом контактов.
Пример 4.22.
Найдем функцию проводимости схемы, изображенной на рис. 4. 3.
Рис. 4.3
f(x, y, z) = (y&z) V (x&Øy&z) V (Øx&Øy&z) º (y&z) V (Øy&z) º z.
Эквивалентная схема изображена на рис. 4.4.
Рис 4.4
1. Выберите правильный вариант ответа 1 – 4 для следующих вопросов:
а) Сколько существует различных булевых функций n переменных? б) Сколько существует различных наборов переменных для булевой функции n переменных?
Варианты ответа: 1) 2n; 2) 22; 3) n2; 4) n!.
2. Какое из следующих утверждений верно:
а) Переменные булевой функции и сама булева функция принимают значения 0 или 1;
б) Переменные булевой функции принимают значения 0 или 1, а значения самой булевой функции совпадают с множеством действительных чисел;
в) Значения переменных булевой функции совпадают с множеством действительных чисел, а сама булева функция принимает значения 0 или 1;
г) Значения переменных булевой функции и значения самой функции совпадают с множеством действительных чисел;
3. Выберите правильный вариант ответа 1 – 4 для следующих вопросов:
а) Сколько может быть различных ДНФ у булевой функции?
б) Сколько может быть различных СДНФ у булевой функции?
в) Сколько может быть различных КНФ у булевой функции?
г) Сколько может быть различных СКНФ у булевой функции?
Варианты ответа:
1 – ноль или одна; 2 – ноль или бесконечно много; 3 – ноль или одна; 4 – одна; 5 – одна или бесконечно много.
4. В какой из нормальных форм (ДНФ, СДНФ, КНФ, СКНФ) находится данная формула булевой функции трех переменных f(x, y, z):
а) xVy&z; б) x&y&z; в) (xVy)&(xVØz); г) xVyVz; д) Øx&y&z V y&Øz; е) xVØy; ж) x&z.
5. Какая релейно-контактная схема соответствует функции проводимости f(x) = (xVy)&(xVØz)?
Ответы на контрольные вопросы
Тема 1
1. Да.
2. Если АВ.
3. Пустое множество.
4. Да. Например, множество целых чисел эквивалентно множеству четных чисел.
5. Мощность множества точек отрезка [0, 1] больше. Это множество имеет мощность континнуума, а множество натуральных чисел является счетным множеством.
Тема 2.
1. Перечислением упорядоченных пар, указанием общего свойства упорядоченных пар, матрицей бинарного отношения.
2. Рефлексивного.
3. Для симметричного.
4. Для транзитивного.
5. Например, отношение параллельности прямых есть отношение эквивалентности. Пусть x и y – углы наклона прямых x и y с осью абсцисс. Тогда отношение = {x, y x y} есть отношение частичного порядка.
6. Функция может быть задана таблицей, формулой, рекурсивной процедурой, с помощью описания.
7. б).
Тема 3.
1. б).
7. Нет. Только для неориентированного графа.
8. Нужно сложить все элементы матрицы и полученную сумму разделить на 2.
10. Нет.
11. а) и б).
12. Нет.
15. Да .
16. а), д)
17. г).
18. Нет.
19. Нет.
21. г).
22. n – 1.
23. Наименьшее – n – 1 (дерево), наибольшее – n( n – 1) 2 (полный граф).
24. Наименьшее – 0 (несвязный граф), наибольшее – n( n – 1) 2 (полный граф).
25. Нет.
27. Одну.
28. Нет.
29. Нахождение минимального пути.
30. Нахождение минимального пути.
31. Нахождение минимального остовного дерева.
32. Нахождение минимального остовного дерева.
33. Нахождение минимального остовного дерева.
34. Нахождение минимального остовного дерева.
Тема 4.
1. а)22; б) 2n.
2. а).
3. а) бесконечно много; б) ноль или одна; в) бесконечно много; г) ноль или одна.
4. а)ДНФ; б)ДНФ, СДНФ, КНФ; в)КНФ; г)ДНФ, КНФ, СКНФ; д)ДНФ; е)ДНФ, КНФ; ж)ДНФ, КНФ.
11. а) и б).
Указания к выполнению лабораторных работ
Лабораторные работы проводятся с помощью обучающей компьютерной системы "Теория графов". В лабораторных работах используются следующие разделы этой системы: "Основные понятия теории графов", "Экстремальные пути в графах".
Чтобы приступить к выполнению лабораторной работы необходимо запустить систему с помощью файла run.bat; выбрать в главном меню пункт "Обучающие программы"; указать раздел; выбрать пункт "Упражнения".
В процессе работы возможно обращение к теоретическому материалу, используя соответствующие пункты меню, а также алфавитный указатель.
Лабораторная работа №1. Основные понятия. Ориентированные графы
Для выполнения этой работы требуется изучить следующие понятия для ориентированного графа: определения дуги, пути, контура, односторонней и сильной связности, компоненты сильной связности, матриц смежности, инцидентности, сильной связности.
Лабораторная работа №2. Основные понятия. Неориентированные графы
Для выполнения этой работы требуется изучить следующие понятия для неориентированного графа: определения ребра, маршрута, цикла, связности, компоненты связности, матриц смежности, инцидентности, связности.
Лабораторная работа №3. Экстремальные пути в графах
Для выполнения этой работы требуется изучить определения нагруженного графа, минимального пути, максимального пути, кратчайшего пути, а также алгоритм Форда – Беллмана.
Контрольные задания по курсу "Дискретная математика".
1. Раздел «Множества»
Вариант № 1
1. Фирма имеет 100 предприятий, причем каждое предприятие выпускает хотя бы одну продукцию вида А, В, С. Продукцию всех трех видов выпускают 10 предприятий, продукцию А и В – 18 предприятий, продукцию А и С – 15 предприятий, продукцию В и С – 21 предприятие. Число предприятий, выпускающих продукцию А равно числу предприятий, выпускающих продукцию В и равно числу предприятий, выпускающих продукцию С. Найти число всех предприятий.
2. Упростить: È È.
3. Является ли множество А = {1, 2, 3} подмножеством множества В = {{1}, {2, 3}}?
4. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ = С.
5. Эквивалентны ли множества A = {x: x2 – 8x + 15= 0} и B = {2, 3}?
Вариант № 2
1. В группе спортсменов 30 человек. Из них 20 занимаются плаванием, 18 – легкой атлетикой и 10 – лыжами. Плаванием и легкой атлетикой занимаются 11 человек, плаванием и лыжами – 8, легкой атлетикой и лыжами – 6 человек. Сколько спортсменов занимаются всеми тремя видами спорта?
2. Упростить: AÇ(AÈB).
3. В каком случае ААÇВ?
4. Нарисовать диаграмму Эйлера-Венна для множества È.
5. Какое из множеств A = {1, 4, 9, 16, 25,…} и B = {1, 1/2, 1/4, 1/6, 1/8,…} имеет большую мощность?
Вариант № 3
1. В студенческой группе 20 человек. Из них 10 имеют оценку “отлично” по английскому языку, 8 - по математике, 7 - по физике, 4 - по английскому языку и по математике, 5 - по английскому языку и по физике, 4 - по математике и по физике, 3 - по английскому языку, по математике и по физике. Сколько студентов группе не имеют отличных оценок?
2. Упростить: (A\B) È (A\B).
3. Найти все подмножества множества A= {1, 2, 3, 4).
4
4. Пусть An = {0, 1/2n}. Найти U An.
n=1
5. Доказать, что множества точек контуров всех треугольников эквивалентны.
Вариант № 4
1. В классе 20 человек. На экзаменах по истории, математике и литературе 10 учеников не получили ни одной пятерки, 6 учеников получили 5 по истории, 5 – по математике и 4 – по литературе; 2 - по истории и математике, 2 - по истории и литературе, 1 - по математике и литературе. Сколько учеников получили 5 по всем предметам?
2. Упростить: (AÇB) È (AÇB).
3. Является ли множество А = {1, 2, 3} подмножеством множества В = {{1}, {2, 3}}?
4. Нарисовать диаграмму Эйлера-Венна для множества (А \ В) Ç С
5. Эквивалентны ли множества A = {2x, 0<x< ¥} и B = {2n, n = 1, 2, …}?
Вариант № 5
1. В спортивном лагере 100 человек, занимающихся плаванием, легкой атлетикой и лыжами. Из них 10 занимаются и плаванием, и легкой атлетикой, и лыжами, 18 – плаванием и легкой атлетикой, 15 – плаванием и лыжами, 21 – легкой атлетикой и лыжами. Число спортсменов, занимающихся плаванием, равно числу спортсменов, занимающихся легкой атлетикой, и равно числу спортсменов, занимающихся лыжами. Найти это число.
2. Упростить: (AÈB) È(AÈB).
3. Найти все подмножества множества A= {1, 2, 3, 4).
4. Нарисовать диаграмму Эйлера-Венна для множества (А \ В) È С
5. Доказать, что множества точек контуров всех треугольников эквивалентны.
Вариант № 6
1. Группе студентов предложено три спецкурса: по мультимедиа, искусственному интеллекту и имитационному моделированию. 22 студента записались на спецкурс по мультимедиа, 18 – на спецкурс по искусственному интеллекту, 10 – на спецкурс по имитационному моделированию, 8 – на спецкурсы по мультимедиа и искусственному интеллекту, 15 – на спецкурсы по мультимедиа и имитационному моделированию, 7 – на спецкурсы по искусственному интеллекту и имитационному моделированию. 5 студентов записались на все три спецкурса. Сколько студентов в группе?
2. Верно или неверно равенство: (A \ B) È(AÇB) = A?
3. Придумать пример множеств А, В, С, каждое из которых имеет мощность континуума, так, чтобы выполнялось равенство: А ÈВ = С.
4. Нарисовать диаграмму Эйлера-Венна для множества (А \ В) È (А \ С).
5. Эквивалентны ли множества A = {x: x2-8x+15= 0} и B = {2, 3}?
Вариант № 7
1. Во время сессии 24 студента группы должны сдать три зачета: по физике, математике и программированию. 20 студентов сдали зачет по физике, 10 – по математике, 5 – по программированию, 7 – по физике и математике, 3 – по физике и программированию, 2 – по математике и программированию. Сколько студентов сдали все три зачета?
2. Упростить: (AÈB) È (AÇB).
3. Доказать, что множество точек A= {(x, y): y = ½x½, -, – 1 £ x £ 1} несчетно.
4. Нарисовать диаграмму Эйлера-Венна для множества (А \ В) È С.
5. Эквивалентны ли множества A = {y: y = x3, 1< x <2} и B = {y: y = 3x, 3< x < ¥}?
Вариант № 8
В группе переводчиков 15 человек владеет английским языком, 19 – французским, 8 – немецким. 9 переводчиков владеют английским и французским языком, 7 – английским и немецким, 6 – французским и немецким. 4 переводчика владеют всеми тремя языками. Сколько переводчиков в группе?
2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В È С) = (А \ В) È С?
3. В каком случае ААÇВ?
4. Нарисовать диаграмму Эйлера-Венна для множества (È) \ (A È B).
5. Эквивалентны ли множества A = {x: x2 –3x + 2 = 0} и B = {1, 3}?
Вариант № 9
1. Опрос группы студентов показал, что 70% из них любят ходить в кино, 60% в театр, 30% на концерты. В кино и театр ходят 40% студентов, в кино и на концерты – 20%, в театр и на концерты – 10%. Сколько студентов (в %) ходят в кино, театр и на концерты?
2. Верно или неверно равенство: (AÇB) Ç (A È В) = В?
3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.
4. Нарисовать диаграмму Эйлера-Венна для множества А \ (В ÇС).
5. Эквивалентны ли множества A = {x: x3 – 1 = 0} и B = {x: x2 – 3x + 2 = 0}?
Вариант № 10
1. В группе 20 учеников. После медицинского осмотра на дополнительное обследование 14 учеников были направлены к терапевту, 6 – к окулисту, 5 – к ортопеду. К терапевту и окулисту были направлены 3 ученика, к терапевту и ортопеду –3, к окулисту и ортопеду – 2. Сколько учеников были направлены к терапевту, окулисту и ортопеду?
2. Упростить: (È) \ (A È B).
3. Нарисовать диаграмму Эйлера-Венна для множества (A Ç B) È (C \ (A È B)).
4. Найти все подмножества множества A= {a, b, c, d}.
5. Эквивалентны ли множества A = {(x, y): y = lnx, 0 < x < ¥} и B = {(x, y): y = sinx, –¥ <x < ¥}?
Вариант № 11
1. При обследовании рынка спроса инспектор указал в опросном листе следующие данные. Из 1000 опрошенных 811 покупают жевательную резинку "Дирол", 752 – "Орбит" , 418 – "Стиморол", 570 – "Дирол" и "Орбит", 356 – "Дирол" и "Стиморол", 348 – "Орбит" и "Стиморол", 297 – все виды жевательной резинки. Показать, что инспектор ошибся.
2. Упростить: È(B \ (AÈB)).
3. Придумать пример множеств А, В, С, так, чтобы выполнялось равенство: А È В = С, причем А – конечное множество, В и С – счетные множества.
4. Нарисовать диаграмму Эйлера-Венна для множества A Ç (B È C ) .
5. Пусть A – множество целых чисел, а B – множество четных чисел. Какие из следующих отношений справедливы: а) A =B; б) A ~ B; в) A ÉB; г) A ÊB; д) A ËB; е) A Î B.
Вариант № 12
1. Всем участникам автопробега не повезло. 12 из них увязли в песке – пришлось толкать машину, 8 понадобилась замена колеса, у шестерых перегрелся мотор, пятеро и толкали машину и меняли колесо, четверо толкали машину и остужали мотор, трое меняли колесо и остужали мотор. Одному пришлось испытать все виды неполадок. Сколько было участников?
2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В ÇС) = (А \В) ÇС?
3. Доказать, что множество точек A = {y: y = 2n, n = 1, 2, …} счетно.
4. Нарисовать диаграмму Эйлера-Венна для множества (А \В) ÇС.
5. Эквивалентны ли множества A = {(x, y): y = x3, 1< x <2} и B = {(x, y): y = 3x, 3< x < ¥}?
Вариант № 13
1. Из 10 участников ансамбля шестеро умеют играть на гитаре, пятеро – на ударных инструментах, пятеро – на духовых. Двумя инструментами владеют: гитарой и ударными – трое, ударными и духовыми – двое, гитарой и духовыми – четверо. Один человек играет на всех трех инструментах. Остальные участники ансамбля только поют. Сколько певцов в ансамбле?
2. Верно или неверно равенство: ÇС) = ÇС ÈÇС ?
3. Записать решение системы неравенств
x-2 > 0
x-5 < 0
в виде пересечения двух множеств.
4. Нарисовать диаграмму Эйлера-Венна для множества Ç(B ÈC ) .
5. Доказать, что множества A = {(x, y): y = x3, 1< x <2} и B = {y: y = 3x, 3< x < ¥} эквивалентны.
Вариант № 14
1. В одной студенческой группе 10 человек могут работать на Дельфи, 10 – на Паскале, 6 – на Си. По два языка знают: 6 человек – Дельфи и Паскаль, 4 – Паскаль и Си, 3 – Дельфи и Си. Один человек знает все три языка. Сколько студентов в группе?
2. Верно или неверно соотношение: AÇÇC Ì A È В?
3. Придумать пример множеств А, В, С, так, чтобы выполнялось равенство: А È В = С, причем А, В, и С – счетные множества.
4. Нарисовать диаграмму Эйлера-Венна для множества ÇС).
5. Эквивалентны ли множества A = {y: y = 3x, 0<x< ¥} и B = {y: y = 3n, n = 1, 2, …}?
Вариант № 15
1. В день авиации на аэродроме всех желающих катали на самолете, планере, дельтаплане. На самолете прокатились 30 человек, на планере – 20, на дельтаплане – 15. И на самолете, и на планере каталось 10 человек, на самолете и дельтаплане – 12, На планере и дельтаплане – 5. Два человека прокатились и на самолете, и на планере, и на дельтаплане. Сколько было желающих прокатиться?
2. Верно или неверно равенство: (A È B) \ A = B \ A ?
3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.
4. Нарисовать диаграмму Эйлера-Венна для множества ÇС ÈÇС.
5. Доказать, что множества A = {y: y = lnx, 0 < x < ¥} и B = {y: y = sinx, –¥ <x < ¥} эквивалентны.
Вариант № 16
1. Все грибники вернулись домой с полными корзинами. У десятерых из них в корзинах были белые грибы, у восемнадцати – подберезовики, у двенадцати – лисички. Белые и подберезовики были в шести корзинах, белые и лисички – в четырех, Подберезовики и лисички – в пяти. Все три вида грибов были у двух грибников. Сколько было грибников?
2. Верно или неверно равенство: (A È B) \ (AÇB) = AÇÈÇB?
3. Доказать, что множество точек A= {(x, y): y = ½x½, -, – 1 £ x £ 1} несчетно.
4. Нарисовать диаграмму Эйлера-Венна для множества Ç (B È C ) .
5. Пусть A – множество точек отрезка [0, 1], а B – множество всех точек числовой оси. Какие из следующих отношений справедливы: а) A =B; б) A ~ B; в) A ÉB; г) A ÊB; д) A ËB; е) A Î B.
Вариант № 17
1. Все туристы взяли в поход консервы. Шесть человек взяли тушенку, пять – сгущенку, восемь – кашу (с мясом). У троих в рюкзаках была тушенка и сгущенка, у двоих – тушенка и каша, у троих – сгущенка и каша, и только в одном рюкзаке лежали все три вида консервов. Сколько было туристов?
2. Верно или неверно равенство: ÇС = С \ (С Ç (AÈB))?
3. Пусть A – множество решений уравнения x2 – 3x + 2 = 0. Записать это множество двумя различными способами.
4. Нарисовать диаграмму Эйлера-Венна для множества (BÇC) \ A .
5. Эквивалентны ли множества A = {x: x2 –3x + 2 = 0} и B = {2, 3}?
Вариант № 18
1. Было опрошено 70 человек. В результате опроса выяснили, что 45 человек знают английский язык, 29 – немецкий и 9 – оба языка. Сколько человек из опрошенных не знает ни английского, ни немецкого языков?
2. Верно или неверно равенство: (A È B) \ (AÇB) = AÇÈÇB?
3. Найти все подмножества множества A= {x, y, z}.
4. Нарисовать диаграмму Эйлера-Венна для множества ÇС.
5. Счетно ли множество {(x, y): y = 3x, 0<x< ¥}?
Вариант № 19
1. В туристической группе 10 человек знают английский язык, 10 – итальянский, 6 – испанский. По два языка знают: 6 человек – английский и итальянский, 4 – английский и испанский, 3 – итальянский и испанский. Один человек знает все три языка. Сколько туристов в группе?
2. Упростить .
3. Привести пример двух множеств А и В, таких, что мощность множества А больше мощности множества В.
4. Нарисовать диаграмму Эйлера-Венна для множества С \ (С Ç (AÈB)).
5. Эквивалентны ли множества A = { 2n, n = 1, 2, …} и B = {n2, n = 1, 2, …}?
Вариант № 20
1. Предприятие объявило набор рабочих на должности токаря, слесаря и сварщика. В отдел кадров обратились 25 человек. Из них 10 человек владели профессией токаря, 15 – слесаря, 12 – сварщика. Профессией и токаря и слесаря владели 6 человек, и токаря, и сварщика – 5 человек, и слесаря и сварщика – 3 человека. Сколько человек владеют всеми тремя профессиями?
2. Верно или неверно равенство: \ = \ ?
3. Привести примеры множеств А, В и С , для которых одновременно выполняются равенства А È В È С = А и А Ç В Ç С = С.
4. Нарисовать диаграмму Эйлера-Венна для множества \ .
5. Можно ли построить взаимно-однозначное соответствие между множеством рациональных чисел отрезка [0, 1] и множеством рациональных чисел из этого интервала? Ответ обосновать.
Вариант № 21
1. Оказалось, что в группе туристов 15 человек были раньше во Франции, 19 – в Италии, 8 – в Германии. 9 туристов были во Франции и в Италии, 7 – во Франции и в Германии, 6 – и в Италии, и в Германии. 4 туриста были во всех трех странах. Сколько туристов были хотя бы в одной из трех стран?
2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В Ç С) = (А \ В) Ç ?
3. Привести примеры множеств А и В, для которых равенство È В =
а) выполняется; б) не выполняется.
4. Нарисовать диаграмму Эйлера-Венна для множества А Ç (В È ).
5. Найти мощность множества точек окружности с центром в точке (0, 0) и радиусом 1.
Вариант № 22
1. Группе студентов из 30 человек была предложена контрольная работа из трех задач. Первую задачу решили 15 студентов, вторую – 13, третью – 12. Первую и вторую задачи решили 7 человек, первую и третью – 6, вторую и третью – 5 человек. Все три задачи решили 2 студента. Сколько студентов из группы не решили ни одной задачи?
2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В È С) = (А \ В) Ç ?
3. Привести пример двух бесконечных множеств А и В, таких, что мощность множества А больше мощности множества В.
4. Нарисовать диаграмму Эйлера-Венна для множества А Ç В Ç .
5. Найти мощность множества точек гиперболы y = при x Î ( 3, ¥).
Вариант № 23
1. Анализ историй болезней группы из 20 детей показало, что 10 детей болели ветрянкой, 6 – корью, 5 – свинкой. Ветрянкой и корью болели 3 ребенка, ветрянкой и свинкой – 3, корью и свинкой – 2. Всеми тремя болезнями болел один ребенок. Сколько детей не болели ни одной из перечисленных болезней?
2. Верно или неверно равенство: ÇС) = ÇÇ С?
3. Доказать, что множество точек A= {(x, y): y = ½x+1½, – 1 £ x £ 1} несчетно.
4. Нарисовать диаграмму Эйлера-Венна для множества (BÇC) \ A .
5. Пусть A – множество точек отрезка [1, 2], а B – множество точек интервала (0, 3). Какие из следующих отношений справедливы: а) A =B; б) A ~ B; в) A Ì B; г) A Ê B; д) A ËB; е) A Î B.
Вариант № 24
1. В книжный киоск привезли для продажи 100 книг Пушкина, Лермонтова и Тургенева. Книги Пушкина купили 60 человек, книги Лермонтова – 50, книги Тургенева – 30 человек. Книги Пушкина и Лермонтова купили 40 человек, книги Пушкина и Тургенева – 20, книги Лермонтова и Тургенева – 10 человек. Пять человек купили книги всех трех писателей. Сколько человек не купили ни одной из перечисленных книг?
2. Верно или неверно равенство:\ = \ ?
3. Привести примеры множеств А, В и С таких, что равенство А È В È С = С
а) справедливо; б) несправедливо.
4. Нарисовать диаграмму Эйлера-Венна для множества \ .
5. Можно ли построить взаимно-однозначное соответствие между множеством натуральных чисел N и множеством действительных чисел отрезка [0, 1]? Ответ обосновать.
Вариант № 25
1. Группа научных работников состоит из 100 человек. Из них 70 человек владеют английским языком, 50 – немецким, 40 – французским, 30 – английским и немецким, 25 – английским и французским, 15 – французским и немецким. Хотя бы один язык знает каждый научный работник. Сколько человек владеют всеми тремя языками?
2. Упростить: (A \ (AÇB)) È В.
3. Привести примеры множеств А, В и С так, чтобы A Î B, В Ì С.
4. Нарисовать диаграмму Эйлера-Венна для множества \ .
5. Можно ли утверждать, что множество всех положительных пятизначных чисел счетно? Ответ обосновать.
Вариант № 26
1. На курсы иностранных языков записалось 100 человек. Оказалось, что 70 человек будут изучать английский язык, 60 человек – французский и 30 человек - немецкий. Английский и французский собираются изучать 40 человек, английский и немецкий – 20, французский и немецкий – 10. Сколько студентов будут изучать все три языка?
2. Упростить равенство: (A Ç С )\ (С Ç (A ÈB)).
3. Привести пример двух различных бесконечных множеств А и В, таких, что мощность множества А равна мощности множества В.
4. Нарисовать диаграмму Эйлера-Венна для множества ÇС).
5. Эквивалентны ли множества A = {x: x3 – 1 = 0} и B = {x: x2 – 3x + 2 = 0}?
Вариант № 27
В команде бегунов десять спортсменов бегают на длинные дистанции, восемнадцать – на средние, двенадцать – на короткие. На длинные и средние дистанции бегают пять спортсменов, на средние и короткие – шесть. На длинные и короткие дистанции не бегает никто. Сколько бегунов в команде?
2. Верно или неверно равенство: ÈС) = ÈÈ С?
3. В каком случае A ÈB = А Ç В?
4. Нарисовать диаграмму Эйлера-Венна для множества È(BÇC ) .
5. Можно ли утверждать, что множество всех положительных чисел имеет меньшую мощность, чем множество всех действительных чисел? Ответ обосновать.
Вариант № 28
1. В студенческой группе 25 человек. Чтобы получить допуск на экзамен по данному курсу необходимо защитить курсовую работу, выполнить лабораторную работу и сдать зачет. 15 студентов защитили курсовую работу, 20 выполнили лабораторную работу, 17 сдали зачет. Защитили курсовую работу и выполнили лабораторную работу 12 человек. Защитили курсовую работу и сдали зачет 13 человек. Выполнили лабораторную работу и сдали зачет 16 человек. Сколько студентов допущено к экзамену?
2. Упростить: Ç (È).
3. Привести пример двух бесконечных множеств А и В, таких, что мощность множества А меньше мощности множества В.
4. Нарисовать диаграмму Эйлера-Венна для множества \ .
5. Эквивалентны ли множество рациональных чисел отрезка [0, 1] и множество рациональных чисел из этого интервала? Ответ обосновать.
Вариант № 29
1. В классе 20 детей. Из них 10 дополнительно занимаются в музыкальной школе, 6 – теннисом, 5 – китайским языком. Музыкальную школу и занятия по теннису посещают три ребенка, музыкой и китайским языком занимаются трое, теннисом и китайским языком двое. Всеми тремя видами дополнительных занятий занимается один ребенок. Сколько детей не занимается ни одним из перечисленных занятий?
2. Пользуясь равносильными преобразованиями, установить, верно или неверно равенство: А \ (В ÈС) = (А \В) Ç?
3. Доказать, что множество точек A = {y: y = 2n, n = 1, 2, …} счетно.
4. Нарисовать диаграмму Эйлера-Венна для множества A ÇÈÇB .
5. Эквивалентны ли множества A = {(x, y): y = x2, 1< x <2} и B = {(x, y): y = 2x, 3< x < ¥}?
Вариант № 30
1. В цеху имеется 25 станков, которые могут выполнять три вида операций: А, В и С. Из них 10 станков выполняют операцию А, 15 – В, 12 – С. Операции А и В могут быть выполнены на 6 станках, А и С – на 5, В и С – на 3 станках. Сколько станков могут выполнять все три операции?
2. Верно или неверно равенство: \ = \ ?
3. Привести примеры множеств А, В и С , для которых одновременно выполняются равенства А È В È С = А и А Ç В Ç С = С.
4. Нарисовать диаграмму Эйлера-Венна для множества ÇС.
5. Можно ли построить взаимно-однозначное соответствие между множеством действительных чисел отрезка [0, 1] и множеством действительных чисел интервала (0, 1)? Ответ обосновать.
2. Раздел «Отношения. Функции»
Вариант № 1
1. Задано бинарное отношение r = {<1, 1>, <1, 3>, <3, 1>, <3, 4>, <4, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не рефлексивного, не симметричного и транзитивного.
3. Дана функция f(x) = x2 + ex, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 2
1. Задано бинарное отношение r = {<1, 3>, <3, 1>, <3, 4>, <4, 3>, <4, 4>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не симметричного, но рефлексивного и транзитивного.
3. Дана функция f(x) = x2 + e-x, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 3
1. Задано бинарное отношение r = {<2, 2>, <2, 3>, <3, 2>, <3, 4>, <4, 1>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, но рефлексивного и симметричного.
3. Дана функция f(x) = x + ex, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 4
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 3>, <4, 4>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x2 + y2 = 25?
3. Дана функция f(x) = x3 + ex, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 5
1. Задано бинарное отношение r = {<1, 2>, <2, 1>, <3, 4>, <4, 3>, <4, 4>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не симметричного, не рефлексивного и транзитивного.
3. Дана функция f(x) = x + e--x, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 6
1. Задано бинарное отношение r = {<2, 2>, <2, 3>, <3, 2>, <3, 1>, <4, 1>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения транзитивного, рефлексивного и антисимметричного.
3. Дана функция f(x) = x + ex, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 7
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <2, 4>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения рефлексивного, симметричного и транзитивного.
3. Дана функция f(x) = x 2 +, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 8
1. Задано бинарное отношение r = {<2, 2>, <2, 3>, <3, 2>, <3, 4>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения транзитивного, рефлексивного и антисимметричного.
3. Дана функция f(x) = x +, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 9
1. Задано бинарное отношение r = {<1, 2>, <2, 3>, <1, 3>, <1, 1>, <2, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения транзитивного, рефлексивного и симметричного.
3. Дана функция f(x) = sinx +, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 10
1. Задано бинарное отношение r = {<1, 1>, <2, 3>, <1, 3>, <3, 1>, <3, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x = 2y?
3. Дана функция f(x) = lnx +, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 11
1. Задано бинарное отношение r = {<1, 1>, <2, 4>, <1, 4>, <4, 1>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и не симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и являющейся сюръективной, инъективной, биективной.
Вариант № 12
1. Задано бинарное отношение r = {<1, 1>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x + y = 100?
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и не являющейся сюръективной, инъективной, биективной.
Вариант № 13
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 1>, <1, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и являющейся сюръективной, но не инъективной.
Вариант № 14
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <2, 1>, <2, 4>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения рефлексивного, симметричного и транзитивного.
3. Дана функция f(x) = x 2, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 15
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <2, 4>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения эквивалентности.
3. Дана функция f(x) = x 2 +, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 16
1. Задано бинарное отношение r = {<b, b>, <b, c>, <c, b>, <c, a>, <d, a>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения частичного порядка на множестве целых чисел..
3. Дана функция f(x) = x 2 +lnx, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 17
1. Задано бинарное отношение r = {<x, x>, <y, z>, <x, z>, <z, x>, <z, y>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения транзитивного и симметричного.
3. Дана функция f(x) = x +, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 18.
1. Задано бинарное отношение r = {<1, 1>, <1, a>, <a, 1>, <a, 4>, <4, a>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения рефлексивного и транзитивного.
3. Дана функция f(x) = x 2 + 2x, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 19
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <2, 3>, <3, 2>, <3, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x 2 – y2 = 0?
3. Дана функция f(x) = 2x +, отображающая множество положительных действительных чисел во множество всех действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 20
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 3>, <4, 4>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не рефлексивного, не симметричного и не транзитивного.
3. Дана функция f(x) = x3ex, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 21
1. Задано бинарное отношение r = {<1, 3>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения частичного порядка на множестве треугольников на плоскости.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и не являющейся сюръективной, инъективной, биективной.
Вариант № 22
1. Задано бинарное отношение r = {<1, 2>, <2, 2>, <2, 1>, <2, 3>, <3, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством x = – y?
3. Дана функция f(x) = lnx +, отображающая множество положительных действительных чисел во множество всех действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 23
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <2, 1>, <2, 3>, <3, 2>, <3, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением частичного полрядка на множестве действительных чисел отношение xry, задаваемое неравенством x 2 – y2 0?
3. Дана функция f(x) = ex +, отображающая множество положительных действительных чисел на множество положительных действительных чисел. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 24
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <3, 1>, <3, 2> <1, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество неотрицательных действительных чисел, R® [0, ) и являющейся сюръективной, но не инъективной.
Вариант № 25
1. Задано бинарное отношение r = {<1, 2>, <2, 1>, <2, 3>, <1, 3>, <3, 1>, <3, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое неравенством x y?
3. Дана функция f(x) = lnx + 2x, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 26
1. Задано бинарное отношение r = {<2, 2>, <2, 4>, <1, 4>, <4, 1>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и не симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и являющейся сюръективной и неинъективной.
Вариант № 27
1. Задано бинарное отношение r = {<1, 1>, <3, 4>, <1, 4>, <4, 1>, <4, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Будет ли отношением эквивалентности на множестве действительных чисел отношение xry, задаваемое равенством xy = 100?
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и не являющейся сюръективной, инъективной, биективной.
Вариант № 28
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <3, 3>, <3, 1>, <1, 3>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения не транзитивного, не рефлексивного и симметричного.
3. Привести пример функции f(x), отображающей множество действительных чисел R во множество действительных чисел, R® R и являющейся сюръективной, но не инъективной.
Вариант № 29
1. Задано бинарное отношение r = {<1, 1>, <2, 2>, <4, 4>, <2, 1>, <2, 4>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения частичного порядка.
3. Дана функция f(x) = x 2, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
Вариант № 30
1. Задано бинарное отношение r = {<1, 1>, <1, 2>, <2, 1>, <2, 4>, <4, 2>}.
Найти D(r), R(r), rr, r -1. Проверить, будет ли отношение r рефлексивным, симметричным, антисимметричным, транзитивным?
2. Привести пример отношения эквивалентности.
3. Дана функция f(x) = x 2 +, отображающая множество действительных чисел R во множество действительных чисел, R® R. Является ли эта функция сюръективной, инъективной, биективной? Почему?
3. Раздел «Графы»
1. Описать граф, заданный матрицей смежности, используя как можно больше характеристик. Составить матрицу инцидентности и связности (сильной связности).
2. Пользуясь алгоритмом Форда-Беллмана, найти минимальный путь из x1 в x7 в ориентированном графе, заданном матрицей весов.
3. Пользуясь алгоритмом Краскала, найти минимальное остовное дерево для графа, заданного матрицей длин ребер.
Варианты заданий
1 .1. 0 1 1 0 1 1 2. ¥ 4 6 12 ¥ ¥ ¥ 3. ¥ 12 6 20 14
1 0 0 1 0 0 ¥ ¥ ¥ 13 7 ¥ ¥ 12 ¥ 2 4 6
1 0 0 0 1 0 ¥ ¥ ¥ 5 ¥ 3 ¥ 6 2 ¥ 10 12
0 1 0 0 1 0 ¥ ¥ ¥ ¥ 10 9 ¥ 20 4 10 ¥ 6
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 8 14 6 12 6 ¥
1 0 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 11
¥ ¥ ¥ ¥ ¥ ¥ ¥
2 .1. 0 0 0 0 0 1 2. ¥ 1 3 9 ¥ ¥ ¥ 3. ¥ 1 ¥ 4 5
0 0 1 1 1 0 ¥ ¥ ¥ 10 4 ¥ ¥ 1 ¥ 2 ¥ 1
0 0 0 0 0 0 ¥ ¥ ¥ 2 ¥ 1 ¥ ¥ 2 ¥ 1 1
1 0 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 ¥ 1 ¥ 3
1 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 5 5 1 1 3 ¥
1 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 8
¥ ¥ ¥ ¥ ¥ ¥ ¥
3 .1. 0 1 0 1 0 0 2. ¥ 3 5 11 ¥ ¥ ¥ 3. ¥ 6 3 10 7
1 0 0 1 0 0 ¥ ¥ ¥ 12 6 ¥ ¥ 6 ¥ 1 2 3
0 0 0 0 1 1 ¥ ¥ ¥ 3 ¥ 2 ¥ 3 1 ¥ 5 6
1 1 0 0 1 1 ¥ ¥ ¥ ¥ 9 8 ¥ 10 2 5 ¥ 3
0 0 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 7 7 3 6 3 ¥
0 0 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 10
¥ ¥ ¥ ¥ ¥ ¥ ¥
4.1. 0 0 0 0 0 1 2. ¥ ¥ 5 4 2 2 9 3. ¥ 7 2 11 7
1 0 1 0 1 1 ¥ ¥ 1 1 ¥ 1 1 7 ¥ 3 ¥ 4
1 0 0 0 0 0 2 ¥ ¥ 1 1 ¥ 3 2 3 ¥ 1 5
0 0 1 0 0 1 ¥ 2 1 ¥ 1 ¥ ¥ 11 ¥ 1 ¥ 3
0 1 1 1 0 0 ¥ ¥ 2 2 ¥ 1 6 7 4 5 3 ¥
0 0 1 0 0 0 1 5 ¥ 1 1 ¥ ¥
2 ¥ 1 ¥ 1 2 ¥
5 .1. 0 0 0 1 1 0 2. ¥ 4 ¥ ¥ 3 1 ¥ 3. ¥ 2 ¥ 5 5
0 0 0 1 0 1 3 ¥ 2 1 ¥ ¥ 4 2 ¥ 8 ¥ 7
1 0 0 0 0 0 1 1 ¥ ¥ ¥ ¥ 1 ¥ 8 ¥ 10 1
0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 5 ¥ 10 ¥ 13
1 0 0 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 13 ¥
0 1 0 1 0 0 ¥ 3 ¥ 2 2 ¥ ¥
¥ ¥ 2 ¥ ¥ 2 ¥
6.1. 0 0 1 0 1 0 2. ¥ ¥ 9 ¥ ¥ 2 12 3. ¥ 1 5 4 5
0 0 1 1 1 1 1 ¥ ¥ ¥ 1 2 4 1 ¥ 2 6 1
1 1 0 0 1 0 2 1 ¥ ¥ 1 ¥ 2 5 2 ¥ 1 7
0 1 0 0 0 1 ¥ 1 1 ¥ ¥ 1 ¥ 4 6 1 ¥ 4
1 1 1 0 0 0 1 2 ¥ 2 ¥ ¥ ¥ 5 1 7 4 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8
¥ 2 1 ¥ 1 2 ¥
7.1. 0 0 1 1 0 0 2. ¥ 3 4 9 ¥ ¥ ¥ 3. ¥ 4 3 5 6
1 0 0 0 0 1 12 ¥ ¥ 10 4 ¥ ¥ 4 ¥ 2 ¥ 1
1 0 0 0 1 0 ¥ ¥ ¥ 2 ¥ 1 ¥ 3 2 ¥ 1 1
0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 5 ¥ 1 ¥ 3
0 0 1 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 5 6 1 1 3 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 8
¥ ¥ ¥ ¥ ¥ ¥ ¥
8 .1. 0 1 1 0 1 1 2. ¥ 2 5 8 9 ¥ ¥ 3. ¥ 1 3 4 5
1 0 1 1 0 1 ¥ ¥ ¥ 10 4 ¥ ¥ 1 ¥ 2 9 1
1 1 0 0 1 1 5 3 ¥ 2 1 ¥ ¥ 3 2 ¥ 1 1
0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 9 1 ¥ 3
1 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 5 5 1 1 3 ¥
1 1 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 9
¥ ¥ ¥ ¥ ¥ ¥ ¥
9 .1. 0 1 0 1 1 1 2. ¥ 2 5 14 ¥ ¥ ¥ 3. ¥ 5 3 10 7
1 0 0 1 0 0 11 ¥ ¥ 12 6 ¥ ¥ 5 ¥ 1 2 4
0 0 0 1 1 0 ¥ ¥ ¥ 3 ¥ 2 ¥ 3 1 ¥ 5 6
1 1 1 0 1 0 ¥ ¥ ¥ ¥ 9 8 ¥ 10 2 5 ¥ 3
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 7 7 4 6 3 ¥
1 0 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 10
¥ ¥ ¥ ¥ ¥ ¥ ¥
10.1 0 1 1 0 1 1 2. ¥ ¥ 5 4 2 3 9 3. ¥ 7 2 11 7
1 0 0 1 1 1 ¥ ¥ 1 1 ¥ 1 6 7 ¥ 3 ¥ 4
1 0 0 0 1 0 4 ¥ ¥ 1 1 ¥ 3 2 3 ¥ 1 5
0 1 0 0 0 1 ¥ 2 1 ¥ 1 ¥ ¥ 11 ¥ 1 ¥ 3
1 1 1 0 0 1 ¥ ¥ 2 2 ¥ 1 6 7 4 5 3 ¥
1 1 0 1 1 0 1 5 ¥ 1 1 ¥ ¥
2 ¥ 1 ¥ 1 2 ¥
11.1. 0 0 1 0 1 0 2. ¥ 4 9 ¥ 3 1 ¥ 3. ¥ 1 ¥ 4 5
0 0 0 1 0 1 3 ¥ 2 1 ¥ ¥ 4 1 ¥ 8 ¥ 7
1 0 0 0 1 0 1 1 ¥ ¥ 10 ¥ 1 ¥ 8 ¥ 10 1
0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 4 ¥ 10 ¥ 13
1 0 1 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 13 ¥
0 1 0 1 0 0 ¥ 3 ¥ 1 2 ¥ ¥
¥ ¥ 2 ¥ ¥ 2 ¥
12.1 0 0 1 0 1 0 2. ¥ ¥ 9 ¥ 10 2 12 3. ¥ 1 5 4 6
0 0 0 1 0 1 1 ¥ ¥ ¥ 1 2 4 1 ¥ 2 6 3
1 1 0 0 1 1 2 1 ¥ ¥ 1 ¥ 2 5 2 ¥ 1 7
0 0 0 0 0 0 ¥ 1 1 ¥ ¥ 1 15 4 6 1 ¥ 4
1 1 1 0 0 0 1 2 ¥ 2 ¥ ¥ ¥ 6 3 7 4 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8
¥ 2 1 ¥ 1 2 ¥
13.1. 0 0 0 0 0 0 2. ¥ 5 6 15 ¥ ¥ ¥ 3. ¥ 12 6 10 4
1 0 0 1 0 1 ¥ ¥ ¥ 13 7 ¥ ¥ 12 ¥ 2 5 6
1 0 0 0 1 0 ¥ ¥ ¥ 4 ¥ 3 ¥ 6 2 ¥ 10 12
1 1 1 0 0 0 ¥ ¥ ¥ ¥ 10 9 ¥ 10 5 10 ¥ 6
1 1 0 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 8 4 6 12 6 ¥
0 1 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 11
¥ ¥ ¥ ¥ ¥ ¥ ¥
14.1. 0 0 1 1 0 0 2. ¥ 2 3 9 ¥ ¥ ¥ 3. ¥ 3 2 4 5
1 0 0 0 0 1 12 ¥ ¥ 10 4 ¥ ¥ 3 ¥ 2 ¥ 1
1 0 0 0 1 0 ¥ ¥ ¥ 2 ¥ 1 ¥ 2 2 ¥ 1 1
0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 ¥ 1 ¥ 3
0 0 1 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 5 5 1 1 3 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 8
¥ ¥ ¥ ¥ ¥ ¥ ¥
15.1. 0 1 0 1 0 0 2. ¥ 2 5 10 ¥ ¥ ¥ 3. ¥ 6 3 10 4
1 0 0 1 0 0 ¥ ¥ ¥ 12 6 ¥ ¥ 6 ¥ 1 2 3
0 0 0 0 1 1 ¥ ¥ ¥ 3 ¥ 1 ¥ 3 1 ¥ 8 6
1 1 0 0 1 1 ¥ ¥ ¥ ¥ 9 8 ¥ 10 2 8 ¥ 3
0 0 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 7 4 3 6 3 ¥
0 0 1 1 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 10
¥ ¥ ¥ ¥ ¥ ¥ ¥
16.1. 0 0 0 0 1 1 2. ¥ ¥ 5 4 2 2 10 3. ¥ 4 2 10 6
0 0 1 1 0 0 ¥ ¥ 2 1 ¥ 2 1 4 ¥ 3 ¥ 4
0 1 0 0 1 0 2 ¥ ¥ 1 1 ¥ 3 2 3 ¥ 1 5
0 1 0 0 0 1 ¥ 2 1 ¥ 1 ¥ ¥ 10 ¥ 1 ¥ 3
1 0 1 0 0 0 ¥ ¥ 2 2 ¥ 1 6 6 4 5 3 ¥
1 0 0 1 0 0 1 5 ¥ 1 1 ¥ ¥
2 ¥ 1 ¥ 1 2 ¥
17.1 0 0 1 0 1 0 2. ¥ 4 9 8 3 1 ¥ 3. ¥ 2 ¥ 3 5
0 0 0 1 0 1 3 ¥ 2 1 ¥ ¥ 4 2 ¥ 8 ¥ 7
1 0 0 0 1 0 1 1 ¥ ¥ ¥ ¥ 1 ¥ 8 ¥ 10 1
0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 3 ¥ 10 ¥ 12
1 0 1 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 12 ¥
0 1 0 1 0 0 ¥ 3 ¥ 2 2 ¥ ¥
¥ ¥ 2 ¥ ¥ 2 ¥
18.1. 0 0 1 0 1 0 2. ¥ ¥ 9 ¥ 10 2 12 3. ¥ 1 3 4 5
0 0 0 0 0 0 1 ¥ ¥ ¥ 1 2 4 1 ¥ 2 6 8
1 0 0 0 1 0 2 1 ¥ ¥ 1 ¥ 2 3 2 ¥ 1 7
0 1 0 0 0 1 ¥ 1 1 ¥ ¥ 1 ¥ 4 6 1 ¥ 4
1 0 1 0 0 0 1 2 9 2 ¥ ¥ ¥ 5 8 7 4 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8
¥ 2 1 ¥ 1 2 ¥
19.1. 0 1 1 0 1 1 2. ¥ 3 5 12 20 ¥ ¥ 3. ¥ 1 6 5 14
1 0 0 1 0 0 ¥ ¥ ¥ 13 8 ¥ ¥ 1 ¥ 3 4 6
1 0 0 1 1 1 ¥ ¥ ¥ 5 ¥ 3 ¥ 6 3 ¥ 10 12
0 1 1 0 1 1 ¥ ¥ ¥ ¥ 10 9 ¥ 5 4 10 ¥ 6
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 8 14 6 12 6 ¥
1 0 1 1 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 11
¥ ¥ ¥ ¥ ¥ ¥ ¥
20.1. 0 1 0 0 1 0 2. ¥ 1 5 7 9 ¥ ¥ 3. ¥ 6 3 4 5
1 0 0 1 0 0 ¥ ¥ ¥ 10 4 ¥ ¥ 6 ¥ 2 9 1
1 0 0 0 1 1 5 3 ¥ ¥ 1 ¥ ¥ 3 2 ¥ 1 4
0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 9 1 ¥ 3
0 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 4 5 1 4 3 ¥
0 1 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 9
¥ ¥ ¥ ¥ ¥ ¥ ¥
21.1. 0 1 0 1 1 1 2. ¥ 1 5 15 ¥ ¥ ¥ 3. ¥ 5 3 6 7
1 0 0 1 0 0 ¥ ¥ 11 12 6 ¥ ¥ 5 ¥ 1 2 4
0 0 0 1 1 0 ¥ ¥ ¥ 3 ¥ 2 ¥ 3 1 ¥ 5 6
1 1 1 0 1 0 ¥ ¥ ¥ ¥ 9 8 ¥ 6 2 5 ¥ 3
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 7 7 4 6 3 ¥
1 0 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 10
¥ ¥ ¥ ¥ ¥ ¥ ¥
22.1 0 0 1 0 1 0 2. ¥ ¥ 3 4 1 5 9 3. ¥ 7 2 11 3
0 0 0 0 0 0 ¥ ¥ 1 2 ¥ 1 6 7 ¥ 3 ¥ 4
0 1 0 0 1 1 4 ¥ ¥ 2 1 ¥ 3 2 3 ¥ 1 5
0 1 0 0 0 1 ¥ 2 3 ¥ 1 ¥ ¥ 11 ¥ 1 ¥ 3
1 1 1 0 0 0 ¥ ¥ 2 2 ¥ 1 6 3 4 5 3 ¥
0 0 0 1 1 0 1 5 ¥ 1 1 ¥ ¥
2 ¥ 1 ¥ 1 2 ¥
23.1. 0 0 1 0 1 0 2. ¥ 4 9 ¥ 3 1 ¥ 3. ¥ 1 9 4 5
0 0 0 1 0 1 3 ¥ 2 1 ¥ ¥ 4 1 ¥ 8 ¥ 7
1 0 0 0 1 0 1 1 ¥ ¥ 10 14 1 9 8 ¥ 10 1
0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 4 ¥ 10 ¥ 13
1 0 1 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 13 ¥
0 1 0 1 0 0 ¥ 3 ¥ 1 2 ¥ ¥
¥ ¥ 2 ¥ ¥ 2 ¥
24.1 0 0 1 0 1 0 2. ¥ ¥ 8 ¥ 10 3 12 3. ¥ 3 2 4 6
0 0 0 1 0 0 1 ¥ ¥ ¥ 1 2 3 3 ¥ 5 6 3
0 1 0 0 1 0 2 1 ¥ ¥ 1 ¥ 2 2 5 ¥ 1 7
0 0 0 0 0 1 ¥ 1 1 ¥ ¥ 1 15 4 6 1 ¥ 4
0 1 1 0 0 0 1 2 ¥ 2 ¥ ¥ ¥ 6 3 7 4 ¥
0 1 0 0 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8
¥ 2 1 ¥ 1 2 ¥
25.1. 0 0 1 0 0 1 2. ¥ ¥ 5 4 2 2 10 3. ¥ 1 2 8 5
0 0 1 1 1 1 ¥ ¥ 2 1 ¥ 2 1 1 ¥ 3 ¥ 4
1 1 0 0 0 0 2 ¥ ¥ 1 1 ¥ 3 2 3 ¥ 1 5
0 1 0 0 0 1 12 2 1 ¥ 1 ¥ ¥ 8 ¥ 1 ¥ 3
0 1 0 0 0 1 ¥ ¥ 2 2 ¥ 1 6 5 4 5 3 ¥
1 1 0 1 1 0 1 5 ¥ 1 1 ¥ ¥
2 ¥ 1 ¥ 1 2 ¥
26.1. 0 0 0 0 1 0 2. ¥ 4 9 8 3 2 ¥ 3. ¥ 2 9 3 5
0 0 0 1 0 0 3 ¥ 2 1 ¥ ¥ 5 2 ¥ 8 ¥ 7
1 0 0 0 1 0 2 1 ¥ ¥ ¥ ¥ 1 9 8 ¥ 10 1
0 1 0 0 0 1 ¥ 3 1 ¥ 1 ¥ ¥ 3 ¥ 10 ¥ 12
0 0 0 0 0 0 ¥ ¥ 2 ¥ ¥ 1 5 5 7 1 12 ¥
0 1 0 0 0 0 ¥ 3 ¥ 2 2 ¥ ¥
¥ ¥ 2 ¥ ¥ 2 ¥
27.1. 0 0 1 0 1 0 2. ¥ ¥ 9 ¥ 8 1 12 3. ¥ 1 3 7 2
0 0 1 1 1 1 1 ¥ ¥ ¥ 2 2 4 1 ¥ 5 6 8
1 1 0 0 1 0 2 1 ¥ ¥ 1 ¥ 2 3 5 ¥ 1 7
0 1 0 0 0 1 ¥ 1 1 ¥ ¥ 1 ¥ 7 6 1 ¥ 4
1 1 1 0 0 0 1 2 9 2 ¥ ¥ ¥ 2 8 7 4 ¥
0 1 0 1 0 0 ¥ ¥ ¥ ¥ 1 ¥ 8
¥ 2 1 ¥ 1 2 ¥
28.1. 0 1 1 0 1 1 2. ¥ 3 5 12 20 ¥ ¥ 3. ¥ 1 6 5 14
1 0 0 1 0 0 ¥ ¥ ¥ 13 8 ¥ ¥ 1 ¥ 3 4 6
1 0 0 1 1 1 ¥ ¥ ¥ 5 ¥ 3 ¥ 6 3 ¥ 10 12
0 1 1 0 1 1 ¥ ¥ ¥ ¥ 10 9 ¥ 5 4 10 ¥ 6
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 8 14 6 12 6 ¥
1 0 1 1 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 11
¥ ¥ ¥ ¥ ¥ ¥ ¥
29.1. 0 1 0 0 1 0 2. ¥ 1 8 6 7 ¥ ¥ 3. ¥ 2 3 4 5
1 0 0 1 0 0 ¥ ¥ ¥ 10 4 ¥ ¥ 2 ¥ 6 9 1
1 0 0 0 1 1 5 3 ¥ ¥ 1 ¥ ¥ 3 6 ¥ 1 4
0 1 0 0 0 1 ¥ ¥ ¥ ¥ 7 6 ¥ 4 9 1 ¥ 3
0 0 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 4 5 1 4 3 ¥
0 1 1 0 0 0 ¥ ¥ ¥ ¥ ¥ ¥ 9
¥ ¥ ¥ ¥ ¥ ¥ ¥
30.1. 0 1 0 1 1 1 2. ¥ 2 4 13 ¥ ¥ ¥ 3. ¥ 5 3 6 4
1 0 0 1 0 0 ¥ ¥ 11 12 6 ¥ ¥ 5 ¥ 1 2 7
0 0 0 1 1 0 ¥ ¥ ¥ 3 ¥ 2 ¥ 3 1 ¥ 5 6
1 1 1 0 1 0 ¥ ¥ ¥ ¥ 9 8 ¥ 6 2 5 ¥ 3
1 0 1 1 0 1 ¥ ¥ ¥ ¥ ¥ ¥ 7 4 7 6 3 ¥
1 0 0 0 1 0 ¥ ¥ ¥ ¥ ¥ ¥ 10
¥ ¥ ¥ ¥ ¥ ¥ ¥
4. Раздел «Булевы функции»
Для данной формулы булевой функции
а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований;
б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”);
в) указать минимальную ДНФ и соответствующую ей переключательную схему.
Варианты заданий
|
Функция |
Функция |
|
1. ((x V y) É Øz) V x&y&z 2. Ø(x&(y É(xVz))) 3. (x É(z&(y ~ x))) 4. Ø(x~y) É (xVz) 5. Ø(x É y) V (y É z) 6. (x&y) É (Ø(x&z) ~ x) 7. (y Éx) ~(x É z) 8. (x&Øy) É ((ØxVz) & y) 9. Ø(x~y) É (xVz) 10. Ø(x& y) É ((xVz)É y) 11.x É(y É (z É y&z)) 12. ((y& Øz) É (xVØz)) É y 13. Ø(x&(y É (x ~ z))) 14. (x É(x&(yV Ø(x ~y)Vx))) 15. Ø(x É z) V Ø(y ~ z) |
16. Ø(x~y) É (xVz) 17. x&y É (Øx&z É (xVy)) 18. (y Éx) ~(Øx É z) 19. (x&Øy É z) É (x ~ z) 20. Ø(x&y É z) É (x É y) 21. Øx É(y É (z ~x)) 22. y&Øz É (xVØz&y) 23. Ø(x&(y É(z ~ y))) 24. x É(x&(yV Ø(x ~z))) 25. Ø(x É y)V Ø(y&(x~z)) 26. Ø(x ~ y) É Ø(x ~z) 27. Ø(x É y) É (x&z) 28. x É(z É(x V y&z)) 29. x&(y É(z ~ y)) 30. Ø(x É z) V (y ~ z) |
Вопросы к экзамену по дисциплине «Дискретная математика»
1. Основные понятия теории множеств: множества, подмножества, пустое множество, универсальное множество, множество-степень.
2. Способы задания множеств.
3. Операции над множествами.
4. Геометрическое моделирование множеств. Диаграммы Эйлера - Венна.
5. Алгебра множеств. Основные тождества алгебры множеств.
6. Эквивалентность множеств. Свойство транзитивности. Мощность множества.
7. Мощность объединения конечных множеств.
8. Эквивалентность множества точек отрезков и интервалов. Теорема Бернштейна.
9. Счетные множества. Теоремы о счетных множествах.
10. Мощность множества точек отрезка [0, 1]. Теорема Кантора.
11. Множества мощности континуума. Теоремы о множествах мощности континуума.
12. Отношения. Основные понятия и определения. Бинарные отношения. Область определения, область значений и область задания бинарного отношения.
13. Операции над отношениями. Обратное отношение, Композиция отношений.
14. Свойства отношений. Рефлексивность, симметричность, транзитивность, эквивалентность.
15. Классы эквивалентности. Разбиение множеств.
16. Отношение частичного порядка.
17. Функция как бинарное отношение. Область определения и область значений функции. Равенство функций.
18. Сюръективные, инъективные, биективные функции.
19. Обратная функция. Композиция функций.
20. Способы задания функций.
21. Определение графа. Различные типы графов.
22. Матричные способы задания графов.
23. Изоморфизм графов.
24. Маршруты, циклы в неориентированном графе.
25. Пути, контуры в ориентированном графе.
26. Связность неориентированного графа. Матрица связности.
27. Связность ориентированного графа. Матрицы односторонней и сильной связности..
28. Экстремальные пути в нагруженных ориентированных графах.
29. Алгоритм Форда – Беллмана нахождения минимального пути.
30. Деревья. Остовные деревья.
31. Минимальное остовное дерево. Алгоритм Краскала.
32. Определение булевой функции. Операции над булевыми функциями.
33. Формулы логики булевых функций.
34. Равносильные преобразования формул булевых функций.
35. Двойственность. Принцип двойственности.
36. Булева алгебра (алгебра логики). Полные системы булевых функций.
37. Нормальные формы формул булевых функций.
38. Разложение булевой функции по переменным.
39. Алгоритм Квайна построения сокращенной ДНФ.
40. Алгоритм Квайна – Мак-Класки построения сокращенной ДНФ.
41. Алгоритм построения минимальной ДНФ с помощью таблицы покрытий.
42. Применение алгебры булевых функций к релейно-контактным схемам.
1. Акимов О. Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001.
2. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. – М.: Энергоиздат, 1988.
3. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
4. Нефедов В. Н., Осипова В. А. Курс дискретной математики. – М.: Издательство МАИ, 1992.
5. Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2002.
6. Судоплатов С. В., Овчинникова В. В. Элементы дискретной математики. – М.: ИНФРА – М, Новосибирск: Изд-во НГТУ, 2002.
Краткие сведения о математиках
Арнольд Владимир Игоревич – математик, академик Российской Академии наук.
Беллман Ричард – американский математик.
Буль Джордж (1815 – 1864) – английский математик. Основатель математической логики.
Гильберт Давид (1862 – 1943) – немецкий математик. Его исследования оказали большое влияние на развитие многих разделов математики, особенно на развитие логических основ математики.
Дейкстра Эдсгер (1930 – 2002) – голландский ученый, виднейший специалист в области программирования, лауреат премии Тьюринга.
Декарт Рене (1596 – 1650) – французский математик и философ. Впервые ввел понятия переменной, функции, системы координат на плоскости.
Кантор Георг (1845 – 1918) – немецкий математик. Разработал теорию бесконечных множеств. Идеи Кантора оказали большое влияние на развитие математики.
Колмогоров Андрей Николаевич (1903 – 19 ) – советский математик, академике АН СССР. Основополагающее значение имеют работы в области теории вероятностей. Является автором фундаментальных работ по теории множеств, теории меры, конструктивной логике, топологии, механике, теории дифференциальных уравнений, функциональному анализу.
Фибоначчи (Леонардо Пизанский) (1180 – 1240) – итальянский математик. Основные работы – трактаты об арифметике, алгебре и геометрии, которые являются первыми произведениями, содержащими задачи на приложения алгебры и геометрии.
Эйлер Леонард (1707 – 1783) – математик, физик, механик, астроном. Родился в Швейцарии, с 1726 по 1741 г. и с 1776 по 1783 г. работал в России.