Материал: Методические указания по выполнению лабораторных работ по дисциплине Дискретная математика для студентов специальности 230101. Леденева Т.М., Недикова Т.Н

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

Задачи для самостоятельного решения

1. Для каждого из следующих отношений, заданных на множестве натуральных чисел перечислите упорядоченные пары, принадлежащие отношениям:

а) ,

б) ,

в) .

2. Пусть - отношение на множестве , определенное условием: тогда и только тогда, когда - нечетное число. Представьте каждым из способов:

а) как множество упорядоченных пар,

б) в виде матрицы,

в) соответствующим графом.

3. Определите область определения и множество значений отношений

а) ,

б) ,

в) .

4. Найдите , если

а) ,

б) .

5. Пусть заданы следующие бинарные отношения и . Найдите отношения .

6. Пусть , а - отношения на множестве , определенные следующим образом:

,

,

,

.

Найдите , .

7. Пусть бинарные отношения определены следующим образом , . Опишите отношения

а) , б) , в) , г) .

8. Для отношений и из уравнения найдите наименьшее отношение , если и

Основные типы отношений

Ключевые слова: рефлексивность, симметричность, транзитивность, отношение эквивалентности, фактор-множество, отношение частичного порядка, диаграмма Хассе.

Задача 3.1. Определите свойства отношения , матрица которого имеет вид

.

Решение. Заметим, что на главной диагонали матрицы стоят все единицы, следовательно, рефлексивное отношение, т.е. . Матрица несимметрична, тогда несимметрично отношение . Проверим антисимметричность. Для этого найдем

.

Так как не все элементы, стоящие вне главной диагонали, нулевые, то отношение не является антисимметричным. Проверим транзитивность.

Вычислим

.

Так как , то отношение нетранзитивно.

Задача 3.2. Докажите, что если и - симметричные отношения, то также симметричное отношение.

Решение. Чтобы доказать симметричность, рассмотрим элемент и покажем, что элемент также принадлежит этому отношению. Итак,

,

что и требовалось доказать.

Задача 3.3. Пусть отношение задано следующим образом:

.

Определите свойства этого отношения.

Решение. Отношение рефлексивно, так как если , то для , и, следовательно .

Отношение симметрично. Предположим, что , тогда существует целое число такое, что и

для целого числа . Таким образом, .

Проверим транзитивность . Предположим, что - целые числа и и . По определению

, тогда для некоторого целого числа ,

, тогда для некоторого целого числа .

Суммирование левых и правых частей этих двух равенств дает

для некоторого целого числа . По определению , поэтому транзитивно. Поскольку рефлексивно, симметрично и транзитивно, то оно является отношением эквивалентности.

Найдем классы эквивалентности . Класс эквивалентности, порожденный элементом в данном случае определяется следующим образом:

=

.