Лекция №2. Тема: свойства счетных множеств.

 

1. Всякое подмножество счетного множества: конечно или счетно.

2. Сумма конечного числа конечных (счетных) множеств есть конечное (счетное) множество.

3. Всякое бесконечное множество содержит хоть одно счетное подмножество.

 

Пусть существует множество M, имеется ряд подмножеств .

Булеан – это и есть множество всех подмножеств множества М.

 

Теория множеств строится на основе следующих аксиом:

 

1. Аксиома СУЩЕСТВОВАНИЯ: Существует по крайней мере одно множество.

2. Аксиома ОБЪЕМНОСТИ: Если два множества, составлены из одних и тех же элементов, то они равны (А = В).

3. Аксиома ОБЪЕДИНЕНИЯ: Для любых М,N существует R, элементами которого являются все элементы этих множеств, которые не содержат никаких других элементов.

4. Для любых M,N существует D, элементами которого являются те и только те элементы множества M, которые не являются элементами N.

Множества часто задают графически с помощью диаграмм Эйлера-Венна, где всякий рассматриваемый контур соответствует одному из рассматриваемых множеств и ограничивает (символически) его элементы.

 

Операции над множествами

 

1. Включение M N (m_i Є M m_i Є N)

Каждый элемент множества М, обязательно принадлежит и множеству N, но не обязательно наоборот.

 

- Диаграмма Эйлера-Венна

 

 

2. Объединение (cложение) M N

Объединение множества М и N, есть

новое множество R, включающее в себя R

все элементы обеих множеств.

M(1,2,3)

M N R (1,2,3,4,5)

M(3,4,5)

 

 

3. Произведение (пересечение): M N

M(1,2,1,3,4)

R(3,4)

N(3,4,5,6)

Таким образом, произведением двух множеств, является множество R, элементы которого принадлежат к М и к N одновременно.

 

4. Вычитание: M\N: R(1,2)

Разность множеств M и N это новое множество, К, элементы которого обладают свойствами М и не обладают свойствами N, т.е. принадлежат только множеству M.

 

 

5. Дополнение:

Пусть имеется некоторое универсальное множество U и все рассматриваемые в нем множества есть его подмножества, тогда элементами множества являются все элементы не входящие в М, но принадлежащие U, т.е. U без М есть множество .

 

 

Лекции №3. Тема: основные тождества алгебры множеств.

1.

2. Коммутативность

3.

4. Ассоциативность

5.

6. Дистрибутивность

7. Закон

7а. Де Моргана

 

8. Ø Ø

9. Ø

10.

11. Ø = Ø

 

12. Закон

13. поглощения

где Ø - пустое множество

 

Пример:

M (1, 9, 12, 17, 33, 4, 16)

N (33, 22, 45, 9, 1, 20, 35)

1. вычитание: R = (12, 17, 4, 16);

2. сложение: R = (1, 9, 12, 17, 33, 4, 16, 22, 45, 20, 35);

3. произведение: R = (1, 9, 33)

 

 

Лекция №4. Тема: кортежи.

Происхождение от французского «торжественность».

 

Пусть М – конечное множество, элементами которого являются символы. Например: цифры, буквы.

Кортеж – есть упорядоченный набор (строгая последовательность) элементов множества M.

Алфавит - есть кортеж попарно различных символов, называемых буквами алфавита.

 

Рассмотрим множество состоящее из n элементов:0,1,2,…,n.

Кортежи длины m из этих элементов, обозначим M^m, тогда мощность n(M^m), есть n^m. Такие кортежи, которые называются упорядоченными наборами или векторами.

Пример: M (1,2,3,4), M (4,3,2,1) M (1,3,2,4); M ≠ M ≠ M ; т.е.если порядок расположения элементов разный, то кортежи не равны друг другу (разные).

 

Декартовое произведение множеств: Пусть заданы множества M₁,M₂,…. M_n.

Декартовым произведением этих множеств называется множество состоящие из всех кортежей (m₁, m₂….m_n) длины k₁(m_k Є M_k, 1 ≤ k ≤ n), где m₁Є M₁, m₂ Є M₂, … m_n Є M_n. Обозначается как M₁*M₂*…M_n. Произведение –

M * M *… * M – nраз, обозначается как Mⁿ и называется n – ой степенью M.

Порядок задания множителей для декартового произведения, как для кортежей одинаков.

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

 

Пример:

M₁ = {0, 1, 2}, M₂ = {x, y, z}, M₃ = {A, Б, С}

Декартовое произведение:

M₁ * M₂ * M₃ K₁ = {(0, 1), (x, y), (A, Б)}, или К₂ = {(1, 2), (x, z), (A, C)}.

 

Отображения множеств (функций)

Отображение f множества x во множество y – это когда каждому элементу x Є X, ставится в соответствие только один элемент y Є Y.

Элемент y множества Y, соответствующий при отображении f элементу x из X называется образом элемента x. Если y = f(x), то x называется прообразом элемента y при этом отображении.

Частный случай отображения множества X в Y имеет место, если каждый элемент множества Y имеет прообраз из множества X. В этом случае отображение (f) сюръективно, (может быть случай, когда несколько элементов Y имеют один и тот же прообраз в X).

Отображение f, называется инъективным, если для каждого элемента

y Є Y существует не более 1- го прообраза, если отображение f сюръективно и инъективно, то оно называется биективным.

Пример: функций, отображающих x Є R на множество y Є R на множество

y Є R, где R – множество (бесконечное) действительных чисел.

 

1. f₁(x) = E^x – инъективно (не сюръективно)

2. f₂(x) = x*(x²-1) – сюръективно (не инъективно)

3. f₃(x) = 3x+1 – биективно

 

Лекция №5. Тема: алгебра логики (булева алгебра).

 

В основе логико – математической теории дискретной математики лежит понятие: высказывание. Это повествовательное предложение, которое интересует математика прежде всего в узком смысле: истинно оно или ложно.

 

В алгебре логики основными связками (операциями) являются следующие:

o дизъюнкция (или)

o конъюнкция (и)

o отрицание (не)

o импликация (если…, то…) →

o эквиваленция (тогда и только тогда, когда…) ↔

o штрих Шеффера (антиконъюнкция) |

o стрелка Пирса (антидизъюнкция) ↓

 

При выполнении операций существует следующий порядок:

- операции в скобках, если их нет тот операции выполняются так:

I. отрицание

II. конъюнкция

III. дизъюнкция

IV. импликация

V. эквиваленция

VI. штрих Шеффера

VII. стрелка Пирса

Конъюнкцией двух высказываний X, Y называется высказывание (функция) x y, которая истина только в том случае, когда X и Y - оба истинны.

 

x	y	X&Y

 

Дизъюнкция X и Y называется высказывание (функция) X Y, которое истинно когда хотя бы одно из X и Y истинно.

 

X	Y	X Y

 

 

Импликацией X и Y называется высказывание (функция) X→Y, которая ложна тогда, и только тогда, когда X истинно, а Y ложно, и истинна в остальных вариантах.

 

Таблица истинности для импликации

X	Y	X→Y

 

 

Эквиваленцией X иY называется высказывание X↔Y, которое истинно тогда, и только тогда, когда X и Y оба истинны или ложны, одновременно.

 

Таблица истинности для эквиваленции

 

X	Y	X↔Y

 

Штрих Шеффера (антиконъюнкция) - X│Y = X∩Y

X	Y	X│Y

 

 

____

Стрелка Пирса (антиконъюнкция) - X↓Y = XUY

 

X	Y	X↓Y

 

____

Сложение по модулю два (антиэквиваленция) - X Y = X↔Y

X	Y	X Y