Журнал фильтра правок

': ''Эта статья об [[Алгебраическая система|алгебраической системе]]. О разделе математической логики, изучающем высказывания и операции над ними, см. [[Алгебра логики]].'' '''Булевой алгеброй'''<ref>{{cite web|author=D. A. Vladimirov|date=2002|url=http://eom.springer.de/B/b016920.htm|title=Springer Online Reference Works – Boolean algebra|publisher=Springer-Verlag|accessdate=2010-08-04|lang=en|archiveurl=https://www.webcitation.org/65JKMgr2a?url=http://www.encyclopediaofmath.org/index.php/Main_Page|archivedate=2012-02-09}}</ref>{{sfn|Владимиров|1969|с=19}}{{sfn|Кузнецов|2007}} называется непустое [[множество]] ''A'' с двумя [[бинарная операция|бинарными операциями]] <math>\land</math> (аналог [[конъюнкция|конъюнкции]]), <math>\lor</math> (аналог [[дизъюнкция|дизъюнкции]]), одной [[унарная операция|унарной операцией]] <math>\lnot</math> (аналог [[отрицание|отрицания]]) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для любых ''a'', ''b'' и ''c'' из множества ''A'' верны следующие [[аксиома|аксиомы]]: {| cellpadding=5 |<math> a \lor (b \lor c) = (a \lor b) \lor c </math> |<math> a \land (b \land c) = (a \land b) \land c </math> | [[Ассоциативность (математика)|ассоциативность]] |- |<math> a \lor b = b \lor a </math> |<math> a \land b = b \land a </math> | [[коммутативность]] |- |<math> a \lor (a \land b) = a </math> |<math> a \land (a \lor b) = a </math> | законы поглощения |- |<math> a \lor (b \land c) = (a \lor b) \land (a \lor c) </math> |<math> a \land (b \lor c) = (a \land b) \lor (a \land c) </math> | [[дистрибутивность]] |- |<math> a \lor \lnot a = 1 </math> |<math> a \land \lnot a = 0 </math> | дополнительность |} {{Hider| title = В нотации · + ¯| hidden = 1 | title-style = text-align: left; | content-style = text-align: left; | content = <math>\begin{align} & a+(b+c)=(a+b)+c & a(bc)=(ab)c \\ & a+b=b+a & ab=ba \\ & a+ab=a & a(a+b)=a \\ & a+bc=(a+b)(a+c) & a(b+c)=ab+ac \\ & a+\bar{a}=1 & a\bar{a} = 0 \end{align}</math> }} Первые три аксиомы означают, что (''A'', <math>\land</math>, <math>\lor</math>) является [[Решётка (теория множеств)|решёткой]]. Таким образом, булева алгебра может быть определена как [[дистрибутивная решётка]], в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется [[псевдобулева алгебра|псевдобулевой алгеброй]]. Названа в честь [[Буль, Джордж|Джорджа Буля]]. == Некоторые свойства == Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬''a'' любого элемента ''a'' однозначно определено. Для всех ''a'' и ''b'' из ''A'' верны также следующие равенства: {| cellpadding=15 | <math> a \lor a = a</math> |<math> a \land a = a </math> | |- |<math> a \lor 0 = a </math> |<math> a \land 1 = a </math> | rowspan=2 | |- |<math> a \lor 1 = 1 </math> |<math> a \land 0 = 0 </math> |- |<math> \lnot 0 = 1 </math> |<math> \lnot 1 = 0 </math> | дополнение 0 есть 1 и наоборот |- |<math> \lnot (a \lor b) = \lnot a \land \lnot b</math> |<math> \lnot (a \land b) = \lnot a \lor \lnot b</math> | [[законы де Моргана]] |- | <math> \lnot \lnot a = a </math>. | | [[инволюция (математика)|инволютивность отрицания]], [[Закон двойного отрицания|закон снятия двойного отрицания]]. |} == Основные тождества == В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких. Сводная таблица свойств и аксиом, описанных выше: {| cellpadding=5 |<math> a \lor b = b \lor a </math> |<math> a \land b = b \land a </math> |1 [[коммутативность]], [[переместительность]] |- |<math> a \lor (b \lor c) = (a \lor b) \lor c </math> |<math> a \land (b \land c) = (a \land b) \land c </math> |2 [[Ассоциативность (математика)|ассоциативность]], [[сочетательность]] |- |3.1 конъюнкция относительно дизъюнкции <math> a \lor (b \land c) = (a \lor b) \land (a \lor c) </math> |3.2 дизъюнкция относительно конъюнкции <math> a \land (b \lor c) = (a \land b) \lor (a \land c) </math> |3 [[дистрибутивность]], [[распределительность]] |- |<math> a \lor \lnot a = 1 </math> |<math> a \land \lnot a = 0 </math> |4 [[комплементность]], [[дополнительность]] (свойства отрицаний) |- |<math> \lnot (a \lor b) = \lnot a \land \lnot b</math> |<math> \lnot (a \land b) = \lnot a \lor \lnot b</math> | 5 [[законы де Моргана]] |- |<math> a \lor (a \land b) = a </math> |<math> a \land (a \lor b) = a </math> | 6 законы поглощения |- |<math>a \lor(\lnot a \land b) = a \lor b</math> |<math>a \land(\lnot a \lor b) = a \land b</math> | 7 Блейка-Порецкого |- | <math> a \lor a = a</math> |<math> a \land a = a </math> | 8 [[Идемпотентность]] |- | <math> \lnot \lnot a = a </math> | | 9 [[инволюция (математика)|инволютивность отрицания]], [[Закон двойного отрицания|закон снятия двойного отрицания]] |- |<math> a \lor 0 = a </math> |<math> a \land 1 = a </math> | rowspan=3 | 10 свойства констант |- |<math> a \lor 1 = 1 </math> |<math> a \land 0 = 0 </math> |- | дополнение 0 есть 1 <math> \lnot 0 = 1 </math> | дополнение 1 есть 0 <math> \lnot 1 = 0 </math> |- | <math> (a \lor b)\land(\lnot a \lor b)=b</math> |<math> (a \land b) \lor (\lnot a \land b)=b</math> | 11 Склеивание |} {{seealso|Алгебра логики#Свойства логических операций}} == Примеры == * Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей: {| |- | width="80" | | {| border="1" cellpadding="4" cellspacing="0" |- ! ∧ || 0 || 1 |- ! 0 | 0 || 0 |- ! 1 | 0 || 1 |} | | width="40" | | {| border="1" cellpadding="4" cellspacing="0" |- ! ∨ || 0 || 1 |- ! 0 | 0 || 1 |- ! 1 | 1 || 1 |} | | width="40" | | {| border="1" cellpadding="4" cellspacing="0" |- ! a || 0 || 1 |- ! ¬a | 1 || 0 |} |} : Эта булева алгебра наиболее часто используется в [[логика|логике]], так как является [[точная модель|точной моделью]] классического [[исчисление высказываний|исчисления высказываний]]. В этом случае 0 называют ''ложью'', 1 — ''истиной''. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы. * Множество всех подмножеств данного множества ''S'' образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — [[пустое множество]], а наибольший — всё ''S''. * Рассмотрим множество <math>U</math> всех натуральных делителей заданного натурального числа <math>m,</math> [[Свободное от квадратов число|свободного от квадратов]]. Определим на <math>U</math> две бинарные операции: нахождение [[Наибольший общий делитель|наибольшего общего делителя]] (аналог конъюнкции) и [[Наименьшее общее кратное|наименьшего общего кратного]] (аналог дизъюнкции); роль отрицания играет одноместная операция, сопоставляющая делителю <math>d</math> делитель <math>m/d.</math> Полученная структура является булевой алгеброй; в ней аналогами булевских нуля и единицы выступают соответственно числа 1 и <math>m.</math> Переложение приведенных выше общих аксиом и свойств булевой алгебры для множества <math>U</math> даёт ряд полезных и не очевидных теоретико-числовых тождеств<ref>{{книга |автор=Виленкин Н. Я., Шибасов Л. П. Шибасова 3. Ф. |ref=За страницами учебника математики |заглавие=За страницами учебника математики : Арифметика. Алгебра. Геометрия : Кн. для учащихся 10-11-х кл. общеобразоват. учреждений |ссылка=https://search.rsl.ru/ru/record/01001733870 |место=М. |издательство=Просвещение : АО "Учеб. лит." |год=1996 |страницы=197 |страниц=319}}</ref>. * [[Алгебра Линденбаума — Тарского]] ([[фактормножество]] всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является [[гомоморфизм]]ом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру. * Если ''R'' — произвольное [[кольцо (алгебра)|кольцо]], то на нём можно определить множество ''центральных идемпотентов'' так: <br> ''A'' = { ''e'' ∈ ''R'' : ''e''² = ''e'', ''ex'' = ''xe'', ∀''x'' ∈ ''R'' }, <br> тогда множество ''A'' будет булевой алгеброй с операциями ''e'' ∨ ''f'' := ''e'' + ''f'' − ''ef'' и ''e'' ∧ ''f'' := ''ef''. == Принцип двойственности == В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на > и наоборот или < на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен. == Представления булевых алгебр == Можно доказать, что любая конечная булева алгебра изоморфна булевой алгебре всех подмножеств какого-то множества. Отсюда следует, что количество элементов в любой конечной булевой алгебре будет степенью двойки. [[Теорема Стоуна о представлении булевых алгебр|Теорема Стоуна]] утверждает, что любая булева алгебра изоморфна булевой алгебре всех открыто-замкнутых множеств какого-то [[компакт]]ного [[вполне несвязное пространство|вполне несвязного]] [[хаусдорфово пространство|хаусдорфова]] топологического пространства. == Аксиоматизация == В [[1933 год]]у американский математик {{не переведено 5|Хантингтон, Эдвард (математик)|Хантингтон||Edward Vermilye Huntington}} предложил следующую аксиоматизацию для булевых алгебр: # ''Аксиома коммутативности'': ''x'' + ''y'' = ''y'' + ''x''. # ''Аксиома ассоциативности'': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z''). # ''Уравнение Хантингтона'': ''n''(''n''(''x'') + ''y'') + ''n''(''n''(''x'') + ''n''(''y'')) = ''x''. Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание. [[Роббинс, Герберт|Герберт Роббинс]] поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй? Аксиоматизация алгебры Роббинса: # ''Аксиома коммутативности'': ''x'' + ''y'' = ''y'' + ''x''. # ''Аксиома ассоциативности'': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z''). # ''Уравнение Роббинса'': ''n''(''n''(''x'' + ''y'') + ''n''(''x'' + ''n''(''y''))) = ''x''. Этот вопрос оставался открытым с 1930-х годов и был любимым вопросом [[Тарский, Альфред|Тарского]] и его учеников. В [[1996 год]]у [[МакКьюн, Вильям|Вильям МакКьюн]], используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй. == См. также == * [[Алгебра логики]] * [[Булева функция]] * [[Битовые операции]] == Примечания == {{примечания}} == Литература == * {{книга |автор = Владимиров Д. А. |часть = |заглавие = Булевы алгебры |оригинал = |ссылка = http://eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu |ответственный = |издание = |место = {{М.}} |издательство = «Наука» |год = 1969 |том = |страницы = |страниц = 320 |серия = |isbn = |тираж = |ref = Владимиров }} * {{книга|автор=Кузнецов О. П.|заглавие=Дискретная математика для инженера|место={{СПб}}|издательство=Лань|год=2007|страниц=394|ссылка=https://search.rsl.ru/ru/record/01003342716|ref = Кузнецов}} * {{книга|автор=Иванов Б. Н.|часть=|заглавие=Дискретная математика. Алгоритмы и программы. Расширенный курс|оригинал=|ссылка=http://bnivanov.ru/?p=761|ответственный=|издание=|место={{М.}}|издательство=«Известия»|год=2011|том=|страницы=|страниц=512|серия=|isbn=|тираж=|ref=Кузнецов}}{{Недоступная ссылка|date=Июнь 2018 |bot=InternetArchiveBot }} * {{книга |автор = Гуров С.И. |часть = |заглавие = Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры |оригинал = |ссылка = https://www.researchgate.net/publication/279495665_Bulevy_algebry_uporadocennye_mnozestva_resetki_Opredelenia_svojstva_primery |ответственный = |издание = |место = {{М.}} |издательство = Либроком |год = 2013 |том = |страницы = |страниц = 352 |серия = |isbn = |тираж = }} {{Дискретная математика}} [[Категория:Теория решёток]] [[Категория:Математическая логика]] [[Категория:Булева алгебра|*]] [[Категория:Дискретная математика]]'