Импликанты и простые импликанты функций алгебры логики

Элементарная конъюнкция K называется импликантой функции f, если K=1 возможно только там, где f=1. Эквивалентно, K→f тождественно равно 1, а геометрически соответствующая K грань полностью лежит в \(N_f\).¹

Простая импликанта — импликанта, которую уже нельзя расширить удалением литералов и сохранить импликантность. Геометрически ей соответствует максимальная по включению грань внутри \(N_f\). Любую импликанту можно расширять до некоторой простой импликанты.¹

Что важно запомнить

K — импликанта f, если \(N_K \subseteq N_f\).
Чем меньше литералов в конъюнкции, тем больше соответствующая грань.
Простая импликанта соответствует максимальной грани, целиком лежащей в \(N_f\).
Любую импликанту можно расширить до простой, удаляя лишние литералы, пока сохраняется условие \(N_K \subseteq N_f\).¹

Импликанта

Пусть K — элементарная конъюнкция. Если из K=1 всегда следует f=1, то K называется импликантой f. На языке множеств это условие записывается как \(N_K \subseteq N_f\). Поэтому импликанта описывает некоторую грань булева куба, целиком лежащую внутри множества единиц функции.¹

Для элементарных конъюнкций поглощение связано с включением наборов литералов. Если из K' удалить часть литералов, соответствующая грань станет больше. Если эта увеличенная грань всё ещё целиком лежит в \(N_f\), исходная импликанта была избыточно узкой.

Простая импликанта

Простой называют импликанту, которая не поглощается никакой другой отличной от неё импликантой f. Эквивалентно, нельзя удалить хотя бы один литерал так, чтобы полученная более короткая элементарная конъюнкция по-прежнему была импликантой f. Геометрически простые импликанты в точности соответствуют максимальным по включению граням множества \(N_f\).¹

Из любой импликанты можно последовательно удалять лишние литералы, пока дальнейшее расширение грани не выведет её за \(N_f\). Полученная конъюнкция будет простой импликантой. Поэтому простые импликанты образуют естественный «максимально укрупнённый» набор блоков, из которых затем строят сокращённую и другие специальные ДНФ.¹

Важно, что слово «простая» не означает «состоящая из одного литерала». Простая импликанта может иметь любой ранг. Её простота означает невозможность дальнейшего поглощения другой импликантой той же функции.

Пример простыми словами

Для f=x1∨x2 конъюнкция x1x2 является импликантой: если x1x2=1, то f=1. Но она не простая, потому что после удаления x2 остаётся x1, а x1 тоже является импликантой f. Импликанты x1 и x2 уже нельзя расширить удалением литералов, поэтому они простые.

Частые ошибки

Переворачивать направление импликации. Для импликанты нужно K→f, а не f→K.
Считать простой любую короткую конъюнкцию. Критерий — невозможность поглощения более общей импликантой.
Искать простые импликанты только среди членов одной выбранной ДНФ. Они являются свойством самой функции f.

Другие вопросы

Источники

1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 1, §3, МГУ, факультет ВМК