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

Во-вторых, любая верхняя грань g множества из элементовx, y, z является верхней гранью множества из элементов sup {x, y} и z, т.е. sup {sup {x, y}, z} 66 g. Следовательно, sup {sup {x, y}, z} — точная верхняя грань множества {x, y, z}. В силупроизвольности x, y, z заключаем, чтоÌÃÒÓJ Очевидно, что формула x + y = sup {x, y} задает корректную операцию на упорядоченноммножестве, если каждое двухэлементное множество имеет точную верхнюю грань* . Остаетсяпроверить аксиомы решетки.

Но коммутативность и идемпотеность очевидны. Кроме того,очевидно и соотношениеsup {sup {x, y}, z} = sup {x, y, z}.ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12К понятию булевой алгебры можно подходить с различных сторон. Во-первых, булеву алгебру легко превратить в кольцо с единицей, если заменить булево сложение + операциейx⊕y = xy+xy. Можно непосредственно проверить, что относительно этой операции булева алгебра есть аддитивная группа и что умножение дистрибутивно относительно введенной операции.В результате мы получаем кольцо с идемпотентным умножением — булево кольцо. Наоборот,булево кольцо всегда коммутативно, а сложение удовлетворяет условию x + x = 0.

Заменив вбулевом кольце сложение операцией x + y + xy, получим симметричное полукольцо. В нем нетрудно ввести дополнение по формуле x = x+1. В этом случае xx = x(x+1) = x2 +x = x+x = 0,x + x = x + x + 1 = 0 + 1 = 1.Таким образом, теории булевых алгебр и булевых колец легко трансформируются одна вдругую. Еще один подход связан с понятием решетки.Полурешетка — коммутативная полугруппа, в которой операция идемпотентна. Идемпотентность операции означает, что в полурешетке, как и в полукольце, возникает отношениепорядка x 6 y ⇔ x + y = y. На полурешетку переносится теорема из теории полуколец о том,что конечное множество имеет точную верхнюю грань, равную сумме элементов множества.Поэтому операция полурешетки восстанавливается по отношению порядка согласно формулеx + y = sup {x, y}.Отметим, что не всякое упорядоченное множество можно превратить в полурешетку, в упорядоченном множестве не всякое конечное множество может иметь точную верхнюю грань.Например, зададим на множестве из трех элементов −1, 0, 1 отношение x 4 y ⇔ |x| < |y| илиx = y.

Тогда двухэлементное множество {−1, 1} не будет иметь ни одной верхней грани, апотому и точной верхней грани.ÌÃÒÓÌÃÒÓПолурешетка — коммутативная полугруппа с дополнительным свойством идемпотентности.Отношение порядка в полурешетке. Теорема: упорядоченное множество имеет структуру полурешетки, если любое двухэлементное множество имеет точную верхнюю грань. Двойственность.Верхняя (L, sup) и нижняя (L, inf) полурешетки упорядоченного множества.

Решетка — алгебра(R, ∨, ∧), которая относительно каждой операции полурешетка, а обе операции связаны тождествами поглощения a ∧ (a ∨ b) = a, a ∨ (a ∧ b) = a. Пример: любое симметричное полукольцоесть решетка. Пример: алгебра ((a, b), max, min) есть решетка, но не полукольцо (нет нуля и единицы). Двойственность порядков решетки. Теорема: любое упорядоченное множество, в которомлюбое двухэлементное множество имеет sup и inf, есть решетка. Решетка и дистрибутивность.Примеры недистрибутивных решеток (пентагон и диамант). Теорема: дистрибутивная решетка с0 и 1 есть симметричное полукольцо.ÌÃÒÓÔÍ-1219.6.

РешеткиÔÍ-12ÌÃÒÓÌÃÒÓ67ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓÌÃÒÓyx*Теорема 19.15. Дистрибутивная решетка, у которой каждая операция имеет нейтральныйэлемент (0 относительно объединения, 1 относительно пересечения) является симметричнымполукольцом.а это и есть аннулирующее свойство нуля решетки. IÔÍ-12J В силу симметрии достаточно убедиться, что выполняются аксиомы основного полукольца.Отметим, что в силу условий теоремы решетка является коммутативным моноидом с идемпотентной операцией и относительно решеточного объединения, и решеточного пересечения.

Решеточное пересечение дистрибутивно относительно решеточного объединения. Остается установить аннулирующее свойство нуля. Используя одно из тождеств поглощения, для любогоэлемента a решетки получаем0 ∧ a = 0 ∨ (0 ∧ a) = 0,ÌÃÒÓРешетка называется дистрибутивной, если каждая из ее операций дистрибутивна относительно другой.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12zможет нарушаться. Пусть x, y ∈ M1 , z ∈ M2 , причем y < x.

Тогдаy∨z = x∗ и x∧(y∨z) = x∧x∗ = x. В то же время (x∧y)∨(x∧z) = y∨x∗ = y.Частным случаем рассмотренной схемы является пентагон — упорядоченное множество их пяти элементов (рис. 19.1). Отношением неравенства связаны любые два элемента, расположенных на одном пути снизувверх.ÔÍ-12xÌÃÒÓПример 19.5. Рассмотрим объединение двух линейно упорядоченных множеств M1 и M2 ,имеющих общие наименьший x∗ и наибольший x∗ элементы (например, левая и правая полуокружности на плоскости, точки которых упорядочены по ординате). Выберем два элементаx1 и x2 .

