Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.[1][2][3] Преобразование функции можно разделить на два этапа:
на первом этапе осуществляется переход от совершенной формы (СДНФ или СКНФ) к так называемой сокращённой форме;
на втором этапе — переход от сокращённой формы к минимальной форме.
Представим, что заданная функция представлена в СДНФ. Для осуществления первого этапа преобразование проходит два действия:
Операция склеивания;
Операция поглощения.
Операция склеивания сводится к нахождению пар членов, соответствующих виду или , и преобразованию их в следующие выражения: . Результаты склеивания теперь играют роль дополнительных членов. Необходимо найти все возможные пары членов (каждый член с каждым).
Потом выполняется операция поглощения. Она основана на равенстве (член поглощает выражение ). Вследствие этого действия из логического выражения вычёркиваются все члены, поглощаемые другими переменными, результаты которых получены в операции склеивания. Обе операции первого этапа могут выполняться до тех пор, пока это может быть осуществимо. Применение этих операций продемонстрировано в таблице:
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
СДНФ выглядит так:
Результат операции склеивания нужен для преобразования функции на втором этапе (поглощения)
Членами результата склеивания являются
Член поглощает те члены исходного выражения, которые содержат , то есть первый и четвёртый. Эти члены вычёркиваются. Член поглощает второй и третий, а член — пятый член исходного выражения.
Повторение обеих операций приводит к следующему выражению:
Здесь склеивается пара членов и (склеивание пары членов и приводит к тому же результату), результат склеивания поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)
Структурная схема функции
Члены сокращённой формы (в нашем случае это и ) называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией — СДНФ. Структурная схема такого элемента показана на рисунке справа.
Второй этап (табличный) (получение минимальной формы)
Как и на первом этапе, в полученном равенстве могут содержаться члены, устранение которых никаким образом не повлияет на конечный результат. Следующий этап минимизации — удаление таких переменных. Таблица, представленная ниже, содержит значения истинности функции. По ней будет собрана следующая СДНФ.
0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
СДНФ, собранная по этой таблице выглядит следующим образом:
Члены этого выражения являются простыми импликантами выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицы.
Импликантная матрица
Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта поглощает члены и (в первом и во втором столбцах поставлены крестики).
Простая импликанта
Вторая импликанта поглощает первый и третий члены СДНФ (указано крестиками) и т. д. Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.
В нашем примере ядро составляют импликанты и (ими перекрываются второй и шестой столбцы). Исключение из сокращённой формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую в уже нелишний член. Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвёртый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту .
Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции:
Структурная схема, соответствующая выражению в МДНФ (второй этап) при минимизации функции методом Квайна
(а)
Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант и . Покажем допустимость подобного исключения членов из логического выражения.
Импликанты и становятся равными лог. 1 соответственно при следующих наборах значений аргументов: , , и , , .
Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу (а), получаем:
при , ,
;
при , ,
;
Использование метода для получения минимальной КНФ
Для получения Минимальной конъюнктивной нормальной формы (МКНФ), используя метод Куайна, вводятся следующие критерии:
для минимизации берётся не СДНФ, а СКНФ функции;
склеиваемые пары членов меняются на: или ;
правило операции поглощения выглядит следующим образом:
Алгебра логики — раздел математической логики, в котором изучаются логические операции над высказываниями. Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика, в отличие от, например, троичной логики.
Ко́мпле́ксные чи́сла — числа вида где — вещественные числа, — мнимая единица, то есть число, для которого выполняется равенство: Множество комплексных чисел обычно обозначается символом Вещественные числа можно рассматривать как частный случай комплексных, они имеют вид Главное свойство — в нём выполняется основная теорема алгебры, то есть любой многочлен -й степени имеет корней. Доказано, что система комплексных чисел логически непротиворечива.
Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ. Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.
Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. Для этого можно использовать: закон двойного отрицания, закон де Моргана, дистрибутивность.
Замкнутый класс в теории булевых функций — такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества , снова входит в это же множество.
Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.
Бу́лева фу́нкция от аргументов — в дискретной математике — отображение , где — булево множество. Элементы булева множества обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число , обозначающее количество аргументов, называется арностью или местностью функции, в случае булева функция превращается в булеву константу. Элементы декартова произведения называют булевыми векторами. Множество всех булевых функций от любого числа аргументов часто обозначается , а от аргументов — . Переменные, принимающие значения из булева множества, называются булевыми переменными. Булевы функции названы по фамилии математика Джорджа Буля.
Ка́рта Ка́рно — графический способ представления булевых функций с целью их удобной и наглядной ручной минимизации.
Конъюнкти́вный одночле́н — булева формула, представляющая собой конъюнкцию литералов:
,
Полином Жегалкина — многочлен над полем , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).
Самодвойственная функция — булева функция, двойственная сама к себе. Более развёрнуто, булева функция называется самодвойственной, если для любых значений верно
Полусумма́тор — комбинационная логическая схема, имеющая два входа и два выхода. Полусумматор позволяет вычислять сумму A+B, где A и B — это разряды (биты) обычно двоичного числа, при этом результатом будут два бита S и C, где S — это бит суммы по модулю 2, а C — бит переноса.
Метод Куайна—Мак-Класки — табличный метод минимизации булевых функций, предложенный Уиллардом Куайном и усовершенствованный Эдвардом Мак-Класки. Представляет собой попытку избавиться от недостатков метода Куайна.
Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — одна из форм представления функции алгебры логики в виде логического выражения. Представляет собой частный случай ДНФ, удовлетворяющий следующим трём условиям:
в ней нет одинаковых слагаемых ;
в каждом слагаемом нет повторяющихся переменных;
каждое слагаемое содержит все переменные, от которых зависит булева функция.
Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных дизъюнкций
в каждой дизъюнкции нет одинаковых пропозициональных переменных
каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.
Расширеннаячисловая прямая — множество вещественных чисел , дополненное двумя бесконечно удалёнными точками: и , то есть ;-\infty \}=[-\infty ;+\infty ]} . Следует понимать, что не являются числами и имеют немного иную природу, но для них, как и для вещественных чисел, тоже определено отношение порядка. Также сами элементы и считаются неравными друг другу.
Комбинационная логика в теории цифровых устройств — двоичная логика функционирования устройств комбинационного типа. У комбинационных устройств состояние выхода однозначно определяется набором входных сигналов, что отличает комбинационную логику от секвенциальной логики, в рамках которой выходное значение зависит не только от текущего входного воздействия, но и от предыстории функционирования цифрового устройства. Другими словами, секвенциальная логика предполагает наличие памяти, которая в комбинационной логике не предусмотрена.
В математике разложением Шеннона или декомпозицией Шеннона по переменной называется метод представления булевой функции от переменных в виде суммы двух подфункций от остальных переменных. Хотя этот метод часто приписывают Клоду Шеннону, но Буль доказал его гораздо раньше, а сама возможность такого разложения по любой из переменной непосредственно вытекает из возможности определения любой булевой функции с помощью таблицы истинности.
Алгоритмы быстрого возведения в степень по модулю — разновидность алгоритмов возведения в степень по модулю, широко использующихся в различных криптосистемах, для ускорения вычислительных операций с большими числами.
Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Предложен в 1956 году американским учёным Стэнли Роем Петриком (1931—2006). Метод Петрика довольно сложно применять для больших таблиц, но очень легко реализовать программно.
Эта страница основана на статье Википедии. Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия. Изображения, видео и звуки доступны по их собственным лицензиям.
