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

Материал из wireshark.wiki

Введение

Булева алгебра – это раздел математической логики, в котором переменные могут иметь всего два значения: «истина» (обычно обозначается как 1) и «ложь» (обычно обозначается как 0). Булева алгебра также известна как булева логика, двоичная логика, двоичная алгебра, алгебра высказываний.

Основы булевой алгебры были заложены в девятнадцатом веке английским математиком Джорджем Булем. Его работа легла в основу многих последующих исследований в области логической алгебры. Уильям Стэнли Джевонс, Эрнст Шрёдер, Чарльз Пирс, Готлоб Фреге, Бертран Рассел, Альфред Норт, Платон Сергеевич Порецкий, Валерий Иванович Гливенко и некоторые другие ученые продолжили развитие его идей, расширяя границы использования алгебраических принципов в логике.

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

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

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

Проверка знаний

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


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

Основы

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


Логическое «И»

Русскоязычное обозначение: И.

Англоязычное обозначение: AND.

Символьное обозначение: ∧, &, &&, ·.

Другие названия: конъюнкция, логическое умножение.

Короткое описание: A ∧ B истинно, если одновременно истинно A и истинно B.

Развернутое описание: при использовании логического «И» выходное значение будет истинным, только если будут истинными все входные значения. Во всех остальных случаях результат будет ложным.

Аналогия: лампочка в светильнике будет гореть (свет = истина) только при одновременном выполнении двух условий: если есть электричество (электричество = истина) и тумблер находится в положении «Включено» (положение «Включено» = истина). Если хотя бы одно из двух условий является ложным, то лампочка гореть не будет (свет = ложь).

Таблица истинности логического «И»
A B A ∧ B
0 0 0
0 1 0
1 0 0
1 1 1


Логическое «ИЛИ»

Русскоязычное обозначение: ИЛИ.

Англоязычное обозначение: OR.

Символьное обозначение: ∨, |, ||, +.

Другие названия: дизъюнкция, логическое сложение.

Короткое описание: A ∨ B истинно, если A ≠ B.

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

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

Таблица истинности логического «ИЛИ»
A B A ∨ B
0 0 0
0 1 1
1 0 1
1 1 1


Логическое «НЕ»

Русскоязычное обозначение: НЕ.

Англоязычное обозначение: NOT.

Символьное обозначение: ¬, !, ~, A̅.

Другие названия: инверсия, отрицание.

Короткое описание: ¬A истинно, если A ложно и ¬A ложно, если A истинно.

Развернутое описание: при использовании логического оператора «НЕ» выходное значение будет противоположным входному значению. Если входное значение истинно, выходное будет ложным, и наоборот.

Аналогия: если человек бодрствует (бодрствование = истина), то он НЕ спит (сон = ложь) и наоборот, если человек спит (сон = истина), то он НЕ бодрствует (бодрствование = ложь).

Таблица истинности логического «НЕ»
A ¬A
0 1
1 0


Суммарная информация

Основные операции булевой логики
Русскоязычное обозначение операции Англоязычное обозначение операции Символьное обозначение операции Примеры использования Другие названия
И AND Λ, &, &&, · A AND B,

A Λ B,

A & B,

A · B

Конъюнкция, логическое умножение
ИЛИ OR ∨, |, ||, + A OR B,

A ∨ B,

A + B

Дизъюнкция, логическое сложение
НЕ NOT ¬, !, ~, A̅ ¬A,

Инверсия, отрицание


Таблица истинности основных логических операций булевой алгебры
A B A ∧ B A ∨ B ¬A
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 0


Порядок выполнения операций

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

  1. Операция «НЕ» (NOT, ¬, !, A̅), так как она имеет самый высокий приоритет.
  2. Операция «И» (AND, &, ∧, ·).
  3. Операция «ИЛИ» (OR, ∨, |, +), так как она имеет самый низкий приоритет.

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


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

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


Свойства, связанные только с одной переменной

  1. A = A
  2. ¬(¬A) = A
  3. A ∧ 0 = 0
  4. A ∧ 1 = A
  5. A ∨ 0 = A
  6. A ∨ 1 = 1
  7. A ∧ ¬A = 0
  8. A ∨ ¬A = 1
  9. A ∧ A = A
  10. A ∨ A = A


