Упорядоченное множество и прямое произведение

Министерство образования и науки Украины

 

ОДЕССКИЙ НАЦИОНАЛЬНЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

 

 

С.А. БОБРИКОВ

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ СИСТЕМ

 

КОНСПЕКТ ЛЕКЦИЙ ДЛЯ СТУДЕНТОВ

СПЕЦИАЛЬНОСТИ 7.091401

 

ОДЕССА ОНПУ 2001

Конспект лекций по дисциплине “Математические основы теории систем” для студентов специальности 7 091 401/сост. С.А. Бобриков - Одесса: ОНПУ, 2001. – 101с.

 

Конспект лекций охватывает разделы математики, необходимые для изучения основных дисциплин специальности 7 091 401, и не вошедшие в курс “Высшая математика” и другие дисциплины: элементы теории множеств и теории графов, математическая логика, теория конечных автоматов, элементы теории случайных функций.

Автор С.А. Бобриков, к.т.н., доц.

 

ВВЕДЕНИЕ..............................................................................................................……………… 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ..................................................................……………. 1.1. Основные определения.......................................................................……………… 1.2. Операции над множествами................................................................……………… 1.3. Упорядоченное множество и прямое произведение множеств........……………... 1.4. Соответствия........................................................................................………………. 1.5. Конечные и бесконечные множества. Мощность множества............…………….. Литература..........................................................................………………. 2. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ........................................................................…………….. 2.1. Основные определения........................................................................……………… 2.2. Способы задания графов.....................................................................……………… 2.3. Операции над графами........................................................................……………… 2.4. Характеристические числа графов......................................................……………… 2.5. Плоские графы.....................................................................................………………. Литература.........................................................................………………. 3. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ..................................................……………. 3.1. Элементарные логические функции....................................................……………… 3.2. Принцип суперпозиции. Законы и тождества алгебры логики...........……………. 3.3. Способы задания логической функции...............................................……………… 3.4. Конституенты единицы и нуля. Составление логической формулы по таблице истинности........................................................................……………… 3.5. Полином Жегалкина............................................................................………………. 3.6. Замкнутые классы логических функций..............................................…………… 3.7. Функционально полные системы элементарных булевых функций...……………. 3.8. Дизъюнктивные и конъюнктивные нормальные формы булевых функций…….. 3.9. Минимизация булевых функций.........................................................………………. 3.10. Минимизация не полностью определенных булевых функций.........…………… 3.11. Синтез схем со многими выходами...................................................……………… Литература..........................................................................……………….. 4. КОНЕЧНЫЕ АВТОМАТЫ.................................................................................…………….. 4.1. Основные понятия и определения.......................................................…………….. 4.2. Переход от автомата Мили к эквивалентному автомату Мура и наоборот..............................................................................................……………….. 4.3. Минимизация числа состояний конечного автомата.........................……………… 4.4. Постановка задачи синтеза автоматов................................................……………… 4.4.1. Структурно полные системы автоматов. Теорема о структурной полноте...........................................................……………….. 4.4.2. Элементарные автоматы......................................................……………… 4.4.3. Структурный синтез конечных автоматов..........................……………. Литература..........................................................................………………. 5. СЛУЧАЙНЫЕ ПРОЦЕССЫ В СИСТЕМАХ УПРАВЛЕНИЯ..........................……………. 5.1. Случайные величины и их основные характеристики........................…………… 5.1.1. Интегральный закон распределения (функция распределения)……….. 5.1.2. Дифференциальный закон распределения (плотность вероятности)….. 5.1.3. Моменты случайных величин и их свойства.……………………………. 5.2. Векторные случайные величины.........................................................…………….. 5.2.1. Функция распределения двумерного случайного вектора.…………….. 5.2.2. Функция плотности вероятности двумерного случайного вектора……   5.2.3. Моменты системы случайных величин...............................……………………………… 5.3. Случайные функции. Многомерные законы распределения..............…………….. 5.4. Характеристики случайных функций..................................................……………… 5.5. Операции над случайными функциями...............................................……………… 5.5.1. Суммирование случайной детерминированной функции..……………… 5.5.2. Интегрирование случайной функции..................................……………… 5.5.3. Дифференцирование случайной функции..........................…………….. 5.5.4. Сложение случайных функций............................................……………… 5.6. Стационарные случайные процессы....................................................…………….. 5.6.1. Эргодическая теорема.........................................................………………. 5.6.2. Корреляционная функция стационарного случайного процесса……… 5.6.3. Расчет корреляционной функции по экспериментальным данным……. 5.7. Спектральная плотность стационарного случайного процесса..........……………. 5.8. Связь между спектральной плотностью и корреляционной функцией стационарного случайного процесса...................................................................….. 5.9. Случайные функции и их характеристики (примеры).......................... …………… 5.10. Прохождение стационарного случайного сигнала через линейную систему…… Литература.............................................................................

 

