{Курс лекций по} {дискретной математике} {Лектор — Угольников Александ Борисович} {IV курс, 7-й семестр, поток математиков} {Москва, 2011г} {Краткое руководство пользователя.} Последние версии исходных кодов данных лекций могут быть получены в git-репозитории { git://gitorious.org/dmvn-project/discretemath.git}. Если Вы нашли ошибку, неточность или несоответствие(а их тут много), или у Вас есть предложения или пожелание пожалуйста, сообщите об ошибке на электронный ящик { illusion.of.life92@gmail.com} с пометкой discretemath. Предпочтительно, присылайте diff-файл, иначе – просто указание места в документе. Скоро здесь будет какая-нибудь copy-left лицензия. {part1.tex} {part2.tex} {part3.tex} {part4.tex} {part5.tex}

{Классы Поста.}

Повторение теории булевых функций.

Основные определения.

= {0,1}

^n = {, _i }

n-местная булева функция: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle f^{(n)} (\set[x]{n}): \Ef^n \to \Ef }

Failed to parse (unknown function "\PD"): {\displaystyle \PD} -множество всех булевых функций.

Failed to parse (unknown function "\set"): {\displaystyle f(\set[x]{n})=g(\set[x]{n})} , если Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \allset[x]{n} \quad f(\xt)=g(\xt) }

$x_{1}$ — существенная переменная для Failed to parse (unknown function "\set"): {\displaystyle f^{(n)}(\set{n})} , если существует Failed to parse (unknown function "\uset"): {\displaystyle \uset{n}{\Ef},\text{что выполнено} } Failed to parse (unknown function "\setf"): {\displaystyle f(0,\setf{n})\neq f(1,\setf{n}) } В противном случае $x_{1}$ несущественная.

Способы задания булевых функций

Таблица
Формула над Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \ag\subseq\PD}

Операции над булевскими функциями

Суперпозиция. Частные случаи:
- Перестановка переменных
- Отождествление переменных
- Переименование переменных без отождествления
- Композиция (подстановка функции вместо переменных)
Введение фиктивной переменной (Failed to parse (unknown function "\nab"): {\displaystyle \nab} )

Пусть есть функция Failed to parse (unknown function "\set"): {\displaystyle f^{(n)}(\set{n})} . Оператор Failed to parse (unknown function "\nab"): {\displaystyle \nab} определяется соотношением Failed to parse (unknown function "\nab"): {\displaystyle (\nab f)(\set{n}\al_{n+1})=f(\set{n}) \quad \forall (\set) \in \Ef^n }

Замкнутые классы

Замыканием множества Failed to parse (unknown function "\ag"): {\displaystyle \ag\subseq\PD} называется множество булевых функций, которые можно получить из множества функций Failed to parse (unknown function "\ag"): {\displaystyle \ag} с помощью операций суперпозиции и введения фиктивной переменной.

Замыкание множества Failed to parse (unknown function "\ag"): {\displaystyle \ag\subseq\PD} обозначим Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle [\ag]} .

Failed to parse (unknown function "\ag"): {\displaystyle \ag} — замкнутое множество (замкнутый класс), если Failed to parse (unknown function "\ag"): {\displaystyle \ag = [\ag]}

Пусть $[F]=F$ и [Failed to parse (unknown function "\ag"): {\displaystyle \ag} ]=F. Тогда будем говорить, что Failed to parse (unknown function "\ag"): {\displaystyle \ag} порождает F.

Замкнутый класс F называется конечнопорожденным, если найдется конечная система Failed to parse (unknown function "\ag"): {\displaystyle \ag\subseq\PD} , что Failed to parse (unknown function "\ag"): {\displaystyle \ag} порождает F.

В дальнейшем будем рассматривать равенство функций с точностью до несущественных переменных.
Failed to parse (unknown function "\queq"): {\displaystyle f(x,y)\queq g(x,z) \Lra (\nab f)(x,y,z) \queq (\nab g)(x,y,z) }

Пусть F-замкнутый класс. Будем обозначать $f_{F}$ функцию не принадлежащую F.

Рассмотрим некотые замкнутые классы. {Линейные функции.}

Линейные функции – функции вида Failed to parse (unknown function "\set"): {\displaystyle f(\set[x]{n}) = a_0+a_1x_1+\cdots+a_nx_n, \quad \pcoef }

Failed to parse (unknown function "\Lb"): {\displaystyle 0, 1, x+y\in\Lb}
Failed to parse (unknown function "\Lb"): {\displaystyle xy\notin\Lb}
Failed to parse (unknown function "\Lb"): {\displaystyle [\Lb] = \Lb}
Failed to parse (unknown function "\Lb"): {\displaystyle \Lb = \cls{0,1,x+y}}
Из нелиненйной функции подстановкой 0,x,y можно получить нелинейную функцию двух переменных.

