Операции булевой алгебры – Булева алгебра — Национальная библиотека им. Н. Э. Баумана

Булева алгебра — Национальная библиотека им. Н. Э. Баумана

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:20, 13 ноября 2016.

Определение

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

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

1. Непустое множество А.
2. Бинарные операции Конъюнкция(ʌ) и Дизъюнкция ( v)
3. Унарная операция отрицания (¬ или не)
4. Логические константы Истина (1) и Ложь (0)

Происхождение

Булева алгебра названа по имени великого английского математика Джорджа Буля (1815—1864), который в 1854 г. опубликовал ставшую впоследствии знаменитой книгу «Исследование законов мышления». В начале гл. 1 он написал:

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

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

Другие математики и логики, в том числе Джон Венн и Эрнст Шрёдер, впоследствии значительно усовершенствовали и расширили алгебру Буля.

В 1938 г. Клод Э. Шеннон, в то время студент Массачусетсского технологического института, впоследствии известный математик и инженер Белловских телефонных лабораторий, а в настоящее время профессор Массачусетского технологического института, показал, что булеву алгебру можно прекрасно применять при синтезе переключательных электрических схем. Его статья «Символический анализ релейно-переключательных схем» представляет собой веху в развитии применений булевой алгебры.

Аксиомы

1) Булева переменная всегда равна либо нулю, либо единице

 х=0, если х≠1
 х=1, если х≠0 

2) Инверсное значение переменной x противоположно ее прямому значению

х=0, если ¬х=1
х=1, если ¬х=0

3) Правила выполнения логического умножения (конъюнкции)

0 ʌ 0=0
1 ʌ 1=1
0 ʌ 1=1 ʌ 0=0

4) Правила выполнения логического сложения (дизъюнкции)

0 v 0 = 0
1 v 1= 1
0 v 1 = 1 v  0 = 1

Законы

1) Ассоциативный (сочетательный) закон

Ассоциативность конъюнкции и дизъюнкции выражается следующими формулами:

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

2) Коммутативный (переместительный) закон<

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

3) Дистибутивный (распределительный) закон

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

4) Законы де Моргана (законы общей инверсии или дуальности)

Законы де Моргана позволяют применять отрицания к целой скобке, позволяя перейти к так называемым тесным отрицаниям, когда ни одно отрицание не стоит перед скобкой.

5) Закон поглощения (элиминации)

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

6) Закон склеивания (исключения)

7) Свойства единицы и нуля

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

A ʌ 0 = 0

A ʌ 1 = A

A v 0 = A

A v 1 = 1

8) Идемпотентность

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

A ʌ A = A

A v A = A

9) Дополнение

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

А ʌ ¬А = 0

А v ¬А = 1

10) Двойное отрицание

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

¬¬А=А

Правила

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

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

инверсия (отрицание ¬),

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

дизъюнкция (v),

импликация (→), эквиваленция (=).

Обозначение на логических схемах

Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах.

Обозначение на схеме

Ссылки

1. Function-x [Электронный ресурс]: Булева алгебра (алгебра логики) / Дата обращения: 26.06.16. — Режим доступа: http://function-x.ru/buleva_algebra.html
2. МГИУ Кафедра информационных систем и технологий [Электронный ресурс]: Булева алгебра / Дата обращения: 26.06.16. — Режим доступа: http://230100.msiu.ru/files/6222-lesson4.html
3. Планета информатики учебник по информатике [Электронный ресурс]: Логические основы ЭВМ / Дата обращения: 26.06.16. — Режим доступа: http://www.inf1.info/book/export/html/210
4. Исория компьютера [Электронный ресурс]: Клод Шеннон / Дата обращения: 26.06.16. — Режим доступа: http://chernykh.net/content/view/444/656
5. Function-x [Электронный ресурс]: Логические схемы и таблицы истинности / Дата обращения: 26.06.16. — Режим доступа: http://function-x.ru/logicheskie_shemy_i_tablici_istinnosti.html
6. СтудопедиЯ [Электронный ресурс]: Аксиомы и законы алгебры логики / Дата обращения: 26.06.16. — Режим доступа: http://studopedia.su/7_11744_aksiomi-i-zakoni-algebri-logiki.html

ru.bmstu.wiki

Булева алгебра. Алгебра логики. Элементы математической логики

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

Логика

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

Порой количество условий (вводных) настолько велико, а взаимосвязи между ними столь запутанны и сложны, что человеческий мозг не в состоянии «переварить» все сразу. Может понадобиться не один месяц (неделя, год) для понимания происходящего. Но современная жизнь не дает нам таких временных интервалов на принятие решений. И мы прибегаем к помощи компьютеров. И вот тут-то и появляется алгебра логики, со своими законами и свойствами. Загрузив все исходные данные, мы позволяем компьютеру распознать все взаимосвязи, исключить противоречия и найти удовлетворительное решение.

Математика и логика

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

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

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

Джордж Буль

Сама личность автора заслуживает отдельного внимания. Даже учитывая то, что в прошлом люди взрослели раньше нас, все равно нельзя не отметить, что в 16 лет Дж. Буль преподавал в деревенской школе, а к 20 годам открыл собственную школу в Линкольне. Математик отлично владел пятью иностранными языками, а в свободное время зачитывался работами Ньютона и Лагранжа. И все это — о сыне простого рабочего!

В 1839 году Буль впервые послал свои научные работы в Кембриджский математический журнал. Ученому исполнилось 24 года. Работы Буля настолько заинтересовали членов Королевского научного общества, что в 1844 году он получил медаль за вклад в развитие математического анализа. Еще несколько опубликованных работ, в которых были описаны элементы математической логики, позволили молодому математику занять пост профессора в колледже графства Корк. Напомним, что у самого Буля образования не было.

Идея

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

Таким образом, алгебра логики может быть использована буквально везде: в составлении расписаний и написании инструкций, анализе противоречивой информации о событиях и определении последовательности действий. Самое главное — понять, что совершенно неважно, как мы определили истинность или ложность высказывания. От этих «как» и «почему» нужно абстрагироваться. Значение имеет только констатация факта: истина-ложь.

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

Основные понятия и определения

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

• высказываний;
• логических операций;
• функций и законов.

Высказывания – любые утвердительные выражения, которые не могут быть истолкованы двузначно. Они записываются в виде чисел (5 > 3) или формулируются привычными словами (слон – самое большое млекопитающее). При этом фраза «у жирафа нет шеи» также имеет право на существование, только булева алгебра определит её как «ложь».

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

Операции булевой алгебры

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

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

Основные логические действия

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

Отрицание (не) применяется только к одному элементу (операнду). Поэтому операцию отрицания называют унарной. Для записи понятия «не А» используют такие символы: ¬A, A¯¯¯ или !A. В табличной форме это выглядит так:

Для функции отрицания характерно такое утверждение: если А истинно, то Б – ложно. Например, Луна вращается вокруг Земли – истина; Земля вращается вокруг Луны – ложь.

Логические умножение и сложение

Логическое И называют операцией конъюнкции. Что это значит? Во-первых, что применить ее можно к двум операндам, т. е. И – бинарная операция. Во-вторых, что только в случае истинности обоих операндов (и А, и Б) истинно и само выражение. Пословица «Терпение и труд все перетрут» предполагает, что только оба фактора помогут человеку справиться со сложностями.

Для записи используются символы: A∧Б, A⋅Б или A&&Б.

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

Дизъюнкцией называют операцию логического ИЛИ. Она принимает значение истинности тогда, когда хотя бы одно из высказываний истинно (или А, или Б). Записывается это так: A∨Б, A+Б или A||Б. Таблицы истинности для этих операций такие:

Дизъюнкция подобна арифметическому сложению. Операция логического сложения имеет только одно ограничение: 1+1=1. Но мы же помним, что в цифровом формате математическая логика ограничена 0 и 1 (где 1 – истина, 0 — ложь). Например, утверждение «в музее можно увидеть шедевр или встретить интересного собеседника» означает, что можно посмотреть произведения искусства, а можно познакомиться с интересным человеком. В то же время, не исключен вариант одновременного свершения обоих событий.

Функции и законы

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

Ассоциативность означает, что в высказываниях типа «и А, и Б, и В» последовательность перечисления операндов не играет роли. Формулой это запишется так:

(A∧Б)∧В=A∧(Б∧В)=A∧Б∧В,

(A∨Б)∨В=A∨(Б∨В)=A∨Б∨В.

Как видим, это свойственно не только конъюнкции, но и дизъюнкции.

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

A∧Б=Б∧A; A∨Б=Б∨A.

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

A∧(Б∨В)=A∧Б∨A∧В; A∨Б∧В=(A∨Б)∧(A∨В).

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

A∧0=0,A∧1=A; A∨0=A,A∨1=1.

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

Б∧Б=Б; Б∨Б=Б.

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

A∧Б∨Б=Б; (A∨Б)∧Б=Б.

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

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

1. Отрицание.

2. Конъюнкция.

3. Дизъюнкция, исключающее ИЛИ.

4. Импликация, эквивалентность.

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

Функции импликации и эквивалентности

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

Импликация, или логическое следование – это высказывание, в котором одно действие является условием, а другое – следствием его выполнения. Иными словами, это предложение с предлогами «если… то». «Любишь кататься, люби и саночки возить». Т. е. для катания необходимо затянуть санки на горку. Если же нет желания съехать с горы, то и санки таскать не приходится. Записывается это так: A→Б или A⇒Б.

Эквивалентность предполагает, что результирующее действие наступает только в том случае, когда истиной являются оба операнда. Например, ночь сменяется днем тогда (и только тогда), когда солнце встает из-за горизонта. На языке математической логики это утверждение записывается так: A≡Б, A⇔Б, A==Б.

Другие законы булевой алгебры

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

Тесное отрицание предполагает, что перед скобкой нет ни одного отрицания: не (А или Б)= не А или НЕ Б.

Когда операнд отрицается, независимо от своего значения, говорят о дополнении:

Б∧¬Б=0; Б∨¬Б=1.

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

Как решать тесты

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

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

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

fb.ru

Булева алгебра (алгебра логики)

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

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

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

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

n переменных равно 2 в степени n. То же самое можно сказать и иначе: число различных n-мерных булевых векторов равно 2 в степени n. А число различных функций алгебры логики от этих векторов равно уже .

Значениям переменной в булевой алгебре соответствуют состояниям элементов микросхем компьютера или любого другого электронного устройства: сигнал присутствует (логическая «1») или сигнал отсутствует (логический «0»).

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

Законы булевой алгебры применяются и в программировании — при написании сложных логических условий и сложных запросов к базе данных. Один пример со скриптом на PHP приведён здесь (это статья о системе многокритериального поиска по сайту с базой данных). Ещё один пример — применение алгебры логики в создании многоуровневого меню сайта, в котором были бы открыты все пункты всех уровней, по которому пролегает путь к конечному открытому пункту меню.

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

Применяются следующие способы описания логических функций:

• словесный;
• табличный;
• числовой;
• аналитический;
• координатный;
• графический.

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

Номер набора	f
0	0
1	1
2	0
3	0
4	1
5	1
6	0
7	1

 

X1	X2	X3	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

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

Пример числового описания логических функций

или .

Пример аналитического описания логических функций

Пример координатного описания логических функций

Карта Карно

Пример графического описания логических функций

Логические функции одной переменной

 

Переменная	Логические функции
x
0	0	0	1	1
1	0	1	0	1

 

Логические функции двух переменных

 

В логических схемах функции могут быть реализованы с произвольных количеством входных переменных, примеры — в материале Логические схемы и таблицы истинности.

Ответить на контрольные вопросы, а затем посмотреть ответы

Контрольный вопрос 1. Даны две переменные x1 и x2. Число различных булевых векторов и различных ФАЛ от полученных векторов равны соответственно:

• 8 и 16
• 8 и 32
• 4 и 8
• 4 и 16

Контрольный вопрос 2. Какие из функций не являются ФАЛ одной переменной (и одна, и вторая в варианте ответа):

• отрицание и сложение по модулю два
• эквивалентность и повторение x
• отрицание и импликация
• функция Шеффера и эквивалентность
• запрет по x2 и отрицание

Правильные ответы на вопрос 1 и вопрос 2.

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

Инверсия (логическое отрицание, «НЕ»)

.

0	1
1	0

Конъюнкция (логическое умножение, «И»)

.

Дизъюнкция (логическое сложение, «ИЛИ»)

.

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

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

Дизъюнктивная нормальная форма

.

Конъюнктивная нормальная форма

.

Аксиомы конъюнкции

.

Аксиомы дизъюнкции

.

Аксиомы отрицания

если , то ; если , то .

Теоремы исключения констант

.

Теоремы идемпотентности (тавтологии, повторения)

.

для n переменных

.

Теорема противоречия

.

Теорема «исключённого третьего»

.

Теорема двойного отрицания (инволюции)

.

Ассоциативный (сочетательный) закон

.

Коммутативный (переместительный) закон

.

Дистибутивный (распределительный) закон

.

.

Законы де Моргана (законы общей инверсии или дуальности)

.

.

Закон поглощения (элиминации)

.

Закон склеивания (исключения)

.

function-x.ru

Основы Булевой алгебры

 

Булева алгебра была впервые описана английским математиком Чарльзом Людвигом Доджосоном, более известным под псевдонимом Льюис Кэрролл, а в 1854 году шотландский математик Джордж Буль ввел двузначную алгебраическую систему, называемую теперь булевой алгеброй. Правда, первоначально аппарат алгебры разрабатывался как средство разбора, подтверждения или, наоборот, отклонения сложных философских высказываний и лишь в 1938 году американский инженер Клод Элвуд Шеннон показал, как приспособить булеву алгебру для описания поведения и анализа схем, составленных из электромеханических реле, которые в то время были самыми распространенными логическими элементами.

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

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

Аксиома 1. X 1, если X 0 и X = 0, если X 1. Другими словами — Да это Да, а Нет это Нет, контакты либо замкнуты, либо разомкнуты и т.д.).

Аксиома 2. Если Х = 0, то Не Х = 1, если Х = 1, то Не Х = 0

Другими словами – если некое реле имеет переключающую группу и в этой группе нормально разомкнутый контакт разомкнут, то в этот же момент времени нормально замкнутый контакт того же реле замкнут.

С учетом перечисленных аксиом рассмотрим три основные простейшие логические операции: дизъюнкцию, конъюнкцию и инверсию.

Операция дизъюнкции (с латинского- разобщение). Обозначается знаками «V» или «+».Другое название этого действия: ИЛИ (операция логического сложения). Для двух переменных Х₁ и Х₂ эта операция даёт результаты, представленные в табл. 1.1, получившей название таблицы истинности, где представлены все возможные сочетания

 

Таблица 1.1

Таблица истинности операции ИЛИ

		Y

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Вывод: Переменная Y принимает единичное значение, если хотя бы одна из переменных равна единице.

Аналитическая запись: Правильная Х₁ V Х₂ = Y, допускаемая Х₁ + Х₂ = Y Читается: Игрек равен икс один или икс два.

Переменных в общем случае может быть n, то есть .

Значение истинно, если истинна хотя бы одна из переменных .

Условное обозначение ЛЭ ИЛИ – дизъюнктора

 

 

Американская

 

 

Схемная реализация логического элемента ИЛИ на контактах и реле

 

 

Операция конъюнкции (с лат. соединение). Другое название «И» (операция логического умножения). Записывается в виде: Правильно Λ или Y = X₁ & X₂, допускается Y = X₁ × X₂ или даже совсем без точки Y = X₁X₂

Читается: Игрек равен икс один И икс два.

Составим таблицу истинности (табл. 1.2) для операции конъюнкции двух переменных, в которой также перечислим все возможные сочетания значений Х₁ и Х₂.

Таблица 1.2

Таблица истинности операции И.

		Y

 

0 · 0 = 0

0 · 1 = 0

1 · 0 = 0

1 · 1 = 1

 

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

Для n переменных:

Значение истинно, если истинны все переменные Х_n.

Условное обозначение логического элемента И – конъюнктора

 

 

Американская

 

Схемная реализация логического элемента И на контактах и реле

 

Операция инверсии (НЕ) — операция логического отрицания

 

Записывается в виде

Читается: Игрек равен не икс

Так как операция выполняется над одной переменной , то число возможных значений равно 2¹ = 2, что и отражено в таблице истинности (табл. 1.3).

Таблица 1.3

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

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

Условное обозначение инвертора

 

 

Американская

 

Схемная реализация на контактах и реле:

 

 

Похожие статьи:

poznayka.org

Основы булевой алгебры

2 глава. Логические основы ЭВМ.

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

Основные элементы булевой алгебры.

Элементами БА являются: числа, операции и функции булевой алгебры.

Числа в булевой алгебре принимают значения из множества {0, 1}. Числа могут быть как переменными, так и постоянными значениями.

Операции в булевой алгебре – действия над числами.

А) Операция отрицания (инверсии). В результате этой операции переменная принимает противоположное значение.

Пример. А=1 – переменная имеет значение равное «1₂».

А=0 – при инверсии переменная принимает значение равное «0₂».

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

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

Б) Операция конъюнкции (логическое умножение, логическая операция «И»).

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

С=А*В=АВ=АВ, где А, В – логические переменные.

С- результат конъюнкции.

Правила логического умножения.

А	В	С
0	0	0
1	1	1
1	0	0

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

Х₁

Y

X_N

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

В) Операция дизъюнкции (логическое сложение, логическая операция «ИЛИ»).

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

С=А+В=АВ= где А, В – логические переменные.

С- результат конъюнкции.

Правила логического умножения.

А	В	С
0	0	0
1	1	1
1	0	1

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

Х₁

Y

X_N

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

Старшинство операций. 1 очередь – инверсия, 2 очередь – умножение, 3 очередь – сложение.

Булевой или логической функцией вида F(x₁,x₂……..x_N), называется функция, аргументами которой являются булевые переменные x_iи которая принимает значения из множества {0,1}.

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

Пример. Y=F(x₁,x₂)= x₁x₂, где n=2 – число аргументов функции.

x₁,x₂ – аргументы функции.

 — операция дизъюнкции, соединяющая аргументы x₁ и x₂.

Отметим, что используя три логические операции (,,) и n-е число булевых переменных можно создать булевые функции любой сложности.

Количество всевозможных функций N от n-го числа аргументов булевой функции выражается зависимостью:

N=(2)ⁿ

Так при n=0 число функций N=2. Такими функциями с n=0 аргументов являются функции не зависящие от аргументов функции.

Пример. F₀( _ )=0 или const=0

F₁( _ )=1 или const=1

При n=1 число функций N=4. Представим зависимость значений этих функций от значений аргументов булевых функций в виде таблицы истинности.

Таблица истинности функций от одной переменной.

Значение аргумента	Значение функции
	Y0	Y1	Y2	Y3
0	0	0	1	1
1	0	1	0	1

Y₁ – функция аналогичная F₀ (смотри предыдущий пример).

Y₃ – функция аналогичная F₁ (смотри предыдущий пример).

Y₂ – функция, выполняющая инверсию аргумента. (Y=X)

Y₁– функция повторения аргумента. (Y= X).

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

M=2ⁿ., где n – число аргументов.

Так при n=1 M=2 (смотри таблицу истинности от 1 аргумента).

Способы задания булевых функций.

Существует 4 способы задания булевых функций.

1. Аналитический. При этом способе функция Y=F(x₁,x₂……..x_N) будет записана в следующем виде:

