Бинарное отношение, удовлетворяющее условиям рефлексивности, симметричности и транзитивности называют отношением эквиваленции. Такими отношениями являются “..=..”, “..быть похожим..”, “..быть родственником..”.
Отношение эквиваленции обозначают r~(xi, xi) или ~(xi, xi). Отношение r~ позволяет формировать классы эквиваленции по образцу хa, в виде подмножества множества X, т.е. Ka ={x| r~(x, xa)=1, x, xaÎX}ÍX.
Два класса эквиваленции не имеют общих элементов множества Х.
Попарно различимые классы эквиваленции Ka1, Ka2,...Kan позволяет выполнять разбиение множества Х на подмножества, т.е. Х={Хa1, Хa2,..,Хan}.
Бинарные отношения, удовлетворяющие условиям рефлексивности, антисимметричности и транзитивности называют отношением частичного порядка. Такими отношениями являются “..³..”, “..£..”, “..быть не старше..” и т.п..
Отношение порядка обозначают для элементов множества: r£(xi, xi) или
£( xi, xi), а для подмножеств множества: rÍ(Xi, Xj) или Í(Xi, Xj). Задание отношения £(xi, xj) позволяет формировать частичный порядок элементов множества X, а задание отношения Í(Xi, Xj) – частичный порядок на подмножествах множества X.
Например, пусть даны множества Х0={1, 2, 3, 4, 5, 6}, X1={1, 2, 3, 4},
X2={2, 3, 4, 5}, X3={2, 3, 4}, X4={3, 4, 5}, X5={2, 3}, X6={3, 4}, X7={4, 5},
X8={2, 4}.
Какой между ними может быть установлен порядок? Анализ следует начинать с множеств, имеющих наименьшее число элементов.
Тогда X8ÍX3ÍX2ÍX0 или X8ÍX3ÍX1ÍX0, X7ÍX4ÍX2ÍX0, X6ÍX4ÍX2ÍX0 или X6ÍX3ÍX2ÍX0 или X6ÍX3ÍX1ÍX0, X5ÍX3ÍX2ÍX0, X5ÍX3ÍX1ÍX0.
Одной из важных характеристик упорядоченного множества является наличие граней. Если на множестве X задан частичный порядок £(xi, xj), то среди элементов множества X найдется такой элемент xa, для которого выполняется условие £(xi, xa) и £(xj, xa) и найдется такой элемент xb, для которого выполняется условие £(xb, xi) и £(xb, xj).. В общем случае для некоторых элементов множества X могут не существовать xa и xb или быть неединственными. Тогда наименьший элемент xa формирует верхнюю грань для элементов xi и xj, что обозначают так: xa=Sup Xi, где Xi={xi, xj}ÍX, а наибольший элемент xb формирует нижнюю грань для элементов xi и xj, что обозгачают так: xb=Inf Xi, где Xi={xi, xj}ÍX.
Бинарное отношение, удовлетворяющее условиям антирефлексивности, асимметричности и транзитивности называют отношением строго порядка. Такими отношениями являются “..>..”, “..<..”, “..быть родителем..”, “быть частью”, “быть подчиненным” и т.п. Отношение строгого порядка обозначают для элементов множества: r<(xi; xi) или <(xi; xi), а для подмножеств множества: rÌ(Xi;Xj) или Ì(Xi;Xj). Примерами упорядоченных множеств являются целые числа, упорядоченные правилом n=(n+1) или буквы, упорядоченные алфавитом и т.п.
Функции, область определения и область значения которых принадлежит одному множеству, называют операцией, т.е. fi: X®X или fi: Xn®X.
A=<X, F>,
где X={x1, x2,..xm} - носитель алгебры;
F={f1, f2,.. } - cигнатура алгебры, содержащая унарные и бинарные операции.
Бинарные операции обладают свойствами:
коммутативности - xifkxj=xjfkxi, т.е. операнды можно менять местами,
ассоциативности - xifk(xjfkxk)=(xjfkxj)fkxk, т. е при исполнении одной операции fk скобки можно не расставлять, а операцию исполнять в любом порядке,
дистрибутивности - xifk(xjfmxk)=(xifkxj)fm(xifkxk), т. е. при исполнении двух различных операций fk и fm первая операция fk исполняется с каждым операндом второй операции fm, а вторая операция fm с результатами исполнения первой операции fk,
идемпотентности – xifkxi=xi, т.е. результатом исполнения бинарной операции над одним операндом будет значение операнда,
поглощения – xifk(xifmxj)=xi, т. е. при исполнении двух различных бинарных операций fk и fm, но содержащих один общий операнд xi, результатом их исполнения будет значение операнда xi.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.