ВВЕДЕНИЕ

 

Современное производство характеризуется широким внедрением во все его сферы микроэлектроники, вычислительной техники, автоматики, систем автоматического управления. Все новейшие отрасли науки и техники так или иначе связаны с техникой автоматического управления, а некоторые из них совершенно немыслимы без широкого использования автоматического управления в технологических процессах. Это атомная энергетика, космические исследования, микроэлектроника и др. Особое место занимают автоматические системы, которые обеспечивают обработку больших потоков информации, надежность и экономическую эффективность производства. В настоящее время теория автоматических систем быстро развивается, ее идеи используются в таких научных направлениях как кибернетика, вычислительная техника, теория оптимального управления и др. Теоретической базой теории систем управления являются разделы математики, которые бурно развиваются: теория множеств, теория графов, математическая логика, теория конечных автоматов, теория случайных процессов и ряд других. Особое место в этом ряду занимает теория множеств, являющаяся фундаментом всей математики и зародившаяся в работах немецкого математика Кантора в 1879 - 1884 гг. В настоящее время теория множеств представляет собой математический аппарат теоретико-множественного анализа систем управления.

Данное учебное пособие представляет собой краткий конспект лекций по дисциплине “Математические основы теории систем”, составленный в соответствии с рабочей программой курса и учебным планом, принятым в Одесском политехническом университете для студентов, обучающихся по специальности 7 091 401 “ Компьютеризированные системы управления и автоматика”. В пособие включены лишь те разделы курса, которые недостаточно освещены в учебной литературе, либо изучение которых представляет для студентов определенные трудности. Это теория множеств, графы, математическая логика, теория конечных автоматов, случайные процессы.

 

 

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

Основные определения

[С. В. Х.1] Под множеством понимают совокупность определенных, вполне различимых объектов, рассматриваемых как единое целое. Множество задано, если о любом объекте можно сказать, принадлежит он данному множеству или нет. Примеры множеств: множество студентов в данной группе, множество книг в библиотеке, множество точек на прямой, множество людей на Марсе и т.д.

Объекты, составляющие множество, называются элементами множества. Принято обозначать множества прописными буквами, а элементы множества – строчными буквами латинского алфавита.

Если объект а является элементом данного множества А, то это записывается с помощью символа принадлежности следующим образом: а Î А и читается как “ а является элементом множества А ”, или “ а входит в А ”.

Множество может быть задано по разному: 1) перечислением всех входящих в него объектов; 2) описанием свойств, которыми должны обладать все элементы данного множества. Например, множество, состоящее из трех человек: Иванов, Петров, Сидоров. Либо множество студентов третьего курса, занимающихся боксом.

Общим обозначением множества служит пара фигурных скобок, внутри которых перечисляются элементы множества. Например, А= {1,2,3,4} – множество А, элементами которого являются числа 1, 2, 3, 4. Пусть М – множество студентов группы, А – множество отличников этой группы, тогда можно записать так: А ={xÎ M: x - отличник группы} – это описательный способ задания множества. В фигурных скобках слева от двоеточия указывается общее обозначение элементов данного множества и какому более объемлющему множеству они принадлежат, а справа от двоеточия указывается общее свойство, которым обладают все элементы данного множества.

Множество может содержать лишь один элемент – одноэлементное множество. Например, А= { а }. Здесь следует различать а и { а }. а – элемент одноэлементного множества { а }: а Î{ а }.

Пустое и универсальное множества. Пустым называется множество, не содержащее ни одного элемента. Обозначается пустое множество символом Æ.

Например, { x Î R:x²-x+1=0}=Æ, если R – множество вещественных чисел. Пустое множество в алгебре множеств аналогично нулю в алгебре чисел.

Если в рассмотрении участвуют только элементы некоторого фиксированного множества J, то это самое большое множество J называется универсальным, или объемлющим, или полным множеством. В различных конкретных случаях роль универсального множества могут играть различные множества.