Y= x₁+x₂x₃……, то есть аналитическая форма представления функции получается при помощи соединения логическими операциями (,,) переменных. Добавим, что эта форма наиболее часто употребляется для представления логических функций.

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

Пример. Функция Y=F(x₁,x₂) – принимает значения 1 при равенстве двух аргументов. Количество наборов M=2ⁿ=2²=4. Тогда таблица истинности будет иметь вид:

Значение аргументов		Значение функции	Примечания
x1	x2	Y
0	0	1	Аргументы равны
0	1	0	Аргументы не равны
1	0	0	Аргументы не равны
1	1	1	Аргументы равны

2. Числовой.

3. Графический.

studfiles.net

4.3. Интерпретации булевой алгебры

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

Булева алгебра множеств описана в гл. 1. Здесь значениями переменных служат подмножества универсального множества U. Константам 1 и 0 соответствуют множества U и . Все соотношения, приведенные в гл. 1, совпадут с основными законами абстрактной булевой алгебры, если операцию дополнения множества заменить на операцию отрицания, а операции  и  (пересечения и объединения множеств) – соответственно на операции  и  (конъюнкции и дизъюнкции).

Интерпретацией абстрактной булевой алгебры является также алгебра событий, используемая в теории вероятностей. Алгебру событий составляют семейство подмножеств множества элементарных событий U и определяемые над этими подмножествами операции отрицания (), объединения () и пересечения (). Любое событие может произойти или не произойти (наступить или не наступить). Отсутствие события А обозначается как А. Событие, состоящее в наступлении обоих событий А и В, называется произведением событий А и В и обозначается А  В или АВ. Событие, состоящее в наступлении хотя бы одного из событий А и В, называется суммой событий А и В и обозначается А  В.

Еще одной интерпретацией является алгебра переключательных схем. Переменным этой алгебры соответствуют элементы переключательной схемы – переключатели. Переключательный элемент, состояние которого представляется булевой переменной а, может быть замкнут, тогда через него течет ток и а  1. Если он разомкнут, то тока нет и а  0. По состояниям переключателей в схеме можно определить, проходит ли по данной схеме ток. На рис. 4.1, а изображено последовательное соединение двух переключателей а и b. Данная схема будет пропускать ток в том и только в том случае, когда оба переключателя замкнуты, т. е. если a  b  1. На рис. 4.1, б изображено параллельное соединение переключателей а и b. Ток будет протекать, если замкнут хотя бы один из переключателей, т. е. если a  b  1.

Два или более переключателей можно условно связать таким образом, чтобы они замыкались и размыкались одновременно. Такие переключатели обычно обозначаются одним и тем же символом. Каждому переключателю можно поставить в соответствие другой переключатель так, чтобы когда один из них замкнут, другой был разомкнут. Если один из них обозначить буквой а, то другой примет обозначение а. В схеме на рис. 4.2 пойдет ток, если и только если а b  bc ab  1. Левая часть этого уравнения представляет структуру схемы.

–––а –––

––––– а ––––– b ––––– ––––– ––––– ––– b –––

а) б)

Рис. 4.1. Примеры соединения переключателей: а) последовательное;

б) параллельное

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

 а   b 

–––––––––– b –––––с ––––––––––

а  b 

Рис. 4.2. Пример переключательной схемы

В исчислении высказываний переменными являются высказывания, принимающие истинные или ложные значения, которые соответствуют константам 1 и 0. Символы операций и их названия в данном случае совпадают не случайно. На основе исчисления высказываний можно выделить булеву алгебру высказываний, которая является одной из интерпретаций абстрактной булевой алгебры. Высказываниеa истинно тогда и только тогда, когда а ложно. Оно читается как «не а» или «не верно, что а». Высказывание a  b, читаемое как «a и b», истинно тогда и только тогда, когда истинны оба высказывания a и b. Высказывание a  b читается как «a или b». Оно истинно, если хотя бы одно из высказываний a и b истинно, и ложно, если оба высказывания ложны.

