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

Поделись знанием:
Перейти к: навигация, поиск
Эта статья об алгебраической системе. О разделе математической логики, изучающем высказывания и операции над ними, см. Алгебра логики.

Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями <math>\land</math> (аналог конъюнкции), <math>\lor</math> (аналог дизъюнкции), одной унарной операцией <math>\lnot</math> (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

<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> дополнительность


Первые три аксиомы означают, что (A, <math>\land</math>, <math>\lor</math>) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй. Названа в честь Джорджа Буля.





Некоторые свойства

Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:

<math> a \lor a = a</math> <math> a \land a = a </math>
<math> a \lor 0 = a </math> <math> a \land 1 = a </math>
<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>. инволютивность отрицания, закон снятия двойного отрицания.

Основные тождества

В данном разделе повторяются свойства и аксиомы, описанные выше с добавлением ещё нескольких.

Сводная таблица свойств и аксиом, описанных выше:

<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> 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 Склеивание

См. также Алгебра логики

Примеры

  • Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:
0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
a 0 1
¬a 1 0
  • Эта булева алгебра наиболее часто используется в логике, так как является точной моделью классического исчисления высказываний. В этом случае 0 называют ложью, 1 — истиной. Выражения, содержащие булевы операции и переменные, представляют собой высказывательные формы.
  • Алгебра Линденбаума — Тарского (фактормножество всех утверждений по отношению равносильности в данном исчислении с соответствующими операциями) какого-либо исчисления высказываний является булевой алгеброй. В этом случае истинностная оценка формул исчисления является гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.
  • Множество всех подмножеств данного множества S образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество, а наибольший — всё S.
  • Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
    A = { eR : e² = e, ex = xe, ∀xR },
    тогда множество A будет булевой алгеброй с операциями ef := e + fef и ef := ef.

Принцип двойственности

В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1, ≤ на > и наоборот или < на ≥ и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.

Представления булевых алгебр

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

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

Аксиоматизация

В 1933 году американский математик Хантингтон[en] предложил следующую аксиоматизацию для булевых алгебр:

  1. Аксиома коммутативности: x + y = y + x.
  2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
  3. Уравнение Хантингтона: n(n(x) + y) + n(n(x) + n(y)) = x.

Здесь использованы обозначения Хантингтона: + означает дизъюнкцию, n — отрицание.

Герберт Роббинс поставил следующий вопрос: можно ли сократить последнюю аксиому так, как написано ниже, то есть будет ли определённая выписанными ниже аксиомами структура булевой алгеброй?

Аксиоматизация алгебры Роббинса:

  1. Аксиома коммутативности: x + y = y + x.
  2. Аксиома ассоциативности: (x + y) + z = x + (y + z).
  3. Уравнение Роббинса: n(n(x + y) + n(x + n(y))) = x.

Этот вопрос оставался открытым с 1930-х годов и был любимым вопросом Тарского и его учеников.

В 1996 году Вильям МакКьюн, используя некоторые полученные до него результаты, дал утвердительный ответ на этот вопрос. Таким образом, любая алгебра Роббинса является булевой алгеброй.

См. также

Напишите отзыв о статье "Булева алгебра"

Примечания

  1. D. A. Vladimirov. [eom.springer.de/B/b016920.htm Springer Online Reference Works – Boolean algebra] (англ.). Springer-Verlag (2002). Проверено 4 августа 2010. [www.webcitation.org/65JKMgr2a Архивировано из первоисточника 9 февраля 2012].
  2. Владимиров Д. А. [eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu Булевы алгебры]. — М.: «Наука», 1969. — С. 19.
  3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. — С. 58.

Литература

  • Владимиров Д. А. [eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu Булевы алгебры]. — М.: «Наука», 1969. — 320 с.
  • Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. — 480 с.
  • Иванов Б. Н. [bnivanov.ru/?p=761 Дискретная математика. Алгоритмы и программы. Расширенный курс]. — М.: «Известия», 2011. — 512 с. — ISBN 978-5-206-00824-1.
  • Гуров С.И. Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры. — М.: Либроком, 2013. — 352 с. — ISBN 978-5-397-03899-7.

Отрывок, характеризующий Булева алгебра

– Но господин Курагин, стало быть, не удостоил своей руки графиню Ростову? – сказал князь Андрей. Он фыркнул носом несколько раз.
– Он не мог жениться, потому что он был женат, – сказал Пьер.
Князь Андрей неприятно засмеялся, опять напоминая своего отца.
– А где же он теперь находится, ваш шурин, могу ли я узнать? – сказал он.
– Он уехал в Петер…. впрочем я не знаю, – сказал Пьер.
– Ну да это всё равно, – сказал князь Андрей. – Передай графине Ростовой, что она была и есть совершенно свободна, и что я желаю ей всего лучшего.
Пьер взял в руки связку бумаг. Князь Андрей, как будто вспоминая, не нужно ли ему сказать еще что нибудь или ожидая, не скажет ли чего нибудь Пьер, остановившимся взглядом смотрел на него.
– Послушайте, помните вы наш спор в Петербурге, – сказал Пьер, помните о…
– Помню, – поспешно отвечал князь Андрей, – я говорил, что падшую женщину надо простить, но я не говорил, что я могу простить. Я не могу.
– Разве можно это сравнивать?… – сказал Пьер. Князь Андрей перебил его. Он резко закричал:
– Да, опять просить ее руки, быть великодушным, и тому подобное?… Да, это очень благородно, но я не способен итти sur les brisees de monsieur [итти по стопам этого господина]. – Ежели ты хочешь быть моим другом, не говори со мною никогда про эту… про всё это. Ну, прощай. Так ты передашь…
Пьер вышел и пошел к старому князю и княжне Марье.
Старик казался оживленнее обыкновенного. Княжна Марья была такая же, как и всегда, но из за сочувствия к брату, Пьер видел в ней радость к тому, что свадьба ее брата расстроилась. Глядя на них, Пьер понял, какое презрение и злобу они имели все против Ростовых, понял, что нельзя было при них даже и упоминать имя той, которая могла на кого бы то ни было променять князя Андрея.
За обедом речь зашла о войне, приближение которой уже становилось очевидно. Князь Андрей не умолкая говорил и спорил то с отцом, то с Десалем, швейцарцем воспитателем, и казался оживленнее обыкновенного, тем оживлением, которого нравственную причину так хорошо знал Пьер.


В этот же вечер, Пьер поехал к Ростовым, чтобы исполнить свое поручение. Наташа была в постели, граф был в клубе, и Пьер, передав письма Соне, пошел к Марье Дмитриевне, интересовавшейся узнать о том, как князь Андрей принял известие. Через десять минут Соня вошла к Марье Дмитриевне.
– Наташа непременно хочет видеть графа Петра Кирилловича, – сказала она.
– Да как же, к ней что ль его свести? Там у вас не прибрано, – сказала Марья Дмитриевна.
– Нет, она оделась и вышла в гостиную, – сказала Соня.
Марья Дмитриевна только пожала плечами.
– Когда это графиня приедет, измучила меня совсем. Ты смотри ж, не говори ей всего, – обратилась она к Пьеру. – И бранить то ее духу не хватает, так жалка, так жалка!
Наташа, исхудавшая, с бледным и строгим лицом (совсем не пристыженная, какою ее ожидал Пьер) стояла по середине гостиной. Когда Пьер показался в двери, она заторопилась, очевидно в нерешительности, подойти ли к нему или подождать его.
Пьер поспешно подошел к ней. Он думал, что она ему, как всегда, подаст руку; но она, близко подойдя к нему, остановилась, тяжело дыша и безжизненно опустив руки, совершенно в той же позе, в которой она выходила на середину залы, чтоб петь, но совсем с другим выражением.
– Петр Кирилыч, – начала она быстро говорить – князь Болконский был вам друг, он и есть вам друг, – поправилась она (ей казалось, что всё только было, и что теперь всё другое). – Он говорил мне тогда, чтобы обратиться к вам…
Пьер молча сопел носом, глядя на нее. Он до сих пор в душе своей упрекал и старался презирать ее; но теперь ему сделалось так жалко ее, что в душе его не было места упреку.
– Он теперь здесь, скажите ему… чтобы он прост… простил меня. – Она остановилась и еще чаще стала дышать, но не плакала.
– Да… я скажу ему, – говорил Пьер, но… – Он не знал, что сказать.
Наташа видимо испугалась той мысли, которая могла притти Пьеру.
– Нет, я знаю, что всё кончено, – сказала она поспешно. – Нет, это не может быть никогда. Меня мучает только зло, которое я ему сделала. Скажите только ему, что я прошу его простить, простить, простить меня за всё… – Она затряслась всем телом и села на стул.
Еще никогда не испытанное чувство жалости переполнило душу Пьера.
– Я скажу ему, я всё еще раз скажу ему, – сказал Пьер; – но… я бы желал знать одно…
«Что знать?» спросил взгляд Наташи.
– Я бы желал знать, любили ли вы… – Пьер не знал как назвать Анатоля и покраснел при мысли о нем, – любили ли вы этого дурного человека?
– Не называйте его дурным, – сказала Наташа. – Но я ничего – ничего не знаю… – Она опять заплакала.
И еще больше чувство жалости, нежности и любви охватило Пьера. Он слышал как под очками его текли слезы и надеялся, что их не заметят.
– Не будем больше говорить, мой друг, – сказал Пьер.
Так странно вдруг для Наташи показался этот его кроткий, нежный, задушевный голос.
– Не будем говорить, мой друг, я всё скажу ему; но об одном прошу вас – считайте меня своим другом, и ежели вам нужна помощь, совет, просто нужно будет излить свою душу кому нибудь – не теперь, а когда у вас ясно будет в душе – вспомните обо мне. – Он взял и поцеловал ее руку. – Я счастлив буду, ежели в состоянии буду… – Пьер смутился.
– Не говорите со мной так: я не стою этого! – вскрикнула Наташа и хотела уйти из комнаты, но Пьер удержал ее за руку. Он знал, что ему нужно что то еще сказать ей. Но когда он сказал это, он удивился сам своим словам.
– Перестаньте, перестаньте, вся жизнь впереди для вас, – сказал он ей.
– Для меня? Нет! Для меня всё пропало, – сказала она со стыдом и самоунижением.
– Все пропало? – повторил он. – Ежели бы я был не я, а красивейший, умнейший и лучший человек в мире, и был бы свободен, я бы сию минуту на коленях просил руки и любви вашей.
Наташа в первый раз после многих дней заплакала слезами благодарности и умиления и взглянув на Пьера вышла из комнаты.
Пьер тоже вслед за нею почти выбежал в переднюю, удерживая слезы умиления и счастья, давившие его горло, не попадая в рукава надел шубу и сел в сани.
– Теперь куда прикажете? – спросил кучер.
«Куда? спросил себя Пьер. Куда же можно ехать теперь? Неужели в клуб или гости?» Все люди казались так жалки, так бедны в сравнении с тем чувством умиления и любви, которое он испытывал; в сравнении с тем размягченным, благодарным взглядом, которым она последний раз из за слез взглянула на него.
– Домой, – сказал Пьер, несмотря на десять градусов мороза распахивая медвежью шубу на своей широкой, радостно дышавшей груди.
Было морозно и ясно. Над грязными, полутемными улицами, над черными крышами стояло темное, звездное небо. Пьер, только глядя на небо, не чувствовал оскорбительной низости всего земного в сравнении с высотою, на которой находилась его душа. При въезде на Арбатскую площадь, огромное пространство звездного темного неба открылось глазам Пьера. Почти в середине этого неба над Пречистенским бульваром, окруженная, обсыпанная со всех сторон звездами, но отличаясь от всех близостью к земле, белым светом, и длинным, поднятым кверху хвостом, стояла огромная яркая комета 1812 го года, та самая комета, которая предвещала, как говорили, всякие ужасы и конец света. Но в Пьере светлая звезда эта с длинным лучистым хвостом не возбуждала никакого страшного чувства. Напротив Пьер радостно, мокрыми от слез глазами, смотрел на эту светлую звезду, которая, как будто, с невыразимой быстротой пролетев неизмеримые пространства по параболической линии, вдруг, как вонзившаяся стрела в землю, влепилась тут в одно избранное ею место, на черном небе, и остановилась, энергично подняв кверху хвост, светясь и играя своим белым светом между бесчисленными другими, мерцающими звездами. Пьеру казалось, что эта звезда вполне отвечала тому, что было в его расцветшей к новой жизни, размягченной и ободренной душе.


С конца 1811 го года началось усиленное вооружение и сосредоточение сил Западной Европы, и в 1812 году силы эти – миллионы людей (считая тех, которые перевозили и кормили армию) двинулись с Запада на Восток, к границам России, к которым точно так же с 1811 го года стягивались силы России. 12 июня силы Западной Европы перешли границы России, и началась война, то есть совершилось противное человеческому разуму и всей человеческой природе событие. Миллионы людей совершали друг, против друга такое бесчисленное количество злодеяний, обманов, измен, воровства, подделок и выпуска фальшивых ассигнаций, грабежей, поджогов и убийств, которого в целые века не соберет летопись всех судов мира и на которые, в этот период времени, люди, совершавшие их, не смотрели как на преступления.
Что произвело это необычайное событие? Какие были причины его? Историки с наивной уверенностью говорят, что причинами этого события были обида, нанесенная герцогу Ольденбургскому, несоблюдение континентальной системы, властолюбие Наполеона, твердость Александра, ошибки дипломатов и т. п.
Следовательно, стоило только Меттерниху, Румянцеву или Талейрану, между выходом и раутом, хорошенько постараться и написать поискуснее бумажку или Наполеону написать к Александру: Monsieur mon frere, je consens a rendre le duche au duc d'Oldenbourg, [Государь брат мой, я соглашаюсь возвратить герцогство Ольденбургскому герцогу.] – и войны бы не было.