Частично упорядоченные множества

Связь представлений булевых функций

Классификация булевых функций

Частично упорядоченные множества

Множество X называется упорядоченным(линейно упорядоченным), если для любых x,y,zÎX выполнены свойства:

1) рефлексивность (x£x);

2) антисимметричность (если x£y, y£x,то x=y);

3) транзитивность (если x£y, y£z,то x£z);

Элемент а ч.у.м. X называется максимальным (минимальным) в X, если он не покрывается никаким другим элементом X (не покрывает никакого другого элемента X).

Если а£b, то интервалом [а,b] в ч.у.м. X называется подмножество X вида:

[а,b]={xÎX: а£x£b}.

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

Конечное ч.у.м. X часто задается диаграммой, представляющей собой специальный неориентированный граф (определение графа дано в разделе 3.4) с множеством вершин X, где пара (x,y) соединена ребром Û y>¾x (см. рис. 3.1 а,б,в). Специфика такого графа состоит в том, что все вершины расположены на нескольких уровнях, при этом если x<y, то вершина y расположена на более высоком уровне, чем вершина x. Число уровней не превышает числа вершин.

Прямым произведением ч.у.м. áX, ñ и ч.у.м. áY, ñ называется ч.у.м. áX´Y,£ñ, где (x,y)£(x¢,y¢) Û x x¢ и y y¢ для любых x,x¢ÎX и y,y¢ÎY. Если сомножители одинаковы, то имеет место декартова степень ч.у.м.

Прямой суммой ч.у.м. áX, ñ и ч.у.м. áY, ñ называется ч.у.м. áXÈY,£ñ, где x£y для x,yÎXÈY, только если x,yÎX и x y, либо x,yÎY и x y.

Цепь в ч.у.м. áX,£ñ - это подмножество С множества X, обладающее свойством линейности. Цепь С называется полной (неуплотняемой, насыщенной) в X, если она либо состоит из одного элемента, либо из отношения y>¾x в С следует, что y>¾x и в X.

Элементы x,y ч.у.м. X называются сравнимыми, если они принадлежат некоторой цепи, и несравнимыми в противном случае. Несравнимость элементов x и y обозначим xúïy. Таким образом, в цепи нет несравнимых элементов.

Антицепь в ч.у.м. áX,£ñ - это подмножество множества X, любые два различных элемента которого несравнимы.

Длину цепи С (обозначим её l(C)) определим как длину соответствующего пути в диаграмме, то есть l(C)=ïСï-1.

Длина ч.у.м. X (обозначим её l(X)) определяется как длина самой длинной из цепей множества X,то есть l(X)=n, если в X найдётся цепь длины n и не найдётся цепи длины n+1.

Ширина ч.у.м. X (обозначим её h(X)) определяется как мощность самой мощной из антицепей множества X, то есть h(X)=п, если в X найдётся антицепь, состоящая из n элементов и не найдётся антицепи, состоящей из n+1 элементов.

Теорема 3.2 (Дилуорс). Ширина конечного ч.у.м. X равна наименьшему числу непересекающихся цепей, покрывающих X.

Пусть имеются ч.у.м. áX,£ñ и áY, ñ. Функция f:X®Y называется сохраняющей порядок (или изотонной, или гомоморфизмом ч.у.м.), если для любых x,x¢ÎX со свойством x£x¢ выполнено f(x) f(x¢). Если гомоморфизмч.у.м. f есть биекция, то он называется изоморфизмом ч.у.м. Изоморфизм ч.у.м. áX,£ñ с самим собой называется автоморфизмом ч.у.м. Биекция X«Y, при которой частичные порядки £ и взаимно инвертируются, называется антиизоморфизмом ч.у.м. (или обратным изоморфизмом ч.у.м.).

Ч.у.м. áX,£ñ и áY, ñ называются изоморфнымиили антиизоморфными(обозначается áX,£ñ@áY, ñ или X@Y), если между ними существует соответственно изоморфизм или антиизоморфизм.

Для любого отношения частичного порядка £ имеется обратное к нему отношение частичного порядка ³. В ч.у.м. áX,£ñотношение x£x¢ выполнено Û отношение x¢³x выполнено в ч.у.м. áX,³ñ. Ч.у.м. áX,³ñ называется двойственным к ч.у.м. áX,£ñ и наоборот.