Предикаты и кванторы. Пусть имеется универсальное множество J и некоторое высказывание, относительно его произвольного элемента. Высказывание, которое отображает наличие или отсутствие того или иного признака у предмета называют предикатом. Таким образом, предикат Р задает множество X, каждый элемент которого xÎX обладает определенным свойством. В общем виде некоторое множество X, состоящее из элементов x, обладающих определенным свойством, можно записать так: X={x:P(x)}.

Могут быть предикаты, которые являются истинными для любого элемента x множества J, т.е. P(x) может быть истинным при любом x. Для обозначения этого факта вводится символ ", который называется квантором общности. Запись "(x)P(x) означает высказывание, что для любого xÎJ значение предиката P(x) - истина.

Введем квантор существования $. Запись $(x)P(x) означает, что среди всех xÎJ существует хотя бы один элемент, для которого предикат P(x) принимает истинное значение.

К кванторам также как и к предикатам можно применять отрицание, которое обозначается чертой над соответствующим символом. Например, запись (x)P(x) означает: не для всякого элемента x в множестве J P(x) - истина. (x)P(x) означает – не существует ни одного элемента x в J, для которого P(x) - истина.

Пусть P(x) представляет высказывание, заключающееся в том, что x обладает некоторым свойством. Тогда запись (x) означает, что элемент x не обладает этим свойством. Запись "(x) (x) имеет следующий смысл: для любого xÎJ P(x) - ложь, а (x) - истина.

Очевидны следующие записи:

"(x)P(x) Û (x) (x), (x)P(x) Û $(x) (x).

Равенство множеств. Два множества называются равными, если они состоят из одних и тех же элементов. При этом порядок расположения элементов в множестве значения не имеет. В одном и том же множестве не может быть несколько одинаковых элементов. Например, запись А= {1,1,2,3}следует считать неправильной. Это множество состоит из трех элементов: A= {1,2,3}.

Подмножество. Множество X является подмножеством Y, если любой элемент множества X принадлежит и множеству Y. Для обозначения подмножества используются символы включения: Ì - строгое включение, Í - нестрогое включение. Например XÌY или XÍY. Эти записи означают, что X есть подмножество множества Y.

В первом случае в множестве Y обязательно есть элементы, не принадлежащие множеству X. Во втором случае таких элементов в Y может и не быть. Символически определение подмножества можно записать следующим образом:

XÍYÛ"(x)[xÎX®xÎY].

Любое множество всегда содержит в себе пустое множество в качестве подмножества и само является подмножеством универсального множества

"(X)[ÆÍX, XÍJ]. Кроме того XÍX.

Для любого множества X существует множество X*, элементами которого являются подмножества множества X. Такое множество обозначается через 2^Xили expX и называется множеством-степенью.

Если число элементов множества X равно n, то число элементов его множества-степени равно 2ⁿ. Например, X ={1,2,3}, тогда

X * = 2^X ={ {1 },{2 },{3},{1,2 },{1,3 },{2,3 },{1,2,3 },Æ }.

Как видно из примера в множество-степень включают также само множество X и пустое множество.

 

Операции над множествами

Объединение множеств. Объединением множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат X или принадлежат Y. Объединение обозначается через XÈY. Суть операции легко понять, пользуясь диаграммами Эйлера-Венна. Пусть X- множество точек левого круга (Рис.1а), Y- множество точек правого круга. Тогда XÈY - заштрихованная область.

 

 

Рис.1. Диаграммы Эйлера-Венна

 

Пересечение множеств. Пересечением множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y. Пересечение множеств обозначается через XÇY. На рис.1б пересечение множеств X и Y соответствует заштрихованной области. Если XÇY= Æ, то множество X и Y называются непересекающимися.

Разность множеств. Разностью множеств X и Y называется множество, состоящее из тех и только тех элементов, которые принадлежат X и не принадлежат Y. Обозначается разность множеств следующим образом: X\Y. На рис1.взаштрихована область, соответствующая разности множеств X и Y.

Симметрическая разность множеств. Симметрической разностью множеств X и Y называется множество, состоящее из всех тех и только тех элементов, которые принадлежат или множеству X, или множеству Y, но не обоим вместе. Обозначается симметрическая разность множеств следующим образом: X Y. На рис1.г заштрихованная область соответствует X Y.

