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

Импликанта булевой функции $f:E_2^n\to E_2$ — любая функция $g:E_2^n\to E_2$ такая, что если $g(x_1,\dots ,x_n)=1$, то $f(x_1,\dots ,x_n)=1$.Шаблон:Sfn

Имплицента булевой функции $f:E_2^n\to E_2$ — любая функция $g:E_2^n\to E_2$ такая, что если $g(x_1,\dots ,x_n)=0$, то $f(x_1,\dots ,x_n)=0$.Шаблон:Sfn

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

• $f_1$ — импликанта $f_2$;
• множество единиц $f_1$ является подмножеством множества единиц $f_2$ ($N_{f_1}\subseteq N_{f_2}$);Шаблон:Sfn
• $f_1\vee f_2=f_2$;
• $f_2$ — имплицента $f_1$;Шаблон:Sfn
• множество нулей $f_2$ является подмножеством множества нулей $f_1$ ($M_{f_2}\subseteq M_{f_1}$);
• $f_1\wedge f_2=f_1$;Шаблон:Sfn
• $f_1\to f_2=1$.

Свойства

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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья