Українські рефератиучбові матеріали на українській мові

RefBaza.com.ua пропонує студентам та абітурієнтам найбільшу базу з рефератів! Також ви можете ділитися своїми рефератами для поповнення бази.

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

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

Лекція 1

Безліч. Алгебра множин.

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

R – безліч дійсних чисел.

X e R – елемент X належить безлічі R.

Рівні безлічі – безлічі, які з однакових елементів.

A = B – безліч А одно безлічі B.

0 – порожній безліч.

A<= З – Безліч А є підмножиною безлічі З.

Якщо А одно З повагою та А <= З, то А < З. (суворо).

Якщо A <= З і З <= Бо А = З.

Байдуже безліч 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 З = A U (B U З), A n (B n З) = (A n B) n З – асоціативність.

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

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