Викиконспекты - Вклад участника [ru]

Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

2017-12-24T15:08:03Z

Haposiwe: Изменения в "см. также"

{{Определение
|definition=
'''Последовательность''' (англ. ''sequence'') {{---}} это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.
}}

==Виды последовательностей ==
{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающей''''' (англ. ''nondecreasing''), если каждый элемент этой последовательности не превосходит следующего за ним. <tex>\{x_n\}</tex> — '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''невозрастающей''''' (англ. ''nonincreasing''), если каждый следующий элемент этой последовательности не превосходит предыдущего. <tex>\{x_n\}</tex> — '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей''''' (англ. ''increasing''), если каждый следующий элемент этой последовательности превышает предыдущий. <tex>\{x_n\}</tex> — '''''возрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n < x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей''''' (англ. ''decreasing''), если каждый элемент этой последовательности превышает следующий за ним. <tex>\{x_n\}</tex> — '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность называется '''монотонной''' (англ. ''monotonic''), если она является неубывающей, либо невозрастающей.
}}

{{Определение
|definition =
Последовательность называется '''строго монотонной''' (англ. ''strictly monotonic''), если она является возрастающей, либо убывающей.
}}

Очевидно, что строго монотонная последовательность является монотонной.

== Теорема о связи длины НВП и НУП ==

{{
Теорема
|author=
|about=
|statement=
Пусть <tex>a</tex> {{---}} перестановка чисел длины <tex>n, l</tex> {{---}} длина наибольшей возрастающей подпоследовательности ([[Задача о наибольшей возрастающей подпоследовательности|НВП]]), <tex>k</tex> {{---}} длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.

|proof=
Рассмотрим два массива длины <tex>n : S </tex> и <tex> T </tex>, где <tex> S_i </tex> {{---}} длина НВП, которая заканчивается на <tex>a_i</tex>, <tex> T_i </tex> {{---}} длина НУП, которая начинается на <tex>a_i</tex>.

Докажем, что все пары <tex>(S_i, T_i)</tex> различны.
Пусть существуют такие <tex>i < j</tex> , что <tex> S_i </tex> = <tex> S_j </tex> и <tex> T_i </tex> = <tex> T_j</tex>. Если <tex>a_i < a_j</tex>, тогда <tex> a_j </tex> можно добавить к НВП, заканчивающейся на <tex> a_i </tex>, следовательно <tex>S_j \geqslant S_i + 1</tex>. Если <tex>a_i > a_j</tex>, то по аналогии <tex>T_i \geqslant T_j + 1</tex>. Противоречие! Следовательно все такие пары различны.

Заметим что <tex>1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k</tex>, поэтому существуют <tex>l k</tex> различных пар <tex> (S_i, T_i) </tex>. Если <tex>l k < n</tex> тогда среди <tex> n </tex> пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. <tex>l k \geqslant n</tex>, ч. т. д.
}}

== Следствие из теоремы ==

{{Утверждение
|statement=
Пусть <tex>n</tex> {{---}} длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше <tex>\sqrt{n}</tex>.
}}

==См. также==
* [[Задача о минимуме/максимуме скалярного произведения]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.9D.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D0.B5_.D0.B2.D0.B8.D0.B4.D1.8B_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9 Википедия {{---}} Последовательность]

*[http://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Свойства комбинаторных объектов]]

Задача о минимуме/максимуме скалярного произведения

2017-12-24T15:07:03Z

Haposiwe: Изменения в "см. также"

{{
Задача
|definition=Необходимо найти минимальную/максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел.
}}
== Решение ==
Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + \ldots + x_m y_m</tex>
{{
Теорема
|about=о минимуме/максимуме скалярного произведениях<ref name = "wiki" />
|statement=Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности <tex>x_1 \ldots x_m</tex> и убывающей последовательности <tex>y_1 \ldots y_m</tex>. При сопоставлении возрастающей <tex>y_1 \ldots y_m</tex> достигается максимум.

|proof=
Будем считать, что последовательность <tex>x_i</tex> отсортирована по возрастанию. Покажем, что если существуют пары чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, такие что <tex>x_i < x_j</tex> и <tex>y_i < y_j</tex>, то скалярное произведение можно уменьшить, поменяв местами <tex>y_i</tex> и <tex>y_j</tex>. Так как в нашем случае <tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j y_j > x_j y_i + x_i y_j</tex>, а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>, и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, таких что <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным.
}}

Данная теорема нашла себе практическое применение в теории [[Теорема Радо-Эдмондса (жадный алгоритм)|матроидов]] и [[Flow shop| расписаний]].

== Примечания ==
<references>
<ref name = "wiki">[https://ru.wikipedia.org/wiki/Перестановочное_неравенство Википедия {{---}} Перестановочное неравенство]</ref>
</references>

==См. также==
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
* [[Теорема Кэли]]
* [[Матричное представление перестановок]]

== Источники информации ==
* Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Свойства комбинаторных объектов]]

Нахождение количества разбиений числа на слагаемые

2017-12-24T15:03:11Z

Haposiwe: Отмена правки 62911 участника Haposiwe (обсуждение)

{{Задача
|definition =
По заданному числу <tex>n</tex> найти количество его различных разбиений на положительные слагаемые<ref name="amount" /> <tex> m_0 + m_1 + m_2 + \dots + m_k = n </tex> так, что при всех <tex> i: m_i \leqslant m_{i+1} </tex>.}}

__TOC__

== Алгоритм за O(N3)==
Пусть <tex>P(n, m, k)</tex> — количество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не превосходит <tex>k</tex>.
Имеет место следующее рекуррентное соотношение:

<tex dpi = "145">P(n, m, k) =
\left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 < m \leqslant n, 0 < k \leqslant n \\
1, & n = 0, m = 0 \\
0, & \text{otherwise} \end{array} \right.
</tex>


Рассмотрим множество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не больше <tex>k</tex>. Разделим его на две непересекающиеся группы — в первой будут все
разбиения, которые не содержат в качестве старшего слагаемого <tex>k</tex>. Таких разбиений <tex>P(n, m, k - 1)</tex>. Во второй — все разбиения со старшим слагаемым <tex>k</tex>. Их столько же, сколько разбиений числа <tex>n - k</tex> на <tex>m - 1</tex> слагаемое, каждое из которых не больше <tex>k</tex>, то есть <tex>P(n - k, m - 1, k)</tex>.

Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(n, i, n)</tex>. Реализация данного алгоритма методом [[Динамическое программирование|динамического программирования]] с мемоизацией будет иметь асимптотику <tex>O(n^{3})</tex>.

== Алгоритм за O(N2) ==
Обозначим <tex>P(n,k)</tex> — количество разбиений числа <tex>n</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>. Оно удовлетворяет следующей рекурентной формуле:
<tex dpi="145">P(n,k) = \left \{
\begin{array}{ll} P(n,k - 1) + P(n - k, k), & 0 < k \leqslant n \\
P(n, n), & k > n \\
1, & n = 0, k = 0 \\
0, & n \neq 0 , k = 0 \end{array} \right.</tex>


Заметим, что нам не нужно считать количество слагаемых <tex>m</tex> в разбиении. Достаточно посчитать <tex>P(n, k)</tex> — количество разбиений числа <tex>n</tex> на произвольное количество слагаемых, каждое из которых не больше <tex>k</tex>. Рассмотрим множество таких разбиений. Разделим его на две непересекающиеся группы. В первую войдут те разбиения, в которых отсутствует слагаемое <tex>k</tex>. Очевидно, таких разбиений <tex>P(n, k - 1)</tex>. Во второй группе — те разбиения, в которые слагаемое <tex>k</tex> вошло. Их количество совпадает с количеством разбиений числа <tex>n - k</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>, и равно <tex>P(n - k, k)</tex>.

Количество всех разбиений числа <tex>n</tex> равно <tex>P(n,n)</tex>. Асимптотика <tex>O(n^{2})</tex>.

== Алгоритм за O(N3/2) ==
Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа <tex>n</tex> на слагаемые, который работает за <tex> O(n \sqrt{n}) </tex>.

Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.

Рассмотрим следующее бесконечное произведение:

<tex> (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^{2k} + \dots) \dots </tex>

После раскрытия скобок каждый член произведения получается в результате умножения мономов (одночленов), взятых по одному из каждой скобки. Если в первой скобке взять <tex dpi = "145">x^{m_1}</tex>, во второй — <tex dpi = "145">x^{2m_2}</tex> и т.д., то их произведение будет равно <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}.</tex> Значит, после раскрытия скобок получится сумма мономов вида <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}</tex>.

Можно увидеть, что <tex> x^n </tex> встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить <tex>n</tex> как сумму <tex>m_1 + 2m_2 + 3m_3 + ...</tex> Каждому такому представлению отвечает разбиение числа <tex>n</tex> на <tex>m_1</tex> единиц, <tex>m_2</tex> двоек и т.д. Таким образом, очевидно, получаются все разбиения, так как из первой скобки мы можем взять любое <tex>x^{m_i}</tex>, где <tex>m_i \in [0 \dots \infty),</tex> то есть произвольное количество единиц в нашем разбиении. Аналогично, мы можем взять произвольное количество двоек и т.д. Но при раскрытии скобок мы находим произведения всех возможных комбинации множителей из разных скобок. Поэтому коэффициент при <tex>x^n</tex> равен числу разбиений <tex>p(n)</tex>.

Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. Полагая <tex>0 \leqslant x < 1</tex>, по формуле ее суммирования:
: <tex dpi = "145">1 + x + x^2 + x^3 + \dots = \frac{1}{1 - x}</tex>,
: <tex dpi = "145">1 + x^2 + x^4 + x^6 + \dots = \frac{1}{1-x^2}</tex>
: <tex>\dots</tex>
: <tex dpi = "145">1 + x^k + x^{2k} + x^{3k} + \dots = \frac{1}{1-x^k}</tex>
: <tex>\dots</tex>

Запишем теперь [[Производящая функция|производящую функцию]] последовательности <tex>p(n)</tex>:
: <tex dpi = "145">p(0) + p(1) x + p(2) x^2 + p(3) x^3 + \dots = \frac{1}{(1-x)(1-x^2)(1-x^3)\dots}</tex>                                                           <tex>(1)</tex>

Рассмотрим произведение <tex>(1-x)(1-x^2)(1-x^3)...</tex>, т.е. знаменатель правой части формулы <tex>(1)</tex>. Раскрывая в нём скобки, получим следующий результат:
: <tex>(1 - x)(1 - x^2)(1 - x^3) ... = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - x^{35} - x^{40} + ...</tex>
Показатели степеней в правой части — пятиугольные числа<ref name="pentagon" />, т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</tex>. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема, впоследствии названная его именем.

{{Теорема
| about =
Пентагональная теорема Эйлера
| statement =
<tex dpi="145"> \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{q=-\infty}^\infty (-1)^q x^{\frac{3q^2+q}{2}}</tex>
| proof =
<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>

Раскроем в этом произведении первые <tex>22</tex> скобки. Мы получим выражение

<tex>A = [1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...]\times(1-x^{23})(1-x^{24})...(1-x^n)...</tex>,

где в квадратной скобке точками обозначены слагаемые, содержащие <tex>x</tex> в более высокой степени, чем <tex>22</tex>. Не будем выписывать эти члены, так как после умножения квадратной скобки на <tex>1-x^{23}</tex>, <tex>1-x^{24}</tex> и т.д. они изменятся. Выписанные же члены больше меняться не будут. Поэтому, если раскрыть все скобки, то получится бесконечный ряд, первые члены которого имеют вид

<tex>A=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...</tex>

Анализируя этот ряд, Эйлер пришел к выводу, что, если превратить бесконечное произведение

<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>

в ряд, то в этом ряду отличны от нуля лишь слагаемые, вида <tex dpi="145">(-1)^q x^{\frac{3q^2+q}{2}}</tex>, где <tex>q</tex> — натуральное число.

При раскрытии скобок в исходном произведении слагаемое <tex>\pm x^N</tex> встретится столько раз, сколькими способами можно разбить число <tex>N</tex> на различные слагаемые. При этом, если число слагаемых четно, то появляется <tex>x^N</tex>, а если это число нечетно, то появляется <tex>-x^N</tex>. Например, разбиению <tex>12=5+4+2+1</tex> соответствует слагаемое <tex>(-x^5)(-x^4)(-x^2)(-x^1)=x^{12},</tex> а разбиению <tex>12=5+4+3</tex> — слагаемое <tex>(-x^5)(-x^4)(-x^3)=-x^{12}</tex>. Таким образом, коэффициент при <tex>x^N</tex> в разложении <tex>A</tex> в ряд равен разности между количеством разбиений <tex>N</tex> на четное число различных слагаемых и количеством разбиений <tex>N</tex> на нечетное число различных слагаемых. Тогда теорему можно переформулировать следующим образом:

{{Теорема
| about =
Переформулировка пентагональной теоремы
| statement =
Если число <tex>N</tex> не может быть представлено в виде <tex dpi="145">N =\frac{3q^2+q}{2}</tex>, то оно имеет одинаковое количество разбиений на четное и на нечетное число различных слагаемых. А для чисел вида <tex dpi="145">N =\frac{3q^2+q}{2}</tex> разность между этими количествами равна <tex>(-1)^q</tex>.
}}

Иными словами, если <tex>q</tex> четно, то на одно больше разбиений на четное число слагаемых, а если <tex>q</tex> нечетно, то на одно больше разбиений на нечетное число слагаемых. Докажем эту теорему с помощью диаграмм Юнга<ref name="young" />. Покажем несколько способов превращения диаграммы с четным числом строк диаграмму из стольких же точек с нечетным числом строк и обратно.

Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через <tex>m</tex>, а число строк нижней трапеции через <tex>n</tex> (на рис. 1 слева изображена диаграмма, для которой <tex>m=2</tex>, <tex>n=3</tex>).
[[Файл:Diagramma_2_3.jpg|thumb|right|500px|Рис. 1. <tex>m = 2, n = 3</tex>]]

'''Преобразование 1.''' Предположим, что диаграмма содержит не менее двух трапеций, причем <tex>m \leqslant n</tex>. В этом случае отбросим первую строку из <tex>m</tex> точек, но удлиним последние <tex>m</tex> строк нижней трапеции на одну точку (рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.

Точно такое же преобразование можно сделать, если диаграмма состоит из одной трапеции, но <tex>n \geqslant m+1</tex>. Стираем верхнюю строку и к нижним <tex>n-1</tex> строчкам приписываем <tex>m</tex> точек.

'''Преобразование 2.'''Пусть теперь диаграмма опять содержит не менее двух трапеций, но <tex>m > n</tex>. Тогда от каждой строки последней трапеции возьмем по одной точке и составим из них первую строку (из <tex> n </tex> точек) новой диаграммы. Это можно сделать, так как <tex>m > n</tex>, и поэтому составленная строка короче первой строки исходной диаграммы. Кроме того, так как мы взяли все строки будут иметь различную длину. Наконец, новая диаграмма содержит столько же точек, что и исходная, но четность числа строк изменилась - новая диаграмма содержит еще одну строку.

Преобразование 2 допускают и диаграммы, состоящие из одной трапеции, если <tex>n \leqslant m - 2</tex> (появляющаяся первая строка состоит из <tex>n</tex> точек, она должна быть короче бывшей первой строки, уменьшившейся до <tex>m-1</tex> точки).

Легко видеть, что описанные преобразования взаимно обратны - если сначала сделать одно из них, а потом второе, то снова получим исходную диаграмму. Кроме того, для каждой диаграммы может быть допустимо лишь одно из этих преобразований. Таким образом, диаграммы разбиений числа <tex>N</tex>, допускающие одно из этих преобразований, распадаются на пары диаграмм с четным и нечетным числом строк, поэтому их одинаковое число.

Осталось выяснить, какие же диаграммы не допускают ни одного из описанных преобразований. Ясно, что эти диаграммы состоят из одной трапеции, причем для них либо <tex>m=n</tex>, либо <tex>m=n+1</tex>. В первом случае диаграмма содержит

<tex dpi="145">n+(n+1)+(n+2)+\dots+(2n-1)=\frac{3n^2-n}{2}</tex>

точек, а во втором - на <tex>n</tex> точек больше, т.е. <tex dpi="145">\frac{3n^2+n}{2}</tex>.

Приведенные рассуждения показывают, что если <tex>N</tex> не является числом вида <tex dpi="145">\frac{3n^2 \pm n}{2}</tex>, то оно имеет поровну разбиений на четное и нечетное число различных слагаемых.

Очевидно также, что равенства <tex dpi="145">N=\frac{3n^2+n}{2}</tex> и <tex dpi="145">N=\frac{3l^2-l}{2}</tex> одновременно выполняться не могут, поэтому если <tex dpi ="145">N=\frac{3n^2\pm n}{2}</tex>, то без пары останется ровно одна диаграмма, не допускающая преобразования и имеющая <tex>n</tex> строк (слагаемых <tex>N</tex>). Если <tex>n</tex> - четное число, то разбиений на четное число слагаемых окажется на <tex>1</tex> больше, чем на нечетное число слагаемых. Если же <tex>n</tex> - нечетное число, то на <tex>1</tex> больше будет разбиений на нечетное число слагаемых. Теорема доказана.

}}

Умножим обе части равенства <tex>(1)</tex> на <tex>\prod\limits_{k=1}^\infty \left(1-x^k \right) </tex> и воспользуемся пентагональной теоремой:
: <tex> ( p(0) + p(1) x + p(2) x^2 + \dots)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots) = 1 </tex>      <tex>(2)</tex>

Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями <tex>x</tex> пишем друг под другом:
: <tex> p(0) + p(1)x + p(2) x^2 + p(3) x^3 + p(4) x^4 + p(5) x^5 + p(6) x^6 + \dots </tex>
::    <tex> - p(0)x - p(1) x^2 - p(2) x^3 - p(3) x^4 - p(4) x^5 - p(5) x^6 - \dots </tex>
::::       <tex> - p(0) x^2 - p(1) x^3 - p(2) x^4 - p(3) x^5 - p(4) x^6 - \dots </tex>
:::::::::::::  <tex>+ p(0) x^5 + p(1) x^6 + \dots </tex>

Так как <tex>p(0) = 1</tex>, то оно сокращается с единицей справа. Так что, чтобы выражение <tex>(2)</tex> было удовлетворено при любом <tex>x</tex>, все коэффициенты должны быть равны <tex>0</tex>. Поэтому:
: <tex> p(1) = p(0) </tex>
: <tex> p(2) = p(1) + p(0) </tex>
: <tex> p(3) = p(2) + p(1) </tex>
: <tex> p(4) = p(3) + p(2) </tex>
: <tex> p(5) = p(4) + p(3) - p(0) </tex>
: <tex>...</tex>

Получаем формулу Эйлера, позволяющую последовательно находить числа <tex>p(n)</tex>:
: <tex dpi="145"> p(n) = p(n-1) + p(n-2)+ ... + (-1)^{q+1} (p\left(n - \frac{3q^2 - q}{2}\right) + p\left(n - \frac{3q^2 + q}{2}\right)) </tex>.

Асимптотика <tex> O(n \sqrt{n}) </tex> получается следующим образом. Так как <tex dpi="145"> n - \frac{3q^2 + q}{2} \geqslant 0 </tex> , то получаем <tex> q </tex> порядка <tex> \sqrt{n} </tex>, а так как находим <tex>n</tex>-е число, то получаем <tex> O(n \sqrt{n}) </tex>.

== Примечания ==
<references>
<ref name="amount">[http://oeis.org/A000041 Последовательность 000041 на OEIS]</ref>
<ref name="pentagon">[http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B3%D1%83%D1%80%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.9F.D1.8F.D1.82.D0.B8.D1.83.D0.B3.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B5_.D1.87.D0.B8.D1.81.D0.BB.D0.B0 Википедия {{---}} Пятиугольные числа]</ref>
<ref name="young">[http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.94.D0.B8.D0.B0.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D1.8B_.D0.AE.D0.BD.D0.B3.D0.B0 Википедия {{---}} Диаграммы Юнга]</ref>
</references>

==См. также==
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Производящая функция]]

== Источники информации ==
* [http://en.wikipedia.org/wiki/Pentagonal_number_theorem Wikipedia {{---}} Pentagonal number theorem]
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* Н.Я. Виленкин "Комбинаторика", 2007. стр. 138-141.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

ДНФ

2017-12-24T14:54:05Z

Haposiwe: Пофикшена СКНФ для медианы от 5 аргументов

== ДНФ ==
{{Определение
|definition =
'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая конъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.

== СДНФ ==
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — ДНФ, удовлетворяющая условиям:
* в ней нет одинаковых простых конъюнкций,
* каждая простая конъюнкция полная.
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':

<tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \ldots ,x_{i-1},0,x_{i+1}, \ldots ,x_n) \vee
x_i \wedge f(x_1, \ldots ,x_{i-1},1,x_{i+1}, \ldots ,x_n)</tex>.

Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу:
<tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,\ldots,0,0)~\vee~</tex>

<tex>\neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,\ldots,0,1) ~\vee~ \\
\ldots \\
~\vee~ x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,\ldots,1,0) ~\vee~\\
x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge x_n \wedge f(1,1,\ldots,1) </tex>

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}

== Алгоритм построения СДНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные конъюнкции связываем операциями дизъюнкции.

== Пример построения СДНФ для медианы==
=== Построение СДНФ для медианы от трех аргументов ===
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
|}

3. Все полученные конъюнкции связываем операциями дизъюнкции:

<tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

=== Построение СДНФ для медианы от пяти аргументов ===
{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 1 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 0 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || 0 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 0 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || 0 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 0 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>
|}

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (\overline {x_1} \land \overline {x_2} \land x_3 \land x_4 \land x_5) \lor (\overline {x_1} \land x_2 \land \overline {x_3} \land x_4 \land x_5) \lor (\overline {x_1} \land x_2 \land x_3 \land \overline {x_4} \land x_5) \lor (\overline {x_1} \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \lor (\overline {x_1} \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline {x_2} \land \overline {x_3} \land x_4 \land x_5) \lor (x_1 \land \overline {x_2} \land x_3 \land \overline {x_4} \land x_5) \lor (x_1 \land \overline {x_2} \land x_3 \land x_4 \land \overline {x_5}) \lor (x_1 \land \overline {x_2} \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land \overline {x_3} \land \overline {x_4} \land x_5) \lor (x_1 \land x_2 \land \overline {x_3} \land x_4 \land \overline {x_5}) \lor (x_1 \land x_2 \land \overline {x_3} \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land \overline {x_4} \land \overline {x_5}) \lor (x_1 \land x_2 \land x_3 \land \overline {x_4} \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline {x_5}) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>.

==Примеры СДНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg {x} \land \neg {y})</tex>.

Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>.

== См. также ==

* [[Сокращенная и минимальная ДНФ]]
* [[КНФ]]

==Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

КНФ

2017-12-24T14:50:10Z

Haposiwe: Исправлена СКНФ для медианы от 5 аргументов

== КНФ ==
{{Определение
|definition =
'''Простой дизъюнкцией''' (англ. ''inclusive disjunction'') или '''дизъюнктом''' (англ. ''disjunct'') называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая дизъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно один раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Пример КНФ:
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex>

== СКНФ ==
{{Определение
|definition =
'''Совершенная конъюнктивная нормальная форма, СКНФ''' (англ. ''perfect conjunctive normal form, PCNF'') — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых дизъюнкций
* каждая простая дизъюнкция полная
}}
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})</tex>

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
|proof =
Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:
<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>

Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}})}) </tex>

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.
}}

== Алгоритм построения СКНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
# Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные дизъюнкции связываем операциями конъюнкции.

== Пример построения СКНФ для медианы==
=== Построение СКНФ для медианы от трех аргументов ===
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \neg{z})</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1 ||
|}

3. Все полученные дизъюнкции связываем операциями конъюнкции.

<tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{y} \lor z) \land ( x \lor y \lor \neg{z})</tex>

=== Построение СКНФ для медианы от пяти аргументов ===

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 1 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 0 || 1 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 1 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 1 || 1 || 1 ||
|}

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land \\ (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline {x_4} \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land \\ (x_1 \lor x_2 \lor \overline {x_3} \lor x_4 \lor \overline {x_5}) \land (x_1 \lor x_2 \lor \overline {x_3} \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline {x_2} \lor x_3 \lor x_4 \lor \overline {x_5}) \land (x_1 \lor \overline {x_2} \lor x_3 \lor \overline {x_4} \lor x_5) \land (x_1 \lor \overline {x_2} \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline {x_5}) \land (\overline {x_1} \lor x_2 \lor x_3 \lor \overline {x_4} \lor x_5) \land (\overline {x_1} \lor x_2 \lor \overline {x_3} \lor x_4 \lor x_5) \land (\overline {x_1} \lor \overline {x_2} \lor x_3 \lor x_4 \lor x_5) </tex>

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) </tex>

Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>

== См. также ==

* [[Специальные формы КНФ]]
* [[ДНФ]]

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская {{---}} Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

КНФ

2017-12-23T20:13:30Z

Haposiwe: giuytngfldld

== КНФ ==
{{Определение
|definition =
'''Простой дизъюнкцией''' (англ. ''inclusive disjunction'') или '''дизъюнктом''' (англ. ''disjunct'') называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая дизъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно один раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Пример КНФ:
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex>

== СКНФ ==
{{Определение
|definition =
'''Совершенная конъюнктивная нормальная форма, СКНФ''' (англ. ''perfect conjunctive normal form, PCNF'') — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых дизъюнкций
* каждая простая дизъюнкция полная
}}
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})</tex>

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
|proof =
Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:
<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>

Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}})}) </tex>

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.
}}

== Алгоритм построения СКНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
# Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные дизъюнкции связываем операциями конъюнкции.

== Пример построения СКНФ для медианы==
=== Построение СКНФ для медианы от трех аргументов ===
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \neg{z})</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1 ||
|}

3. Все полученные дизъюнкции связываем операциями конъюнкции.

<tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{y} \lor z) \land ( x \lor y \lor \neg{z})</tex>

=== Построение СКНФ для медианы от пяти аргументов ===

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 1 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 0 || 1 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 1 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 1 || 1 || 1 ||
|}

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor \overline{x_2} \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor \overline{x_2} \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor \overline{x_5}) </tex>

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) </tex>

Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>

== См. также ==

* [[Специальные формы КНФ]]
* [[ДНФ]]

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская {{---}} Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

ДНФ

2017-12-23T20:07:21Z

Haposiwe: Добавлены разделы для медианы от трех и пяти аргументов

== ДНФ ==
{{Определение
|definition =
'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая конъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.

== СДНФ ==
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — ДНФ, удовлетворяющая условиям:
* в ней нет одинаковых простых конъюнкций,
* каждая простая конъюнкция полная.
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':

<tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \ldots ,x_{i-1},0,x_{i+1}, \ldots ,x_n) \vee
x_i \wedge f(x_1, \ldots ,x_{i-1},1,x_{i+1}, \ldots ,x_n)</tex>.

Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу:
<tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,\ldots,0,0)~\vee~</tex>

<tex>\neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,\ldots,0,1) ~\vee~ \\
\ldots \\
~\vee~ x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,\ldots,1,0) ~\vee~\\
x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge x_n \wedge f(1,1,\ldots,1) </tex>

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}

== Алгоритм построения СДНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные конъюнкции связываем операциями дизъюнкции.

== Пример построения СДНФ для медианы==
=== Построение СДНФ для медианы от трех аргументов ===
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
|}

3. Все полученные конъюнкции связываем операциями дизъюнкции:

<tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

=== Построение СДНФ для медианы от пяти аргументов ===
{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 1 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 0 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || 0 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 0 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || 0 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 0 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>
|}

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \land x_2 \land x_3 \land \overline{x_4} \land \overline{x_5}) \lor (x_1 \land x_2 \land \overline{x_3} \land x_4 \land \overline{x_5}) \lor \\ (x_1 \land \overline{x_2} \land x_3 \land x_4 \land \overline{x_5}) \lor (\overline{x_1} \land x_2 \land x_3 \land x_4 \land \overline{x_5}) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline{x_5}) \lor \\ (x_1 \land x_2 \land \overline{x_3} \land \overline{x_4} \land x_5) \lor (x_1 \land \overline{x_2} \land x_3 \land \overline{x_4} \land x_5) \lor (\overline{x_1} \land x_2 \land x_3 \land \overline{x_4} \land x_5) \lor \\ (x_1 \land x_2 \land x_3 \land \overline{x_4} \land x_5) \lor (x_1 \land \overline{x_2} \land \overline{x_3} \land x_4 \land x_5) \lor (\overline{x_1} \land x_2 \land \overline{x_3} \land x_4 \land x_5) \lor (x_1 \land x_2 \land \overline{x_3} \land x_4 \land x_5) \lor (\overline{x_1} \land \overline{x_2} \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline{x_2} \land x_3 \land x_4 \land x_5) \lor (\overline{x_1} \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5) </tex>.

==Примеры СДНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg {x} \land \neg {y})</tex>.

Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>.

== См. также ==

* [[Сокращенная и минимальная ДНФ]]
* [[КНФ]]

==Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

КНФ

2017-12-23T19:07:24Z

Haposiwe: Добавлена таблица истинность для медианы от 5 аргументов

== КНФ ==
{{Определение
|definition =
'''Простой дизъюнкцией''' (англ. ''inclusive disjunction'') или '''дизъюнктом''' (англ. ''disjunct'') называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая дизъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно один раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Пример КНФ:
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex>

== СКНФ ==
{{Определение
|definition =
'''Совершенная конъюнктивная нормальная форма, СКНФ''' (англ. ''perfect conjunctive normal form, PCNF'') — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых дизъюнкций
* каждая простая дизъюнкция полная
}}
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})</tex>

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
|proof =
Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:
<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>

Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}})}) </tex>

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.
}}

== Алгоритм построения СКНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
# Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные дизъюнкции связываем операциями конъюнкции.

== Пример построения СКНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \neg{z})</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1 ||
|}

3. Все полученные дизъюнкции связываем операциями конъюнкции.

<tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{y} \lor z) \land ( x \lor y \lor \neg{z})</tex>

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) </tex>

Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>

Медиана 5 аргументов:

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 0 || 1 || 1 || 0 || <tex>(x_1 \lor x_2 \lor x_3 \lor \neg {x_4} \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 0 || 1 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 1 || 0 || 0 || <tex>(x_1 \lor x_2 \lor \neg {x_3} \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 0 || 1 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 1 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 0 || 0 || 0 || <tex>(x_1 \lor \neg {x_2} \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 0 || 1 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor x_4 \lor \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 1 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor x_3 \lor \neg {x_4} \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor x_2 \lor \neg {x_3} \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 0 || 0 || 0 || <tex>(\neg {x_1} \lor \neg {x_2} \lor x_3 \lor x_4 \lor x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 1 || 1 || 1 || 1 ||
|}

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor \overline{x_2} \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor \overline{x_2} \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor \overline{x_5}) </tex>
== См. также ==

* [[Специальные формы КНФ]]
* [[ДНФ]]

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская {{---}} Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

КНФ

2017-12-23T19:01:43Z

Haposiwe: Добавлено "см. также"

== КНФ ==
{{Определение
|definition =
'''Простой дизъюнкцией''' (англ. ''inclusive disjunction'') или '''дизъюнктом''' (англ. ''disjunct'') называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая дизъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно один раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Пример КНФ:
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex>

== СКНФ ==
{{Определение
|definition =
'''Совершенная конъюнктивная нормальная форма, СКНФ''' (англ. ''perfect conjunctive normal form, PCNF'') — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых дизъюнкций
* каждая простая дизъюнкция полная
}}
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})</tex>

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
|proof =
Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:
<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>

Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}})}) </tex>

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.
}}

== Алгоритм построения СКНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
# Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные дизъюнкции связываем операциями конъюнкции.

== Пример построения СКНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \neg{z})</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1 ||
|}

3. Все полученные дизъюнкции связываем операциями конъюнкции.

<tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{y} \lor z) \land ( x \lor y \lor \neg{z})</tex>

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) </tex>

Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>

Медиана 5 аргументов:

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor \overline{x_2} \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor \overline{x_2} \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor \overline{x_5}) </tex>
== См. также ==

* [[Специальные формы КНФ]]
* [[ДНФ]]

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская {{---}} Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

ДНФ

2017-12-23T18:57:45Z

Haposiwe: Добавлена таблица истинности для медианы от 5 аргументов

== ДНФ ==
{{Определение
|definition =
'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая конъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.

== СДНФ ==
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — ДНФ, удовлетворяющая условиям:
* в ней нет одинаковых простых конъюнкций,
* каждая простая конъюнкция полная.
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':

<tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \ldots ,x_{i-1},0,x_{i+1}, \ldots ,x_n) \vee
x_i \wedge f(x_1, \ldots ,x_{i-1},1,x_{i+1}, \ldots ,x_n)</tex>.

Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу:
<tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,\ldots,0,0)~\vee~</tex>

<tex>\neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,\ldots,0,1) ~\vee~ \\
\ldots \\
~\vee~ x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,\ldots,1,0) ~\vee~\\
x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge x_n \wedge f(1,1,\ldots,1) </tex>

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}

== Алгоритм построения СДНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные конъюнкции связываем операциями дизъюнкции.

== Пример построения СДНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
|}

3. Все полученные конъюнкции связываем операциями дизъюнкции:

<tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

==Примеры СДНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg {x} \land \neg {y})</tex>.

Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>.

Медиана 5 аргументов:

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x_1 </tex>||<tex> x_2 </tex>||<tex> x_3 </tex>||<tex>x_4</tex>||<tex> x_5 </tex>||<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 1 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 0 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 0 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 0 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || 0 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || 1 || 1 || <tex>(\neg {x_1} \land x_2 \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 0 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 0 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || 0 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || 1 || 1 || <tex>(x_1 \land \neg {x_2} \land x_3 \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 1 || 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land \neg {x_3} \land x_4 \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 0 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 0 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land \neg {x_4} \land x_5)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || 0 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land \neg {x_5})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || 1 || 1 || <tex>(x_1 \land x_2 \land x_3 \land x_4 \land x_5)</tex>
|}

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \land x_2 \land x_3 \land \overline{x_4} \land \overline{x_5}) \lor (x_1 \land x_2 \land \overline{x_3} \land x_4 \land \overline{x_5}) \lor \\ (x_1 \land \overline{x_2} \land x_3 \land x_4 \land \overline{x_5}) \lor (\overline{x_1} \land x_2 \land x_3 \land x_4 \land \overline{x_5}) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline{x_5}) \lor \\ (x_1 \land x_2 \land \overline{x_3} \land \overline{x_4} \land x_5) \lor (x_1 \land \overline{x_2} \land x_3 \land \overline{x_4} \land x_5) \lor (\overline{x_1} \land x_2 \land x_3 \land \overline{x_4} \land x_5) \lor \\ (x_1 \land x_2 \land x_3 \land \overline{x_4} \land x_5) \lor (x_1 \land \overline{x_2} \land \overline{x_3} \land x_4 \land x_5) \lor (\overline{x_1} \land x_2 \land \overline{x_3} \land x_4 \land x_5) \lor (x_1 \land x_2 \land \overline{x_3} \land x_4 \land x_5) \lor (\overline{x_1} \land \overline{x_2} \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline{x_2} \land x_3 \land x_4 \land x_5) \lor (\overline{x_1} \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5) </tex>.
== См. также ==

* [[Сокращенная и минимальная ДНФ]]
* [[КНФ]]

==Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

Задача о минимуме/максимуме скалярного произведения

2017-12-23T17:53:35Z

Haposiwe: Добавлены\изменены \ldots. Пофикшена ссылка

{{
Задача
|definition=Необходимо найти минимальную/максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел.
}}
== Решение ==
Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + \ldots + x_m y_m</tex>
{{
Теорема
|about=о минимуме/максимуме скалярного произведениях<ref name = "wiki" />
|statement=Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности <tex>x_1 \ldots x_m</tex> и убывающей последовательности <tex>y_1 \ldots y_m</tex>. При сопоставлении возрастающей <tex>y_1 \ldots y_m</tex> достигается максимум.

|proof=
Будем считать, что последовательность <tex>x_i</tex> отсортирована по возрастанию. Покажем, что если существуют пары чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, такие что <tex>x_i < x_j</tex> и <tex>y_i < y_j</tex>, то скалярное произведение можно уменьшить, поменяв местами <tex>y_i</tex> и <tex>y_j</tex>. Так как в нашем случае <tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j y_j > x_j y_i + x_i y_j</tex>, а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>, и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, таких что <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным.
}}

Данная теорема нашла себе практическое применение в теории [[Теорема Радо-Эдмондса (жадный алгоритм)|матроидов]] и [[Flow shop| расписаний]].

== Примечания ==
<references>
<ref name = "wiki">[https://ru.wikipedia.org/wiki/Перестановочное_неравенство Википедия {{---}} Перестановочное неравенство]</ref>
</references>

==См. также==
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Матричное представление перестановок]]

== Источники информации ==
* Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Свойства комбинаторных объектов]]

Нахождение количества разбиений числа на слагаемые

2017-12-23T17:09:08Z

Haposiwe: Добавлено "см. также"

{{Задача
|definition =
По заданному числу <tex>n</tex> найти количество его различных разбиений на положительные слагаемые<ref name="amount" /> <tex> m_0 + m_1 + m_2 + \dots + m_k = n </tex> так, что при всех <tex> i: m_i \leqslant m_{i+1} </tex>.}}

__TOC__

== Алгоритм за <tex>O(N^3)</tex>==
Пусть <tex>P(n, m, k)</tex> — количество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не превосходит <tex>k</tex>.
Имеет место следующее рекуррентное соотношение:

<tex dpi = "145">P(n, m, k) =
\left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 < m \leqslant n, 0 < k \leqslant n \\
1, & n = 0, m = 0 \\
0, & \text{otherwise} \end{array} \right.
</tex>


Рассмотрим множество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не больше <tex>k</tex>. Разделим его на две непересекающиеся группы — в первой будут все
разбиения, которые не содержат в качестве старшего слагаемого <tex>k</tex>. Таких разбиений <tex>P(n, m, k - 1)</tex>. Во второй — все разбиения со старшим слагаемым <tex>k</tex>. Их столько же, сколько разбиений числа <tex>n - k</tex> на <tex>m - 1</tex> слагаемое, каждое из которых не больше <tex>k</tex>, то есть <tex>P(n - k, m - 1, k)</tex>.

Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(n, i, n)</tex>. Реализация данного алгоритма методом [[Динамическое программирование|динамического программирования]] с мемоизацией будет иметь асимптотику <tex>O(n^{3})</tex>.

== Алгоритм за <tex>O(N^2)</tex> ==
Обозначим <tex>P(n,k)</tex> — количество разбиений числа <tex>n</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>. Оно удовлетворяет следующей рекурентной формуле:
<tex dpi="145">P(n,k) = \left \{
\begin{array}{ll} P(n,k - 1) + P(n - k, k), & 0 < k \leqslant n \\
P(n, n), & k > n \\
1, & n = 0, k = 0 \\
0, & n \neq 0 , k = 0 \end{array} \right.</tex>


Заметим, что нам не нужно считать количество слагаемых <tex>m</tex> в разбиении. Достаточно посчитать <tex>P(n, k)</tex> — количество разбиений числа <tex>n</tex> на произвольное количество слагаемых, каждое из которых не больше <tex>k</tex>. Рассмотрим множество таких разбиений. Разделим его на две непересекающиеся группы. В первую войдут те разбиения, в которых отсутствует слагаемое <tex>k</tex>. Очевидно, таких разбиений <tex>P(n, k - 1)</tex>. Во второй группе — те разбиения, в которые слагаемое <tex>k</tex> вошло. Их количество совпадает с количеством разбиений числа <tex>n - k</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>, и равно <tex>P(n - k, k)</tex>.

Количество всех разбиений числа <tex>n</tex> равно <tex>P(n,n)</tex>. Асимптотика <tex>O(n^{2})</tex>.

== Алгоритм за <tex>O(N^{3/2})</tex> ==
Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа <tex>n</tex> на слагаемые, который работает за <tex> O(n \sqrt{n}) </tex>.

Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.

Рассмотрим следующее бесконечное произведение:

<tex> (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^{2k} + \dots) \dots </tex>

После раскрытия скобок каждый член произведения получается в результате умножения мономов (одночленов), взятых по одному из каждой скобки. Если в первой скобке взять <tex dpi = "145">x^{m_1}</tex>, во второй — <tex dpi = "145">x^{2m_2}</tex> и т.д., то их произведение будет равно <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}.</tex> Значит, после раскрытия скобок получится сумма мономов вида <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}</tex>.

Можно увидеть, что <tex> x^n </tex> встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить <tex>n</tex> как сумму <tex>m_1 + 2m_2 + 3m_3 + ...</tex> Каждому такому представлению отвечает разбиение числа <tex>n</tex> на <tex>m_1</tex> единиц, <tex>m_2</tex> двоек и т.д. Таким образом, очевидно, получаются все разбиения, так как из первой скобки мы можем взять любое <tex>x^{m_i}</tex>, где <tex>m_i \in [0 \dots \infty),</tex> то есть произвольное количество единиц в нашем разбиении. Аналогично, мы можем взять произвольное количество двоек и т.д. Но при раскрытии скобок мы находим произведения всех возможных комбинации множителей из разных скобок. Поэтому коэффициент при <tex>x^n</tex> равен числу разбиений <tex>p(n)</tex>.

Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. Полагая <tex>0 \leqslant x < 1</tex>, по формуле ее суммирования:
: <tex dpi = "145">1 + x + x^2 + x^3 + \dots = \frac{1}{1 - x}</tex>,
: <tex dpi = "145">1 + x^2 + x^4 + x^6 + \dots = \frac{1}{1-x^2}</tex>
: <tex>\dots</tex>
: <tex dpi = "145">1 + x^k + x^{2k} + x^{3k} + \dots = \frac{1}{1-x^k}</tex>
: <tex>\dots</tex>

Запишем теперь [[Производящая функция|производящую функцию]] последовательности <tex>p(n)</tex>:
: <tex dpi = "145">p(0) + p(1) x + p(2) x^2 + p(3) x^3 + \dots = \frac{1}{(1-x)(1-x^2)(1-x^3)\dots}</tex>                                                           <tex>(1)</tex>

Рассмотрим произведение <tex>(1-x)(1-x^2)(1-x^3)...</tex>, т.е. знаменатель правой части формулы <tex>(1)</tex>. Раскрывая в нём скобки, получим следующий результат:
: <tex>(1 - x)(1 - x^2)(1 - x^3) ... = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - x^{35} - x^{40} + ...</tex>
Показатели степеней в правой части — пятиугольные числа<ref name="pentagon" />, т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</tex>. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема, впоследствии названная его именем.

{{Теорема
| about =
Пентагональная теорема Эйлера
| statement =
<tex dpi="145"> \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{q=-\infty}^\infty (-1)^q x^{\frac{3q^2+q}{2}}</tex>
| proof =
<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>

Раскроем в этом произведении первые <tex>22</tex> скобки. Мы получим выражение

<tex>A = [1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...]\times(1-x^{23})(1-x^{24})...(1-x^n)...</tex>,

где в квадратной скобке точками обозначены слагаемые, содержащие <tex>x</tex> в более высокой степени, чем <tex>22</tex>. Не будем выписывать эти члены, так как после умножения квадратной скобки на <tex>1-x^{23}</tex>, <tex>1-x^{24}</tex> и т.д. они изменятся. Выписанные же члены больше меняться не будут. Поэтому, если раскрыть все скобки, то получится бесконечный ряд, первые члены которого имеют вид

<tex>A=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...</tex>

Анализируя этот ряд, Эйлер пришел к выводу, что, если превратить бесконечное произведение

<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>

в ряд, то в этом ряду отличны от нуля лишь слагаемые, вида <tex dpi="145">(-1)^q x^{\frac{3q^2+q}{2}}</tex>, где <tex>q</tex> — натуральное число.

При раскрытии скобок в исходном произведении слагаемое <tex>\pm x^N</tex> встретится столько раз, сколькими способами можно разбить число <tex>N</tex> на различные слагаемые. При этом, если число слагаемых четно, то появляется <tex>x^N</tex>, а если это число нечетно, то появляется <tex>-x^N</tex>. Например, разбиению <tex>12=5+4+2+1</tex> соответствует слагаемое <tex>(-x^5)(-x^4)(-x^2)(-x^1)=x^{12},</tex> а разбиению <tex>12=5+4+3</tex> — слагаемое <tex>(-x^5)(-x^4)(-x^3)=-x^{12}</tex>. Таким образом, коэффициент при <tex>x^N</tex> в разложении <tex>A</tex> в ряд равен разности между количеством разбиений <tex>N</tex> на четное число различных слагаемых и количеством разбиений <tex>N</tex> на нечетное число различных слагаемых. Тогда теорему можно переформулировать следующим образом:

{{Теорема
| about =
Переформулировка пентагональной теоремы
| statement =
Если число <tex>N</tex> не может быть представлено в виде <tex dpi="145">N =\frac{3q^2+q}{2}</tex>, то оно имеет одинаковое количество разбиений на четное и на нечетное число различных слагаемых. А для чисел вида <tex dpi="145">N =\frac{3q^2+q}{2}</tex> разность между этими количествами равна <tex>(-1)^q</tex>.
}}

Иными словами, если <tex>q</tex> четно, то на одно больше разбиений на четное число слагаемых, а если <tex>q</tex> нечетно, то на одно больше разбиений на нечетное число слагаемых. Докажем эту теорему с помощью диаграмм Юнга<ref name="young" />. Покажем несколько способов превращения диаграммы с четным числом строк диаграмму из стольких же точек с нечетным числом строк и обратно.

Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через <tex>m</tex>, а число строк нижней трапеции через <tex>n</tex> (на рис. 1 слева изображена диаграмма, для которой <tex>m=2</tex>, <tex>n=3</tex>).
[[Файл:Diagramma_2_3.jpg|thumb|right|500px|Рис. 1. <tex>m = 2, n = 3</tex>]]

'''Преобразование 1.''' Предположим, что диаграмма содержит не менее двух трапеций, причем <tex>m \leqslant n</tex>. В этом случае отбросим первую строку из <tex>m</tex> точек, но удлиним последние <tex>m</tex> строк нижней трапеции на одну точку (рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.

Точно такое же преобразование можно сделать, если диаграмма состоит из одной трапеции, но <tex>n \geqslant m+1</tex>. Стираем верхнюю строку и к нижним <tex>n-1</tex> строчкам приписываем <tex>m</tex> точек.

'''Преобразование 2.'''Пусть теперь диаграмма опять содержит не менее двух трапеций, но <tex>m > n</tex>. Тогда от каждой строки последней трапеции возьмем по одной точке и составим из них первую строку (из <tex> n </tex> точек) новой диаграммы. Это можно сделать, так как <tex>m > n</tex>, и поэтому составленная строка короче первой строки исходной диаграммы. Кроме того, так как мы взяли все строки будут иметь различную длину. Наконец, новая диаграмма содержит столько же точек, что и исходная, но четность числа строк изменилась - новая диаграмма содержит еще одну строку.

Преобразование 2 допускают и диаграммы, состоящие из одной трапеции, если <tex>n \leqslant m - 2</tex> (появляющаяся первая строка состоит из <tex>n</tex> точек, она должна быть короче бывшей первой строки, уменьшившейся до <tex>m-1</tex> точки).

Легко видеть, что описанные преобразования взаимно обратны - если сначала сделать одно из них, а потом второе, то снова получим исходную диаграмму. Кроме того, для каждой диаграммы может быть допустимо лишь одно из этих преобразований. Таким образом, диаграммы разбиений числа <tex>N</tex>, допускающие одно из этих преобразований, распадаются на пары диаграмм с четным и нечетным числом строк, поэтому их одинаковое число.

Осталось выяснить, какие же диаграммы не допускают ни одного из описанных преобразований. Ясно, что эти диаграммы состоят из одной трапеции, причем для них либо <tex>m=n</tex>, либо <tex>m=n+1</tex>. В первом случае диаграмма содержит

<tex dpi="145">n+(n+1)+(n+2)+\dots+(2n-1)=\frac{3n^2-n}{2}</tex>

точек, а во втором - на <tex>n</tex> точек больше, т.е. <tex dpi="145">\frac{3n^2+n}{2}</tex>.

Приведенные рассуждения показывают, что если <tex>N</tex> не является числом вида <tex dpi="145">\frac{3n^2 \pm n}{2}</tex>, то оно имеет поровну разбиений на четное и нечетное число различных слагаемых.

Очевидно также, что равенства <tex dpi="145">N=\frac{3n^2+n}{2}</tex> и <tex dpi="145">N=\frac{3l^2-l}{2}</tex> одновременно выполняться не могут, поэтому если <tex dpi ="145">N=\frac{3n^2\pm n}{2}</tex>, то без пары останется ровно одна диаграмма, не допускающая преобразования и имеющая <tex>n</tex> строк (слагаемых <tex>N</tex>). Если <tex>n</tex> - четное число, то разбиений на четное число слагаемых окажется на <tex>1</tex> больше, чем на нечетное число слагаемых. Если же <tex>n</tex> - нечетное число, то на <tex>1</tex> больше будет разбиений на нечетное число слагаемых. Теорема доказана.

}}

Умножим обе части равенства <tex>(1)</tex> на <tex>\prod\limits_{k=1}^\infty \left(1-x^k \right) </tex> и воспользуемся пентагональной теоремой:
: <tex> ( p(0) + p(1) x + p(2) x^2 + \dots)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots) = 1 </tex>      <tex>(2)</tex>

Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями <tex>x</tex> пишем друг под другом:
: <tex> p(0) + p(1)x + p(2) x^2 + p(3) x^3 + p(4) x^4 + p(5) x^5 + p(6) x^6 + \dots </tex>
::    <tex> - p(0)x - p(1) x^2 - p(2) x^3 - p(3) x^4 - p(4) x^5 - p(5) x^6 - \dots </tex>
::::       <tex> - p(0) x^2 - p(1) x^3 - p(2) x^4 - p(3) x^5 - p(4) x^6 - \dots </tex>
:::::::::::::  <tex>+ p(0) x^5 + p(1) x^6 + \dots </tex>

Так как <tex>p(0) = 1</tex>, то оно сокращается с единицей справа. Так что, чтобы выражение <tex>(2)</tex> было удовлетворено при любом <tex>x</tex>, все коэффициенты должны быть равны <tex>0</tex>. Поэтому:
: <tex> p(1) = p(0) </tex>
: <tex> p(2) = p(1) + p(0) </tex>
: <tex> p(3) = p(2) + p(1) </tex>
: <tex> p(4) = p(3) + p(2) </tex>
: <tex> p(5) = p(4) + p(3) - p(0) </tex>
: <tex>...</tex>

Получаем формулу Эйлера, позволяющую последовательно находить числа <tex>p(n)</tex>:
: <tex dpi="145"> p(n) = p(n-1) + p(n-2)+ ... + (-1)^{q+1} (p\left(n - \frac{3q^2 - q}{2}\right) + p\left(n - \frac{3q^2 + q}{2}\right)) </tex>.

Асимптотика <tex> O(n \sqrt{n}) </tex> получается следующим образом. Так как <tex dpi="145"> n - \frac{3q^2 + q}{2} \geqslant 0 </tex> , то получаем <tex> q </tex> порядка <tex> \sqrt{n} </tex>, а так как находим <tex>n</tex>-е число, то получаем <tex> O(n \sqrt{n}) </tex>.

== Примечания ==
<references>
<ref name="amount">[http://oeis.org/A000041 Последовательность 000041 на OEIS]</ref>
<ref name="pentagon">[http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B3%D1%83%D1%80%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.9F.D1.8F.D1.82.D0.B8.D1.83.D0.B3.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B5_.D1.87.D0.B8.D1.81.D0.BB.D0.B0 Википедия {{---}} Пятиугольные числа]</ref>
<ref name="young">[http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.94.D0.B8.D0.B0.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D1.8B_.D0.AE.D0.BD.D0.B3.D0.B0 Википедия {{---}} Диаграммы Юнга]</ref>
</references>

==См. также==
* [[Числа Стирлинга первого рода]]
* [[Числа Стирлинга второго рода]]
* [[Производящая функция]]

== Источники информации ==
* [http://en.wikipedia.org/wiki/Pentagonal_number_theorem Wikipedia {{---}} Pentagonal number theorem]
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* Н.Я. Виленкин "Комбинаторика", 2007. стр. 138-141.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП

2017-12-23T17:05:10Z

Haposiwe: Добавлено "см. также"

{{Определение
|definition=
'''Последовательность''' (англ. ''sequence'') {{---}} это набор элементов некоторого множества пронумерованный натуральными числами. Последовательность является результатом последовательного выбора элементов множества. При этом элементы последовательности могут повторяться. В частности, последовательность не является подмножеством заданного множества.
}}

==Виды последовательностей ==
{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''неубывающей''''' (англ. ''nondecreasing''), если каждый элемент этой последовательности не превосходит следующего за ним. <tex>\{x_n\}</tex> — '''''неубывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \leqslant x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''невозрастающей''''' (англ. ''nonincreasing''), если каждый следующий элемент этой последовательности не превосходит предыдущего. <tex>\{x_n\}</tex> — '''''невозрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n \geqslant x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''возрастающей''''' (англ. ''increasing''), если каждый следующий элемент этой последовательности превышает предыдущий. <tex>\{x_n\}</tex> — '''''возрастающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n < x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность <tex>\{x_n\}</tex> элементов множества <tex>X</tex> называется '''''убывающей''''' (англ. ''decreasing''), если каждый элемент этой последовательности превышает следующий за ним. <tex>\{x_n\}</tex> — '''''убывающая''''' <tex>\Leftrightarrow\forall n \in \mathbb N: x_n > x_{n+1}</tex>.
}}

{{Определение
|definition =
Последовательность называется '''монотонной''' (англ. ''monotonic''), если она является неубывающей, либо невозрастающей.
}}

{{Определение
|definition =
Последовательность называется '''строго монотонной''' (англ. ''strictly monotonic''), если она является возрастающей, либо убывающей.
}}

Очевидно, что строго монотонная последовательность является монотонной.

== Теорема о связи длины НВП и НУП ==

{{
Теорема
|author=
|about=
|statement=
Пусть <tex>a</tex> {{---}} перестановка чисел длины <tex>n, l</tex> {{---}} длина наибольшей возрастающей подпоследовательности ([[Задача о наибольшей возрастающей подпоследовательности|НВП]]), <tex>k</tex> {{---}} длина наибольшей убывающей подпоследовательности (НУП). Тогда <tex>l k \geqslant n</tex>.

|proof=
Рассмотрим два массива длины <tex>n : S </tex> и <tex> T </tex>, где <tex> S_i </tex> {{---}} длина НВП, которая заканчивается на <tex>a_i</tex>, <tex> T_i </tex> {{---}} длина НУП, которая начинается на <tex>a_i</tex>.

Докажем, что все пары <tex>(S_i, T_i)</tex> различны.
Пусть существуют такие <tex>i < j</tex> , что <tex> S_i </tex> = <tex> S_j </tex> и <tex> T_i </tex> = <tex> T_j</tex>. Если <tex>a_i < a_j</tex>, тогда <tex> a_j </tex> можно добавить к НВП, заканчивающейся на <tex> a_i </tex>, следовательно <tex>S_j \geqslant S_i + 1</tex>. Если <tex>a_i > a_j</tex>, то по аналогии <tex>T_i \geqslant T_j + 1</tex>. Противоречие! Следовательно все такие пары различны.

Заметим что <tex>1 \leqslant S_i \leqslant l, 1 \leqslant T_i \leqslant k</tex>, поэтому существуют <tex>l k</tex> различных пар <tex> (S_i, T_i) </tex>. Если <tex>l k < n</tex> тогда среди <tex> n </tex> пар найдутся две одинаковые. Такого быть не может по доказанному выше, т. е. <tex>l k \geqslant n</tex>, ч. т. д.
}}

== Следствие из теоремы ==

{{Утверждение
|statement=
Пусть <tex>n</tex> {{---}} длина последовательности, тогда длина наибольшей монотонной подпоследовательности не меньше <tex>\sqrt{n}</tex>.
}}

==См. также==
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Матричное представление перестановок]]

== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.9D.D0.B5.D0.BA.D0.BE.D1.82.D0.BE.D1.80.D1.8B.D0.B5_.D0.B2.D0.B8.D0.B4.D1.8B_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B5.D0.B9 Википедия {{---}} Последовательность]

*[http://en.wikipedia.org/wiki/Longest_increasing_subsequence Wikipedia {{---}} Longest increasing subsequence]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Свойства комбинаторных объектов]]

Задача о минимуме/максимуме скалярного произведения

2017-12-23T17:04:13Z

Haposiwe: Добавлено "см. также"

{{
Задача
|definition=Необходимо найти минимальную/максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел.
}}
== Решение ==
Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + ... + x_m y_m</tex>
{{
Теорема
|about=о минимуме/максимуме скалярного произведениях<ref>[http://ru.wikipedia.org/wiki/Перестановочное_неравенс.. Транс-неравенство или перестановочное неравенство]</ref>
|statement=Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности <tex>x_1..x_m</tex> и убывающей последовательности <tex>y_1..y_m</tex>. При сопоставлении возрастающей <tex>y_1..y_m</tex> достигается максимум.

|proof=
Будем считать, что последовательность <tex>x_i</tex> отсортирована по возрастанию. Покажем, что если существуют пары чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, такие что <tex>x_i < x_j</tex> и <tex>y_i < y_j</tex>, то скалярное произведение можно уменьшить, поменяв местами <tex>y_i</tex> и <tex>y_j</tex>. Так как в нашем случае <tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j y_j > x_j y_i + x_i y_j</tex>, а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>, и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, таких что <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным.
}}

Данная теорема нашла себе практическое применение в теории [[Теорема Радо-Эдмондса (жадный алгоритм)|матроидов]] и [[Flow shop| расписаний]].

== Примечания ==
<references/>

==См. также==
* [[Умножение перестановок, обратная перестановка, группа перестановок]]
* [[Действие перестановки на набор из элементов, представление в виде циклов]]
* [[Таблица инверсий]]
* [[Матричное представление перестановок]]

== Источники информации ==
* Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]

[[Категория: Свойства комбинаторных объектов]]

Нахождение количества разбиений числа на слагаемые

2017-12-23T16:49:45Z

Haposiwe: степень в заголовках переделана в tex

{{Задача
|definition =
По заданному числу <tex>n</tex> найти количество его различных разбиений на положительные слагаемые<ref name="amount" /> <tex> m_0 + m_1 + m_2 + \dots + m_k = n </tex> так, что при всех <tex> i: m_i \leqslant m_{i+1} </tex>.}}

__TOC__

== Алгоритм за <tex>O(N^3)</tex>==
Пусть <tex>P(n, m, k)</tex> — количество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не превосходит <tex>k</tex>.
Имеет место следующее рекуррентное соотношение:

<tex dpi = "145">P(n, m, k) =
\left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 < m \leqslant n, 0 < k \leqslant n \\
1, & n = 0, m = 0 \\
0, & \text{otherwise} \end{array} \right.
</tex>


Рассмотрим множество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не больше <tex>k</tex>. Разделим его на две непересекающиеся группы — в первой будут все
разбиения, которые не содержат в качестве старшего слагаемого <tex>k</tex>. Таких разбиений <tex>P(n, m, k - 1)</tex>. Во второй — все разбиения со старшим слагаемым <tex>k</tex>. Их столько же, сколько разбиений числа <tex>n - k</tex> на <tex>m - 1</tex> слагаемое, каждое из которых не больше <tex>k</tex>, то есть <tex>P(n - k, m - 1, k)</tex>.

Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(n, i, n)</tex>. Реализация данного алгоритма методом [[Динамическое программирование|динамического программирования]] с мемоизацией будет иметь асимптотику <tex>O(n^{3})</tex>.

== Алгоритм за <tex>O(N^2)</tex> ==
Обозначим <tex>P(n,k)</tex> — количество разбиений числа <tex>n</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>. Оно удовлетворяет следующей рекурентной формуле:
<tex dpi="145">P(n,k) = \left \{
\begin{array}{ll} P(n,k - 1) + P(n - k, k), & 0 < k \leqslant n \\
P(n, n), & k > n \\
1, & n = 0, k = 0 \\
0, & n \neq 0 , k = 0 \end{array} \right.</tex>


Заметим, что нам не нужно считать количество слагаемых <tex>m</tex> в разбиении. Достаточно посчитать <tex>P(n, k)</tex> — количество разбиений числа <tex>n</tex> на произвольное количество слагаемых, каждое из которых не больше <tex>k</tex>. Рассмотрим множество таких разбиений. Разделим его на две непересекающиеся группы. В первую войдут те разбиения, в которых отсутствует слагаемое <tex>k</tex>. Очевидно, таких разбиений <tex>P(n, k - 1)</tex>. Во второй группе — те разбиения, в которые слагаемое <tex>k</tex> вошло. Их количество совпадает с количеством разбиений числа <tex>n - k</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>, и равно <tex>P(n - k, k)</tex>.

Количество всех разбиений числа <tex>n</tex> равно <tex>P(n,n)</tex>. Асимптотика <tex>O(n^{2})</tex>.

== Алгоритм за <tex>O(N^{3/2})</tex> ==
Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа <tex>n</tex> на слагаемые, который работает за <tex> O(n \sqrt{n}) </tex>.

Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.

Рассмотрим следующее бесконечное произведение:

<tex> (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^{2k} + \dots) \dots </tex>

После раскрытия скобок каждый член произведения получается в результате умножения мономов (одночленов), взятых по одному из каждой скобки. Если в первой скобке взять <tex dpi = "145">x^{m_1}</tex>, во второй — <tex dpi = "145">x^{2m_2}</tex> и т.д., то их произведение будет равно <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}.</tex> Значит, после раскрытия скобок получится сумма мономов вида <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}</tex>.

Можно увидеть, что <tex> x^n </tex> встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить <tex>n</tex> как сумму <tex>m_1 + 2m_2 + 3m_3 + ...</tex> Каждому такому представлению отвечает разбиение числа <tex>n</tex> на <tex>m_1</tex> единиц, <tex>m_2</tex> двоек и т.д. Таким образом, очевидно, получаются все разбиения, так как из первой скобки мы можем взять любое <tex>x^{m_i}</tex>, где <tex>m_i \in [0 \dots \infty),</tex> то есть произвольное количество единиц в нашем разбиении. Аналогично, мы можем взять произвольное количество двоек и т.д. Но при раскрытии скобок мы находим произведения всех возможных комбинации множителей из разных скобок. Поэтому коэффициент при <tex>x^n</tex> равен числу разбиений <tex>p(n)</tex>.

Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. Полагая <tex>0 \leqslant x < 1</tex>, по формуле ее суммирования:
: <tex dpi = "145">1 + x + x^2 + x^3 + \dots = \frac{1}{1 - x}</tex>,
: <tex dpi = "145">1 + x^2 + x^4 + x^6 + \dots = \frac{1}{1-x^2}</tex>
: <tex>\dots</tex>
: <tex dpi = "145">1 + x^k + x^{2k} + x^{3k} + \dots = \frac{1}{1-x^k}</tex>
: <tex>\dots</tex>

Запишем теперь [[Производящая функция|производящую функцию]] последовательности <tex>p(n)</tex>:
: <tex dpi = "145">p(0) + p(1) x + p(2) x^2 + p(3) x^3 + \dots = \frac{1}{(1-x)(1-x^2)(1-x^3)\dots}</tex>                                                           <tex>(1)</tex>

Рассмотрим произведение <tex>(1-x)(1-x^2)(1-x^3)...</tex>, т.е. знаменатель правой части формулы <tex>(1)</tex>. Раскрывая в нём скобки, получим следующий результат:
: <tex>(1 - x)(1 - x^2)(1 - x^3) ... = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - x^{35} - x^{40} + ...</tex>
Показатели степеней в правой части — пятиугольные числа<ref name="pentagon" />, т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</tex>. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема, впоследствии названная его именем.

{{Теорема
| about =
Пентагональная теорема Эйлера
| statement =
<tex dpi="145"> \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{q=-\infty}^\infty (-1)^q x^{\frac{3q^2+q}{2}}</tex>
| proof =
<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>

Раскроем в этом произведении первые <tex>22</tex> скобки. Мы получим выражение

<tex>A = [1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...]\times(1-x^{23})(1-x^{24})...(1-x^n)...</tex>,

где в квадратной скобке точками обозначены слагаемые, содержащие <tex>x</tex> в более высокой степени, чем <tex>22</tex>. Не будем выписывать эти члены, так как после умножения квадратной скобки на <tex>1-x^{23}</tex>, <tex>1-x^{24}</tex> и т.д. они изменятся. Выписанные же члены больше меняться не будут. Поэтому, если раскрыть все скобки, то получится бесконечный ряд, первые члены которого имеют вид

<tex>A=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...</tex>

Анализируя этот ряд, Эйлер пришел к выводу, что, если превратить бесконечное произведение

<tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex>

в ряд, то в этом ряду отличны от нуля лишь слагаемые, вида <tex dpi="145">(-1)^q x^{\frac{3q^2+q}{2}}</tex>, где <tex>q</tex> — натуральное число.

При раскрытии скобок в исходном произведении слагаемое <tex>\pm x^N</tex> встретится столько раз, сколькими способами можно разбить число <tex>N</tex> на различные слагаемые. При этом, если число слагаемых четно, то появляется <tex>x^N</tex>, а если это число нечетно, то появляется <tex>-x^N</tex>. Например, разбиению <tex>12=5+4+2+1</tex> соответствует слагаемое <tex>(-x^5)(-x^4)(-x^2)(-x^1)=x^{12},</tex> а разбиению <tex>12=5+4+3</tex> — слагаемое <tex>(-x^5)(-x^4)(-x^3)=-x^{12}</tex>. Таким образом, коэффициент при <tex>x^N</tex> в разложении <tex>A</tex> в ряд равен разности между количеством разбиений <tex>N</tex> на четное число различных слагаемых и количеством разбиений <tex>N</tex> на нечетное число различных слагаемых. Тогда теорему можно переформулировать следующим образом:

{{Теорема
| about =
Переформулировка пентагональной теоремы
| statement =
Если число <tex>N</tex> не может быть представлено в виде <tex dpi="145">N =\frac{3q^2+q}{2}</tex>, то оно имеет одинаковое количество разбиений на четное и на нечетное число различных слагаемых. А для чисел вида <tex dpi="145">N =\frac{3q^2+q}{2}</tex> разность между этими количествами равна <tex>(-1)^q</tex>.
}}

Иными словами, если <tex>q</tex> четно, то на одно больше разбиений на четное число слагаемых, а если <tex>q</tex> нечетно, то на одно больше разбиений на нечетное число слагаемых. Докажем эту теорему с помощью диаграмм Юнга<ref name="young" />. Покажем несколько способов превращения диаграммы с четным числом строк диаграмму из стольких же точек с нечетным числом строк и обратно.

Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через <tex>m</tex>, а число строк нижней трапеции через <tex>n</tex> (на рис. 1 слева изображена диаграмма, для которой <tex>m=2</tex>, <tex>n=3</tex>).
[[Файл:Diagramma_2_3.jpg|thumb|right|500px|Рис. 1. <tex>m = 2, n = 3</tex>]]

'''Преобразование 1.''' Предположим, что диаграмма содержит не менее двух трапеций, причем <tex>m \leqslant n</tex>. В этом случае отбросим первую строку из <tex>m</tex> точек, но удлиним последние <tex>m</tex> строк нижней трапеции на одну точку (рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.

Точно такое же преобразование можно сделать, если диаграмма состоит из одной трапеции, но <tex>n \geqslant m+1</tex>. Стираем верхнюю строку и к нижним <tex>n-1</tex> строчкам приписываем <tex>m</tex> точек.

'''Преобразование 2.'''Пусть теперь диаграмма опять содержит не менее двух трапеций, но <tex>m > n</tex>. Тогда от каждой строки последней трапеции возьмем по одной точке и составим из них первую строку (из <tex> n </tex> точек) новой диаграммы. Это можно сделать, так как <tex>m > n</tex>, и поэтому составленная строка короче первой строки исходной диаграммы. Кроме того, так как мы взяли все строки будут иметь различную длину. Наконец, новая диаграмма содержит столько же точек, что и исходная, но четность числа строк изменилась - новая диаграмма содержит еще одну строку.

Преобразование 2 допускают и диаграммы, состоящие из одной трапеции, если <tex>n \leqslant m - 2</tex> (появляющаяся первая строка состоит из <tex>n</tex> точек, она должна быть короче бывшей первой строки, уменьшившейся до <tex>m-1</tex> точки).

Легко видеть, что описанные преобразования взаимно обратны - если сначала сделать одно из них, а потом второе, то снова получим исходную диаграмму. Кроме того, для каждой диаграммы может быть допустимо лишь одно из этих преобразований. Таким образом, диаграммы разбиений числа <tex>N</tex>, допускающие одно из этих преобразований, распадаются на пары диаграмм с четным и нечетным числом строк, поэтому их одинаковое число.

Осталось выяснить, какие же диаграммы не допускают ни одного из описанных преобразований. Ясно, что эти диаграммы состоят из одной трапеции, причем для них либо <tex>m=n</tex>, либо <tex>m=n+1</tex>. В первом случае диаграмма содержит

<tex dpi="145">n+(n+1)+(n+2)+\dots+(2n-1)=\frac{3n^2-n}{2}</tex>

точек, а во втором - на <tex>n</tex> точек больше, т.е. <tex dpi="145">\frac{3n^2+n}{2}</tex>.

Приведенные рассуждения показывают, что если <tex>N</tex> не является числом вида <tex dpi="145">\frac{3n^2 \pm n}{2}</tex>, то оно имеет поровну разбиений на четное и нечетное число различных слагаемых.

Очевидно также, что равенства <tex dpi="145">N=\frac{3n^2+n}{2}</tex> и <tex dpi="145">N=\frac{3l^2-l}{2}</tex> одновременно выполняться не могут, поэтому если <tex dpi ="145">N=\frac{3n^2\pm n}{2}</tex>, то без пары останется ровно одна диаграмма, не допускающая преобразования и имеющая <tex>n</tex> строк (слагаемых <tex>N</tex>). Если <tex>n</tex> - четное число, то разбиений на четное число слагаемых окажется на <tex>1</tex> больше, чем на нечетное число слагаемых. Если же <tex>n</tex> - нечетное число, то на <tex>1</tex> больше будет разбиений на нечетное число слагаемых. Теорема доказана.

}}

Умножим обе части равенства <tex>(1)</tex> на <tex>\prod\limits_{k=1}^\infty \left(1-x^k \right) </tex> и воспользуемся пентагональной теоремой:
: <tex> ( p(0) + p(1) x + p(2) x^2 + \dots)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots) = 1 </tex>      <tex>(2)</tex>

Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями <tex>x</tex> пишем друг под другом:
: <tex> p(0) + p(1)x + p(2) x^2 + p(3) x^3 + p(4) x^4 + p(5) x^5 + p(6) x^6 + \dots </tex>
::    <tex> - p(0)x - p(1) x^2 - p(2) x^3 - p(3) x^4 - p(4) x^5 - p(5) x^6 - \dots </tex>
::::       <tex> - p(0) x^2 - p(1) x^3 - p(2) x^4 - p(3) x^5 - p(4) x^6 - \dots </tex>
:::::::::::::  <tex>+ p(0) x^5 + p(1) x^6 + \dots </tex>

Так как <tex>p(0) = 1</tex>, то оно сокращается с единицей справа. Так что, чтобы выражение <tex>(2)</tex> было удовлетворено при любом <tex>x</tex>, все коэффициенты должны быть равны <tex>0</tex>. Поэтому:
: <tex> p(1) = p(0) </tex>
: <tex> p(2) = p(1) + p(0) </tex>
: <tex> p(3) = p(2) + p(1) </tex>
: <tex> p(4) = p(3) + p(2) </tex>
: <tex> p(5) = p(4) + p(3) - p(0) </tex>
: <tex>...</tex>

Получаем формулу Эйлера, позволяющую последовательно находить числа <tex>p(n)</tex>:
: <tex dpi="145"> p(n) = p(n-1) + p(n-2)+ ... + (-1)^{q+1} (p\left(n - \frac{3q^2 - q}{2}\right) + p\left(n - \frac{3q^2 + q}{2}\right)) </tex>.

Асимптотика <tex> O(n \sqrt{n}) </tex> получается следующим образом. Так как <tex dpi="145"> n - \frac{3q^2 + q}{2} \geqslant 0 </tex> , то получаем <tex> q </tex> порядка <tex> \sqrt{n} </tex>, а так как находим <tex>n</tex>-е число, то получаем <tex> O(n \sqrt{n}) </tex>.

== Примечания ==
<references>
<ref name="amount">[http://oeis.org/A000041 Последовательность 000041 на OEIS]</ref>
<ref name="pentagon">[http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B3%D1%83%D1%80%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.9F.D1.8F.D1.82.D0.B8.D1.83.D0.B3.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B5_.D1.87.D0.B8.D1.81.D0.BB.D0.B0 Википедия {{---}} Пятиугольные числа]</ref>
<ref name="young">[http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.94.D0.B8.D0.B0.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D1.8B_.D0.AE.D0.BD.D0.B3.D0.B0 Википедия {{---}} Диаграммы Юнга]</ref>
</references>

== Источники информации ==
* [http://en.wikipedia.org/wiki/Pentagonal_number_theorem Wikipedia {{---}} Pentagonal number theorem]
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* Н.Я. Виленкин "Комбинаторика", 2007. стр. 138-141.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

КНФ

2017-12-23T16:32:24Z

Haposiwe: 1) Изменены "..." на "\ldot" 2) Добавлена СКНФ для медианы от 5 аргументов

== КНФ ==
{{Определение
|definition =
'''Простой дизъюнкцией''' (англ. ''inclusive disjunction'') или '''дизъюнктом''' (англ. ''disjunct'') называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая дизъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно один раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Конъюнктивная нормальная форма, КНФ''' (англ. ''conjunctive normal form, CNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Пример КНФ:
<tex>f(x,y,z) = (x \lor y) \land (y \lor \neg{z})</tex>

== СКНФ ==
{{Определение
|definition =
'''Совершенная конъюнктивная нормальная форма, СКНФ''' (англ. ''perfect conjunctive normal form, PCNF'') — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых дизъюнкций
* каждая простая дизъюнкция полная
}}
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})</tex>

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
|proof =
Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:
<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>

Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge \ldots \wedge x_{n}^{\sigma_{n}})}) </tex>

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, \ldots ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee \ldots \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, не равной тождественному нулю, то теорема доказана.
}}

