Конъюнктивный одночлен

Конъюнкти́вный одночле́н (элементарная конъюнкция, минте́рм) — булева формула, представляющая собой конъюнкцию литералов:

$x_{1}^{\sigma _{1}}\land \ldots \land x_{r}^{\sigma _{r}}$,

где $r\geq 0$, $x_{i}\neq x_{j}$ при $i\neq j$. Здесь запись вида $x_{i}^{\sigma _{i}}$ — обозначение для литералов, определяемая для заданного значения $\sigma _{i}\in E_{2}$ как:

$x_{i}^{\sigma _{i}}={\begin{cases}x_{i}&\sigma _{i}=1\\{\overline {x_{i}}}&\sigma _{i}=0\end{cases}}$

Число $r$ называется рангом элементарной конъюнкции. Если ранг равен одному, то элементарная конъюнкция является литералом. Если ранг равен нулю, то элементарная конъюнкция определяется как формула $1$.

Примеры:

• $x_{1}\land x_{2}$
• $x_{1}\land {\overline {x_{2}}}\land x_{3}$
• ${\overline {x_{1}}}$
• $1$

Элементарные конъюнкции понимаются с точностью до перестановки литералов и расстановки скобок между ними, то есть $x_{1}\land {\overline {x_{2}}}$ и ${\overline {x_{2}}}\land x_{1}$ считаются одной и той же элементарной конъюнкцией, $(x_{1}\land x_{2})\land x_{3}$ и $x_{1}\land (x_{2}\land x_{3})$ — тоже.

Элементарные конъюнкции, как и формулы, определяются над множеством переменных, при этом переменная из этого множества может и не входить в элементарную конъюнкцию. Каждая элементарная конъюнкция однозначно определяется множеством своих литералов, но не любое множество литералов определяет элементарную конъюнкцию. Чтобы конечное множество литералов определяло элементарную конъюнкцию нужно, чтобы ни для какой переменной $x$ в него не входили одновременно литералы $x$ и ${\overline {x}}$.

Каждая переменная из множества переменных, над которым определяется конъюнкция, может либо входить без отрицания, либо входить с отрицанием, либо не входить вообще, поэтому количество элементарных конъюнкций над конечным множеством переменных мощности $n$ равно $3^{n}$. Количество элементарных конъюнкций ранга $r$ над множеством переменных $X,|X|\geq r$ равно $2^{r}$. Если ранг элементарной конъюнкции равен мощности множества переменных, над которым она определена, то такая элементарная конъюнкция называется полной над этим множеством.

Склеивание и поглощение элементарных конъюнкций

Говорят, что две элементарные конъюнкции совпадают по переменной $x_{i}$, если эта переменная либо входит в обе эти конъюнкции без отрицания, либо в обе с отрицанием, либо вообще не входит ни в одну из них. Если две элементарные конъюнкции совпадают по всем переменным, над которыми они определены, то они равны. Две элементарные конъюнкции называются ортогональными по переменной $x_{i}$, если в одну из конъюнкций эта переменная входит с отрицанием, а в другую без. Две элементарные конъюнкции ортогональны тогда и только тогда, когда их конъюнкция тождественно равна нулю. Если две элементарные конъюнкции ортогональны по одной и только одной переменной, то такие элементарные конъюнкции называются смежными по этой переменной. Если две элементарные конъюнкции совпадают по всем переменным кроме одной, по которым они смежны, то такие элементарные конъюнкции называются соседними по этой переменной.

Пусть $K,K_{1},K_{2}$ — произвольные элементарные конъюнкции. Тогда выполнены следующие тождества:

• $K_{1}\lor K_{1}K_{2}=K_{1}$ — закон поглощения;
• $xK\lor {\overline {x}}K=K$ — закон склеивания;
• $xK\lor {\overline {x}}K=xK\lor {\overline {x}}K\lor K$ — закон неполного склеивания;
• $xK_{1}\lor {\overline {x}}K_{2}=xK_{1}\lor {\overline {x}}K_{2}\lor K_{1}K_{2}$ — закон обобщённого склеивания.

Если выполнено тождество $K_{1}\lor K_{2}=K_{1}$, то говорят, что элементарная конъюнкция $K_{1}$ поглощает $K_{2}$. Элементарная конъюнкция $K_{1}$ поглощает $K_{2}$ тогда и только тогда, когда множество литералов $K_{1}$ является подмножеством множества литералов $K_{2}$. Примеры:

• $x_{1}$ поглощает $x_{1}\land {\overline {x_{2}}}\land x_{3}$;
• $x_{1}\land {\overline {x_{3}}}$ поглощает $x_{1}\land x_{2}\land {\overline {x_{3}}}$;
• $1$ поглощает любую элементарную конъюнкцию.

В общем, $x_{i_{1}}^{\sigma _{1}}\land \ldots \land x_{i_{r}}^{\sigma _{r}}$ поглощает $x_{i_{1}}^{\sigma _{1}}\land \ldots \land x_{i_{r}}^{\sigma _{r}}\land x_{i_{r+1}}^{\sigma _{r+1}}\land \ldots \land x_{i_{r+r'}}^{\sigma _{r+r'}}$

Функции, задаваемые элементарной конъюкцией

Две разные элементарные конъюнкции относительно одного и того же набора переменных $(x_{1},\ldots ,x_{n})$ задают разные булевы функции. Поэтому, если зафиксировать набор переменных, то элементарную конъюнкцию можно отождествлять с булевой функцией, которую она задаёт. При этом, не любая булева функция может быть задана при помощи элементарной конъюнкции. Например, тождественный ноль не может быть представлен в виде элементарной конъюнкции.

Элементарные конъюнкции допускают простую геометрическую интерпретацию. Зафиксируем набор $(x_{1},\ldots ,x_{n})$ и будем отождествлять элементарные конъюнкции над этим набором с функциями, которые они задают. Булева функции арности $f$ однозначно определяется её множеством единиц $N_{f}=\{(\alpha _{1},\ldots ,\alpha _{n})\in E_{2}^{n}|f(\alpha _{1},\ldots ,\alpha _{n})=1\}$. Поэтому можно задать взаимо однозначное соответствие между булевыми функциями и подмножествами булева куба. Элементарным конъюнкциям ранга $r$ при этом будут соответствовать грани булева куба размерности $n-r$ (а если точнее, множества вершин граней). Более формально, назовём n-r-мерной гранью булева куба $E_{2}^{n}$ множество вида:

$\{(\alpha _{1},\ldots ,\alpha _{n})\in E_{2}^{n}|\alpha _{i_{1}}=\sigma _{1},\ldots ,\alpha _{i_{r}}=\sigma _{r}\}$

для некоторых $\sigma _{1},\ldots ,\sigma _{r}\in E_{2}^{n}$. Таким образом, элементарной конъюнкции соответствует множество наборов, у которых определённые $r$ координат фиксированы.

Данное соответствие задаётся следующим образом. Элементарной конъюнкции $x_{i_{1}}^{\sigma _{1}}\land \ldots \land x_{i_{r}}^{\sigma _{r}}$ соответствует грань $\{(\alpha _{1},\ldots ,\alpha _{n})\in E_{2}^{n}|\alpha _{i_{1}}=\sigma _{1},\ldots ,\alpha _{i_{r}}=\sigma _{r}\}$. Элементарной конъюнкции ранга $0$ соответствует весь булев куб (n-мерная грань). Элементарной конъюнкции ранга $n$ соответствует синглтон из одной вершины булева куба (0-мерная грань, то есть точка). Две элементарные конъюнкции $K_{1}$ и $K_{2}$ ортогональны тогда и только тогда, когда $N_{K_{1}}$ и $N_{K_{2}}$ не пересекаются.

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

Основная статья: Простая импликанта

Булева функция $g\colon E_{2}^{n}\to E_{2}$ называется импликантой функции $f\colon E_{2}^{n}\to E_{2}$, если из того, что $g(\alpha _{1},\ldots ,\alpha _{n})=1$ следует $f(\alpha _{1},\ldots ,\alpha _{n})=1$. Нетрудно видеть, что это условие эквивалентно тому, что $N_{g}\subseteq N_{f}$. Таким образом, при геометрической интерпретации импликанта функции это просто подмножество.

Элементарная конъюнкция $K_{1}$ поглощает $K_{2}$ тогда и только тогда, когда $N_{K_{1}}\supseteq N_{K_{2}}$. В геометрической интерпретации поглощающая конъюнкция есть просто надгрань. Резюмируя, следующие 3 условия эквиваленты:

• $K_{1}$ поглощает $K_{2}$ ($K_{1}\land K_{2}=K_{1}$);
• Множество литералов $K_{1}$ является поднмножеством множества литералов $K_{2}$;
• $N_{K_{1}}\supset N_{K_{2}}$.

Из последних двух условий можно видеть, что при переходе между представлением в виде множества литералов и в виде множества единиц знак включения обращается.

Элементарная конъюнкция $K$ называется простой импликантой функции $f\colon E_{2}^{n}\to E_{2}$, если она импликанта $f$ и не существует элементарной конъюнкции $K'$, которая поглощает $K$ и тоже является импликантой $f$. $K$ является простой импликантой $f$ тогда и только тогда, когда грань $N_{K}\subseteq N_{f}$ и никакая большая грань $N_{K'}\supset N_{K}$ не входит в $N_{f}$. Проще говоря в геометрической интерпретации простым импликантам функции соответствуют максимальные подграни.

См. также

• Дизъюнктивная нормальная форма
• Конъюнктивная нормальная форма
• Дизъюнктивный одночлен
• Совершенный одночлен
• Булева алгебра
• Алгебра логики

Литература

• Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 с.

Ссылки

• Логика высказываний