Булева алгебра - Boolean algebra


Из Википедии, свободной энциклопедии

В математике и математической логике , Булева алгебра является ветвью алгебры , в которой значение переменных являются истинностными значения истинными и ложными , обычно обозначает 1 и 0 соответственно. Вместо элементарной алгебры , где значения переменных являются числами, и простые операции : сложение и умножение, основные операции булевой алгебры являются конъюнкцией и обозначается как ∧, в дизъюнкции или обозначается как ∨, а отрицание не обозначается как ¬ , Таким образом , формализм для описания логических отношений таким же образом , что элементарная алгебра описывает числовые отношения.

Булева алгебра была введена Джордж Буль в своей первой книге Математический анализ логики (1847), и более подробно описывается в его Исследовании законов мышления (1854). По словам Хантингтона , термин «Булева алгебра» впервые была предложена Шеффером в 1913 году, хотя Чарльз Сандерс Пирс в 1880 году дал название «А алгебра с булевым One Constant» в первую главу своей книги «простейшие математики». Булева алгебра имеет фундаментальное значение в развитии цифровой электроники , и предоставляется во всех современных языках программирования. Он также используется в теории множеств и статистики .

история

Алгебра Буля предшествовала современные разработки в абстрактной алгебры и математической логики; это, однако , рассматривается как связано с происхождением обоих полей. В абстрактной обстановке, Булева алгебра была доведена до совершенства в конце 19 - го века Джевонса , Шрёдер , Хантингтон и другие , пока не достигла современной концепции (абстрактной) математической структуры . Например, эмпирические наблюдения , что можно манипулировать выражений в алгебре множеств , переводя их в выражения в алгебре Буля объясняется в современных условиях, говоря , что алгебра множеств Булева алгебра (обратите внимание на неопределенный артикль ). На самом деле, М. Стоун доказал в 1936 году , что каждая булева алгебра изоморфна к области наборов .

В 1930 - х годах, в то время как изучение коммутационных схем , Клод Шеннон заметил , что один может также применять правила алгебры Буля в этой ситуации, и он ввел переключение алгебры как способ анализа и проектирование схем алгебраических средств в терминах логических вентилей . Шеннон уже имел в своем распоряжении абстрактный математический аппарат, таким образом , он бросил его переключающий алгебру как два-элемента булевой алгебры . В настройках схемотехнических сегодня, нет нужды рассматривать другие булевы алгебры, таким образом , «переключающий алгебра» и «булева алгебра» часто используются как взаимозаменяемые. Эффективная реализация из булевых функций является одной из основных проблем в конструкции из комбинационных логических схем. Современные электронные автоматизации проектирования инструментов для СБИСА часто полагаются на эффективном представлении булевых функций , известные как (уменьшенные упорядоченные) бинарные диаграммы принятия решений (BDD) для логического синтеза и формальной верификации .

Логические предложения , которые могут быть выражены в классическом исчислении высказываний имеют эквивалентное выражение в булевой алгебре. Таким образом, булева логика иногда используются для обозначения исчисления высказываний выполняются таким образом. Булева алгебра не является достаточной для захвата логических формул с помощью кванторов , как и из логики первого порядка . Хотя развитие математической логики не следовать программе Буля, связь между его алгеброй и логикой была позже поставить на твердой почве в постановке алгебраической логики , которая также изучает алгебраические системы многих других логик. Проблема определения , является ли переменные данной булевой (пропозициональных) формулы могут быть назначены таким образом, чтобы формула оценки истина называется проблемой Булева выполнимость (СБ), и имеет важное значение для теоретической информатики , будучи первая проблема показано, что NP-полной . Тесно связана модель вычислений , известные как схемы булевой относится временная сложность (в качестве алгоритма ) для сложности схем .

Ценности

В то время как в элементарных выражений алгебры обозначают в основном числа , в булевой алгебре они обозначают истинностные значения ложь и правда . Эти значения представлены с битами (или двоичных цифр), а именно 0 и 1. Они не ведут себя как целые числа 0 и 1, для которых 1 + 1 = 2, но могут быть определены с элементами поля двухэлементной GF (2) , то есть целочисленной арифметики по модулю 2 , для которых 1 + 1 = 0. Сложение и умножение затем играть логические роли XOR (исключающее или) и и (конъюнкции) , соответственно, с дизъюнкции ху (включительно -или) определяемые , как х + у - ху .

