Автор работы: Пользователь скрыл имя, 09 Марта 2014 в 20:32, шпаргалка
Работа содержит ответы на вопросы для экзамена по предмету "Дискретная математика".
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. Объединение- обеъдинением мн-в
А и В наз-ют мн-во состоящее
из всех тех и только тех
элем-в которые принадлежат
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-следствие
5. эквивалентностью наз-ся
6. неравнозначность(исключающие
14. Формулы алгебры логики. Эквивалентность формул.
Пропорциональной переменной наз-ся всякая переменная вместо которой можно подставить конкретные высказ. Обознач х1, х2, y, z
Формулой алгебры логики наз-ся выражение которое строится из пропорциональных переменных по следующим правилам:
1)всякая пропозиционная
2) если и - формулы, то
3) других формул нет
Подформулой формулы наз-ся всякая часть формулы, являющаяся формулой
Порядок действий обычно определяется скобками. Если скобок нет, то операции выполняются в следующем порядке
Логическое значение ф-лы полностью пределяется логическими значениями переменных входящих в ф-лу и значениями логических операций, участвующими в потроение ф-лы. Для произвольных ф-л можно строить таблицы истинности.
(х1…х2) наз-ся выполнимой если сущ-ет набор высказываний А1…Аn который обращает эту ф-лу в истинное (ложное) высказывание
(х1…х2) наз-ся товтологией ели она обрщается в истинное высказывание на всех наборах значений переменных.
(х1…х2) наз-ся противоречием если она обращается в ложное высказывание на всех наборах значений переменных.
14. Формулы алгебры логики. Эквивалентность формул.
Пропорциональной переменной наз-ся всякая переменная вместо которой можно подставить конкретные высказ. Обознач х1, х2, y, z
Формулой алгебры логики наз-ся выражение которое строится из пропорциональных переменных по следующим правилам:
1)всякая пропозиционная
2) если и - формулы, то
3) других формул нет
Подформулой формулы наз-ся всякая часть формулы, являющаяся формулой
Порядок действий обычно определяется скобками. Если скобок нет, то операции выполняются в следующем порядке
Логическое значение ф-лы полностью пределяется логическими значениями переменных входящих в ф-лу и значениями логических операций, участвующими в потроение ф-лы. Для произвольных ф-л можно строить таблицы истинности.
Информация о работе Шпаргалка по предмету "Дискретная математика"