Презентация, доклад на тему Основы дискретной математики

Анри Пуанкаре.

3 Классифицировать функции

4 Рассмотреть основные понятия графов

5 Классифицировать основные логические операции

6 Изучить основные понятия о деревьях

Обозначение: f : x →y; y = f(x)

Здесь Y – зависимая переменная, X – независимая переменная (аргумент)

Понятие функции

При аналитическом способе функцию можно задать:
Несколькими выражениями
Параметрически
В полярной системе координат

Обратно тригонометрическая: Y=arcsin X, Y=arccos X,
Y =arctg X, X= arcctg Y

Степенная: Y=xa;

Показательная: Y=ax;

Логарифмическая: Y=logax

Логическая: Y = true; X = false;

Например: {1, 3, 5, 7} или {a, b, c, d}.

Для обозначения множества в тексте используют прописные буквы латинского алфавита A, B, C, ...X, Y, Z, а для его элементов - строчные буквы a, b, c,...x, y, z.
Иногда эти буквы используют с индексами.

Принадлежность множества

Элемент Х не принадлежит множеству A

Основное отношение между элементами и множеством - это отношение принадлежности элемента множеству.

Если N конечно, то множество называют конечным.

Число элементов счетного конечного множества A называют его мощностью и обозначают так:
|A|=n.

Понятие подмножества

А={1, 2, 3}

B={1, 2, 3, 4, 5}

“⊆“

Обозначение:

знак включения: A⊆B.

знак невключения A⊄B

“⊄“

Пустое множество является подмножеством любого множества.

Обозначение:

∅

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

∅ ={ } (нет элементов)

Обозначение:

U

U ={a, b, c, d}

Множества, элементами которых являются другие множества, часто называют семействами или классами.

Например, A∈{{a, b}, {b, c, d}}, B∈{{a, b}, {b, c, d}}.

Максимально возможное число подмножеств универсального множества называют булеаном.

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

fi: X→X или fi: Xn→X.

Множество X вместе c заданным множеством операций F={f1, f2, ..} называют Алгеброй.

- символ унарной операции – дополнения,
∪ - символ бинарной операции – объединения,
∩ -символ бинарной операции - пересечения.

Если В=∅, то А∪В=А∪∅=А.
Если B=U, то А∪В=А∪U=U.
Если А⊆С и В⊆С, то А∪В⊆С.

Обозначение:

Объединение множеств

Если В=∅, то А∩В=А∩∅=∅.
Если B=U, то А∩В=А∩U=А.
Если С⊆А и С⊆В, то С⊆А∩В.
Если А≠∅ и В≠∅, то при А∩В=∅ множества A и B не имеют общих элементов

Обозначение:

Пересечение множеств

“\”

С=(А\В)= {x|x∈А и x∉В},

“Δ”

С=(АΔВ)=(А∩⎤В)∪(В∩⎤А)

(АΔВ)=(А∩⎤В)∪(В∩⎤А)=∅, то А=В.

*Это правило будет часто использоваться при доказательстве тождеств и поиске неизвестных множеств.

Отношение

R часто пишут xRy.

Бинарное отношение

Бинарные отношения между элементами множества X удобно описывать матрицами (Х⊗Х), строки и столбцы которых есть элементы множества.
На пересечении i-ой строки и j-го столбца ставят знак “1”, если задано отношение r(i, j) между i-м и j-м элементами и “0” в противном случае

Рефлексивность

Симметричность

Асимметричность

Рефлексивность

Отношения Эквиваленций

=

+

+

Отношения Эквиваленций

Отношение эквиваленции обозначают r~(xi, xi) или ~(xi, xi).

История логики

Первым этапом на пути в развитии логики заложил Аристотель, создав основы формальной логики, где впервые отделил логические формы речи от ее содержания.

Поэтому начальный раздел математической логики часто называют булевой алгеброй или алгеброй логики.

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

Математическая логика

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно сказать, истинно оно или ложно.

Например, предложение «6-четное число» следует считать высказыванием, так как оно истинное.
Предложение «Рим – столица Франции» тоже высказывание, так как оно ложное.

Высказывания, которые получаются из простых предложений с помощью грамматических связок “не”, “и”, “или”, “если…, то…”, “… тогда и только тогда, когда…” и т.п., называют сложными.
Для обозначения грамматических связок в формальном языке вводят дополнительные символы, которые называют логическими связками.
∨:=”или”,
&:=“и”,
⎤:=”не”,
→:=“если…, то…”,
↔:=“…тогда и только тогда, когда …”.
Для построения сложных высказываний используют также вспомогательные символы “(“, “)” - скобки.

Высказывание

Символы логических операций заданы логическими связками:

⎤ - отрицание,
& - конъюнкция,
∨ - дизъюнкция,
→ - импликация,
↔ - эквиваленция.

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

(⎤ F)

Обозначение:

Таблица логического отрицания

(F1&F2)

Обозначение:

Таблица логического умножения

(F1∨F2)

Обозначение:

Дизъюнкция

Таблица логического сложения

(F1↔F2)

(F1→F2)

Обозначение:

Импликация

Таблица логического следования

Мы часто сталкиваемся с задачами, в условиях которых заданы некоторые объекты и между некоторыми их парами имеются определенные связи.
Если объекты изобразить точками (вершинами), а связи - линиями (ребрами), соединяющими соответствующие пары точек, то получится рисунок, называемый Графом.

История графов

Для пояснения задачи представлена модель, где каждый участок суши замещен точкой на плоскости, а мосты – линиями, связывающими участки.

Множество точек, являющихся образом множества объектов, называют вершинами графа, а множество отрезков линий, являющихся образом множества отношений, - рёбрами или дугами графа.

Вершина

Ребро

E вершина u называется началом e, а вершина v - концом e, говорят, что ребро e ведет из u в v.

V1={ a,b,c,d}, E1={ (a,b), (a,c), (b,b), (b,d), (d,a)},

G1=(V1, E1)

Ориентированный граф

E имеется противоположное ребро (v,u) E,
т.е. отношение E симметрично.

Для его задания можно использовать обозначение для множества концов: {u, v}, но чаще используется указание одной из пар в круглых скобках. Если e= (u,v) E, то вершины u и v называются смежными в G, а ребро e и эти вершины называются инцидентными. Степенью вершины в неориентированном графе называется число смежных с ней вершин. Вершина степени 0 называется изолированной.

Такая пара (u,v), (v,u) называется неориентированным ребром

G2=(V2, E2 )

V2={ a,b,c,d}, E2={ (a,b), (a,c), (a,d), (b,d)}

Неориентированный граф

Неориентированный граф называется деревом, если он связный и в нем нет циклов.

Ориентированный граф G=(V,E) называется (ориентированным) деревом, если:

в нем есть одна вершина, в которую не входят ребра; она называется корнем дерева
в каждую из остальных вершин входит ровно по одному ребру;
все вершины достижимы из корня.

Способы позволяют линейно упорядочить вершины дерева и тем самым представить его "двумерную структуру" в виде линейной последовательности вершин.

Способы обхода деревьев

Прямой

Обратный

основан на принципе: "сначала родитель, затем дети"

основан на противоположном принципе: "сначала дети, затем родитель".