Дискретная математика

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

Понятие множества относится к числу простейших и в то же время фундаментальных понятий математики. Это понятие является неопределимым — его нельзя свести к каким-то более простым математическим объектам, но можно пояснить с помощью наглядных примеров. Множества — это совокупности каких-то объектов произвольной природы, и эти объекты называются элементами того или иного множества .

Тот факт, что какой-то объект e является элементом множества E, записывается в виде

e? E или E? e

и выражается словами

e принадлежит (множеству) E,

или

(множество) E содержит (элемент) e,

или

e является элементом (множества) E.

Часто в вычислениях необходимо выбирать элементы множеств, которые удовлетворяют некоторому «отношению». Это понятие довольно общее, поэтому широко применимо. При соответствующем выборе отношения его аргументы могут быть связаны какой-либо формулой, иногда достаточно простой, если возможно найти удачное описание.

n-местным отношением R на множествах A1, …, An называется подмножество прямого произведения A1x… x An.

Другими словами, элементы x1, …, xn (где x1? A1, …, xn? An) связаны отношением R тогда и только тогда, когда (x1, x2, …, xn)?R, а (x1, x2, …, xn) — упорядоченный набор из n элементов .

Если n = 1, то отношение называется унарным. Таким образом, унарные отношения — это просто подмножества множества A. Например, свойство карты быть бубной является унарным отношением, определённым на колоде карт.

Если n = 2, то отношение называется бинарным. Например, свойство двух чисел не иметь общих делителей является бинарным отношением на множестве натуральных чисел. Свойство двух точек прямой находиться на расстоянии не более заданного числа? друг от друга является бинарным отношением на множестве действительных чисел.

Если n = 3, то отношение называется тернарным. Например, свойство трех точек быть вершинами равностороннего треугольника — тернарное отношение на плоскости. Свойство трех человек быть отцом, матерью и ребенком является тернарным отношением на множестве всех людей.

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

Пусть R есть отношение на A: R? А х A, a, b? А. Определим следующие виды отношений: