Отношения

1.2.1. Понятие отношения

Для выражения взаимодействий и связей между элементами множеств в математике используется понятие отношения.

n – местным (n – арным) отношением R на множествах называется любое подмножество прямого произведения этих множеств, то есть . Другими словами, элементы этих множеств связаны отношением R тогда и только тогда, когда n упорядоченных чисел .

Отношение называется n – местным на множестве А.

При отношение R задает фиксированный элемент множества А. При отношение R представляет собой подмножество множества А и называется унарным отношением или свойством. При отношение R называется бинарным или соответствием. При отношение тернарное и т. д.

В математике чаще всего используются бинарные отношение (соответствия). В дальнейшем рассматриваются в основном только такие отношения и при этом слово “бинарные” опускается.

Пусть А и В – два множества. Соответствием или (бинарным) отношением из множества А в множество В называется подмножество R прямого произведения , т.е. . Если aÎA, bÎB, находятся в отношении, то пишут: (a,b)ÎR или R(a,b), а также в инфиксной форме aRb. При этом говорят, что b соответствует a при соответствии R или b находится в отношении R с a. Если R=Æ, то отношение называют пустым. Отношение называют полным. Для любого множества А определяется тождественное отношение - .

Принадлежность элементов а и b отношению R наглядно можно представить в следующем виде

Областью определения (DomR) соответствия R, называется множество элементов aÎA, для каждого из которых, найдется хотя бы один элемент bÎB, такой, что aRb.

Областью значения (ImR) соответствия R называется множество элементов bÎB, для каждого из которых, найдется хотя бы один элемент aÎA, такой, что aRb.

Соответствие R называется всюду определенным, если DomR=A, в противном случае – частично определенным. Соответствие называется сюръективным, если ImR=B.

Для каждого aÎA, множество элементов bÎB таких, что aRb называется образом элемента aÎA относительно R и обозначается im_Ra.

Прообразом элемента bÎB относительно R, называется множество элементов aÎA, таких, что aRb. Прообраз обозначается: coim_Rb

Заметим, что и .

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

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

Списком, т.е. перечислением тех пар элементов, для которых это отношение выполнено. Например, если A= { a,b,c } и B= { x,y }, то R= {(a,x), (a,y), (b,y), (c,x)}.

Матрицей [ R ] размерности , элементы которой т.е. строки этой матрицы помечаются элементами из A, а столбцы – элементами из B, а на пересечении строки a _i со столбцом b _i стоит единица (1), если aRb; и нуль (0), - в противном случае. Тогда для выше приведенного примера имеем матрицу

	x	y
a
b
c

Графиком на координатной плоскости, горизонтальная и вертикальная оси которой представляют элементы множеств А и В соответственно.

Графом, в котором элементы множеств А и В изображаются точками на плоскости. Причем эти точки обозначаются теми же символами, что и соответствующие элементы. Точки a и b соединяются направленным отрезком от a к b, если aRb. Например, для предыдущего случая отношение R изображается ориентированным графом.

1.2.2. Операции над отношениями

Так как отношения из А в В задаются подмножествами , следовательно для них определены те же теоретико-множественные операции, что и над множествами:

Объединение .

Пересечение .

Разность .

Дополнение .

Заметим, что операции объединения, пересечения и дополнения бинарных отношений удовлетворяют законам идемпотентности, коммутативности, ассоциативности, поглощение, инволюции и законам де Моргана.

Над отношениями могут также осуществляться другими алгебраические операции:

Обратное отношение .

Произведение (композиция) отношений

.

Степень отношения .

Заметим, что:

, где сложение элементов матриц осуществляется по правилам 0+0=0, 1+1=1+0=0+1=1.

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

, где умножение матриц производится по обычному правилу умножения матриц.

, где символ T означает транспонирование матрицы.

1.2.3. Свойства отношений на множестве

Пусть задано отношение на множестве А, т.е. , тогда отношение R называется:

рефлексивным,	если
антирефлексивным,	если
симметричным,	если
антисимметричным,	если
транзитивным,	если
полным или линейным,	если

Для указанных отношений справедливы следующие утверждения:

R рефлексивно	Û
R антирефлексивно	Û
R симметрично	Û
R антисимметрично	Û
R транзитивно	Û
R полно	Û

Заметим, что:

в матрице рефлексивного отношения все диагональные элементы равны единице, а антирефлексивного – нулю. Для симметричного отношения справедливо . В случае антисимметричного отношения матрица имеет все элементы вне главной диагонали равные нулю. Для транзитивного отношения верно утверждение .

1.2.4. Отношения эквивалентности, толерантности

и порядка

Отношение R называется отношением эквивалентности, если R рефлексивно, симметрично и транзитивно. Это отношение обозначается символами E и ~(тильда): aEb или a ~ b. Важное значение отношения эквивалентности состоит в том, что оно определяет признак, по которому происходит разбиение исходного множества на непересекающиеся подмножества, называемые классами эквивалентности. Пусть E – эквивалентность на множестве А. Классом эквивалентности элемента называется множество . Классы эквивалентности Е называются также Е – классами. Множество называется фактор-множеством множества А по отношению к Е. Множество является разбиением множества А. Обратно, если - некоторое разбиение множества А, то можно задать соответствующее ему отношение эквивалентности Е по следующему правилу: для некоторого i.

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

В ряде случаев требуется указать старшинство, важность, “первичность” и другие подобные свойства объектов. Для этого служат различные виды отношения порядка.

Отношение называется предпорядком или квазипорядком, если R рефлексивно и транзитивно.

Отношение называется отношением порядка, если оно антисимметрично и транзитивно. Отношение порядка может быть рефлексивным, и тогда оно называется отношением нестрогого порядка. Антирефлексивное отношение порядка называется отношением строгого порядка. Отношение порядка может быть полным (линейным), и тогда оно называется отношением полного или линейного порядка. Отношение порядка, не обладающее свойством полноты (линейности), называется отношением частичного порядка.

Отношение строгого порядка (полного или частичного) обозначается символом <, а отношение нестрогого порядка - . Отношение порядка в общем случае обозначается знаком .

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

1.3. ПОНЯТИЕ АЛГЕБРАИЧЕСКОЙ СИСТЕМЫ

1.3.1. Понятие отображения

Частным видом отношения является отображение (функциональное соответствие).

Отображение – это закон, по которому каждому элементу x некоторого заданного множества X, однозначно соответствует определенный элемент y, другого заданного множества Y. Такое соответствие записывается в виде y=f(x) или f:x®y, при этом говорят, что отображение f действует из X в Y и пишут f:X ®Y. Элемент y=f(x) называется образом элемента x, а x называется прообразом элемента y.

Отображение числового множества в числовое называется функцией.

Когда множества X и Y не числовые, отображение называется оператором. Отображение не числового множества в числовое называется функционалом. Отображение f:X®X называется преобразованием множества X.

Иногда рассматривают отображения f, определённое на некотором подмножестве . В этом случае называется областью определения отображения f. Подмножество Im f={f(x) | xÎX} множества Y называется областью значений (образом) f.

Сужением (ограничением) отображения f:X®Y, на подмножество AÌX, называется отображение f_A(x), заданное равенством f_A(x)=f(x), для всех xÎA.

Расширением (продолжением, распространением) отображения f:X®Y на множестве BÉX (X – является подмножеством B) называется любое отображение f_B:B®Y, совпадающее с f на множестве X.

Если заданы три множества X,Y,Z и два отображения f:X®Y и g:Y®Z, то существует отображение h:X®Z, которое определяется равенством h(x)=g(f(x)). Это отображение называется композицией (суперпозицией, произведением) отображений и обозначается gf. Композиция отображений обладает свойством ассоциативности, то есть h(gf)=(hg)f.

Отображение называется тождественным, если f(x)=x, для всех xÎX. Отображение f:X®Y называется инъективным, если для любых двух элементов , таких что следует, что . Отображение называется сюръективным, если Imf=Y. Отображение, одновременно являющееся инъективным и сюръективным называется биективным.

