Где применяется булева алгебра

ОСНОВНЫЕ ПОЛОЖЕНИЯ БУЛЕВОЙ АЛГЕБРЫ

Название этого раздела математики связано с именем его основателя — Джорджа Буля (1815—1864). Используя классическое понятие алгебры, булеву алгебру можно определить как систему А = = (В, (рь фг, ф_я), в которой несущим множеством является двухэлементное множество двоичных чисел В = <0,1>, aQ = <фь фг,Фя) — заданные на этом множестве логические операции, сущность которых раскрывается ниже (см. разд. 2.2.2).

Основные логические операции — дизъюнкцию, конъюнкцию и отрицание — можно интерпретировать как операции, введенные в теорию множеств: свойства указанных операций аналогичны свойствам операций объединения, пересечения и дополнения множеств соответственно (см. разд. 1.1.2). Однако логические операции имеют несколько иной смысл; они позволяют формировать простые и сложные высказывания. Все множество логических операций обозначается Е₂.

Как правило, существует логическая интерпретация элементов множества В: 1 — истинно; 0 — ложно. В ряде случаев в качестве элемента множества рассматривается двоичная переменная (ее называют также логической или булевой переменной) х, которая принимает значения х = 0 или х = 1.

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

Булева алгебра применяется как средство:

1) алгоритмического описания в языках программирования для определения логических условий;

2) формирования логических высказываний в математической логике, лингвистике, теории искусственного интеллекта;
3) разработки и описания дискретных технических систем.

Алгебра логики позволяет производить анализ и синтез логических

устройств. Анализ — это поиск аналитического выражения, которое описывает работу системы. Синтез — обратная задача: создание технического устройства на основе математического описания средствами булевой алгебры.

Высказывания

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

Высказывание — это любое повествовательное предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. Обычно высказывания обозначаются буквами латинского алфавита: а, Ь, с, А, В, С. Для каждого высказывания вводится значение истинности, которое может принимать одно из двух возможных значений: 1 — истина, 0 — ложь.

Пример. Рассмотрим справедливость утверждений:

а — число 4 — четное;

b — снег — красный;

Значения истинности данных высказываний следующие: а = 1, b = 0, с = 0 .

Два высказывания А и В называются эквивалентными, если их значения истинности совпадают. Значение истинности может быть постоянным либо изменяется в зависимости от обстоятельств. Изменяемое высказывание может рассматриваться как переменный параметр — двоичная переменная, принимающая одно из двух значений (обозначается х, у, z).

Зачем нужна алгебра логики

Основные понятия алгебры логики, её применение в информатике. Решение задачи с расчетом стоимости стеклопакетов. Информационная и аналитическая модель задачи, технология решения задачи в MS Excel. Результаты компьютерного эксперимента и их анализ.

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	22.01.2015
Размер файла	44,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБОУ ВПО

«Финансовый университет при правительстве российской федерации»

Кафедра Экономической теории

по дисциплине «Информатика»

на тему «Применение алгебры логики в информатике»

алгебра логика задача компьютерный

1. Теоретическая часть

1.1 Наука алгебра логики

1.2 Основные понятия алгебры логики

1.3 Применение алгебры логики в информатике

2. Практическая часть

2.1 Постановка задачи

2.1.1 Цель решения задачи

2.1.2 Условие задачи

2.2 Компьютерная модель решения задачи

2.2.1 Информационная модель решения задачи

2.2.2 Аналитическая модель решения задачи

2.2.3 Технология решения задачи

2.3 Результаты компьютерного эксперимента и их анализ

2.3.1 Результаты компьютерного эксперимента

2.3.2 Анализ полученных результатов

Список использованной литературы

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

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

Цель данной курсовой работы состоит в изучении применения алгебры логики в информатике.

Для достижения цели необходимо ответить на следующие вопросы:

– наука алгебра логики

– основные понятия алгебры логики

– применение алгебры логики в информатике (к построению схем, обработке знаний и т.д.)

Практическая часть выполнена с использование MS Excel и MS Word.

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Отцом алгебры логики по праву считается английский математик 19-го столетия Джорж Буль (1815-1864). Именно он построил один из разделов формальной логики в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней. Алгебра в широком смысле слова – наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только с числами, но и над другими математическими объектами. Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т.д.

Большой вклад в становление и развитие алгебры логики внесли Августус де Морган (1806-1871), Уильям Стенли Джевонс (1835-1882), П.С. Порецкий(1846 – 1907), Чарлз Сандерс Пирс (1839-1914), А.А. Марков (1903-1979), А.Н. Колмогоров (1903-1987) и др.

Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 Клод Шеннон (1916-2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.

Алгебра логики явилась математической основой теории электрических и электронных переключателей схем, используемых в ЭВМ. В компьютерных науках её предпочитают называть не алгеброй логики, а Булевой алгеброй – по имени её создателя.

Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, <0,1>).Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика».