== Алгоритм построения СКНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.
# Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные дизъюнкции связываем операциями конъюнкции.

== Пример построения СКНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex>0</tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу : если значение некоторой переменной есть <tex>0</tex>, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''x''' || '''y''' || '''z''' || <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \neg{z})</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>
|-align="center" bgcolor=#FFF
| 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>
|-align="center" bgcolor=#FFF
| 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#FFF
| 1 || 1 || 1 || 1 ||
|}

3. Все полученные дизъюнкции связываем операциями конъюнкции.

<tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{y} \lor z) \land ( x \lor y \lor \neg{z})</tex>

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) </tex>

Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>

Медиана 5 аргументов:

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor x_5) \land \\ (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (\overline{x_1} \lor \overline{x_2} \lor x_3 \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor \overline{x_2} \lor \overline{x_3} \lor x_4 \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land \\ (\overline{x_1} \lor x_2 \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor \overline{x_2} \lor x_3 \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor \overline{x_3} \lor \overline{x_4} \lor x_5) \land (x_1 \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (\overline{x_1} \lor x_2 \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor \overline{x_2} \lor x_3 \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor \overline{x_3} \lor x_4 \lor \overline{x_5}) \land (x_1 \lor x_2 \lor x_3 \lor \overline{x_4} \lor \overline{x_5}) </tex>
== Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 Википедия {{---}} СКНФ]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская {{---}} Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

ДНФ

2017-12-23T16:22:40Z

Haposiwe: 1) Изменены "..." на "\ldot" 2) Добавлена СДНФ для медианы от 5 аргументов

== ДНФ ==
{{Определение
|definition =
'''Простой конъюнкцией''' (англ. ''inclusive conjunction'') или '''конъюнктом''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая конъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно <tex> 1 </tex> раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
'''Дизъюнктивная нормальная форма, ДНФ''' (англ. ''disjunctive normal form, DNF'') {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
<tex>f(x,y,z) = (x \land y) \lor (y \land \neg {z})</tex>.

== СДНФ ==
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ''' (англ. ''perfect disjunctive normal form, PDNF'') — ДНФ, удовлетворяющая условиям:
* в ней нет одинаковых простых конъюнкций,
* каждая простая конъюнкция полная.
}}
Пример СДНФ:
<tex>f(x,y,z) = (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю, существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона''':

<tex>f(\vec{x}) = \neg x_i \wedge f(x_1, \ldots ,x_{i-1},0,x_{i+1}, \ldots ,x_n) \vee
x_i \wedge f(x_1, \ldots ,x_{i-1},1,x_{i+1}, \ldots ,x_n)</tex>.

Данное соотношение легко проверить подстановкой возможных значений <tex>x_i</tex> (<tex>0</tex> и <tex>1</tex>). Эта формула позволяет выносить <tex>x_i</tex> за знак функции. Последовательно вынося <tex>x_1</tex>, <tex>x_2</tex>,.., <tex>x_n</tex> за знак <tex>f(\vec{x})</tex>, получаем следующую формулу:
<tex> f(\vec{x}) = \neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge \neg x_n \wedge f(0,0,\ldots,0,0)~\vee~</tex>

<tex>\neg x_1 \wedge \neg x_2 \wedge \ldots \wedge \neg x_{n-1} \wedge x_n \wedge f(0,0,\ldots,0,1) ~\vee~ \\
\ldots \\
~\vee~ x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge \neg x_n \wedge f(1,1,\ldots,1,0) ~\vee~\\
x_1 \wedge x_2 \wedge \ldots \wedge x_{n-1} \wedge x_n \wedge f(1,1,\ldots,1) </tex>

Так как применение данного соотношения к каждой из переменных увеличивает количество конъюнктов в два раза, то для функции от <tex>n</tex> переменных мы имеем <tex>2^n</tex> конъюнктов. Каждый из них соответствует значению функции на одном из <tex>2^n</tex> возможных наборов значений <tex> n </tex> переменных. Если на некотором наборе <tex>f(\vec{x})=0</tex>, то весь соответствующий конъюнкт также равен нулю и из представления данной функции его можно исключить. Если же <tex> f(\vec{x})=1</tex>, то в соответствующем конъюнкте само значение функции можно опустить. В результате для произвольной функции была построена СДНФ.
}}