Другие операции алгебры логики также могут иметь интерпретации в исчислении высказываний. Союз «или» может быть использован при прочтении высказывания a  b. Наряду с «a либо b» его можно читать как «или a, или b». Оно истинно, когда истинно только одно из высказываний a и b, и ложно, когда оба высказывания истинны или оба ложны. Высказывание a ~ b истинно тогда и только тогда, когда значения истинности высказываний a и b совпадают. Это высказывание может быть прочитано следующим образом: «a равносильно b», «a, если и только если b», «a тогда и только тогда, когда b». Импликация a  b читается как «если a, то b». Это высказывание ложно, когда а истинно, а b ложно. Во всех остальных случаях оно истинно.

studfiles.net

Лекция 2. Теория булевых функций. Булева алгебра

Определение.

Множество M с двумя введенными бинарными операциями (& V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (Аксиомы булевой алгебры). Названия операций пока не введены.

1. X & Y = Y&X, X V Y = Y V X – коммутативность.

2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

4. Поглощение – X & X = X, X V X = X.

5. Свойства констант

X & 0 = 0

X & I = X, где I – аналог универсального множества.

6. Инвальтивность (X*)* = X

7. Дополнимость X V X* = I, X & X* = 0.

8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.

U = {a1, a2… an)

[U] = N

[P(U)] = 2n

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

Oбъединение эквивалентно V, пересечение — &, дополнение — *, пустое множество – 0, а универсальное – I.

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

Булева алгебра характеристических векторов.

Пусть A <= U, A <- P(U) a- характеристический вектор этого подмножества.

AA = {a, a2 ..an)

N = [P(U)]

Ai = 1, если ai <- A (принадлежит).

Ai = 0, если ai не принадлежит A.

U = {1 2 3 4 5 6 7 8 9}

A = {2 4 6 8}

B = {1 2 7}

AA = {0 1 0 1 0 1 0 1 0}

AB = {1 1 0 0 0 0 1 0 0}

Или

AA = 010101010 – скобки не нужны

AA= 110000100

Характеристические векторы размерностью n называются булевыми векторами.

Они располагаются в вершинах n – мерного булева куба.

Номером булевого вектора является число в двоичном представлении, которым он является

1101 – номер.

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

Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.

Булев куб размерности 1

Булев куб размерности 2

Булев куб размерности 3

0 – нулевой вектор.

I – вектор из одних единиц.

Отрицание

X = 0 Y = 0

_ _

Х = 1 Y= 1

Для размерности n операции над векторами производятся покоординатно.

Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.

Утверждение

Между множеством всех подмножеств множества U и булевым кубом Bn, где n= =[U] можно установить взаимное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.

Следствие

Множество всех характеристических векторов является булевой алгеброй.

Булева алгебра высказываний (алгебра логики)

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

U = {1 2 3 4 5 6 7 8 9}

A = «число четное»

B = «число, меньшее пяти»

Множеством истинности высказывания называется совокупность всех элементов, для которых это высказывание истинно.

SA = {2 4 6 8}

SB = {1 2 3 4}

Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным.

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

Равносильные высказывания объединим в один класс Р. В. и не будем их разделять, т. к. все они имеют одно и то же множество истинности.

Операции над высказываниями

Дизъюнкция высказываний (V, ИЛИ, OR)

Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.

Конъюнкция высказываний (&, И, AND).

Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.

Отрицание высказываний (- над буквой, НЕ, NOT).

Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.

A B	A & B	A V B	Not A
Л Л	Л	Л	И
Л И	Л	И	И
И Л	Л	И	Л
И И	И	И	Л

Л – ложно.

И – истинно.

Утверждение (основа всей алгебры логики)

Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения.

Следствие. Множество классов эквивалентных высказываний является булевой алгеброй.

Теорема

Существуют 3 булевых алгебры:

1. P(U)

2. Bn

3. Множество классов эквивалентных высказываний.

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

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

< Предыдущая		Следующая >

matica.org.ua

No related posts.