Шпаргалка по предмету "Дискретная математика"

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

Множеством наз-ся совокупность объектов обладающих каким-то общим признаком. Объекты которые входят в состав мн-ва – элементы. Всякое мн-во определяется своими элем-ми. Мн-во обзначается А,В,С. Элем-ты мн-ва обозначаются а,в,с; иногда с индаксами. При записи мн-ва элем-ты записываются в фигурных скобках N={1,2,3…}-мн-во нат.чисел. Z={0,±1,±2…}-мн-во целых чисел. Q={n/m, где n€N, m€Z}-рац.числа. Мн-ва бывают конечные и бесконечные. Мн-во наз-ся конечным если оно состоит из конечного числа элем-в. Число элем-в в конечном мн-ве наз-ся его мощностью |  |.

Способы задания мн-в:

1)перечиление-задаются только конечные  мн-ва

2)порождающей процедурой-т.е. описанием  способа получения элем-в мн-ва  из уже полученных элем-в или  из других объектов.

M={1,2,4,8…} 1€M, если m€M, то 2m€M.

3)описанием характеристики св-в  которыми должны обладать элем-ты  мн-ва: под св-вом объекта понимается  такое повест.предлож. в котором нечто утверждается отн-но этого объекта и которое можно охарак-ть как истинное или ложное по отношению к объекту.

Мн-во А наз-ся подмн-ом мн-ва В если всякий элем-т А явл-ся элем-ом В. Св-ва:

1. А   А

2. А   В, В   С →А   С

3. Ǿ    А

Мн-ва АиВ наз-ся равными если они состоят из одних и тех же элем-в. А   В, В   А

А   В и А≠В, то мн-во А наз-ся собсвенным подмн-вом мн-ва В (А   В)

Мн-во всех подмн-в данного мн-ва наз-ся его булеаном β(А) | β(А) | =2  n=| А |

 

2.Операции над мн-вами. Св-ва операций.

В алгебре мн-в в качестве 0 рассматр. пустое мн-во. Роль 1 в алгебре мн-в играет универсальное мн-во U. Это мн-во содержащее любые рассматр-мые мн-ва полностью.

1. Объединение- обеъдинением мн-в  А и В наз-ют мн-во состоящее  из всех тех и только тех  элем-в которые принадлежат хотя  бы одному из мн-в. А   В={x| x€A или x€B}

 

 

 

2. Пересечение- пересечением мн-в А и В наз-ют мн-во состоящее из всех те и только тех элем-в которые принадлежат каждому из А и В. А   В – те элем-ты которые € и А и В.

 

 

 

3. Разность- разностью мн-в А  и В наз-ют мн-во всех тех  и только тех элем-в А которые  не содержатся в В.

А/B = {х| х€А, х¢В}

Св-ва: А/В≠В/А  Если А/В=Ǿ, то А   В

 

 

 

4. Допонение- дополнением мн-ва  А относ-но В, А   В, наз-ся  мн-во элем-в не принадлежащих  А, но принадлежащих В.

А={x| x   B, x¢A, x€B}

 

 

 

Св-ва оперций:

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

А/В = В   А

А   В = В   А

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

(А   В)   С = А   (В   С)

(А   В)   С = А   (В   С)

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

А   (В   С) = (А   В)   (А   С)

А   (В   С) = (А   В)   (А   С)

4. Законы поглощения

А   (А   В) = А

А   (А   В) =А

5. Закон иденпатентности

А  А=А

А   А=А

6. Законы де моргана 

А   В=А   В

А   В=А   В

7. Дополнение 

А=А

8. Законы 0и1

А      =А

A   U=U

A      =

A   U=A

A   A=U

A   A=

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Кортежи. Декартево произведение  мн-в. Отношения: определение,способы  задания.

Упорядоченным мн-ом или кортежем наз-ся послед-ть элем-ов в которой каждый элем-т занимает опред-ое место. Объекты образующие кортеж наз-ся его компонентами или координатами. Число компонентов кортежа наз-ся его длиной.

Два корежа х=(х1,…,хn) и у=(у1,…,уn) наз-ся равными (х=у) если они имеют одинаковую длину и соответствующие координаты их равны.

Декартовым (прямым) произведением двух мн-в А и В наз-ся мн-во всех упорядченных пар А, В таких что а€А, в€В, А×В={ (a,b) | a€A, b€B} Если А и В конечные мн-ва |А|=m, |B|=n, то |А×В|=n*m Если А и В равные мн-ва, то А×В=А×А=А  - декартов квадрат мн-ва А  Если |А|=m, то |A |=m

Декартовым произведением мн-в А1, А2,…,Аn наз-ся мн-во кортежей (а1,а2,…,аn) длины n таких что а1€А1, аn€Аn. А1×А2×…×Аn={(а1,а2,…,аn) | а1€А1…аn€Аn}. Если А1=А2=…=Аn=А.

