Реферат: Основные положения дискретной математики

Пример №1

Доказать тождество:

.

Решение:

1) ;

2) .

1.5 Отношения на множествах

Отношения бывают одноместными, двуместными (бинарными) и n-местными. Одноместное отношение– это просто подмножество. Мы остановимся на бинарных отношениях.

1. упорядоченная пара (x, y) есть совокупность двух элементов записанных в определенном порядке.

2. Две пары (x, y) и (x₁ , y₁ ) считаются равными тогда и только тогда x₁ = х, y₁ = y.

3. Прямым произведением xy называется совокупность пар (x,y)таких, что .

Можно привести следующие примеры бинарных отношений:

· Отношение «иметь общий делитель отличный от 1» выполняется для пар (6,9); (4,2); (2,4); (4,4), но не выполняется для пар (7,9); (4,7).

· Отношение «быть делителем», т. е. x делит y выполняется для пар (2,4); (4,4), но не выполняется для пар (4,2); (7,9).

· Отношение выполняется для пар (7,9); (7,7), но не выполняется для пары (9,7).

1.6 Свойства отношений

1. Рефлексивность;

2. Симметричность;

3. Транзитивность.

Отношение обозначается R и записывается так: xRy (x и y находятся в отношении R).

Отношение 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 – условие выполняется , следовательно данное отношение рефлективно.