1.3.2. Алгебраическая операция

Отображение f: A ⁿ ® A называется n- местной алгебраической операцией на множестве A. Очевидно, что n -местная алгебраическая операция на множестве A является () – местным отношением на множестве A. При операция f: A ⁰ ® A есть {(Æ, a)} для некоторого aÎA. Эта операция называется константой на множестве A и отождествляется с некоторым элементом a этого множества. При операция f называется унарной, а при - бинарной.

Примерами унарных операций являются:

Элементарные функции одного аргумента - и другие;

Операция над множествами – дополнение ;

Операции над отношениями – дополнение , обратное отношение , составное отношение и другие.

Примерами бинарных операций являются:

Арифметические операции – сложение, вычитание, умножение, деление, возведение в степень.

Операции над множествами – пересечение, объединение и разность.

Операция композиции функций, отображений, отношений.

Обозначим символом T произвольную бинарную алгебраическую операцию. Тогда операция над элементами , дающая результат записывается в виде a T b = c.

Свойства бинарных операций:

Ассоциативность - (a T b) T с = a T( b T с). (Выполнение этого условия означает, что скобки в этом выражении можно не расставлять.)

Коммутативность - a T b = b T a.

дистрибутивность - T (b ^ c)=(a T b)^(a T c) - дистрибутивность операции T слева относительно операции ^ и (a ^ b) T c= (a T c)(b T c) – дистрибутивность операции T справа относительно операции ^

Способы задания операций

Унарные операции задаются:

Перечнем всех аргументов и соответствующих им значений :

f =

Списком всех пар “аргумент – значение” для всех возможных значений аргументов: f ={ }.

Формулой , например .

Бинарные операции задаются:

Таблицей (таблица Кэли). Слева и сверху таблицы выписываются все значения аргументов, а на пересечении строк и столбцов – результат операции. Например, для операции “сложение по модулю 3” на множестве {0,1,2} имеет следующий вид:

Списком, путем перечисления всех троек . Например, для предыдущей операции:

{(0,0,0), (0,1,1), (0,2,2), (1,0,1), (1,1,2), (1.2,0), (2,0,2), (2,1,0), (2,2,1)}

Формулой или a T b = c. Например: , где - операция сложения по модулю 3.

1.3.3. Общие сведения об алгебраических системах

Алгебраическая система – это множество с определенными на нем операциями и отношениями. Алгебраическая система – это объект A , где - непустое множество, - семейство алгебраических операций, а - семейство отношений, заданных на множестве . Множество называется носителем алгебраической системы, а его элементы – элементами системы. Алгебраическая система называется конечной, если множество конечно.

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

Пусть A - алгебраическая система, в которой , причем есть арная операция, а есть местное отношение. Тогда последовательность целых чисел называется типом алгебраической системы A.

Пусть A и B - две алгебраические системы одного и того же типа. Отображение , называется гомомофизмом системы A в систему B, если выполняются следующие условия:

и

для всех и .

Если - гомоморфизм, то его обозначают A ® B.

Гомоморфизм A ® B являющийся инъекцией, называется мономорфизмом. Гомоморфизм A ® B, являющийся сюръекцией, называется эпиморфизмом и при этом система B называется гомоморфным образом системы A. Гомоморфизм A ® A называется эндоморфизмом. Сюръективный мономорфизм A ® B, для которого гомоморфизм, называется изоморфизмом и обозначается A «B. Изоморфизм A «A называется автоморфизмом системы A.

Понятие изоморфизма – одно из важнейших понятий в современной математике. При изоморфизме сохраняются действие всех основных операций и отношений. Это позволяет переносить изучение свойств с одной системы на другую.

1.4. РЕЛЯЦИОННАЯ АЛГЕБРА

1.4.1. Алгебра отношений

Алгебра отношений – это алгебра, носителем которой является множество отношений P ={ P₁, P₂, …,P_m,… }. Сигнатура ∑ алгебры отношений состоит из символов двухместных операций объединения , пересечения , разности \ и декартова произведения ´ отношений.

