Конъюнктивный одночлен — Википедия

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

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

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

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

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

Примеры:

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

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

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

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

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

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

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

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

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

В общем, ${\displaystyle x_{i_{1}}^{\sigma _{1}}\land \ldots \land x_{i_{r}}^{\sigma _{r}}}$ поглощает ${\displaystyle 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'}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Это заготовка статьи по математике. Помогите Википедии, дополнив её.

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (20 октября 2024)