Алгебра логики – предельно важная для цифровых компьютеров тема. И с точки зрения их устройства, схем техники, и с точки зрения их функционирования и программирования поведения.

Действительно, мало-мальски сложное действие невозможно без обратной связи, без анализа условий выполнения. Например, «ЕСЛИ нам хочется пить, ТО мы пьём, ИНАЧЕ мы даже не думаем об этом». «ЕСЛИ компьютер не работает И питание включено, ТО компьютер сгорел». «ЕСЛИ точка левее левой стороны квадрата ИЛИ правее правой, ТО точка расположена не в квадрате». «Ревёт ли зверь в лесу глухом, трубит ли рог, гремит ли гром. ». «Кошелёк или жизнь». Помимо манипуляций константами «да» и «нет» логические переменные могут являться результатом применения к числам операторов отношения (меньше, больше, равно и т.п.). В компьютерах булевы переменные представляются (кодируются) битами (разрядами двоичной системы счисления), где 1 означает истину, а 0 – ложь. Манипуляции высказываниями и их комбинациями используются для получения некоего единственного результата, который можно использовать, например, для выбора той или иной последовательности действий. Поскольку логические переменные кодируются по тем же принципам, что и числа, символы и прочая информация, то можно комбинировать операции логики с операциями арифметики для реализации различных алгоритмов.

Таким образом, алгебра логики (другое название – Булева алгебра) – это область математики. Она оперирует величинами, которые могут принимать два значения (булевых значения). Эти два значения могут быть обозначены как угодно, лишь бы по-разному. Самые распространенные варианты:

При применении булевой алгебры в вычислительной технике, булевы значения – это 0 и 1. Они представляют собой состояние ячейки памяти объёмом в 1 бит или наличие/отсутствие напряжения в электрической схеме. Алгебра логики позволяет строить сложные электронные узлы, элементы которых работают согласно этой математической теории. При применении булевой алгебры в логических построениях в математике, булевы значения – это «ложь» и «истина». Они определяют истинность или ложность некоторого высказывания. Под высказываниями понимаются математические формулы. При применении булевой алгебры в повседневных рассуждениях, булевы значения – это также «ложь» и «истина». Они представляют собой оценку истинности или ложности некоторого высказывания. Под высказываниями понимаются фразы, которые удовлетворяют строго определенному списку свойств.

Алгебра логики применяется:

1) для упрощения сложных логических формул и доказательств тождеств;

2) при решении логических задач;

3) в контактных схемах;

4) при доказательствах теорем;

5) в базах данных при составлении запросов.

1.2 Основные понятия алгебры логики

Объектом логики как науки выступает абстрактное мышление. Логика изучает абстрактное мышление как средство познания объективного мира, исследует формы и законы, в которых происходит отражение мира в процессе мышления. Основными формами абстрактного мышления являются:

Понятие — форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов: портфель трапеция ураганный ветер, (например, "дерево", "самолет") или группой слов, т.е. словосочетаниями, например, "студент гуманитарного института", "создатель художественных картин", "река Дон", "космический корабль" и др.

Суждение — мысль, в которой что-либо утверждается или отрицается о предметах. Суждения являются повествовательными предложениями, истинными или ложными. Они могут быть простыми и сложными: Весна наступила, и грачи прилетели.

Пример сложного суждения: "Наступила осень, и лебеди улетают". Оно состоит из двух простых суждений.

Умозаключение — прием мышления, посредством которого из исходного знания получается новое знание; из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем заключение. Есть несколько видов умозаключений. Все металлы — простые вещества. Литий — металл. Литий — простое вещество.

Все металлы – вещества. Железо – металл. Железо – вещество

Чтобы достичь истины при помощи умозаключений, надо соблюдать законы логики.

Формальная логика — наука о законах и формах правильного мышления.

Математическая логика изучает логические связи и отношения, лежащие в основе дедуктивного (логического) вывода.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 – ЛОЖЬ, 1 – ИСТИНА); тогда операция ¬ приобретает смысл вычитания из единицы; ? – немодульного сложения; & (или ?) – умножения; – – равенства; ? – в буквальном смысле сложения по модулю 2 (исключающее Или – XOR); ? – непревосходства суммы над 1 (то есть A?B = (A + B) В

Законы алгебры логики

Алгебра логики это раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности), и логические операции над ними.
В алгебре логики принято отождествлять истинность высказывания с числом 1, а ложность — с числом 0 (А = 1 и С = 0 означает, что А истинно и что С ложно).

Что изучает алгебра логики?

Предметом изучения алгебры логики являются функции которые принимают лишь два значения: 0 или 1. Объединение простых высказываний в сложные в алгебре логики производится без учёта внутреннего содержания (смысла) этих высказываний.