Законы и свойства, связанные с одной и более чем одной переменной

Название закона или свойства Для операции И Для операции ИЛИ
Свойства констант1
A ∧ 0 = 0
A ∧ 1 = A
A ∨ 0 = A
A ∨ 1 = 1
Свойства комплементарности (дополнительности) 1
A ∧ ¬A = 0
A ∨ ¬A = 1
Свойства идемпотентности1
A ∧ A = A
A ∨ A = A
Свойства коммутативности (переместительности)
A ∧ B = B ∧ A
A ∨ B = B ∨ A
Свойства ассоциативности (сочетательности)
A ∧ (B ∧ C) = (A ∧ B) ∧ C
A ∨ (B ∨ C) = ( A ∨ B) ∨ C
Свойства дистрибутивности (распределительности)
A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
Законы де Моргана
¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
Законы поглощения
A ∧ (A ∨ B) = A
A ∨ (A ∧ B) = A
Законы Блейка – Порецкого
A ∨ (¬A ∧ B) = A ∨ B
A ∧ (¬A ∨ B) = A ∧ B
Свойства склеивания
(A ∧ B) ∨ (¬A ∧ B) = B
(A ∨ B) ∧ (¬A ∨ B) = B

1 В графе дублируется информация из раздела «Свойства, связанные только с одной переменной».


Проверка знаний по булевой алгебре

Доступ к базе из более 100 вопросов

Проверить знания по булевой алгебре можно в личном кабинете проекта «Курсы-по-ит.рф». Проверка полностью бесплатная и не требует какой-либо регистрации.

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

  1. Перейти на сайт: https://kursy-po-it.online.
  2. Указать (без кавычек) имя пользователя: «demo» и пароль: «Pass66word!».
  3. Выбрать курс «Архитектура современных компьютерных сетей (демоверсия)».
  4. В разделе «Работы, доступные в демоверсии курса» выбрать подраздел «Модуль 1. Математика и физика | Часть 2. Булева алгебра».

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


Примеры вопросов

Демовопрос № 1 по булевой алгебре

Демовопрос № 4 по булевой алгебре

Демовопрос № 6 по булевой алгебре

Демовопрос № 10 по булевой алгебре

Демовопрос № 18 по булевой алгебре


Составные операции булевой алгебры

Основы

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


Логическое исключающее «ИЛИ»

Русскоязычное обозначение: исключающее ИЛИ.

Англоязычное обозначение: XOR.

Символьное обозначение: ⊕, ^^.

Другие названия: взаимоисключающее ИЛИ, неравнозначность.

Короткое описание: A ⊕ B истинно, если A ≠ B.

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

Аналогия: можно смотреть фильм (просмотр фильма = истина) либо в одном кинозале, либо в другом. Нельзя одновременно смотреть фильмы в обоих кинозалах. Так же не получится смотреть фильм, если не посетить ни один из кинозалов.

Таблица истинности логического исключающего «ИЛИ»
A B A ⊕ B
0 0 0
0 1 1
1 0 1
1 1 0

Логическое отрицание исключающего «ИЛИ»

Русскоязычное обозначение: отрицание исключающего ИЛИ.

Англоязычное обозначение: XNOR.

Символьное обозначение: ↔, ≡.

Другие названия: эквиваленция, логическая равнозначность.

Короткое описание: A ↔ B истинно, если A = B.

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

Аналогия: на весах установлены два датчика. Первый датчик срабатывает, когда вес груза превышает 5 килограмм. Второй датчик реагирует, когда вес груза превышает 10 килограмм. Есть лампочка-индикатор, которая загорается в двух случаях: если ни один из датчиков не сработал (груз весит менее 5 килограмм) или если оба датчика активированы (груз весит более 10 килограмм).

Таблица истинности логического отрицания исключающего «ИЛИ»
A B A ↔ B
0 0 1
0 1 0
1 0 0
1 1 1


Логическое «ЕСЛИ… ТО»

Русскоязычное обозначение: ЕСЛИ… ТО.

Англоязычное обозначение: IMPL, IMP.

Символьное обозначение: →.

Другие названия: условное утверждение, импликация, импликационное следование.

Короткое описание: A → B истинно, если A ≤ B.

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

