Прямое произведение множеств. Бинарные отношения. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Пусть ...
Пусть и - произвольные элементы. Из элементов и можно образовать двухэлементное множество . Порядок указания элементов в этом множестве может быть любым. В целом множество остаётся тем же: . Определим упорядоченную пару , в которой - первая компонента, а – вторая. Если , то , т.к. для упорядоченной пары первая компонента – , а вторая – .
Определение 1: Прямым или декартовым произведением множеств и называется множество всех упорядоченных пар, таких, что первая компонента принадлежит множеству , а вторая – множеству . Другими словами:
.
Например, пусть , . Тогда . Упорядоченная пара может принадлежать или не принадлежать прямому произведению. Например, пара , а другая пара .
В общем случае, когда , прямое произведение не коммутативно:
.
Число упорядоченных пар, входящих в прямое произведение, можно посчитать следующим образом. Если – конечное множество, содержащее элементов, а – конечное множество, содержащее элементов, то их прямое произведение содержит элементов.
Прямым произведением можно также перемножать три и более множеств. Пусть А, В, С - произвольные множества, тогда их прямое произведение – это множество упорядоченных троек:
.
Пусть - произвольные множества. Тогда их прямое произведение имеет вид:
.
В частном случае можно рассматривать прямое произведение , которое называется декартовым квадратом множества и обозначается . Например, каждая точка на плоскости имеет две действительные координаты, значит, множество точек плоскости можно обозначить и рассматривать декартов квадрат: . По аналогии: - множество точек пространства.
Аналогично определяется - я декартова степень множества :
.
В частности – есть n-мерное пространство; – единичный куб n-мерного пространства. Если – окружность радиуса 1, то – поверхность цилиндра, – поверхность тора.
Пусть - произвольные множества, - их прямое произведение.
Определение 2: Всякое подмножество прямого произведения называется - местным (или - арным) отношением на множествах . Обозначают: .
Замечание: Если - это отношение, то по определению: .
При отношение называется унарным ().
При отношение называется бинарным ().
При отношение называется тернарным () и т. д.
Особый интерес представляют бинарные отношения, которые будут рассмотрены ниже более детально.
Определение 3:Бинарным отношением между элементами множеств и называют всякое подмножество прямого произведения . Пишут: . При этом само множество называют универсальным бинарным отношением. Всякое бинарное отношение между элементами множеств и является подмножеством универсального множества.
Таким образом, бинарные отношения состоят из упорядоченных пар элементов некоторых множеств. Если некоторая пара принадлежит бинарному отношению, т. е. , то говорят, что элемент находится в отношении с элементом . Можно встретить такое обозначение: (читается: находится в отношении с элементом ).
Замечание: При задании бинарного отношения обязательным является указание множества, на котором это отношение рассматривается.
Например, рассмотрим некоторые бинарные отношения на множестве всех натуральных чисел . Пусть , тогда , где . На это множестве, как и на любом числовом множестве, можно рассматривать отношения: <, >, =.
На множестве всех прямых плоскости можно рассмотреть отношение параллельности.
Определение 4: Пусть - бинарное отношение на множествах и . Множество всех , таких, что , называется областью определения бинарного отношения (или первой проекцией бинарного отношения).
Согласно определению: - это множество всех первых элементов пар, принадлежащих .
Определение 5:Вторая проекция бинарного отношения (или множество значений отношения ) – это множество, состоящее из вторых компонент упорядоченных пар, принадлежащих отношению . Обозначают: .
Из последних определений видно, что , .
Для наглядности восприятия бинарных отношений их можно изображать на плоскости в виде графиков и в виде графов.
Определение 6: График бинарного отношения - это множество точек плоскости таких, что .
Таким образом, графиком бинарного отношения является некоторая область в плоскости . Область определения отношения - это проекция на ось , а множество значений - проекция на ось .
Все темы данного раздела:
ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
(для студентов специальности «Прикладная математика»,
«Информатика», «Системный анализ»,
«Компьютерные системы и сети»)
Представление бинарных отношений графами.
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй.
Отметим, что теория решеток и теория булевых алгебр – это самостоятельные разделы алгебры.
Определение 8: Линейно упорядоченное множество, удовлетворяющее условию мини
Мощность множества. Сравнение мощностей.
Пусть даны конечные множества и , число элементов которых равно
Определение 2: Множества, обладающие одинаковой мощностью, называются равномощными (эквивалентными).
Два конечных множества будут равномощными, если в них содержится одинаковое число элементов. Если имеем дело с бесконечными множествами, то вопросы, связанные с мощностями, решаются путём установле
Определение 3: Множество, эквивалентное множеству чисел натурального ряда, называется счетным.
Натуральный ряд чисел – это счётное множество. Все множества, равномощные множеству , имеют такую же мощность.
Теорема 4:
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Определение 3: Если два линейно упорядоченных множества изоморфны, то их называют подобными множествами.
Подобие для линейно упорядоченных множеств - есть бинарное отношение между линейно упорядоченными множествами, являющееся отношением эквивалентности. Фактор-множество по этому отношению эквивалентн
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Отрицание – обозначается ,читается:«не » или «неверно, что ».
2) Дизъюнкция (логическое сложение), обозначаемое(читается «и
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Определение 3: Множество всех значений таких, что предикат при этих значениях принимает значение «истина», называется областью истинности предиката.
Определение 4: Предикат , определённый на множестве , называе
Формулы и тавтологии логики предикатов.
При введении определения формул логики предикатов будем использовать следующие обозначения (алфавит):
1) – индивид
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Предикатов. Свойства теорий первого порядка.
Для записи формул логики предикатов используется следующий алфавит: скобки, запятые, символы исчисления высказываний (отрицание
Задачи для самостоятельной работы.
1.Определить истинность следующих высказываний, если , ,
Определение формулы и суперпозиции.
Пусть имеется счетное множество переменных , где
Принцип двойственности.
Пусть – некоторое подмножество множества булевых функций: .
Линейные функции. Монотонные функции.
Рассмотрим систему функций:
, ,
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Задачи для самостоятельной работы.
1) Сколько имеется различных двоичных наборов длины ?
2) Сколько имеется
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.
Очевидно, что множество, содержащее более одного элемента, можно упорядочить не единственным способом.
Например, из двух букв и
Определение 8: Конечные упорядоченные множества называются размещениями.
Теорема 3: Количество всех размещений из элементов по элемен
Определение 10: Конечные неупорядоченные множества называются сочетаниями.
Таким образом, сочетания – это такая выборка элементов, при которой их порядок совершенно не важен.
Сочетаний из элементов по
Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Определение 2: Группы, составленные из объектов, которые принадлежат одному из типов элементов, называют сочетаниями с повторениями.
Число всевозможных сочетаний с повторениями обозначают следующим символом: .
Сочетания с повторениями, как было показано в примере
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Новости и инфо для студентов