Реферат Курсовая Конспект
Основные понятия теории множеств - раздел Математика, 1.Основные Понятия Теории Множеств. Способы Задания Множеств....
|
1.Основные понятия теории множеств. Способы задания множеств.
Под множеством будем понимать совокупность определённых вполне различаемых объектов, рассматриваемых как единое целое, это понятие – фундаментально. Для обозначения конкретных множеств используются заглавные буквы с индексом или без (A, X1, Х2), элементы множеств обозначаются строчными буквами (а, х1, х2). Принадлежность элемента множеству обозначается символом ∈. Множества бывают конечными и бесконечными. Конечные множества – множества, в которых число элементов конечно. Бесконечные множества – бесконечное число элементов.
Множества задаются двумя способами: перечислением и описанием. Задание перечислением – перечисление всех элементов, составляющих множество. Он удобен для задания конечных множеств с небольшим количеством элементов и для задания множеств типа {2, 4, 6, 8…}.
Описательный способ задания множества состоит в том, что указывается характерное свойство, которым обладают все элементы множества.
Элементы множества – отдельные объекты, из которых состоит множество. Считают, что множество задано своими элементами, т.е. множество задано, если о любом объекте можно сказать: принадлежит он этому множеству или не принадлежит. Задавать множество можно следующими способами:
1) Если множество конечно, то его можно задать перечислением всех его элементов. Так, если множество А состоит из элементов 2, 5, 7, 12, то пишут А = {2, 5, 7, 12}. Количество элементов множества А равно 4, пишут n(А) = 4.
Но если множество бесконечно, то его элементы нельзя перечислить. Трудно задать множество перечислением и конечное множество с большим числом элементов. В таких случаях применяют другой способ задания множества.
Характеристическое свойство – это такое свойство, которым обладает каждый элемент, принадлежащий множеству, и не обладает ни один элемент, не принадлежащий ему.
2.Операции над множествами и их свойства.
Объединением (суммой) множеств А и В называется множество А ∪ В, элементы которого принадлежат хотя бы одному из этих множеств.
Пересечением (произведением) множеств А и В называется множество А ∩ В, элементы которого принадлежат как множеству А, так и множеству В.
Разностью множеств А и В называется множество АВ, элементы которого принадлежат множесву А, но не принадлежат множеству В.
Симметричной разностью множеств А и В называется множество А Δ В, являющееся объединением разностей множеств АВ и ВА, то есть А Δ В = (АВ) ∪ (ВА).
Свойства перестановочности
A ∪ B = B ∪ A
A ∩ B = B ∩ A
Сочетательное свойство
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)
3.Декартово произведение множеств. Бинарные отношения, способы задания, свойства.
Одним из способов конструирования новых объектов из уже имеющихся множеств является декартово произведение множеств. Пусть и - множества. Выражение вида , где и , называется упорядоченной парой. Равенство вида означает, что и . В общем случае, можно рассматривать упорядоченную n-ку из элементов . Упорядоченные n-ки иначе называют наборы или кортежи. Если множество умножается само на себя, то говорят о декартовой степени множеств А х А = А2.
В математике большую роль играют бинарные отношения, т.е. отношения, заданные на декартовом произведении двух множеств .
Способы задания бинарных отношений.
1. Перечисление.
2. Указание характеристического свойства.
3. Стрелочные диаграммы.
4. Графический.
Законы логики. Равносильные преобразования.
Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний
(А=В).
II-группа
7.Закон идентичности:
X / X = X
X / X = X
8.Закон инверсии:
X / X(х отриц.) = 1
X / X(х отриц) = 0
9.Операции с константами:
X / 0 = X
X / 0 = 1
X / 1 = X
X / 0 = 0
III- группа
10.Снятие двойного отрицания
X(две палочки над х) = X
11.Снятие импликации:
Х Y = (X(х отриц.) / Y) / (X / Y(у отриц))
12.Снятие эквиваленции:
X Y= (X(х отриц.) / Y) / (X / Y(у отриц.))
Понятие булевой функции.
Функию f(x/1,x/2,…x/n) от n переменных принимающую значения 0 или 1 при чем каждая переменная так же принимает значения 0 или 1 называют булевой функцией от n переменных. Если n=1, тогда функция зависит от одной переменной и таких функций.
Если n=2, то булевых функций 16
Если n=3, то 256ю
Общее кол-во функций рассчитывается по формуле:
2(2n)
Минимизация булевых функций. Карты Карно.
Минимизация или упрощение Булевых функций можно осуществить несколькими способами:
1. Анализтический
2. Графический
Один из графических методов является метод Карт Карно.
Карта Карно – прямоугольная таблица разделенная на 2n клеток в каждой из которых двоичный n-мерный набор значений функции из таблицы истинности.
Важнейшие замкнутые классы.
I. T0 – класс булевых функций сохр константу 0
F(0,0,…0) = 0
II. T1 – класс функций сохр константу 1
F(1,1,…1)=1
III. L – класс линейных функций
Булева функция является линейной если ее многочлен жигалкина линейный. Многочлен жигалкина называется линейным если он не содержит конъюнкций:
a0 + a1 x1 + … + an xn
IV. S – класс самодейственных функций. Функция самодейственная, если она совпадает с своей двойственной функцией:
F((x1, x2 ,x3 …xn) = f(x1 ,x2 ,…xn(все под отриц) ) отриц
V. M – функция называется монотонной если у всех условий а1 < b1… an < bn следует f(a1,…an) < f(b1,..bn)
Где аi bi – значения переменных.
Операции над предикатами. Квантовые операции.
Предикаты, так же, как высказывания, принимают два значения истинное и ложное, поэтому к ним применимы все операции логики высказываний. Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.
Логические операции
Конъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «истина» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката А(х) В(х), х Х является пересечение множеств истинности предикатов А(х) – Т1 и В(х) – Т2, т.е. Т= Т1 ∩Т2. Например: А(х): «х – четное число», В(х): « х кратно 3». А(х) В(х) – «х – четное число и х кратно 3». Т.е. предикат «х делится на 6».
Дизъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката А(х) В(х) является объединение областей истинности предикатов А(х) В(х).
Отрицанием предиката А(х) называется новый предикат , который принимает значение «истина» при всех значениях х Т, при которых предикат А(х) принимает значение «ложь», и принимает значение «ложь», если А(х) принимает значение «истина». Множеством истинности предиката , х Х является дополнение Т' к множеству Т в множестве Х.
Импликацией предикатов А(х) и В(х) называется новый предикат А(х) В(х), который является ложным при тех и только тех значениях х Т, при которых А(х) принимает значение «истина», а В(х) – значение «ложь» и принимает значение «истина» во всех остальных случаях. Читают: «Если А(х), то В(х)». Например. А(х): «Натуральное число х делится на 3». В(х): «Натуральное число х делится на 4», можно составить предикат: «Если натуральное число х делится на 3, то оно делится и на 4». Множеством истинности предиката А(х) В(х) является объединение множества Т2 – истинности предиката В(х) и дополнения к множеству Т1 истинности предиката А(х).
Кванторные операции
Квантор (все-)общности
Квантор существования
Квантор существования по переменной 1
Метод математической индукции.
Вычислимые функции и алгоритмы. Теория рекурсивных функций.
Нормальные алгоритмы. Основные понятия.
Нормальный алгоритм Маркова. Понятие машины Тьюринга.
– Конец работы –
Используемые теги: основные, понятия, Теории, множеств0.073
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Основные понятия теории множеств
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов