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

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

Высказывание - это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет.

Таким образом по своей сути высказывания фактически являются двоичными объектами и поэтому часто истинному значению высказывания ставят в соответствие 1, а ложному - 0. Например, запись А = 1 означает, что высказывание А истинно.

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

Самой простой логической операцией является операция НЕ, по-другому ее часто называют отрицанием, дополнением или инверсией и обозначают NOT_X. Результат отрицания всегда противоположен значению аргумента. Логическая операция НЕ является унарной, т.е. имеет всего один операнд. В отличие от нее, операции И (AND) и ИЛИ (OR) являются бинарными, так как представляют собой результаты действий над двумя логическими величинами.

X	not X
0	1
1	0

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

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

X	Y	X and Y	X or Y	X xor Y
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

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

Логические основы ЭВМ

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

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

Вся информация в ЭВМ представляется в двоичной системе счисления. Поставим в соответствие входным сигналам отдельных устройств ЭВМ соответствующие значения х_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_i – i-й выход; m – число выходов в устройстве,

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

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

N=2²ⁿ. (2.3)

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

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

Таблица 2.4

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

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

Этим функциям соответствуют определенные технические аналоги. Схема, реализующая зависимость у₂=х, называется повторителем, а схема y₃=х - инвертором.

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

Таблица 2.5

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

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

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

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

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

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

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

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

Она называется "отрицание конъюнкции” или " штрих Шеффера”. Функция к называется логической равнозначностью, она принимает значение единицы, если все ее переменные имеют одинаковое значение (или 0 или 1):

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

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

Из перечисленных функций двух переменных можно строить сколь угодно сложные зависимости, отражающие алгоритмы преобразования информации, представленной в двоичной системе счисления. Алгебра логики устанавливает правила [6] формирования логически полного базиса простейших функций, из которых могут строиться любые более сложные. Наиболее привычным базисом является набор трех функций {инверсия - é , дизъюнкция - v, конъюнкция - Λ или &}. Работа с функциями, представленными в этом базисе, очень похожа на использование операций обычной алгебры.

Алгебра логики устанавливает, что существуют и другие комбинации простейших логических функций, обладающих свойством логической полноты. Например, наборы логических функций {инверсия, дизъюнкция} и {инверсия, конъюнкция} также являются логически полными. Наиболее интересны минимальные базисы, включающие по одной операции {"отрицание дизъюнкции (ØÚ )”} и {"отрицание конъюнкции (ØÙ )”}. Однако работа с функциями, представленными в указанных базисах, требует от специалистов по проектированию ЭВМ определенных навыков.