Операции над множествами. Понятия и определения отношений и функций. Характеристики графов, алгоритм Форда–Беллмана нахождения минимального пути. Минимальные остовные деревья нагруженных графов. Формулы логики булевых функций, преобразования формул.
.2 Матричные способы задания графов 3.5 Пути, контуры в ориентированном графе 3.8 Алгоритм Форда - Беллмана нахождения минимального пути Контрольные вопросы к теме 3 4.2 Формулы логики булевых функцийКантор определял множество так: "Множество есть многое, мыслимое как целое". Множество и его элементы обозначаются следующим образом: А = {a1, a2, a3} - множество, состоящее из трех элементов; Множество может состоять из элементов, которые сами являются множествами. Множество А = {1, 2} состоит из двух элементов 1, 2; но множество {А} состоит из одного элемента А. Пусть А = {2} - множество, состоящее из одного элемента, В = {{2}, {4}} - множество, состоящее из двух элементов, каждое из которых является одноэлементным множеством.Рассмотрим основные операции над множествами. Объединением множеств А и В называется множество AEB, все элементы которого являются элементами хотя бы одного из множеств А или В: AEB = {x c XI А или XIB}. Тогда AEB = {2, 4, 5, 6}. б) Пусть А - множество чисел, которые делятся на 2, а В - множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Пересечением множеств А и В называется множество ACB, все элементы которого являются элементами обоих множеств А и В: ACB = {x c XI А и XIB}. Относительным дополнением множества В до множества А называется множество А \ В, все элементы которого являются элементами множества А, но не являются элементами множества В: А \ В = {x c XI А и XIB}.Множества вместе с определенными на них операциями образуют алгебру множеств. Последовательность выполнения операций задается с помощью формулы алгебры множеств. Чтобы доказать некоторое тождество Докажем таким образом, например, свойство дистрибутивности для объединения (тождество 3а)): AE (BCC) = (AEB) C (AEC). Основные тождества алгебры множеств можно использовать для доказательства других тождеств.Сопоставим этот элемент элементу a I А. Значит, для всякого элемента a I А существует единственный элемент c I C и для всякого элемента c I C существует единственный элемент a I А. Мощностью конечного множества А (обозначается CAC) называется число элементов этого множества. 1.1) мы рассматривали множество всех подмножеств данного множества А, которое называется множеством-степенью и обозначается P(A). Множество P(A) состоит из 2n элементов.Множество, эквивалентное множеству натуральных чисел N = {1, 2, 3, …, n,…}, называется счетным. Можно сказать также, что множество счетно, если его элементы можно перенумеровать. Чтобы установить счетность некоторого множества, достаточно указать взаимно однозначное соответствие между элементами данного множества и множества натуральных чисел. Для примера 1.19 взаимно однозначное соответствие устанавливается по следующим правилам: для множества Чтобы доказать, что данное множество имеет мощность континуума, достаточно указать взаимно однозначное соответствие между данным множеством и множеством точек отрезка, интервала или всей прямой.Упорядоченной парой называется совокупность двух элементов x и y, расположенных в определенном порядке. A и B называется множество упорядоченных пар, таких, что первый элемент каждой пары принадлежит множеству Бинарным (или двуместным) отношением r называется множество упорядоченных пар. Бинарное отношение может быть задано перечислением упорядоченных пар или указанием общего свойства упорядоченных пар. 1. r = {, , } - отношение задано перечислением упорядоченных пар;Так как отношения являются множествами, то все операции над множествами справедливы для отношений. Рассмотрим на этом множестве следующие отношения: r1 -"? "; r2 -"= "; r3 -"". Определим еще две операции над отношениями. Отношение называется обратным к отношению r (обозначается r-1), если r-1 = {c I r}. Композицией двух отношений r и s называется отношение s r = {cсуществует такое y, что I r и Is}.Отношение r называется рефлексивным на множестве X, если для любого XI X выполняется xr x. Это отношение рефлексивно, т.к. каждое число равно самому себе. в) Пусть X - множество людей и r отношение "жить в одном городе". Отношение r называется отношением эквивалентности на множестве X, если оно рефлексивно, симметрично и транзитивно на множестве X. Отношение r называется отношением частичного порядка (или просто частичным порядком) на множестве X, если оно рефлексивно, антисимметрично и транзитивно на множестве X. Это определение не противоречит определению равенства функций как равенства множеств (ведь мы определили функцию как отношение, т. е. множество): множества f и g равны, тогда и только тогда, когда они состоят из одних и тех же элементов.Для данной формулы булевой функции а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований; б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”); Функция Функция Основные понятия теории множеств: множества, подмножества, пустое множество, универсальное множество, множество-степень. Способы задания множеств.
1.4 Алгебра множеств. Основные тождества алгебры множеств
1.5 Эквивалентность множеств
1.6 Счетные множества
1.7 Множества мощности континуума
Контрольные вопросы к теме 1
Тема 2 Отношения. Функции
2.1 Отношения. Основные понятия и определения
2.2 Операции над отношениями
2.3 Свойства отношений
2.4 Функции. Основные понятия и определения
Контрольные вопросы к теме 2
Тема 3. Графы
Список литературы
Краткие сведения о математиках
ТЕМА 1. МНОЖЕСТВА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 г. работал в России.
Размещено на .ru
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
