Импликанта и имплицента

Импликанта булевой функции $f\colon E_{2}^{n}\to E_{2}$ — любая функция $g\colon E_{2}^{n}\to E_{2}$ такая, что если $g(x_{1},\ldots ,x_{n})=1$, то $f(x_{1},\ldots ,x_{n})=1$.

Имплицента булевой функции $f\colon E_{2}^{n}\to E_{2}$ — любая функция $g\colon E_{2}^{n}\to E_{2}$ такая, что если $g(x_{1},\ldots ,x_{n})=0$, то $f(x_{1},\ldots ,x_{n})=0$.

Следующие условия эквивалентны:

• $f_{1}$ — импликанта $f_{2}$;
• множество единиц $f_{1}$ является подмножеством множества единиц $f_{2}$ ($N_{f_{1}}\subseteq N_{f_{2}}$);
• $f_{1}\lor f_{2}=f_{2}$;
• $f_{2}$ — имплицента $f_{1}$;
• множество нулей $f_{2}$ является подмножеством множества нулей $f_{1}$ ($M_{f_{2}}\subseteq M_{f_{1}}$);
• $f_{1}\land f_{2}=f_{1}$;
• $f_{1}\to f_{2}=1$.

Свойства

Дизъюнкция импликант даст импликанту функции; конъюнкция имплицент даст имплиценту функции.

Пусть набор $(\alpha _{1},\ldots ,\alpha _{n})$ — единица функции $f$ (то есть $f(\alpha _{1},\ldots ,\alpha _{n})=1$). Будем говорить, что импликанта $g$ накрывает единицу $(\alpha _{1},\ldots ,\alpha _{n})$, если $g(\alpha _{1},\ldots ,\alpha _{n})=1$. Система импликант функции называется полной, если для каждой единицы функции в этой системе есть импликанта, которая её накрывает. Дизъюнкция полной системы импликант даст изначальную функцию. Дизъюнкция системы импликант даёт всю функцию тогда и только тогда, когда она полна. Полная система импликант называется приведённой, если любая её собственная подсистема неполна.

Пусть набор $(\alpha _{1},\ldots ,\alpha _{n})$ — нуль функции $f$ (то есть $f(\alpha _{1},\ldots ,\alpha _{n})=0$). Будем говорить, что имплицента $g$ накрывает нуль $(\alpha _{1},\ldots ,\alpha _{n})$, если $g(\alpha _{1},\ldots ,\alpha _{n})=0$. Система имплицент функции называется полной, если для каждого нуля функции в этой системе есть имплицента, которая его накрывает. Конъюнкция полной системы имплицент даст изначальную функцию. Конъюнкция системы имплицент даёт всю функцию тогда и только тогда, когда она полна. Полная система имплицент называется приведённой, если любая её собственная подсистема неполна.

Элементарная импликанта и имплицента

Импликанта $g$ называется элементарной импликантой, если она может быть выражена в виде элементарной конъюнкции. Имплицента $g$ называется элементарной имплицентой, если она может быть выражена в виде элементарной дизъюнкции. Элементарные импликанты и имплиценты часто отождествляют с элементарными конъюнкциями/дизъюнкциями, которыми они задаются. Например, под дизъюнкцией элементарных импликант обычно имеют в виду именно дизъюнкцию элементарных конъюнкций, которые задают эти импликанты. В этом смысле дизъюнкции элементарных импликант являются дизъюнктивными нормальными формами. Это отождествление также имеет особый смысл, когда говорят про поглощение одной элементарной импликантой/имплицентой другой. Дело в том, что терминология «элементарная конъюнкция/дизъюнкция поглощается другой элементарной конъюнкцией/дизъюнкцией» определяется именно для элементарных конъюнкций/дизъюнкций и не может быть однозначно обобщена для произольной булевой функции. Так выходит потому, что поглощение для конъюнкций и дизъюнкций определено по-разному. Элементарная конъюнкция поглощает другую тогда и только тогда, когда она является её имплицентой; но элементарная дизъюнкция поглощает другую тогда и только тогда, когда она является её импликантой. Однако, когда мы говорим об элементарных импликантах/имплицентах терминология поглощения всё же имеет смысл, поскольку элементарные импликанты/имплиценты можно отождествляють с элементарными конъюнкциями/дизъюнкциями, которые их задают, и иметь в виду поглощение для них.

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

Элементарная импликанта $g$ функции $f$ называется простой, если не существует элементарной импликанты $h$ такой, что она поглощает элементарную конъюнкцию $g$ и не совпадает с $g$. При геометрической интерпретации функции $f$ множеством единиц $N_{f}$ простой импликанте соответствует максимальная грань. Более формально, возьмём множество всех граней булева куба, входящих в $N_{f}$. Тогда простым импликантам функции $f$ соответствуют максимальные по включению грани из этого множества.

Элементарная имплицента $g$ функции $f$ называется простой, если не существует элементарной дизъюнкции $h$ такой, что она поглощает элементарную дизъюнкцию $g$ и не совпадает с $g$. При геометрической интерпретации функции $f$ множеством нулей $M_{f}$ простой имплиценте соответствует максимальная грань. Более формально, возьмём множество всех граней булева куба, входящих в $M_{f}$. Тогда простым имплицентам функции $f$ соответствуют максимальные по включению грани из этого множества.

Система всех простых импликант (имплицент) является полной, поэтому её дизъюнкция (конъюнкция) даст всю функцию. Если при этом представить импликанты (имплиценты) как элементарные конъюнкции (дизъюнкции), то получится ДНФ (КНФ) функции, которая называется сокращённая дизъюнктивная (конъюнктивная) нормальная форма. Дизъюнкция (конъюнкция) приведённой системы импликант (имплицент) называется приведённой или тупиковой ДНФ (КНФ).

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

Литература

• Глушков В. М. Синтез цифровых автоматов (рус.). — М.: Физматгиз, 1962. — 476 с. — (Математическая логика и основания математики).
• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.
• Голощапов В. Н., Ролдугин П. В. О числе биюнктивных функций, инвариантных относительно данной подстановки (рус.) // Дискретная математика : журнал. — 2013. — Т. 25, вып. 1. — С. 45-62. — doi:10.4213/dm1220.
• Ролдугин П. В., Тарасов А. В. Оценка числа переменных булевых функций небольшого веса, не содержащих имплицент меньше длины (рус.) // Дискретная математика : журнал. — 2002. — Т. 14, вып. 3. — С. 23-41. — doi:10.4213/dm251.