Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

1.2. Формы представления булевых функций

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

Пусть будут заданы номера наборов четырех переменных, на которых логическая функция принимает единичное значение:

f (2, 5, 6, 7, 10, 12, 13, 14) = 1.

Выразим эту логическую функцию в СДНФ (символ конъюнкции писать не будем):

F (0010, 0101, 0110, 0111, 1010, 1100, 1101, 1110) =

= x₄x₃x₂x₁ ∨ x₄x₃x₂x₁ ∨ x₄x₃x₂x₁ ∨ x₄x₃x₂x₁ ∨

∨ x₄x₃x₂x₁ ∨ x₄x₃x₂x₁ ∨ x₄x₃x₂x₁ ∨ x₄x₃x₂x₁.

На первом этапе минимизации исходную СДНФ можно упростить за счет использования закона склеивания:

f = x₂x₁ ∨ x₄x₃x₁ ∨ x₁x₃x₂ ∨ x₃x₂x₁ ∨ x₄x₃x₂ ∨ x₄x₃x₁.

Обращаем внимание на то, что одну и ту же конституенту (импликанту) можно склеивать с другими конституентами (импликантами) многократно, так как в логике Буля действует закон идемпотентности:

а = а ∨ а = а ∨ а ∨ а = ... ,     а = а ∧ а = а ∧ а ∧ а = ... ,

поэтому любую конституенту можно размножить.

На втором этапе воспользуемся таблицей Куайна (табл. 1. 11), в соответствии с которой метод минимизации получил наименование — метод Куайна.

Таблица 1.10

x4x3x2x1	0010	0101	0110	0111	1010	1100	1101	1110
– – 0 1	1	0	1	0	1	0	0	1
0 1 – 1	0	1	0	1	0	0	0	0
0 1 1 –	0	0	1	1	0	0	0	0
– 1 0 1	0	1	0	0	0	0	1	0
1 1 0 –	0	0	0	0	0	1	1	0
1 1 – 0	0	0	0	0	0	1	0	1

В таблице по вертикали перечислены все полученные на первом этапе упрощения импликанты, а по горизонтали — исходные конституенты. Единица в табл. 1. 11 стоит там, где импликанта «накрывает» конституенту. Дело в том, что конституента всегда может быть заменена импликантой или даже отдельным термом по закону поглощения:

а = а ∨ (а ∧ b) = а ∨ (а ∧ abc) = ... , 

а = а ∧ (а ∨ b) = а ∧ (а ∨ abc) = ...

После заполнения таблицы Куайна получилось так, что почти в каждой графе оказалось по две единицы; между тем достаточно иметь одну единицу на графе. Поэтому, по возможности, нужно исключить избыточные единицы. Выбор единиц производится из соображений минимальности числа термов (выбранные единицы заштрихованы). В итоге оказалось, что можно обойтись только тремя импликантами вместо шести:

f = x₂x₁ ∨ x₄x₃x₁ ∨ x₄x₃x₂.

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