Полукольца (1076805)
Текст из файла
Семинар 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 10 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∗ есть 10 01СЕМИНАР 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 10 1 1 0∗.A =0 1 1 01 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 ..
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
