Структура - раздел Философия, Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА Частично Упорядоченное Множество X Называется Стру...
Частично упорядоченное множество X называется структурой, если в нем любое двухэлементное множество 
имеет точные границы 
и 
.
Лемма 1. В любой структуре всякое конечное множество элементов имеет точные границы.
Упражнения
1.Упростить выражение 
2. Докажите, что следующие условия эквивалентны 1
, 2. 
, 3 
, 4
, 5 
.
3. Записать множество 
через пересечение (
).
4. Докажите, что 
. Как называется этот закон?
5. Докажите, что 
. Как называется этот закон?
1. Группа студентов насчитывает 25 человек. Из них 15 любят математику, 10 — физику, 8 — не любят ни математику, ни физику. Сколько студентов любят и математику, и физику?
2. На собрании студентов-отличников были как студенты второго курса, так и студенты третьего курса. Все они либо любители прозы, либо любители поэзии. Студентов-юношей было 16, а любителей прозы — 24. Студентов-девушек было ровно столько, сколько юношей любителей прозы. Сколько студентов было на собрании?
3. В группе из 100 студентов английским языком владеют 28 человек, немецким — 30, французским — 42, английским и немецким — 8, английским и французским— 10, немецким и французским— 5, а всеми тремя языками владеют 3 студента. Сколько студентов не знают ни одного из названых языков?
Комментарий
ОТСТУПЛЕНИЕ
Существование и анализ парадоксов в теории множеств способствовали развитию так называемого конструктивизма — направления в математике, в рамках которого рассматриваются только такие объекты, для которых известны процедуры (алгоритмы) их порождения. В конструктивной математике исключаются из рассмотрения те понятия и методы классической математики, которые не заданы алгоритмически
Первым и важнейшим математическим пространством является трехмерное эвклидово пространство, предоставляющее собой приближенный абстрактный образ реального пространства. Общее понятие пространства в математике сложилось в результате обобщений и изменений понятий геометрии эвклидова пространства.
В современной математике пространство — это множество объектов, называемых точками, введенными отношениями между точками и теми или иными операциями над элементами множеств.
Примерами пространств могут служитьметрическое пространство, нормированное пространство, пространство событий, пространство состояний и целый ряд других пространств.Метрическое пространство — это множество точек Х с расстоянием между ними d>0, удовлетворяющем трем аксиомам:
1) d(х, у) =0 тогда и только тогда, когда х=у (аксиома идентичности);
2) d(х, у) = d(у, х) (аксиома симметрии);
3) d(х, у) = d(х, z) + d(y,z) + d(y,z), гдех,у,z
Х (аксиома треугольника).
Расстояние d(х, у) называетсяметрикой, а пара (х, d) —метрическим пространством. Простейшим примером метрического пространства является множество действительных чисел Х с расстоянием между ними d = х - у.
В двумерном эвклидовом пространстве Е2(плоскости) расстояние между двумя точками М1(х1,y1), М2(х2 ,у2) определяется по выражению d2 = (х1 – х2)2 + (у1 – y2)2. Эта же формула распространяется на трехмерное эвклидово пространство d2 = (х1 – х2)2 + (у1 – y2)2+ (z1 - z2)2 и на многомерное его обобщение Еn, в котором элементами множества Х являются упорядоченные наборы <х1, х2, ..., хi ..., хn> действительных чисел: расстояние между двумя точками этого пространства определяется по выражению
d2 = (х1 – х2)2 + (у1 – y2)2 + (z1 - z2)2
Линейные пространства — это такие множества, элементы которых удовлетворяют следующим условиям:
1) для каждой пары элементов х,уХ определен третий элемента zХ, называемый их суммой и обозначаемой как х+у. При этой сумма удовлетворяет следующим условиям: х+у=у+х,
x+(у+v) = (x+у)+v;
2) во множестве Хсуществует такой элемент 0, что х+0 = х для всех хX;
3) для всех хХ существует такой элемент-х, что х+(-х) = 0;
4) для любого числа а и любого элемента хX определен элемент а такой, что (а+β)х = ах+βx, а(х+у) = ах + ау.
Очевидным примером линейного пространства является множество действительных чисел с обычными правилами их сложениям умножения. Если n-мерном эвклидовом пространстве E* упорядоченные наборы чисел <х1, ..., хi, ..., хn>Х считать координатами векторов с условием, что нулевой вектор – это вектор с нулевыми значениями <х1, ..., хi, ..., хn>, то такое векторное пространство линейное, потому что операции действия с вектором отвечают перечисленным выше аксиомам.
Дальнейшим расширением понятия линейного пространства является линейное нормированное пространство. Это такое пространство, в котором для каждого элемента хX существует неотрицательное число ||х||, называемое его нормой и удовлетворяющее следующим условиям:
||х|| = 0, тогда и только тогда, когда х = 0;
||ах|| = а||х||, где а — некоторое число;
||х+y|| ≤ ||х|| + ||y||
Линейное нормированное пространство является метрическим пространством с нормой d = ||х - y||, так как эта норма удовлетворяет аксиомам метрического пространства:
||х - y|| = 0, если х = у; ||х - y|| = ||y-х||; ||х - y|| ≤ ||х - z|| + ||z - y||
Нормой ||х|| в одномерном векторном пространстве Е1является абсолютная величина х. Нормой двумерного пространства (плоскости) Е2 является длина вектора, вычисляемая по выражению ||х|| = 
. Для n-мерного векторного пространства норма ||х|| определяется по аналогии с двухмерным пространством
||х|| = 
.
В заключение следует сказать, что в терминах линейных векторных пространств формулируются задачи математического программирования, и в частности, дискретного программирования, которое относят к задачам дискретной математики.
Все темы данного раздела:
Предмет дискретной математики
Предмет дискретная (финитная, конечная) математика – направление математики, изучающее свойства дискретных структур, в то время как классическая (непрерывная) математика изучает свойства объ
Изоморфизм
Наука, изучающая алгебраические операции называется алгеброй. Это понятие по мере изучения курса будет конкретизироваться и углубляться. Алгебру интересует только вопрос, КАК действуе
Упражнения
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. Если , то
Множество с атрибутивной точки зрения
Агрегатная точка зрения, в отличие от атрибутивной, является логически несостоятельной в том плане, что она приводит к парадоксам типа Рассела и Кантора (см. ниже).
В рамках атрибутивной т
Покрытие и разбиение множеств
Разбиением множества А называется семейство А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) (с неотрицательными значениями) очень удобны следующи
Метаобозначения
Обозна-чения
Содержание
Пример
ИЛИ
Новости и инфо для студентов