Минимизация логических функций методом карт Карно
Метод Квайна хорош для большого числа аргументов и при использовании ЭВМ
Для более простых случаев используются карты Карно – своеобразный вид таблицы истинности.
Каждая клетка соответствует одной импликанте СДНФ. Карта Карно – индивидуальная таблица истинности.Пример:
х1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
х2 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
х3 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
f |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
Правила получения МДНФ
- Все клетки, карты Карно содержащие 1, объединяются в области
- Каждая область должна представлять прямоугольник с числом клеток 2k ,где
k =0,1,2,3 – неотрицательное целое число т.о. допустимое число клеток в области: 1,2,4,8.
- Области могут пересекаться
- Одни и те же клетки могут входить в разные области
- Областей должно быть как можно меньше
- Области должны быть как можно крупнее.
- Карту можно сворачивать
Запись МДНФ: каждая область представляется членом, состоящим из тех аргументов, которые для соответствующей области не меняют своего знака.