3. Основные теоретические сведения

3.1. Элементы теории множеств

М ножество − любая совокупность объектов, рассматриваемых совместно. Объекты, из которых составлено множество, называются его элементами. Для задания множества необходимо указать, какие элементы ему принадлежат. Множества обозначают прописными буквами латинского алфавита (A, B, C…), а элементы − строчными (a, b, с…), которые обычно снабжаются индексами. Множество, не содержащее элементов, называется пустым и обозначается . Некоторые множества имеют общепринятые имена: N − множество натуральных чисел; Z − множество целых чисел; R − множество вещественных чисел. Элементы множества заключаются в фигурные скобки и отделяются друг от друга запятыми. Основное соотношение между элементом и содержащим его множеством обозначается a A (a принадлежит A). Если количество элементов в множестве счётно, то множество называется конечным, иначе − бесконечным. Существует два способа задания множеств: перечислением его элементов или указанием порождающей процедуры. Например,

A={ a₁,a₂,a₃ };

X={1,2,3,4,5,6,7,8,9 } или X={ x_i | x_i N & x_i <10 }.

Обычно, в каждом конкретном случае элементы рассматриваемого множества выбираются из некоторого универсального множества U (своего для каждого случая).

Над множествами определены следующие операции:

объединение:

А В = { х | х А или х В};

пересечение:

А В = { х | х А & х В };

разность:

А \ В = { х | х А & х В };

дополнение:

= { х | х А },

операция дополнения подразумевает, что задано некоторое универсальное множество U: = U \ А, в противном случае операция дополнения не определена.

Операции над множествами обладают рядом важных свойств.

Пусть задано универсальное множество U, тогда для любых А, В, С U выполняются следующие равенства:

1) идемпотентность:

A А = А , А А = А ;

2) коммутативность:

A В = В А , А В = В А ;

3) ассоциативность:

A (B C) = (A B) C , А (В С) = (А В) С ;

4) дистрибутивность:

A (В С) = (A В) (A С) ,

A (B С) = (A В) (А С) ;

5) поглощение:

(А В) А = А , (А В) А = А ;

6) свойства нуля:

A = А , А = ;

7) свойства единицы:

A U = U , А U =А ;

8. Инволютивность:

А = А ;

8. Законы де Моргана:

А В = A В, А В = A В ;

10. свойства дополнения:

A А = U , А А = ;

10. Выражение для разности:

A \ B = A B .

3.2. Отношения

Если a и b – некоторые объекты, то через (a,b) обозначим упорядоченную пару.

Пусть A и B – конечные множества, такие, что A={a₁, a₂,… a_n}, B={b₁, b₂,… b_m}. Декартовым произведением множеств A и B называется множество D = A × B, состоящее из всех упорядоченных пар ( a_i, b_j ), таких, что a_i A , b_j B.

Бинарным отношением называется любое подмножество R декартового произведения множеств A и B, т. е. R D .

Если R – бинарное отношение, то говорят, что a_i и b_j связаны отношением R при ( a_i, b_j ) R, и обозначают a_i R b_j .

Отношение R однозначно определяется множеством R. Часто отношения задают матрицей отношений R = ||r_ij||, в которой

r_ij=

Отношения определены как множества, поэтому над ними выполняются операции объединения, пересечения и дополнения. Кроме того, введены две новых операции: обратное отношение и композиция или произведение отношений.

Обратное отношение R ^‑1:

( a_i , b_j ) R ( b_j ,a_i ) R ^-1.

Композиция отношений R_{1 º} R₂:

пусть A, B, С – конечные множества и R₁ A × B , R₂ B ×С , тогда

R_{1 º} R₂={(a_i, c_k ) | a_i A & c_k C & b_j B ( a_i R₁ b_j & b_j R₂ c_k ) }.

Если R A × A, то говорят, что бинарное отношение определено на множестве A.

Бинарное отношение R на непустом множестве A называется рефлексивным, если ( a_i,a_i ) R для всех a_i, A; отношение R называется антирефлексивным ( иррефлексивным ), если

( a_i,a_i ) R для всех a_i, A. Если хотя бы для одного a_i, A пара

( a_i,a_i ) R, то отношение называется нерефлексивным.

Б инарное отношение R на непустом множестве A называется симметричным, если для всех пар (a_i,a_j ) R (a_j,a_i ) R; если

(a_i,a_j) R (a_j,a_i) R, то отношение называется антисимметричным ( асимметричным).

Б инарное отношение R на непустом множестве A называется транзитивным, если (a_i,a_j) R & (a_j,a_k) R (a_i,a_k) R .

Пусть на множестве A задано отношение несовместимости R . Подмножество Y A называется совместимым, если для любых y_i Y и y_j Y пара (y_i, y_j) R. Подмножество Y A называется максимальным совместимым, если в него нельзя ввести никакой новый элемент так, чтобы не нарушить условие совместимости.

Если заданы множество B={b₁, b₂,… b_m} и множество A={A₁, A₂,… A_n} подмножеств элементов множества B, то отношение включения во множества A_i элементов множества B называется таблицей покрытий. Решение задачи о покрытии заключается в нахождении множества подмножеств A_i , которые содержат все элементы множества B. Таким образом, покрытие – это множество подмножеств A_i, для которых A_i=B.

Покрытие с наименьшим числом элементов называется кратчайшим. Если каждому элементу множества A поставлена в соответствии числовая характеристика (вес или стоимость), то покрытие с наименьшим суммарным весом называется минимальным.