2. Логические устройства

Основные логические операции предложены английским математиком Дж. Булем в 1854 г для исследования процессов человеческих рассуждений и основаны на созданной ученым булевой алгебре. В алгебре логики используются два понятия “Да (Истина)” и “Нет (Ложь) ”.

Основные логические операции следующие:

“НЕ”(NOT)– операция инверсии (отрицания)

“И”(AND) – операция умножения (конъюнкции)

“ИЛИ”(OR) – операция сложения (дизъюнкции)

“И-НЕ”(NOT AND) – инверсия операции “И”

“ИЛИ-НЕ”(NOT OR) – инверсия операции “ИЛИ”

“ДА” – повторитель (буфер) y = x

Условные обозначения логических элементов и их таблицы

истинности (переключений) приведены ниже.

2.1. Основные правила алгебры логики

Алгебра логики определяется следующей системой аксиом:

(2.1)

(2.2)

(2.3)

(2.4)

(2.5)

Аксиома (2.1) утверждает, что в алгебре логики рассматриваются только двоичные переменные. Аксиомы (2.2…2.4) определяют операции дизъюнкции и конъюнкции, а аксиома (2.5) – операцию отрицания.

Если в аксиомах (2.2…2.4), заданных парами, произвести взаимную замену операций дизъюнкции и конъюнкции, а также элементов “0” и “1”, то из одной аксиомы пары можно получить другую. Это свойство называется принципом двойственности.

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

В ряде случаев метод перебора не очень трудоемок ввиду того, что переменные могут принимать только два значения: “0” и “1”. Методом перебора доказываются следующие теоремы:

1) идемпотентные законы:

(2.6)

2) коммутативные законы:

(2.7)

3) ассоциативные законы:

(2.8)

4) дистрибутивные законы:

(2.9)

5) законы отрицания:

(2.10)

5. законы нулевого множества

(2.11)

7) законы универсального множества

(2.12)

8) законы двойственности (теорема де Моргана):

(2.13)

9) закон двойного отрицания:

. (2.14)

Теоремы (2.6 …2.13) записаны парами, причем по принципу двойственности из одной теоремы можно получить другую взаимной заменой операций дизъюнкции и конъюнкции, а также элементов “0” и “1”. Теорема (2.14) самодвойственна, так как не изменяется по принципу двойственности. Теорему (2.14) используют для формального доказательства некоторых других теорем и тождеств, не прибегая к методу перебора. Следует отметить, что в этих теоремах вместо переменных x, y и z можно использовать логические выражения (функции), составленные из переменных с помощью операций алгебры логики. Как и в обычной алгебре, при преобразовании логических выражений должен соблюдаться определенный порядок выполнения операций (порядок старшинства): сначала отрицание, затем конъюнкция, и после этого дизъюнкция. Кроме того, в сложных логических выражениях порядок выполнения операций задается с помощью скобок.

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

1) законы поглощения

(2.15)

2) операции склеивания

(2.16)

3) операции обобщенного склеивания

(2.17)

(2.18)

Все тождества записаны парами на основании принципа двойственности.

Операция “штрих Шеффера” (операция И-НЕ) обозначается косой чертой и определяется соотношением:

.

Операция “стрелка Пирса” (операция ИЛИ-НЕ) обозначается символом и определяется соотношением:

. (2.19)

Операция “по модулю два” (исключающее ИЛИ, логическая неравнозначность) обозначается символом и определяется соотношением:

Для операции справедливы следующие тождества:

(2.20)

Отношение эквивалентности удовлетворяет следующим условиям:

а) x = x – рефлексивность

б) если x = y, то y = x – симметричность

в) если x = y, а y = z, то x = z – транзитивность.

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

Порядок размещения различных комбинаций значений входных переменных следует выбрать таким, чтобы при переходе от одной ячейки к соседней изменялась лишь одна переменная. В эти ячейки заносятся те значения выходной переменной Y, которые соответствуют значениям входных переменных. В качестве примера приведена таблица истинности 2.1 для функции И (табл.2.1) и соответствующая ей таблица Карно (табл.2.2)

Таблица 2.1 Таблица 2.2

X1	X2	0	1
0		0	0
1		0	1

X1	X2	Y
0	0	0
1	0	0
0	1	0
1	1	1

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

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

. (2.21)

Для ячейки, расположенной правее, следует записать:

. (2.22)

Когда, наконец, будет составлена логическая сумма всех произведений, помимо других, в ней встретится и такой фрагмент:

. (2.23)

Он упрощается следующим образом:

. (2.24)

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

Таблица 2.3 Таблица 2.4

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

, (2.25)

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

Для столбца D, состоящего из четырех ячеек, можно записать:

. (2.26)

Для контура C, имеющего квадратную форму и состоящего также из четырех элементов, получим следующее логическое произведение:

. (2.27)

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

. (2.28)

Для дизъюнктивной нормальной формы сразу найдем максимально упрощенный результат:

, (2.29)

. (2.30)

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