Формы представления логических функций

Существуют следующие формы задания логических функций [2]:

– словесная;

– таблицей истинности;

– аналитическим способом;

– числовым способом.

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

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

Таблица 1.4

Табличный способ представления логической функции

№ набора	Аргументы			Функция
0	0	0	0	0
1	0	0	1	0
2	0	1	0	0
3	0	1	1	1
4	1	0	0	0
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

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

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

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

Рассмотрим функцию, представленную таблицей 1.1. Она равна единице на наборах переменных с номерами 3, 5, 6, 7, а на остальных наборах равна нулю. Отсюда формулировка записи этой функции по единичным значениям может быть представлена так:

.                                   (1.17)

Такая конъюнкция, включающая в себя полный набор переменных, на котором функция равна единице, называется конституентой единицы (минтермом), а запись функции в виде суммы конституент единицы (т.е. дизъюнкция конституент единицы) называется совершенной дизъюнктивной нормальной формой (СДНФ).

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

.                                   (1.18)

Используя закон Де Моргана, выражение (1.18) можно переписать в виде

;

. (1.19)

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

.                                                       (1.20)

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

1. И, ИЛИ, НЕ;

2. И–НЕ;

3. ИЛИ–НЕ.

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

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

Наиболее широкое распространение в силу своей простоты и наглядности получили способы, использующие карты Карно или Вейча. Эти карты представляют собой таблицы истинности, преобразованные таким образом, что у функции, нанесенной на такую карту, соседние конъюнкции находятся либо рядом, либо на заранее известных местах [2, 5, 6, 9].

Карты Карно для двух, трех, четырех и пяти переменных приведены на рис. 1.1.

Рис. 1.1. Карты Карно для двух, трех и четырех и пяти переменных

Для поиска соседних конъюнкций на карту Карно необходимо сначала нанести функцию, т.е. поставить на местах десятичных номеров той или иной карты значения логической функции на этих номерах наборов. Например, для функции, приведенной в таблице 1.4, выбираем карту Карно для трех переменных и на местах наборов 3, 5, 6, 7 ставим единицы, а на остальных нули (рис. 1.2).

Рис. 1.2. Минимизация с помощью карты Карно функции (1.17)

Порядок операций при минимизации функций при помощи карт Карно:

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

2. Выполняются накрытия всех единичных (или всех нулевых) значений функции минимальным числом максимальных по площади правильных прямоугольников. Площадь прямоугольников подчиняется закону , т.е. допустимое число клеток равно 1, 2, 4, 8 и т.д. Чем больше площадь накрытия, тем меньше переменных входит в результат, а чем меньше число накрытий, тем меньше конъюнкций будет в результате.

3. Записывается результат в виде логической суммы конъюнкций, составляющих каждое отдельное накрытие. Каждый член МДНФ (минимальная дизъюнктивная нормальная форма) составляется лишь из тех аргументов, которые для клеток соответствующей области имеют одинаковое значение (с инверсией либо без инверсии).

Для получения МКНФ функции замкнутыми областями охватываются клетки с нулевыми значениями функции, и при записи членов логического выражения берутся инверсии аргументов, на пересечении которых находятся области. Так, для функции, приведенной в таблице 1.4, МКНФ

.                                              (1.21)

Пример 1.1. Используя карты Карно, минимизировать функцию четырех переменных

.                                  (1.22)

Результат минимизации приведен на рис. 1.3.

Рис. 1.3. Минимизация с помощью карты Карно функции (1.22)

Пример 1.2. Записать полученную в примере 1.1 МДНФ в базисах И–НЕ и ИЛИ–НЕ.

Для синтеза в базисе И–НЕ дважды инвертируем правую часть МДНФ

.                            (1.23)

Проводим преобразование по формуле Де Моргана:

.                        (1.24)

Записываем выражение с использованием символа операции И–НЕ:

.           (1.25)

Выражению (1.25) соответствует схема, приведенная на рис. 1.4.

Рис. 1.4. Структурная схема функции, заданной выражением (1.25)

Для синтеза в базисе ИЛИ–НЕ запишем инверсную МДНФ функции (1.22) (рис. 1.5).

Рис. 1.5. Получение инверсной МДНФ функции (1.22)

Дважды инвертируем каждую конъюнкцию и преобразуем их в инверсии дизъюнкций входных переменных с помощью правила Де Моргана 

.                                      (1.26)

Записываем выражение (1.26) в базисе ИЛИ–НЕ

.       (1.27)

Пример 2.3. С помощью карт Карно минимизировать не полностью определенную функцию, заданную таблицей истинности 1.5.

Таблица 1.5

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

	0	0	0	0	1	1	1	1
	0	0	1	1	0	0	1	1
	0	1	0	1	0	1	0	1
	*	0	1	*	1	*	*	1

Составляем карту Карно для не полностью определенной функции трех переменных (рис.1.6).

Рис. 1.6. Минимизация с помощью карты Карно не полностью определенной функции

⇐ Предыдущая123456789Следующая ⇒

Поделиться: