Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

27 Тема 2. Минимизация булевых функций 6. Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски Проблема минимизации Определение. ДНФ  функции f называется а) минимальной (минимальной по литералам), если она имеет наименьшее число символов переменных среди других ДНФ функции f ; б) кратчайшей (минимальной по конъюнкциям), если она имеет минимальное число элементарных конъюнкций. Число различных элементарных конъюнкций от n переменных равно 3 n , т.к. любая переменная может либо входить в конъюнкцию, либо не входить, либо входить с отрицанием. Тогда ДНФ от n переменных однозначно определяется вектором длины 3 n , состоящим из нулей и единиц, где 1 означает, что соответствующая элементарная конъюнкция входит в ДНФ, а 0 – не входит. Поэтому число всех ДНФ от «n» переменных равно n 3 2 . Для произвольной функции алгебры логики можно написать много ДНФ. Проблема минимизации состоит в том, чтобы для функции f построить минимальную ДНФ в определенном выше смысле. Эта проблема допускает тривиальное решение, заключающееся в переборе всех n 3 2 ДНФ, но очевидно, что такое решение является чрезвычайно трудоемким даже при небольших значениях n . Определение. Формула  влечет формулу  ( обозначение    ) , если (    )  1 , т.е. не существует такого набора значений переменных, при котором  принимает значение 1 , а  – значение 0 . Определение. Элементарная конъюнкция K называется импликантом функции f , если K  f .