Вообще то говоря Квайна (Quine), но в старой рускоязычной литературе - Куина. Карты Карно хороши, когда число входов мало. (меньше или равно 5). Что же делать если число входов велико? Существуют методы Основной из них - метод Куина-Маккласки (Quine-McCluskey): Метод базируется на соотношеии: X*Y + X#*Y = Y 1) Берем таблицу истинности выписываем бинарно все минтермы (элементарные конъюнкции рангом равным рангу функции). 2) Затем ищем минтермы которые отличаются на один бит, и вносим их в таблицу минтермов более высокого уровня, так продолжаем пока не закончатся минтермы. 3) Затем процессируем термы большего порядка (см пункт (2)). До тех пор пока минтермов большего порядка не будет. 4) Выписываем минтермы начиная с меньшего ранга, при этом связанные минтермы в таблицах большего ранга не выписываем.
Не факт что досчитан до конца, главное показана идея. Таблица истинности функции: ------------------------------------------------------------- X1X2X3X4 F(X) Term Пары различающиеся на 1 бит ------------------------------------------------------------- 0000 1 X1#X2#X3#X4# 1 2 0001 1 x1#X2#X3#X4 1 5 11 0010 0 0011 0 0100 1 X1#X2X3#X4# 2 3 0101 0 0110 1 X1#X2X3X4# 3 4 11 0111 1 X1#X2X3X4 4 10 1000 0 1001 1 X1X2#X3#X4 5 9 1010 0 1011 0 1100 1 X1X2X3#X4# 6 1101 1 X1X2X3#X4 6 7 9 1110 0 1111 1 X1X2X3X4 7 10 ------------------------------------------------------------- Пример
Строим таблицу термов более низкого ранга: ------------------------------------------------------------- Пара X1X2X3X4 Терм Пары различающиеся на 1 бит ------------------------------------------------------------- 1 000- X1#X2#X3# C 2 0-00 X1#X3#X4# < - Result 3 01-0 X1#X2X4# < - Result 4 011- X1#X2X3 B 5 -000 X2#X3#X4# < - Result 6 110- X1X2X3# <- Result 7 11-1 X1X2X4 < - Result 9 1-01 X1X3#X4 < - Result 10 -111 X2X3X4 < - Result 11 010- X1#X2X3# B C ...... -------------------------------------------------------------
Сортируем ее по перестановкам: И ищем термы внутри перестановки которые отличаются на 1 бит: ------------------------------------------------------------- Пара X1X2X3X4 Терм Пары различающиеся на 1 бит ------------------------------------------------------------- 1 000- X1#X2#X3# C 4 011- X1#X2X3 B 6 110- X1X2X3# <- Result 11 010- X1#X2X3# B C ---------------------------------------------------------- 3 01-0 X1#X2X4# < - Result 7 11-1 X1X2X4 < - Result ---------------------------------------------------------- 2 0-00 X1#X3#X4# < - Result 9 1-01 X1X3#X4 < - Result ---------------------------------------------------------- 5 -000 X2#X3#X4# < - Result 10 -111 X2X3X4 < - Result ...... -------------------------------------------------------------
Затем строит пары еще более низкого ранга: ------------------------------------------------------------- Пара X1X2X3X4 Терм Пары различающиеся на 1 бит ------------------------------------------------------------- B 01-- x1#X2 <- Result C 0-0- X1#X3# < - Result ------------------------------------------------------------- итд пока не сможем это делать.
Затем выписываем результат от младшего ранга к старшему (не выписывая термы которые вошли в термы более младшего ранга). Результат: F(X) = X1#X2 + X1#X3# + + X1#X3#X4# + X1#X2X4# + X2#X3#X4# + X1X2X3# + + X1X2X4 + X1X3#X4 + X2X3X4 Дальнейшая минимизация связана уже с выведением функции за пределы ДНФ. (и минимизация числа произведений и сложений). = X1#X2 + X1#X3# + + X4#(X1#X3# + X1#X2 + X2#X3#) + X1X2X3# + + X4 (X1X2 + X1X3# + X2X3) или = X1#X2 + X1#X2X4# + X1X2X4 + X3# (X1 + X1#X4# + X2#X4# + X1X2 + X1X4) + X2X3X4 Метод Квина-Маккласки очень плохо оптимизирует XOR. (В реальной жизни XOR надо отслеживать и порождать XOR)