Лекция 2. Булева алгебра. Основы логики, логические связки, таблицы истинности.
Аппарат булева алгебра создан в 1854 г. Дж. Булем как попытка изучения логики мышления математическими методами. Булева алгебра - основное средство анализа, разработки и описания структурно - функциональной архитектуры современной вычислительной техники.
Схемы вычислительных устройств можно условно разделить на три группы: исполнительные, информационные и управляющие.
- Исполнительные схемы производят обработку информации, представленной в бинарной форме.
- Информационные схемы служат для передачи бинарной информации.
- Управляющие схемы выполняют управляющие функции, генерируя соответствующие сигналы.
Во всех случаях используются сигналы двух различных уровней, которые могут представляться бинарными символами (0,1) или логическими значениями Истина (true), Ложь (false).
Базовыми булевыми операциями являются операции И (AND), ИЛИ (OR), НЕ (NOT) (таблица 2.1). Операция И (AND) называется конъюнкцией (логическим умножением), операция ИЛИ (OR) называется дизъюнкцией (логическим сложением), НЕ (NOT) называется инверсией (логическим отрицанием):
1) Логическое умножение или конъюнкция:
Конъюнкция - это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное выражение ложно.
Обозначение: F = A & B.
2) Логическое сложение или дизъюнкция:
Дизъюнкция - это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражения ложны.
Обозначение: F = A + B.
3) Логическое отрицание или инверсия:
Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным.
Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
Переменные Конъюнкция Дизъюнкция Отрицание
X Y X×Y или X^Y X+Y или XvY X' или X
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 0
Таблица 2.1 Базовые булевы операции
Элементарные логические схемы, используемые при создании средств ВТ, называются вентилями. В настоящее время существует целый ряд базовых вентилей, на основе которых строится современная ЭВМ. Набор логических операций {И, ИЛИ, НЕ} является универсальным, т. е. на его основе можно представлять любую логическую функцию, то соответствующий ему набор вентилей также будет универсальным:
На основе базовых вентилей может быть построена любая логическая схема, при этом вентили И, ИЛИ могут иметь любое число входов, определяемое количеством переменных логического выражения, описывающего логическую схему.
 |  |  |
На основе базовых вентилей может быть построена любая логическая схема, при этом вентили И, ИЛИ могут иметь любое число входов, определяемое количеством переменных логического выражения, описывающего логическую схему.
Рассмотрим дополнительные логические операции – импликацию и эквивалентность.
4) Логическое следование или импликация:
Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.
Таблица истинности для импликации
A | B | F |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 1 |
0 | 0 | 1 |
5) Логическая равнозначность или эквивалентность:
Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
Таблица истинности для эквивалентности
A | B | F |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 1 |
Порядок выполнения логических операций в сложном логическом выражении
1. Инверсия; 2. Конъюнкция; 3. Дизъюнкция; 4. Импликация; 5. Эквивалентность.
Конъюнкции соответствует операция пересечения множеств, т. е. множеству получившемуся в результате умножения множеств А и В соответствует множество, состоящее из элементов, принадлежащих одновременно двум множествам.
Дизъюнкции соответствует операция объединения множеств, т. е. множеству получившемуся в результате сложения множеств А и В соответствует множество, состоящее из элементов, принадлежащих либо множеству А, либо множеству В.
Логическому отрицанию соответствует операция дополнения до универсального множества, т. е. множеству получившемуся в результате отрицания множества А соответствует множество, дополняющее его до универсального множества.
