Свойства бинарных отношений - раздел Философия, Курс лекций По дисциплине ДИСКРЕТНАЯ МАТЕМАТИКА Бинарное Отношение R На Множестве Х...
Бинарное отношение R на множестве Хобладает следующими свойствами:
(а) рефлексивно, если хRхдля каждого ,
Отношение R на множестве Х является рефлексивным, если оно выполняется между самим элементом, т.е. хRх. Пример, в отношениях «х имеет общий признак с у», «х похож на у» имеет место хRх, так как элемент х похож на самого себя.
- прямая x параллельна прямой y в плоскости z - хRх
- студент x ровесник студенту y – каждый студент сам себе ровесник хRх.
(а1) иррефлексивно, если хRхне имеетсмысла
- отношение строго порядка x <x на множестве действительных чисел – оно всегда ложно.
(а2) антирефлексивно, если хRхдля каждого ,
Отношение R на множестве Х являетсяантирефлексивным, если хRх не выполняется ни для одного хX. Например, в отношениях «брат х старше брата у», «операция х выполняется раньше операции у», хRх не выполняется, так как брат хне может быть старше себя, а операция х начаться раньше самой себя.
(б) транзитивно, если произвольных ,
Отношение R на множестве Х является транзитивным, если для всех из соотношений хRу, уRzследует хRz. Например, в отношении «операция х предшествует операции y, а операция у предшествует операции z из хRу и уRzследует хRz.
- город x связан с городом y шоссейной дорогой – между городом y и z
- студент x ровесник студенту y
- треугольник x подобен треугольнику y
- действительное число x больше действительного числа y
(в) симметрично, если для произвольных ,
Отношение R на множестве Х являетсясимметричным, если для всех х,уХ из хRу следует уRх. Например, в отношениях «хпохож на у», «операция хнесовместима с операцией у» имеет место как хRу, так и уRх. Действительно, если х похож на у, то у похож на х, если операция х несовместима с у, то операция у несовместима с х.
- прямая х перпендикулярна у (не рефлексивно).
- студент х приходится соседом у (не рефлексивно) .
(в1) антисимметрично, если для произвольных .
Отношение R на множестве Х являетсяантисиммитричным, если соотношения хRуи уRх выполняются тогда и только тогда, когда х = у для всех . Например, в отношении «операция х является частью операции у» имеет место хRуи уRх только тогда, когда х = у.
- бинарное отношение включения множеств
(в2) асимметрично, если для произвольных .
Отношение R на множестве Х является асимметричным, если из двух соотношений хRу, уRх одно не выполнено для всех . Например, в отношениях «х подчиняется у», «операция х выполнена раньше операции у» имеет место хRу, но не выполняется уRх.
Помимо этих свойств на практике используются еще следующие:
- отношением эквивалентности,
- отношение толерантности
- отношения порядка.
Отношение эквивалентности
Отношение эквивалентности – это произвольное бинарное отношение R на множестве Х, обладающее свойствами:
- рефлексивности,
- транзитивности
- симметричности.
По смыслу отношение эквивалентности определяется как «элементы х и у одинаковы», «элементы х и у взаимозаменяемы».
В этом отношении каждый элемент эквивалентен самому себе (рефлексивность). Если элемент х эквивалентен элементу у, то и элемент у эквивалентен элементу х (симметричность). Если элемент х эквивалентен элементу у, а элемент у эквивалентен элементу z, то элемент х эквивалентен элементу z (транзитивность).
Лемма 1.Всякое разбиение множества А на классы задает на множестве А отношение эквивалентности.
Доказательство. Пусть , положим aRb ↔a и b лежат в одном классе разбиения. Покажем, что полученное бинарное отношение является отношением эквивалентности. Для этого необходимо доказать, что оно рефлексивно, симметрично и транзитивно. Действительно. Поскольку a лежит в некотором классе разбиения, то aRa, т.е. оно рефлексивно.
Пусть K – некоторый класс разбиения и тогда и т.е aRb →bRa, Симметричность доказана.
Из aRb →bRc следует , Следовательно aRc, ч.т.д.
Лемма 2.Всякое отношение эквивалентности R, определенное на множестве А задает разбиение на классы.
Лемма 3.Между разбиениями множества на классы и отношениями эквивалентности, заданными на этом множестве , существует взаимно однозначное соответствие.
Пример 1. Отношение эквивалентности на множестве чисел является отношение равенства (=). Любое число а из множества действительных чисел равно самому себе a=a (рефлексивность). Если а=b, то b=а (симметричность). Если а=b, а b=с, то а=с (транзитивность).
Пример 2. Отношения параллельности прямых в эвклидовой плоскости.
Пример 3. Отношения проживания в одном доме жителей города.
Отношение эквивалентности разбивает любое множество на непересекающиеся подмножества (классы эквивалентности). В примере 3 все жители города разбиваются на жителей, живущих в одних и тех же домах. В результате получим столько классов эквивалентности, сколько домов, в которых проживают люди. Таким образом, если Мi, — i-й классiI, а М — множество жителей, то iIMi =M, MiMj=для всех i, j I ,где I — множество классов.
Примеры на эквивалентность
1. R - отношение равенства(=).
Отношение равенства x = y является эквивалентностью на любом множестве A, так как оно
рефлексивно (x = x),
симметрично (x = y y = x),
транзитивно (x = y & y = z x = z).
2. R - отношение подобия треугольников.
Отношение подобия на множестве треугольников является отношением эквивалентности.
рефлексивно (x = x),
симметрично (x = y y = x),
транзитивно (x = y & y = z x = z).
3. R - отношение равномощности.
На любом множестве B(U) отношение равномощности |A| = |B| является отношением эквивалентности. Для любых множеств A, B, C выполняются следующие свойства:
рефлексивно: (A ~ A поскольку idA : A ↔ A),
симметрично: если A ~ B, то B ~ A (так как из f: A ↔ B следует f-1: B ↔ A),
транзитивно: если A ~ B и B ~ C, то A ~ C (так как из f: A ↔ B, g: B ↔ C следует f◦g: A ↔ C).
4. R - отношение принадлежности.
Отношение принадлежности к одной студенческой группе на множестве студентов МГСУ является отношением эквивалентности.
рефлексивно (x = x),
симметрично (x = y y = x),
транзитивно (x = y & y = z x = z).
5. R - отношение вычисление одной и той же функции.
Пусть M – множество программ, вычисляющих одну и ту же функцию. Отношение E = {(x,y)| программы x и y вычисляют одну и ту же функцию} на множестве M является отношением эквивалентности.
рефлексивно (x = x),
симметрично (x = y y = x),
транзитивно (x = y & y = z x = z).
Отношениетолерантности
Отношение R на множестве Х называется отношениемтолерантности, если оно
- рефлексивно
- симметрично.
Пример. Отношение «игрок х играет сам с собой в шахматы и с другом у» есть отношение толерантности, так как хRх, а хRувлечет уRх.
Отношения порядка
А) Нестрогий порядок
Отношение R на множестве Х называется отношениемнестрого порядка, если оно
- рефлексивно,
- антисимметрично
- транзитивно.
Отношения ≤, ≥ на множестве чисел Х являются отношениями нестрогого порядка, так как любое число хХ равно самому себе (рефлексивность).
Для любой пары чисел х,уХпри а≤b не выполняется b≤a, а при а≥b не выполняется b≥a (антисимметричность).
Для любой тройки чисел х,у,zX, если а≤b и b≤с, то а≤с или, если а ≥b, b≥с, то а ≥с (транзитивность).
Б) Отношение частичной упорядоченности
Отношение частичной упорядоченности - это произвольное бинарное отношение, обладающее свойствами:
- рефлексивности,
- транзитивности
- антисимметричности.
Отношение частичной упорядоченности обычно обозначается через « ≤ », а пара <Х, ≤ > называется частично упорядоченным множеством. Будем применять также очевидные обозначения, такие как х ≥ у для у ≤ х, х <. у для и т. д.
Примером частично упорядоченного множества может служить множество целых чисел с отношением делимости, множество целых (или вещественных) чисел с обычным отношением меньше или равно « ≤ », а также множество Р(X)с отношением включения .
В) Отношениестрого порядка
Отношение R на множестве Х называется отношениемстрого порядка, если оно
- антирефлексивно,
- антисимметрично
- транзитивно.
Отношения <, > на множестве чисел Х являются отношениями строгого порядка, так как любое число хX не может быть меньше или больше самого себя (антирефлексивность).
Для любой пары чисел х, уX при х<у не может быть у<х, а при х>уне выполняется у>х (антисимметричность).
Для любой тройки чисел х,у,zX, еслих<у, ау<z, то х< z, если х>у, а у> z, то х>z (транзитивность).
Множество Х с заданным на нем отношением нестрогого или строгого порядка R называетсяупорядоченным и обозначается парой <X, R>.
Если для каждой пары х, уX справедливо отношение строгого или нестрогого порядка, то множество <X, R> называетсяполностью упорядоченным. В противном случае множество <X, R> называется частично упорядоченным.
Строгий или нестрогий порядок, заданный на полностью упорядоченном множестве <X, R>, называетсялинейным порядком.
Пример 1. Все множества чисел линейно упорядочены, так как для любых чисел из этих множеств одно меньше другого или они равны.
Пример 2. Множество букв русского или латинского алфавита линейно упорядочено отношением предшествования, или, что то же, отношением следования.
Пример 3. Отношение подчиненности на некотором предприятии определяет строгий частичный порядок, так как в нем несравнимы сотрудники разных отделов.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ... ИНСТИТУТ ЭКОНОМИКИ УПРАВЛЕНИЯ И ИНФОРМАЦИОННЫХ СИСТЕМ В СТРОИТЕЛЬСТВЕ... ИЭУИС...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Свойства бинарных отношений
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Предмет дискретной математики
Предмет дискретная (финитная, конечная) математика – направление математики, изучающее свойства дискретных структур, в то время как классическая (непрерывная) математика изучает свойства объ
Изоморфизм
Наука, изучающая алгебраические операции называется алгеброй. Это понятие по мере изучения курса будет конкретизироваться и углубляться. Алгебру интересует только вопрос, КАК действуе
Упражнения
1. Докажите, что изоморфное отображение всегда изотонно, а обратное утверждение неверно.
2. Запишите на языке множеств свою группу.
3. Запишите на языке множеств предметы, которые
Множество и элементы множества
В настоящее время существующие теории множеств различаются парадигматикой (системой взглядов) концептуального базиса и логических средств. Так, в качестве примера, можем привести две противоположны
Конечные и бесконечные множества
То, из чего состоит множество, т.е. объекты, образующие множество, называется его элементами. Элементы множества различны и отличаются друг от друга.
Как видно из приведенных пример
Мощность множества
Мощность для конечного множества равна числу его элементов. Например, мощность универсума В(A) множества A мощностью n
Подмножество, собственное подмножество
После того как введено понятие множества, возникает задача конструирования новых множеств из уже имеющихся, то есть определить операции над множествами.
Множество М',
Символический язык содержательных теорий множеств
В процессе изучения курса будем различать объектный язык теории множеств и метаязык, средствами которого изучается объектный язык.
Под языком теории множеств будем понимать реляцион
Ограниченные множества. Границы множеств
Пусть на некотором множестве X задана числовая функция f(х).
Верхней гранью (границей) функции f(х) называется такое число
Точная верхняя (нижняя) граница
Совокупность всех верхних границ Е обозначается через Еs, всех нижних границ - через Еi. В случа
Множество с атрибутивной точки зрения
Агрегатная точка зрения, в отличие от атрибутивной, является логически несостоятельной в том плане, что она приводит к парадоксам типа Рассела и Кантора (см. ниже).
В рамках атрибутивной т
Структура
Частично упорядоченное множество X называется структурой, если в нем любое двухэлементное множество
Частично упорядоченные множества
Множество 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
Конгруэнции
Конгруэнцией на алгебре A = <A; Σ> (Σ – сигнатура алгебры состоит только из функциональных символов) называется такое отношение эквивалентности
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Графы - математические объекты.
Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование о
Граф, вершина, ребро
Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, что
Соответствие
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, ко
Неориентированный граф
Если ребра не имеют ориентации, то граф называется неориентированным (неориентированный дубликат или неориен
Инцидентность, смешанный граф
Если ребро е имеет вид {и, v } или <и, v>, то будем говорить, что ребро е инцидентно вер
Связность
Две вершины в графе называются связным, если существует соединяющая их простая цепь. Граф называется связным, если все его вершины связны.
Теорема.
Граф со взвешенными дугами
Граф G = (N, A) называется взвешенным, если на множестве дуг A определена некоторая функция l: A → R, которую на
Матрица сильной связности.
Матрица сильной связности: по диагонали ставим 1; заполняем строку X1 - если вершина достижима из X1 и X1 д
ДЕРЕВЬЯ
Деревья важны не только потому, что они находят приложения в различных областях знаний, но и Вилу особого положения их в самой теории графов. Последнее вызвано предельной простотой строения деревье
Теорема
Центр свободного дерева состоит из одной вершины или из двух смежных вершин:
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-ой степени множества
Таблицы булевых функций
Булева функция от n переменных может быть задана таблицей, состоящей из двух столбцов и 2n строк. В первом столбце перечисляются все наборы из B
Порядок выполнения операций
Если в сложном выражении скобок нет, то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание.
Соглашения относительно расстановки ско
Эквивалентность формул
Различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.
Формулы φ(x1,..., xn) и
Замечание
1. Формула φ тождественно ложна тогда и только тогда, когда неφ тождественно истинна (|=неφ );
2. Формула φ
Фактор-алгебра алгебры формул
Обозначим через Фn множество всех формул алгебры логики с переменными из множества {х1, х2, ... , хn}.
Определение
Если х — логическая переменная, , то выражение
Алгоритм приведения формулы к ДНФ.
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, ..., Хп произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных вы
Применение предикатов в алгебре
Рассмотрим предикаты, в которых свободной является лишь одна переменная, которую обозначим через х, и обсудим применение предикатов в алгебре.
Типичным приме
Булева алгебра предикатов
Так как к предикатам можно применять логические операции, то для них справедливы основные законы булевой алгебры.
Теорема. (Свойства логических операций для предикатов).
Мн
Исчисление предикатов
Исчисление предикатов называют еще теорий первого порядка.
В исчислении предикатов, так же как и в исчислении высказываний, на первом по важности месте стоит проблема разрешимост
Следование и эквиваленция
Высказывательная форма Q2 следует из высказывательной формы Q1, если импликация Q1→Q2 обращается в истинное выс
Принятые обозначения
Символы «порядка не более». При сравнении скорости роста двух функций f(n) и g(n) (с неотрицательными значениями) очень удобны следующи
,
,
произвольных 
,
из соотношений хRу, уRz следует хRz. Например, в отношении «операция х предшествует операции y, а операция у предшествует операции z из хRу и уRz следует хRz.
для произвольных 
,
Х из хRу следует уRх. Например, в отношениях «хпохож на у», «операция хнесовместима с операцией у» имеет место как хRу, так и уRх. Действительно, если х похож на у, то у похож на х, если операция х несовместима с у, то операция у несовместима с х.
для произвольных 
. Например, в отношении «операция х является частью операции у» имеет место хRу и уRх только тогда, когда х = у.
, положим aRb ↔a и b лежат в одном классе разбиения. Покажем, что полученное бинарное отношение является отношением эквивалентности. Для этого необходимо доказать, что оно рефлексивно, симметрично и транзитивно. Действительно. Поскольку a лежит в некотором классе разбиения, то aRa, т.е. оно рефлексивно.
тогда и 
т.е aRb →bRa, Симметричность доказана.
, Следовательно aRc, ч.т.д.
iIMi =M, Mi
Mj=
для всех i, j I ,где I — множество классов.
y = x),
и т. д.
.
Новости и инфо для студентов