Дополнение множества. Множество , определяемое из соотношения = J\X называется дополнением множества X. Пусть множество точек прямоугольника на рис.2 составляет универсальное множество J, X -множество точек круга. Тогда - множество точек заштрихованной области. Множества X и не имеют общих элементов, поэтому XÇ =Æ. Кроме того не имеется элементов в множестве J, которые не принадлежали бы ни X, ни , т.к. те элементы, которые не принадлежат X принадлежат . Следовательно XÈ = J.

 

 

Рис.2. - дополнение множества X

Разбиение множества. Некоторые множества можно представить как систему подмножеств. Так, например, множество студентов института составляют систему подмножеств факультетов, либо систему подмножеств курсов.

Рассмотрим некоторое множество М и систему множеств S={X₁, X₂,...,X_n}. Система множеств S называется разбиением множества M, если она удовлетворяет следующим условиям.

1. Любое множество X_i (i=1,2,...,n) из S является подмножеством множества M - X_iÌ M, т.е. "XÎS: XÌM.

2. Любые два множества X_i и X_j из S являются непересекающимися - X_iÇX_j=Æ, если i¹j, т.е. "X_iÎS и "X_jÎS (i¹j): X_iÇX_j=Æ.

3. Объединение всех множеств, входящих в разбиение, равно множеству M –

.

Тождества алгебры множеств. С помощью различных операций над множествами из множеств можно составлять различные алгебраические выражения. Пусть в результате некоторых операций над одними и теми же множествами X,Y,Z получены новые множества U и V, содержащие одни и те же элементы. Выражение U=V представляет собой тождество алгебры множеств.

Рассмотрим наиболее важные тождества алгебры множеств.

 

1. XÈY=YÈX

2. XÇY=YÇX Коммутативные

3. XDY=YDX законы

4. XÈ(YÈZ)=(XÈY)ÈZ Ассоциативные

5. XÇ(YÇZ)=(XÇY)ÇZ законы

6. (XÈY)ÇZ=(XÇZ)È(YÇZ) Дистрибутивные

7. (XÇY)ÈZ=(XÈZ)Ç(YÈZ) законы

8. = Ç Тождества

9. = È де Моргана

 

Все приведенные тождества могут быть легко доказаны, например, с помощью диаграмм Эйлера-Венна. В качестве примера рассмотрим доказательство дистрибутивного закона (тождество 6).

 

 

Рис.3. Геометрическая иллюстрация тождества 6.

 

На рис.3а двойная штриховка соответствует выражению (XÈY)ÇZ, на рис.3б заштрихованная область равна (XÇZ)È(YÇZ). Из диаграмм видно, что оба выражения определяют одно и то же множество.

 

Упорядоченное множество и прямое произведение

Множеств

Упорядоченным множеством или кортежем называется такое множество, в котором каждый элемент занимает определенное место. Число элементов кортежа называется длиной кортежа. Для обозначения кортежа используются круглые скобки. Например, A=(a₁, a₂, a₃) - кортеж длины 3. Частным случаем кортежа является кортеж длины 1 - (a) и пустой кортеж длины 0, обозначаемый () или Ù. В отличие от простого множества в кортеже могут быть и одинаковые элементы.

Упорядоченное множество, элементами которого являются вещественные числа, можно рассматривать как координаты точки. Так, кортеж длины 2 можно рассматривать как точку на плоскости, либо вектор, проведенный из начала координат в данную точку. Кортеж длины 3 - точка, либо вектор в трехмерном пространстве, кортеж длины n - точка, либо вектор в n-мерном пространстве.

 

Прямое произведение множеств. Прямым произведением множества X на множество Y называется множество таких упорядоченных пар (x,y), что xÎX, а yÎY. Обозначается прямое произведение следующим образом: X´Y. X´Y={(x,y): xÎX и yÎY}.

Например: X ={1,2}, Y ={a,b}, X´Y ={(1,a),(2,a),(1,b),(2,b)}.

Как следует из определения, прямое произведение множеств не обладает свойством коммутативности, т.е. X´Y¹Y´X.

Если элементами множеств X и Y являются действительные числа, то элементы прямого произведения удобно изображать в виде точек, лежащих на плоскости и имеющих соответственно координаты x и y. Операция прямого произведения множеств может быть применена и к большему числу множеств. Прямым произведением множеств X₁, X₂,...,X_k называется множество, состоящее из кортежей длины k, первая компонента которых принадлежит X₁, вторая X₂, и т.д. Прямое произведение множеств обладает свойством дистрибутивности относительно операций объединения и пересечения:

