FN_Alg19 (Лекции 2009)

Московский государственный технический университетимени Н.Э. БауманаÌÃÒÓФакультет «Фундаментальные науки»Кафедра «Математическое моделирование»ÌÃÒÓÀ.Í. ÊàíàòíèêîâÈÇÁÐÀÍÍÛÅ ËÅÊÖÈÈÏÎ ÀËÃÅÁÐÅÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12Äëÿ ñòóäåíòîâ ôàêóëüòåòà ÔÍÌÃÒÓÊîíñïåêò ëåêöèéÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12Москва2009ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦА И БУЛЕВЫ АЛГЕБРЫÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓ51ÔÍ-12Пример 19.1. а. Первым примером полукольца является любое кольцо с единицей.

Отметим, что в кольце сложение не может быть идемпотентным, так как из равенства x + x = x всилу свойства сокращения следует, что x = 0.б. Второй пример — система R∗ = (R∗ , +, ·, 0, 1), являющаяся коммутативным полукольцом, но не кольцом. Это полукольцо не идемпотентно.в. Алгебраическая система SA = 2A , ∪, ∩, ∅, A является коммутативным идемпотентным полукольцом. В этом можно убедиться непосредственной проверкой.ÌÃÒÓПолукольцо — алгебраическая система с двумя бинарными операциями +“ и ·“ (сложение””и умножение), причем:• относительно сложения эта алгебра есть коммутативный моноид;• относительно умножения — тоже моноид;• умножение дистрибутивно (слева и справа) относительно сложения;• нейтральный элемент по сложению (нуль полукольца) есть аннулирующий элемент поумножению.Эти четыре условия дают восемь аксиом:1) x + y = y + x;2) (x + y) + z = x + (y + z);3) x + 0 = x;4) (xy)z = x(yz);5) x · 1 = 1 · x = x;6) (x + y)z = xz + yz;7) z(x + y) = zx + zy;8) x · 0 = 0 · x = 0.Полукольцо называется коммутативным, если умножение полукольца коммутативно.Мы ограничимся рассмотрением идемпотентных полуколец, т.е.

полуколец, в которыхоперация сложения идемпотентна: x + x = x.ÔÍ-12Полукольцо — алгебраическая система с двумя бинарными операциями +“ и ·“ (сложение и””умножение), причем относительно сложения эта алгебра есть коммутативный моноид, относительноумножения — тоже моноид, кроме того, умножение дистрибутивно (слева и справа) относительносложения, а нейтральный элемент сложения (нуль полукольца) есть аннулирующий элемент умножения. Всего восемь аксиом. Коммутативное полукольцо и идемпотентное полукольцо (x + x = x).Примеры (R∗ = {x ∈ R: x > 0}):а) любое кольцо с единицей;б) R∗ = (R∗ , +, ·, 0, 1) — коммутативное неидемпотентное полукольцо;Aв) SA = 2 , ∪, ∩, ∅, A — коммутативное идемпотентное полукольцо;г) RA = 2A×A , ∪, ◦, ∅, idA — идемпотентное некоммутативное полукольцо;д) Ua,b = ([a, b], max, min, a, b) — коммутативное идемпотентное полукольцо;е) La,b = ([a, b], min, max, b, a) — коммутативное идемпотентное полукольцо;ж) R+ = (R∗ ∪ {+∞}, min, +, +∞, 0) — коммутативное идемпотентное полукольцо.Отношение порядка в полукольце: x 6 y ⇔ x + y = y.

Свойства: а) 0 6 a, a ∈ K; б) a 6 a + b,a, b ∈ K; в) a 6 b, c 6 d ⇒ a + c 6 b + d; г) a + b = 0 ⇒ a = 0 и b = 0; д) a 6 c, b 6 c ⇒ a + b 6 c;е) a 6 b ⇒ ac 6 bc. Теорема 1: если A конечное множество идемпотентного полукольца, то суммавсех элементов A есть sup A.ÌÃÒÓÌÃÒÓ19.1. Определение полукольцаÌÃÒÓПервые четыре свойства повторяют соответствующие свойства отношения естественногопорядка на множестве действительных неотрицательных чисел.

А вот два последних свойстване имеют аналога среди отношений порядка на числовых множествах, хотя для отношениявключения множеств оно очевидно. Проверка свойств элементарна и не вызывает затруднений.Поэтому доказательство их мы опускаем.ÔÍ-12а) 0 6 a, a ∈ K;б) a 6 a + b, a, b ∈ K;в) a 6 b, c 6 d ⇒ a + c 6 b + d;г) a + b = 0 ⇒ a = 0 и b = 0;д) a 6 c, b 6 c ⇒ a + b 6 c;е) a 6 b ⇒ ac 6 bc.ÌÃÒÓОтношение естественного порядка полукольца K обладает следующими свойствами:ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓВ идемпотентном полукольце K отношение {(x, y): x + y = y} есть отношение порядка, которое обозначают символом 6 и называют естественным порядком полукольца.Покажем, что введенное отношение действительно есть отношение порядка.

Во-первых, изусловий x 6 y и y 6 x делаем вывод, что x + y = y и y + x = x, откуда в силу коммутативностисложения вытекает, что x = y. Следовательно, введенное нами отношение антисимметрично.Во-вторых, это отношение транзитивно, так как условия x 6 y и y 6 z означают, что x + y = yи y + z = z, а следовательно, x + z = x + y + z = y + z = z и x 6 z. Наконец, рефлексивностьотношения, т.е. выполнение условия x 6 x означает выполнение для любого x ∈ K равенстваx + x = x, т.е.

