- •Математика
- •Пересечение множеств
- •Вычитание множеств
- •Свойства операций над множествами
- •Число элементов в объединении конечных множеств и в дополнении к подмножеству
- •Контрольные вопросы:
- •Способы задания декартова произведения двух множеств
- •Основные свойства декартова произведения.
- •Раздел II. Элементы комбинаторики
- •Контрольные вопросы:
- •Контрольные вопросы:
- •Перестановки без повторений
- •Бином Ньютона
- •Свойства сочетаний. Треугольник Паскаля.
- •1. Правило симметрии:
- •Раздел III. Математические утверждения и их структура
- •Контрольные вопросы:
- •Отношения между понятиями
- •Способы определения понятий
- •Требования к определению понятий
- •Контрольные вопросы:
- •Высказывания и операции над ними
- •Операции над высказываниями
- •Отрицание высказываний
- •Законы отрицания:
- •Конъюнкция двух высказываний
- •Импликация высказываний
- •Закон контрапозиции
- •Эквиваленция двух высказываний
- •Обращение предиката в высказывание
- •Операции над предикатами
- •Отрицание высказываний, содержащих кванторы
- •Отношение логического следования и равносильности на множестве предложений
- •Строение теоремы. Виды теорем
- •Закон контрапозиции. Теоремы
- •Умозаключения. Анализ рассуждений. Простейшие правила вывода
- •Простейшие схемы дедуктивных умозаключений
- •Способы установления истинности умозаключения
- •Индуктивные умозаключения
- •Раздел IV. Соответствия
- •Контрольные вопросы:
- •Полный образ и полный прообраз
- •Способы задания соответствий
- •Типы соответствий
- •Отображения
- •Виды отображений
- •Отношения
- •Свойства отношений на множестве
Отношения
Пусть F= <X,Y,Gf >, где Gf - соответствие между элементами Х иY.
Определение: Если Х=Y, то F=<X,X,Gf > называется отношением на множестве Х.
Другими словами, отношение на множестве X это соответствие между элементами одного и того же множества.
Из определения отношения на Х следует , что отношение – это частный случай соответствия. Следовательно, все понятия, которые имеют место для соответствий, имеют место и для отношений, но есть и особенности.
Особенности, присущие отношениям:
1) область отправления и область прибытия совпадают;
2) DF X;
3) EF X (а для общего случая соответствий: ЕFY);
4) GF = {(x,y)/xX, yX, xFy }.
Способы задания те же, что и для соответствий, но граф отношения на Х- однодольный (Х = Y), доля не рисуется , элементы обозначаются точками и называются вершинами графа .Факт вступления элементов в отношение обозначается стрелкой. Если элемент вступил в отношения сам с собой, то в вершине рисуется петля.
Пусть Х = {a,b,c}. Отношение F между элементами множества X задано при помощи графа:
Тогда область отправления отношения F: Х, область прибытия :Х.
a b c
Область определения DF = {a,с}X;
множество значений EF = {a,b}X.
График отношения GF = {(a,a),(c,b)} X2.
Задание – самостоятельно перечислить все способы задания отношения.
Свойства отношений на множестве
Пусть F=<X, X, GF >, где GF X2 – отношение на множестве Х.
GF = {(x,y)| xX, yX, xFy}.
Определение: Отношение на множестве Х называется рефлексивным, если всякий элемент xX вступает в это отношение сам с собой:
(xX) [xFx]- «и»
Особенности графа: в каждой вершине графа рефлексивного на множестве Х отношения - петля.
Особенности графика: графику рефлексивного отношения принадлежат все пары вида (х,х): (xX) (x; x).
Определение 2: Отношение F на множестве Х называется антирефлексивным, если ни один элемент множества Х не вступает в отношения F сам с собою:
(хХ)[ ]-«и».
Особенности графа: ни в одной вершине графа нет петли.
Особенности графика: графику не принадлежит ни одна пара с равными компанентами (вида (х,х)): (xX) (x; x).
Примеры: отношение равенства на множестве множеств; не меньше; не больше на числовом множестве; параллельности на множестве прямых и т.д. – рефлексивные отношения. Отношения неравенства; больше; меньше на числовых множествах; перпендикулярности на множестве прямых и др. – антирефлексивные отношения.
Рассмотрим отношение, заданное на множестве людей: «быть отцом».
Является ли оно рефлексивным? Нет, так как ни один человек не может быть отцом самому себе. Стало быть, оно антирефлексивное.
Определение 3: Отношение F на множестве Х называется симметричным, если для любых элементов х,уХ истинно утверждение: если элемент x вступил в отношение F c элементом y (хFy), то и элемент y вступил в данное отношение с элементом x (уFx):(х,уХ)[xFyyFx] – «и».
Особенности графа: граф симметричного отношения содержит только двойные стрелки или никаких.
Особенности графика: если графику принадлежит пара (х,у), то и пара (у,х) принадлежат этому графику: (x,yX) [(х,у) GF (y,x) GF].
Примеры: отношения равенства на множестве множеств и на числовом множестве; отношения параллельности и перпендикулярности на множестве прямых; отношение «быть родственником» на множестве людей и др.
Определение 4: Отношение F на множестве Х называется асимметричным, если для любых двух элементов х и у множества Х верно утверждение: если элемент хX вступает в отношение F с элементом у, то неверно, что элемент у вступает в отношение F c элементом х этого же множества: (x,yX) [xFy]-«и».
Другими словами: ни для каких элементов х и уХ; не может быть одновременно xFy u yFx.
Особенности графа: все стрелки графа асимметричного отношения одинарные и ни в одной вершине нет петель!
Особенности графика: (x,yX) если (х,у) GF, то (у,х) GF.
Примеры: отношения «>»; «<»; «толще» и т.д. являются асимметричными.
Определение 5: Отношение F на множестве Х называется антисимметричными, если для любых двух различных элементов х и у из множества Х истинно утверждение: если хХ вступает в отношение F с элементом у, то у не вступает в отношение F с элементом х .
Итак, F- антисимметрично (x,yX) (x ≠ y) [xFy=>].
Особенности графа: граф антисимметричного отношения содержит только одинарные стрелки и могут быть петли.
Особенности графика: (x,yX)если (x,y)GF, то (у,х) GF, и (x,x)GF
Замечание: асимметричное отношение - это одновременно антисимметричное и антирефлексивное отношение.
Определение 6: Отношение F на множестве Х называется транзитивным, если для любых трех элементов множества Х справедливо утверждение: если элемент х находится в отношении F с элементом y, а элемент y находится в отношении F с элементом z, то элемент х вступит в отношение F с элементом z: (xFy)Λ(yFz)=>(xFz).
Таким образом, F –транзитивно (x,y,zX)[xFyyFzxFz].
Особенности графа: граф транзитивного отношения с каждой парой стрелок идущих от х к у и от у к z, содержит стрелку от х к z.
Особенности графика: если (x,y)GF (y,z)GF то (х,z)GF.
Пример 1: отношение параллельности на множестве прямых является транзитивным: (aв)(вс) (ac) для любых (a,в,с) из множества прямых на плоскости.
Пример 2: отношение «>» на множестве действительных чисел:
(х > y)(y > z) (x > z)(x,y,zR).
Определение 7: Отношение F на множестве Х называется антитранзитивным, если для (х,у,zX) верно утверждение: если элемент х находится в отношении F с элементом y, а элемент y находится в отношении F с элементом z, то элемент х не вступает в отношение F с элементом z: [xFyyFz=>].
Таким образом, F- антитранзитивно (x,y,zX)[xFyyFz=>].
Особенности графа: если граф содержит стрелку от х к у и у к z, то не содержит стрелку от х к z.
Особенности графика: если (x,y)GF (y,z)GF то (х,z) GF.
Пример 1: отношение перпендикулярности на множестве прямых антитранзитивно.
а
в с
Определение 8: Отношение F на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.
Пример: отношение равенства на множестве чисел, отношение параллельности на множестве прямых, отношение равенства на множестве множеств, отношение подобия на множестве фигур являются отношениями эквивалентности.
Отношение эквивалентности связано с разбиением множества на классы.
Теорема: Для того, чтобы отношение R позволяло разбить множество X на попарно непересекающиеся классы, необходимо и достаточно, чтобы R было отношением эквивалентности.
Доказательство смотри стр 174 учебника ч.1 (Охременко Д.В., Тонких А.П.)
Пример: Пусть X = {x׀xN, x < 12}. Зададим отношение F: x и у делятся на 5 с одинаковым остатком.
Является ли оно отношением эквивалентности? Если да, то задайте классы эквивалентности. Укажите граф.
Данное отношение рефлексивно, симметрично, транзитивно. Следовательно, оно является отношением эквивалентности и производит разбиение множества Х на классы эквивалентности.
1:5=0(ост.1) 6:5=1(ост.1) 11:5=2(ост.1)
2:5=0(ост.2) 7:5=1(ост.2)
3:5=0(ост.3) 8:5=1(ост.3)
4:5=0(ост.4) 9:5=1(ост.4)
5:5=1(ост.0) 10:5=2(ост.0)
Тогда Х1 = {1,6,11} X2 = {2,7} X3 = {3,8} X4 = {4,9} X5 = {5,10}.
Все условия разбиения множества на классы выполнены:
XiXj = Ǿ (i,jN) X1X2X3X4X5 = X.
1 2 4 5 6 7 8 9 10 11 3
Отношение порядка. Упорядоченные множества
Пусть на множестве Х задано отношение F.
Определение 9: Отношение F на множестве Х называется отношением строгого порядка, если оно асимметрично и транзитивно.
Из определения следует, что если
Другими словами, если отношение F
1)антирефлексивно
2)антисимметрично то F - отношение строгого порядка.
3)транзитивно
Например, отношение «>», «<», «выше», «уже» и другие являются отношениями строгого порядка.
Определение 10: Отношение F на множестве Х называется отношением нестрогого порядка,если оно рефлексивно, антисимметрично и транзитивно.
Из определения следует, что, если
1
2)(x,yX)(x ≠ y)[xFy] F – отношение нестрогого порядка.
3)(x,y,zX)[xFy yFzxFz]
Например, отношение «≤», «≥», «не выше», «не старше» и другие являются отношениями нестрогого порядка.
Особенности графов:
граф отношения строгого порядка – не содержит петли, все стрелки одинарные, все треугольники стрелок замкнуты.
2) граф нестрогого порядка – содержит петли в каждой вершине, все стрелки одинарные, все треугольники стрелок замкнуты.
Определение: Множество Х называется упорядоченным или линейно упорядоченным, если:
а) на множестве Х задано отношение порядка F=<X,X,G>;
б) любые два различных элемента x и y множества Х находятся в данном отношении, т.е. имеет место либо хFу, либо уFх. Это говорит о том, что на графе нет ни одной пары элементов, между которыми не было бы стрелки.
Пример: Пусть А = {Ваня, Коля, Саша, Олег, Игорь}. Отношение: F:«х прыгнул дальше y» задано графом:
В
К
О
С
И
Является ли множество А линейно упорядоченным?
Анализируя граф данного отношения, будем иметь:
1) F –антирефлексивно, т.к. ни в одной вершине графа нет петли;
2) F – антисимметрично, т.к все стрелки одинарные;
3) F- транзитивно.
Следовательно, F – отношение строго порядка, но оно не упорядочивает множество А т.к. не все элементы множества А связаны друг с другом . В этом случае говорят о частичном порядке.