Метод Блейка

Минимизация булевых функций.

Теорема.

Для того чтобы система S булевых функций была функционально полной, необходимо и достаточно, чтобы эта система содержала хотя бы одну булеву функцию, не сохраняющую константу 1, хотя бы одну булеву функцию, не сохраняющую константу 0, хотя бы одну несамодвойственную булеву функцию, хотя бы одну нелинейную булеву функцию и хотя бы одну немонотонную булеву функцию

" При проектировании компьютеров широко используются методы минимизации булевых функций, позволяющие получать рекомендации для построения экономичных схем компьютеров.

Общая задача минимизации булевых функций может быть сформулирована следующим образом: найти аналитическое выражение заданой булевой функции в форме, содержащей минимально возможное число букв.

Элементарной конъюнкцией называется конъюнкция конечного числа различных между собой булевых переменных, каждая из которых может иметь или не иметь отрицания

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюкций

Минимальной дизъюнктивной нормальной формой булевой функции называется ДНФ, содержащая наименьшее число букв (по отношению ко всем другим ДНФ, представляющим заданную булеву функцию)

Булева функция g(x₁,...,x_n) называется импликантой булевой функции f(x₁,...,x_n), если для любого набора переменных, на котором g=1, справедливо f=1

Импликанта g булевой функции f, являющаяся элементарной конъюнкцией, называется простой, если никакая часть импликанты g не является импликантой функции f

Рассмотрим несколько методов минимизации. Все они практически различаются лишь на первом этапе - этапе получения сокращенной ДНФ. Следует отметить, что, к сожалению, поиск минимальной ДНФ всегда связан с некоторым перебором решений. Существуют методы уменьшения этого перебора, однако он всегда остается.

"Метод Квайна основывается на применении двух основных соотношений.

1.Соотношение склеивания Ах V А/х = Ах V А/х V А,

где А - любое элементарное произведение.

2.Соотношение поглощения А~х V А = А, ~х E {х; /x}.

Справедливость обоих соотношений легко проверяется. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью.

" Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания:

Ax v B/x = Ax v B/x v AB,

В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции f произвести все возможные oбобщенные склеивания, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции f.

Тема 3. Алгоритмические основы вычислительных процессов. Элементы теории

Дата добавления: 2014-01-20