Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств
Конечные, счетные, континуальные множества. Мощность булеана
жүктеу/скачать 318 Kb.
|
1. Теория множеств
- Бұл бет үшін навигация:
- Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.
| Конечные, счетные, континуальные множества. Мощность булеана.
Если А~n для некоторого , т.е. А имеет ровно n элементов, то множество А называется конечным (|A|=n). Множество, не являющееся конечным, называется бесконечным. Если А~ω, то множество А называется счетным: |A|=ω. Если А~2ω, то множество А называется континуальным или континуумом: |A|=2ω. Мощности множеств также иногда называют кардинальными числами. Мощность булеана: |P(U)|=2|U| для любого множества U. Доказательство: Установим биекцию между Р(U) и 2А Любому подмножеству А из U взаимно однозначно ставим в соответствие функцию , для которой т.е. P(U)~2U. Заметим, что 2|U|=|2U|. Матрицы бинарных отношений и их свойства. Специальные бинарные отношения. Рассмотрим два конечных множества А={a1, a2,…, am}, B={b1, b2,…, bn} и бинарное отношение . Определим матрицу [P]=(pij) размера бинарного отношения Р по следующему правилу: Полученная матрица содержит полную информацию о связях между элементами. Основные свойства матриц бинарных отношений: Если , [P]=(pij), [Q]=(qij), то и , где сложение осуществляется по правилам 0+0=0, 1+1=1+0=0+1=1, а умножение – обычным образом. Если , , то , где умножение матриц [P] и [Q] производится по обычному правилу умножения матриц, но произведение и сумма элементов по определенным в п.1 правилам. Матрица обратного отношения Р-1 равна транспонированной матрице отношения P: [P-1]=[P]T. Если , [P]=(pij), [Q]=(qij), то pij≤qij. Матрица тождественного отношения idA единична: [idA]=E. Специальные бинарные отношения: Пусть Р – бинарное отношение на множестве А: Отношение Р называется рефлексивным, если для всех выполняется , т.е . Отношение Р называется симметричным, если для любых из следует , т.е Р-1=Р, или [P]T=[P]. Отношение Р называется антисимметричным, если из и следует, что x=y, т.е , или на языке матриц это означает, что в матрице все элементы вне главной диагонали являются нулевыми. Отношение Р называется транзитивным, если из и следует , т.е жүктеу/скачать 318 Kb. Достарыңызбен бөлісу:
|