Булева алгебра также имеет дело с функциями , которые имеют свои значения в множестве {0, 1}. Последовательность бит является широко используемой такой функцией. Другой распространенный примером является подмножествами множества Е : на подмножество Р из Й связан с индикаторной функцией , которая принимает значение 1 на F и 0 вне F . Наиболее общий пример является элементами булевой алгебры , со всеми из вышеуказанных случаев , являющихся их.

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

операции

Основные операции

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

  • И ( конъюнкция ), обозначаемая ху (иногда х и у или К х ), удовлетворяет еу = 1 , если х = у = 1 и ху = 0 в противном случае.
  • ИЛИ ( дизъюнкция ), обозначаемая ху (иногда х ИЛИ у или А х ), удовлетворяет еу = 0 , если х = у = 0 и ху = 1 в противном случае.
  • НЕ ( отрицание ), обозначаемые ¬ х (иногда НЕ х , Н х или! Х ), удовлетворяет ¬ х = 0 , если х = 1 и ¬ х = 1 , если х = 0.

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

Если истина значения 0 и 1 интерпретируются как целые числа, эти операции могут быть выражены с обычными операциями арифметики (где х + у использует сложение и х использует умножение), или с помощью минимальных / максимальных функций:

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

Вторичные операции

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

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

0 0 1 0 1
1 0 0 1 0
0 1 1 1 0
1 1 1 0 1

Первая операция, х  →  у , или С х , называется материальной импликацией . Если х истинно , то значение х  →  у берется что и у . Но если х ложно , то значение у можно пренебречь; Однако операция должна возвращать некоторое логическое значение , и есть только два варианта. Таким образом , по определению, х  →  у является истинным , когда х является ложным. ( Релевантность логика предполагает это определение Просматривая импликацию с ложной предпосылкой , как нечто иное , чем истинная или ложный.)

Вторая операция, х  ⊕  у или J х , называется исключающей или (часто сокращенно XOR) , чтобы отличить его от дизъюнкции как включительно рода. Это исключает возможность как х и у . Определено в терминах арифметики это сложение по модулю 2 , где 1 + 1 = 0.

Третья операция, дополнение исключающее или, является эквивалентность или Логическое равенство: х  ≡  у , или Е х , верно только тогда , когда х и у имеют одинаковое значение. Следовательно , х  ⊕  у в качестве дополнения можно понимать как х  ≠  у , будучи истинным только тогда , когда х и у различны. Аналог эквивалентности в арифметических модах 2, х + у + 1.

Принимая во внимание два операнда, каждый с двумя возможными значениями, есть 2 2 = 4 возможных комбинаций входов. Поскольку каждый выход может иметь два возможных значения, есть в общей сложности 2 4 = 16 возможных бинарных булевых операций .

Законы

Закон булевой алгебры является идентичностью таких как х ∨ ( уг ) = ( ху ) ∨ г между двумя булевыми точками, где булева термином определяются как выражение строится из переменных и констант 0 и 1 , используя операции ∧, ∨ и ¬. Эта концепция может быть расширена с точки зрения с участием других логических операций , таких как ⊕, →, и ≡, но такие расширения не нужны для целей , на которые ставятся законы. Такие цели включают в себя определение булевой алгебры , как и любая модель булевых законов, а также как средство для получения новых законов от стара , как и при выводе х ∨ ( уг ) = х ∨ ( гу ) от уг = гу , как обрабатывают в разделе , посвященном аксиоматизации .

законы Монотонные

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

Ассоциативность :
Ассоциативность :
Коммутативности :
Коммутативности :
Дистрибутивности над :
Идентичность для :
Идентичность для :
Annihilator для :

Следующие законы держат в булевой алгебре, но не в обычной алгебре:

Annihilator для :
Идемпотентности :
Идемпотентности :
Поглощение 1:
Поглощение 2:
Дистрибутивности над :

Принимая х = 2 в третьем законе выше показывает, что это не обычная алгебра закон, так как 2 × 2 = 4. Остальные пять законов могут быть фальсифицированы в обычной алгебре, принимая все переменные, чтобы быть 1, например, в абсорбции закона 1 левая сторона будет 1 (1 + 1) = 2 в то время как правая сторона будет 1, и так далее.