== Алгоритм построения СДНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.
# Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные конъюнкции связываем операциями дизъюнкции.

== Пример построения СДНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно <tex> 1 </tex>.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1
|}

2. Для каждого отмеченного набора записываем конъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть <tex> 1 </tex>, то в конъюнкцию включаем саму переменную, иначе ее отрицание.

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
|<tex> x </tex>||<tex> y </tex>||<tex> z </tex>|| <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 0 || 1 || 0 ||
|-align="center" bgcolor=#FFFFFF
| 0 || 1 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 0 || 1 || 1 || 1 || <tex>(\neg {x} \land y \land z)</tex>
|-align="center" bgcolor=#FFFFFF
| 1 || 0 || 0 || 0 ||
|-align="center" bgcolor=#FFFFFF
! 1 || 0 || 1 || 1 || <tex>(x \land \neg {y} \land z)</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 0 || 1 || <tex>(x \land y \land \neg {z})</tex>
|-align="center" bgcolor=#FFFFFF
! 1 || 1 || 1 || 1 || <tex>(x \land y \land z)</tex>
|}

3. Все полученные конъюнкции связываем операциями дизъюнкции:

<tex> \langle x,y,z \rangle = (x \land y \land z) \lor (\neg {x} \land y \land z) \lor (x \land \neg {y} \land z) \lor (x \land y \land \neg {z})</tex>.

