Алгебра логики Джорджа Буля

Эта статья — о применении булевой алгебры в схемотехнике. Логические элементы.

А́лгебра ло́гики Джо́рджа Бу́ля (бу́лева а́лгебра) — раздел математической логики, изучающий высказывания и операции над ними.

Названа в честь Джорджа Буля, английского математика и логика, который ставил перед собой цель решать традиционные логические задачи посредством алгебраических методов. Для этого Буль стал обозначать символами не числа, как это делается в обычной алгебре, а высказывания, и показал, что уравнениями, схожими с алгебраическими, можно решать вопросы об истинности и ложности высказываний. При этом смысл и содержание высказываний не играют никакой роли, они характеризуются только одним качеством — значением истинности, то есть все элементы булевой алгебры определены в двоичном множестве символов {«ложь», «истина»}.

В математических выражениях множеству {«ложь», «истина»} сопоставляется множество {«логический 0», «логическая 1»}.

Одним из первых, кто показал, что математический аппарат булевой алгебры может иметь прикладное применение в технике, был Клод Шеннон, сформулировавший теорию релейно-контактных схем. Шеннон доказал, что булева алгебра полностью пригодна для анализа и синтеза релейных и переключательных схем. В основу своей теории Шеннон положил соответствие области существования булевых переменных в множестве {«логический 0», «логическая 1»} бинарным состояниям контактов электромеханических реле: «контакт замкнут», «контакт разомкнут».

Замкнутый контакт реле, обеспечивающий прохождение тока в цепи, соответствовал переменой «логическая 1», разомкнутый контакт — переменной «логический 0». В дальнейшем эта теория нашла свое развитие и применение при разработке как релейно-контактных схем, так и специализированных электронных систем, а также при создании систем управления на базе свободно программируемых цифровых устройств.

Булевы функции

Полный набор булевых функций для $n$ переменных представлен в таблице, называемой таблицей истинности. Каждая функция соответствует своему набору переменных $x$ в множестве {«логический 0», «логическая 1»} или, сокращённо, {«0», «1»}. Количество переменных $x$ в каждом наборе составляет $2^{n}$. Общее число функций для $n$ переменных составляет $m$ = $2^{2^{n}}$

Функции n переменных
	X1	X2	…	Xn-1	Xn	Ym = fm(X1,X2,…,Xn-1,Xn)
1e-06	0	0	...	0	0	Y0 = f0 (0,0,…,0,0)
2e-06	0	0	...	0	1	Y1 = f1 (0,0,…,0,1)
3e-06	0	0	...	1	0	Y2 = f2 (0,0,…,1,0)
4e-06	0	0	...	1	1	Y3 = f3 (0,0,…,1,1)
5e-06	...	...	...	...	...	...
6e-06	1	1	...	1	0	Ym-1 = fm-1 (1,1,…,1,0)
7e-06	1	1	...	1	1	Ym = fm (1,1,…,1,1)

Функции одной переменной

Наборы булевых функций для одной переменной, когда $n$ = 1, представлены в приведённой ниже таблице истинности. Количество функций согласно формуле m = $2^{2^{n}}$составляет $2^{2^{1}}$ = 4. Обозначим их как Y₀, Y₁, Y₂, Y₃

Функции одной переменной
	X	Y0	Y1	Y2	Y3
1e-06	0	0	0	1	1
2e-06	1	0	1	0	1

• Функция Y₀ не зависит от значений переменной $x$ и носит название «константа ноль» (const 0);
• Функция Y₁ повторяет значения переменной $x$ и носит название «тождественная функция»;
• Функция Y₂ имеет значения, инверсные значениям переменной $x$ и носит название «функция НЕ» или «логическое отрицание»;
• Функция Y₃ не зависит от значений переменной $x$ и носит название «константа единица» (const 1);

Функции двух переменных

Наборы булевых функций для двух переменных, когда $n$=2, представлены в приведённой ниже таблице истинности. Количество функций согласно формуле $m$ = $2^{2^{n}}$составляет $2^{2^{2}}$ = 16. Обозначим их как Y₀, Y₁, Y₂,…, Y₁₅

Функции двух переменных
	X1	X2	Y0	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8	Y9	Y10	Y11	Y12	Y13	Y14	Y15