Аналогия: рассмотрим два утверждения – A (x делится на 9) и B (x делится на 3). В этом случае возможны следующие варианты:

  • Истинное утверждение: если x не делится на 9, то x не делится и на 3. Пример: x = 20.
  • Истинное утверждение: если x не делится на 9, то, возможно, x делится на 3. Пример: x = 12.
  • Ложное утверждение: если x делится на 9, то невозможна ситуация, в которой x не делится на 3.
  • Истинное утверждение: если x делится на 9, то x обязательно делится на 3. Пример: x = 18.
Таблица истинности логического импликационного следования
A B A → B
0 0 1
0 1 1
1 0 0
1 1 1


Логическое обратное «ЕСЛИ… ТО»

Русскоязычное обозначение: обратное ЕСЛИ… ТО.

Англоязычное обозначение: отсутствует.

Символьное обозначение: ←.

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

Короткое описание: A ← B истинно, если A ≥ B.

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

Аналогия: рассмотрим два утверждения – A (x делится на 3) и B (x делится на 9). В этом случае возможны следующие варианты:

  • Истинное утверждение: если x не делится на 3, то x не делится и на 9. Пример: x = 20.
  • Ложное утверждение: если x не делится на 3, то x делится на 9.
  • Истинное утверждение: если x делится на 3, то возможна ситуация, в которой x не делится на 9. Пример: x = 12.
  • Истинное утверждение: если x делится на 3, то, возможно, x делится на 9. Пример: x = 18.
Таблица истинности логического обратного импликационного следования
A B A ← B
0 0 1
0 1 0
1 0 1
1 1 1


Логическое «НЕ-И»

Русскоязычное обозначение: НЕ-И.

Англоязычное обозначение: NOT AND, NAND.

Символьное обозначение: ↑.

Другие названия: отрицание И, И-НЕ, отрицание конъюнкции, штрих Шеффера.

Короткое описание: A ↑ B истинно, если ложно A или ложно B.

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

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

Таблица истинности логического «НЕ-И»
A B A ↑ B
0 0 1
0 1 1
1 0 1
1 1 0


Логическое отрицание «НЕ-ИЛИ»

Русскоязычное обозначение: НЕ-ИЛИ.

Англоязычное обозначение: NOT OR, NOR.

Символьное обозначение: ↓.

Другие названия: отрицание ИЛИ, ИЛИ-НЕ, отрицание дизъюнкции, стрелка Пирса, функция Вебба.

Короткое описание: A ↓ B истинно, если одновременно ложно A и ложно B.

Развернутое описание: логическая операция «НЕ-ИЛИ» представляет собой комбинацию операций «НЕ» и «ИЛИ». Выходное значение операции «НЕ-И» будет истинным, только если оба входных значения ложны. Во всех остальных случаях результат будет ложным.

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

Таблица истинности логического «НЕ-ИЛИ»
A B A ↓ B
0 0 1
0 1 0
1 0 0
1 1 0


Суммарная информация

Составные операции булевой алгебры
Русскоязычное обозначение операции Англоязычное обозначение операции Символьное обозначение операции Примеры использования Другие названия
Исключающее ИЛИ XOR
A ⊕ B,
A XOR B
Взаимоисключающее ИЛИ
Отрицание исключающего ИЛИ XNOR ↔, ≡
A XNOR B,
A ≡ B
Эквиваленция
ЕСЛИ… ТО IMPL, IMP
A IMPL B,
A IMP B, A → B
Условное утверждение, импликация, импликационное следование
Обратное ЕСЛИ… ТО B ← A Обратное условное утверждение, обратная импликация, обратное импликационное следование
НЕ-И NOT AND, NAND A NOT AND B,

A NAND B,

A ↑ B

Отрицание И
НЕ-ИЛИ NOT OR, NOR A NOT AND B,

A NOR B,

A ↓ B

Отрицание ИЛИ


Таблица истинности составных логических операций булевой алгебры
A B
A ⊕ B
A ↔ B
A → B
A ← B
A ↑ B
A ↓ B
0 0 0 1 1 1 1 1
0 1 1 0 1 0 1 0
1 0 1 0 0 1 1 0
1 1 0 1 1 1 0 0