Отношения Р_i и P_j называются совместимыми, если Р_i, P_j Í Аⁿ для некоторого множества А и числа n Î N.

Объединением Р_i P_j двух совместимых отношений Р_i и P_j называется множество всех кортежей X, каждый из которых принадлежит хотя бы одному из этих отношений: Р_i P_j ={ X | X Î Р_i или Х Î P_j }.

Пересечением P_j Р_i двух совместимых отношений Р_i и P_j называется множество всех кортежей X, принадлежащих как отношению Р_i,, так и отношению P_j: Р_i P_j = { X | X Î Р_i и Х Î P_j }.

Разностью Р_i \ P_j двух совместимых отношений Р_i и P_j называется множество всех кортежей X, длины n принадлежащих отношению Р_i и не принадлежащих P_j: Р_i \ P_j = { X | X Î Р_i и Х Ï P_j }.

Пример. Если Р = {(a,b,d), (b,c,e)}, Q ={(a,b,d), (b,d,e)}, то P Q ={(a,b,d), (b,c,e), (b,d,e)}, P Q ={(a,b.d)}, P \ Q = {(b,c,e)}.

Декартовым произведением Р_i ´ P_j двух отношений Р_i и P_j называются множество всех кортежей z таких, что z – конкатенация кортежей x Î Р_i и y Î P_j: , где , если х =(х₁,…,x_r), y =(y₁,…,y_s). Итак .

Пример Если Р ={(a,b),(b,c)}, Q ={(b,c,a),(c,a,a)}, то {(a,b,b,c,a),(a,b,c,a,a),(b,c,b,c,a),(b,c,c,a,a)}.

Алгебры отношений используются для формализации реальных объектов. Рассмотрим, применение алгебры отношений при создании информационного обеспечения – разработке реляционной базы данных. Основой построения реляционной базы данных является двумерная таблица. Каждый i – й столбец таблицы соответствует i – му домену. Если n – местное отношение R_n содержится в D₁ ´ D₂ ´… D_n, то i – м доменом отношения R_{n ,} где i = 1,…, n, называется множество D_i.

Строка таблицы соответствует кортежу значений доменов, находящихся в отношении R_n.

Пример. Рассмотрим 4-местное отношение R₄ (расписание экзаменов).

R4	D1	D2	D3	D4
	А – 1 А - 2 А – 2 А – 1 А – 1 А - 2	Информатика Физика Анализ Физика Анализ Информатика	10 января 10 января 15 января 16 января 21 января 21 января	Ауд. 320 Ауд. 324 Ауд. 324 Ауд. 320 Ауд. 324 Ауд. 320

Отношение R₄ является подмножеством декартова произведения D ₁´ D ₂´ D ₃´ D ₄, и поэтому каждое из множеств D_i является доменом:

- домен D ₁ (группа) содержит значения А-1, А-2, то есть D ₁ = {A – 1, A – 2};

- домен D ₂ (дисциплина) - D ₂ ={Информатика, Физика, Анализ};

- домен D ₃ (дата) – D ₃ = {10 янв., 16 янв., 21 янв.};

- домен D ₄ (аудитория) – D ₄ = {Ауд.320, Ауд. 324}.

Порядок столбцов в таблице фиксирован, а строки в общем случае располагаются произвольно. Цифры первого столбца 1,2,…,6 являются идентификаторами отношения R ₄.

Таким образом, каждому отношению можно поставит в соответствие определенную таблицу.

1.4.2. Реляционная алгебра

Для преобразования отношений используется реляционная алгебра. Носитель реляционной алгебры представляет собой множество отношений, а набор операций кроме введенных операций È, Ç, \, ´ включает специальные операции над отношениями - выбор, проекцию и соединение.

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

Например с помощью операции выбора из отношения R ₄ (расписание экзаменов), строится, например, отношение (расписание экзаменов по физике). Результатом операции выбора являются строки, в которых домен D ₂ представлен значением «Физика»,это 2-я и 4-я строки. В результате получается:

R4	1	D2	D3	D4
	А-2 А-1	Физика Физика	10 января 16 января	Ауд. 324 Ауд. 320