1e-06	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
2e-06	0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
3e-06	1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
4e-06	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Легко заметить, что сочетания «0» и «1» в значениях функций соответствуют их номерам, записанным в двоичной системе счисления.

Например, номер функции Y₁, равный 1 в десятичной системе счисления, в двоичной записывается как 0001. Соответственно Y₂ имеет номер 2₁₀ = 0010₂, последняя функция Y₁₅ имеет номер 15₁₀ = 1111₂

Приведенная таблица истинности отражает все возможные булевы функции от двух переменных. Они имеют названия и специальные обозначения.

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

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

Рассмотрим логические элементы, выполненные в виде электронных устройств, каждое из которых предназначено для выполнения определённой логической функции. Обработка информации производится в виде обработки электрических сигналов низкого и высокого уровней, соответствующих переменным «0», «1» в двоичной логике, то есть эти устройства выполняют логическую операцию над входными сигналами и позволяют получить на выходе сигналы в той же форме «0», «1», соответствующие значению выполняемой логической функции.

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

Таблицы истинности и логические элементы приведены для двух входных переменных, но в ряде случаев правило распространяется на любое количество переменных. Например, логический элемент, реализующий функцию «И» (см. ниже), теоретически может иметь 1,2,3,…, k входов.

Конъюнкция (логическое умножение). Операция «И»

Логический элемент, реализующий функцию конъюнкции, называется схемой логического умножения или схемой «И». Функция принимает значение «1» в том и только в том случае, когда все её аргументы принимают значение «1».

Запись функции: Y = A$\land$B, Y = A$\And$B. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y₁.

Обозначение на схеме:

• Элемент «И»
• 
• 

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

Функция «И»
	A	B	Y = A$\land$B
1e-06	0	0	0
2e-06	0	1	0
3e-06	1	0	0
4e-06	1	1	1

Дизъюнкция (логическое сложение). Операция «ИЛИ»

Логический элемент, реализующий функцию дизъюнкции, называется схемой логического сложения — схемой «ИЛИ». Функция принимает значение «1» в том и только в том случае, когда любой из её аргументов или все принимают значение «1».

Запись функции: Y = A$\lor$B, Y = A+B. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y₇.

Обозначение на схеме:

• Элемент «ИЛИ»
• 
• 

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

Функция «ИЛИ»
	A	B	Y = A$\lor$B
1e-06	0	0	0
2e-06	0	1	1
3e-06	1	0	1
4e-06	1	1	1

Отрицание. Операция «НЕ»

Логический элемент, реализующий функцию инверсии входной переменной, называется схемой «НЕ». Функция относится к разряду унитарных, принимает значение «1» в том случае, когда входной аргумент принимает значение «0» и наоборот, принимает значение «0», когда входной аргумент принимает значение «1». Запись функции: Y =⌝A, Y = Ā. В таблице, приведённой выше для булевых функций от одной переменной, это функция Y₂.

Обозначение на схеме:

• Элемент «НЕ»
• 
• 

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

Функция «НЕ»
	A	Y =⌝A
1e-06	0	1
2e-06	1	0

Отрицание конъюнкции. Операция «И-НЕ»

Логический элемент, реализующий функцию отрицания конъюнкции (штрих Шеффера), называется схемой «И-НЕ». Функция принимает значение «1» в том и только в том случае, когда любой из её аргументов или все принимают значение «0». Является инверсией функции «И». Запись функции: Y = A|B. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y₁₄.

Обозначение на схеме:

• Элемент «И-НЕ»
• 
• 

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

Функция «И-НЕ»
	A	B	Y = A|B
1e-06	0	0	1
2e-06	0	1	1
3e-06	1	0	1
4e-06	1	1	0

Отрицание дизъюнкции. Операция «ИЛИ-НЕ»

Логический элемент, реализующий функцию отрицания дизъюнкции (стрелка Пирса), называется схемой «ИЛИ-НЕ». Функция принимает значение «1» в том и только в том случае, когда все её аргументы принимают значение «0». Является инверсией функции «ИЛИ». Запись функции: Y = A$\downarrow$B. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y₈.

Обозначение на схеме:

• Элемент «ИЛИ-НЕ»
• 
• 

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

Функция «ИЛИ-НЕ»
	A	B	Y = A$\downarrow$B
1e-06	0	0	1
2e-06	0	1	0
3e-06	1	0	0
4e-06	1	1	0

Сложение по модулю два. Операция «Исключающее ИЛИ»

Логический элемент, реализующий функцию сложение по модулю два, называется схемой «Исключающее ИЛИ» (иначе эту функцию называют альтернативой или «строгое ИЛИ»). Функция принимает значение «1» в том и только в том случае, когда только один из её аргументов принимает значение «1». Математически реализует сложение двух двоичных чисел без переноса результата в старший разряд. Запись функции: Y = A⊕B. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y₆.

Обозначение на схеме:

• Элемент «Исключающее ИЛИ»
• 
• 

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

Функция «Исключающее ИЛИ»
	A	B	Y = A⊕B
1e-06	0	0	0
2e-06	0	1	1
3e-06	1	0	1
4e-06	1	1	0

Равнозначность. Операция «Исключающее ИЛИ-НЕ»

Логический элемент, реализующий функцию равнозначности аргументов, называется схемой «Исключающее ИЛИ-НЕ». Функция принимает значение «1» в том и только в том случае, когда все её аргументы принимают одинаковые значения. Запись функции: Y = A$\leftrightarrow$B. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y₉.

Обозначение на схеме:

• Элемент «Исключающее ИЛИ-НЕ»
• 
• 

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

Функция «Исключающее ИЛИ-НЕ»
	A	B	Y = A$\leftrightarrow$B
1e-06	0	0	1
2e-06	0	1	0
3e-06	1	0	0
4e-06	1	1	1

Импликация. Логическое следование «B» из посылки «A».

Логический элемент, реализующий функцию логического следования «Если A, то B». Функция принимает значение «0» в том и только в том случае, когда из истинной посылки «А» следует ложное следствие «В». Запись функции: Y = A$\rightarrow$B. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y₁₃.

Обозначение на схеме:

• Элемент «Прямая импликация»
• 
• 

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

Функция «Прямая импликация»
	A	B	Y=A$\rightarrow$B
1e-06	0	0	1
2e-06	0	1	1
3e-06	1	0	0
4e-06	1	1	1

Функционально полные наборы. Правила де Моргана

В булевой алгебре существуют наборы логических операций (функций), посредством которых можно выразить любые другие логические операции. Такие наборы логических операций (функций) носят название функционально полных наборов (ФПН):

• набор операций «И», «ИЛИ», «НЕ»;

• набор операций «И», «НЕ»;
• набор операций «ИЛИ», «НЕ»;
• операция «И-НЕ»;
• операция «ИЛИ-НЕ».

Для преобразования любого набора логических операций (функций) в один из ФПН используются законы (правила) де Моргана — это логические правила, связывающие пары логических операций при помощи функции логического отрицания. Звучат они так:

— отрицание конъюнкции тождественно дизъюнкции отрицаний: НЕ (A$\land$B) $\equiv$ (НЕ А)$\lor$(НЕ В);

— отрицание дизъюнкции тождественно конъюнкции отрицаний: НЕ (A$\lor$B) $\equiv$ (НЕ А)$\land$(НЕ В).

Примеры схемной реализации логических элементов

Диодно-транзисторная логика (ДТЛ)

ДТЛ. Схема, реализующая логическую функцию 2И-НЕ

Приведём пример построения логического элемента на базе диодно-транзисторной схемы, составленной из входной линейки диодов VD1, VD2, на катоды которых приходят сигналы либо высокого уровня (логическая «1»), либо низкого уровня (логический «0»), и транзисторного ключа.

Если хотя бы на один из входов Inp1, Inp2 или на оба сразу приходит логический «0», то на базу транзистора подается низкий уровень. Транзистор закрыт. На выходе Out появляется высокий уровень, то есть логическая «1».

Если на оба входа Inp1, Inp2 подаются сигналы высокого уровня, транзистор открыт и на выходе Out появляется низкий уровень, то есть логический «0». Таким образом мы видим, что схема реализует логическую функцию «И-НЕ». На практике, если входных сигналов несколько, к названию функции добавляется количество входов. Соответственно, этот логический элемент носит название 2И-НЕ.

Транзисторно-транзисторная логика (ТТЛ)

ТТЛ. Схема, реализующая логическую функцию 2И-НЕ

