Для структурно-функционального описания логических схем, составляющих основу любого дискретного вычислительного устройства, ЭВМ или ВС в целом, используется аппарат булевой алгебры, созданной в 1854 г. Дж. Булем как попытка изучения логики мышления математическими методами.
Являясь основным средством анализа, разработки и описания структурно-функциональной архитектуры современной ВТ, булева алгебра является обязательной составной частью курса компьютерной информатики, а также целою ряда разделов вычислительных наук.
В общем случае любая формальная математическая система состоит из трех множеств: элементов, операций над ними и аксиом.
Схемы вычислительных устройств можно условно разделить на три группы: исполнительные, информационные и управляющие. Первые производят обработку информации, представленной в бинарной форме; вторые служат для передачи бинарной формы информации; третьи выполняют управляющие функции, генерируя соответствующие сигналы.
Во всех случаях, как правило, в тех или иных точках логических схем появляются сигналы двух различных уровней. Следовательно, сигналы могут представляться бинарными символами {0, 1} или логическими значениями {Истина (True), Ложь (False)}.
Поэтому, множество элементов В={0,1}булевой алгебры выбирается бинарным, такая алгебра называется бинарной или переключательной. Ее элементы называются константами, или логическими 0 и 1; а ряде случаев логическим 0 и 1 соответствуют бинарные цифры, в других случаях им соответствуют логические значения соответственно Ложь (False) и Истина (True).
Для структурно-функционального описания логических схем ее узлам ставятся в соответствие булевы переменные, принимающие логические значения 0 и 1; для обозначения булевых переменных будем использовать латинский алфавит.
Определив множество элементов булевой алгебры, необходимо задать для нее множества операций и постулатов (аксиом)
Таблица 1
| Переменные | Базовые логические операции | |||
| х.. | Y | {X·Y|X^Y} | {X+Y|X\/Y} | {X'X} |
| (а) | (б) | (в) |
Существует несколько булевых операций, из которых только три: И (AND), ИЛИ (OR) и НЕ(NOT) — полагаются базовыми, остальные можно получать на их основе.
Операция И называется логическим умножением или конъюнкцией, обозначается знаком {|^} умножения и определяется табл. 1 (а).
Операция ИЛИ называется логическим сложением или дизъюнкцией, обозначается знаком {+|\/} и определяется табл. 1 (б).
Операция НЕ называется логическим отрицанием или инверсией (дополнением), обозначается знаком {‘|} и определяется табл. 1 (в); табл. 1 задает аксиомы (постулаты) булевой алгебры.
Таким образом, булева алгебра определяется множеством элементов В={0,1}, множеством операций { И, ИЛИ, НЕ } и аксиомами, определяемыми табл. 3.
Так как целью булевой алгебры является структурно-функциональное описание логических схем (ЛС), то мы должны располагать соответствующей методикой.
Представив ЛС в виде некоторого черного ящика (рис. 1), имеющего п входов и один выход, его поведение можно определять некоторой логической F(x1, x2,..., хп) -функцией от п логических переменных.
Логическая F-функция может быть задана таблицей истинности (табл. 2) или посредством 6улевых выражений; ЛС, представимые одним из этих способов, называются комбинационными.
Рис. 1. Формальное представление произвольной логической схемы
Таблица 2 Таблица истинности F-функции
| х1 | х2 | .... | хn-1 | хn | F(х1, х2,…, хn) |
| .... | F(0,0,…,0,0) | ||||
| .... | F(0,0,...,0,1) | ||||
| .... | F(0,0,....,1,0) | ||||
| .... | .... | .... | .... | .... | .... |
| F(1,1, …,1,1) |
Другой класс составляют ЛС с внутренней памятью, называемые последовательностными; для них значения выходных логических переменных определяются не только текущими значениями входных переменных, но также их значениями в предыдущие моменты времени. Мы ограничимся рассмотрением только комбинационных ЛС, что вполне достаточно для иллюстрации рассматриваемой проблематики.
Логические переменные, объединенные знаками логических операций, составляют логические выражения. При вычислении значения логического выражения определено следующее старшинство выполнения логических операций: сначала выполняется инверсия, затем конъюнкция и в последнюю очередь— дизъюнкция.