Результатом операции проекции отношения R_nÍ А₁´А₂´…´Аn на А_i1, А_i2, …, А_im, где { i₁,…,i_m }Í{1,2,…, n } i_j<i_k при j<k, называется множество

{(a_i1, a_i2, …, a_im)|(a_1, a₂,…, a_n)Î R_n }. Например, p ₁ ^Rn = { a₁ |(a₁,a₂,…,a_n)Î R_n }.

Операция проекции определяет построение «вертикального» подмножества отношения, то есть из кортежей удаляются координаты, соответствующие невыделенным доменам.

Например, проекция p_2,3^R4 отношения R ₄ определяет множество пар, каждая из которых содержит название дисциплины и дату:

p2,3R4	D2	D3
	Информатика Физика Анализ Физика Анализ Информатика	10 января 10 января 15 января 16 января 21 января 21 января

Операция соединения по двум таблицам, имеющим общий домен, позволяет построить одну таблицу, каждая строка которой! образуется соединением двух строк исходных таблиц. Из заданных таблиц берут строки, содержащие одно и то же значение общего домена; общему домену ставится в соответствие один столбец.

Например, найдем по двум заданным таблицам R₄ и R¢₄

R4	D1	D2	D3	D4
	А – 1   А - 2	Информатика   Физика	10 января   10 января	Ауд. 320   Ауд. 324

R¢4	D1	D2	D3	D4
	А – 2   А – 1	Анализ   Физика	15 января   16 января	Ауд. 324     Ауд. 320

Результат соединения по домену D₁

R7	D1	D2	D3	D4	D¢2	D¢3	D¢4
	А – 1   А - 2	Информат   Физика	10 янв   10 янв	А -320 А -324	Физика   Анализ	16янв   15янв	А -320   А -324

В данном примере кортежи соединяются по условию равенства соответствующих координат, соединяющих кортежи, то есть а = (a₁,..., a_i,..., a_n) и b = (b₁,...,b_i,..., b_n), когда a_i = b_i.

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

2. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

2.1. АЛГЕБРА ВЫСКАЗЫВАНИЙ

2.1.1. Общие понятия

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

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

Математическая логика имеет дело с высказываниями. Высказывание - это повествовательное предложение, о котором имеет смысл говорить, что оно истинно или ложно, но ни то и другое вместе. Обычно, высказывания обозначаются большими буквами латинского алфавита, а их значения, то есть истина и ложь – 1 и 0 соответственно.

Логическая структура сложного высказывания. В процессе рассуждений (не только в математики) из одних высказываний формируются другие, так называемые сложные высказывания, полученные из элементарных с помощью частицы «НЕ» или путем соединения элементарных высказываний с помощью связок «И», «ИЛИ», «ЕСЛИ..,ТО» ТОГДА И ТОЛЬКО ТОГДА, КОГДА» и других. Эти связки обозначают определенные логические связи между высказываниями. Их можно рассматривать как некоторые операции над высказываниями. Эти операции позволяют судить об истинности или ложности сложного высказывания по истинности и ложности составляющих его высказываний.

2.1.2. Операции над высказываниями (законы логики)

1. Отрицание ` А - означает, что высказывание, которое истинно, когда А - ложно и ложно, когда А - истинно. В обычной речи оно соответствует частице «НЕ».

2. Конъюнкция А Ù В означает высказывание, которое истинно в том случае, когда А и В оба истинны. Соответствует связки “И”.

3. Дизъюнкция А Ú В означает, что высказывание истинно в том случае, когда истинно одно из высказываний А или В. Соответствует связке «ИЛИ».

4. Импликация А ® В означает высказывание, которое ложно тогда и только тогда, когда А - истинно, а В - ложно. Соответствует связки «ЕСЛИ..,ТО…».

5. Эквивалентность А «В означает высказывание, которое истинно тогда и только тогда, когда А и В оба истинны или оба ложны. Соответствует связке «ТОГДА И ТОЛЬКО ТОГДА, КОГДА».

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