Булева алгебра


эту тему нельзя путать с алгеброй-логикой как теорией для анализа всяких интегральных схем

булевы операции

idempotence:

        A * A = A
        A + A = A      

commutativity:

        A * B = B * A
        A + B = B + A      

accosiativity:

        A * (B * C) = (A * B) * C
        A + (B + C) = (A + B) + C      

distributivity:

        A * (B + C) = (A * B) + (A * C)
        A + (B * C) = (A + B) * (A + C)    

duality:

        if C = A * B then ¬C = ¬A + ¬B
        if C = A + B then ¬C = ¬A * ¬B      

NAND :

    A ↑ B = ¬(A * B) = ¬A + ¬B

      ¬A = A ↑ A
      A * B = (A ↑ B) ↑ (A ↑ B)
      A + B = (A ↑ A) ↑ (B ↑ B)

NOR :

    A ↓ B = ¬(A + B) = ¬A * ¬B 

      ¬A = A ↓ A
A + B = (A ↓ B) ↓ (A ↓ B) A * B = (A ↓ A) ↓ (B ↓ B)

нет - тут речь идет об изучении вообще колец с отношением x*x=x. если кольцо, как положено, с единицей, то такая структура называется булевой алгеброй. единицы может не быть, тогда это называется булевым кольцом

тривиальные примеры булевых алгебр

кольцо с одним элементом,
поле с двумя элементами,
подмножества фиксированного множества

а булево кольцо, которое не является булевой алгеброй

это, например, множество целых нечетных чисел


легко доказать, что любая булева алгебра будет коммутативной и иметь характеристику 2. но обратное не верно, например нетривиальное расширение Галуа поля из двух элементов булевой алгеброй уже не будет. смысл тут в том, что задавая отношение x*x=x мы получаем как-бы бесточечную (pointfree или pointless) модель наивной теории множеств, или не только наивной если рассматривать булевы кольца, при этом саму являющееся множеством. отсюда переносятся все теоретико-множественные операции и понятие порядка. например, порядок определятся чисто алгебраическими средствами как

x ≤ y <=> x*y = x

а операция объединения как

x ∪ y = x + y + x*y

при этом у нас получается дистрибутивная решетка

самым полезным из базовой теории является понятие о разбиении единицы в булевой алгебре

к дискретной математике булевы алгебры не относятся, и к логике их можно отнести только в силу инертности мышления. на первый взгляд это чисто алгебраическая теория, однако топология там используется довольно интенсивно. потому просто к алгебре или тем более к топологии относить эту теорию нельзя. один учитель однажды сказал, что "анализ - это алгебра с топологией", а тут мы имеем дело именно с этим

связь с топологией обеспечивается тем, для изучения булевых алгебр активно используются пространства Стоуна или просто функтор Стоуна. этот функтор сопоставляет каждому булевому кольцу локально-компактное ноль-мерное Хаусдорффово пространство ненулевых морфизмов из самого кольца в поле из двух элементов. каждому элементу булевой алгебры в таком пространстве соответствует открытый компакт. и порядок тут переносится как порядок вложений. поэтому, если булевой была алгебра, то её пространство Стоуна будет компактно. однако это в общем случае неконструктивно и требует работы с ультрафильтрами. но, так как многие факты про булевы алгебры доказываются именно через пространства Стоуна, то можно представить, что мы имеем дело с алгебраической топологией шиворот-навыворот! т.е. исследуем регулярные алгебраические структуры с помощью функтора в топологические пространства

функтор этот, между прочим, контравариантный. стрелочки поворачиваются! и произведения становятся копроизведениями и наоборот. т.е., декартовым произведениям булевых алгебр соответствует несвязные объединения пространств Стоуна, а их тензорным произведениям - уже декартовы произведения пространств Стоуна. все это очень просто и логично если подумать про конечные аналоги и их комбинаторику

еще есть очень важные понятия о (секвенциональной) полноте, замкнутости и непрерывности в смысле порядка. речь тут идет просто про существование и сохранение инфов и супов в булевом порядке. когда в курсе теории вероятностей говорят про сигма-алгебры, то это сокращение для “секвенционально замкнутые по Дедекинду булевы алгебры подмножеств”

пример булевой алгебры, не являющейся сигма-алгеброй

алгебра конечных-коконечных подмножеств целых чисел

