FN_Alg19 (Лекции 2009), страница 5

Двойственность в симметричных полукольцах. Свойства: а) 0 6 x 6 1. б) тождества поглощения x + xy = x и x(x + y) = x; в) x 6 y ⇔ xy = x; г) xy = 1 ⇒ x = y = 1;д) x1 x2 . . . xk = inf {x1 , x2 , . . . , xk }. Булева алгебра — симметричное полукольцо, в котором дополнительно есть унарная операция — дополнение x, удовлетворяющая аксиомам x+x = 1, x·x = 0.Свойства: 1) единственность; 2) нильпотентность x = x; 3) законы де Моргана x + y = x · y,xy = x + y. Пример булевой алгебры — двухэлементная булева алгебра B. Декартово произведениебулевых алгебр, декартова степень булевой алгебры и булев куб Bn . Булевы векторы.

Теорема:любая конечная булева алгебра изоморфна Bn .ÌÃÒÓÔÍ-1219.5. Симметричные полукольцаÔÍ-12ÌÃÒÓÌÃÒÓ63ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ64Теорема 19.12. В симметричном полукольце K для каждого x ∈ K элемент x, удовлетворяющий условиям (19.3), определен однозначно.J Рассмотрим два элемента x1 и x2 , удовлетворяющие равенствамx + x1 = 1,xx1 = 0,x + x2 = 1,xx2 = 0.ÔÍ-12откуда x2 6 x1 .

Повторив это рассуждение со вторым и третьим равенствами, получаем x1 66 x2 . Следовательно, x1 = x2 . IИз доказанной теоремы вытекает, что дополнение в симметричном полукольце полностьюопределяется свойствами сложения и умножения. Дополнение в симметричном полукольце может и не существовать, но если его можно ввести, то единственным способом.Примером симметричного полукольца, в котором нет дополнения, служит алгебра Ua,b == ([a, b], max, min, a, b).

Если бы дополнение существовало, должны были выполняться равенства max {x, x} = b, min{x, x} = a, что возможно только для x = a или x = b.Свойства дополнения:1) нильпотентность x = x;2) законы де Моргана x + y = x · y, xy = x + y;3) xy = 0 ⇒ x 6 y;4) x + y = 1 ⇒ y 6 x.ÌÃÒÓJ Первое свойство вытекает из симметричности равенств (19.4). Докажем второе свойство —законы де Моргана. Отметим, что два закона де Моргана являются двойственными друг кдругу.

Поэтому достаточно доказать один из них, например первый.Первый закон де Моргана можно интерпретировать так: элемент x · y является дополнениемк элементу x + y. Чтобы убедиться в этом, достаточно проверить выполнение равенств (19.4).Первое равенство (используем дистрибутивность сложения относительно умножения):ÔÍ-12ÌÃÒÓx1 x2 = xx2 + x1 x2 = x2 ,ÌÃÒÓÌÃÒÓУмножив первое равенство на x2 и учтя, что xx2 = 0, находимÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓВторое равенство:x y(x + y) = x(yx + yy) = xyx = 0y = 0.Третье и четвертое свойства двойственны друг другу. Можно ограничиться доказательством лишь одного из них. Если xy = 0, тоxy = xy + xy = x(y + y) = x · 1 = x.ÔÍ-12ÔÍ-12x y + x + y = (x + x)(y + x) + y = y + x + y = 1 + x = 1.0 + 0 = 0,1 + 0 = 0 + 1 = 1 + 1 = 1,1 · 1 = 1,0 · 1 = 1 · 0 = 0 · 0 = 0.Операции этой алгебры можно определить как максимум и минимум.

При этом минимум совпадает с операцией умножения, а максимум можно определить выражением max {x, y} = x+y−xy.Рассмотрим булевы алгебры B1 , B2 , . . . , Bk . Тогда на декартовом произведении B1 ×B2 ×. . .. . . × Bk можно ввести структуру булевой алгебры, рассматривая на кортежах поэлементныеоперации:(x1 , x2 , . . . , xk ) · (y1 , y2 , .

. . , yk ) = (x1 · y1 , x2 · y2 , . . . , xk · yk ),(x1 , x2 , . . . , xk ) = (x1 , x2 , . . . , xk ).ÌÃÒÓ(x1 , x2 , . . . , xk ) + (y1 , y2 , . . . , yk ) = (x1 + y1 , x2 + y2 , . . . , xk + yk ),ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Пример булевой алгебры — двухэлементная булева алгебра B. Всего два элемента 0 и 1.Действие операций таковоÌÃÒÓÌÃÒÓРавенство xy = x равносильно условию x 6 y. IÌÃÒÓÌÃÒÓÌÃÒÓ65ÔÍ-12Несложно проверить выполнение аксиом булевой алгебры (включая равенства (19.3)). Полученная таким образом булева алгебра называется декартовым произведением булевыхалгебр B1 , B2 , .

. . , Bk . Частным случаем этой конструкции является декартова степеньB n булевой алгебры B. Декартову степень Bn двухэлементной булевой алгебры B называют n-мерным булевым кубом, а элементы этой алгебры, т.е. кортежи длины n из нулей иединиц, — n-мерными булевыми векторами.Булева алгебра Bn — пример конечной булевой алгебры (она содержит 2n элементов). Оказывается, что других конечных булевых алгебр нет. Чтобы доказать это, выделим в конечнойбулевой алгебре B определенные элементы. Наряду с естественным порядком x 6 y в B будемрассматривать строгий порядок x < y, означающий, что x 6 y и x 6= y.Элемент x 6= 0 алгебры B будем называть атомом, если не существует ни одного элементаy, удовлетворяющего условию 0 < y < x.

Если элемент x не является атомом, то для негоможно выбрать элемент x1 , для которого 0 < x1 < x. Элемент x1 либо атом, либо имеет x2 ,удовлетворяющий условию 0 < x2 < x1 . Таким образом, каждый элемент алгебры являетсяконцом цепочки последовательно убывающих элементов. В бесконечном случае такая цепочкаможет быть бесконечной (например, в U0,1 цепочка 1, 1/2, 1/3, . . . ). В конечной же алгебре Bтакая цепочка должна быть конечной. Самый маленький элемент в ней — атом, подчиненныйисходному элементу x.

Совокупность всех атомов конечной булевой алгебры образует своегорода базис в ней.Пусть a1 , a2 , . . . , ak — атомы в булевой алгебре B. Рассмотрим выражениеÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓ(19.5)где αi , βi ∈ {0, 1}, i = 1, k, то αi = βi , i = 1, k.J Отметим, что если a1 , a2 , . . . , ak — различные атомы, то произведение a1 a2 a3 .

. . ak отлично отнуля. Действительно, если a1 a2 a3 . . . ak = 0, то по свойству дополнения a1 a2 a3 . . . ak−1 6 ak . Нотак как ak — атом, то левая часть либо равна нулю, либо ak . Но во втором случае заключаем,что a1 6 ak , а это для двух различных атомов невозможно. Итак, a1 a2 a3 . . . ak−1 = 0. Повторяяпроцедуру, заключаем, что a1 = 0, что противоречит определению атома.Пусть a1 , a2 , . . .

, ak — различные атомы и имеет место равенство (19.5). Домножим равенство на произведение a2 a3 . . . ak−1 6 ak . Тогда в обеих частях равенства уничтожатся всеслагаемые кроме первого, поскольку в эти слагаемые будет входить произведение вида ai ai . Врезультате получим, чтоα1 a1 a2 a3 . . . ak−1 6 ak = β1 a1 a2 a3 . . .

ak−1 6 ak .Лемма 19.2. Для любого элемента y конечной алгебры B имеет место представлениеy = α1 a1 + α2 a2 + . . . + αn an ,где a1 , a2 , . . . , an — совокупность всех атомов алгебры B, а коэффициенты αi определяютсяследующим образом: αi = 1, если ai 6 y и αi = 0, если ai не подчинен y.ÔÍ-12Отсюда вытекает, что α1 = β1 , поскольку иначе один из этих коэффициентов равен нулю, авторой единице, а следовательно, одна часть равенства нулевая, а вторая — нет. Повторяя этирассуждения для остальных индексов, получим утверждение леммы. IÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12α1 a1 + α2 a2 + . . . + αk ak = β1 a1 + β2 a2 + . .

. + βk ak ,ÌÃÒÓÌÃÒÓЛемма 19.1. ЕслиÔÍ-12ÔÍ-12где αi либо нуль, либо единица булевой алгебры. Это выражение уместно назвать линейнойкомбинацией атомов a1 , a2 , . . . , ak . Фактически линейная комбинация — это сумма некоторогоатомов из рассматриваемой системыÌÃÒÓÌÃÒÓα1 a1 + α2 a2 + . . . + αk ak ,ÌÃÒÓÌÃÒÓ66J Положим y∗ = α1 a1 +α2 a2 +. . . αn an , где αi = 1 при ai 6 y и αi = 0 в противном случае.