Если имеется утверждение о ч.у.м. áX,£ñ, то заменяя в нем все вхождения £ на ³, получаем утверждение о ч.у.м. áX,³ñ, двойственное к исходному утверждению. Таким образом, для множеств с частичным порядком выполняется принцип двойственности, состоящий в том, что любое утверждение имеет место в áX,£ñ Û двойственное ему утверждение имеет место в áX,³ñ. Например, если Y – антицепь в áX,£ñ, то Y – антицепь и в áX,³ñ и т.д.

Полурешетки и решетки

Пусть Y – подмножество ч.у.м. X и xÎX. Элемент x называется нижней (верхней) границейч.у.м. Y, если x£y (y£x) для всех yÎY. Нижняя (верхняя) граница x множества Y называется его нижней (верхней) гранью, если z£x (x£z) для любой нижней (верхней) границы z множества Y. При этом обозначается: x=infY (x=supY).

Для (x,y)ÎX² обозначим: inf(x,y)=xÙy, sup(x,y)=xÚy. Из определения верхней и нижней грани следует, что для элементов x,yÎX выполнены свойства:

x£y Û xÙy=x Û xÚy=y.

Ч.у.м. X называется нижней полурешёткойили Ù-полурешёткой, если xÙyÎX для всех x,yÎX. Ч.у.м. X называется верхней полурешёткойили Ú-полурешёткой, если xÚyÎX для всех x,yÎX. Если X есть Ù-полурешётка (Ú-полурешётка), то inf(x,y) (sup(x,y)) есть функция X²®X.

Ч.у.м. X называется решёткой, если X является и нижней, и верхней полурешёткой.

В Ú-полурешётке (Ù-полурешётке) X элемент supX (infX) определен однозначно. Действительно, если это не так, то x=supX и y=supX. Так как X есть Ú-полурешетка, то x,yÎX, и по определению верхней грани одновременно выполнено x£y и y£x. Отсюда по свойству 2) из определения ч.у.м. имеем: x=y. Следовательно, в нижней (верхней) полурешётке X имеется нуль, т.е. наименьший (единица, т.е. наибольший) элемент. Обозначим нуль и единицу соответственно 0_X и 1_X (кратко 0и 1). В решётке X имеется и 0_X, и 1_X.

Атомом нижней (коатомом верхней) полурешётки Xназывают всякий элемент x со свойством x>¾0_X (1_X>¾x).

В нижней (верхней) полурешётке Xпорядка большего 1 каждый отличный от 0_X (от 1_X) элемент или совпадает или сравним хотя бы с одним из атомов (коатомов) решётки.

Гомоморфизмы f:X®Y для полурешеток и решеток X,Y допускают различные определения.

1. Как изотонная функция ч.у.м.

2. Как Ù-гомоморфизм или гомоморфизм нижних полурешеток: то есть f(xÙy)=f(x)Ùf(y) для всех x,yÎX.

3. Как Ú-гомоморфизм или гомоморфизм верхних полурешеток: то есть f(xÚy)=f(x)Úf(y) для всех x,yÎX.

4. Как решеточный гомоморфизмили гомоморфизм решеток: то есть f есть и Ù-гомоморфизм и Ú-гомоморфизм.

Биективный гомоморфизм решеток (Ù-, Ú-гомоморфизм) называется изоморфизмом решеток(Ù-, Ú-изоморфизмом).

Функция y:X¢®Y называется ограничением(или подфункцией)функцииf на множестве X¢, где X¢ÍX, если f(x)=y(x)для любого xÎX¢.

Нижняя (верхняя) полурешетка áY,£ñ называется подполурешеткой нижней (верхней) полурешетки áX,£ñ, если YÍX и inf(x,y) (sup(x,y)) в полурешетке áY,£ñ совпадает с ограничением функции inf(x,y):X²®X (sup(x,y):X²®X) на множество Y². Решетка áY,£ñ называется подрешеткой решетки áX,£ñ, если áY,£ñ является и нижней, и верхней подполурешёткой решетки áX,£ñ.

Утверждение 3.1. Пусть áY₁,£ñ,…,áY_k,£ñ - нижние (верхние) подполурешетки нижней (верхней) полурешетки áX,£ñ. Тогда á ,£ñ - нижняя (верхняя) подполурешетка полурешетки áX,£ñ.

t Пусть Y= . По условию Y_i – нижняя полурешетка, поэтому inf(x,y)ÎY_i при любых x,yÎY_i, i=1,…,k. Следовательно, inf(x,y)ÎY при любых x,yÎY. Отсюда подмножество Y нижней полурешетки X является нижней полурешеткой.

