Читайте также:
|
В этом случае любая логическая функция должна быть задана СДНФ. В качестве примера приведем минимальную карту для функции трех аргументов.
| x1 | x2 | x3 | x1x2 | x1x3 | x2x3 | x1x2x3 |
| x1 | x2 | _ x3 | x1x2 | _ x1x3 | _ x2x3 | _ x1x2x3 |
| x1 | _ x2 | x3 | _ x1x2 | x1x3 | _ x2x3 | _ x1x2x3 |
| x1 | _ x2 | _ x3 | _ x1x2 | _ x1x3 | _ _ x2x3 | _ _ x1x2x3 |
| _ x1 | x2 | x3 | _ x1x2 | _ x1x3 | x2x3 | _ x1x2x3 |
| _ x1 | x2 | _ x3 | _ x1x2 | _ _ x1x3 | _ x2x3 | _ _ x1x2x3 |
| _ x1 | _ x2 | x3 | _ _ x1x2 | _ x1x3 | _ x2x3 | _ _ x1x2x3 |
| _ x1 | _ x2 | _ x3 | _ _ x1x2 | _ _ x1x3 | _ _ x2x3 | _ _ _ x1x2x3 |
Эта таблица содержит все возможные конъюнкции заданных простых переменных и всегда имеет 2n-1 столбцов и 2n строк, где n – число аргументов логической функции. Сами переменные рассматриваются как конъюнкции в силу соотношения иденпотентности. Порядок использования минимизирующей карты следующий:
1. вычеркиваются все строки таблицы, соответствующие тем конституентам 1, которые отсутствуют в заданной СДНФ. В дальнейшем будем пояснять на примере логической функции _ _ _ _ _ _ _ _ _
F(x1x2x3) = x1x2x3 ∨ x1x2x3 ∨ x1x2x3 ∨ x1x2x3 ∨ x1x2x3 ∨ x1x2x3
В данном случае убираем строки 2 и 6.
2. В оставшихся строках в каждом столбце зачеркиваются элементы, одинаковые с теми, которые уже были зачеркнуты в этом столбце.
3. 
Из каждой незачеркнутой строки выбирается по одной конъюнкции, содержащей минимальное число множителей. Эти конъюнкции соединяются знаком дизъюнкции (x3 ∨ x2)
МДНФ получается после исключения повторяющихся множителей и слагаемых.
|
| x1 | x2 | x3 | x4 | x1x2 | x1x3 | x1x4 | x2x3 | x2x4 | x3x4 | x1x2x3 | x1x2x4 | x1x3x4 | x2x3x4 | x1x2x3x4 |
| x1 | x2 | x3 | _ x4 | x1x2 | x1x3 | _ x1x4 | x2x3 | _ x2x4 | x3x4 | x1x2x3 | _ x1x2x4 | _ x1x3x4 | _ x2x3x4 | _ x1x2x3x4 |
| x1 | x2 | _ x3 | x4 | x1x2 | _ x1x3 | x1x4 | _ x2x3 | x2x4 | x3x4 | _ x1x2x3 | x1x2x4 | _ x1x3x4 | _ x2x3x4 | _ x1x2x3x4 |
| x1 | x2 | _ x3 | _ x4 | x1x2 | _ x1x3 | _ x1x4 | _ x2x3 | _ x2x4 | x3x4 | _ x1x2x3 | _ x1x2x4 | _ _ x1x3x4 | _ _ x2x3x4 | _ _ x1x2x3x4 |
| x1 | _ x2 | x3 | x4 | _ x1x2 | x1x3 | x1x4 | _ x2x3 | _ x2x4 | x3x4 | _ x1x2x3 | _ x1x2x4 | x1x3x4 | _ x2x3x4 | _ x1x2x3x4 |
| x1 | _ x2 | x3 | _ x4 | _ x1x2 | x1x3 | _ x1x4 | _ x2x3 | _ _ x2x4 | x3x4 | _ x1x2x3 | _ _ x1x2x4 | _ x1x3x4 | _ _ x2x3x4 | _ _ x1x2x3x4 |
| x1 | _ x2 | _ x3 | x4 | _ x1x2 | _ x1x3 | x1x4 | _ _ x2x3 | _ x2x4 | x3x4 | _ _ x1x2x3 | _ x1x2x4 | _ x1x3x4 | _ _ x2x3x4 | _ _ x1x2x3x4 |
| x1 | _ x2 | _ x3 | _ x4 | _ x1x2 | _ x1x3 | _ x1x4 | _ _ x2x3 | _ _ x2x4 | x3x4 | _ _ x1x2x3 | _ _ x1x2x4 | _ _ x1x3x4 | _ _ _ x2x3x4 | _ _ _ x1x2x3x4 |
| _ x1 | x2 | x3 | x4 | _ x1x2 | _ x1x3 | _ x1x4 | x2x3 | x2x4 | x3x4 | _ x1x2x3 | _ x1x2x4 | _ x1x3x4 | x2x3x4 | _ x1x2x3x4 |
| _ x1 | x2 | x3 | _ x4 | _ x1x2 | _ x1x3 | _ _ x1x4 | x2x3 | _ x2x4 | x3x4 | _ x1x2x3 | _ _ x1x2x4 | _ _ x1x3x4 | _ x2x3x4 | _ _ x1x2x3x4 |
| _ x1 | x2 | _ x3 | x4 | _ x1x2 | _ _ x1x3 | _ x1x4 | _ x2x3 | x2x4 | x3x4 | _ _ x1x2x3 | _ x1x2x4 | _ _ x1x3x4 | _ x2x3x4 | _ _ x1x2x3x4 |
| _ x1 | x2 | _ x3 | _ x4 | _ x1x2 | _ _ x1x3 | _ _ x1x4 | _ x2x3 | _ x2x4 | x3x4 | _ _ x1x2x3 | _ _ x1x2x4 | _ _ _ x1x3x4 | _ _ x2x3x4 | _ _ _ x1x2x3x4 |
| _ x1 | _ x2 | x3 | x4 | _ _ x1x2 | _ x1x3 | _ x1x4 | _ x2x3 | _ x2x4 | x3x4 | _ _ x1x2x3 | _ _ x1x2x4 | _ x1x3x4 | _ x2x3x4 | _ _ x1x2x3x4 |
| _ x1 | _ x2 | x3 | _ x4 | _ _ x1x2 | _ x1x3 | _ _ x1x4 | _ x2x3 | _ _ x2x4 | x3x4 | _ _ x1x2x3 | _ _ _ x1x2x4 | _ _ x1x3x4 | _ _ x2x3x4 | _ _ _ x1x2x3x4 |
| _ x1 | _ x2 | _ x3 | x4 | _ _ x1x2 | _ _ x1x3 | _ x1x4 | _ _ x2x3 | _ x2x4 | x3x4 | _ _ _ x1x2x3 | _ _ x1x2x4 | _ _ x1x3x4 | _ _ x2x3x4 | _ _ _ x1x2x3x4 |
| _ x1 | _ x2 | _ x3 | _ x4 | _ _ x1x2 | _ _ x1x3 | _ _ x1x4 | _ _ x2x3 | _ _ x2x4 | x3x4 | _ _ _ x1x2x3 | _ _ _ x1x2x4 | _ _ _ x1x3x4 | _ _ _ x2x3x4 | _ _ _ _ x1x2x3x4 |
_ _ _
МДНФ имеет вид F(x1x2x3x4)=x1x2 ∨ x1x2x3
Дата добавления: 2015-07-10; просмотров: 78 | Нарушение авторских прав