Полукольца (Семинары)

Семинар 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦАОпределение 11.1. Полукольцо — это алгебра с двумябинарными и двумя нульарными операциямиS = (S, +, ·, 0, 1),такая, что для произвольных элементов a , b , c множества Sвыполняются следующие аксиомы полукольца:1) a + (b + c) = (a + b) + c; 2) a + b = b + a; 3) a + 0 = a;4) a · (b · c) = (a · b) · c;5) a · 1 = 1 · a = a;6) a · (b + c) = a · b + a · c; 7) (b + c) · a = b · a + c · a;8) a · 0 = 0 · a = 0.Операцию + называют сложением полукольца,операцию · — умножением полукольца;элементы 0 и 1 — нулем и единицей полукольца S .1СЕМИНАР 11.

ЗАМКНУТЫЕ ПОЛУКОЛЬЦА2Выделяют два вида полуколец: коммутативное полукольцоc коммутативной операцией умножения; идемпотентное полукольцо с идемпотентной операцией сложения.Пример 11.1. Рассмотрим алгебру B = ({0, 1}, +, ·, 0, 1), вкоторой операции + и · заданы таблицами Кэли (табл. 11.1 и11.2).Таблица 11.1 Таблица 11.2+ 0 1· 0 10 0 10 0 01 1 11 0 1Эта алгебра — идемпотентное коммутативное полукольцо.

Проверку аксиом можно провести непосредственно по таблицам.Операции полукольца B можно трактовать как логические операции или“ и и“, а элементы 0 и 1 — как ложь“ и истину“.””””СЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА3Пример 11.2. Алгебра¡ +¢+R = R ∪ {+∞}, min, +, +∞, 0 ,гдеR+ — множество неотрицательных действительных чисел,min — операция взятия наименьшего из двух данных чисел,+ — операция сложения действительных чисел,+∞ — плюс бесконечность“,”0 — число нуль“,”есть идемпотентное коммутативное полукольцо, носителем которого является полуось R+ = {x: x ≥ 0} , пополненная элементом+∞ (множество всех неотрицательных действительных чисел вместе с плюс бесконечностью“).”Согласно сигнатуре, элемент +∞ рассматривается как нульполукольца, а элемент 0 как единица полукольца.СЕМИНАР 11.

ЗАМКНУТЫЕ ПОЛУКОЛЬЦА4На носителе идемпотентного полукольца S = (S, +, ·, 0, 1)может быть введено отношение порядка: для произвольных x ,y ∈ S положим x ≤ y тогда и только тогда, когда x + y = y , т.е.x ≤ y ⇔ x + y = y.(11.1)Его называют естественным порядком идемпотентногополукольца.Поскольку для любого элемента x произвольного идемпотентногополукольца S = (S, +, ·, 0, 1) имеет место 0+x = x , то для любогоx ∈ S выполняется неравенство 0 ≤ x , т.е. нуль идемпотентногополукольца есть наименьший элемент относительно естественногопорядка идемпотентного полукольца.Теорема 11.1. Если A — конечное подмножество (носителя)идемпотентного полукольца, то точная верхняя грань множестваA ( sup A ) относительно естественного порядка этого полукольцаравна cумме (в полукольце) всех элементов множества A .СЕМИНАР 11.

ЗАМКНУТЫЕ ПОЛУКОЛЬЦА5Определение 11.2. Полукольцо S = (S, +, ·, 0, 1) называютзамкнутым, если:1) оно идемпотентно;2) любая последовательность элементов множества S имеет точную верхнюю грань относительно естественного порядка ≤ этого идемпотентного полукольца;3) операция умножения полукольца S сохраняет точные верхние грани последовательностей, т.е.

для любого a ∈ S и любойпоследовательности X = {xn}n∈N элементов множества Sa sup X = sup(aX),Теорема 11.2.замкнуто.(sup X)a = sup(Xa).Любое конечное идемпотентное полукольцоСЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА6В замкнутом полукольце точная верхняя грань последовательности {xn}n∈N есть сумма элементов последовательности,∞Xxn = sup {xn: n ∈ N} .(11.2)n=1Итерация x∗ элемента x определяется как точная верхняя граньпоследовательности всех степеней элемента x , т.е.x∗ =∞Xxn,n=0где, по определению, x0 = 1 , а xn = xn−1x , n = 1, 2, . . .СЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА7Пусть матрицы A и B принадлежат полукольцу матрицнад некоторым замкнутым полукольцом S.Наименьшие решения уравненийX = AX + B илиX = XA + BMn(S)(11.3)относительно неизвестной матрицы X естьX = A∗B илиX = BA∗.(11.4)Матрица A∗ называется итерацией, или замыканием, матрицы A .Для вычисления C = A∗ можно решить в S при всех j = 1, .

. . , nсистему уравнений видаξ = Aξ + εj ,где εj ∈ S n — j -ый единичный вектор, т.е. вектор, все элементыкоторого, кроме j -ого, равны 0 , а j -ый равен 1 полукольца S .ξ = A∗εj есть j -й столбец матрицы A∗ .СЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА8Пример 11.3. Пусть матрица A над полукольцом B имеет вид0 1 1 10 1 1 0 .A=0 1 0 0 1 0 1 0Запишем систему уравнений в полукольце B для определенияпервого столбца матрицы A∗ :x1 =x2 + x3 + x4 + 1,x2 =x2 + x3+ 0,x3 =x2+ 0,x4 = x1+ x3+ 0.Подставим третье уравнение во второе.

