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

Date: 2015-10-07; view: 529.

1)Множества- совокупность объектов произвольной .природы. Множества- А, элемент- а.Элемент множества – это объект, кот. Составляет множество. Множество задается простым перечислением его элементов, либо указанием характ.признаков.

Множества: 1. Дескретное- счетное множество,т.е. его элементы можно псочитать(четное, конечное, количество элем.-размерность).Количество элем. дискретного множ. наз-ся его размерностью или мощностью. 2. Непрерывное-это кусок действительных чисел(бесконечность). Универсальное мн.- содержащие все рассматр.мн.

Операции: 1. Дополнение(когда одно из множеств содержащие только отсутствующие элементы первого). 2. Объединение. 3. Пересечение(их общие). 4. Разность(содержит элементы первого,но не содержит эл.второго).5 . симметрическая разность (A\b)U(B\A).

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ — множество А × В всех упорядоченных пар элементов (a, b), из которых a принадлежит множеству A, b — множеству B. Порядок следования пар может быть любым, но расположение элементов в каждой паре (векторе, кортеже) определяется порядком следования перемножаемых элементов. Поэтому A × B ≠ B × A, если B ≠ A..

Функция называется мерой (иногда объёмом), если она удовлетворяет следующим аксиомам:

1. мера пустого множества равна нулю;

2. Для любых непересекающихся множеств — мера объединения непересекающихся множеств равна сумме мер этих множеств (аддитивность, конечная аддитивность).

Норма- Функция d(X) в векторном пространстве над полем вещественных или комплексных чисел, удовлетворяющая следующим условиям: d(X) ≥ 0 (причем d(X) = 0 только при X = 0); d(X+Y) ≤ d(X) + d(Y); d(aX) = |a|d(X), где X, Y — элементы векторного пространства, a — скаляр.

2)Мат.логика-часть общ.логики в которой законы мышления выраж. формулами, показывает ист. Или лож. мат. Утверж. Исходя из совокупности перв. Аксиом. Предмет мат.логики- метод рассуждений построения новых понятий и теорем + изуч.способов рассуждений. П.высказывания-утверждения. С.высказывания-простые+ свзки: «тогда» и «только тогда». Тавтология-всегда ист.высказывание. Мат.фор-тавтология.

Операции: 1.Отрицание-оно истинно когда х ложно и ложно когда х истинно.. 2.Конъюнкция(^-умнож)-высказывание кот. истинно.когда оба высказ-я истинны и ложны для всех отсальных случаев. 3.Дизъюнкцию(сложение)-высказ-я когда оба ложны, для всех осталных случаев истинно. 4.Импликация(x->y, при переходе из0-1 или 1-1->1)-выск-е,кот. ложно,если х- истинно, а у-ложно и истинно во всех остальных случаях.5) Эквивалентность(x<->y)-выск-е, кот. Истинно, если оба высказ-я одновременно истинны или ложны и ложны во всех остальн. случаях..

Таблица истенности- любая операция.. Два высказывания равны,если они принимают одинаковые значения при одинаковых наборах переменных.

Предекарт- функция субъектов заданная на некотором множестве.множ.знач. х ,при кот. Предикат истенен, наз-ся множеством истинности.

Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих выcказывание. Квантор всеобщности (обозначение: , читается: «для любого…»).Квантор существования (обозначение: , читается: «существует…» ). В математической логике приписывание квантора к формуле называется связыванием или квантификацией.

3)Граф-упорядоченная пара множ.V-мн.вершин графов. E-мн.ребер, состоящих из упорядоченных пар элем. Из множества. Вершина инцидентна ребру,если оно является его началом или концом. Графы: 1. Неориентированные. 2. Ориентированные.

Мультиграф-если не одно ребро между двумя вершинами. Петля-ребро началом и концом,кот. служит одна и та же вершина. Псевдографы(там где есть петля). Степень вершины- кол-во ребер инцидентных вершине. Степень выхода(число ребер с одним началом) и степень входа(число ребер с одним и темже концом). Путь- совокупность вершин и ребе соединнех между собой таким образом, что можно двиг.по графу. В орграф- Маршрут. П.Путь-все вершины по 1 разу.

путь: 1.Простой. 2.Замкнутый. Висящей-наз.вершина степень которой равно 0. Размеченный-граф с пронумерованными вершинами.

Способы задания графов: 1.Аналитический(указывают множества V и E) 2. Графический(ввиду диограмм) 3.Задание матриц смежности(вершина-вершина) и инцидентности(вершина-ребро). Изоморфизм- когда из одного соответствует другое. Эйлеров граф- содержащий эйлеров цикл(путь проходящий по всем ребрам только один раз, циклическим является). Гамильтонов граф- граф в котором нач и конеч совпадают , каждую вершину проходит 1 раз.

4)Комбинаторика-раздел дис.матем., в котором изучаются задачи выбора и расположения элементов конечного множества в соответствии с заданными сво-ми. Изучает кол-во комбинация. Выборка-подмнож.заданного мн. КБЗ-позволяет посчитать кол-во кобинаций.

КБЗ: 1. Простые(1-но мно-о или условие). 2.Сложные(либо неск.множ., либо неск.условий). Сложные задачи решаются сведением к простым с использ.комбинаторных принципов слож. и умнож.

Сложение-когда требуется составить комбинации отвечающие одному ИЛИ другому условию. Перемножение-(тоже самое что и слож, только союз «И»).

Выборки:1. Перестановка-комбинации получаемые из всех элем.заданного мн., путем перестанови их эл. ,т.е.состав один,но разный порядок. 2.Размещение-комб.составленные из n-эл., заданного мн., по m-эл, которые отличаются составом и порядком следования(упорядоченные). 3. Сочитания-Комб. Составленные из n-эл., по m-эл., которые отличаются только составом. Выборки:1.Повторяющие. 2. Неповторяющие. Объем-кол-во эл выборки

Факториал-это последовательность нат.чисел от 1 до n.

(надо еще формулы выписать)