Представление бинарных деревьев - раздел Философия, Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА Всякое Свободное Дерево Можно Ориентировать, Назначив Один Из Узлов Корнем. В...
Все темы данного раздела:
Предмет дискретной математики
Предмет дискретная (финитная, конечная) математика – направление математики, изучающее свойства дискретных структур, в то время как классическая (непрерывная) математика изучает свойства объ
Изоморфизм
Наука, изучающая алгебраические операции называется алгеброй. Это понятие по мере изучения курса будет конкретизироваться и углубляться. Алгебру интересует только вопрос, КАК действуе
Упражнения
1. Докажите, что изоморфное отображение всегда изотонно, а обратное утверждение неверно.
2. Запишите на языке множеств свою группу.
3. Запишите на языке множеств предметы, которые
Множество и элементы множества
В настоящее время существующие теории множеств различаются парадигматикой (системой взглядов) концептуального базиса и логических средств. Так, в качестве примера, можем привести две противоположны
Конечные и бесконечные множества
То, из чего состоит множество, т.е. объекты, образующие множество, называется его элементами. Элементы множества различны и отличаются друг от друга.
Как видно из приведенных пример
Мощность множества
Мощность для конечного множества равна числу его элементов. Например, мощность универсума В(A) множества A мощностью n
А1A2A3| + … + |А1A2A3| + … + |А1A2An| + … + |Аn-2An-1An| + (-1)n-1 |А1A2A3…An|.
Конечное множество А имеет мощность k, если оно равномощно отрезку 1.. k;:
Подмножество, собственное подмножество
После того как введено понятие множества, возникает задача конструирования новых множеств из уже имеющихся, то есть определить операции над множествами.
Множество М',
Символический язык содержательных теорий множеств
В процессе изучения курса будем различать объектный язык теории множеств и метаязык, средствами которого изучается объектный язык.
Под языком теории множеств будем понимать реляцион
Доказательство
Множество В бесконечно, значит,
Добавление и удаление элементов
Если А — множество, а х — элемент, причем , то элемент
Ограниченные множества. Границы множеств
Пусть на некотором множестве X задана числовая функция f(х).
Верхней гранью (границей) функции f(х) называется такое число
Точная верхняя (нижняя) граница
Совокупность всех верхних границ Е обозначается через Еs, всех нижних границ - через Еi. В случа
Точная верхняя (нижняя) граница множества
Если элемент z принадлежит пересечению множества E и множеству всех его верхних границ Es (соответственно нижних г
Основные свойства верхних и нижних границ
Пусть X - частично упорядоченное множество.
1. Если , то
Множество с атрибутивной точки зрения
Агрегатная точка зрения, в отличие от атрибутивной, является логически несостоятельной в том плане, что она приводит к парадоксам типа Рассела и Кантора (см. ниже).
В рамках атрибутивной т
Структура
Частично упорядоченное множество X называется структурой, если в нем любое двухэлементное множество
Покрытие и разбиение множеств
Разбиением множества А называется семейство Аi
Бинарные отношения
Последовательность длины п, члены которой суть а1, .... аn, будем обозначать через {а1, .... а
Свойства бинарных отношений
Бинарное отношение R на множестве Хобладает следующими свойствами:
(а) рефлексивно, если хRх
Тернарные отношения
Декартовым произведением XY
N-арные отношения
По аналогии с декартовым произведением двух множеств X,Y можно построить декартово произведение X
Отображения
Отображения – это некоторые связи между элементами множеств. Простейшими примерами отношений являются отношения принадлежности х
Соответствие
ПодмножествоSдекартового произведения называетсяn-арным соответствиeмэлементов множествMi.
Формально
Функция
В основе всех разделов дискретной математики лежит понятие функции.
Пусть Х —
Представление функции в терминах отношений
Функцией называется бинарное отношение f, если из и
Инъекция, сюръекция, биекция
При использовании термина «отображение» различают отображение ХвY и отображение Х на Y
Обратная функция
Для произвольных , определим
Частично упорядоченные множества
Множество S называется частично упорядоченным (ЧУМ), если на нем задано рефлексивное, транзитивной и антисимметричное бинарное отношение частичного порядка
Минимизации представления множества
Используя эти законы, рассмотрим задачу минимизации представления множества М с помощью операций
Перестановки
Дано множество A. Пусть A – конечное множество, состоящее из n элементов A = {a1, a2, …, a
Перестановки с повторениями
Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n1, n2, … ,nk
Размещения
Кортежи длины k (1≤k≤n), состоящие из различных элементов n-элементного множества A (кортежи отличаются од
Размещения с повторениями
Пусть во множестве A имеются одинаковые (повторяющиеся) элементы. Размещениями с повторениями из n элементов по k назы
Упорядоченное размещение
Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два
Сочетания
Из m-элементного множества A построим упорядоченное множество длины n, элементы которого являются размещениями с одними и тем
Сочетания с повторениями
Полученные формулы справедливы только, когда в множестве A нет одинаковых элементов. Пусть имеются элементы n видов и из них составляется кортеж из
Метод производящий функций
Этот метод используется для перечисления комбинаторных чисел и установления комбинаторных тождеств.
Исходным пунктом являются последовательность {ai} комбинатор
Алгебраическая система
Алгебраической системой A называется совокупность ‹M,O,R›, первая составляющая которой M есть непустое множество, вторая компонента O – множество
Замыкание и подалгебры
Подмножество называется замкнутым относительно операции φ, если
Алгебры с одной бинарной операцией
Пусть на множестве М задана одна бинарная операция. Рассмотрим порождаемые ею алгебры, но предварительно рассмотрим некоторые свойства бинарных операций.
Бинарная о
Группоид
Алгебра вида <М, f2>называется группоидом.
Если f2 — операция типа умножения (
Фактор-множества и фактор-алгебра
Если отношение R обладает свойствами: рефлексивное симметричное транзитивное, т.е. является отношением эквивалентности (~ или ≡ или Е) на множестве M
Целые числа по модулю m
Дано кольцо целых чисел <Z; +, >.
Напомним. Алгебра <М,
Конгруэнции
Конгруэнцией на алгебре A = <A; Σ> (Σ – сигнатура алгебры состоит только из функциональных символов) называется такое отношение эквивалентности
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Графы - математические объекты.
Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование о
Граф, вершина, ребро
Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что
Соответствие
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, ко
Неориентированный граф
Если ребра не имеют ориентации, то граф называется неориентированным (неориентированный дубликат или неориен
Инцидентность, смешанный граф
Если ребро е имеет вид {и, v } или <и, v>, то будем говорить, что ребро е инцидентно вер
Обратное соответствие
Поскольку представляет собой множество таких вершин
Изоморфизм графов
Два графа G1 = <V1, E1> и G2 = <V2, E2> изоморфны (G
Путь, ориентированный маршрут
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в котор
Смежные дуги, смежные вершины, степень вершины
Дуги а = (хi, хj), хi ≠ хj, имеющие общие концевые вершины, н
Связность
Две вершины в графе называются связным, если существует соединяющая их простая цепь. Граф называется связным, если все его вершины связны.
Теорема.
Граф со взвешенными дугами
Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую на
Матрица сильной связности.
Матрица сильной связности: по диагонали ставим 1; заполняем строку X1 - если вершина достижима из X1 и X1 д
ДЕРЕВЬЯ
Деревья важны не только потому, что они находят приложения в различных областях знаний, но и Вилу особого положения их в самой теории графов. Последнее вызвано предельной простотой строения деревье
Следствие 1 В любом нетривиальном дереве имеются по крайней мере две висячие вершины.
Доказательство
Рассмотрим дерево G(V, Е). Дерево — связный граф, следовательно,
Теорема
Центр свободного дерева состоит из одной вершины или из двух смежных вершин:
Z(G) = 0&k(G) = 1 → С(G) = К1
Ориентированные, упорядоченные и бинарные деревья
Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и программировании. Дерево (ориент
Доказательство
1. Каждая дуга входит в какой-то узел. Из п. 2 определения 9.2.1 имеем:
v
Упорядоченные деревья
Множества Т1,.. ., Тk в эквивалентном определении ордерева являются поддеревьями. Если относительный порядок поддеревьев Т1,.. .,
Бинарные деревья
Бинарное (или двоичное) дерево - это конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев - левого и правого.
Бинарное дерево не яв
Представление свободных деревьев
Для представления деревьев можно использовать те же приёмы, что и для представления графов общего вида — матрицы смежности и инциденций, списки смежности и другие. Но используя особенные свойства д
End for
Обоснование
Код Прюфера действительно является представлением свободного дерева. Чтобы убедиться в этом, покажем, что если Т' — дерево
Основные логические функции
Обозначим через E2 = {0, 1} – множество, состоящее из двух чисел. Числа 0 и 1 являются основными в дискретной мате
Булева функция.
Булевой функцией от n аргументов x1, x2, … ,xn, называется функция f из n-ой степени множества
Двухэлементная булева алгебра.
Рассмотрим множество Во = {0,1} и определим на нем операции , согласно таблицам ист
Таблицы булевых функций
Булева функция от n переменных может быть задана таблицей, состоящей из двух столбцов и 2n строк. В первом столбце перечисляются все наборы из B
F5 – повторение по y
f6 – сумма по модулю 2
f7
Порядок выполнения операций
Если в сложном выражении скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание.
Соглашения относительно расстановки ско
Эквивалентность формул
Различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.
Формулы φ(x1,..., xn) и
Замечание
1. Формула φ тождественно ложна тогда и только тогда, когда неφ тождественно истинна (|=неφ );
2. Формула φ
Фактор-алгебра алгебры формул
Обозначим через Фn множество всех формул алгебры логики с переменными из множества {х1, х2, ... , хn}.
Определение
Если х — логическая переменная, , то выражение
Алгоритм приведения формулы к ДНФ.
1. Выразить все логические операции, участвующие в построении формулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалентности
Совершенные ДНФ (СДНФ) и КНФ (СКНФ).
Пусть (x1,..., xn) — набор логических переменных, Δ = (δ1,,.., δп) — набор нулей и
Первая теорема Шеннона
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исходной формуле φ, предварительно рассмотрим разложения булевой функции f(x1, х2
Вторая теорема Шеннона
В силу принципа двойственности для булевых алгебр справедлива
Теорема 6.4.3 (вторая теорема Шеннона). Любая булева функция f(x1, х2,...
Функциональная полнота
Теорема(о функциональной полноте). Для любой булевой функции f найдется формула φ, представляющая функцию f
Алгоритм нахождения СДНФ.
Для нахождения СДНФ данную формулу нужно привести сначала к ДНФ, а затем преобразовать ее конъюнкты в конституенты единицы с помощью следующих действий:
а) если в конъюнкт входит некоторая
Метод Квайна
Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие триоперации:
- операция полного склеивания -
Каноническое представление логических функций
Каноническими формами логических (формул) функций называются выражения, имеющие стандартную форму булевой формулы такой, которая однозначно представляет логическую функцию.
В алгебр
Системы булевых функций
Пусть даны булевы функции f(g1, g2, …, gm) и g1(x1, x2, …, xn), g2(x1
Базис Жегалкина.
Примерю Рассмотрим систему . Она является полной, так как любая функция из стандартного базиса выражается чере
Теорема Поста
Теорема Поста устанавливает необходимые и достаточные условия полноты системы булевых функций.
(Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Stu
Доказательство.
Необходимость. От противного. Пусть и
Алгебра Жегалкина
Сумма по модулю 2, конъюнкция и константы 0 и 1 образуют функционально полную систему, т.е. образуют алгебру - алгебру Жегалкина.
A = <FB,
ЛОГИКА ВЫСКАЗЫВАНИЙ
Математическая логика изучает базовые понятия синтаксиса (формы) и семантики (содержания) естественного языка. Рассмотрим три крупных направления исследований в математической логике — логику
Определение предиката
Пусть Х1, Х2, ..., Хп произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных вы
Применение предикатов в алгебре
Рассмотрим предикаты, в которых свободной является лишь одна переменная, которую обозначим через х, и обсудим применение предикатов в алгебре.
Типичным приме
Булева алгебра предикатов
Так как к предикатам можно применять логические операции, то для них справедливы основные законы булевой алгебры.
Теорема. (Свойства логических операций для предикатов).
Мн
F↔G=(F→G)(G→F), F→G=неFG.
2. Использовать закон ненеF=F, законы де Моргана:
не(F
Исчисление предикатов
Исчисление предикатов называют еще теорий первого порядка.
В исчислении предикатов, так же как и в исчислении высказываний, на первом по важности месте стоит проблема разрешимост
Следование и эквиваленция
Высказывательная форма Q2 следует из высказывательной формы Q1, если импликация Q1→Q2 обращается в истинное выс
Принятые обозначения
Символы «порядка не более». При сравнении скорости роста двух функций f(n) и g(n) (с неотрицательными значениями) очень удобны следующи
Метаобозначения
Обозна-чения
Содержание
Пример
ИЛИ
Новости и инфо для студентов