Логические основы вычислительной техники

3

ЛОГИЧЕСКИЕ ФУНКЦИИ

Понятие о логической функции и логическом устройстве

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

Если длина кодовых слов составляет n разрядов, то можно построить 2ⁿ различных комбинаций - кодовых слов. Например при n=3 можно построить 2³=8 слов: 000, 001, 011, 100, 101, 110, 111.

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

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

Цифровые устройства (либо их узлы) можно делить на типы по различным признакам.

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

На входы устройства последовательного действия символы кодовых слов поступают не одновременно, а последовательно, символ за символом (в так называемой последовательной форме). Пример такого устройства показан на рисунке 1.1,а.

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

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

В устройствах смешанного действия входные и выходные кодовые слова представляются в разных формах. Например, входные слова - в последовательной форме, выходные - в параллельной. Устройства смешанного действия могут использоваться для преобразования кодовых слов из одной формы представления в другую (из последовательной формы в параллельную и наоборот).

По способу функционирования логические устройства (и их схемы) делятся на два класса: комбинационные устройства (и соответственно комбинационные схемы) и последовательные устройства (последовательные схемы).

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

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

Рассмотрим примеры работы комбинационного и последовательного устройств.

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

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

Элементарные логические функции

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

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

Таблица истинности для одного аргумента приведена в таблице 1.1.

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

Функции одного аргумента (табл. 1.1) представляется следующими выражениями:

f₁(x)=0 (константа 0); f₂(x)=x; f₃(x)=x; f₄(x)=1(константа 1).

Устройства, реализующие функции f₁(x), f₂(x) и f₄(x), оказываются тривиальными. Как видно из рис.1.3, формирование функций f₁(x) требует разрыва между входом и выходом, формирование функции f₂(x) - соединения входа с выходом, формирование функции f₄(x) -подключения выхода к источнику сигнала лог.1. Таким образом, из всех функций одного аргумента практический интерес может представлять лишь функция f₃(x)=x (логическое НЕ).

Свойства конъюнкции, дизъюнкции и инверсии

Конъюнкция переменных x₁ и x₂ равна лог.1 в том случае, когда и x₁ и x₂ равны лог.1 (отсюда возникло название операции логическое И).

Дизъюнкция переменных x₁ и x₂ равна лог.1, если или x₁ или x₂ равна лог.1 (отсюда понятно возникновение названия операции: логическое ИЛИ).

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

В математике установлен определенный порядок выполнения операций в сложном выражении. Например, в выражении x₁+x₂·х₃ вначале выполняется операция умножения x₂·х₃ и затем операция сложения. Если требуется изменить этот порядок, используются скобки. Например, (x₁+x₂)·х₃. Здесь вначале выполняется операция в скобках.

Подобно этому и для сложного логического выражения установлен определенный порядок выполнения операций: вначале выполняются операции инверсии, затем операции конъюнкции и в последнюю очередь операции дизъюнкции. Например, запись логического выражения x₁Vx₂·x₃Vx₄·x₂ предполагает, что при вычислении выражения вначале выполняются операции инверсии x₃ и x₄, затем операции конъюнкции x₂·x₃ и x₄·x₂ и в последнюю очередь операции дизъюнкции. А если требуется нарушить это правило, используются скобки. Например, (x₁Vx₂) ·( x₃Vx₄). В этом случае вначале выполняются операции в скобках (а если одни скобки вложены в другие, то вначале выполняются операции в самых внутренних скобках).

Операции конъюнкции и дизъюнкции обладают рядом свойств:

сочетательный закон: x₁·(x₂·x₃) = (x₁·x₂)·x₃, x₁V(x₂Vx₃) = (x₁Vx₂)Vx₃;

переместительный закон: x₁·x₂ = x₂·x₁, x₁Vx₂ = x₂Vx₁;

распределительный закон: x₁·(x₂Vx₃) = x₁·x₂ V x₁·x₂ , x₁V(x₂·x₃) = (x₁Vx₂)·(x₁Vx₂).

Легко убедиться в справедливости следующих выражений:

Покажем справедливость так называемых формул де Моргана:

В выражении = x₁·x₂ левая часть обращается в 1 только в том случае, если x₁Vx₂ = 0, для чего необходимо x₁=0 и x₂=0. Правая часть выражения обращается в 1 только при x₁=1 и x₂=1, т.е. при x₁=0 и x₂=0. Таким образом, только набор x₁=0 и x₂=0 обращает в 1 и правую и левую части выражения; следовательно, при остальных наборах значений аргументов правая и левая части выражения будут равны 0, что и доказывает справедливость рассматриваемого равенства.

В выражении = x₁Vx₂ и правая и левая части обращаются в 0 при x₁=1 и x₂=1, при остальных наборах значений аргументов обе части выражения равны 1, что и доказывает справедливость данного равенства.

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

Выражение элементарных функций через операции И, ИЛИ, НЕ.

1. Операция запрета. x₁x₂ = x₁·x₂. (1.3)

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

2. Сумма по модулю 2. x₁ x₂ = x₁·x₂ V x₁·x₂ = (x₁Vx₂)·( x₁ V x₂). (1.4)

3. Функция Вебба (операция ИЛИ - НЕ). x₁ x₂ = (1.5)

4. Логическая равнозначность. x₁~x₂ = = x₁·x₂ V x₁·x₂ = (x₁Vx₂)·(x₁Vx₂) (1.6)

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

5. Импликация. x₁ x₂ = x₁ V x₂. (1.7)

6. Функция Шеффера (операция И - НЕ). x₁|x₂ =

Полные системы функций алгебры-логики.

Очевидно могут быть построены простейшие логические элементы, реализующие элементарные логические функции двух переменных f₀, ..., f₁₅. Сложные логические функции могут быть построены последовательным выполнением функциональных зависимотей, связывающих пары переменных. Например, функция f (x₁, x₂, x₃, x₄) = (((x₁·x₁) x₃|x₄) V x₁ может быть получена с помощью схемы на рис. 1.4.

рис. 1.4

Следовательно, имея элементы, осуществляющие элементарные операции f₀, ..., f₁₅ можно выполнить любую сложную логическую операцию. Такую систему можно назвать полной системой или базисом. Условие наличия 16 различных типов логических элементов, каждый из которых реализует одну из 16 элементарных функций f₀, ..., f₁₅, является достаточным для синтеза логических устройств любой сложности, но оно не является необходимым, т.е. при синтезе можно ограничиться меньшим набором элементарных функций, взятых из f₀, ..., f₁₅.

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

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

Как показано выше, с помощью логических операций конъюнкции (И), дизъюнкции (ИЛИ) и инверсии (НЕ) можно выразить любую другую из элементарных функций f₀, ..., f₁₅. Следовательно, эта совокупность логических функций образует базис. Это означает, что любая логическая функция, как бы сложна она не была, может быть представлена через логические операции И, ИЛИ, НЕ. Иначе, можно построить любое логическое устройство, имея лишь три типа логических элементов, выполняющих операции И, ИЛИ, НЕ.

Базис И, ИЛИ, НЕ не является минимальным. Из этой совокупности функций можно исключить функцию И, либо функцию ИЛИ и оставшийся набор функций будет удовлетворять свойствам базиса. Действительно, если исключить функцию И, то операцию И можно выразить через оставшиеся операции ИЛИ и НЕ. Чтобы показать это, дважды инвертируем конъюнкцию и применим затем правило де Моргана.

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

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

1. Базис образует функция Шеффера (И-НЕ). Действительно операции НЕ и И следующим образом можно выразить через операции И-НЕ:

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

2. Базис образует функция Вебба (ИЛИ-НЕ). Покажем, что операция НЕ и ИЛИ выражаются через операцию ИЛИ-НЕ.

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

3. Базис образуют функция запрета и константа единицы. Действительно,

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