Коньюнкции.

Коньюнкции – функции вида Failed to parse (unknown function "\set"): {\displaystyle f(\set[x]{n}) = a_0\&(a_1\vee x_1)\&\dots\&(a_n\vee x_n) \quad \pcoef }

Failed to parse (unknown function "\Kb"): {\displaystyle 0, 1, x, xy \in \Kb}
Failed to parse (unknown function "\Kb"): {\displaystyle x\vee y\notin \Kb}
Failed to parse (unknown function "\Kb"): {\displaystyle [\Kb] = \Kb }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \Kb = [\{0,1,xy\}]}

Дизьюнкции.

Дизьюнкции – функции вида Failed to parse (unknown function "\set"): {\displaystyle f(\set[x]{n}) = a_0\vee(a_1x_1)\vee\dots\vee a_nx_n \quad \pcoef }

Failed to parse (unknown function "\Db"): {\displaystyle 0, 1, x, x\vee y \in \Db}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle xy \notin \Db}
Failed to parse (unknown function "\Db"): {\displaystyle [\Db] = \Db }
Failed to parse (unknown function "\Db"): {\displaystyle \Db = [\{0, 1, x\vee y\}]}

Монотонные функции.

Пусть Failed to parse (unknown function "\gset"): {\displaystyle \gset{n}} и Failed to parse (unknown function "\gset"): {\displaystyle \gset[\beta]{n}} . Тогда по определению полагаем Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \tilde\alpha \le \tilde\beta \Lra\forall i \; \alpha_i \le \beta_i } Считаем,что $0<1$ .

Монотонные функции - функции Failed to parse (unknown function "\set"): {\displaystyle f(\set[x]{n})} , для который верно утверждение Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle f(\alt)\le f(\tilde\beta)\quad\forall \alt,\tilde\beta \in \Ef^n }

Failed to parse (unknown function "\Mb"): {\displaystyle 0, 1, xy, x+y \in \Mb}
Failed to parse (unknown function "\Mb"): {\displaystyle [\Mb] = \Mb }
Пусть Failed to parse (unknown function "\set"): {\displaystyle f(\set[x]{n}) \in \Mb} . Тогда верно соотношение Failed to parse (unknown function "\set"): {\displaystyle f(\set[x]{n}) = x_1f(1, \setf[x]{n})\vee f(0, \setf[x]{n}) }

={0, 1, xy, x y}
Пусть $f\neq 0$ , $f\neq 1$ , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle f \in \Mb} . Тогда Failed to parse (unknown function "\cls"): {\displaystyle f \in \cls{\dn, xy} }
Пусть Failed to parse (unknown function "\Mb"): {\displaystyle f_K, f_D \in \Mb} . Тогда $x\vee y\in [\{1,f_{K}\}]$ $xy\in [\{0,f_{D}\}]$

Докажем один случай. Второй аналогичен. Failed to parse (unknown function "\Db"): {\displaystyle f_{\Db}(\set[x]{n}) \notin \Db, f_{\Db} \in \Mb, n \ge 2 } Пусть все Failed to parse (unknown function "\set"): {\displaystyle \set[x]{n}} существенны. Существует Failed to parse (unknown function "\al"): {\displaystyle \tilde \al= (\set{n})} с ровно одной единицей, что Failed to parse (unknown function "\Db"): {\displaystyle f_{\Db}(\tilde \al) = 0} . Без ограничения общности можно считать, что

= (1, 0 , 0)

Failed to parse (unknown function "\Db"): {\displaystyle f_{\Db}(1, 0 \etc, 0) = 0 } Так как переменная $x_{1}$ — существенная, то существует Failed to parse (unknown function "\setf"): {\displaystyle \setf[\beta]{n}} , что Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle f_{\Db}(0, \setf[\beta]{n}) \neq f_{\Db}(1, \setf[\beta]{n}) } На самом деле, из монотонности следует, что Failed to parse (unknown function "\fD"): {\displaystyle \fD(0, \setf[\beta]{n}) = 0;\; \fD(1, \setf[\beta]{n}) } Не все $\beta _{j}$ – нули, поэтому существует k, что, не ограничивая общности можно считать, что $\beta _{2}=\ldots =\beta _{k}=1$ $\beta _{k+1}=\ldots =\beta _{n}=0$ Рассмотрим функцию Failed to parse (unknown function "\fD"): {\displaystyle g(x,y)=\fD(x, \ub{y\etc, y}_{k-1}, 0\etc, 0) } Из предыдущий выклдок следует, что $g(1,0)=0,g(0,1)=0,g(1,1)=1$ . По монотонности, $g(0,0)=0$ . Отсюда, $g(x,y)=xy$
, ={0, 1, ,}
Из немонотонной функции подстановкой 0, 1, x можно получить Failed to parse (unknown function "\ol"): {\displaystyle \ol x}