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

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

$x_1^{{\sigma }_1}\wedge \dots \wedge x_r^{{\sigma }_r}$,

где $r\ge 0$, $x_i\ne x_j$ при $i\ne j$.Шаблон:Sfn Здесь запись вида $x_i^{{\sigma }_i}$ — обозначение для литералов, определяемая для заданного значения ${\sigma }_i\in E_2$ как:

$x_i^{{\sigma }_i}=\{\begin{array}{cc}{x}_i& {\sigma }_i=1\\ \overline{x_i}& {\sigma }_i=0\end{array}$Шаблон:Sfn

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

Примеры:

• $x_1\wedge x_2$
• $x_1\wedge \overline{x_2}\wedge x_3$
• $\overline{x_1}$
• $1$

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

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

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

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

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

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

• $K_1\vee K_1{K}_2=K_1$ — закон поглощения;
• $xK\vee \bar{x}K=K$ — закон склеивания;
• $xK\vee \bar{x}K=xK\vee \bar{x}K\vee K$ — закон неполного склеивания;
• $x{K}_1\vee \bar{x}{K}_2=x{K}_1\vee \bar{x}{K}_2\vee K_1{K}_2$ — закон обобщённого склеивания.

Если выполнено тождество $K_1\vee K_2=K_1$, то говорят, что элементарная конъюнкция $K_1$ поглощает $K_2$. Элементарная конъюнкция $K_1$ поглощает $K_2$ тогда и только тогда, когда множество литералов $K_1$ является подмножеством множества литералов $K_2$. Примеры:

• $x_1$ поглощает $x_1\wedge \overline{x_2}\wedge x_3$;
• $x_1\wedge \overline{x_3}$ поглощает $x_1\wedge x_2\wedge \overline{x_3}$;
• $1$ поглощает любую элементарную конъюнкцию.

В общем, $x_{i_1}^{{\sigma }_1}\wedge \dots \wedge x_{i_r}^{{\sigma }_r}$ поглощает $x_{i_1}^{{\sigma }_1}\wedge \dots \wedge x_{i_r}^{{\sigma }_r}\wedge x_{i_{r+1}}^{{\sigma }_{r+1}}\wedge \dots \wedge x_{i_{r+r^{\prime }}}^{{\sigma }_{r+r^{\prime }}}$

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

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

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

$\{({\alpha }_1,\dots ,{\alpha }_n)\in E_2^n|{\alpha }_{i_1}={\sigma }_1,\dots ,{\alpha }_{i_r}={\sigma }_r\}$

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

Данное соответствие задаётся следующим образом. Элементарной конъюнкции $x_{i_1}^{{\sigma }_1}\wedge \dots \wedge x_{i_r}^{{\sigma }_r}$ соответствует грань $\{({\alpha }_1,\dots ,{\alpha }_n)\in E_2^n|{\alpha }_{i_1}={\sigma }_1,\dots ,{\alpha }_{i_r}={\sigma }_r\}$. Элементарной конъюнкции ранга $0$ соответствует весь булев куб (n-мерная грань). Элементарной конъюнкции ранга $n$ соответствует синглтон из одной вершины булева куба (0-мерная грань, то есть точка). Две элементарные конъюнкции $K_1$ и $K_2$ ортогональны тогда и только тогда, когда $N_{K_1}$ и $N_{K_2}$ не пересекаются.

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

Шаблон:Основная статья Булева функция $g:E_2^n\to E_2$ называется импликантой функции $f:E_2^n\to E_2$, если из того, что $g({\alpha }_1,\dots ,{\alpha }_n)=1$ следует $f({\alpha }_1,\dots ,{\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\wedge K_2=K_1$);
• Множество литералов $K_1$ является поднмножеством множества литералов $K_2$;
• $N_{K_1}\supset N_{K_2}$.

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

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

См. также

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

Литература

• Шаблон:Книга

Ссылки

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