Элементы математической логики. Отношения

Унарные отношения

Отношения – один из способов задания взаимосвязей между элементами множества.
Унарные

Бинарные (двухместные отношения) используются для определения каких-либо взаимосвязей, которыми характеризуются пары

n-местное отношение

Бинарные отношения

Пример. Пусть . Рассмотрим отношение R⊆ A × A ,

Область определения и область значений

Область определения D(x) - это множество значений

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

Способы задания отношений

2. Характеристическим свойством.
Например,

3. Графически.

Например, R ={(1,5), (2,4), (3,6),

Способы задания отношений

Пример. R ={(1,5), (2,4), (3,6), (6,2)} на R⊆ Х2,
Х =

Способы задания отношений

Матрица отношения будет иметь вид:

Способы задания отношений

Способы задания отношений

Способы задания отношений

Способы задания отношений

4.

на рис.

Рассмотрим подробнее графический способ задания отношений.
Графические методы задания отношения:
Координатный метод;
Линейно-координатный метод;
Линейный

Координатный метод

Способы задания отношений

Пусть дано множество и отношение R⊆X2:

Основной недостаток

Линейно-координатный метод

Способы задания отношений

Представим то же отношение
На множестве линейно-координатным методом.

Недостаток этого

Линейный метод
Используя параллельные вертикальные линии для D и R получаем диаграммы,

Графовый метод
Элементы множества, на котором строится отношение, представлены вершинами графа, а

Задача. По матрице представить отношение списком, графически

Способы задания отношений

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

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

Пример. Пусть
Определено на множестве
Зададим списком:
Свойства отношения R:
рефлексивно, так как х/х=1

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

1

2

3

4

7

6

5

8

9

Пример. На булеане множества М={1, 2, 3} задано отношение R –

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

∅

∅

{1}

{2}

{3}

{1,2}

{1,3}

{2,3}

{1,2,3}

{1}

{3}

{2}

{1,2}

{1,3}

{2,3}

{1,2,3}

3)

Линейный метод

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

∅

{1}

{2}

{3}

{1,2}

{1,3}

{2,3}

{1,2,3}

Графовый метод

Свойства отношения R – «быть собственным подмножеством»:
Не является рефлексивным
Антирефлексивно, так как

Пример. R
Задать всеми способами и определить свойства отношения R.
N={1,2,3,4,5,6,7,8,9}
Решение.
Списком:
Графически:

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

R

Матрица отношения «иметь общий делитель»

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

Свойства отношения R- «иметь общий делитель»:
нерефлексивно, так как выполняется аRа

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

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

Матрица рефлексивного отношения имеет на главной диагонали 1

А на диаграмме

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

На диаграмме графового представления антирефлексивного отношения ни для какого узла

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

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

В матрице симметричного отношения единицы симметричны относительно главной диагонали

На диаграмме

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

Пример матрицы антисимметричного отношения

На диаграмме графового представления антисимметричного отношения ни для какой стрелки, соединяющей

5) На диаграмме графового представления транзитивного отношения для каждой пары узлов

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

Пример. На рисунке схематично представлено расположение офисов семи

Определение: Отношение эквивалентности– это бинарное отношение на множестве Х, удовлетворяющее следующим

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

Пример. R- «быть равным» на множестве натуральных чисел.
Свойства:
Рефлексивно, т.к. а=а,

Примеры отношений эквивалентности:
Отношение «быть равным», «иметь один и тот же

Отношение толерантности

Определение: Отношением толерантности (или просто толерантностью) на множестве X называется

Отношения «быть другом», «быть знакомым», - отношения толерантности, так как они

Отношения порядка
Множество М, которое обладает отношением порядка, называется упорядоченным.

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

антисимметричность

транзитивность

+ рефлексивность

+

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

Определение: Отношение строгого порядка– это бинарное отношение на множестве

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

Определение: Отношение нестрогого порядка– это бинарное отношение на множестве

Особые виды отношений

Задача 2. Дан граф некоторого отношения. Дополните его минимальным числом стрелок

Задача 3. Назовем два слова сходными, если они состоят из одинако­вого