==Примеры СДНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg {x} \land \neg {y})</tex>.

Исключающее или: <tex> x \oplus y \oplus z = (\overline{x} \land \overline{y} \land z) \lor (\overline{x} \land y \land \overline{z}) \lor (x \land \overline{y} \land \overline{z}) \lor (x \land y \land z)</tex>.

Медиана 5 аргументов:

<tex> \langle x_1, x_2, x_3, x_4, x_5 \rangle = (x_1 \land x_2 \land x_3 \land \overline{x_4} \land \overline{x_5}) \lor (x_1 \land x_2 \land \overline{x_3} \land x_4 \land \overline{x_5}) \lor \\ (x_1 \land \overline{x_2} \land x_3 \land x_4 \land \overline{x_5}) \lor (\overline{x_1} \land x_2 \land x_3 \land x_4 \land \overline{x_5}) \lor (x_1 \land x_2 \land x_3 \land x_4 \land \overline{x_5}) \lor \\ (x_1 \land x_2 \land \overline{x_3} \land \overline{x_4} \land x_5) \lor (x_1 \land \overline{x_2} \land x_3 \land \overline{x_4} \land x_5) \lor (\overline{x_1} \land x_2 \land x_3 \land \overline{x_4} \land x_5) \lor \\ (x_1 \land x_2 \land x_3 \land \overline{x_4} \land x_5) \lor (x_1 \land \overline{x_2} \land \overline{x_3} \land x_4 \land x_5) \lor (\overline{x_1} \land x_2 \land \overline{x_3} \land x_4 \land x_5) \lor (x_1 \land x_2 \land \overline{x_3} \land x_4 \land x_5) \lor (\overline{x_1} \land \overline{x_2} \land x_3 \land x_4 \land x_5) \lor (x_1 \land \overline{x_2} \land x_3 \land x_4 \land x_5) \lor (\overline{x_1} \land x_2 \land x_3 \land x_4 \land x_5) \lor (x_1 \land x_2 \land x_3 \land x_4 \land x_5) </tex>.
== См. также ==

* [[Сокращенная и минимальная ДНФ]]
* [[КНФ]]

==Источники информации ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%94%D0%9D%D0%A4 СДНФ — Википедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]