По условию Y_i – нижние подполурешетки полурешетки X, поэтому inf(x,y) в полурешетке X совпадает с inf(x,y) в полурешетке Y_i для всех x,yÎY_i, i=1,…,k, и, следовательно, совпадает с inf(x,y) в полурешетке Y для всех x,yÎY. Значит, Y – нижняя подполурешетка полурешетки X. Для верхних подполурешеток утверждение доказывается двойственно. u

Утверждение 3.2. Если áX, ñ и áY, ñ - нижние (верхние) полурешетки, то и их прямое произведение - также нижняя (верхняя) полурешетка.

t Пусть x,x¢ÎX, a=xÙx¢ и y,y¢ÎY, b=yÙy¢, тогда по условию aÎX и bÎY. Значит, (a,b)ÎX´Y и (a,b) – нижняя граница пары ((x,y),(x¢,y¢)). В силу определения элементов a и b любая другая нижняя граница (a¢,b¢) этой пары удовлетворяет неравенствам: a¢ a и b¢ b. Значит, (a¢,b¢)£(a,b), и, следовательно, (a,b) - нижняя грань пары ((x,y),(x¢,y¢)). Отсюда áX´Y,£ñ - нижняя полурешетка. Двойственно, получаем: áX´Y,£ñ - верхняя полурешетка. u

Пусть YÍX,где áX,£ñ - нижняя (верхняя) полурешетка. Нижней (верхней) подполурешеткой, порожденной множеством Y (обозначается á[Y],£ñ) назовем минимальную нижнюю (верхнюю) подполурешетку полурешетки áX,£ñ, содержащую множество Y. Полурешетка á[Y],£ñ содержится во всякой нижней (верхней) подполурешетке, содержащей Y.

Если Y={y₁,…,y_m} – конечное множество, то нижняя (верхняя) подполурешетка á[Y],£ñ совпадает с множеством {infY¢:Y¢Í2^Y, Y¢¹Æ} ({supY¢:Y¢Í2^Y, Y¢¹Æ}).

Для решетки X функции Ù и Ú определены на X² и принимают значения в X, иначе говоря, являются бинарными операциями на X. Некоторые свойства операций Ù и Ú на решетках аналогичны свойствам умножения и сложения в различных алгебрах. А именно, для любых x,y,zÎX выполнены свойства:

1) идемпотентность: xÙx= x, xÚx= x;

2) коммутативность: xÙy=yÙx, xÚy=yÚx;

3) ассоциативность: xÙ(yÙz)=(xÙy)Ùz, xÚ(yÚz)=(xÚy)Úz;

4) поглощение: xÙ(yÚx)=xÚ(yÙx)=x;

Элемент x решетки X, где x¹0_X,называется Ú-неразложимым, если из x=yÚz следует, что x=y или x=z; Ù-неразложимостьопределяется двойственно.

Пусть X - решетка, x,y,zÎX. Максимальный элемент y со свойством xÙy£z (со свойством xÙy=0_X) называется относительнымÙ-псевдодополнением x в z (Ù-псевдодополнением x), обозначим эти элементы соответственно x^Ù(z) и x^Ù. Минимальный элемент y со свойством xÚy³z (со свойством xÚy=1_X) называется относительным Ú-псевдодополнением x в z (Ú-псевдодополнением x), обозначим эти элементы соответственно x^Ú(z) и x^Ú.

Утверждение 3.4. В конечной дистрибутивной решетке X элементы x^Ù(z), x^Ù, x^Ú(z) и x^Ú существуют для любых x и z и определены однозначно.

t Рассмотрим элемент x^Ù(z), для остальных элементов доказательство аналогично. Пусть y и y¢ - различные Ù-псевдодополнения x в z, тогда y¢úïy, иначе один из них не максимальный. Для Ù-псевдодополнений x в z выполнено:

xÙy£z; xÙy¢£z.

Значит, z - верхняя граница для xÙy и xÙy¢. Отсюда

(xÙy)Ú(xÙy¢)£z.

Тогда, используя условие дистрибутивности, получаем:

xÙ(yÚy¢)£z.

Так как y¢úïy, то y<yÚy¢ и y¢<yÚy¢, что вкупе с последним соотношением противоречит определению элементов y и y¢. u