- •Министерство образования и науки республики казахстан
- •Практическая работа № 1. Основные понятия теории множеств. Отношения.
- •Практическая работа 2.
- •8. Найти элементы нечеткого множества , если,.
- •9. Найти элементы нечеткого множества , если,.
- •Практическая работа 3 Элементы математической логики
- •2. Записать сднф функции, заданной следующей картой Вейча:
- •3. Записать минтерм, отмеченный на карте Вейча: .
- •Практическая работа 4 Исчисление высказываний и исчисление предикатов
- •1. Записать символически высказывания, употребляя буквы для обозначения простых высказываний. Построить таблицы истинности для каждого высказывания:
- •XyA(X, y) и yxA(X, y)
- •Практическая работа 6 Элементы теории кодирования
- •Порождающая и проверочная матрицы
- •Практическая работа 7 Элементы комбинаторики
- •Перестановки без повторений
- •Перестановки с повторениями
- •Размещения с повторениями
- •Практическая работа 8 Теория графов
- •Практическая работа 9 Числа графов. Поиск маршрутов в графе. Цепи и циклы
- •2. Задача. Для данного неорграф g рис 2. Определить цикломатическое число. Выяснить можно ли нарисовать g, не отрывая руки от бумаги и не проходя ни по одному ребру дважды.
- •Рекомендуемая литература
- •Методические указания
Практическая работа 2.
Соответствия, отображения, функции. Взаимнооднозначные соответствия и мощности множеств. Теорема Кантора. Элементы теории нечетких множеств (2 час)
Цель работы: Ознакомиться с взаимнооднозначными соответствиями и мощности множеств. Рассмотреть Теорему Кантора. Элементы теории нечетких множеств
Порядок выполнения работы:
Практическая работа рассчитана на 2 часа аудиторных занятий, включающих в себя следующее:
1. Изучить:
- Взаимнооднозначные соответствия и мощности множеств.
- Счетные множества, теоремы о счетных множествах.
- Множества мощности континуума. Теорема Кантора.
- Способы задания нечетких множеств.
- Операции над нечеткими множествами.
2. Решить упражнения к разделу «Нечеткие множества». Выполнить каждый пункт упражнения согласно варианту. Вариант определяется как сумма двух последних цифр зачётной книжки, если количество заданий в пункте упражнения меньше, чем полученная цифра, то эта цифра делится пополам (берётся её целая часть).
3. Оформить отчет о проделанной работе в соответствии с требованиями.
4. Проработать контрольные задания СРС.
Требования к отчету:
Отчет по практической работе распечатывается в виде твердой копии и состоит из следующих пунктов:
Вариант индивидуального задания;
Результаты полученных решений заданий;
Ответы на контрольные задания СРС.
Методические указания
Отношения соответствия.
В общем случае между элементами множеств А и В могут быть четыре вида соответствия в зависимости от того, один или несколько элементов множества А соответствуют элементу множества В и один или несколько элементов множества В ставятся в соответствие элементу А:
Взаимно однозначное соответствие, когда каждому элементу ставится в соответствие единственный элементи когда каждому элементусоответствует только один элемент.
Одно-многозначное соответствие, когда каждому элементу ставится в соответствие несколько (более одного) элементов множества В, но каждому элементусоответствует только один элемент.
Много-однозначное соответствие, когда для каждого элемента существует только один элемент, но каждому элементу множества В соответствует более одного элемента множества А.
Много-многозначное соответствие, когда каждому элементу соответствует более одного элемента множества В и каждому элементусоответствует также более одного элемента множества А.
Множество, равномощное множеству всех натуральных чисел, называется счетным.
Мощность счетногомножества обозначается символомчитается: алеф нуль. Алеф первая буква финикийского (древнесемитского) алфавита.
Кардинальное число конечного множества А обозначается |A|. Это обозначение будем использовать и в случае бесконечных множеств. Например, если Е – счетное множество, то |E| =.
При ведем некоторые теоремы о счетных множествах.
Теорема 1.Всякое бесконечное множество содержит счетное подмножество.
Теорема 2.Всякое бесконечное подмножество счетного множества счетно.
Теорема 3.Множество всех целых чисел счетно.
Теорема 4.Объединение счетного множества В счетно.
Теорема 5.Объединение конечного множества счетных множеств счетно.
Теорема 6.Декартово произведение двух счетных множеств А и В счетно.
Теорема 7.Объединение счетного множества счетных множествA,B,C… счетно.
Теорема 8.множество всех рациональных чисел счетно. Рациональными называют все положительные и отрицательные дроби вида, где P и q – натуральные числа. К рациональным относятся все целые положительные и отрицательные числа, а также нуль.
Теорема 9.множество всех алгебраических чисел счетно.
Несчетные множества.
Если А - конечное множество, то |A|<|B(A)|, то есть булеан всякого конечного множества А содержит больше элементов , чем множество А, т.к.
Всякое бесконечное множество также имеет подмножества и можно говорить о мощности его булеана.
Множество всех двоичных чисел бесконечной длины, представляется кардинальным числом
Теорема. Мощность булеана бесконечного множества Е превышает мощность множества Е. Это очень важная теорема. Если Е – счетное множество, то согласно приведенной теореме
Множество В(Е) несчетно и его мощность равна мощности континуума (continuum– в переводе с латинского - непрерывное). Примером континуума может служить множество точек отрезка.
Несчетным является и множество всех действительных чисел в интервале . Для доказательства этого сначала предположим, что все действительные числа можно пронумеровать. Запишем одна под другой бесконечные десятичные дроби:
…
Получим матрицу, содержащую четное множество строк, в каждой из которых бесконечное число десятичных цифр. Допустим, что в матрице нет не одной пары равных между собой чисел. Все ли действительные числа окажутся в матрице? Нет, не все. Чтобы убедится в этом воспользуемся диагональным методом, разработанным Г. Кантором, и найдем число, которое соответствует матрице, т.е. оказалось незанумерованным. Суть метода Г. Кантора применительно к данному случаю состоит в следующем. Если в первом числе первая после запятой цифра (цифра ) не равна, например, 3, то в искомое число после запятой записываем цифру 3. Если же=3, то записываем, допустим 2. Переходя ко второму числу матрицы. Если, то записываем на втором месте искомого числа цифру 3. Если, то записываем число 2. Перейдя к третьему числу, записываем искомое число 3, еслии т.д. Очевидно что получившееся число отсутствует в списке, так как оно отличается от первого числа после запятой цифрой, от второго числа отличается цифрой от третьего – третьей и т.д. Таким образом полученное число отсутствует в списке, но принадлежит множеству действительных чисел интервала.
Полученное число не является единственным отсутствующим в списке. Достаточно вместо цифры 3 и 2 взять какие-нибудь другие и мы получим еще одно число. Даже если найденные числа включит в общий список, то и в расширенном списке будут находится не занумерованные числа.
Так как мощность булеана В(Е) равна мощности множества всех действительных чисел интервала , то эти множества эквивалентны. Они являются несчетными и оба характеризуются кардинальным числом. Такие множества условно называют-множествами.
Мощность континуума – не самая большая мощность среди бесконечных множеств. Что бы убедится в этом воспользуемся двоичными числами, так же как и в случае с счетными множествами. Поставим в соответствие каждому элементу -множества двоичный разряд. Если единица в числе обозначает вхождение элемента в подмножество, а нуль – отсутствие элемента в данном подмножестве, то каждому двоичному числу будет соответствовать некоторое подмножество-множества. Мощность множества таких подмножеств обозначается буквой, очевидно, что
Откуда следует что мощность булеана -множества превышает мощность-множества.
Точно так же можно утверждать, что
То есть мощность -множества превышает мощность булеана-множества. Далее по аналогии получаем :
,,,…,,…
Откуда следует, что множества с наибольшей мощностью не существует.
В завершение подраздела приведем одну теорему о множествах мощности континуума: объединение множества мощности континуума и счетного множества имеет мощность континуума.
Под нечётким множеством A понимается совокупность
, где Х — универсальное множество, а — функция принадлежности (характеристическая функция), характеризующая степень принадлежности элементанечёткому множеству А .
Функция принимает значения в некотором вполне упорядоченном множествеМ. Множество М называют множеством принадлежностей, часто в качестве М выбирается отрезок . Если, то нечёткое множество может рассматриваться как обычное, чёткое множество.
Упражнения для выполнения:
Упражнение 1
1. Найдите │R│, еслиRопределено следующим образом:xделитy(без остатка);
x A;y B, где
A= {1, 2, 3, 4, 5};B= {6, 7, 8, 9, 10, 11, 12}. (26)
2. Найдите │R│, еслиRна паре множеств (26) определено следующим образом:
x<y; гдеx A; y B
3. Определите │aRb│ для множеств (26), еслиR– это отношение:a A- нечетное число;b B.
4. Определите │aRb│ для множеств (26), еслиR– это отношение:a A- простое число;b АВ – четное или простое число.
5. Найдите для множеств (26), еслиR– это отношение:a=b; гдеa A,b B.
6. Найдите │R│, еслиRопределено следующим образом:x В;y А, где
A= {1, 2, 3, 4, 5};B= {3, 4, 5, 6, 7, 8, 9, 10}.
Упражнение 2
1. Укажите транзитивные отношения:
равно; меньше на 5; больше или равно; быть южнее;
не равно; быть врагом; быть другом; быть логарифмом.
2. Укажите интранзитивные отношения в упр. 1.
3. Укажите нетранзитивные отношения в упр. 1.
Упражнение 3
1. Укажите рефлексивные отношения:
1) Таня – сестра Зины;
2) a ≤ b, где a и b – натуральные числа;
3) a ≠ b, где a и b – натуральные числа;
4) треугольник a подобен треугольнику b;
5) площадь круга a больше площади круга b;
6) Иван написал письмо Петру;
7) выражения a и b имеют одно и то же значение в множестве числовых выражений.
2. Укажите симметричные отношения в упр. 1.
3. Укажите рефлексивные отношения:
1) a похож на b (в множестве людей);
2) в книге a в два раза больше страниц, чем в книге b;
3) фраза a имеет тот же смысл, что и фраза b;
4) Петров и Сидоров имеют одинаковый рост;
5) дорога a имеет ту же длину, что и дорога b;
6) Смирнов и Васильев живут на третьем этаже;
7) поезд a идет быстрее поезда b.
4. Укажите отношения, являющиеся одновременно транзитивными и рефлексивными:
1) число a равно числу b;
2) Иванов и Петров служат в одном полку;
3) a и b равновеликие треугольники;
4) число a не больше числа b;
5) тетрадь a дороже тетради b;
6) Афанасьев слушает Васильева;
7) Иванов дал книгу Петрову.
5. Укажите отношения эквивалентности:
1) Иванов задал вопрос Петрову;
2) Книга a имеет такую же цену, что и книга b;
3) Смирнов попрощался с Федоровым;
4) Саша позвал в гости Игоря;
5) Павлов и Васильев смотрят один и тот же фильм;
6) Высота горы a равна высоте горы b;
7) Федоров и Савин поступили в ТУСУР в одном и том же году.
6. Укажите отношения строгого порядка:
1) Иванов выше Сидорова;
2) Лена – сестра Наташи;
3) Отрезок a короче отрезка b;
4) Отрезок a длиннее отрезка b на 2 см;
5) Васильев знает Петрова;
6) Иванов живет этажом выше Соколова;
7) Спортсмен Семенов бежит непосредственно за Николаевым.
7. Укажите отношения нестрогого порядка:
1) автомобиль a едет быстрее автомобиля b;
2) число a не меньше числа b, где a,b {1,2,…,50};
3) число a и b не равны числу 6, где a и b – натуральные числа;
4) число a без остатка делится на число b, где a,b {1,2,3,4,5,6};
5) a>5 и b>5, где a,b {1,2,…,8};
6) Петров и Иванов – друзья;
7) Угол a не больше угла β.