рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Основные понятия теории множеств

Основные понятия теории множеств - раздел Математика, 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. Графический.

Свойства бинарных отношений.

2. , . 3. = . 4. = .

Законы логики. Равносильные преобразования.

Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний

(А=В).

I-группа

Х / У = У / Х Х / У = У / Х 2. Ассоциативности: (сочетательный)

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)

Дизъюнктивные и конъюнктивные нормальные формы. Совершенные нормальные формы. Алгоритм построения.

X1 / X2(отриц.)/ X3, X1 / X 3(отриц.) , X 1 / X 2 / X3 Аналогично конъюнктивным одночленом называется конъюнкция переменных или их… X1 / X2 ; X1 / X2 / X3

Минимизация булевых функций. Карты Карно.

Минимизация или упрощение Булевых функций можно осуществить несколькими способами:

1. Анализтический

2. Графический

Один из графических методов является метод Карт Карно.

Карта Карно – прямоугольная таблица разделенная на 2n клеток в каждой из которых двоичный n-мерный набор значений функции из таблицы истинности.

 

Многочлен Жегалкина. Алгоритм построения.

Многочленами Жегалкина назваются формулы над множеством функций FJ={ 0, 1, *, +} Таким образом, каждый многочлен Жегалкина (возможно, после раскрытия скобок и… Для любой булевой функции существует задающий ее многочлен Жегалкина. Он единственен с точностью до перестановок…

Важнейшие замкнутые классы.

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 – значения переменных.

Полнота множества функций. Теорема Поста.

Теорема Поста Все остальные логические функции можно составить из набора логических функций,…  

Предикаты. Применение предикатов.

Предика́т (n-местный, или n-арный) — это функция с множеством значений (или «ложь» и «истина»), определённая на множестве . Таким образом,… Предикат называют тождественно-истинным и пишут:

Операции над предикатами. Квантовые операции.

Предикаты, так же, как высказывания, принимают два значения истинное и ложное, поэтому к ним применимы все операции логики высказываний. Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов.

Логические операции


Конъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «истина» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях. Множеством истинности Т предиката А(х) В(х), х Х является пересечение множеств истинности предикатов А(х) – Т1 и В(х) – Т2, т.е. Т= Т1 ∩Т2. Например: А(х): «х – четное число», В(х): « х кратно 3». А(х) В(х) – «х – четное число и х кратно 3». Т.е. предикат «х делится на 6».


Дизъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях х Т, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката А(х) В(х) является объединение областей истинности предикатов А(х) В(х).


Отрицанием предиката А(х) называется новый предикат , который принимает значение «истина» при всех значениях х Т, при которых предикат А(х) принимает значение «ложь», и принимает значение «ложь», если А(х) принимает значение «истина». Множеством истинности предиката , х Х является дополнение Т' к множеству Т в множестве Х.


Импликацией предикатов А(х) и В(х) называется новый предикат А(х) В(х), который является ложным при тех и только тех значениях х Т, при которых А(х) принимает значение «истина», а В(х) – значение «ложь» и принимает значение «истина» во всех остальных случаях. Читают: «Если А(х), то В(х)». Например. А(х): «Натуральное число х делится на 3». В(х): «Натуральное число х делится на 4», можно составить предикат: «Если натуральное число х делится на 3, то оно делится и на 4». Множеством истинности предиката А(х) В(х) является объединение множества Т2 – истинности предиката В(х) и дополнения к множеству Т1 истинности предиката А(х).

Кванторные операции

Квантор (все-)общности

Квантор существования

Квантор существования по переменной 1

Формулы логики предикатов. Равносильные формулы, приведенные и нормальные формы.

1. атом есть формула; 2. если A и B - формулы, то ~A, AÙB, AÚB, A® B, A«B - тоже… 3. если A(x) - есть формула, а x - свободная переменная в A(x) , то ("x)A(x) и ($x)A(x) - тоже формулы;

Формальные системы. Умозаключения и их виды.

Формальная система — это совокупность абстрактных объектов, не связанных с внешним миром, в котором представлены правила оперирования множеством…  

Метод математической индукции.

Вычислимые функции и алгоритмы. Теория рекурсивных функций.

Нормальные алгоритмы. Основные понятия.

Нормальный алгоритм Маркова. Понятие машины Тьюринга.

 

– Конец работы –

Используемые теги: основные, понятия, Теории, множеств0.073

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Основные понятия теории множеств

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

РАЗДЕЛ I. ОБЩИЕ ОСНОВЫ ТЕОРИИ И МЕТОДИКИ ФИЗИЧЕСКОЙ КУЛЬТУРЫ ВВЕДЕНИЕ В ТЕОРИЮ И МЕТОДИКУ ФИЗИЧЕСКОЙ КУЛЬТУРЫ Основные понятия теории и методики физической культуры
РАЗДЕЛ I ОБЩИЕ ОСНОВЫ ТЕОРИИ И МЕТОДИКИ... ФИЗИЧЕСКОЙ КУЛЬТУРЫ... ВВЕДЕНИЕ В ТЕОРИЮ И МЕТОДИКУ ФИЗИЧЕСКОЙ КУЛЬТУРЫ...

Основные понятия теории вероятностей. Случайное событие. Вероятность. Статистическая вероятность. Геометрическая вероятность. Основные формулы комбинаторики
Случайные события... Случайные события бывают х видов... Невозможные Обозначение V Достоверные Случайные...

Основные понятия в теории функциональных систем Анохина
Основные физиологические закономерности таких систем были сформулированы лабораторией Анохина ещ в 1935 году, т.е. задолго до того, как были… Под функциональной системой мы понимаем такое сочетание процессов и… Получается, что состав функциональной системы далее ФС и направление е деятельности определяются не органом, ни…

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ. ЭЛЕМЕНТЫ ЯЗЫКА. ЭЛЕМЕНТЫ ДАННЫХ. ВЫРАЖЕНИЯ. ОСНОВНЫЕ ИНСТРУКЦИИ. ПРОЦЕДУРЫ. ПРЕПРОЦЕССОР. СТИЛЬ ПРОГРАММИРОВАHИЯ
ВВЕДЕНИЕ... ОСНОВНЫЕ ПОНЯТИЯ И...

КОНСПЕКТ ЛЕКЦИЙ ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ВЕРОЯТНОСТЕЙ И СТАТИСТИКИ, ИСПОЛЬЗУЕМЫЕ В ЭКОНОМЕТРИКЕ
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ... ФИНАНСОВО ЭКОНОМИЧЕСКИЙ ИНСТИТУТ... Кафедра статистики и эконометрики...

Тема № 1. Предмет, задачи, основные категории и понятия теории статистики
Пример... При контрольной проверке качества хлебобулочных изделий проведено ное... На основе полученных в выборке данных нужно установить возможные значения доли стандартных изделий и среднего веса...

Основные понятия термодинамики. Предмет термодинамики. Основные параметры состояния термодинамической системы
На сайте allrefs.net читайте: Конспект лекций Дисциплина по учебному плану направления подготовки: 260901 Технология швейных изделий. Омск СОДЕРЖАНИЕ...

Основные понятия и категории экономической теории, их место в системе производственных отношений
В центре любого производственного процесса стоит труд. Само производство можно характеризовать как систему трудовых процессов, необходимых для… Конечно, процесс труда для физиолога будет характеризоваться как… Веществу природы он сам противостоит как сила природы. Для того, чтобы присвоить вещество природы в форме, пригодной…

Основные понятия Теории электрических цепей
Электрическая цепь Составные части элементы электрической цепи можно разделить на две... Понятие об источниках электрических Сигналов и... Основные параметры Характеризующие электрический сигнал...

ПРЕДМЕТ ТЕОРИИ ФИЗИЧЕСКОГО ВОСПИТАНИЯ И ЕГО ОСНОВНЫЕ ПОНЯТИЯ Спецификой предмета является изучение закономерностей физического воспитания и управление развитием ребенка от рождения до семи лет
ПРЕДМЕТ ТЕОРИИ ФИЗИЧЕСКОГО ВОСПИТАНИЯ И ЕГО ОСНОВНЫЕ ПОНЯТИЯ... В системе дошкольного образования теория и методика физического воспитания как... Цель физического воспитания ребенка это подготовка к жизни труду защите Отечества...

0.041
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам