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

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

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

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

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

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

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

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