Тогдаy∗ есть сумма всех атомов, подчиненных y и, следовательно, y∗ 6 y. Рассмотрим c = yy ∗ . Намдостаточно показать, что y 6 y∗ , а это равносильно соотношению c = yy ∗ = 0. Предполагая,что это соотношение неверно, заключаем, что c имеет хотя бы один подчиненный атом. Пустьэто a1 (иначе можно просто изменить нумерацию атомов). Значит, a1 6 c. Но тогда a1 6 y и всумме, представляющей y1 , α1 = 1. Отсюда заключаем, чтоYa1 c = a1 y · α1 a1 + α2 a2 + . .

. αn an = a1 yaj = 0,aj 6yтак как a1 входит в произведение. В то же время в силу неравенства a1 6 c имеем a1 c = a1 ,откуда a1 = 0, а это противоречит условию, что a1 — атом. Итак, предположение c 6= 0приводит к противоречию. Значит, c = 0 и y = y1 = α1 a1 + α2 a2 + . . . αn an . IÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓгде коэффициенты суммируются по правилу сложения элементов в B.

Аналогично проверяетсяравенство(α1 a1 + α2 a2 + . . . + αn an )(β1 a1 + β2 a2 + . . . + βn an ) = (α1 β1 )a1 + (α2 β2 )a2 + . . . + (αn βn )an ,в котором умножение коэффициентов есть умножение алгебры B (необходимо учесть, что произведение двух разных атомов равно нулю, поскольку должно быть не более каждого из атомов).Наконец, учитывая полученные равенства, а также равенство(элементу 1 подчинены все атомы алгебры), заключаем, что дополнением к элементу y = α1 a1 ++ α2 a2 + .

. . + αn an является элемент y = α1 a1 + α2 a2 + . . . + αn an , так какy + y = (α1 a1 + α2 a2 + . . . + αn an ) + (α1 a1 + α2 a2 + . . . + αn an ) == (α1 + α1 )a1 + (α2 + α2 )a2 + . . . + (αn + αn )an = a1 + a2 + . . . + an = 1y+y = (α1 a1 +α2 a2 +. . .+αn an )(α1 a1 +α2 a2 +. . .+αn an ) = (α1 α1 )a1 +(α2 α2 )a2 +. . .+(αn +αn )an = 0.Итак, построенное отображение биективно и сохраняет все операции, т.е. представляет собойизоморфизм.

IÔÍ-12иÌÃÒÓa1 + a2 + . . . an = 1ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓ(α1 a1 + α2 a2 + . . . + αn an ) + (β1 a1 + β2 a2 + . . . + βn an ) = (α1 + β1 )a1 + (α2 + β2 )a2 + . . . + (αn + βn )an ,ÌÃÒÓÔÍ-12и притом единственным образом. Это верно и для нуля алгебры: достаточно взять линейнуюкомбинацию с нулевыми коэффициентами. Каждому y ∈ B ставим в соответствие n-мерныйбулев вектор (α1 , α2 , . .

. , αn ) из коэффициентов линейной комбинации. Получим биективноеотображение ϕ: B → Bn . Покажем, что это отображение есть гомоморфизм булевых а лгебр,т.е. оно сохраняет три булевых операции. Для сложения это очевидно, посколькуÔÍ-12ÌÃÒÓy = α1 a1 + α2 a2 + . . . + αn an ,ÌÃÒÓÔÍ-12J Пусть a − 1, a2 , . . . , an — набор всех атомов конечной алгебры B. Согласно доказаннымлеммам, каждый элемент y 6= 0 представим в виде линейной комбинацииÔÍ-12ÔÍ-12Теорема 19.13.

Любая конечная булева алгебра изоморфна некоторой алгебре Bn .ÌÃÒÓТеорема 19.14. Каждое упорядоченное множество (M, 6), в котором каждое двухэлементное множество имеет точную верхнюю грань, есть полурешетка с операцией x + y = sup {x, y}.sup {sup {x, y}, z} = sup {x, y, z} = sup {x, sup {y, z}}.I*Здесь следует выделить случай x = y, в котором элементы x и y есть на самом деле один элемент идвухэлементного множества не возникает. В этом случае полагаем x + x = x.ÔÍ-12Во-первых, по условиям теоремы левая часть определена и является верхней гранью множества,составленного из элементов x, y, z.