Все законы обработанными до сих пор были конъюнкции и дизъюнкции. Эти операции имеют свойство , что изменение либо аргумент либо выходит из выхода без изменений или изменений в выходные так же, как вход. Эквивалентное изменение любого переменного от 0 до 1 никогда не приводит к выходу меняется от 1 до 0. Операций с этим свойством называется монотонным . Таким образом, аксиомы до сих пор все было монотонной булевой логики. Немонотонности входит через дополнение ¬ следующим образом .

немонотонные законы

Операция комплемента определяется следующими двумя законами.

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

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

Но в то время как обычная алгебра удовлетворяет два законов

Булева алгебра удовлетворяет законам де Моргана :

завершенность

Законы , перечисленные выше , определяют булеву алгебру, в том смысле , что они влекут за собой остальную часть предмета. Законы Комплементация 1 и 2, а также с законами монотонных, достаточно для этой цели , и , следовательно , могут быть принята в качестве одного из возможных полного свода законов или аксиоматизаций булевой алгебры. Каждый закон булевой алгебры логически вытекает из этих аксиом. Кроме того, булевы алгебры , то могут быть определены как модель этих аксиом , как обработанные в раздел по этому вопросу .

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

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

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

Принцип: Если {X, R} является ч.у.м. , то {Х, R (обратный)} также ч.у.м..

Там нет ничего магического о выборе символов для значений булевой алгебры. Мы могли бы переименовать 0 и 1, чтобы сказать, α и р, и до тех пор, как мы делали так последовательно на протяжении все равно будет Булева алгебра, хотя и с некоторыми очевидными косметическими отличиями.

Но предположим, что мы переименуем 0 и 1 к 1 и 0 соответственно. Тогда он все равно будет Булева алгебра, и к тому же работает на одних и тех же значений. Однако это не будет идентична нашей исходной булевой алгебре, потому что теперь мы находим ∨ себя так, как ∧ используется, чтобы сделать и наоборот. Таким образом, есть еще некоторые косметические различия, чтобы показать, что мы были возились с обозначениями, несмотря на то, что мы до сих пор с помощью 0s и 1s.

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

Когда значения и операции могут быть соединены в пути , который оставляет весь важные неизменным , когда все пары переключаются одновременно, мы называем члены каждой пару два друг к другу. Таким образом , 0 и 1 имеют двойные, а ∧ и ∨ двойственны. Двойственность Принцип , называемый также De Morgan дуальность , утверждает , что Булева алгебра не изменяется , когда все дуальные пары меняются местами.

Одно из изменений , мы не должны сделать как часть этого обмена было дополнением. Мы говорим , что дополнение является самодвойственна операцией. Идентичность или ничегонеделания операция х (копия входа на выход) также самодвойственна. Более сложный пример автодуальных операций ( ху ) ∨ ( уг ) ∨ ( гх ). Там нет самодвойственны бинарной операции , которая зависит от обоего своих аргументов. Композиция автодуальных операций является автодуальной операцией. Например, если Р ( х , у , г ) = ( ху ) ∨ ( уг ) ∨ ( гх ), то F ( F ( х , у , г ), х , т ) является самостоятельным -двойственная работа четыре аргументов х, у, г, т .

Принцип двойственности можно объяснить из теории групп точки зрения тот факт , что существуют ровно четыре функции, один-к-одному отображений ( автоморфизмов ) множества булевых многочленов обратно к себе: тождественной функции, функции комплемента, двойная функция и функция contradual (дополнено двойной). Эти четыре функции образуют группу по функции композиции , изоморфную Klein четыре группы , действующие на множестве полиномов булевых. Вальтер Готшальк отметил , что , следовательно , более подходящее название для этого явления было бы в принципе (или квадрат ) из quaternality .

Схематические представления

диаграммы Венна

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

Три диаграммы Венна на рисунке ниже , представляют соответственно конъюнкции ху , дизъюнкции ху , и дополнить ¬ х .

Рисунок 2. Диаграмма Венна для конъюнкции, дизъюнкции и дополнения

Для связи, область внутри обоих кругов заштрихована , чтобы указать , что ху равно 1 , когда обе переменные равны 1. Другие регионы остаются незатененными , чтобы указать , что ху = 0 для остальных трех комбинаций.

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

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

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

Идемпотентность из ∧ и ∨ можно визуализировать, сдвинув два круга вместе , и отмечая , что заштрихованная область становится вся окружность, как для ∧ и ∨.

