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

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

Определение

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


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

  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) Дистибутивный (распределительный) закон

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

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

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


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

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

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

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


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