Конспект по дискретної математики

Дискретна математика.

Введение

Общество 21 В. — суспільство інформаційне. Центр тяжкості у вирішенні завдань перемістився від завдань обчислювальної математики до завдань на дискретних структурах. Математика потрібна не як засіб розрахунку, бо як метод мисленню засіб формування та організації… Таке володіння математикою багатою культури, розуміння важливості точних формулювань. У дисципліни мало методів, але є багато визначень і термінів. У основі дискретної математиці 4 розділу: 1. Мова дискретної математики; 2. Логічні функції і автомати; 3. Теорія алгоритмів; 4. Графи і дискретні екстремальні задачи.

Теория алгоритмів і формальних систем є в дисципліни. У справжні період від неї виникли відгалуження, наприклад, розробка алгоритмічних мов программирования.

Одной з найважливіших негараздів у дискретної математики є проблема складності вычислений.

Теория складності обчислень допомагає оцінити витрата часу й пам’яті при рішенні завдань на ЕОМ. Теорія складності дає можливість окреслити об'єктивно складні завдання (завдання перебору) і нерозв’язні задачи.

Мы займатимемося в рішенням завдань реальної розмірності з урахуванням обмеженості тимчасових і емкостных ресурсів ЭВМ.

Сила-силенна та проведення операції над ними Одно з основних понять математики — множество.

Определение: Безліччю називається сукупність, набір предметів, об'єктів чи элементов.

Множество позначають: M, N … m1, m2, mn — елементи множества.

Символіка A (M — приналежність елемента до безлічі; А (М — неналежність елемента до множеству.

Примеры числових множеств:

1,2,3,… безліч натуральних чисел N;

…,-2,-1,0,1,2,… — безліч цілих чисел Z.

[pic] безліч раціональних чисел а.

I — безліч ірраціональних чисел.

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

K — безліч комплексних чисел.

Множество, А називається підмножиною У, якщо всякий елемент, А є елементом У. А (У — А підмножина У (нестрогое включение) Множества Проте й У рівні, якщо їх елементи совпадают.

A = B.

Если, А (У й О (У той, А (У (суворе включение).

Множества бувають кінцеві і бесконечные.

|М| - потужність безлічі (число його элементов).

Конечное безліч має кінцеве кількість элементов.

Пустое безліч зовсім позбавлений елементів: M = (.

Пример: порожній множество:

1) безліч дійсних коренів рівняння x2+1=0 порожній: M = (. 2) безліч (, сума кутів якого (1800 порожній: M = (.

Если дано безліч Є. і безліч і ми розглядаємо усі його підмножини, то безліч Є називається униварсельным.

Пример: Якщо за Є взяти безліч книжок його підмножини: художні книжки, книжки з математиці, фізики, фізики …

Если універсальне безліч складається з n елементів, то число підмножин = 2n.

Если [pic], що складається з елементів E, котрі належать до А, називається дополненным.

Множество можна задать:

1) Списком елементів {a, b, c, d, e};

2) Інтервалом 1 ставлення антирефлексивное головна діагональ містить нули.

Ін. отношнний.

(рефлексивное.

< антирефлексивное.

2. Якщо з aRb слід bRa, ==> ставлення R симетричний. У матриці відносини елементи сум Cij=Cji. Якщо з aRb і bRa слід a=b ==> ставлення R — антисимметричное.

Ін. Якщо, а (b і b (a ==> a=b.

3. Якщо дано (a, b, c з aRb і aRc слід aRC ==> ставлення зване транзитивным.

4. Ставлення називається ставленням еквівалентності, коли вона рефлексивно, симетрично і транзитивно.

Ін. ставлення рівності E.

5. Ставлення називається ставленням несуворого порядку, коли вона рефлексивно, антисимметрично і транзитивно. Ставлення називається ставленням суворого порядку, коли вона антирефлексивно, антисимметрично і транзитивно.

Ін. а) ставлення (u (для чисел ставлення несуворого б) ставлення < u > для чисел ставлення строгого.

Лекція: Елементи загальної алгебры.

Р. Операції на множествах Множество М разом із заданої у ньому сукупністю операцій (= {(1,…, (m}, тобто. система, А = {М1;(1,…, (m} називається алгеброю. (- сигнатура.

Если M1(M і якщо значення ((M1), тобто. замкнуто ==> A1={М1;(1,…, (m} подалгебра A. Ін. 1. Алгебра (R;+;*) — називається полем дійсних чисел обидві операції бінарні і тому тип цієї алгебри (2;2).

2. B=(Б;(;() — булева алгебра. тип операцій (2;2;1) Р. Властивості бінарних алгебраїчних операцій запис a (b. 1. (a (b)(c=a ((b (c) — асоціативна операция.

Ін. +, x — складання і множення чисел асоціативно 2. a (b = b (a — коммутативная операция.

Ін. +, x — коммутат.

-; : — некоммут. множення мат A (B (B (A — некоммутативно. 3. a ((b© = (a (b) ((a© -дистрибутивность слева.

(a (b)© = (a© ((b© -дистрибутивность справа.

Ін. (ab)e=aebe — спорудження до рівня дистрибутивного відносини твори справа але з abc (abac.

Р. Гомоморфизм і изоморфизм Алгебры з різними членами мають різні будівлі. Алгебри з членами мають подібність. Нехай дано дві алгебри A=(K; (I) і B=(M; (I) — однакового типу. Нехай відображення Г: K (M за умови Г ((I)= (I (Г), (1) тобто. результат досягнуто не залежить від послідовності можливих операцій: Або спочатку вип. операції (I b Проте й потім відображенні Р, чи спочатку відображення Р, чи спочатку відображення Р і далі відображення (I в У. Тоді умова (1) називається Гомоморфизмом алгебри На алгебру У. Коли існує взаимооднозначный гомоморфизм її називають изоморфизмом. І тут існує зворотне відображення Г-1. Потужності ізоморфних алгебр равны.

Ін. Алгебри (QN; +) і (Q2; +) — відображення типу, і умова (1) запишеться як 2(а+b)=2а+2b. Ставлення ізоморфізму є ставленням еквівалентності на безлічі алгебр, тобто обчислення рефлексивне, симетричності і транзитивності. Ізоморфізм найважливіше поняття у математиці. Отримані співвідношення в алгебрі А автоматично … на ізоморфні алгебры.

———————————- А.

В.

A.

C.

B.

A.

B.

Объединение трьох множеств:

AUB AUB.

А В.

А В.

С.

В А.

А В.

A.

B.

A B.

а) взаимнооднозначное соответствеие (отображение) а) не взаимнооднозначное соответствеие (отображение) Мх.

My.

x=2 (y=2.

y=2 (x=2.4.

не взаимнооднозначное соответствие.

2 3 4.

y.

X.

-(/2.

(/2.

1-ый елемент 1-го множества.

1-ый елемент 2-го множества.

}.

С=.

101 010 001.