Чтобы увидеть первый закон поглощения, х ∧ ( ху ) = х , начнут с диаграммой в середине для йу и заметят , что часть заштрихованной области общего с й окружностью весь х окружностей , Для второго поглощения закона, х ∨ ( ху ) = х , начнут с левой диаграммой для йу и заметят , что затенение всего х результатов окружности в только х окружностях затемнены, так как предыдущий затенения был внутри х круг.

Закон двойного отрицания можно увидеть, дополняя затенение в третьей диаграмме ¬ х , что оттенки х круг.

Для того, чтобы визуализировать первый закон Де Моргана, (¬ х ) ∧ (¬ у ) = ¬ ( ху ), начните со средней диаграммы ху и дополнить его затенения так , что только область вне обоих кругов заштрихована, которые является то , что правая часть закона описывает. Результат такого же , как если бы мы затененные ту область , которая одновременно вне й круга и вне у круга, т.е. конъюнкции их экстерьеров, что и левая рука закона описывает.

Второй закон Де Моргана (¬ х ) ∨ (¬ у ) = ¬ ( ху ), работает так же , как с двумя диаграммами поменять местами.

Первый закон дополнения, х ∧¬ х = 0, говорит о том , что внутренняя и внешняя часть х окружности не перекрываются. Второе дополнение закон, х ∨¬ х = 1, говорит , что все это либо внутри , либо снаружи й круга.

Цифровые логические вентили

Цифровая логика является применением булевой алгебры 0 и 1 в электронное аппаратное обеспечение , состоящее из логических элементов , соединенных с образованием схемы . Каждые ворота реализует булеву операцию, и изображен схематически в форме , указывающей операцию. Формы , связанные с воротами для связи (И-вентилей), дизъюнкции (ИЛИ-вентилей), и дополнения (инверторы) следующим образом .

LogicGates.GIF

Линии на левой части каждого ворот представляют собой входные провода или порты . Значение входного сигнала представлена напряжением на свинец. Для так называемого «активного» высокой логики, 0 представлен напряжением , близкой к нулю или «земли», в то время как 1 представлено напряжение близко к напряжению питания; активные низкие переворачивает это. Линия справа от каждых ворот представляет собой выходной порт, который обычно следует за одни и те же условные напряжения в качестве входных портов.

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

Двойственность Принцип , или законы Де Моргана , можно понимать как утверждение , что все три дополняя порты логический элемент преобразует его в логический элемент ИЛИ и наоборот, как показано на рисунке 4 ниже. Дополнение оба порта инвертора однако оставляет операцию без изменений.

DeMorganGates.GIF

В более общем смысле можно дополнить любого из восьми подмножеств трех портов либо И или ИЛИ ворот. Получаемые шестнадцать возможностей вызвать лишь восемь логических операции, а именно с нечетным числом 1 в их таблице истинности. Есть восемь таких , потому что «нечетный бит из» может быть либо 0 или 1 и могут пойти в любом из четырех позиций в таблице истинности. Там быть шестнадцать двоичных логических операций, это должно оставить восемь операций с четным числом 1 в их таблицы истинности. Два из них являются константами 0 и 1 ( в виде двоичных операций , которые игнорируют оба их вход); четыре операция , которые зависят от нетривиальных точно одного из своих двух входов, а именно х , у , ¬ х , и ¬ у ; а остальные две являются ху (исключающее ИЛИ ) и его дополнение ху .

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

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

Конкретные булевы алгебры

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

(Как и в сторону, исторически X сам по себе должен был быть непустым , а также , чтобы исключить вырожденные или один элемент булева алгебра, которая является одним исключением из правила , что все булевы алгебры удовлетворяют тем же уравнениям , поскольку вырожденных алгебры удовлетворяет каждое уравнение. Однако , это исключение конфликтует с предпочтительным чисто эквациональным определением «булевой алгебра» , так как нет никакого способа , чтобы исключить один-элемент алгебру с использованием только equations- 0 ≠-не считается, будучи отрицанием уравнения. Поэтому современные авторы позволяют вырождаются булева алгебра и пусть X пусто.)

Пример 1. силовой агрегат 2 X из X , состоящее из всех подмножеств X . Здесь X может быть любым набор: пусто, конечный, бесконечный, или даже несчетный .

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

Пример 3. Множество конечных и коконечны наборы целых чисел, где множество коконечно является одним пропустив лишь конечное число целых чисел. Это явно замкнуто относительно дополнения, и закрывается при союзе , потому что объединение коконечны набором с любым набором коконечно, в то время как объединение двух конечных множеств конечно. Пересечения ведет себя как союз с «конечным» и «коконечен» поменять местами.