(AÈB)´C=(A´C)È(B´C), (AÇB)´C=(A´C)Ç(B´C).

Проекции множества. Рассмотрим сначала проекции кортежа. Проекцией кортежа на первую ось является первый элемент кортежа, проекцией на вторую ось - второй элемент и т.д. Пусть элементами множества M являются кортежи одинаковой длины. Тогда проекцией M на какую-либо ось будет множество проекций кортежей из M на ту же ось.

Пример. Пусть M= {(a,b,c), (x,x,x), (1,2,1)}.

Тогда Пр₁ М= {a,1,x}; Пр_2,3 М= {(b,c), (2,1), (x,x)}.

Если M=X´Y, то Пр₁ М=X; Пр₂ М= Y.

Если QÍX´Y, то Пр₁QÍX; Пр₂ QÍY.

 

Соответствия

Пусть заданы два множества X и Y. Если каким-либо элементам xÎX сопоставляются некоторые элементы yÎY, образуя пары (x,y)ÍX´Y,то говорят, что между множествами X и Y установлено соответствие. Чтобы задать соответствие, нужно указать множество X, множество Y и множество QÍX´Y,определяющее закон, по которому осуществляется соответствие. Таким образом, соответствие q представляет собой упорядоченную тройку множеств q=(X,Y,Q), где QÍX´Y. Очевидно, что Пр₁QÍX и Пр₂QÍY.

Множество X называется областью отправления соответствия.

Множество Y - областью прибытия соответствия.

Множество Q - графиком соответствия.

Пр₁Q - областью определения соответствия.

Пр₂Q - областью значений соответствия.

 

Пример: X={x:0£x£10}, xÎR, R - множество вещественных чисел; Y={a,b,c,d,e.} Одним из возможных соответствий между элементами X и Y может быть Q={(1,a),(5,a),(2,b),(5,d)}. Как видно из примера не обязательно, чтобы все элементы из X и из Y участвовали в соответствии. Кроме того, одному и тому же элементу из X могут соответствовать несколько элементов из Y, а один и тот же элемент из Y может сопоставляться с разными элементами из X.

Для каждого соответствия q=(X,Y,Q), QÍX´Y можно построить обратное соответствие, которое определяется следующим образом:

q^-1=(Y,X,Q^-1),где Q^-1ÍY´X.

Отображение. Если в некотором соответствии q=(X,Y,Q), QÍX´Y область определения совпадает с областью отправления Пр₁Q=X,то такое соответствие называется отображением. Отображение обозначают следующим образом: Г:X®Y, где ГÍX´Y - график отображения X в Y.

Множество тех элементов yÎY, которые сопоставляются с каким-либо элементом xÎX при отображении Г:X®Y, называется образом элемента x и обозначается Гx. Очевидно ГxÍY.

Множество тех элементов xÎX, с которыми сопоставляется какой-либо элемент yÎY, называется прообразом элемента y: Г^-1yÍX.

Пример. Пусть X={1,2,3}; Y={a,b,c,d,e}. Рассмотрим отображение X в Y, график которого имеет вид: Г={(1,a),(1,b),(2,c),(3,a),(3,b),(3,d)}. Образами в этом отображении являются:

Г₁={a,b} - образ элемента 1;

Г₂={c} - образ элемента 2;

Г₃={a,b,d} - образ элемента 3;

 

Прообразы: Г^-1a={1,3} - прообраз элемента a;

Г^-1b={1,3} - прообраз элемента b;

Г^-1c={2} - прообраз элемента c;

Г^-1d={3} - прообраз элемента d;

Г^-1e=Æ - прообраз элемента е.

Однозначное отображение или отображение, при котором образ каждого элемента есть одноэлементное множество, называется функцией. Для функции принято обозначение f: X®Y. Значение y в любой из пар (x,y)Îf называется функцией от данного x и записывается в виде y = f(x). Символ f при определении функции используется в двух смыслах: 1) f является множеством, элементами которого являются пары (x,y), участвующие в соответствии; 2) f(x) является образом x, т.е. f(x)=y.

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

Если в функции область прибытия совпадает с областью значений, то она называется сюрьективной или сюрьекцией.

Сюрьективная инъекция называется биекцией. Таким образом, биекция есть взаимно однозначное отображение, в котором участвуют все элементы одного множества и все элементы другого множества.

