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

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

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

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

Множество 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 =inf Y (x =sup Y).

Для (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 элемент sup X (inf X) определен однозначно. Действительно, если это не так, то x =sup X и y =sup X. Так как 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 ],£ñ совпадает с множеством {inf Y ¢: Y ¢Í2 ^Y, Y ¢¹Æ} ({sup Y ¢: 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