Пример 4. Для менее тривиального примера точки , сделанной в примере 2, рассмотрит схему Венна , образованной п замкнутых кривых Partitioning диаграммы на 2 п областей, и пусть X будет (бесконечное) множество всех точек в плоскости не на любой кривой , но где - то в пределах диаграммы. Внутренняя часть каждой области, таким образом , бесконечное подмножество X , и каждая точка X находится точно в одном регионе. Тогда множество всех- 2 п возможных объединений регионов ( в том числе пустого множества , полученное как объединение пустого множества областей и X , полученные как объединение всех 2 п регионов) замкнуто относительно объединения, пересечения и дополнения по отношению к X и , следовательно , образует конкретную булеву алгебру. Опять мы имеем конечное число подмножеств бесконечного множества , образующее конкретную булеву алгебру, с примером 2 , возникающим в случае п = 0 из каких - либо кривых.

Подмножество как битовые векторы

Подмножество Y из X могут быть идентифицированы с помощью индексированного семейства битов с индексом множества X , причем бит индексируется хХ равно 1 или 0 , в зависимости от наличия или отсутствия хY . (Это так называемая характеристической функция понятие подмножества). Например, 32-разрядный компьютер слово а состоит из 32 бит , индексированных множеством {0,1,2, ..., 31}, с 0 и 31 индексацией низкий и высокий порядок биты соответственно. Для уменьшения размера , например, если Х = { а, Ь, с } , где а, б, в , рассматриваются как позиции битов в указанном порядке слева направо, восемь подмножеств {}, { C }, { Ь }, { Ь , с }, { }, { , с }, { , Ь } и { , Ь , с } из X может быть идентифицирована с соответствующим битом векторов 000, 001, 010, 011, 100, 101, 110 и 111. Битовые векторы , индексированные множества натуральных чисел бесконечные последовательности битов, в то время как те , индексируется чисел в единичном интервале [0,1] упакованы слишком плотно , чтобы иметь возможность написать условно , но тем не менее , образуют хорошо определенные индексированные семьи (представьте окраски каждую точку отрезки [0,1] черной или белой независимо друг от друга, черные точки , то образуют произвольное подмножество [0,1]).

С этого битового вектора точки зрения, конкретная Булева алгебра может быть эквивалентно определена как непустое множество битовых векторов все той же длины ( в более общем случае , индексируется одним и тем же набором) и закрывается под бит векторных операций побитового ∧, ∨, и ¬, как в 1010∧0110 = 0010, = 1110 1010∨0110 и ¬1010 = 0101 бит векторных реализации пересечения, объединения и дополнение соответственно.

Прототипом Булева алгебра

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

Законы удовлетворяют все невырожденные конкретными булевыми алгебрами совпадают с удовлетворены прототипичной булевой алгеброй.

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

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

Булевы алгебры: определение

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

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

Булева алгебра это любой набор с бинарными операциями ∧ и ∨ и одноместный операция ¬ на нем , удовлетворяющем булевы законы.

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

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

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

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

Представимые булевы алгебры

Хотя каждая конкретная Булева алгебра является булевой алгеброй, не всякая булева алгебра должен быть конкретным. Пусть п быть бесквадратно положительное целое число, не делится на квадрат целого числа, например 30 , но не 12. Операции наибольший общий делитель , наименьшее общее кратное , и деления на п (то есть, ¬ х = п / х ), можно показать , чтобы удовлетворить все логические законы , когда их аргументы пробегают положительные делители п . Следовательно , эти делители образуют булеву алгебру. Эти делители не являются подмножествами множества, делая делители п булева алгебра , которая не конкретно по нашим определениям.

Однако, если мы представить каждый делитель п множеством своих главных факторов, мы находим , что эта nonconcrete Булева алгебра изоморфна к конкретной булевой алгебре , состоящей из всех множеств простых делителей п , с объединением , соответствующим наименьшему общего кратного, пересечение чтобы наибольший общий делитель, а дополнение к разделению в п . Так что этот пример пока технически не бетон по крайней мере , «морально» бетон с помощью этого представления, называется изоморфизмом . Этот пример является экземпляром следующего понятия.

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

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

Каждая булева алгебра представима.

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

Законы удовлетворяют все булевы алгебрами совпадают с удовлетворены прототипичной булевой алгеброй.

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

