Метод карт Карно.

Упражнение № 2

Методические указания

Калуга 2014

Упражнение №2

Преобразование логических функций.

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

Задание: изучить теоретические сведения, выполнить все задания упражнения и продемонстрировать преподавателю, оформить результаты выполнения в виде отчёта.

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

Теоретические сведения.

Метод карт Карно.

Пусть логическая функция задана таблицей истинности:

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

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

Для того чтобы найти СДНФ, отметим строки таблицы, в которых . Рассмотрим значения переменных, при которых функция принимает единичное значение. Если значение переменной равно 0, то она записывается в СДНФ с инверсией, если 1 – то без инверсии.

Пользуясь данным правилом, найдём СДНФ, используя таблицу истинности представленную выше:

Здесь для краткости записи операция конъюнкции (логическое И, логическое умножение, &) используется символ ”·”, который опущен. Операция дизъюнкции (логическое ИЛИ) обозначается символом ”|”. Части СДНФ, объединённые дизъюнкцией называются термами.

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

Рассмотрим метод минимизации с использованием карт Карно.

Таблица истинности функции преобразуется в карту Карно. Логические переменные группируются в столбцы и строки. Соседние столбцы и соседние строки могут отличаться не более чем в одном элементе.

В карте Карно необходимо отыскать области, пригодные для склеивания.

Области должны удовлетворять следующим условиям:

- они должны содержать в себе 1, если требуется получить ДНФ и 0, если требуется КНФ;

- площадь области единиц должна быть 2ⁿ, где n – целое число, и область должна быть симметрична относительно центра;

- в области должны содержаться только 1;

- все 1 должны принадлежать какой-либо области;

- общее число областей должно быть минимальным, а число 1 в областях максимальным;

- одна ячейка карты Карно может входить в несколько областей;

- крайние клетки каждой горизонтали и каждой вертикали также граничат между собой.

После нахождения всех областей каждая их них рассматривается отдельно. Неизменные переменные в области выписываются с конъюнкцией, изменяющиеся переменные отбрасываются. Конъюнкции всех областей соединяются дизъюнкцией:

Дата добавления: 2015-07-16