Пример. Построить карту Карно для функции

Пример.

Построить карту Карно для функции .

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

Таблица 3.21 − Карта Карно для функции

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

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

В таблицах 3.22 и 3.23 приведены карты Карно для трех переменных с отмеченными соседними ячейками для ячеек А и В.

Таблица 3.22 − Карта Карно для функции с отмеченными соседними ячейками для ячейки А

			А

Таблица 3.23 − Карта Карно для функции с отмеченными соседними ячейками для ячейки В

				В

Правило склеивания ячеек и записи минимальной ДНФ:

1.Строится карта Карно, соответствующая данной функции.

2. Ячейки объединяются в группы, обозначающие операции склеивания. В объединении участвуют только соседние ячейки, в которых находятся единицы. В группу объединяется только то количество ячеек, которое равно . При этом группа может иметь только прямоугольную или квадратную форму.

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

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

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

Дата добавления: 2014-10-22