Переход от табличного представления к аналитическому

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

Тема 2.3 Минимизация логических функций

Содержание: Переход от табличного представления к аналитическому. Совершенная дизъюнктивная и конъюнктивная нормальные формы представления функций. Минимизация логических функций с использованием законов и тождеств. Карты Вейча, Карно для двух, трёх, четырёх переменных.

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

Синтез логических комбинационных схем распадается на этапы:

- задание логической функции ЛФ в словесной, табличной или иной форме;

- представление её в виде логического выражения в некотором базисе (И-НЕ, ИЛИ-НЕ);

- минимизация ЛФ, обеспечивающая при синтезе минимальные аппаратные затраты;

- составление логической схемы по логической функции в заданном базисе.

Приняты две канонические формы представления ЛФ: СДНФ и СКНФ.

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

Запись ЛФ в СДНФ называют записью по единицам функции.

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

Запись ЛФ в СКНФ называют записью по нулям функции.

Для исходной функции заданной в форме таблицы, СДНФ имеет вид:

Для записи СДНФ ЛФ, заданной таблицей истинности, необходимо:

1. записать простые конъюнкции аргументов (если в таблице 1, то аргумент записывается без инверсии, если 0 – то с инверсией) для значений ЛФ, равных 1.

2. Составить логическую сумму простых конъюнкций.

Форма записи СДНФ– нормальная, если в каждый член логической суммы

аргумент или его инверсия входят не более одного раза. Форма записи – совершенная, если каждый член логической суммы содержит все аргументы или их инверсии.

Любая ЛФ имеет единственную СДНФ.

Для исходной функции, заданной в форме таблицы, СКНФ имеет вид:

( ) ( ) ( )

Для записи СКНФ ЛФ, заданной таблицей истинности, необходимо:

1. записать простые дизъюнкции аргументов (если в таблице 1, то аргумент записывается с инверсией, если 0 – то без инверсии) для значений ЛФ, равных 0.

2. Составить логическое произведение простых дизъюнкций.

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

Любая ЛФ имеет единственную СКНФ.

Дата добавления: 2015-06-27