Базис ИЛИ-НЕ

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

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

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

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

Существует помимо перечисленных еще куча других элементов, рассматривать их будем по ходу дела. Эти элементы представляют собой комбинацию вышеперечисленных. Ну а напоследок рассмотрим элемент "ИСКЛЮЧАЮЩЕЕ-ИЛИ".

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

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

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

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

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

Минимизация логических функций необходима для упрощения сложных выражений этих самых функций, например, сложные логические функции могут отображаться в две-три и более строк (допустим, на листе формата А4). Понятно, что сразу приступать к схемной реализации таких функций по большому счету тупо. Минимизировать логические функции можно с помощью всяких правил и законов алгебры логики (про это здесь), можно с помощью так называемых карт Карно. Представление функций с помощью карт Карно очень удобно, когда число переменных невелико (меньше или равно 6). По сути карта Карно - это табличка, которая содержит 2ⁿ клеток, где n - число переменных (n=1, 2, 3 ... n). К каждой клетке содержится логическое произведение переменных или их инверсий. Одни перемнные располагаются по горизонтали, другие - по вертикали. Изображаться карты Карно могут по-разному. Например, так:

Или так:

Что касается первой таблички, первый знак (0 или 1) относится к первому символу (x₁ или x₃). Второй знак, соответственно, ко второму символу. Т. е., если в самой нижней правой ячейке стоит 1, то функция записывается x₂x₄. Во втором варианте вертикальные и горизонтальные черточки напротив ячеек означают, что переменная перекрывает эти ячейки, т. е. x₁ перекрывает две верхние стрроки, x₂ - два верхних столбца и т. п. И так, и так правильно, но лично мне более предпочтителен второй вариант.

Заполняются карты Карно следующим образом. Допустим есть некая функция из четырех переменных. Карта Карно будет содержать 16 клеток (2⁴ = 16). Функция вот такая:

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

Как это все делается? Посмотрите, вторая сверху слева ячейка, в ней стоит 1 и этой единице соответствует первое слагаемое в формуле. Единица стоит именно там, поскольку в этой ячейке перекрываются все переменные. Стоит уйти на ячейку влево, вправо, вверх, вниз и одна из переменных уже перекрывать ее не будет. Если одна из переменных с инверсией, что характерно для второго слагаемого, единица ставится с учетом не перекрытия ячейки этой переменной, т. е. для второго слагаемого x₁ с инверсией и единица стоит в третьей (сверху) строке третьего столбца. Для четвертого слагаемого с инверсией переменные x₂ и x₄. Поэтому единица стоит в последней строке (второй столбец). Так проставляются все единицы. В пустых ячейках по идее стоят нули (не показаны для наглядности). Подытожим, если пременная без инверсии, ей соответствует 1, если с инверсией - 0. Суть ясна?

После проставления всех единиц начинается объединение ячеек, в которых стоят эти самые единицы. Объединяются клетки по следующим правилам: число объединяемых клеток 2, 4, 8, 16, 32 и т. д., т. е. 2ⁿ, объединять надо как можно больше клеток, а самих объединений должно быть как можно меньше. На рисунке ниже показано, как это делается:

Для тех, кто не понял, единицы в количестве три, пять, шесть, семь, девять, десять и т. п. не объединяются. Если единицы стоят буквой "Т", "Г" и пр., то они также не объединяются.

После объединения ячеек составляется уравнение функции. Объединенные клетки условно считаются за одну, т. е. говоря простым языком, начинается обратный процесс составления карты Карно. Судя по рисунку, четырем объединенным единицам соответствует выражение x₃x₄. То есть, область объединения попадает в зону видимости всех переменных. Во втором объединении не участвует x₂, поэтому эта переменная будет с инверсией. Таким образом, после преобразования с помощью карты Карно была получена вот такая функция:

Вот так. Было 5 слагаемых, осталось 2. Такую функцию уже намного легче реализовать. Такая форма записи функции называется совершенной дизъюнктивной нормальной формой (СДНФ). Дизъюнктивная нормальная форма (ДНФ) - это такая форма представления функции, при которой логические выражения функции строятся в виде дизъюнктивного ряда членов, каждый из которых является простой конъюнкцией аргументов. На простом языке, ДНФ - это форма записи функции в виде логической суммы слагаемых, каждое из которых является логическим произведением переменных. Если в каждом члене ДНФ представлены все аргументы или их инверсии, такая форма записи называется совершенной (СДНФ). Существует также конъюнктивная нормальная форма (КНФ) - форма представления функции в виде конъюнкции (логического умножения) ряда членов, каждый из которых является простой дизъюнкцией (логическим сложением) аргументов. Если в каждом члене КНФ представлены все аргументы или их инверсии, то такая форма называется совершенной (СКНФ).

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

Рис. 1 - Дифференцирующая цепочка и форма напряжения на входе и выходе

Вот такое соединение резика и кондера называется дифференцирующей цепью или укорачивающей цепью. На графиках показаны эпюры напряжения на входе и выходе этой цепи. Допустим кондер разряжен. При подаче на вход RC-цепи ипмульса напряжения кондер сразу же начнет заряжаться током, проходящим через него самого и резик. Сначала ток будет максимальным, затем по мере увеличения заряда конденсатора постепенно уменьшится до нуля по экспоненте. Когда через резик проходит ток, на нем образуется падение напряжения, которое определяется, как U=i R, где i-ток заряда кондера. Поскольку ток изменяется экспоненциально, то и напряжение будет изменяться также - экспоненциально от максимума до нуля. Падение напряжения на резике как раз-таки и является выходным. Его величину можно определить по формуле U_вых = U₀e^-t/τ. Величина τ называется постоянной времени цепи и соответствует изменению выходного напряжения на 63% от исходного (e^-1 = 0.37). Очевидно, что время изменения выходного напряжения зависит от сопротивления резистора и емкости конденсатора и, соответственно, постоянная времени цепи пропорциональна этим значениям, т. е. τ = RC. Если емкость в Фарадах, сопротивление в Омах, то τ в секундах.

Если поменять местами резистор и конденсатор, как показано на рисунке 2, то получим интегрирующую цепь или удлиняющую цепь.

Рис. 2 Интегрирующая цепочка и формы напряжения на входе и выходе

Выходным напряжением в интегрирующей цепи является напряжение на кондере. Естесственно, если кондер разряжен, оно равно нулю. При подаче импульса напряжения на вход цепи кондер начнет накапливать заряд, и накопление будет происходить по экспоненциальному закону, соответственно, и напряжение на нем будет нарастать по экспоненте от нуля до своего максимального значения. Его значение можно определитиь по формуле U_вых = U₀(1 - e^-t/τ). Постоянная времени цепи определяется по такой же формуле, как и для дифференцирующей цепи и имеет тот же смысл.

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

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

Поскольку в цифровых устройствах используются только два символа 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 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

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

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

Схема "И"

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

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

Схема "ИЛИ"

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

Его таблица истинности:

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

Схема "НЕ"

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

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

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

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