Глава 5. Логические основы построения персональных компьютеров
5.1. Аппарат алгебры логики
Основу любого дискретного вычислительного устройства, в том числе персонального компьютера, составляют элементарные логические схемы. Работа этих схем основана на законах и правилах алгебры логики, которая оперирует двумя понятиями: истинности и ложности высказывания.
Алгебра логики – раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.
Высказывание – некоторое предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Аппарат алгебры логики (булевой алгебры) создан в 1854 году Дж. Булем как попытка изучения логики мышления математическими методами. Впервые практическое применение булевой алгебры было сделано К. Шенноном в 1938 году для анализа и разработки релейных переключательных сетей. Результатом чего явилась разработка метода представления любой сети, состоящей из совокупности переключателей и реле, математическими выражениями и принципов их преобразования на основе правил булевой алгебры.
Аппарат булевой алгебры, как и любая другая формальная математическая система состоит из трех множеств: элементов, операций над ними и аксиом.
Элементы. Наименьшим элементом алгебры логики является 0, наибольшим элементом - 1.
Поэтому множество элементов булевой алгебры выбирается бинарным В = {0,1}, а сама алгебра называется бинарной, или переключательной.
Ее элементы называются константами, или логическими 0 и 1, которым в ряде случаев соответствуют бинарные цифры, а в других случаях – логические значения истина (True) и ложь (False).
Операции. Основными, или базовыми, операциями булевой алгебры служат: И (AND), ИЛИ (OR) и НЕ (NOT), табл. 5.1.
Операция И называется логическим умножением или конъюнкцией и обозначается знаком умножения { ×, ^}.
Операция ИЛИ называется логическим сложением или дизъюнкцией и обозначается знаком сложения { +, v}.
Операция НЕ называется логическим отрицанием или инверсией (дополнением) и обозначается знаком { -, ¬}.
Таблица 5.1.
Базовые логические операции
|
Операция |
Название операции |
Обозначение операции |
|
И (AND) |
Логическое умножение - конъюнкция |
* ^ |
|
ИЛИ (OR) |
Логическое сложение - дизъюнкция |
+ v |
|
НЕ (NOT) |
Логическое отрицание - инверсия |
- ¬ |
При выполнении операций применяются отношение эквивалентности “=” и скобки “()”, которые определяют порядок выполнения операций. Если скобок нет, то операции выполняются в следующей последовательности: логическое отрицание, логическое умножение и логическое сложение.
5.2. Основные аксиомы и законы алгебры логики
Аксиомы (постулаты) алгебры логики:
-
Дизъюнкция двух переменных равна 1, если хотя бы одна из них равна 1:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
-
Конъюнкция двух переменных равна 0, если хотя бы одна из них равна 0:
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1
-
Инверсия одного значения переменой совпадает с ее другим значением:
1 = 0
0
= 1
Законы алгебры логики:
-
Сочетательный:
( a + b ) + c = a + ( b + c )
( a * b ) * c = a * ( b * c )
-
Переместительный:
a + b = b + a
a * b = b * a
-
Распределительный:
a * ( b + c ) = a * b + a * c
a + b * c = a * b + a * c