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

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

В цифровой технике для тех же целей пользуются кодовыми словами. Особенность этих слов заключается в том, что все они имеют чаще всего одинаковую длину (т.е. состоят из одного и того же количества букв), и для их построения используется простейший алфавит из двух букв. Эти буквы принято обозначать символами 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, будем эти функции называть функциями алгебры логики. Устройства, предназначенные для формирования функций алгебры логики, называются логическими устройствами или цифровыми устройствами.

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

Рассмотрим функции одной переменной 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	f 4	f 5	f 6	f 7	f 8	f 9	f 10	f 11	f1 2	f 13	f 14	f 15
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.

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

 

1.1.3. Способы задания логических функций

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

Проиллюстрируем словесное описание функции алгебры логики на примере.

Логическая функция трех переменных равна 1, если хотя бы две входные переменные равны 1.

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

Таблица, содержащая все возможные комбинации входных переменных x_n-1 …x₁x₀ и соответствующие им значения выходных переменных y _i, называется таблицей истинности или комбинационной таблицей. В общем случае таблица истинности содержит 2ⁿ строк и m+n столбцов, где n – количество входных сигналов, а m – выходных.

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

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

ДНФ может быть получена из таблицы истинности с использованием следующего алгоритма:

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

б) логически суммируют все конституенты единицы.

ДНФ, полученную суммированием конституент единицы, называют совершенной (СДНФ).

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

КНФ может быть получена из таблицы истинности с использованием следующего алгоритма:

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

б) логически перемножают все полученные конституенты нуля.

КНФ, полученную суммированием конституент нуля, также называют совершенной (СКНФ).

Пример 1.1. Запишите дизъюнктивную и конъюнктивную нормальные формы для следующей таблицы истинности:

x2	x 1	x 0	y
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Решение. Согласно приведенному выше алгоритму дизъюнктивная нормальная форма примет вид

,          (1.1)

а конъюнктивная нормальная форма определится как

.      (1.2)

Иногда удобнее применять не саму функцию алгебры логики, а ее инверсию. В этом случае при использовании вышеописанных методик для записи СДНФ необходимо выбирать нулевые, а для записи СКНФ – единичные значения функции.

 

Логические элементы

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

В соответствии с перечнем логических операций различают три основных логических элемента: И, ИЛИ, НЕ. Условные графические обозначения этих логических элементов показаны на рис. 1.1.

 

Рис. 1.1. Условные графические обозначения основных (а)

и совмещающих в себе две функции (б) логических элементов

Число входов логических элементов И или ИЛИ может быть произвольным. Элемент НЕ всегда имеет только один вход.

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

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

Решение приведено на рис. 1.2

 

Рис. 1.2. Пример структурной схемы логического устройства

 

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