Аксиоматизирующих Булева алгебра

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

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

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

Вводя дополнительные законы , не перечисленные выше, становится возможным сократить список еще дальше. В 1933 году Эдвард Хантингтон показал , что если основные операции берется ху и ¬ х , с ху считается производной операции (закон , например , с помощью Де Моргана в виде ху = ¬ (¬ х ∨¬ у )), то уравнение ¬ (¬ х ∨¬ у ) ∨¬ (¬ ху ) = х вместе с двумя уравнений , выражающих ассоциативности и коммутативности ∨ полностью аксиоматизирована булевой алгебре. Когда только основные операции бинарной операции NAND ¬ ( ху ), Стивен Вольфрам предложил в своей книге Новый вид науки единственной аксиомой ((( ху ) г ) ( х (( XZ ) х ))) = г как одно уравнения аксиоматизация булевой алгебры, где для удобства здесь х обозначает NAND , а не из и х и у .

Логика высказываний

Логика высказываний является логической системой , которая тесно связана с булевой алгеброй. Многие синтаксические понятия булевой алгебры переносятся логики лишь с незначительными изменениями в обозначениях и терминологии, а семантика логики определяютсяпомощью булевых алгебр таким образомчто тавтологии (теоремы) логики высказываний соответствуют Эквациональной теореме булевой алгебры ,

Синтаксический, каждая булева член соответствует пропозициональной формуле логики высказываний. В этом переводе между булевой алгеброй и логикой, логическим переменными х, у ... становятся пропозициональным переменных (или атомы ) P, Q , ..., логические термины , такими как ху становится пропозициональными формулы PQ , 0 становятся ложным или , и 1 становится истинным или Т . Это удобно , когда речь общих положений , чтобы использовать греческие буквы Ф, ф, ... , как метапеременные (переменные вне языка исчисления высказываний, используемого при разговоре о исчислении) для обозначения положения.

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

Эта семантика допускает перевод между тавтологиями логики высказываний и эквациональными теоремами булевой алгебры. Каждая тавтологию Φ из логики может быть выражена в виде булевой уравнение Ф = 1, который будет теоремой булевой алгебры. Обратно каждая теорема Φ = Ψ булевой алгебры соответствует тавтологиям (Φ∨¬Ψ) ∧ (¬Φ∨Ψ) и (Φ∧Ψ) ∨ (¬Φ∧¬Ψ). Если → находится на языке эти последние тавтологиями также может быть записана в виде (Φ → Ψ) ∧ (Ψ → Φ), или как два отдельных теоремы Ф → Ф и Ч → Ф; если ≡ доступен, то единственная тавтология Φ ≡ Ψ может быть использован.

Приложения

Одним из мотивации применения исчисления высказываний является анализ предложений и дедуктивных рассуждений на естественном языке. В то время как предложение « если х = 3 , то х + 1 = 4» , зависит от значений таких символов , как + и 1, то предложение « если х = 3 , то х = 3» нет; это верно только в силу своей структуры, и остается верным ли « х = 3» заменяется на « х = 4» или «луна сделана из зеленого сыра.» Родовая или абстрактная форма этой тавтологии является « если Р , то Р », или на языке алгебры логики, « PP ».

Замена Р от й = 3 или любого другого предложения, называется экземпляром из P этого предложения. Результат инстанцирования P в абстрактном предложении, называется экземпляром предложения. Таким образом , « х = 3 → х = 3» является тавтологией в силу того , является экземпляром абстрактного тавтологией « PP ». Все вхождения в реализованном переменном должны быть созданы с тем же предложением, чтобы избежать такого бреда как Pх = 3 или х = 3 → х = 4.

Исчисление ограничивает внимание абстрактных положений, построенных по сравнению с пропозициональных переменных с помощью булевых операций. Инстанцирование по - прежнему возможно в исчислении высказываний, а только инстанцировании пропозициональные переменные абстрактных положений, таких как инстанцировании Q с помощью QP в P → ( QP ) , чтобы получить экземпляр Р → (( QP ) → P ).

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

Дедуктивные системы логики

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

Sequent исчисление

Исчисление обычно организована в виде системы Гильберта , чьи операции только те булевой алгебры и чьи теоремы являются булевыми тавтологии, эти логические условия , равные булевой константой 1. Другой формой является исчисление секвенций , которое имеет два вида, предложения , как в обычном исчисление и пары списков предложений , называемых секвенции , таких как AB , AC , ... A , BC , .... Две половинки секвенции называется антецедентом и сукцедентом соответственно. Обычные метапеременный , обозначающий антецедент или его часть является Γ, и для сукцедента А; Таким образом , Γ, Δ обозначало бы секвенцию которого сукцедентный список Δ и чья предшествующий список Γ с дополнительным высказыванию А приложенном после него. Антецедент интерпретируются как совместно ее положения, сукцедент как дизъюнкции ее положений, и секвенция в качестве самого следования в сукцеденте по антецеденту.

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

Приложения

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

компьютеры

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

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

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

Компьютеры используют два-значение булевых схемы по указанным выше причинам. Наиболее распространенное использование компьютерных архитектур упорядоченных последовательностей булевых значений, называемые биты, 32 или 64 значений, например 01101000110101100101010101001011. При программировании в машинном коде , ассемблере и некоторых других языках программирования , программисты работают с цифровой структурой низкого уровня из регистры данных . Эти регистры работают на напряжениях, где ноль вольт представляет Логическое 0, и опорное напряжение (часто + 5V, + 3.3V, + 1,8В) представляет собой булеву 1. Такие языки поддерживают как числовые операции и логические операции. В этом контексте, «числовой» означает , что компьютер обрабатывает последовательность бит в качестве двоичных чисел (два числа базовых) и выполняет арифметические операции , такие как сложение, вычитание, умножение, деление , или. «Логические» относится к логическим операциям булевых дизъюнкции, конъюнкции и отрицания между двумя последовательностями бит, в котором каждый бит в одной последовательности просто по сравнению с ее аналогом в другой последовательности. Поэтому Программисты имеют возможность работать в и применении правил либо числовой алгебры или булевой алгебры , как это необходимо. Сердечник дифференцировании функции между этими семействами операций является наличие переноса операции в первой , но не второй.

Двузначной логики

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

Центральное понятие теории множеств является членство. Теперь организация может позволить несколько степеней членства, такие как новичок, соратник и полный. С наборами Однако элемент либо внутрь или наружу. Кандидаты на членство в множестве работ так же, как провода в ЦВМ: каждый кандидат является либо членом или нечленом, так же, как каждый провод высокий или низкий.

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

Двузначная логика может быть расширена до многозначной логики , в частности , путем замены домена Boolean {0, 1} с единичным интервалом [0,1], в этом случае , а не только принимает значение 0 или 1, любое значение между и в том числе 0 и 1 можно предположить. Алгебраически, отрицание (NOT) заменяется на 1 -  х , конъюнкции (И) заменяется умножением ( ) и дизъюнкции (ИЛИ) определяется с помощью закона Де Моргана . Интерпретация этих значений в качестве логических значений истинности дает многозначную логику, которая формирует основу для нечеткой логики и вероятностной логики . В этой интерпретации, значение интерпретируется как «степень» правды - в какой степени суждение верно, или вероятность того, что предложение является истинным.

Логические операции

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

Естественные языки , такие как английский имеют слова для нескольких логических операций, в частности , соединение ( и ), дизъюнкции ( или ), отрицание ( не ), и вывод ( подразумевают ). Но не является синонимом и не . Когда используются для объединения ситуационного утверждения , таких как «блок на столе» и «кошки пьют молоко,» наивно является либо истинными , либо ложными, значение этих логических связок часто имеет смысл их логических аналоги. Однако, с описаниями поведения, как «Джим прошел через дверь», один начинает замечать различия , такие как отказ от коммутативности, например , конъюнкция «Джим открыл дверь» с «Джим прошел через дверь» в том , что заказ не соответствует их вместе в другом порядке, так и , как правило , означает и то в таких случаях. Вопросы могут быть подобны: заказ «небо синее, и почему небо голубое?» имеет больше смысла , чем в обратном порядке. Присоединительные команды о поведении, как поведенческие утверждения, как в Одевайся и идти в школу . Дизъюнктивные такие команды любят меня или оставить меня или рыбу или вырезать приманки , как правило, асимметричны по смыслу , что одна альтернатива является менее предпочтительным. Сиамские существительные , такие как чай и молоко обычно описывают , как агрегирование с множественным объединением в то время как чай или молоко является выбор. Однако контекст может изменить эти чувства, как и в вашем выборе, кофе и чай , который обычно означает то же самое , как ваш выбор кофе или чай (варианты). Двойное отрицание , как и в «Я не не люблю молоко» редко буквально означает «я как молоко» , а скорее передает какие - то хеджирование, как бы подразумевает , что есть третья возможность. «Не не P» можно свободно интерпретировать как «уверенно Р», и хотя P обязательно означает «не не P » обратный подозреваемый на английском языке, так же как и с интуиционистской логикой . Ввиду весьма своеобразного использование конъюнкции на естественных языках, Булева алгебра не может рассматриваться в качестве надежной основы для их интерпретации.

Логические операции используются в цифровых логиках для объединения бит , передаваемых по отдельным проводам, таким образом , их интерпретации над {0,1}. Когда вектор п идентичных двоичных вентилей используются для объединения двух битовых векторов , каждый из п бит, отдельные битовые операции могут быть поняты вместе как одну операцией на значения из булевой алгебры с 2 п элементами.

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

256-элементная свободная булева алгебра на трех генераторах развернута в компьютерных дисплеях на основе растровой графики , которые используют битовое блитирование манипулировать целую область , состоящие из пикселей , опираясь на булевых операциях , чтобы определить , как область источника должен быть объединена с назначением, как правило , с помощью третьей области , называемой маски . Современные видеокарты предлагают все 2 - 3  = 256 тройных операции для этой цели, при выборе операции является параметром один байты (8 бит). Константы SRC = 0xAA или 10101010, ДСТ = 0xCC или 11001100, и ММС = 0xf0 или 11110000 позволяют логические операции , такие как (SRC ^ DST) и MSK ( что означает XOR источника и получателя , а затем и результат с маской) , чтобы быть написаны непосредственно в качестве константы , обозначающех байты , рассчитанных во время компиляции, 0x60 в (SRC ^ DST) & пример MSK, 0x66 , если только SRC ^ DST и т.д. во время выполнения видеокарта интерпретирует байты как операции растры , указанные исходное выражение единообразно , что требует удивительно мало аппаратных средств и которая занимает много времени полностью независимо от сложности выражения.

Твердые моделирования система автоматизированного проектирования предлагает различные методы для создания объектов из других объектов, комбинаций булевых операций является одним из них. В этом методе пространство , в котором существуют объекты понимается как множества S из вокселей (трехмерный аналог пикселей в двумерной графики) и формы определяются как подмножества S , позволяя объекты быть объединены в виде наборов с помощью объединения, пересечение и т.д. Одно очевидное применение в строительстве сложной формы от простых форм просто как объединение последнего. Другое использование в Скулптинге понимается как удаление материала: любой помол, фрезерование, маршрутизация, или операции бурения , которые могут быть выполнены с физической машиной на физических материалах может быть смоделированы на компьютере с булевой операцией х  ∧ ¬ у или х  -  у , которая в теории множеств установлено значение, удалить элементы у от тех х . Таким образом , учитывая две формы одного, подлежащей обработке , а другой материал должен быть удален, в результате механической обработки первое , чтобы удалить последние описывается просто как их установить разницу.

булевы поиски

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

  • Doublequotes используются, чтобы объединить разделенные пробелами слова в единый термин поиска.
  • Пробелы используется для указания логического элемента И, как это оператор по умолчанию для соединения для поиска:
"Search term 1" "Search term 2"
  • Или ключевое слово используется для логического ИЛИ:
"Search term 1" OR "Search term 2"
  • Префиксом знак минус используется для логического NOT:
"Search term 1" −"Search term 2"

Смотрите также

Рекомендации

генеральный

Мано, Моррис; Ciletti, Michael D. (2013). Digital Design . Пирсон. ISBN  978-0-13-277420-8 .

дальнейшее чтение

  • J. Элдоном Whitesitt (1995). Булева алгебра и ее приложения . Courier Dover Publications. ISBN  978-0-486-68483-3 . Подходит введение для студентов в прикладных областях.
  • Двингер, Филипп (1971). Введение в булевы алгебры . Вюрцбург: Physica Verlag.
  • Сикорский, Роман (1969). Булевы алгебры (3 / е изд.). Berlin: Springer-Verlag. ISBN  978-0-387-04469-9 .
  • Бохенский, Юзеф Мария (1959). Конспект математической логики . В переводе с французского и немецкого издания Отто птице. Дордрехт, Южная Голландия: D. Reidel.

Историческая перспектива

внешняя ссылка