Если эти элементы принадлежат одному линейно упорядоченному множеству, то онисравнимы, например x1 6 x2 . Тогда sup {x1 , x2 } = x2 и inf {x1 , x2 } = x1 . Если же эти элементыиз разных частей, то sup {x1 , x2 } = x∗ и inf {x1 , x2 } = x∗ . Теперь нетрудно убедиться в том,что равенство*x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)xÔÍ-12Примером полурешетки является любое симметричное полукольцо. Однако этим примеромпонятие полурешетки не исчерпывается. Алгебра ((a, b); max; min является полурешеткой, но неявляется симметричным полукольцом, так как обе операции не имеют нейтрального элемента.В полурешетке каждая из операций порождает свое отношение порядка, но два порядка всилу тождеств поглощения являются взаимно обратными. В самом деле, если x ∨ y = y, тоx ∧ y = x ∧ (x ∨ y) = x.

Иначе говоря из отношения x 6u y, соответствующего решеточномуобъединению, вытекает отношение y 6l x, соответствующее решеточному пересечению. В силусимметрии верно и обратное.Уже отмечено, что симметричное полукольцо есть решетка, а решетка может не быть симметричным полукольцом из-за отсутствия нуля и единицы. Второе расхождение между двумя алгебраическими структурами — свойство дистрибутивности каждой из операций относительнодругой. В решетке свойство дистрибутивности может отсутствовать.ÌÃÒÓÌÃÒÓÌÃÒÓ68На упорядоченном множестве M могут возникнуть две решеточных операции: одна — точная верхняя грань, другая — точная нижняя грань (это точная верхняя грань для обратногопорядка).

Для этого достаточно, чтобы любое двухэлементное множество имело и точнуюверхнюю грань, и точную нижнюю. При этом алгебру (M, sup) называют верхней полурешеткой, а алгебру (V, inf) — нижней полурешеткой.Решеткой называют алгебру (M, ∨, ∧) с двумя бинарными операциями ∨ (решеточноеобъединение) и ∧ (решеточное пересечение), которая, во-первых, является полурешеткой относительно каждой из двух операций, а во-вторых, эти операции связаны тождествамипоглощенияa ∧ (a ∨ b) = a, a ∨ (a ∧ b) = a.Рис. 19.1ÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19.

ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓÌÃÒÓ...............................................................................................9. Жорданова нормальная форма9.1. Корневые подпространства . . .9.2. Жорданова нормальная форма9.3. Комплексные корни . . . . . . .9.4. Теорема Кэли — Гамильтона .........................................................................................121214192013.

Операции над тензорами13.1. Понятие тензора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.2. Матричная запись тензоров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .13.3. Преобразование тензоров, записанных в матричной форме . . . . . .

. . . . . . . .2222232414. Множества и отношения14.1. Алгебра множеств . . . . . . . . . .14.2. Отображения и соответствия . . .14.3. Отношения и операции . . . . . . .14.4. Элементы математической логики14.5. Мощность множеств . . . . . . . ......262630323435.....363636363640..........................16. Кольца и поля16.1. Кольца . . . . . .

. . . . . . . . . . . .16.2. Специальные типы колец . . . . . . . .16.3. Гомоморфизмы колец и факторизация16.4. Модули и алгебры . . . . . . . . . . . .16.5. Алгебры на полем . . . . . . . . . . . .......................................................................................................................................................................................................................................................................................................................................................19.

Полукольца и булевы алгебры19.1. Определение полукольца . . .19.2. Ряды в полукольцах . . . . . .19.3. Замкнутые полукольца . . . .19.4. Системы линейных уравнений19.5. Симметричные полукольца . .19.6. Решетки . . . . . . . . . . . ...................................................................................................................51515357586367...в... . . . . . . .. . .

. . . . .. . . . . . . .полукольцах. . . . . . . .. . . . . . . .69............ÔÍ-12.....434345494950ÌÃÒÓ17. Кольцо многочленов17.1. Определение кольца многочленов . . . . . . . . .17.2. Деление с остатком и его свойства . . . . . . . .17.3. Разложение на неприводимые множители . . . .17.4. Использование делимости в теории шифрования17.5. Кватернионы . . . .

. . . . . . . . . . . . . . . . .ÌÃÒÓÔÍ-12ÌÃÒÓ.....ÔÍ-12ÔÍ-12.....ÌÃÒÓÌÃÒÓ.....1134610ÔÍ-124. Псевдорешения и псевдообратная матрица4.1. Метод наименьших квадратов . . . . . . . .4.2. Псевдорешения . . . . . . . . . . . . . . . . .4.3. Скелетное разложение . . . . . . . . .

. . .4.4. Псевдообратная матрица . . . . . . . . . . .4.5. Проектирование на подпространство . . . .ÌÃÒÓÔÍ-12ОГЛАВЛЕНИЕÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓ.