Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

Двоичная логика

Материал из Циклопедии
(перенаправлено с «Булева логика»)
Перейти к навигации Перейти к поиску
Проблема вычисления значения двоичной функции // Irina Shoshmina [4:30]

Двоичная, двузначная, бинарная или булева логика — это формальная система, основанная на двух утверждениях: истина (логическая единица) и ложь (логический нуль). Из-за простоты реализации получила широкое распространение в вычислительной технике.

В вычислительной технике разделяют положительную (истина = 1, ложь = 0) и отрицательную (истина = 0, ложь = 1) логику.

В простейшей Булевой алгебре есть только два элемента, 0 и 1, и операции над ними.

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

Появление и применение алгебры логики[править]

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

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

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

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

Операции[править]

Нульарные[править]

Нульарные операции суть константы. В двоичной логике ими являются логический нуль (0) и логическая единица (1).

Унарные[править]

Инверсия (отрицание) — «¬», «НЕ», «НЕТ», f(1,1,01)2(x) = f(1,1,1)10(x)

X НЕ X
0 1
1 0

Бинарные[править]

Конъюнкция — «», «&», «И», f(2,1,8)10(x, y)

Дизъюнкция — «», "|", «ИЛИ», f(2,1,14)10(x, y).

X Y X И Y
0 0 0
1 0 0
0 1 0
1 1 1
X Y X ИЛИ Y
0 0 0
1 0 1
0 1 1
1 1 1

Двоичный полусумматор[править]

f(10,10,10000110)2(x, y) = f(2,2,134)10(x, y)

X Y S=X ⊕ Y=
f(2,1,06)10(x,y)
P=X&Y=
f(2,1,08)10(x,y)
0 0 0 0
1 0 1 0
0 1 1 0
1 1 0 1

S — бит суммы по модулю 2
P — бит переноса в n+1 разряд

Двоичный полувычитатель[править]

f(10,10,01000110)2(x, y) = f(2,2,70)10(x, y)

X Y R=X ⊕ Y=
f(2,1,06)10(x,y)
Z(N+1)=
f(2,1,04)10(x,y)
0 0 0 0
1 0 1 0
0 1 1 1
1 1 0 0

R — бит разности по модулю 2
Z — бит займа из n + 1 разряда

Тринарные[править]

f(11,01,10000000)2(x, y, z) = f(3,1,128)10(x, y, z) и
f(11,01,11111110)2(x, y, z) = f(3,1,254)10(x, y, z)

X Y Z X И Y И Z
0 0 0 0
1 0 0 0
0 1 0 0
1 1 0 0
0 0 1 0
1 0 1 0
0 1 1 0
1 1 1 1
X Y Z X ИЛИ Y ИЛИ Z
0 0 0 0
1 0 0 1
0 1 0 1
1 1 0 1
0 0 1 1
1 0 1 1
0 1 1 1
1 1 1 1

Двоичный сумматор[править]

f(11,10,1110100010010110)2(x, y, z) = f(3,2,59542)10(x, y, z)

X Y P(N-1) S=X ⊕ Y ⊕ Z=
f(3,1,150)10(x,y,z)
P(N+1)=
f(3,1,232)10(x,y,z)
0 0 0 0 0
1 0 0 1 0
0 1 0 1 0
1 1 0 0 1
0 0 1 1 0
1 0 1 0 1
0 1 1 0 1
1 1 1 1 1

Двоичный вычитатель[править]

f(11,10,110100010010110)2(x, y, z) = f(3,2,55446)10(x, y, z)

X Y Z(N−1) R=X ⊕ Y ⊕ Z=
f(3,1,150)10(x,y,z)
Z(N+1)=
f(3,1,216)10(x,y,z)
0 0 0 0 0
1 0 0 1 0
0 1 0 1 1
1 1 0 0 0
0 0 1 1 1
1 0 1 0 0
0 1 1 0 1
1 1 1 1 1

Z(N − 1) — бит займа в N − 1 разряд, второе вычитаемое
Z(N + 1) — бит займа из N + 1 разряда

Булевы функции[править]

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

Булевы функции от n переменных
X1 X2 Xn-1 Xn Ym = f (X1,X2,…,Xn-1,Xn)
0 0 0 0 Y0 = f (0,0,…,0,0)
0 0 0 1 Y1 = f (0,0,…,0,1)
0 0 1 0 Y2 = f (0,0,…,1,0)
0 0 1 1 Y3 = f (0,0,…,1,1)
1 1 1 0 Ym-1 = f (1,1,…,1,0)
1 1 1 1 Ym = f (1,1,…,1,1)
Функции одной переменной[править]

Наборы булевых функций для одной переменной[4], когда = 1, представлены в приведённой ниже таблице истинности. Количество функций согласно формуле m = составляет = 4. Обозначим их как Y0, Y1, Y2, Y3

Булевы функции от одной переменной
X Y0 Y1 Y2 Y3
0 0 0 1 1
1 0 1 0 1
  • Функция Y0 не зависит от значений переменной и носит название «константа ноль» (const 0);
  • Функция Y1 повторяет значения переменной и носит название «тождественная функция»;
  • Функция Y2 имеет значения, инверсные значениям переменной и носит название «функция НЕ» или «логическое отрицание»;
  • Функция Y3 не зависит от значений переменной и носит название «константа единица» (const 1);
Функции двух переменных[править]

Наборы булевых функций для двух переменных[4], когда =2, представлены в приведённой ниже таблице истинности. Количество функций согласно формуле = составляет = 16. Обозначим их как Y0, Y1, Y2,…, Y15

Булевы функции от двух переменных
X1 X2 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 Y10 Y11 Y12 Y13 Y14 Y15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

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

Например, номер функции Y1, равный 1 в десятичной системе счисления, в двоичной записывается как 0001. Соответственно Y2 имеет номер 210 = 00102, последняя функция Y15 имеет номер 1510 = 11112

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

Логические элементы[править]

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

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

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

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

Конъюнкция. Операция «И»[править]

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

Переменные Функция Обозначение на схеме
A B AB (AB)
0 0 0
0 1 0
1 0 0
1 1 1

Запись функции: Y = AB, Y = AB. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y1

Дизъюнкция. Операция «ИЛИ»[править]
A B AB
0 0 0
0 1 1
1 0 1
1 1 1

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

Запись функции: Y = AB, Y = AB. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y7.

Отрицание. Операция «НЕ»[править]
A Y
0 1
1 0

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

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

Отрицание конъюнкции. Операция «И-НЕ»[править]
A B AB
0 0 1
0 1 1
1 0 1
1 1 0

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

Запись функции: Y = AB. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y14.

Отрицание дизъюнкции. Операция «ИЛИ-НЕ»[править]
A B AB
0 0 1
0 1 0
1 0 0
1 1 0

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

Запись функции: Y = AB. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y8.

Сложение по модулю два. Операция «Исключающее ИЛИ»[править]
A B AB
0 0 0
0 1 1
1 0 1
1 1 0

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

Запись функции: Y = AB. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y6.

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

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

Запись функции: Y = AB. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y9.

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

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

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

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

De Morgans laws RU.svg


— отрицание конъюнкции тождественно дизъюнкции отрицаний: НЕ (AB) (НЕ А)(НЕ В);


— отрицание дизъюнкции тождественно конъюнкции отрицаний: НЕ (AB) (НЕ А)(НЕ В).

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

Диодно-транзисторная логика (ДТЛ)[править]
ДТЛ. Схема, реализующая логическую функцию 2И-НЕ

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

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

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

Транзисторно-транзисторная логика (ТТЛ)[править]
ТТЛ. Схема, реализующая логическую функцию 2И-НЕ

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

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

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


Программная реализация логических функций[править]

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

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

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

Язык STL (Statement List) — язык списка инструкций[9]. Примеры написаны с использованием синтаксиса и команд языка STL Simatic Step 7. <syntaxhighlight lang="c++"> A X1 //загрузка битовой переменной Х1 A X2 //загрузка битовой переменной X2, выполнение операции AND (Функция «И») = Y0 //присвоение результата переменной Y0 </syntaxhighlight><syntaxhighlight lang="c++"> A X1 //загрузка битовой переменной Х1 O X2 //загрузка битовой переменной X2, выполнение операции OR (Функция «ИЛИ») = Y0 //присвоение результата переменной Y0 </syntaxhighlight>

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

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

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

byte 1 0 1 1 0 1 1 1 0
byte 2 1 0 1 0 0 1 1 1
result 0 0 1 0 0 1 1 0

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

См. также[править]

Источники[править]

  1. Владимиров Д. А. Булевы алгебры. — М.: Наука, 1963. — 319 с.
  2. Гл. ред. Прохоров А. М. Высказывание // БСЭ в 30-ти томах. — М.: Советская энциклопедия, 1969—1986. — Vol. 5.
  3. Шеннон К. Работы по теории информации и кибернетике. — М.: Иностранная литература, 1963. — 832 с.
  4. 4,0 4,1 Математический форум Math Help Planet. Булевы функции от одного и двух аргументов..
  5. ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ И СХЕМЫ.
  6. Логические элементы. Диодно-транзисторная логика.
  7. Транзисторно-транзисторная логика (ТТЛ).
  8. Hans Berger Automating with Step 7 in LAD & FBD. — Weinheim, Germany: Wiley-VCH, 2001. — 348 с.
  9. STL для S7-300 и S7- 400 Программирование.