Цифровая логика организации компьютеров

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

Этот вид алгебры работает с 0 и 1, здесь присутствуют такие операции (табл. 1.0) как: И (конъюнкция), ИЛИ (дизъюнкция), НЕ (отрицание), ИСКЛЮЧАЮЩЕЕ ИЛИ и их комбинации и т.д. Чтобы описать логические функции можно использовать разные способы, но мы сконцентрируемся только на двух: таблица истинности и дизъюнктивно нормальная форма.

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

Минтерма представляет собой логическую функцию, которая принимает истинное значение только при одном наборе значений входящих в нее переменных, реализуется это за счет взятия И от всех переменных (с или без НЕ). Например !A&B&C (! — НЕ, & — И) принимает истинное значение только, когда A=0, B=C=1. Когда мы представим все истинные строки в виде минтерм, потребуется взять от всех минтерм ИЛИ (дизъюнкцию). Так вот теперь объединяя все выше сказанное мы можем реализовать функцию в виде схемы.

Например, давайте возьмем функцию ИСКЛЮЧАЮЩЕЕ ИЛИ (табл. 1.0). Мы видим, что у нее есть две истинные строки: при A=0, B=1 и A=1, B=0. Мы берем и представляем их как две минтермы, !A&B и A&!B. Действительно, первая минтерма равна 1 только в том случае, когда A=0, B=1; Другая только в том случае, когда A=1, B=0; Как раз таки у нас только такие строки в таблице истинности принимают истинные значения. Теперь когда у нас есть все необходимые минтермы, мы берем от всех минтерм операцию ИЛИ, то есть, (A&!B) | (!A&B). Мы взяли и представили функцию ИСКЛЮЧАЮЩЕЕ ИЛИ в виде формулы, которую можем легко представить в виде логической схемы (рис 1.1а), ведь она состоит из простых функций: двух И и одной ИЛИ. Было бы эффективней если бы мы сократили (рис. 1.1б) кол-во входов, для этого можно объединить A с !A в один вход A, только понадобится еще добавить между новым входом А и старым входом !A вентиль НЕ, чтобы входной сигнала для A был противоположным для старых A и !A; то же самое можем сделать с B и !B.

Рисунок 1.1. Схема ИСКЛЮЧАЮЩЕГО ИЛИ (черта над переменной обозначает НЕ).