К основным логическим операциям относятся операции: отрицания, логического умножения, или конъюнкции, логического сложения, или дизъюнкции, эквивалентности, импликации.

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

Где используется алгебра логики?

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

Конъюнкция такого рода высказываний будет тогда средством выражения последовательного соединения элементов, а дизъюнкция — их параллельного соединения. На этом основана возможность применять средства алгебры логики к задачам анализа и синтеза переключателей схем. Алгебра логики используется в теории релейных схем, теории ЭВМ и в теории дискретных автоматов.

Что такое алгебра логики?

Алгебра логики (булева алгебра) – это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

Что же собой представляет алгебра логики?

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

либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два

значения: 0, либо 1.

Что такое простое

логическое высказывание? Это фразы типа «два больше одного», «5.8 является целым числом». В первом случае мы имеем истину, а во втором ложь. Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.

Логические операции. Дизъюнкция, конъюнкция и отрицание

Так как же связываются между собой простые логические высказывания, образуя сложные? В естественном языке мы используем различные союзы и другие части речи. Например, «и», «или», «либо», «не», «если», «то», «тогда». Пример сложных высказываний: «у него есть знания

и навыки», «она приедет во вторник,

либо в среду», «я буду играть

тогда, когда сделаю уроки», «5

не равно 6». Как мы решаем, что нам сказали правду или нет? Как-то логически, даже где-то неосознанно, исходя из предыдущего жизненного опыта, мы понимает, что правда при союзе «и» наступает в случае правдивости обоих простых высказываний. Стоит одному стать ложью и все сложное высказывание будет лживо. А вот, при связке «либо» должно быть правдой только одно простое высказывание, и тогда все выражение станет истинным.

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

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

конъюнкция (И),

дизъюнкция (ИЛИ) и

отрицание (НЕ). Часто конъюнкцию обозначают

&, дизъюнкцию –

||, а отрицание – чертой над переменной, обозначающей высказывание.

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

При дизъюнкции истина сложного выражения наступает при истинности хотя бы одного входящего в него простого выражения или двух сразу. Бывает, что сложное выражение состоит более, чем из двух простых. В этом случае достаточно, чтобы одно простое было истинным и тогда все высказывание будет истинным.

Отрицание – это унарная операция, т.к выполняется по отношению к одному простому выражению или по отношению к результату сложного. В результате отрицания получается новое высказывание, противоположное исходному.

Таблицы истинности

Логические операции удобно описывать так называемыми

таблицами истинности, в которых отражают результаты вычислений сложных высказываний при различных значениях исходных простых высказываний. Простые высказывания обозначаются переменными (например, A и B).

Логические основы компьютера

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

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

Переключательные схемы

В ЭВМ применяются электрические схемы, состоящие из множества переключателей. Переключатель может находиться только в двух состояниях: замкнутом и разомкнутом. В первом случае – ток проходит, во втором – нет. Описывать работу таких схем очень удобно с помощью алгебры логики. В зависимости от положения переключателей можно получить или не получить сигналы на выходах.

Вентили, триггеры и сумматоры

Вентиль представляет собой логический элемент, который принимает одни двоичные значения и выдает другие в зависимости от своей реализации. Так, например, есть вентили, реализующие логическое умножение (конъюнкцию), сложение (дизъюнкцию) и отрицание.

Триггеры и сумматоры – это относительно сложные устройства, состоящие из более простых элементов – вентилей.

Триггер способен хранить один двоичный разряд, за счет того, что может находиться в двух устойчивых состояниях. В основном триггеры используется в регистрах процессора.

Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.

Практическое применение булевых функций

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

Диагностика (распознавание) заболеваний

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

Тогда связь между симптомами заболеваний и заболеваниями может быть выражена на языке алгебры логики. Например, если заболевание всегда сопровождается симптомами и , то булева функция тождественно равна 1. Аналогично, может быть известно, что если обнаружены симптомы , то обязательно должно быть заболевание , и, наоборот, это заболевание всегда проявляется в указанных симптомах. Следовательно, тождественно равна 1 булева функция следующего вида: . Часто один какой-нибудь симптом (например, высокая температура) сопровождает многие заболевания, булева функция в этом случае

Таким образом, экспериментально устанавливаются следующие булевы равенства:

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