Схема ТТЛ выполнена в варианте интегральной микросхемы и реализует ту же функцию 2И-НЕ, только в качестве входного элемента работает многоэмиттерный транзистор, объединяющий функции входных диодов и повторителя сигнала.

При подаче на любой из эмиттеров или на оба эмиттера транзистора VT1 сигналов низкого уровня (логический «0») транзистор VT1 открывается, на его коллекторе и, соответственно, на базе VT2 появляется низкий уровень. Транзисторный ключ VT2 инвертирует сигнал, на его выходе появляется высокий уровень (логическая «1»).

При подаче на оба эмиттера VT1 сигналов высокого уровня (логическая «1») картина обратная, то есть транзистор VT1 закрыт, высокий потенциал на его выходе открывает транзистор VT2, на выходе которого появляется низкий уровень (логический «0»).

Программная реализация логических функций

Управляющие логические цепи

Языки программирования, используемые для программирования логических контроллеров (ПЛК), наряду с возможностью реализации математических операций дополнительно дают возможность программного построения управляющих логических цепей с использованием битовых переменных, принимающих только два значения: «логический 0» или «логическая 1», то есть логические функции можно реализовывать программным путём. Ниже приведены примеры, в которых показано, как это выглядит в языках программирования ПЛК.

Язык LD (Ladder Diagram) — графический язык, основанный на принципах релейно-контактных схем

• 

  Функция «И» (Y₀ = X₀$\land$X₁)

• 

  Функция «ИЛИ» (Y₀ =X₀$\lor$X₁)

Язык STL (Statement List) — язык списка инструкций. Примеры написаны с использованием синтаксиса и команд языка STL Simatic Step 7.

Функция «И»

A  X1 //загрузка битовой переменной Х1
A  X2 //загрузка битовой переменной X2, выполнение операции AND (Функция «И»)
=  Y0 //присвоение результата переменной Y0

Функция «ИЛИ»

A  X1 //загрузка битовой переменной Х1
O  X2 //загрузка битовой переменной X2, выполнение операции OR (Функция «ИЛИ»)
=  Y0 //присвоение результата переменной Y0

Реализация переменной «Константа 0»

A  X1 //загрузка битовой переменной Х1
AN X1 //загрузка битовой переменной  НЕ X1, выполнение операции AND (Функция «И»)
=  Y0 //присвоение результата переменной Y0

Реализация переменной «Константа 1»

A  X1 //загрузка битовой переменной Х1
ON X1 //загрузка битовой переменной  НЕ X1, выполнение операции OR (Функция «ИЛИ»)
=  Y0 //присвоение результата переменной Y0

Функция «Исключающее ИЛИ»

A   X1 //загрузка битовой переменной Х1
XOR X2 //загрузка битовой переменной X2, выполнение операции XOR (Функция «Исключающее ИЛИ»)
=   Y0 //присвоение результата переменной Y0

Реализация функции «Исключающее ИЛИ» с помощью ФПН «И», «ИЛИ», «НЕ»

(
A  X1 //загрузка битовой переменной Х1
AN X2 //загрузка битовой переменной НЕ X2, выполнение операции AND (Функция «И»)
)
O     //выставление флага операции «ИЛИ» для логического сопряжения предыдущей операции «И» с последующей
(
AN X1 //загрузка битовой переменной НЕ X1
A  X2 //загрузка битовой переменной X2, выполнение операции AND (Функция «И»)
)
=  Y0 //присвоение окончательного результата Y=(Х1∧⌝Х2)∨(⌝Х1∧Х2) переменной Y0

Примеры логических операций в машинных словах

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

Пример поразрядного логического умножения («И») в двух восьмиразрядных словах (байтах):

Поразрядное логическое умножение в двух байтах
1e-06	Byte 1	0	1	1	0	1	1	1	0
2e-06	Byte 2	1	0	1	0	0	1	1	1
3e-06	Result	0	0	1	0	0	1	1	0

Видно, что в слове Result, куда помещён результат операции, единичные значения присутствуют только в тех разрядах, в которых совпали единицы в исходных словах Byte 1 и Byte 2.

Примечания

Данная статья имеет статус «готовой». Это не говорит о качестве статьи, однако в ней уже в достаточной степени раскрыта основная тема. Если вы хотите улучшить статью — правьте смело!