В нашей онлайн базе уже более 10821 рефератов!

Список разделов
Самое популярное
Новое
Поиск
Заказать реферат
Добавить реферат
В избранное
Контакты
Украинские рефераты
Статьи
От партнёров
Новости
Крупнейшая коллекция рефератов
Предлагаем вам крупнейшую коллекцию из 10821 рефератов!

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

Дискретная математика (Конспекты 15 лекций)

Дискретная математика (Конспекты 15 лекций)

Лекция 1

Множество. Алгебра множеств.

Введем обозначения.

R – множество действительных чисел.

X e R – элемент X принадлежит множеству R.

Равные множества – множества, состоящие из одинаковых элементов.

A = B – множество А равно множеству B.

0 – пустое множество.

A<= C – Множество А является подмножеством множества С.

Если А не равно С и А <= C, то А < С. (строго).

Если A <= C и C <= А, то А = С.

Пустое множество 0 является подмножеством любого множества.

Существуют конечные и бесконечные множества. Пусть n – число элементов данного множества А. Это число называется мощностью данного множества.

У множества рациональных чисел мощность является счетной (т.е. все элементы можно пронумеровать).

У множества иррациональных чисел мощность – континиум. Обозначается (С).

Основное правило комбинаторики (показано на примере)

Пусть имеется палочка, разделенная на 3 части. Первую ее часть можно раскрасить n способами, вторую – m, третью – k. Всего способов раскраски палочки – n*m*k.

Аналогично с множествами

U = {a1,a2… an-1, an}

Пусть U = {a1, a2, a3}

Выпишем множество всех подмножеств множества U.

P(U) = {0, a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3}.

Мощность множества U равна 3, а мощность P(U) равна 8.

Методом математической индукции доказывается, что при произвольной мощности n множества U, мощность множества P(U) равна 2n.

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

1. Объединение множеств (A U B). Элемент, принадлежащий полученному множеству, принадлежит множеству А ИЛИ множеству В.

2. Пересечение множеств (A n B). Элемент, принадлежащий полученному множеству, принадлежит множеству А И множеству В.

3. Дополнение множества А. (С = А ) – не А. Все элементы, принадлежащие универсальному множеству, не принадлежат множеству А.

Свойства операций над множествами.

1. A U B = B U A – коммутативность

. A n B = B n A

2. (A U B) U C = A U (B U C), A n (B n C) = (A n B) n C – ассоциативность.

3. (A U B) n C = (A n C) u (B n C), (AnB) U C = (A U C) n (B U C) – дистрибутивность.

4. Поглощение A U A = A, A n A = A.

5. Существование универсальных границ.

А U 0 = A

A n 0 = 0

A u U = U

A n U = A

6. Двойное дополнение

A = A

7. A U A = U

A n A = 0

8. Законы двойственности или закон Де – Моргана

(AUB) = A n B

(AnB) = A U B

Объединение множеств

Дополнение множества

Лекция 2

Теория булевых функций. Булева алгебра.

Определение.

Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры). Названия операций пока не введены.

1. X & Y = Y&X, X V Y = Y V X – коммутативность.

2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

4. Поглощение – X & X = X, X V X = X.

5. Свойства констант

X & 0 = 0

X & I = X, где I – аналог универсального множества.

6. Инвальтивность (X*)* = X

7. Дополнимость X V X* = I, X & X* = 0.

8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.

U = {a1, a2… an)

[U] = N

[P(U)] = 2n

Легко показать, что свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.

Oбъединение эквивалентно V, пересечение - &, дополнение - *, пустое множество – 0, а универсальное – I.

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

Булева алгебра характеристических векторов.

Пусть A <= U, A <- P(U) a- характеристический вектор этого подмножества.

aA = {a, a2 an)

n = [P(U)]

ai = 1, если ai <- A (принадлежит).

ai = 0, если ai не принадлежит A.

U = {1 2 3 4 5 6 7 8 9}

A = {2 4 6 8}

B = {1 2 7}

aA = {0 1 0 1 0 1 0 1 0}

aB = {1 1 0 0 0 0 1 0 0}

или

aA = 010101010 – скобки не нужны

aA= 110000100

Характеристические векторы размерностью n называются булевыми векторами.

Они располагаются в вершинах n – мерного булева куба.

Номером булевого вектора является число в двоичном представлении, которым он является

1101 – номер.

Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (если они отличаются только одной координатой).

Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.

0 1

Булев куб размерности 1

Булев куб размерности 2

Булев куб размерности 3

Подпись: 001 Подпись: 011

0 – нулевой вектор.

Логическое умножение

[1] 2 3 4 5 6 7 8 9 10

скачать реферат скачать реферат

Новинки
Интересные новости


Заказ реферата
Заказать реферат
Счетчики

Rambler's Top100

Ссылки
Все права защищены © 2005-2019 textreferat.com