идемпотентность сложения.Пример 19.2. В полукольце SA = 2A , ∪, ∩, ∅, A условие B ∪C = C равносильно включению B ⊂ C. Следовательно в этом полукольце отношение естественного порядка есть отношение включения.В полукольце Ua,b = ([a, b], max, min, a, b) отношение естественного порядка полукольцасовпадает с естественным числовым порядком, а в полукольце La,b естественное отношениепорядка является обратным к естественному числовому порядку.ÌÃÒÓÔÍ-12г.

Алгебраическая система RA = 2A×A , ∪, ◦, ∅, idA , носителем которой является множество отношений на множестве A, сложением — объединение отношений, а умножением —композиция отношений, представляет собой идемпотентное некоммутативное полукольцо.д. Алгебраическая система Ua,b = ([a, b], max, min, a, b) — коммутативное идемпотентноеполукольцо. В этом можно убедиться непосредственно, проверяя аксиомы полукольца.

Однакоследует заметить, что пример а полукольца нетрудно модифицировать: можно рассмотретьне все множество всех подмножеств множества A (булеан множества A), а любое семействоподмножеств множества A, замкнутое относительно операций объединения и пересечения двухмножеств и включающее подмножества ∅ и A. Если в качестве указанного семейства множестввыбрать совокупность отрезков вида [a, x], обозначаемых правым концом x, то объединениеотрезков с концами x и y будет отрезком с концом max {x, y}, а пересечение этих отрезков —отрезком с концом min{x, y}. Иными словами полукольцо Ua,b можно интерпретировать какчастный случай полукольца SA .е.

Еще один пример коммутативного идемпотентного полукольца — алгебраическая системаLa,b = ([a, b], min, max, b, a). Любопытно, что если в полукольцах SA и Ua,b поменять местамидве бинарные операции и две нульарные, то также получим полукольцо. Действительно, SAявляется коммутативным моноидом и относительно объединения, и относительно пересечения.Каждая из этих операций дистрибутивна относительно другой, а нейтральный элемент однойоперации является аннулирующим элементом другой.е. Алгебраическая система R+ = (R∗ ∪ {+∞}, min, +, +∞, 0), где R∗ — множество неотрицательных действительных чисел, является коммутативным идемпотентным полукольцом.ÔÍ-12ÌÃÒÓÌÃÒÓ52ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓÌÃÒÓÌÃÒÓПоскольку на идемпотентном полукольце естественным образом возникает отношение порядка, такое полукольцо всегда можно рассматривать как упорядоченное множество.

Напомним, что для таких множеств введены понятия наибольшего (наименьшего) элемента, максимального (минимального элемента), верхней (нижней) грани множества и точной верхней(нижней) грани.Теорема 19.1. Если A конечное множество элементов идемпотентного полукольца, тосумма всех элементов A есть sup A.J Пусть A = {a1 , a2 , . . . , an }. Чтобы доказать утверждение, достаточно показать, что, содной стороны, сумма a = a1 + a2 + . . . + an есть верхняя грань множества A, а с другой она непревышает никакой другой верхней грани множества A.Используя свойства естественного порядка, заключаем, чтоai 6 ai + a = ai + a1 + a2 + .

. . + ai + . . . + an = a,i = 1, n.Таким образом, сумма a есть верхняя грань множества A.Пусть b — какая-либо грань множества A, т.е. ai 6 b, i = 1, n. Тогда в силу свойства д)естественного порядка полукольцаa1 + a2 6 b,(a1 + a2 ) + a3 6 b,...,(a1 + a2 + . . . + an−1 ) + an 6 b.Следовательно, a 6 b и сумма a не превышает любой произвольно взятой верхней грани множества A. IРяд в идемпотентном полукольце. Частичные суммы и сумма ряда; неубывающая последовательность частичных сумм.

Теорема 2: если ряд сходится, то его сумма является точной верхнейгранью последовательности членов ряда; если последовательность членов ряда имеет точную верх∞Pнюю грань, то ряд сходится. Следствие: ai 6 a ⇒ai 6 a. Группировки и перестановки в рядах.ÌÃÒÓ19.2. Ряды в полукольцахÔÍ-12ÔÍ-12ÌÃÒÓ53ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓ19. ПОЛУКОЛЬЦАÔÍ-12И БУЛЕВЫ АЛГЕБРЫ ÌÃÒÓi=1S 1 = a1 ,S2 = a1 + a2 = S1 + a2 ,...,Sn+1 = Sn + an ,...называются частичными суммами рассматриваемого ряда. Из равенств Sn+1 = Sn + an ,n ∈ N, следует, что S1 6 S2 6 . .

. 6 Sn 6 . . . , т.е. последовательность {Sn } частичных суммÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓназывается рядом. Тема ряды“ — одна из важнейших в курсе математического анализа, при”этом теория числовых рядов активно использует понятие предела числовой последовательности.В полукольцах нет понятия предела последовательности. Однако можно построить элеметарную теорию рядов, похожую на теорию занкоположительных рядов.∞PИтак, пусть дан рядai .

ЗначенияÔÍ-12ÔÍ-12i=1ÌÃÒÓПусть {an } — некоторая последовательность элементов полукольца K. Символическая запись∞Xa1 + a2 + . . . + an + . . . =aiÔÍ-12ÔÍ-12i=1Теорема 3: если ряд сходится, то и любая его перестановка сходится к той же сумме. Теорема 4:Если ряд сходится, то сходится любая его группировка; если группировка ряда сходится, то и самряд сходится (в основе утверждение: точная верхняя грань неубывающей последовательности совпадает с точной верхней гранью любой ее подпоследовательности). Бесконечная ассоциативностьP ибесконечная коммутативность.