Основные положения дискретной математики (стр. 2 из 11)

Отношение R называется рефлективным, если для любого

имеет место aRa. Главная диагональ его матрицы содержит только единицы.

Отношение R называется антирефлективным, если для любого

не выполняется aRa. Главная диагональ его матрицы содержит только нули. Отношения = - рефлективные, а отношение < - антирефлективное.

Отношение R называется симметричным, если для пары (а,в)

из aRb следует bRa, иначе говоря для любой пары отношение выполняется либо в обе стороны, либо не выполняется вообще. Матрица данного отношения симметрична относительно главной диагонали.

Отношение R называется транзитивным, если для любых a,b,c из aRb и bRс следует aRс отношения

= - транзитивны, отношение «пересекаться» – нетранзитивно. (Пример: пересекается с пересекается с , однако и не пересекаются).

Задание №2

Установите какими свойствами обладает каждое из отношений, заданных на R следующими высказывательными формами:

a) x+y=2;

Решение:

в данном случае заданы отношения + и

.

Подставим в выражение x+y=2 конкретные значения: 1+1=2, последовательно проверим каждое свойство:

Рефлективность: aRа = а+а = 1+1 – условие выполняется , следовательно данное отношение рефлективно.

Симметричность: из aRb следует bRa = из а+b следует b+а = из 1+1 следует 1+1 – условие выполняется, следовательно данное отношение симметрично.

Транзитивность: из aRb и bRс следует aRс данное условие мы проверит не можем, т. к. оно применимо только для трех или более элементов.

1.7 Декартово произведение множеств

Декартовым произведением – X

Y множеств X и Y называется множество М вида

В круглых скобках обозначена последовательность, т. е. множество, в котором зафиксирован порядок элементов.

Подмножество F

X Y называется функцией, если для каждого элемента x X, найдется не более одного элемента y Y вида (x,y) F; при этом, если для каждого элемента х имеется один элемент y вида (x,y) F, то функция называется всюду (полностью) определенной, в противном случае – частично определенной (не доопределенной).

Множество Х образует область определения функции F.

Множество Y образует область значений функции F.

Часто вместо (x,y)

F пишут у=F(х), при этом элемент х называется аргументом или переменной, а у – значением функции F.

Сопоставим с декартовым произведением двух множеств х=

. и у= . прямоугольную решетку, узлы которой взаимно однозначно соответствуют элементам декартова произведения (рис.5).

Подмножества декартова произведения обозначены штриховкой соответствующих элементов.

На рис.5 а) показано подмножество декартова произведения не являющееся функцией.

На рис.5 б) показано подмножество декартова произведения, являющееся полностью определенной функцией.

На рис. 5 в) показано подмножество декартова произведения, являющееся частично определенной функцией.

Количество аргументов определяет местность функции. До настоящего момента были рассмотрены одноместные функции.

Аналогично понятию декартова произведения двух множеств можно определить понятие декартова произведения n-множеств.

Декартовым произведением

множеств М₁, М₂,…., М_n называется множество Элементами декартова произведения являются всевозможные последовательности, каждая из которых состоит из n элементов, причем первый элемент принадлежит множеству М₁, второй – множеству М₂, n-ый – множеству М_n.

Если множество М_х в определении функции у=F(x) является декартовым произведением множеств М _х1, М _х2,…., М _хn, то получаем определение n-местной функции у=F(х₁, х₂,….,х_n).

1.8 Функция как отношение

Функцией называется функциональное соответствие.

Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция f имеет тип А

В, обозначается f: А В. каждому элементу а из своей области определения функция f ставит в соответствие единственный элемент b из области значений. Обозначается f(a)=b.

Элемент а называется аргументом функции, элемент b называется значением функции на а.

Полностью определенная функция f: A

B называется отображением А и В.

Областью определения называется выражение D=

Функция называется инъективной, если из отношений (x₁,y)f, (x₂,y)f

x₁=x₂

Функция называется сюръективной, если для каждого у

Y существует х Х.

Инъективная и сюръективная функции образуют биекцию – это взаимнооднозначное отношение множеств.

1.9 Отношение порядка

Отношение называется отношением нестрогого порядка, если оно рефлективное, антисимметрично, транзитивно.

Отношение называется отношением строгого порядка, если оно антирефлективное, антисимметрично, транзитивно. Оба типа отношений называются отношениями порядка.

Элементы a,b сравнимы по отношению порядка, если выполняется aRb или bRa. Множество М, на котором задано отношение порядка называется полностью упорядоченным, если любые два элемента множества М сравнимы, в противном случае – частично упорядоченным.

Пример: отношения

для чисел являются отношениями нестрого порядка, отношения <,> - отношения строгого порядка. Оба отношения полностью упорядочивают множество. Отношение строгого включения задает строгий частичный порядок: .

Отношение эквивалентности

Отношение называется отношением эквивалентности (эквивалентностью), если оно одновременно рефлективно, симметрично и транзитивно.

Примеры:

1. отношение равенства на любом множестве является отношением эквивалентности;

2. утверждение вида (a+b)(b-a)=a²-b² – формулы соединенные знаком равенства задают бинарное отношение. Такое отношение называют отношением равносильности. Оно отличается от равенства, т. к. может выполняться для различных формул.

3. Отношение подобия геометрических фигур, «быть соседями по квартире», «быть ровесниками» так же являются отношениями эквивалентности.

Каждое отношение эквивалентности является в определенном смысле равенством, например, отношение «быть ровесником» означает равенство возрастов.

Задание №3

Какие из перечисленных отношений являются отношениями эквивалентности, а какие – отношениями порядка: <,

(на множестве действительных чисел), предшествовать (на множестве слов в словаре), быть однофамильцем (на множестве учащихся в данном вузе).

Решение: необходимо проверить каждое из свойств отношений (аналогично заданию №2) и определить эквивалентность или порядок отношений.

2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

Модель является отображением чего-либо. В науке о природе моделирование используется как метод познания.

2.1 Преобразование к модели

1. Эксперимент на модели должен быть проще эксперимента на оригинале.

2. Информация об объекте, полученная в результате эксперимента на модели должна быть переносима на объект.