В силу идемпотентностисложения получимx2 = x2 + (x2 + 0) + 0 = x2 + 0.СЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА9Следовательно, x2 = 1∗ · 0 = 1 · 0 = 0 . (Отметим, что x2 = 0 —наименьшее решение уравнения.) Далее x3 = 0 + 0 = 0 .Для x1 и x4 получим систему½x1 = x4 + 1,x4 = x1 + 0,откуда x1 = x1 + 1, x1 = 1∗ · 1 = 1 и x4 = 1 .Итак, первый столбец A∗ есть 10 01СЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА10Второй столбец определяется из системыx1 =x2 + x3 + x4 + 0,x2 =x2 + x3+ 1,x3 =x2+ 0,x4 = x1+ x3+ 0.Здесь x2 = x2 + (x2 + 0) + 1 = x2 + 1 , x2 = 1∗1 = 1 и x3 = x2 = 1 .Тогда½x1 = x4 + 1,x4 = x1 + 1,откуда x1 = (x1 + 1) + 1 = x1 + 1 , x1 = 1∗1 = 1 , а x4 = 1 + 1 = 1 .Действуя аналогично, получаем матрицу A∗ :1 1 1 10 1 1 0∗.A =0 1 1 01 1 1 1СЕМИНАР 11.

ЗАМКНУТЫЕ ПОЛУКОЛЬЦАПусть над полукольцом R+ задана матрица∞ 5 10 1∞ 2 3 ∞A=∞ 1 ∞ ∞3 ∞ 4 ∞11(11.5)Система для вычисления первого столбца матрицы A∗ имеет вид:x1 =5x2 + 10x3 + 1x4 + 0,x2 =2x2 + 3x3+ ∞,x3 =1x2+ ∞,x4 = 3x1+ 4x3+ ∞.Поскольку сложение в R+ — взятие наименьшего из двух чисел,а умножение — обычное арифметическое сложение, то множитель1 и слагаемое 0 существенны, т.к. x 6= x + 0 и x 6= 1 · x в общемслучае.СЕМИНАР 11.

ЗАМКНУТЫЕ ПОЛУКОЛЬЦА12При наличии слагаемого 0 (числа 0!) в любой сумме эта суммаравна числу 0. Cлагаемое +∞ можно не записывать (как нольполукольца.)Из первого уравнения получаем x1 = 0 .Напомним, что итерация любого элемента в рассматриваемомполукольце равна единице полукольца. Учитавая это, из второгоуравнения получаемx2 = 2∗(3x3 + ∞) = 3x3.Исключая x2 из остальных уравнений системы, получим:x2 = 3x3 + ∞,x3 = 1(3x3) + ∞,x4 = 3(8x3 + 10x3 + 1x4 + 0) + 4x3 + ∞,Так как в последнем уравнении в скобках стоит слагаемое 0 , то всяскобка равна 0 . Далее, из второго уравненияx3 = (1 · 3)x3 + ∞ = 4x3 + ∞,СЕМИНАР 11.

ЗАМКНУТЫЕ ПОЛУКОЛЬЦА13откуда x3 = 4∗ · ∞ = ∞, и поэтомуx4 = 3 · 0 + 4 · ∞ + ∞ = 3 + 4 = 3.Подставляя найденное значение x3 в выражение для x2 , получимx2 = ∞ . Первый столбец матрицы A∗ вычислен: 0∞ ∞3Аналогично вычисляются остальные столбцы матрицы A∗ . Врезультате получим:0 5 5 1 ∞ 0 3 ∞A= ∞ 1 0 ∞3 5 4 0СЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА14Задачи11.1. Установить, является ли алгебра ({0, 1}, max, min, 0, 1)полукольцом? Замкнутым полукольцом?11.2.

Установить, является ли алгебра ([0, 1], max, min, 0, 1)полукольцом? Замкнутым полукольцом?11.3. Показать, что алгебра (2{0,1}, ∪, ∩) есть замкнутое полукольцо. Какие элементы являются нулем и единицей этого полукольца?Решить в указанном полукольце уравнениеx = {1} ∩ x ∪ {0}.СЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА1511.4. Показать, что алгебра (2M , ∪, ∩) есть замкнутое полукольцо. Какие элементы являются нулем и единицей этого полукольца?При M = [0, 1] решить в указанном полукольце уравнениеx = A ∩ x ∪ B,где A = (0, 0.6) , B = [0.3, 0.8] .11.5. Найти матрицу A∗ в полукольце B , если матрица0 1 0A = 1 0 1.1 1 011.6.

Найти матрицу A∗ в полукольце R+ , если матрица5 1 2A = 1 3 6.2 4 3СЕМИНАР 11. ЗАМКНУТЫЕ ПОЛУКОЛЬЦА1611.7. Доказать, что для любой матрицы A n×n над полукольцомnXB A∗ =Ak .k=0Рассмотреть матрицы A2 , A3 и Ak как матрицы бинарныхотношений на n -элементном множестве и установить, как связаныэти бинарные отношения с бинарным отношением, задаваемымматрицей A .Показать, что матрица A∗ есть матрица рефлексивнотранзитивного замыкания бинарного отношения n -элементноммножестве, заданного матрицей A ..