А1×А2×…×Аn=А  - n-ная декартовая степень мн-ва А

n-местным отношением R на мн-ах А1,А2,…,Аn наз-ся любое подмн-во декартового произведения этих мн-в. R   А1×А2×…Аn. Если А1=А2=…=Аn, то R   А .

R   А×В, то для задания отнош-ия исп-ся способы задания мн-в. Отношения определенные на конечных мн-ах можно задать списком, т.е перечислением пар для которых отношение вып-ся

Особого внимания требует задание отнош-ия с помощью матрицы. Матрицей бинарного отнош-ия R наз-ся матрица [R]=(r    )     размера m×n, элем-ты (i=1m, j=1n)

 

 

 

Любую матрицу из 0 и 1 можно рассмотреть как матрицу бинарного отношения.

 

 

 

4.Бинарные отношения. Операции  над бинарными отношениями.

При n=2, R   A×B – бинарное отношение.

Бинарное отношение используется для определения каких либо взаимосвязей, которыми харак-ся пара элем-ов рассматр. мн-в.

Если (а,в)€R, то записывают aRb (а и в связаны отношением R)

Операции над бинарными отношеиями:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Св-ва бинарных отношений.

Пусть R    А×А

1) R наз-ся рефлексивным, если для    a€A, вып. aRa

2) R наз-ся антирефлексивным если     a€A не вып  aRa

3) R наз-ся семетричным если    a,b€A из aRb→bRa

4) R наз-ся антисеметричным если из aRb и bRa→a=b

5) R наз-ся транзитивным если

Бинарное отношение заданное на мн-ве А наз-ся отношением эквивалентности если оно рефлексивно, семетрично, транзитивно.

 

6. Неориентированный граф  и его основные характеристики.

Пусть V – некоторое не пустое мн-во

V={v1,v2,…,vn}  |V|=n

V  - мн-во неупорядоченных 2-х элемен-ых подмн-в мн-ва V

Неориентированным графом G (неорграфом) наз-ся совокупность мн-в (V,E), где E – подмн-во мн-ва  V   .

Элем-ты мн-ва  V наз-ся вершинами графа. Элем-ты мн-ва E – ребрами. Ребра бознач {v ,v } где v  и v  различные вершины из мн-ва V.

G наз-ся мультиграфом если мн-во ребер Е содержит несколько ребер вида V  ,V  , где V ≠V  V  €E, V  €V, такие ребра наз-ся кратными.

Мультиграф имеющий ребра вида {v  ,v  } наз-ся псевдографом. {v  ,v  }наз-ся петлями.

Мультиграф G наз-ся конечным если конечны мн-ва его вершин V и ребер E.

G наз-ся конечным если его мн-во вершин V конечно.

Конечный граф с n вершинами наз-ся графом n-ого порядка.

На мн-ве вершин графа можно ввести отношение смежности.

Пусть G=(V,E), |V|=n – конечный неорграф

Две вершины v  и v  (v  €V, v  €V, i=j) наз-ся смежными если они соединены ребром т.е  {v  ,v  }€E. Вершины образующие ребро {v  ,v  }€E наз-ся концами ребра. Два ребра наз-ся смежными если они имеют общий конец.

Лемма о рукопожатии:

Сумма степеней всех вершин графа равна удвоенному числу его ребер.

 

 

 

7. Ориентированный граф  и его основные характеристики.

Пусть V – не пустное мн-во, |V|=n. Рассмотрим декартов квадрат V =V×V мн-во все упорядоченных пар мн-ва V.

Граф G наз-ся ориентировнным графом если E   V . Элем-ты мн-ва Е наз-ся дугами обозначаются

На рис. дуги обозначаются стрелочками.

 

 

Вершина v  наз-ся началом дуги (v  ,v  ), а v  - концом. Дуга (v  ,v  ) наз-ся исходящей из вершины v  и заходящей на вершину v .

Полустепенью исхода вершины v     наз-ся число дуг исходящих из вершины v . Число дуг заходящих в вершину полустепень захода

Лемма о рукопожатии: сумма полустепеней исхода=сумме полустепеней захода и=числу дуг графа.

 

 

8.Способы представления  графов. Изоморфизм графов.

Занумеруем вершин орграфа(графа) и дуги(ребра) натуральными числами начиная с 1.

Таким образом орграф(граф) может быть представлен в виде матрицы размера n×m (n-число вершин, m-число дуг(ребер))

1. представление орграфа(графа) с  помощью матрицы инцидентности.

Матрицей инцидентности орграфа(графа) G наз-ся матрица A=(a   ) размера n×m (i=1,n, j=1,m) определяемая по следующему правилу

 

 

 

 

 

2.Представление орграфа(графа) с  помощью матрицы смежности.

Матрицей сменности вершин орграфа( графа) наз-ся квадратная матрица В=(b  ) порядка n (n-число вершин графа) элементы которой определяются по следующему правилу

 

 

 

 

 

9. Предмет комбинаторики. Основные правила комбинаторики.

Комбинаторика-раздел математики посвещенный решению задач выбора.

Два основных правила комбинаторики: правило умножения и правило сложения.

Правило умножения: если из некоторого конечного мн-ва первый объект (а) можно выбрать n1 способами, а второй объект (b) – n2 способами, то оба объекта (a и b) в указанном порядке можно выбрать n1*n2 способами.

Правило сложения: если некоторый объект а можно выбрать n1 способами, а объект b можно выбрать (независимо от выбора объекта а) n2 способами, то любой из объектов (а или b) можно выбрать n1+n2 способами.

Это правило распространяется на любое конечное число объектов.

Сущ-ет две схемы выбора m элем-ов из заданного мн-ва: без возвращения, когда выбранные элем-ты не возвращаются в исходное мн-во, и с возвращением, когда выбор осуществляется полементно с обязательным возвращением отобранного элем-та на каждом шаге.

 

10. Основные комбинаторные конфигурации: размещения, перестановки, сочетания без повторения.

Размещением из n элем-ов по k (0  k  n) наз-ся любое упорядоченное подмн-во данного мн-ва содержащее k различных элем-ов.

 

 

 

Перестановкой из n элем-ов наз-ся размещение в котором участвуют все n элем-ов мн-ва. Любые 2 перестановки отличаются друг от друга только порядком следования элем-ов.

 

 

 

 

Сочетанием из n элем-ов по k (0  k  n) наз-ся любое подмн-во данного мн-ва содержащее k различных элем-ов. Любые два сочетания отличаются друг от друга тольо составом элем-ов.

 

 

 

11. Свойства биномиальных  коэффициентов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12. Основные комбинаторные  конфигурации: размещения, сочетания, перестановки с повторениями.

Размещением из n элем-ов по k с повторением (0  k  n) наз-ся любое упорядоченное подмн-во данного мн-ва, содержащее k элем-ов.

 

 

 

 

Сочетанием из n элем-ов по k с повторением (0  k  n) наз-ся любое подмн-во данного мн-ва содержащее k элем-ов.

 

 

 

 

 

Перестановкой с повторением из n элем-ов назся перестановка, в которой участвуют n1 элем-ов 1-го типа, n2 элем-ов 2-го типа,…, nk элем-в k-го типа, где n1+n2+…+nk=n.

 

 

 

 

13. Высказывания. Операции  над высказываниями.

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

 

 

 

Операции над высказываниями:

1. отрицанием наз-ся высказвание  истинное тогда и только тогда  когда Р- ложь.

2. конъюнкцией наз-ся высказывание истинное тогда и только тогда когда оба высказывания истины

3. дезъюнкцией наз-ся высказывание  ложное тогда и только тогда  когда оба высказывания ложны.

4. импликацией наз-ся высказывание  ложное тогда и тольо тогда  когда Р-истина, а Q-ложь

Р-посылка импликции, Q-следствие

5. эквивалентностью наз-ся высказывание  истинное тогда и только тогда  когда Р и Q принимают одинаковые истинностные значения.

6. неравнозначность(исключающие или) наз-ся высказывание истинное  тогда и только тогда когда  истинностные значения высказываний  Р и Q не совпадают.

 

 

14. Формулы алгебры логики. Эквивалентность формул.

Пропорциональной переменной наз-ся всякая переменная вместо которой можно подставить конкретные высказ. Обознач х1, х2, y, z

Формулой алгебры логики наз-ся выражение которое строится из пропорциональных переменных по следующим правилам:

1)всякая пропозиционная переменная  – формула

2) если    и  - формулы, то

3) других формул нет

Подформулой формулы наз-ся всякая часть формулы, являющаяся формулой

Порядок действий обычно определяется скобками. Если скобок нет, то операции выполняются в следующем порядке

 

 

 

 

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

   (х1…х2) наз-ся выполнимой  если сущ-ет набор высказываний А1…Аn который обращает эту ф-лу в истинное (ложное) высказывание

   (х1…х2) наз-ся товтологией  ели она обрщается в истинное  высказывание на всех наборах  значений переменных.

   (х1…х2) наз-ся противоречием  если она обращается в ложное  высказывание на всех наборах  значений переменных.

 

 

14. Формулы алгебры логики. Эквивалентность формул.

Пропорциональной переменной наз-ся всякая переменная вместо которой можно подставить конкретные высказ. Обознач х1, х2, y, z

Формулой алгебры логики наз-ся выражение которое строится из пропорциональных переменных по следующим правилам:

1)всякая пропозиционная переменная  – формула

2) если    и   - формулы, то

3) других формул нет

Подформулой формулы наз-ся всякая часть формулы, являющаяся формулой

Порядок действий обычно определяется скобками. Если скобок нет, то операции выполняются в следующем порядке

 

 

 

 

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