Логотип

Основы цифровой техники

 материалы в категории

Основы логической алгебры

Поскольку в цифровых устройствах всего лишь только два символа: 0 и 1, то алгебра логики использует логические переменные и функции от них, которые также принимают только два значения - 0 и 1.
В логике 0 и 1 это не цифры а символы! Единица обозначает абсолютную истину, символ 0 - абсолютную ложь. Основы алгебры логики придумал в середине XIX века ирландский математик Дж. Буль, поэтому алгебра логики иногда называется булева алгебра.

В отличие от обычной математики, в алгебре логики операции сложения и умножения заменяют операцией логического умножения, которая по-буржуйски звучит красивым словом конъюнкция, и операцией логического сложения (дизъюнкция). Для обозначения операций сложения и умножения используют специальные символы: \/ - логическое сложение, /\ - логическое умножение, но мы для простоты будет обозначать привычными нам + и х, все равно правильно. Опять же, "х" - это не всеми любимая буква, а знак умножения.

Операция логического сложения обозначается союзом "ИЛИ", да да, БОЛЬШИМИ БУКВАМИ. Выражение a + b означает "или a или b". т. е. если и a, и b равно нулю, то и результат равен нулю. Результат равен единице, если хотя бы одна из переменных равна единице. Результат также будет единицей, если обе переменных равны единице.

Логическое умножение обозначается союзом "И", также В ВЕРХНЕМ РЕГИСТРЕ. Выражение a x b означает "a и b", т. е. если a и b равны нулю, то и результат равен нулю. Если одна из переменных равна единице, другая нулю, то результат все равно равен нулю. Результат равен единице, если обе переменных равны единице. В двух словах все вышесказанное: для логического сложения результат равен нулю только при совпадении нулей, для логического умножения результат равен единице только при совпадении единиц.

Есть еще понятие отрицания, обозначаемое "НЕ". Обозначается отрицание чертой над обозначением переменной или символом ¬, стоящим перед переменной. Например, ā означает отрицание a. По-другому это отрицание называется инверсией. То есть, если a = 1, то ā = 0 и наоборот. Отрицание может быть не только одной переменной, но и целого выражения.

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

Аналогично обычной алгебре, в булевой действительны свойства перестановки, сочетательности и распределительности:

a + b = b + a
a x b = b x a
a + (b + c) = (a + b) + c
a x (b x c) = (a x b) x c
a x (b + c) = a x b + a x c

Помимо этих есть и другие, свойственные только алгебре логики, законы:

Законы одинарных элементов
a x 1 = a
a + 1 = 1
a x 0 = 0
a + 0 = a
Законы отрицания
(правила де Моргана)
Распределительность дизъюнкции
a + (b x c) = (a x b) + (a x c)
Правила поглощения
a + (a x b) = a
a x (a + b) = a

Эти правила и законы позволяют значительно упростить логические уравнения и функции.

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

Логический элемент И

Двухвходовый логический элемент "И" обозначается вот так:

логический элемент И обозначение

 

x2 x1 y
0 0 0
0 1 0
1 0 0
1 1 1

Такая табличка называется таблицей истинности логического элемента. Она поясняет, как работает элемент, т. е. какой сигнал на его выходе при определенных сигналах на входе. Таблицы истинности присуще всем цифровым устройствам. В этой таблице символы x1 и x2 означают входные сигналы, y - выходные. Причем входы принято обозначать слева (это касается любых устройств), выходы - справа. Переменная х с индексом 1 обозначает младший разряд, x2 - старший.
Судя по таблице, единица будет на выходе только тогда, когда на обоих входах будут единицы. Символ & говорит о том, что это элемент "И". Не так уж и сложно, правда?

Логический элемент ИЛИ

Логический элемент "ИЛИ" обозначается так:

логический элемент ИЛИ обозначение

Вот его таблица истинности:

x2 x1 y
0 0 0
0 1 1
1 0 1
1 1 1

То есть, единица на выходе тогда, когда хотя бы на одном из входов присутствует единица. Символ 1 говорит о том, что это элемент "ИЛИ".

Логический элемент НЕ

Логический элемент "НЕ", который иначе называется инвертор, обозначается так:

логический элемент НЕ обозгачение

Таблица истинности:

x y
0 1
1 0

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

Теперь поглядим еще на парочку элементов, имеющих некоторые особенности.

Базисные элементы логики

Очевидно, базис происходит от слова "база". Абсолютно в дырочку. Намек понятен?Базисом называется совокупность элементов, с помощью которых схемотехнически можно реализовать устройство любой сложности. Простым языком, базис - это те элементы, при помощи которых можно сделать любое устройство (речь идет о цифровой технике). Да да, абсолютно любое и самое интересное, что этих базисных элементов всего 2. На их основе можно сделать все вышеперечисленные элементы и еще кучу других, что, собственно, и делается.

Элемент И-НЕ

И-НЕ - это схема И и схема НЕ, сложенные вместе. Операция, которую производит такой элемент называется инверсией логического умножения или отрицанием логического умножения, ну или инверсией конъюнкции и еще красивым словосочетанием штрих Шеффера. Штрих кого-то там называется потому, что в виде формулы операция И-НЕ записывается так: y = x1 | x2. Вертикальная черта между иксами и есть штрих какого-то Шеффера.

Логический элемент И-НЕ обозначается так:

логический элемент И-НЕ обозначение

Таблица истинности для него:

x2 x1 y
0 0 1
0 1 1
1 0 1
1 1 0

Ну то есть в принципе тут все просто: чуть выше мы рассматривали логический элемент И, а тут не его выходе прилеплен инвертор и поэтому все показания будут "наизнанку"

Элемент ИЛИ-НЕ

Здесь все по аналогии с элементом И-НЕ. Операция, выполняемая элементом ИЛИ-НЕ называется инверсией логического сложения или инверсией дизъюнкции и еще красивым словосочетанием стрелка Пирса. Стрелка потому, что в виде формулы функция записывается так: y = x 1↓ x2. Символ между иксами и есть стрелка какого-то Пирса.

Обозначается элемент ИЛИ-НЕ вот так:

элемент ИЛИ-НЕ обозначение

Таблица истинности:

x2 x1 y
0 0 1
0 1 0
1 0 0
1 1 0

Аналогично, если к выходу элемента ИЛИ-НЕ прилепить инвертор, то получится элемент ИЛИ.

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

Элемент Исключающий ИЛИ

Операция, выполняемая таким элементом называется сложение по модулю два и обозначается плюсиком в кружочке, т. е. вот таким символом . В виде уровнения функция записывается так: X1X2. Читается это, как "либо икс один, либо икс два". Обозначается элемент ИСКЛЮЧАЮЩЕЕ-ИЛИ вот так:

исключающий или обозначение

Таблица истинности:

x2 x1 y
0 0 0
0 1 1
1 0 1
1 1 0

Кстати, этот элемент можно заменить логическими элементами И, ИЛИ, НЕ, поскольку

 

Для пущей наглядности составим схему из базисных элементов (И-НЕ, ИЛИ-НЕ):

исключающий или на логике

 Вот вам и применение законов алгебры логики. Где это может пригодиться? Ну допустим, собираете вы какую-то схему с использованием цифровых микросхем, среди которых есть логический элемент ИСКЛЮЧАЮЩЕЕ-ИЛИ (или два), а у вас его нет. Ну в падлу идти в магазин или где-то ковыряться в платах. А тут бах, под рукой завались микросхем с логикой И-НЕ, ИЛИ-НЕ, например 155ЛА3. Таким образом, зная свойства цифровых устройств и основы булевой алгебры, недостающий элемент легко заменяется другими. К тому же, подобный метод имеет и обратное направление, т. е. если в какой-то схеме стоит изображенная на рисунке часть, она легко заменяется на один элемент ИСКЛЮЧАЮЩЕЕ-ИЛИ (а вдруг автор схемы торопился и не догадался сам этого сделать). Причем схемотехническая часть может быть любой, главное, чтобы выполнялось условие сложения по модулю два. Идея ясна? Подобным принципом менять можно почти все, суть в том, чтобы максимально упростить схемотехнику при сохранении ее простоты и легкоповторяемости.

Примечание: подсмотрено на сайте http://naf-st.ru/

Почта сайта