Глава 1. Логические основы цифровой техники

1.1. Логические функции

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

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

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

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

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

1.1.2. Логические (Булевы) функции

Рассмотрим функции одной переменной y = f(x). Пронумеруем эти функции (их четыре) и расположим в виде таблицы:

х	f0	f1	f2	f3
0	0	0	1	1
1	0	1	0	1

Видно, что f₀(х) = 0, a f₃(х) = 1, т.е. эти две функции не зависят от х, f₁(х) = х, т.е. она не меняет аргумента. Функция f₂(х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается и называется отрицанием.

Рассмотрим функции двух переменных y = f(x₁, x₂).

Число этих функций равно 2⁴ = 16. Пронумеруем и расположим их в естественном порядке.

x1	x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Рассмотрим более подробно эти функции. Две из них f₀ = 0 и f₁₅ = 1 являются константами. Функции

, ,,

являются по существу функциями одной переменной.

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

Перечислим семь важнейших функций.

1. Конъюнкция (функция И)

.

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

Конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают x₁ & x₂ или x₁x₂.

2. Дизъюнкция (функция ИЛИ)

.

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

3. Импликация (следование)

.

Иногда импликацию обозначают x₁ כ х₂ или x₁ → х₂ (читается “из x₁ следует х₂”).

Это очень важная функция, особенно в логике. Ее можно рассматривать следующим образом: если x₁ = 0 (т. е. x₁ “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если х₂ = 1 (т.е. х₂ “истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным. Заметим, что любая теорема всегда фактически содержит эту логическую функцию.

4. Сложение по модулю 2, Исключающее ИЛИ (здесь и далее, если не оговорено противное, знаком “+” мы будем обозначать такое сложение):

.

5. Эквивалентность или подобие ~

.

Эта f₉ = 1 тогда и только тогда, когда х₁ = х₂.

6. Штрих Шеффера

.

Иногда эту функцию называют “НЕ И” (так как она равна отрицанию конъюнкции).

7. Стрелка Пирса (иногда эту функцию называют штрих Лукасевича)

.

Эта функция является отрицанием дизъюнкции, и поэтому иногда ее называют “не ИЛИ”.

Заметим, что свойства последних двух функций похожи между собой и, может быть, поэтому в литературе их часто путают (т. е. называют f₈ штрихом Шеффера, а f₁₄ – стрелкой Пирса).

Три оставшиеся функции, (f₂ , f₄ и f₁₁) особого значения в дискретной математике не имеют.

Операцию отрицания называют инверсией или дополнением. Для ее обозначения используют черту над соответствующим выражением. Операция определяется следующими постулатами:

если х = 1, то = 0, еслих = 0, то = 1.

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

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

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20.

21. ;

22. ;

23.

Справедливость всех перечисленных теорем может быть до-казана непосредственной подстановкой.