- •Математика
- •Пересечение множеств
- •Вычитание множеств
- •Свойства операций над множествами
- •Число элементов в объединении конечных множеств и в дополнении к подмножеству
- •Контрольные вопросы:
- •Способы задания декартова произведения двух множеств
- •Основные свойства декартова произведения.
- •Раздел II. Элементы комбинаторики
- •Контрольные вопросы:
- •Контрольные вопросы:
- •Перестановки без повторений
- •Бином Ньютона
- •Свойства сочетаний. Треугольник Паскаля.
- •1. Правило симметрии:
- •Раздел III. Математические утверждения и их структура
- •Контрольные вопросы:
- •Отношения между понятиями
- •Способы определения понятий
- •Требования к определению понятий
- •Контрольные вопросы:
- •Высказывания и операции над ними
- •Операции над высказываниями
- •Отрицание высказываний
- •Законы отрицания:
- •Конъюнкция двух высказываний
- •Импликация высказываний
- •Закон контрапозиции
- •Эквиваленция двух высказываний
- •Обращение предиката в высказывание
- •Операции над предикатами
- •Отрицание высказываний, содержащих кванторы
- •Отношение логического следования и равносильности на множестве предложений
- •Строение теоремы. Виды теорем
- •Закон контрапозиции. Теоремы
- •Умозаключения. Анализ рассуждений. Простейшие правила вывода
- •Простейшие схемы дедуктивных умозаключений
- •Способы установления истинности умозаключения
- •Индуктивные умозаключения
- •Раздел IV. Соответствия
- •Контрольные вопросы:
- •Полный образ и полный прообраз
- •Способы задания соответствий
- •Типы соответствий
- •Отображения
- •Виды отображений
- •Отношения
- •Свойства отношений на множестве
Полный образ и полный прообраз
Рассмотрим в соответствии R = <X,Y,GR>, где GR XY все пары вида (a; у), где и , для которых верно аRу.
Множество всех таких у из множества Y, для которых верно аRy, назовём полным образом элемента а Х в соответствии R между элементами множеств Х иY.
X Y
Y1
Y2
Y3
Пусть у=bY. Расмотрим все пары вида (х,b) для которых верно хRb. Тогда множество таких х из множества Х, для которых верно хRb, назовём полным прообразом элемента b соответствии R между элементами множеств Х и Y.
X Y
X1
X2
X3
X4
В примере 1 полный прообраз элемента 4 состоит из одного элемента: 2; полный образ элемента 3 состоит из одного элемента: 9.
Способы задания соответствий
1) по определению бинарное соответствие будет задано, если будут заданы множества Х,Y, и GR - это самый общий способ задания cоответствия;
2) соответствие может быть задано своим графиком: GR = {(x,у)| хХ, уR ,хRy}. График соответствия может быть задан перечислением элементов или указанием характеристических свойств;.
3) если множества Х иY конечные, то соответствие между элементами этих множеств может быть задано с помощью графа:
X R Y
4) с помощью таблицы, если множества Х и Y-конечные;
Х У |
4 |
9 |
2 |
|
|
3 |
|
|
5 |
|
|
5) соответствие может быть задано графически на плоскости , если множества Х и Y-числовые.
В примере 1
9 М2 М1 (2;4).
М2(3;9).
4 М1
2 3 5
6) с помощью двухместного предиката, то есть предложения с двумя переменными, выражающего факт вступления элементов в соответствие.
R(х; у): хRy, хХ, у Y
R(x; у): «x – делитель y», х Х , у Y .
Рассмотрим между элементами множеств Х = {2; 3; 4} и Y = {5; 6; 8} соответствие R: х - делитель у. Тогда Х - область отправления соответствия, Y- область прибытия. Область определения соответствия: ДR = {2,3,4}, множество значений соответствия: ЕR = {6;8}.
Пусть соответствие между элементами множеств X и Y задано при помощи графа.
X R Y
.
Тогда полный образ элемента 2состоит из двух элементов: 6 и 8:
R(2) = {6;8}; R(3) = {6}; R(4) = {8}. R(7) – пуст.
Полный прообраз элемента 5 пуст; ; .
Типы соответствий
Пусть R = <X,Y,GR>, где GR XY и GR = {(x,у)| хХ, yY, хRy}.
Определение: Если множество GR (график соответствия R между элементами множеств X иY) совпадает с множеством , то это соответствие называется полным.
Пример: X = {1,2,3} Y = {5,7,8}. R(x; y): х < y.
ХY = {(1,5),(1,7),(1,8),(2,5),(2,7),(2,8),(3,5),(3,7),(3,8)}
GR = {(1,5),(1,7),(1,8),(2,5),(2,7),(2,8),(3,5),(3,7),(3,8)}.
Тогда GR =. Следовательно, R- полное соответствие.
Определение: Если график соответствия R между элементами множеств Х и Y-есть пустое множество (GR = Ǿ }, то такое соответствие называется пустым.
Пример: X = {1,2,3} Y = {5,7,8}. R(x; y): х > y.
Очевидно, GR = Ǿ = > R- пустое соответствие.
Определение: Соответствия F и R между элементами множеств X и Y называется противоположными, если их графики являются дополнениями друг друга до множества ХY, то есть GFGR = Ǿ и GFGR = ХY => F и R - противоположные.
Если соответствие F задано предикатом F(x,у), то противоположное ему соответствие задаётся предикатом, который есть отрицание предиката F(x,у).
Пример : X = {1,2,3}, Y = {5,7,8}.
Пусть F(x,у): х < y. Тогда : х y – противоположное ему соответствие . Очевидно, G = Ǿ, а G = {(1,5),(1,7),(1,8),(2,5),(2,7),(2,8),(3,5),(3,7),(3,8)}. Они являются противоположными соответствиями.
Определение: Соответствия F и R между элементами множеств Х и Y называются несовместимыми, если GF∩GR = Ǿ.
Это значит, что нет ни одной пары (х,у), для которой одновременно выполняются условия хFy и хRy.
Ясно, что противоположные соответствия, можно называть несовместимыми, а наоборот - нельзя.
Определение: Если график соответствия F между элементами множеств Х иY является подмножеством графика соответствия R между элементами множеств Х иY ( то есть GFGR), то соответствие R называется следствием соответствия F.
Пример 1: Х - множество треугольников плоскости.
F: ∆ х = ∆у.
R: ∆ х ~ ∆y.
GF GR => R - следствие соответствия F.
Пример 2: X = {1, 2, 3}
Y = {2, 3, 5}
F: х y. Тогда GF = {(1,2),(1,3),(1,5),(2,2),(2,3),(2,5),(3,5)}.
R: х < y. GR = {(1,2),(1,3),(1,5),(2,3),(2,5),(3,5)}.
GR GF => F- следствие соответствя R.
Определение: Обратным к соответствию R = <X,Y,GR> между элементами множеств X и Y называется такое соответствие между элементами множеств Y и X , при котором тогда и только тогда, когда .
Граф обратного соответствия получается из графа данного соответствия путём замены стрелок на противоположные.
Пусть GR – график данного соответствия между элементoв множества Х и Y, тогда, чтобы построить график обратного соответствия R-1 между элементoв множества Y и Х, надо поменять местами компоненты пар.