Просмотр отдельных изменений
Эта страница позволяет вам проверить переменные, сгенерированные фильтром злоупотреблений, на предмет отдельного изменения.
Переменные, созданные для этого изменения
Переменная | Значение |
---|---|
Число правок участника ($1) (user_editcount) | null |
Имя учётной записи ($1) (user_name) | '85.140.13.122' |
Возраст учётной записи ($1) (user_age) | 0 |
Группы (включая неявные) в которых состоит участник ($1) (user_groups) | [
0 => '*'
] |
Права, которые есть у участника ($1) (user_rights) | [
0 => 'createaccount',
1 => 'read',
2 => 'edit',
3 => 'createpage',
4 => 'createtalk',
5 => 'writeapi',
6 => 'viewmywatchlist',
7 => 'editmywatchlist',
8 => 'viewmyprivateinfo',
9 => 'editmyprivateinfo',
10 => 'editmyoptions',
11 => 'abusefilter-log-detail',
12 => 'urlshortener-create-url',
13 => 'centralauth-merge',
14 => 'abusefilter-view',
15 => 'abusefilter-log',
16 => 'vipsscaler-test',
17 => 'flow-hide'
] |
Редактирует ли пользователь через мобильное приложение ($1) (user_app) | false |
Редактирует ли участник через мобильный интерфейс ($1) (user_mobile) | true |
ID страницы ($1) (page_id) | 143756 |
Пространство имён страницы ($1) (page_namespace) | 0 |
Название страницы (без пространства имён) ($1) (page_title) | 'Булева алгебра' |
Полное название страницы ($1) (page_prefixedtitle) | 'Булева алгебра' |
Последние десять редакторов страницы ($1) (page_recent_contributors) | [
0 => 'Alexei Kopylov',
1 => '91.103.248.178',
2 => '31.129.194.144',
3 => 'InternetArchiveBot',
4 => 'Maqivi',
5 => 'TextworkerBot',
6 => 'Alpha-Gamma',
7 => 'LGB',
8 => '91.243.110.100',
9 => '193.19.127.4'
] |
Возраст страницы (в секундах) ($1) (page_age) | 432566913 |
Действие ($1) (action) | 'edit' |
Описание правки/причина ($1) (summary) | '' |
Старая модель содержимого ($1) (old_content_model) | 'wikitext' |
Новая модель содержимого ($1) (new_content_model) | 'wikitext' |
Вики-текст старой страницы до правки ($1) (old_wikitext) | ': ''Эта статья об [[Алгебраическая система|алгебраической системе]]. О разделе математической логики, изучающем высказывания и операции над ними, см. [[Алгебра логики]].''
'''Булевой алгеброй'''<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 =
|тираж =
}}
{{Дискретная математика}}
[[Категория:Теория решёток]]
[[Категория:Математическая логика]]
[[Категория:Булева алгебра|*]]
[[Категория:Дискретная математика]]' |
Вики-текст новой страницы после правки ($1) (new_wikitext) | ': ''Эта статья об [[Алгебраическая система|алгебраической системе]]. О разделе математической логики, изучающем высказывания и операции над ними, см. [[Алгебра логики]].''
'''Булевой алгеброй'''<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>
| дополнительность
|}
== Некоторые свойства ==
Из аксиом видно, что наименьшим элементом является 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 =
|тираж =
}}
{{Дискретная математика}}
[[Категория:Теория решёток]]
[[Категория:Математическая логика]]
[[Категория:Булева алгебра|*]]
[[Категория:Дискретная математика]]' |
Унифицированная разница изменений правки ($1) (edit_diff) | '@@ -23,22 +23,4 @@
| дополнительность
|}
-
- {{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>) является [[Решётка (теория множеств)|решёткой]]. Таким образом, булева алгебра может быть определена как [[дистрибутивная решётка]], в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется [[псевдобулева алгебра|псевдобулевой алгеброй]].
-Названа в честь [[Буль, Джордж|Джорджа Буля]].
== Некоторые свойства ==
' |
Новый размер страницы ($1) (new_size) | 17376 |
Старый размер страницы ($1) (old_size) | 18492 |
Изменение размера в правке ($1) (edit_delta) | -1116 |
Добавленные в правке строки ($1) (added_lines) | [] |
Удалённые в правке строки ($1) (removed_lines) | [
0 => '',
1 => ' {{Hider|',
2 => ' title = В нотации · + ¯|',
3 => ' hidden = 1 |',
4 => ' title-style = text-align: left; |',
5 => ' content-style = text-align: left; |',
6 => ' content =',
7 => '<math>\begin{align}',
8 => '& a+(b+c)=(a+b)+c & a(bc)=(ab)c \\',
9 => '& a+b=b+a & ab=ba \\ ',
10 => '& a+ab=a & a(a+b)=a \\',
11 => '& a+bc=(a+b)(a+c) & a(b+c)=ab+ac \\',
12 => '& a+\bar{a}=1 & a\bar{a} = 0',
13 => '\end{align}</math> ',
14 => '}}',
15 => '',
16 => 'Первые три аксиомы означают, что (''A'', <math>\land</math>, <math>\lor</math>) является [[Решётка (теория множеств)|решёткой]]. Таким образом, булева алгебра может быть определена как [[дистрибутивная решётка]], в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется [[псевдобулева алгебра|псевдобулевой алгеброй]].',
17 => 'Названа в честь [[Буль, Джордж|Джорджа Буля]].'
] |
Все внешние ссылки, добавленные в правке ($1) (added_links) | [] |
Все внешние ссылки в новом тексте ($1) (all_links) | [
0 => 'http://eom.springer.de/B/b016920.htm',
1 => 'https://www.webcitation.org/65JKMgr2a?url=http://www.encyclopediaofmath.org/index.php/Main_Page',
2 => 'https://search.rsl.ru/ru/record/01001733870',
3 => 'http://eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu',
4 => 'https://search.rsl.ru/ru/record/01003342716',
5 => 'http://bnivanov.ru/?p=761',
6 => 'https://www.researchgate.net/publication/279495665_Bulevy_algebry_uporadocennye_mnozestva_resetki_Opredelenia_svojstva_primery'
] |
Ссылки на странице до правки ($1) (old_links) | [
0 => 'http://bnivanov.ru/?p=761',
1 => 'http://eom.springer.de/B/b016920.htm',
2 => 'http://eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu',
3 => 'https://search.rsl.ru/ru/record/01001733870',
4 => 'https://search.rsl.ru/ru/record/01003342716',
5 => 'https://www.researchgate.net/publication/279495665_Bulevy_algebry_uporadocennye_mnozestva_resetki_Opredelenia_svojstva_primery',
6 => 'https://www.webcitation.org/65JKMgr2a?url=http://www.encyclopediaofmath.org/index.php/Main_Page'
] |
Была ли правка сделана через выходной узел сети Tor (tor_exit_node) | false |
Unix-время изменения ($1) (timestamp) | 1571297507 |