пример сигма-алгебры не являющейся замкнутой по Дедекинду

Борелева алгебра на действительных числах


интересные результаты тут - это теорема Лумиса-Сикорского про то, что любая сигма-алгебра представляется как фактор сигма-алгебры подмножеств по какому-то сигма-идеалу. еще есть интересная конструкция замыкания через построения алгебры открытых областей или регулярных открытых множеств в пространстве Стоуна со всеми универсальными свойствами замыкания. другая возможная конструкция замыкания - это алгебра идеалов, но она сильнее выносит мозг, так как операции с идеалами отличаются от обычной алгебры множеств. самый полезный тут факт такой, что любой автоморфизм булевой алгебры - непрерывен

тут напрашивается удивительная аналогия с эргодической теорией

тут у нас элементы булевой алгебры - это регионы пространства, автоморфизмы - это динамические процессы, а их степени - это дискретное время. отсюда берется представление об эргодических, смешивающих, рекуррентных и апериодических автоморфизмах. все это создает ощущение не просто бесточечной (pointfree и pointless) эргодической теории, а эргодической теории совершено абстрактной и пустой, лишенной каких-либо конкретных измерений. ничего полезного в нормальной эргодической теории доказать нельзя, а воспринимать эту теорию нужно скорее как модель для углубления понимания и вдохновения

как вишенка на торте - теоремы про факторизацию автоморфизмов на т.н. обменивающие инволюции. это все издалека очень напоминало теоремы из аффинной геометрии про представление поворотов в произведений отражений. но на практике там оказалось длинное, техническое, “комбинаторное” доказательство. такое доказательство может занять ни одну лекцию. но в итоге результат звучит так, что в алгебре не замкнутой по Дедекинду любой автоморфизм представляется как произведение не более чем трех инволюций. отсюда следует определенный подход к подсчету нормальных подгрупп и критерии простоты. в частности можно доказать, что у группы автоморфизмов Борелевской сигма-алгебры действительной прямой только три нетривиальные нормальные подгруппы - удивительное утверждение на стыке элементарной алгебры и элементарного анализа

намного интереснее было бы изучать булевы алгебры с мерой (нормированные алгебры)

не только автоморфизмы создают поток в дискретном времени, но и эндоморфизмы, да, и просто эндофункции. эндоморфизмы тоже создают поток, то только у автоморфизмов его всегда можно повернуть вспять, т.е. имеет место “нулевая потеря информации”. а что касается эндофункций, то тут главная фишка булевых алгебр в том, что их элементы по смыслу соответствуют подмножествам. поэтому есть эндофункция для какого-то множества, то она будет действовать на его подмножества прообразами, и это будет уже эндоморфизм. а при работе с абстрактными булевыми алгебрами про существования самих точек и перемещающих их эндофункции можно забыть

строение частично упорядоченного множества P как булевой алгебры зависит от правил классической логики через свойства связок "и", "или" и "не". эту зависимость можно сделать совершенно явной с помощью характеристических функций. следующий результат показывает, как теоретико-множественные операции зависят от истинностных функций

Теорема: если А и В - подмножества в D с характеристическими функциями

     χA: D→2 и χB: D→2 
то
  (i)   χ⁻A = ¬ χA
 (ii)   χA∩B = χA ∩ χB
(iii)   χA∪B = χA ∪ χB

Имеется также совершенно другой подход, позволяющий описать операции пересечения и объединения в Set в категорных терминах

пересечения

диаграмма

является декартовым квадратом в Set. в частично упорядоченном множестве P(D) пересечение А∩В является наибольшей нижней гранью А и В, а следовательно, их произведением и даже расслоенным произведением. итак, приведенная диаграмма будет декартовым квадратом в Set, а не только в P(D)

объединения

В P(D) множество А∪В является копроизведением А и В. это описание нельзя обобщить на Set аналогично предыдущему случаю, так как мы еще не знаем, имеет ли Sub(d) копроизведения. более того, в Set копроизведение А+В является дизъюнктным объединением А и В. поэтому если А и В пересекаются, то

        А + В ≠ A U В 
однако A U В можно охарактеризовать как объединение образов функций включения f:А→D и g:В→D


топос W называется булевым, если для каждого W-объекта d решетка (Sub(d),⊆) является булевой алгеброй