Представление логических функций

Наиболее наглядно, но и наиболее громоздко, логическая функция представляется таблицей соответствия, где каждому набору аргументов ставится в соответствие значение функции (см. табл.4.2). От таблицы соответствия легко перейти к алгебраической форме записи (логической формуле).

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

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

 

		Таблица 4.2
Таблица соответствия	Наборы	Наборы
a	b	с	d	Y	переменных ДНФ	переменных КНФ

 

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

 

ПРИМЕР 1: Получение ДНФ и КНФ по таблице соответствия

Логическая функция задана в виде таблицы соответствия (табл.4.2). Карта Карно, соответствующая табл.4.2 приведена на рис.4.1.

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

 

 

Рис.4.1. Пример заполнения Карты Карно (диаграммы Вейча)

 

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

(4.1)

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

(4.2)

 

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

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

4.2.3.1. Для получения ДНФ (КНФ) все единицы (нули) объединяются в прямоугольные контуры, не содержащие внутри нулей (единиц), с числом клеток в контуре , где n = 0, 1, 2, 3,...

4.2.3.2. Контур проводится через соседние клетки, т.е. клетки, отличающие значением только одной переменной.

4.2.3.3. Контуры могут частично накладываться друг на друга и должны иметь максимальные возможные размеры.

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

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

4.2.3.6. ДНФ получается в виде суммы значений всех единичных контуров.

4.2.3.7. КНФ получается в виде произведения значений всех нулевых контуров.

Таблица 4.3

Законы (правила преобразования) алгебры логики

Логические формулы	Закон
a b = b a; a + b = b + a	Переместительный
( a + b ) c = a c + b c	Распределительный
( a + c ) ( b + c ) = a b + c	Распределительный
a.a = a; a + a = a	Повторения
a .1 = a; a + 1 = 1	Множества
	Дополнения
	де Моргана
	де Моргана
	Склеивания

 

ПРИМЕР 2: Минимизировать карту Карно, приведенную на рис.4.2.

 

Рис.4.2 Карта Карно с единичными и нулевыми контурами

Анализ единичных контуров дает следующее выражение для ДНФ

(4.3)

/ \

контур 1 контур 2

Анализ нулевых контуров дает следующее выражение для КНФ

(4.4)

/ \

контур 3 контур 4

 

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

Поделиться:

Популярное:

1. F. Переживание мифологических и сказочных сюжетов
2. VI.2. Представление отдельных видов текстового материала
3. А также на геологических картах и вертикальных разрезах
4. А4 Какой показатель даёт владельцу коммерческого предприятия представление об эффективности его работы?
5. Автоматизация строительных машин и технологических процессов в строительстве
6. Алгоритм формально-логических показателей правописания наречий, наречных сочетаний и сочетаний предлога с существительным
7. Алгоритмы записи произвольной функции, заданной в таблице в виде с помощью элементарных функций.
8. Алогизм – непредсказуемое совмещение понятий; сознательное нарушение логических связей в художественном произведении.
9. Анатомо-морфологическая база высших психических функций.
10. В.В. Виноградов. ОБ ОСНОВНЫХ ТИПАХ ФРАЗЕОЛОГИЧЕСКИХ ЕДИНИЦ В РУССКОМ ЯЗЫКЕ. (Виноградов В.В. Лексикология и лексикография: Избранные труды. М., 1977)
11. Взаимосвязь общих и конкретных функций менеджмента
12. Виды технологических процессов