Замыкание отношений.

Рефлексивным замыканием ρ_R отношения ρ на множестве М называется пересечение всех рефлексивных отношений, содержащих данное отношение.

ρ ρ_R

0 0 1 1 0 1 - ставим единицы на главной диагонали. 1 1 0 1 1 0 0 0 0 0 0 1

Коммутативным замыканием ρ_К отношения ρ на множестве М называется пересечение всех коммутативных отношений, содержащих данное отношение.

ρ ρ_R

0 0 1 0 1 1 - делаем матрицу симметричной 1 1 0 1 1 0 (можно заменять только нули на 0 0 0 1 0 0 единицы)

Транзитивным замыканием ρ_Т отношения ρ называется пересечение всех транзитивных отношений, содержащих данное.

Транзитивное замыкание можно отыскивать двумя способами: 1) аналитически, путем перемножения матриц и 2) графически.

1): пусть дана матрица А отношения, тогда а) находим произведение А*(А+Е)=А₁, которая будет содержать нулей не больше, чем матрица А; б) находим А₁*(А+Е)=А₂ и т.д. в) вычисления проводят до тех пор, пока не установятся нули.

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

Типы бинарных отношений.

1. отношение эквивалентности – это отношение ρ, если это ρ: а) рефлексивное, б) симметричное и в) транзитивное. Пример: параллельность на множестве прямых, ‘=’. Не эквивалентное: перпендикулярность на множестве прямых. Отношение эквивалентности устанавливается между элементами одного множества и разбивает множество на непересекающиеся подмножества, которые в сумме дают всё множество. Причем каждое из этих подмножеств зовут классом эквивалентности. Все элементы, попавшие в один класс, считаются эквивалентными между собой, а элементы разных классов между собой не эквивалентны. Пример: M={2,3,4,5,6,7,8}; {2,4,6,8}- отношение «четные» и {3,5,7} – отношение нечетные. Если составить множество из всех классов эквивалентности множества М, то получим множество, которое зовут фактор-множество относительно отношения эквивалентности M\ ~. M\ ~{{2,4,6,8},{3,5,7}} – множество множеств. Отношение эквивалентности разбивает заданное множество на подмножества по некоторому признаку. Верно и обратное: если некоторое множество М разбить на непересекающиеся подмножества, которые в сумме дают множество М, то это разбиение определяет на множестве М отношение эквивалентности. При этом считается, что все элементы, попавшие в один класс, эквивалентны между собой, а различных классов – не эквивалентны.

2. отношение порядка. Бинарное отношение зовут отношением порядка, если оно несимметрично и транзитивное. (ху) – читаем «х предшествует, подчиняется у». Порядок может быть строгим, т.е. если пара (х,у)Îρ, то пара (у,х)ρ. Пример: отношение ‘<’. Множество, на котором введен порядок, зовут упорядоченным. Если отношение рефлексивно, антисимметрично и транзитивно, то оно зовется отношением частичного порядка (не строгого). Пример: ‘<=’; не является таковым ‘=’,’ ≠’. Если все элементы частично упорядоченного множества сравнимы между собой (т.е для некоторых элементов (х,у)ÎМ верно х=у или у=х), то множество М зовут линейно упорядоченным, иначе оно не является линейно упорядоченным. Пример: ‘<=’ – множество упорядоченно на хÎR; ‘’ – не является линейно упорядоченным, т.к. не всегда верно АВ.

Отображение и функции.

Отображение: пусть имеем два множества Х и У. Отображением множества Х во множество У (пишем так: f: XY) называется f-правило, по которому каждому элементу х из Х ставится в соответствие единственный элемент у из У. y=f(x). Это отображение осуществляется с помощью функции y=f(x). У зовут образом Х, а Х зовут прообразом У. Если не для всех х из Х есть соответствие у из У, то это не отображение.

Свойство отображений:

1. f: xy зовут сюрьективным, если каждый элемент уÎУ обладает хоть одним прообразом. Если Х и У – конечные множества, то сюрьекцию можно осуществить, если мощность Х не меньше мощности У: |X|>=|Y|. Пример: является с. y=x³, не является – y=x².

2. f: xy зовут инъективным, если каждый образ имеет ровно один прообраз. х1,х2 ÎХ, f(x1)=f(x2) => x1=x2. если множество конечно, то инъекция осуществима тогда, когда |X|<=|Y|. Пример: явл. и. – y=e^x, не и. - y=x², т.к. у(х)=у(-х).

Если отображение одновременно сюрьективно и инъективно, то его зовут биективным, или взаимно однозначным соответствием (пример: у=2х-3).

3. обратным отображением f^—1 множества У во множество Х зовут множество таких х, что f(x)=y; f^-1(y)={x|f(x)=y}. При обратном отображении образы и прообразы меняются местами => обратное отображение может осуществиться только тогда, когда отображение f: x®y биективное. (f^-1)^-1=f. Обратное отображение можно определить для инъекции, не являющейся сюрьекцией, но это будет частичным отображением, т.е. отображением, заданном на некотором подмножестве общего множества, которое в этом случае зовут областью определения отображения. Пример: f:y=a^x, f^-1:x=log_ay. Если у нас отображение сюрьективное, но не инъективное, то частичное обратное отображение построить нельзя.

Связь между отображением и бинарными отношениями. ρXY; (x,y) – множество упорядоченных пар. f: x®y (x,f(x))=(x,y) – тоже множество упорядоченных пар. Итак, отображение есть тоже бинарное отношение. Но не всякое бинарное отношение является функцией. По определению функции каждому хÎХ соответствует единственное уÎУ, что на языке отношений пишется так: (x,y)ρ и (x,z)ρ, то y=z. Пример: ρ={(1,2),(1,3),(2,4)} – это бинарное отношение, но не функция. ρ={(1,2),(3,2)} – f. Очевидно, используя бинарные отношения, можно сказать, что обратное отношение ρ^-1 будет функцией, если различным х соответствуют различные у. Пример: ρ={(1,2),(3,2)}; ρ^-1={(2,1),(2,3)}- уже не функция.

Булевы функции.

Основные способы задания.

E={0,1}. f: Eⁿ®E – отображение ЕЕЕ…Е®Е называется булева функция от переменных y=f(x1,…,xn), (x1,…,xn)Eⁿ. БФ – двоичная функция двоичных переменных. f (x̃)=f(x1,…,xn). f(0…0)=f(0̃), f(1…1)=f(1̃). y=f(x), x=0,1; y=f(x1,x2). БФ можно задать кубически. При этом область определения – вершины n – мерного куба.

БФ может быть задана таблично, причем все наборы f(x,y,z) условимся заносить в порядке возрастания их десятичных эквивалентов.

x y z f f(10101110) – канонический набор. Если мы имеем 0 0 0 1 функцию n переменных, то количество наборов = 2ⁿ=к … Т.к. переменные принимают конечное число значений,

1 1 1 0 то и БФ-й от n переменных будет конечное число. 2^α=2^к

Изучать БФ, используя табличное задание можно, если число переменных невелико. Иногда удается в функции сократить число переменных, причем свойства функции от этого не меняются. Переменная x_i называется существенной, если удается найти такой набор α_i, что значения f(α₁,…, α_i-1,0, α_i+1,… α_n)≠ f(α₁,…, α_i-1,1, α_i+1,… α_n). Существенная зависимость означает невозможность определения значений функции без использования переменной x_i. Переменная x_i называется фиктивной, если для всех наборов f(α₁,…, α_i-1,0, α_i+1,… α_n)= f(α₁,…, α_i-1,1, α_i+1,… α_n).