эту тему нельзя путать с алгеброй-логикой как теорией для анализа всяких интегральных схем
булевы операции
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нет - тут речь идет об изучении вообще колец с отношением x*x=x. если кольцо, как положено, с единицей, то такая структура называется булевой алгеброй. единицы может не быть, тогда это называется булевым кольцом
A + B = (A ↓ B) ↓ (A ↓ B) A * B = (A ↓ A) ↓ (B ↓ B)
кольцо с одним элементом,
поле с двумя элементами,
подмножества фиксированного множества
это, например, множество целых нечетных чисел
легко доказать, что любая булева алгебра будет коммутативной и иметь характеристику 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 в категорных терминах
диаграмма
В P(D) множество А∪В является копроизведением А и В. это описание нельзя обобщить на Set аналогично предыдущему случаю, так как мы еще не знаем, имеет ли Sub(d) копроизведения. более того, в Set копроизведение А+В является дизъюнктным объединением А и В. поэтому если А и В пересекаются, то
А + В ≠ A U Воднако A U В можно охарактеризовать как объединение образов функций включения f:А→D и g:В→D
топос W называется булевым, если для каждого W-объекта d решетка (Sub(d),⊆) является булевой алгеброй