Основные сведения из алгебры логики

Теоретической основой построения ЭВМ являются специальные математические дисциплины. Одной из них является алгебра логики или булева алгебра (Дж. Буль – английский математик прошлого столетия, основоположник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их оптимизации и проектирования.

Так как вся информация в ЭВМ представляется в двоичной системе счисления, то поставим в соответствие входным сигналам отдельных устройств ЭВМ соответствующие значения х_i(i=1,…,n), а выходным сигналам - значения функций y_j(j=1,…,m) (рис.2.1).

Рис. 2.1. Представление схемы ЭВМ

В этом случае зависимостями

y_j=f(x₁,x₂,…,x_i,…,x_n), (2.2)

где x_i – i-й вход; n – число входов; y_j – j-й выход; m – число выходов в устройстве, можно описывать алгоритм работы любого устройства ЭВМ.

Каждая такая зависимость у_jпо стандарту ISO 2382/2-76 является булевой функцией, у которой число возможных состояний и каждой ее независимой переменной равно двум, т.е. функцией алгебры логики, а ее аргументы определены на множестве {0,1}. Алгебра логики устанавливает основные законы формирования и преобразования логических функций. Она позволяет представить любую сложную функцию в виде композиции простейших функций. Рассмотрим наиболее употребительные из них.

Известно, что количество всевозможных функций N от п аргументов выражается зависимостью

N=2²ⁿ. (2.3)

При n=0 в зависимости (2.3) можно определить две основные функции (N=2), не зависящие от каких-либо переменных: у₀, тождественно равную нулю (у₀=0), и у₁ , тождественно равную единице (у₁=1). Технической интерпретацией функции у₁=1 может быть генератор импульсов. При отсутствии входных сигналов на выходе этого устройства всегда имеются импульсы (единицы). Функция у₀=0может быть интерпретирована отключенной схемой, сигналы от которой не поступают ни к каким устройствам.

При п=1 в зависимости (2.3) дает N=4 т.е.получаем четыре различные функции от одной переменной. Представим зависимость значений этих функций от значения аргумента х в виде специальной таблицы истинности (табл. 2.4).

Таблица 2.4. Таблица функций от одной переменной

Yj	Y0	Y1	Y2	Y3
X

В этой таблице, как и ранее, у₀=0 и y₁=1. Функция y₂=х, а функция у₃= (инверсия x). Этим функциям соответствуют определенные технические аналоги. Схема, реализующая зависимость у₂=х, называется повторителем, а схема у₃= – инвертором.

При п=2, в зависимости (2.3) N=l6, т.е. можно построить шестнадцать различных функций от двух переменных,. В табл. 2.5 представлена часть из них, имеющая фундаментальное значение при построении основных схем ЭВМ.

Таблица 2.5.Таблица функций от двух переменных

Yj	Y0	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8	Y9	...
X1 X2
											...
											...
											...
											...

Представленные табл. 2.5 функции у₀-у₃, полностью соответствуют функциям табл. 2.4, а также приведены новые, часто используемые функции у₄-у₉.

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

Функция у₄представляет собой функцию логического сложения или дизъюнкцию. Она принимает значение единицы, если значение единицы имеет хотя бы одна переменная х₁ или х₂:

Функция y₅ является инверсной функцией по отношению к y₄:

Она имеет название «отрицание дизъюнкции». Иногда в литературе встречается ее специальное название «стрелка Пирса», по фамилии математика, исследовавшего ее свойства.

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

Функция y₇ является инверсной функцией по отношению к у₆:

Она называется «отрицание конъюнкции» или «штрих Шеффера».

Функция y₈ называется логической равнозначностью и принимает значение единицы, если все ее переменные имеют одинаковое значение (или 0 или 1):

Функция y₉ является инверсной по отношению к y₈:

Она принимает значение единицы, если ее переменные имеют противоположные значения.

Функции у₈ и у₉ являются основой для построения сумматоров, так как они соответствуют правилам формирования цифр двоичных чисел при сложении (вычитании).

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

Элемент И-НЕ

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

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

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

x2	x1	y

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

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

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

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

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

x2	x1	y

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

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