Мощность множества. Сравнение мощностей. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Пусть Даны Конечные Множества ...
Пусть даны конечные множества и , число элементов которых равно и соответственно. В зависимости от величин и , возможны следующие ситуации:
, , .
Какое из этих соотношений имеет место, можно решить двумя способами. Можно пересчитать число элементов каждого из множеств и сравнить полученные числа. А можно сравнить два множества путем установления взаимно однозначного соответствия между их элементами.
Определение 1: Назовем два множества эквивалентными, если существует взаимно однозначное соответствие между их элементами.
Обозначают: . Определенное нами бинарное отношение эквивалентности между множествами обладает свойствами:
1) рефлексивность: ,
2) симметричность: из того, что следует, что ,
3) транзитивность: если и , то , т.е. действительно является эквивалентностью.
Таким образом, всевозможные множества распадаются на классы эквивалентных между собой множеств. В один класс эквивалентности попадают множества, состоящие из одного и того же числа элементов.
Поставим в соответствие каждому классу эквивалентных между собой множеств некоторый символ , который назовем кардинальным числом или мощностью любого из множеств данного класса.
Например, линейная функция устанавливает взаимно однозначное соответствие между точками интервала и точками интервала для любого . Функция устанавливает взаимно однозначное соответствие между всеми точками интервала и точками прямой линии .
Замечание: Понятие мощности для конечного множества совпадает с понятием числа элементов этого множества. Кардинальное число – это количество элементов во множестве.
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Фесенко Т Н...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Мощность множества. Сравнение мощностей.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Представление бинарных отношений графами.
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов