Алгебра буля: алгебра буля — это… Что такое алгебра буля?

Содержание

алгебра буля — это… Что такое алгебра буля?

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

Буль представляет логику как алгебру классов (будем обозначать их символами А, В, С,…). Основными операциями в А. Б. являются: сложение классов AE.B; умножение классов АCВ; дополнение класса А\’. Свойства этих операций описываются следующими аксиомами:

la. AE(BEC)=(AEB) EC — ассоциативность сложения;

16. AC(BCC)= (ACВ) EC — ассоциативность умножения;

2a.AEB= BEA — коммуникативность сложения;

2б.АCВ =ВCА — коммуникативность умножения;

3a.AE(ВCС)= =(AEB) C(AEC) — дистрибутивность сложения относительно умножения;

36.AC(BEC)==(ACB) E(ACC) — дистрибутивность умножения относительно сложения.

В А. Б. существуют два элемента 0 и 1, операции с которыми

подчиняются следующим соотношениям:

AE0=A;

AC1=A;

AEA\’=1;

ACA\’=0.

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

равна А: АEА=А, а не 2А, как в обычной алгебре. Точно так же и произведение двух A равно A: АCА=А, а не A2.

Важным законом А. Б. является принцип двойственности, согласно которому если в некотором справедливом равенстве мы заменим все вхождения E на C и C на E, 1 на 0 и 0 на 1, то получим равенство, двойственное первому и также справедливое. Примерами двойственных равенств являются приведенные выше аксиомы.

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

Б. часто используются для иллюстрации и прояснения отношений между объемами понятий.

Словарь по логике. — М.: Туманит, изд. центр ВЛАДОС. А.А.Ивин, А.Л.Никифоров. 1997.

БУЛЕВА АЛГЕБРА — это… Что такое БУЛЕВА АЛГЕБРА?

БУЛЕВА АЛГЕБРА

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



Это — алгебра лотки. На рисунке проиллюстрированы пять основных логических утверждении. Для любого из них, если А верно, то в таблице появляется «1». Если А ложно, появляется «О». В утверждении типа «И» С верно (т.е. в таблице имеется 1), когда верны А и В, но ложно, если и А, и В ложны. В утверждении «ИЛИ» С верно, если верно либо А, либо В, и ложно только в том случае, если и А, и В ложны. Утверждение «НЕТ» имеет один вход и один выход, его функция заключается в перемене местами «верного» и «ложного»; применение его к выражениям «И» и «ИЛИ» дает соответственно «НЕ» и «НИ». Утверждения Булевой алгебры,показанные здесь, можно также изобразить как элементы электрического контура (ввод слева, выход справа) или, по способу ы, как в теории множеств (результат обозначен на рисунке закрашиванием соответствующих участков).

Научно-технический энциклопедический словарь.

Смотреть что такое «БУЛЕВА АЛГЕБРА» в других словарях:

  • БУЛЕВА АЛГЕБРА —     БУЛЕВА АЛГЕБРА см. Алгебра логики. Новая философская энциклопедия: В 4 тт. М.: Мысль. Под редакцией В. С. Стёпина. 2001 …   Философская энциклопедия

  • Булева алгебра — раздел математической логики, изучающий высказывания и операции над ними. Наиболее известными операциями булевой алгебры являются: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание. По английски: Boolean algebra См. также: Логические …   Финансовый словарь

  • БУЛЕВА АЛГЕБРА — Boolean algebra От Дж.Буль английский математик 1815 1864 Раздел математической логики, изучающий высказывания и операции над ними. Наиболее известными операциями булевой алгебры являются: конъюнкция, дизъюнкция, импликация, эквивалентность,… …   Словарь бизнес-терминов

  • Булева алгебра — Эта статья об алгебраической системе. О разделе математической логики, изучающем высказывания и операции над ними, см. Алгебра логики. Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями (аналог конъюнкции),… …   Википедия

  • булева алгебра — Boolean algebra statusas T sritis automatika atitikmenys: angl. Boolean algebra vok. Boolesche Algebra, f rus. булева алгебра, f pranc. algèbre de Boole, f ryšiai: sinonimas – Bulio algebra …   Automatikos terminų žodynas

  • БУЛЕВА АЛГЕБРА — булева решетк а, частично упорядоченное множество специального вида. Б. а. наз. дистрибутивная решетка (дистрибутивная структура), имеющая наибольший элемент 1 единицу Б. а., наименьший элемент 0 нуль Б. а. и содержащая вместе с каждым своим… …   Математическая энциклопедия

  • Булева алгебра — алгебра, в которой каждая переменная может принимать одно из двух значений: «истина» или «ложь». Операции над переменными в булевой алгебре называются логическими операциями. Правила выполнения логических операций удобны для преобразования… …   Начала современного естествознания

  • БУЛЕВА АЛГЕБРА — Названная по имени ее создателя, английского математика Джорджа Буля, система операций с символами, которая использует алгебраические процедуры, но независимо от определенных математических интерпретаций.

    Булева логика, или калькуляция (как она… …   Толковый словарь по психологии

  • Булева алгебра — (араб.) – система алгебраических операций с символами, названная в честь Д. Буля, одного из её создателей. Также называется калькуляцией (лат. calсulatio – счёт, подсчёт). Интересно, что Д. Буль рассматривал свою работу как представление основных …   Энциклопедический словарь по психологии и педагогике

  • булева алгебра элементарных логических операции — — [http://slovarionline.ru/anglo russkiy slovar neftegazovoy promyishlennosti/] Тематики нефтегазовая промышленность EN Boolean algebra …   Справочник технического переводчика

Книги

  • Дискретная математика. Учебное пособие, Шевелев Юрий Павлович. Представлено пять тем: теория множеств, булева алгебра логики, теория конечных автоматов, комбинаторика и теория графов. Из теории множеств освещены темы: алгебра множеств, бинарные… Подробнее  Купить за 3613 руб
  • Дискретная математика, Шевелев Ю. . Представлено пять тем: теория множеств, булева алгебра логики, теория конечных автоматов, комбинаторика и теория графов. Из теории множеств освещены темы: алгебра множеств, бинарные… Подробнее  Купить за 2143 руб
  • Дискретная математика, Ю. П. Шевелев. Представлено пять тем: теория множеств, булева алгебра логики, теория конечных автоматов, комбинаторика и теория графов. Из теории множеств освещены темы: алгебра множеств, бинарные… Подробнее  Купить за 1836 руб
Другие книги по запросу «БУЛЕВА АЛГЕБРА» >>

Алгебра Буля

§ 4 Функции алгебры логики

4.1 Алгебра Буля

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

 

            Рассмотрим непустое множество М элементов любой природы , в котором определены отношения «=» (равно) и три операции: «+» (сложение), «*» (умножение) и «-» (отрицание), подчиняющиеся следующим аксиомам:

 

Коммутативные законы:

1а. x+y=y+x                       1б. x*

y=y*x

 

Ассоциативные законы:

2а. x+(y+z)=(x+y)+z          2б. x*(y*z)=(x*y)*z

 

Дистрибутивные законы:

3а. (x+y)*z=(x*z)+(y*z)      3б. (x*y)+z=(x+z)*(y+z)

 

Законы идемпотентности:

4а. x+x=x                           4б. x*x=x

 

Закон снятия двойного отрицания:

5.

 

Законы де-Моргана:

6а.                   6б.

 

Законы поглощения:

7а. x+(y*x)=x                       7б. x*(y+x)=x

 

            Такое множество М называется булевой алгеброй. Если под основными элементами  рассматривать высказывания, а под операциями «+», «*»,   «-» дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства как знак равносильности, то, как следует из равносильностей I, II и III групп, все аксиомы булевой алгебры выполняются. Значит, алгебра логики является интерпретацией булевой алгебры.

 

200 лет со дня рождения Джорджа Буля :: Государственный Университет Телекоммуникаций

Джордж Буль родился 2 ноября 1815 года в Линкольне (Англия), в семье бедного башмачника. Хотя он был современником Ч. Бэббиджа, но происходил не из привилегированного класса, как Бэббидж.

Выходец из слоя общества, дети которого фактически были лишены посещения университета, Джордж должен был заниматься самостоятельно. Хотя промышленная революция уже произошла в Англии, знание древних языков было показателем уровня образования джентльмена. Конечно, ника­кой латинский или греческий не преподавали в школе, которую посещал Буль. Буль сам изучил греческий и латинский, пользуясь поддержкой малообразованного отца, и в возрасте 12 лет сумел перевести оду Хорейса на английский язык. Ничего не понимая в качестве техники перевода, гордый отец Буля все-таки напечатал его в местной газете. Некоторые специалисты заявляли, что 12-летний мальчик не мог сделать такой перевод, другие отме­чали серьезные технические дефекты перевода. 

Расширив общий метод Лейбница, сформулированный на 188 лет раньше, в котором все истинные причины были сведены к виду вычислений, английский математик Д. Буль в 1854 году заложил основу того, что мы сегодня знаем как математическую логику, опубликовав работу “Исследование законов мышления”.

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

Его теория логики, основанная на трех основных действиях — AND (и), OR (или), NOT (не), — должна была стать в XX веке основой для разработки переключающих телефонных линий и проекта ЭВМ. Так же, как и идеями Лейбница, булевой алгеброй пренебрегали в течение многих лет после того, как она была создана.

Несмотря на большое значение булевой алгебры во многих других областях математики, необычайная работа Буля в течение многих лет считалась странностью. Как и Бэббидж, Буль был человеком, опередившим свое время. Это произошло раньше, чем Альфред Уайтхед и Бертран Рассел опубликовали свой трехтомник “Принципы математики” (1910—1913), в котором рассматривались вопросы формальной логики.

Жена Буля была племянницей Джорджа Эвереста, в 1841 году завершившего в Индии грандиозные по масштабам работы. В честь его заслуг высочайшая вершина мира Джомолунгма в Гималаях одно время даже именовалась Эверестом. Сама Мэри, в отличие от жен многих других математиков, понимала научные идеи своего мужа и своим внимани­ем и участием подвигала его на продолжение исследований. После его смер­ти она написала несколько сочинений и в последнем из них — “Философия и развлечения алгебры”, — опубликованном в 1909 году, пропагандировала математические идеи Джорджа.

У четы Булей было пять дочерей. Старшая, Мэри, вышла замуж за Ч. Хин-тона — математика, изобретателя и писателя-фантаста — автора широко из­вестной повести “Случай в Флатландии”, где описаны некие существа, жи­вущие в плоском двухмерном мире. Из многочисленного потомства Хинто-нов трое внуков стали учеными: Говард — энтомологом, а Вильям и Джоан — физиками. Последняя была одной из немногих женщин-физиков, принимавших участие в работе над атомным проектом в США.

Вторая дочь Булей, Маргарет, вошла в историю как мать крупнейшего анг­лийского механика и математика, иностранного члена Академии наук СССР Джеффри Тэйлора. Третья, Алисия, специализировалась в исследовании многомерных пространств и получила почетную ученую степень в Гронин-генском университете. Четвертая, Люси, стала первой в Англии женщиной-профессором, возглавившей кафедру химии.

Но наиболее известной из всех дочерей Булей стала младшая, Этель Лили­ан, вышедшая замуж за ученого — эмигранта из Польши Войнича. Войдя в революционную эмигрантскую среду, она написала прославивший ее на весь мир роман “Овод”. За ним последовало еще несколько романов и му­зыкальных произведений, а также перевод на английский язык стихотворе­ний Тараса Шевченко. Войнич скончалась в Нью-Йорке в возрасте 95 лет, немного не дожив до столетия со дня смерти своего знаменитого отца мате­матика Джорджа Буля.

Алгебра событий или алгебра Буля

В теории вероятностей и теории множеств используют графические диаграммы Венна, которые позволяют изображать основные операции с множествами или событиями. Выделяют четыре основные операции: сложение множеств или событий, умножение, вычитание и отрицание. На рисунке справа приведены графические диаграммы для перечисленных операций. На картинках штриховкой отмечен результат операции. Событие в теории вероятностей можно представлять как множество. Приведем основные определения для событий и операций над ними.
Определение 1. События А и В называются равными, если наступление события А влечет за собой наступление события В и наоборот. Обозначение: \(A=B\).
Определение 2. Суммой событий А и В называется событие \(A+B\), состоящее в том, что в опыте произойдет хотя бы одно из этих событий.
Определение 3. Произведением событий А и В называется событие \(AB\), состоящее в одновременном появлении этих событий.
Определение 4. Разностью событий А и В называется событие А\В, состоящее в том, что событие А произойдет, а событие В – не произойдет.
Определение 5. Событие называется противоположным событию А, если оно заключается в не появлении события А. Обозначение противоположного события: \(\overline{A}\)
На основе этих определений можно получить основные тождества, так называемой алгебры Буля или булевой алгебры. Это соотношения для множеств или событий. Большинство из них легко понимаются и похожи на обычные свойства операций. На рисунке справа (кликнуть для увеличения) приведены 18 наиболее часто используемых равенств. Эти равенства используют для доказательства равенств, задающих сложные события или множества. Вы можете скачать этот справочник по ссылке внизу этой страницы. Файл в формате *.doc и его можно распечатать в текстовом редакторе Word. Приведем пример для решения которого будут использованы эти тождества.
Пример. Доказать что \(A+AB+BC+\overline{A}C=A+C\).
Решение. Пользуясь формулами операций над множествами (тождества булевой алгебры), получим последовательно из левой части равенства правую. В фигурных скобках будем записывать номер использованной формулы (смотрите номера формул на картинке вверху): $$A+AB+BC+\overline{A}C=\left\{5 \right\}=\left(A+\overline{A}C \right)+\left(AB+BC \right)=\left\{7 \right\}=$$ $$=\left(A+\overline{A}C \right)+B\left(A+C \right)=\left\{17 \right\}=\left(A+\overline A \right)\left(A+C \right)+B\left(A+C \right)=\left\{11 \right\}=$$ $$=\Omega\left(A+C \right)+B\left(A+C \right) =\left\{7 \right\}=\left(\Omega+B \right)\left(A+C \right)=\left\{8 \right\}=$$ $$=\Omega\left(A+C \right)=\left\{10 \right\}=A+C$$ Таким образом, из левой части последовательно получили правую часть. Значит равенство верное. Это строгое доказательство (аналитическое), так как для преобразований были использованы тождества алгебры Буля. Пример графического решения этого примера с помощью диаграмм Венна приведен на рисунке внизу. Последовательно построены диаграммы для разных фрагментов выражения и показано (последняя картинка), что выражение левой части равно правой: \(A+C\). Не всегда удается получить строгое доказательство. А если равенство не верное, то найти решение еще труднее, так как проводя преобразования надо равенство привести к явно противоречивому. Если найти решение не удается, то можно попробовать графический метод решения. Графический метод с использованием диаграмм Венна проще, но он не является строгим или полным решением в том случае, если равенство справедливо. Это объясняется тем, что вам надо будет рассмотреть все возможные расположения графических диаграмм, изображающих события или множества. Это очень громоздко, так как вариантов может быть очень много. Но графические диаграммы дают однозначный ответ в том случае, когда равенство не справедливо. Действительно, если удалось найти хотя бы один пример (контрпример), когда равенство не верное, значит оно точно не выполняется. Но диаграммы Венна могут помочь найти аналитическое решение, после того как построено графическое.

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

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

Логика (греч. λογικη от λόγος — слово, рассуждение) — наука о правильном мышлении, которая регламентирует формы и методы интеллектуальной познавательной деятельности, формализуемой с помощью языка.

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

Рисунок 1. Сократ

СОКРАТ из Афин (469-399 до н.э.) — знаменитый античный философ, учитель Платона, воплощенный идеал истинного мудреца в исторической памяти человечества. Учение Сократа было устным; все свободное время он проводил в беседах с приезжими и местными гражданами, политиками и обывателями, друзьями и незнакомыми на различные темы, например, что есть добро и что — зло, что прекрасно, а что безобразно, что добродетель и что порок, как приобретается знание и т.д.

Математическая логика — логика умозаключений, использующая математические методы.

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


Рисунок 2. Г.В. Лейбниц

Готфрид Вильгельм Лейбниц (1646-1716) — немецкий философ, математик и физик. Родился в семье профессора философии морали (этики) Лейпцигского университета Фридриха Лейбница и Катерины Шмюк. Когда мальчику было 8 лет, его отец умер, оставив после себя большую личную библиотеку. Свободный доступ к книгам и врождённый талант, позволили молодому Лейбницу уже к 12 годам самостоятельно освоить латынь и взяться за изучение греческого языка. В 15-летнем возрасте Готфрид сам поступил в тот же Лейпцигский университет, где когда-то работал его отец. Будучи студентом он познакомился с работами Кеплера, Галилея и других учёных.

В 1666 году Лейбниц защитил диссертацию по праву. Однако, отказавшись от предложенной должности профессора Нюрнбергского университета, предпочёл ей карьеру дипломата. В 1672-1676 годах был дипломатическим представителем в Париже. С 1676 года поселился в Ганновере. Являлся действительным членом английского Королевского общества и первым президентом Берлинской Академии. Совмещал также должность библиотекаря библиотеки Герцога Августа в Нижней Саксонии — крупнейшей библиотеки Европы в XVII веке. В 1697 году, когда Пётр I путешествовал по Голландии с целью освоения морского дела, он познакомился с Лейбницем. Это знакомство оказало сильное влияние на молодого царя и привело в дальнейшем к созданию Академии наук в Петербурге и началу развития научных исследований в России. Лейбниц стал первым гражданским лицом Германии, которому был воздвигнут памятник.

Рисунок 3. Джордж Буль

Джордж Буль (1815-1864) — английский математик. Родился в семье рабочего. Первые уроки математики получил у отца. В 12 лет знал латынь, затем овладел греческим, французским, немецким и итальянским языками. В 16 лет уже преподавал в деревенской школе, а в 20 открыл собственную школу в Линкольне. В редкие часы досуга зачитывался математическими журналами Механического института, интересовался работами Ньютона, Лапласа, Лагранжа.

Начиная с 1839 года, Буль стал посылать свои работы в новый Кембриджский математический журнал. В своем исследовании 1844 года, опубликованном в «Философских трудах Королевского общества», он коснулся проблемы взаимодействия алгебры и исчисления. В том же году молодой ученый был награжден медалью Королевского общества за вклад в математический анализ. Вскоре, после того как Буль убедился, что его алгебра вполне применима к логике, в 1847 году он опубликовал памфлет «Математический анализ логики», в котором высказал идею, что логика более близка к математике, чем к философии. Эта работа была высоко оценена английским математиком Огастесом (Августустом) Де Морганом. Благодаря этой работе Буль в 1849 году получил пост профессора математики Куинз-колледжа в графстве Корк, несмотря на то, что он даже не имел университетского образования. В 1854 году опубликовал работу «Исследование законов мышления, базирующихся на математической логике и теории вероятностей». Работы 1847 и 1854 годов положили начало алгебре логики. В своей работе «Законы мышления» (1854 г.) Буль окончательно сформулировал основы математической логики. Он также попытался сформулировать общий метод вероятностей, с помощью которого из заданной системы вероятных событий можно было бы определить вероятность последующего события, логически связанного с ними. В 1857 году Буль был избран членом Лондонского Королевского общества. Его работы «Трактат о дифференциальных уравнениях» (1859 г.) и «Трактат о вычислении предельных разностей» (1860 г.) оказали колоссальное влияние на развитие математики. В них нашли свое отражение наиболее важные открытия Буля. Сегодня идеи Буля используются во всех современных цифровых устройствах.

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

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

gaz.

wiki — gaz.wiki

Navigation

  • Main page

Languages

  • Deutsch
  • Français
  • Nederlands
  • Русский
  • Italiano
  • Español
  • Polski
  • Português
  • Norsk
  • Suomen kieli
  • Magyar
  • Čeština
  • Türkçe
  • Dansk
  • Română
  • Svenska

Учебник по логической алгебре

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

Это действительно логично.

Введение

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

Наброски

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

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

  1. Основы логической алгебры — Что такое булева алгебра и обзор основных операторов.
  2. Законы булевой алгебры — Основной набор приложений и значений операторов.
  3. Выражения логической алгебры — Использование правил для управления и упрощения выражений логической алгебры.

Так зачем мне изучать булеву алгебру?

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

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

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

Изучение логической алгебры

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

  • Перебери вещей несколько раз с хорошим перерывом между ними. Вы будете удивлены, как что-то может иметь мало смысла в первый раз, когда вы прочитаете это, но если вы оставите это на некоторое время, чтобы дать этому поваляться в вашей голове, а затем вернетесь к этому, это станет более осмысленным при втором чтении.
  • Нарисуйте на бумаге. Я сталкиваюсь с множеством ленивых студентов, которые говорят: «Нет, все в порядке, я просто проработаю это в своей голове». Для абстрактных вещей, таких как логическая алгебра, это не сработает, если вы достигнете определенного уровня сложности. Немного времени и усилий, чтобы нарисовать это на бумаге, избавят вас от многих часов разочарования. Это также упростит повторение ваших шагов, когда что-то пойдет не так.
  • Говорите вслух , а не просто мысленно.Это может показаться глупым, но когда вы говорите это, а не просто думаете, вы увидите это с другой точки зрения, и это может помочь лучше понять, что происходит.
  • Практика !! Чем больше вы практикуетесь, тем больше ваш ум будет складывать кусочки головоломки по этим абстрактным концепциям. Чем больше вещей начнут обретать смысл.

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

Булева алгебра — обзор

IE Булева матрицы и графы

Булева алгебра B имеет элементы {0, 1} и операции +, ·, c , задаваемые 0 + 0 = 0, 0 + 1 = 1 + 0 = 1 + 1 = 1, 0 · 0 = 1 · 0 = 0 · 1 = 0, 1 · 1 = 1, 0 c = 1, 1 c = 0. Существует множество интерпретаций и вариантов использования логического выражения. алгебра B: (1) логика высказываний, где 0 — ложь, 1 — истина, + — «или», · — «и» c — «нет», (2) схемы переключения, где 0 означает, что ток не течет, 1 означает текущие потоки; и (3) B × B × ⋯ × B можно принять как набор подмножеств набора элементов n { y i }, где ( x 1 , x 2 ,…, x n ) соответствует подмножеству { y i : x i = 1}; (4) 0 означает ноль в R , 1 ​​означает некоторое положительное число в R , где R обозначает набор всех действительных чисел.Алгебра B удовлетворяет тем же законам, что и алгебра множеств под ∪,, ~, где ~ обозначает дополнение, поскольку это булева алгебра.

Логическая матрица n × m A = ( a ij ) представляет собой прямоугольник n × m элементов B. Запись в строке (горизонтальная) i и столбец (вертикальный) j обозначается a ij . Для каждого бинарного отношения R из набора X = { x 1 , x 2 ,…, x n }, чтобы установить Y = { y 1 , y 2 ,…, y m } мы можем назначить логическую матрицу M = ( m ij ), где m ij равно 0 или 1 в соответствии с лежит ли ( x i , y j ) в R .Это дает 1–1 для соответствия булевых матриц от X до Y до n × m . Многие вопросы можно решить просто в форме булевой матрицы. Булевы матрицы умножаются и складываются по тем же формулам, что и для обычных матриц, за исключением того, что операции являются логическими. Состав (объединение) бинарных отношений соответствует произведению (сумме) булевых матриц.

Ориентированный граф (сокращенно орграф) состоит из набора V элементов, называемых вершинами (представленных точками), и набора E или упорядоченных пар V , называемых ребрами.Каждая упорядоченная пара ( x, y ) представлена ​​сегментом со стрелкой, идущей от точки x к точке y . Таким образом, орграфы по сути такие же, как бинарные отношения от множества к самому себе. Любая логическая матрица n × n ( n -квадрат) или двоичное отношение на помеченном множестве может быть представлена ​​как орграф, и наоборот. На рисунке 3 показаны логическая матрица и граф бинарного отношения на {1, 2, 3, 4}.

РИСУНОК 3. Матрица и график отношения.

Булева алгебра | Encyclopedia.com

Свойства множеств

Свойства булевой алгебры

Приложения

Ресурсы

Булеву алгебру часто называют алгеброй логики. Английский математик Джордж Буль (1815–1864), который в значительной степени ответственен за ее начало, был первым, кто применил алгебраические методы к логической методологии. Он показал, что логические предложения и их связки могут быть выражены на языке теории множеств.Таким образом, булева алгебра также является алгеброй множеств. Алгебра — это раздел математики, который занимается отношениями величин.

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

Набор — это набор объектов, называемых членами или элементами. Члены набора могут быть физическими объектами, такими как люди, звезды или розы, или они могут быть абстракциями, такими как числа или даже другими наборами. Набор называется универсальным набором (обычно называется I), если он содержит все рассматриваемые элементы.Множество S, не равное I, называется собственным подмножеством I, если каждый элемент S содержится в I. Это записывается и читается как «S содержится в I.» (см. рисунок 1)

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

При работе с наборами необходимо выполнить три важных операции.Две из этих операций являются двоичными (то есть они включают объединение наборов по два за раз), а третья включает только один набор за раз. Две бинарные операции — это объединение и пересечение. Третья операция — дополнение. Объединение двух множеств S и T — это совокупность тех членов, которые принадлежат либо S, либо T, либо обоим. (см. рисунок 2)

Пересечение множеств S и T — это совокупность тех элементов, которые принадлежат как S, так и T. (см. рисунок 3)

Дополнение к подмножеству S — это та часть I, которая не содержится в S и пишется S .(см. рисунок 4)

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

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

S∩T = T∩S и S∪T = T∪S.

(2) Каждая двоичная операция имеет связанный с ней элемент идентификации. Универсальный набор — это тождественный элемент для операции пересечения, а нулевой набор — это тождественный элемент для операции объединения.

S∩I = S и S ∪Ø = S.

(3) каждая операция является распределительной по отношению к другой.

S ∪ (T∩ V) = (S ∪ T) ∩ (S ∪ V) и S ∩ (T∪V) = (S ∩ T) U (S V).

Это отличается от алгебры действительных чисел, для которой умножение дистрибутивно над сложением, a (b + c) = ab + ac, но сложение не является дистрибутивным над умножением, a + (bc) не равно (a + b) (а + с).

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

A ∪ ′ = I и A ∩ ′ = Ø.

Это также отличается от алгебры действительных чисел. Каждое действительное число имеет два других связанных с ним, так что его сумма с одним из них является тождественным элементом для сложения, а его произведение с другим является тождественным элементом для умножения. То есть a + (-a) = 0 и a (1 / a) = 1.

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

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

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

См. Также Компьютер, цифровой.

КЛЮЧЕВЫЕ УСЛОВИЯ

Двоичная операция — Двоичная операция — это метод объединения элементов набора, по два за раз, таким образом, что их комбинация также является членом набора.

Дополнение — Дополнение набора S, записанное как S , — это набор, содержащий те элементы универсального набора, которые не содержатся в S.

Элемент — Любой элемент набора. Объект в комплекте.

Пересечение — Пересечение двух наборов само по себе является набором, состоящим из всех элементов, общих для обоих наборов.

Набор— Набор — это набор вещей, называемых членами или элементами набора. В математике членами множества часто являются числа.

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

Подмножество — Набор S называется подмножеством другого набора I, если каждый член S содержится в I.

Объединение — Объединение двух наборов — это набор, содержащий все элементы. можно найти в одном или другом из двух наборов.

Универсальный набор — Универсальный набор — это набор, содержащий все рассматриваемые элементы.

КНИГИ

Марковиц, Алан Б. Введение в логический дизайн. Нью-Йорк: Макгроу-Хилл, 2006.

Дж. Р. Мэддокс

Булева алгебра — Практика EE

Булева алгебра — это раздел математики, который устанавливает систему символов для логических функций, позволяющих писать логические уравнения, и устанавливает правила, управляющие операциями с логическими переменными, которые могут иметь только два возможных значения: истина (1) или ложь ( 0). Булеву алгебру ввел Джордж Буль, английский математик 1815-1864 гг.

Джордж Буль (1815-1864)

В современной булевой алгебре мы используем символ плюса (+) для обозначения ИЛИ, символ точки (•) для обозначения И и черту над переменной для обозначения НЕ. Обратите внимание, что иногда я буду использовать! вместо bar означает НЕ, поскольку это намного проще сделать в HTML, и этот символ (восклицательный знак или удар) широко используется для обозначения НЕ в языках программирования. Логические переменные, которые могут иметь значение только 1 или 0, обычно представляют собой заглавные буквы, такие как A, B, C и т. Д.

Приоритет оператора: НЕ> И> ИЛИ

Приоритет логического оператора НЕ> И> ИЛИ. Таким образом, выражение A +! B • C будет оцениваться следующим образом: инвертировать B, И это с помощью C, а затем ИЛИ, что результат с A.Вы можете заключить выражение в круглые скобки, чтобы переопределить приоритет оператора по умолчанию. (например, (A + B) • C означает сначала выполнить A OR B, затем AND с C.) Обратите внимание, что этот порядок приоритета аналогичен математике с вещественными числовыми переменными, где AND похоже на умножение, OR похоже на сложение, а NOT похоже на оператор унарного знака (например, -8).

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

Законы булевой алгебры

Закон Описание
A + 1 = 1 ИЛИ 1 равно 1. 1 всегда ИСТИНА, поэтому не имеет значения, с чем вы ИЛИ, результат всегда будет ПРАВДА.
A + 0 = A A OR 0 равно A. 0 всегда FALSE, поэтому он не влияет на функцию OR, результат следует за переменной A.
A • 1 = A А И 1 — это А.1 всегда ИСТИНА, поэтому он не влияет на функцию И, результат следует за переменной A.
A • 0 = 0 И 0 равно 0. 0 всегда ЛОЖЬ, поэтому не имеет значения, что Вы И это с, результат всегда ЛОЖЬ.
A + A = A A OR A равно A. A равно 0 или 1. Если A равно 0, то 0 OR 0 равно 0, а если 1, то 1 OR 1 равно 1.
A • A = A A AND A равно A. A равно 0 или 1. Если A равно 0, то 0 AND 0 равно 0, а если 1, то 1 AND 1 равно 1.
НЕ А = А НЕ НЕ А это А. Обратное обратное — это… ммм… стих? Обратная функция отрицает другую обратную функцию.
A + A = 1 A OR NOT A равно 1. Либо A равно 1, либо NOT A равно 1, поэтому результат OR всегда равен 1.
A • A = 0 A AND NOT A равно 0. A и NOT A никогда не могут быть 1, поэтому результат AND всегда равен 0.
A + B = B + A A OR B то же самое, что B OR A.Коммутативное свойство работает для функции ИЛИ.
A • B = B • A A AND B совпадает с B AND A. Свойство коммутативности работает для функции AND.
A • (B + C) = A • B + A • C A И количество B OR C равно A AND B OR A AND C. Это свойство распределения для OR. Обратите внимание на наличие и отсутствие круглых скобок и приоритет оператора AND над OR.
A + (B • C) = (A + B) • (A + C) A ИЛИ количество B AND C — это количество A OR B И количество A OR C.Это свойство распределения для AND. Обратите внимание на наличие и отсутствие круглых скобок и приоритет оператора AND над OR.
A + B = A • B НЕ из результата (A ИЛИ B) равно НЕ A И НЕ B. Это теорема Де Моргана.
A • B = A + B НЕ из результата (A AND B) равно НЕ A OR NOT B. Это также теорема Де Моргана.

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

Теорема Де Моргана названа в честь Августа Де Моргана, который был британским математиком с 1806 по 1871 год. Вот фотография, на которой он делал Наполеона.

Огастес де Морган (1806-1871)

Далее: Комбинаторная логика

Компьютеры с булевой алгеброй

Джордж Буль Wikimedia Commons Есть две основные причины, по которым математика очаровывает человечество на протяжении двух тысяч лет.Во-первых, математика дает нам инструменты, необходимые для понимания вселенной и построения вещей. Во-вторых, изучение самих математических объектов может быть красивым и интригующим, даже если у них нет очевидного практического применения.

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

«И», «Или», «Не»

Булева алгебра — это комбинация логики и алгебры, первоначально разработанная Джорджем Булем, в честь которого назван предмет, в 1840-х и 1950-х годах, а затем усовершенствованная другими логиками. через остаток девятнадцатого и начала двадцатого веков.

Формальная логика касается истинности или ложности утверждений или предложений. «Барак Обама — президент Соединенных Штатов» — верное утверждение. Утверждение «Google производит iPhone» неверно.

Все становится интереснее, когда мы начинаем комбинировать простые предложения. «Барак Обама — президент Соединенных Штатов, а Джо Байден — вице-президент» верно, поскольку оба простых утверждения, соединенных «и» в середине, верны. «Либо в Техасе проживает 300 человек, либо телевидение было изобретено Иссаком Ньютоном» — ложно, поскольку оба простых утверждения, соединенных «или» в середине, ложны.

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

Например, если предложение X истинно, а предложение Y истинно, то составное предложение «X и Y» также истинно. Если либо X, либо Y ложны, или оба ложны, то «X и Y» также ложны.

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

В логической алгебре Буля переменные, представляющие логические предложения, объединяются в формулы и уравнения с помощью логических операций и, или, и not. Утверждение «X и Y истинно» преобразуется в уравнение X × Y = 1. Утверждение «X или Y ложно» становится X + Y = 0.

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

Сто лет спустя

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

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

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

Одно из первых крупных приложений булевой алгебры появилось в 1937 году в магистерской диссертации Клода Шеннона, одного из самых важных математиков и инженеров 20-го века. Шеннон понял, что переключатели в релейных сетях, таких как телефонная сеть или ранний протокомпьютер, можно легко описать, рассматривая «включенные» переключатели, имеющие логическое значение «истина», «выключенные» переключатели как имеющие логическое значение. со значением «false» и с различными шаблонами, в которых переключатели связаны друг с другом, соответствующими логическим операциям «and», «or» и «not».

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

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

Элемент «and», например, принимает два входа. Если оба входа имеют высокое напряжение (представляющее «истину»), затвор «и» также имеет высокое напряжение на выходе, равное «истине», в то время как если один или оба входа имеют низкое напряжение или ложь, затвор будет иметь низкое напряжение. вывод false.

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

Далее, эта булева алгебра, встроенная в компьютеры, возвращается к обычной математике. Булевская дихотомия истина и ложь прекрасно подходит для представления двоичных чисел: истина соответствует 1, а ложь — 0. В соответствии с этой интерпретацией можно собрать логические схемы, которые просто путем правильного объединения двух двоичных входных чисел с использованием and, or, а не операции, могут складывать, вычитать, умножать или делить числа.

Иногда достижения чистой математики спустя десятилетия или столетия могут найти удивительное применение.

Логическая алгебра

  • Изучив этот раздел, вы должны уметь:
  • Описывать логические схемы с помощью булевых уравнений.
  • • Создайте логические выражения для промежуточных выходов вентилей.
  • • Используйте сложные логические уравнения для описания полных логических схем.
  • Упростите булевы уравнения, используя булевы законы.
  • • Коммутативный.
  • • Ассоциативный.
  • • Распределительный.
  • • Идентичность.
  • • Дополнение.
  • • Двойственность.
  • • Теорема Де Моргана.
  • Используйте теорему Де Моргана, чтобы преобразовать схемы с несколькими вентилями в универсальные вентили.

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

Модуль

Digital Electronics Module 2.1 показал, что работу одного логического элемента можно описать с помощью логического выражения. Например, работа одного логического элемента И со входами A и B и выходом X может быть выражена как:

X = A • B

Примечание:

Символ • представляет собой логическое И, но поскольку использование специальных символов может быть неудобным в печатных материалах, символ И часто опускается, как в AB, или отделяется точкой, как в A. B используется для обозначения умножения в стандартной алгебре. Символы умножения x и * также можно увидеть в некоторых текстах, потому что логическое И похоже на двоичное умножение (но не то же самое, когда используются числа, имеющие более одного бита). Модуль 2.2 показал взаимосвязь между таблицей истинности, описывающей работу схемы, и булевым уравнением, описывающим логику схемы.

Комбинационная логическая схема, такая как показанная на рисунке 2.3.1 (повторение рисунка 2.2.2) описывается логическим уравнением как:

X = (A • B) + (A • C) + (A • B • C)

Рис. 2.3.1 Трехвходовая схема с резервными вентилями

Это также можно было бы записать (менее четко) как «Выход X будет 1, когда A и B или A и C или A и B и C равны 1, в противном случае X будет 0».

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

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

Упрощение схем с использованием булевой алгебры

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

Логические законы

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

Коммутативные законы

В группе переменных, соединенных операторами И или ИЛИ, порядок переменных не имеет значения.

1а. Логическое сложение (ИЛИ): A + B = B + A

1б. Логическое умножение (И): A • B = B • A

Ассоциативные законы

Порядок расчета можно изменить, не влияя на результат (измените, какие термины указаны в скобках, или удалите скобки). Примечание: это нормально, только если все знаки (+ или •) одинаковы.

2а.Логическое сложение (ИЛИ): (A + B) + C = A + (B + C) = A + B + C

2б. Логическое умножение (И): (A • B) • C = A • (B • C) = A • B • C = ABC

Распределительные законы

Тот же ответ достигается при умножении (И) переменной на группу переменных в квадратных скобках, сложенных (ИЛИ) вместе, как и при каждом умножении (И) отдельно.

Закон 3a аналогичен факторизации в нормальной алгебре, но закон 3b уникален для булевой алгебры, потому что в отличие от нормальной алгебры, где A x A = A 2 , в булевой алгебре A • A = A

3а. A • (B + C) = A • B + A • C

3б. A + (B • C) = (A + B) • (A + C)

Элементы идентификации

В правиле 4a, когда к переменной A добавляется логическая 1 (называемая элементом идентичности для оператора AND). Переменная, помеченная AND с 1, сохраняет свою идентичность.

Правило 4b показывает, что Identity Element для оператора OR равен 0, и любая переменная (например, A), объединенная с помощью OR с 0, сохраняет свою идентичность.

4а. A • 1 = A

4б. А + 0 = А

5a и 5b показывают, как «принуждение элемента идентичности» (в столбце B таблиц истинности) к состояниям, противоположным тем, которые используются в 4a и 4b, дает результат, который является таким же, как и элемент идентичности.

5а. A • 0 = 0

5б. А + 1 = 1

6a и 6b показывают, что операция И или ИЛИ двух идентичных переменных дает результат, равный одной переменной, показывая, что одна из переменных является избыточной, что является полезным правилом при упрощении булевых уравнений.

6а. A • A = A

6б. А + А = А

Закон о дополнении

7а. A + A = 1 Любая переменная, объединенная с помощью ИЛИ с обратным ей, равна 1

7б. A • A = 0 Любая переменная, связанная операцией AND и обратным ей, равна 0

Редукция

8а.Когда одна переменная (A) соединяется с самой собой ИЛИ со второй переменной (A + B), результат равен одной переменной.

8a A • (A + B) = A

8б. Когда одна переменная (A) соединяется с ней ИЛИ второй переменной (A • B), результат равен одной переменной.

8b A + (A • B) = A

8с. Когда одна переменная (A) объединяется с самой собой ИЛИ со второй переменной (A + B), эта единственная переменная исчезает.

8c А + (А + В) = (А + В)

8д. Когда одна переменная (A) соединяется с самой собой И второй переменной (A • B), эта единственная переменная исчезает.

8d A • (A • B) = (A • B)

Правила двойственности

Можно получить дополнительные идентификаторы путем получения двойного идентификатора. Это включает в себя замену операторов AND на OR и операторов OR на AND. Кроме того, любые 0 изменяются на 1 и 1 на 0, как показано в Таблице 2.3.2.

Правило двойственности может использоваться для изменения логического выражения, содержащего элементы И и ИЛИ, на эквивалентное двойное выражение.

Таблица 2.3.3 показывает, что A • (B + C) совпадает с A + (B • C).

Упрощение булевых уравнений

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

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

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

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

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

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

Примеры логического упрощения

Пример 1

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

Только менеджер магазина (M) может войти один. Помощник менеджера (A) и кассир (C) также имеют доступ, но только в сопровождении друг друга или менеджера магазина. Разработайте комбинационную логическую схему, которая обеспечит доступ путем создания логической 1 при выполнении вышеуказанных условий.

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

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

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

X = M + M • C + A • C + A • M + A • C • M

Рис. 2.3.2 Схема доступа в кассу

Это предполагает схему, подобную показанной на рис. 2.3.2, для которой потребуются четыре ИС:

1x 74HCT08 2 входа И (с 4 воротами).

1x 74HCT10 3 входа И (с 3 воротами).

1x 74HCT32 2 входа ИЛИ (с 4 воротами).

1x 74HCT4075 3 входа ИЛИ (с 3 воротами).

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

Исходя из уравнения, полученного из таблицы 2.3.4:

Рис. 2.3.3 Упрощенная схема доступа в кассу

X = M + M • C + A • C + A • M + A • C • M

Так как M + M • C = M (правило редукции 8b)

X = M + A • C + A • M + A • C • M

А так как M + A • C + A • M = M + A • M + A • C (Закон коммутации 1a)

X = M + A • M + A • C + A • C • M

А как M + A • M = M (правило редукции 8b)

X = M + A • C + A • C • M

И как M + A • C + A • C • M = M + A • C • M + A • C (Закон о коммутаторе 1a)

X = M + A • C • M + A • C

А как M + A • C • M = M (правило редукции 8b)

X = M + A • C

Дальнейшее сокращение невозможно.

Упрощенная схема показана на рис. 2.3.3, который выполняет те же функции, что и рис. 2.3.2. Это можно подтвердить, сравнив упрощенное уравнение X = M + A • C с исходным столбцом X в таблице 2.3.5.

Упрощенная схема на рис. 2.3.3 по-прежнему требует двух ИС (И и ИЛИ), и теперь в ней используется только один вентиль на микросхему. Если только запасные ворота не будут использоваться где-то еще в другой части цепи, это все равно будет расточительно.

Рис.2.3.4 Цепь доступа в кассу только NAND

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

Операция

NAND 1 имеет оба своих входа, соединенных вместе, что преобразует их в инвертор или НЕ-вентиль и, следовательно, производит Mat на своем выходе. NAND 2 работает как логический элемент И с инвертированным выходом и, таким образом, выдает выходной сигнал A • C. Логическое выражение для схемы, использующей вентили NAND, теперь принимает вид:

X = M + A • C

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

Пунктирная полоса A • B указывает на то, что входы (например, для логического элемента И) инвертированы, в то время как непрерывная полоса A • B указывает на инвертированный выход.

Теорема Де Моргана

Рис. 2.3.5 Закон Де Моргана 1

Рис. 2.3.6 Закон Де Моргана 2

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

Закон 1.

A + B = A • B Инвертирование входов логического элемента ИЛИ изменяет его функцию на И-НЕ.

Закон 2.

A • B = A + B Инвертирование входов в логический элемент И изменяет его функцию на NOR

Рассматривая эти два равенства с другой стороны, A + B = A • B Теорема Де Моргана часто описывается как «сломайте планку и измените знак.»Это означает, что при размещении или удалении полосы над оператором И или ИЛИ (• или +) оператор инвертируется. Следовательно, дополнением к функции И является ИЛИ.

Применение теоремы Де Моргана

Эти равенства, обычно называемые законами 1 и 2 Де Моргана, проиллюстрированы на рис. 2.3.5 и рис. 2.3.6 применительно к логическим элементам AND, NOR, NAND и OR. Однако обратите внимание, что когда теорема Де Моргана применяется к вентильным элементам XOR и XNOR, функция элемента не изменяется.

Полезность теоремы Де Моргана в применении к схемам можно увидеть, сравнив рис.2.3.3 и рис. 2.3.4, где он сыграл важную роль в изменении функций логических элементов И и ИЛИ на рис. 2.3.3 на все логические элементы И-НЕ на рис. 2.3.4, так что схема может быть построена с использованием одной ИС. из двух.

Инвертирование входов

На рис. 2.3.4 в схеме появляется дополнительный вентиль И-НЕ 1, два входа которого соединены вместе, чтобы действовать как вентиль НЕ (проверьте это, посмотрев на таблицу истинности для логического элемента И-НЕ на рисунке 2.3.5). , когда оба входа одинаковы (строка 1 и строка 4), выход (X) является инвертированной версией входов (A • B).

Этот дополнительный вентиль на рис. 2.3.4 обеспечивает М на верхнем входе в И-НЕ 3 вместо М, применяемого к верхнему входу логического элемента ИЛИ на рис. 2.3.3.

NAND 2 на рис. 2.3.4 заменяет логический элемент AND на рис. 2.3.3, так что нижний вход в NAND 3 теперь A • C вместо A • C.

Следовательно, входы в NAND 3 теперь M и M • C. Следовательно, оба входа в И-НЕ 3 были инвертированы (без фактического использования каких-либо вентилей НЕ), чтобы заставить И-НЕ 3 действовать, согласно теореме Де Моргана, как функция ИЛИ, что дает правильный выход X = M + A • C.

Сводка

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

Булева алгебра — Викиверситет

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

Булева алгебра описывает логические операции и операции над наборами. Логической операцией может быть, например: «У меня есть мука и вода, я могу сделать тесто». В случае, когда у меня есть мука и вода, это утверждение верно. Если один из элементов неверен, то он явно неверен.
Другой вариант: «У меня есть яйца или бекон, у меня есть еда». В случае, если у меня были яйца, но не бекон, или если бы у меня был только бекон, или если бы у меня были яйца и бекон, утверждение, что у меня есть еда, было бы правдой.Только если бы у меня не было яиц или бекона, «у меня есть еда» было бы ложным.

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

Теперь, взяв первый пример, давайте заменим муку соответствующей буквой: F, воду на W и тесто на D. Чтобы записать это, нам понадобится символ «и». Символ «и» в логической алгебре — ∧ {\ displaystyle \ land}.
Таким образом, объединив все вышесказанное, можно описать «У меня есть мука и вода, я могу сделать тесто»: F∧W = D {\ displaystyle F \ land W = D}

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

  • ∧ {\ displaystyle \ land} Означает логическое И.
  • ∨ {\ displaystyle \ lor} означает логическое ИЛИ.
  • ¬ {\ displaystyle \ lnot} Означает логическое НЕ.
  • → {\ displaystyle \ rightarrow} Означает логическое следствие.

Чтобы добавить немного путаницы, инженеры часто используют + для ИЛИ и знак умножения, x или * для И. Некоторые используют черту над символом или выражением для обозначения НЕ, тогда как другие используют символ! после термина или символ ~ перед термином, чтобы обозначить НЕ.Примеры:

  • q = a * b означает, что если AND b истинно, q истинно
  • q = a + b означает, что если ИЛИ b истинно, q истинно
  • д = а! означает, что если a истинно, q ложно. Если a ложно, q истинно (т. Е. Q противоположно a)


Операции, одна за другой:

  • ∧ {\ displaystyle \ land} означает И. Мне нравится запоминать это по сходству с буквой «н».
И описывает ситуацию, когда утверждение истинно тогда и только тогда, когда части слева от него и его справа истинны.
  • ∨ {\ displaystyle \ lor} означает ИЛИ.
ИЛИ описывает ситуацию, когда утверждение истинно, если по крайней мере одна из частей слева от него или его правая истинны. (Обратите внимание, что если и a, и b истинны, a + b по-прежнему истинно)
  • ¬ {\ displaystyle \ lnot} означает НЕ.
НЕ инвертирует следующий за ним символ или выражение в квадратных скобках.Итак, если A истинно, а я говорю B = ¬ {\ displaystyle \ lnot} A, тогда B ложно.
  • → {\ displaystyle \ rightarrow} означает импликацию.
Вывод означает, что если часть слева истинна, то часть справа истинна. Однако он не говорит ничего значимого, если часть слева ложна, например, «Если яблоки и апельсины существуют, значит, что-то существует», безусловно, верно, поскольку яблоки и апельсины существуют, и что-то существует, но «Если яблоки существуют, но нет апельсинов, тогда что-то существует »также верно, хотя апельсины действительно существуют, что делает« яблоки существующими, но апельсины не «ложными».

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

∧ {\ displaystyle \ land} AND
Проверка уравнения: A∧B = X {\ displaystyle A \ land B = X} Где каждая строка имеет различную комбинацию A и B, а результирующее значение X

А B Х
Истинно Истинно Верно
Истинно Ложь Ложь
Ложь Истинно Ложь
Ложь Ложь Ложь

∨ {\ displaystyle \ lor} OR
Проверка уравнения: A∨B = X {\ displaystyle A \ lor B = X} Где каждая строка имеет различную комбинацию A и B, а результирующее значение X

А B Х
Истинно Истинно Верно
Истинно Ложь Верно
Ложь Истинно Верно
Ложь Ложь Ложь

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

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

Объединение операций [править | править источник]

Итак, два элемента, способствующих достижению одного результата, — это хорошо, но что, если я возьму бекон, яйца и сыр?
Элементы можно просто объединить в цепочку, добавив больше операций. Таким образом, приведенное выше будет:
Bacon∧Eggs∧Cheese {\ displaystyle Bacon \ land Eggs \ land Cheese}
Но что делать, если у вас есть и операции OR, и AND? Чтобы ясно и недвусмысленно передать наше уравнение, мы должны использовать круглые скобки (скобки).Выражения в квадратных скобках сначала решаются из самых внутренних скобок. Например:
Если бы я считал едой только бекон И яйца, но сыр также является едой, я бы написал:
У меня есть ((Bacon∧Eggs) ∨Cheese) = Я поел {\ displaystyle {\ text {I have}} ((Bacon \ land Eggs) \ lor Cheese) = {\ text {Я уже пообедал}}}
Если бы я считал только бекон И яйца, или бекон И сыр едой, но только любой предмет, или яйцо и сыр, чтобы быть неправильной едой, я бы написал:
У меня есть (Bacon∧ (Eggs∨Cheese)) = Я поел {\ displaystyle {\ text {I have}} (Bacon \ land (Eggs \ lor Cheese )) = {\ text {Я поел}}}

Как и в обычной алгебре, где умножение имеет приоритет перед сложением, И имеет приоритет (или приоритет) перед ИЛИ.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *