Способы покрытия таблицы Квайна

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

Объединение этих импликант называется ядром покрытия. Если ядро покрытия не перекрывает все конституенты функции, то к нему добавляются дополнительные импликанты до полного покрытия. Все минимальные покрытия отыскиваются с помощью простого перебора.

Так для нашего примера: ядро покрытия покрывает конституенты

0х1 - 001 и 011

1х0 - 100 и 110

Констутиента 111 осталась непокрытой, следовательно к ядру нужно добавить еще одну импликанту. При этом получаем 2 минимальных покрытия:

{0х1, 1х0, х11}

{0х1, 1х0, 11х}

Первому покрытию соответствует тупиковая форма

f = ₁М₃ + М_{1 3} + М₂ М₃

а второму:

f = ₁ М₃ + М₁М₃ + М₁М₂

Такой способ образования минимальных покрытий для функций с большим числом переменных затруднен при применении.

Рассмотрим другой, более эффективный способ.

Для этого каждую простую импликанту таблицы Квайна представим с помощью множества. При этом будем считать, что для таблицы Квайна множество – малые латинские буквы.