Это равенство представляет собой своего рода неявное задание функций (заболеваний) от аргументов (симптомов) . Задача диагностики состоит в том, чтобы явно выявить эти зависимости и применить их к конкретному больному. Для этого можно составить таблицу значений функции . Из общего числа строк нас будут интересовать в ней лишь те, в которых для всех симптомов, выявленных у исследуемого больного, соответствующее значение , а общее число симптомов, задействованных в нашем анализе, пять: . Тогда число строк, представляющих интерес в данном случае, равно четырем. Предположим, что эти строки таковы (для простоты примем, что исследуются три заболевания: и им соответствуют три переменные:

Анализ выделенных строк показывает, что во всех строках, соответствующих симптомам больного, есть заболевание (точнее, ) и нет заболевания (точнее, ), а заболевание (т.е. ) в одних строках есть, а в других нет. Из этого можно сделать вывод, что у больного нет заболевания , но он определенно страдает заболеванием . Относительно заболевания требуются дополнительные исследования. Для этого нужно увеличить число анализируемых симптомов, выявить дополнительные указания . На практике число столбцов и строк построенной таблицы может оказаться столь большим, что ее анализ будет под силу лишь компьютеру.

Распознавание образов

Нетрудно видеть, что в самых общих чертах ситуация, рассмотренная в предыдущем пункте, может быть охарактеризована следующим образом. Имеется некоторое множество скрытых причин (болезней) и множество наблюдаемых следствий (симптомов). Кроме того, имеются высказывания, связывающие причины и следствия. Требуется, опираясь на эти высказывания, по предъявляемому набору следствий (симптомов, наблюдаемых у данного пациента) определить возможные причины, их породившие (болезни пациента). Во второй половине XX в. сформировалась область прикладной математики, занимающаяся решением подобных проблем. Она получила название теория распознавания образов . В предыдущем пункте показано, как распознавать "образ болезни", но подобная ситуация встречается весьма часто и в других областях науки. В геологии, например, причины труднодоступны, так как это — залегающие на разных глубинах полезные ископаемые. Но следствия сравнительно легко наблюдаемы: это — сопутствующие минералы, выходящие на поверхность, окраска почвы, характер растительности, данные сейсморазведки, аэро- и космической фотосъемки и т.п. В химии скрытые причины — это качественный состав и строение вещества, а наблюдаемые следствия — ответы в тестовых реакциях: помутнение, окраска, запах, выделение теплоты ит.п. В биологии: малодоступные гены контролируют легко наблюдаемые признаки. В криминалистике: скрывшийся преступник оставляет следы, улики, показания свидетелей.

В разных науках такое "распознавание образов" называется по-разному; для рассмотренных это — диагностика, геологическая разведка, анализ, раскрытие преступления и т.д. С точки зрения математики здесь решается одна задача, сформулированная как "распознавание образов". Решать ее в самой общей постановке и призвана математическая теория распознавания образов. Один из методов ее решения опирается на теорию булевых функций, которая позволяет в определенном смысле автоматизировать процесс решения, используя для этой цели ЭВМ.

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

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

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

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

$<\displaystyle a\lor b=b\lor a>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />	1 коммутативность
$<\displaystyle a\lor (b\lor c)=(a\lor b)\lor c>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />	2 ассоциативность
3.1 конъюнкция относительно дизъюнкции $<\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)>» width=»» height=»» /></td> <td>3.2 дизъюнкция относительно конъюнкции <img decoding=$ » width=»» height=»» />	3 дистрибутивность
$<\displaystyle a\lor \lnot a=1>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />	4 дополнительность (свойства отрицаний)
$<\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />	5 законы де Моргана
$<\displaystyle a\lor (a\land b)=a>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />	6 законы поглощения
$<\displaystyle a\lor (\lnot a\land b)=a\lor b>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />	7 Блейка-Порецкого
$<\displaystyle a\lor a=a>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />	8 Идемпотентность
$<\displaystyle \lnot \lnot a=a>» width=»» height=»» /></td> <td>9</td> <td><img decoding=$ » width=»» height=»» />	10 свойства констант
$<\displaystyle a\lor 1=1>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />
дополнение 0 есть 1 $<\displaystyle \lnot 0=1>» width=»» height=»» /></td> <td>дополнение 1 есть 0<img decoding=$ » width=»» height=»» />
$<\displaystyle (a\lor b)\land (\lnot a\lor b)=b>» width=»» height=»» /></td> <td><img decoding=$ » width=»» height=»» />	11 Склеивание

Примеры

Самая простая нетривиальная булева алгебра содержит всего два элемента, 0 и 1, а действия в ней определяются следующей таблицей:

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

гомоморфизмом алгебры Линденбаума — Тарского в двухэлементную булеву алгебру.

Множество всех подмножеств данного множества S образует булеву алгебру относительно операций ∨ := ∪ (объединение), ∧ := ∩ (пересечение) и унарной операции дополнения. Наименьший элемент здесь — пустое множество, а наибольший — всё S.

Если R — произвольное кольцо, то на нём можно определить множество центральных идемпотентов так:
A = < e ∈ R : e 2 = e, ex = xe, ∀x ∈ R >,
тогда множество A будет булевой алгеброй с операциями e ∨ f := e + f − ef и e ∧ f := ef.

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

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

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

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

Знаменитая вполне несвязного хаусдорфова топологического пространства.

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

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

Аксиома коммутативности: 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.

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

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