Если в соответствии рассматривается множество функций с одной стороны и множество чисел с другой стороны, то оно называется функционалом. Например,

J(x)= .

Соответствие, установленное между двумя множествами, элементами которых являются функции, называется оператором. Например,

f ^΄(x) = - оператор дифференцирования.

Отношения. Некоторые отображения, заданные между элементами одного и того же множества, называются отношениями. Для задания отношения нужно указать множество X, между элементами которого вводится отношение, и закон, по которому один элемент из X сопоставляется с другим. Например, отношение (X,Г), где ГÍX².

Пусть yÎX есть образ элемента xÎX при задании отношения (X,Г). Тогда говорят, что элемент y находится в отношении Г к элементу x, и записывают это в виде yГx.

Отношения характеризуются определенными свойствами. Перечислим важнейшие из них.

1. Рефлексивность. Пусть задано некоторое отношение Г на множестве X. Если любой элемент xÎX находится в том же отношении к самому себе, то это свойство называется рефлексивностью. Его можно записать следующим образом: xГx - истинно.

2. Антирефлексивность. Это свойство выражается следующим образом: xГx - ложно.

3. Симметричность. Это свойство заключается в том, что при рассмотрении двух элементов, связанных некоторым отношением, обладающих свойством симметричности, неважно, какой элемент рассматривать первым, а какой вторым, т.е. xГy® yГx.

4. Антисмметричность. Это свойство заключается в следующем. Если два элемента x и y находятся в отношении, обладающим этим свойством, причем xГy - истинно и yГx - истинно, то из этого обязательно следует, что x=y: xГy и yГx®x=y.

5. Несимметричность. Это свойство определяется следующим образом. Если xГy - истинно, то yГx - ложно и наоборот.

6. Транзитивность. Свойство транзитивности означает, что если два элемента находятся в некотором отношении с этим свойством с третьим элементом, то это же отношение существует и между ними. В общем виде это свойство записывается следующим образом: xГy и yГz®xГz.

Виды отношений. В зависимости от того, какими свойствами обладают отношения, их делят на виды.

1. Отношение эквивалентности. Отношением эквивалентности называется такое отношение, которое обладает следующими свойствами: рефлективность, симметричность, транзитивность.

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

Пример: отношение “быть на одном курсе” на множестве студентов факультета; отношение равенства на множестве чисел; отношение подобия на множестве треугольников и т.д.

2. Отношение толерантности. Отношение толерантности удовлетворяет свойствам рефлективности и симметричности. В отличие от эквивалентности толерантность не обладает свойством транзитивности. Эквивалентность можно рассматривать как частный случай толерантности.

Пример: на множестве кортежей одинаковой длины толерантность можно задать различными способами, например, наличием в паре кортежей хотя бы одной общей компоненты.

3. Отношение нестрогого порядка. Это отношение обладает следующими свойствами: рефлексивность, антисимметричность, транзитивность.

Примеры: отношение “больше или равно” или “меньше или равно” на множестве чисел; отношение нестрогого включения на множествах; отношение “произойти не позже” или “произойти не раньше” на множестве состояний динамической системы.

4. Отношение строгого порядка. Это отношение определяется следующими свойствами: антирефлексивность, несимметричность, транзитивность.

Примеры: отношение “больше” или “меньше” на множестве чисел; отношение строгого порядка на множествах; отношение “произойти раньше” или “произойти позже” на множестве состояний динамической системы и т.п.

Оба отношения - нестрогого порядка и строгого порядка - определяют некоторый порядок расположения элементов множества. Множество, на котором определено отношение порядка, называют упорядоченным. Множество совершенно (линейно, просто) упорядочено, если для любых двух его элементов имеет место xГy или yГx (Г - отношение порядка). В общем случае может оказаться, что для некоторых пар (x,y) ни одно из соотношений x<y и y<x не имеет места (такие элементы называют несравнимыми). Тогда говорят, что множество частично упорядочено. Примером частичного порядка является отношение нестрогого включения на множестве подмножеств некоторого множества. Среди всех подмножеств одного и того же множества имеются такие, что ни одно из соотношений XÍY и YÍX для них не имеет места.

5. Отношение доминирования. Это отношение определяется следующими свойствами: антирефлексивность, несимметричность.

Например: на множестве спортивных команд отношение “выиграть матч”.