Основы анализа и синтеза комбинационных логических устройств (стр. 3 из 14)
Пример 1.2. Представить в СДНФ логическую функцию пяти аргументов f(x1,x2,x3,x4,x5), равную единице на следующих четырех наборах
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Решение. 1. Запишем четыре произведения аргументов, связанных знаком дизъюнкции, и под каждым из них - один из перечисленных наборов
| x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5 |
| 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 |
2. Расставляя отрицания над аргументами, равными нулю, получим СДНФ логической функции:
Ú 
Ú 
Ú 
СКНФ находят по правилу записи переключательной функции “по нулям”:
1) выписывают произведения дизъюнкций всех аргументов с количеством сомножителей, равным числу наборов, на которых заданная функция обращается в нуль;
2) записывают под каждым сомножителем набор аргументов, на котором функция равна нулю, а над аргументами, равными единице ставят знаки отрицания.
Пример 1.3. Представить в СКНФ переключательную функцию четырех аргументов f(x1,x2,x3,x4), равную нулю на наборах
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Решение. 1. Запишем четыре произведения дизъюнкций всех аргументов и под каждым из них один из перечисленных наборов:
| (x1Úx2Úx3Úx4) × (x1Úx2Úx3Úx4) × (x1Úx2Úx3Úx4) × (x1Úx2Úx3Úx4) |
| 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 |
2. Расставляя знаки отрицания над аргументами, равными единице, получим СКНФ логической функции:
При выборе совершенной формы записи логической функции следует иметь в виду, что СДНФ является более целесообразной, если число наборов, на которых функция равна 0, превышает число наборов, на которых функция равна 1. В противоположном случае более приемлемой будет СКНФ.
Пример 1.4. Необходимо построить мажоритарную ячейку (ячейку голосования) на три входа, т.е. такую ячейку, у которой сигнал на выходе равен единице тогда, когда большинство входных сигналов равно единице, т.е. он равен единице, когда на двух или трех входах присутствует сигнал единицы, в противном случае выходной сигнал равен нулю [2].
Представить логическую функцию мажоритарной ячейки в виде таблицы истинности и в алгебраическом виде в формах СДНФ и СКНФ.
Решение. 1. Для трех входных сигналов, т.е. для n=3 переменных существует q=2n=23=8 различных комбинаций этих сигналов табл.1.4.
Таблица 1.4
Таблица истинности
| x1 | x2 | x3 | f |
| 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 |
2. Для представления логической функции в алгебраическом виде в форме СДНФ нужно представить эту функцию в виде суммы логических произведений аргументов, соответствующих тем строкам таблицы истинности, для которых логическая функция равна единице. При записи этих логических произведений следует брать соответствующий аргумент с инверсией, если этот аргумент в данной строке таблицы равен нулю, и без инверсии, если он равен единице:
3. Для представления логической функции в алгебраическом виде в форме СКНФ нужно представить эту функцию в виде произведения логических сумм аргументов, соответствующих тем строкам таблицы истинности, для которых логическая функция равна нулю. При записи этих логических сумм следует брать соответствующий аргумент с инверсией, если этот аргумент в данной строке таблицы равен единице, и без инверсии, если он равен нулю:
Пример 1.5. Полный набор
= 16 логических функций двух переменных приведен в табл.1.5. Записать алгебраические выражения этих функций в формах СДНФ и СКНФ.Таблица 1.5
Полный набор логических функций двух переменных
| Таблица истинности | Название функции | Условноеобозначение | Алгебраическое выражение | ||||||
| Функция | x1 | 0 | 0 | 1 | 1 | ||||
| x2 | 0 | 1 | 0 | 1 | СДНФ | СКНФ | |||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| f0 | 0 | 0 | 0 | 0 | Константа нуль | 0 | |||
| f1 | 0 | 0 | 0 | 1 | Конъюнкция | x1 x2 | |||
| f2 | 0 | 0 | 1 | 0 | Запрет по x2 | x1  x2x1  x2 | |||
| f3 | 0 | 0 | 1 | 1 | Тождественность x1 | x1 | |||
| f4 | 0 | 1 | 0 | 0 | Запрет по x1 | x2 x1x2 x1 | |||
| f5 | 0 | 1 | 0 | 1 | Тождественность x2 | x2 | |||
| f6 | 0 | 1 | 1 | 0 | Исключающее ИЛИ Сумма по модулю 2 | x1  x2 | |||
| f7 | 0 | 1 | 1 | 1 | Дизъюнкция | x1Ú x2x1 + x2 | |||
| f8 | 1 | 0 | 0 | 0 | Стрелка Пирса | x1¯ x2 | |||
| f9 | 1 | 0 | 0 | 1 | Равнозначность | x1~ x2 | |||
| f10 | 1 | 0 | 1 | 0 | Инверсия x2 |  | |||
| f11 | 1 | 0 | 1 | 1 | Импликация от x2 к x1 | x2® x1 | |||
| f12 | 1 | 1 | 0 | 0 | Инверсия x1 |  | |||
| f13 | 1 | 1 | 0 | 1 | Импликация от x1 к x2 | x1® x2 | |||
| f14 | 1 | 1 | 1 | 0 | Штрих Шеффера | x1 / x2 | |||
| f15 | 1 | 1 | 1 | 1 | Константа единицы | 1 | |||
1.1.2 Графическое представление логической функции в виде Карты Карно (диаграммы Вейча)
Логическая функция может быть представлена графически в виде карт минтермов - карт Карно.
Логическую функцию предварительно, исходя из таблицы истинности, приводят к совершенной дизъюнктивной нормальной форме (СДНФ):
,Где fi, mi - значение функции (0 или 1) и минтерм, соответствующий i-ому набору переменных.
Минтерм - конъюнкция переменных, которые входят либо в прямом виде, если значение данной переменной в наборе равно 1, либо в инверсном виде, если значение переменной равно 0.
Минтерм - это простая конъюнкция, в которую входят все аргументы рассматриваемой логической функции [3].
Простой конъюнкцией считается логическое произведение переменных, взятых с отрицаниями или без них, в котором каждая переменная встречается не более одного раза (в простую конъюнкцию не должны входить суммы переменных, отрицания функций двух или нескольких переменных).
После представления функции в СДНФ, следует заполнить прямоугольную таблицу, в которой число клеток равно числу возможных минтермов. Эту таблицу называют диаграммой Вейча или картой Карно. Каждой клетке таблицы ставится в соответствие определенная конъюнкция так, чтобы в соседних клетках (снизу и сверху, слева и справа) конъюнкции отличались не более чем одним сомножителем. Для этого нумерацию столбцов и строк таблицы ведут кодом Грея, количество разрядов которого равно количеству переменных, отведенных для строк и столбцов.
При заполнении таблицы в соответствующую клетку ставится 1, если логическая функция при данном наборе аргументов равна единице(рис.1.1-1.4).
| x1x2 | 0 | 1 |
| 0 |  |  |
| 1 |  |  |
Рис.1.1 Карта Карно для логической функции двух аргументов.