\documentclass[11pt,oneside,a4paper]{article} \usepackage[margin=2cm]{geometry} \usepackage{fancyhdr} \usepackage{amsmath,amsthm,amssymb} \usepackage{graphicx} \usepackage[pdftex, pdfauthor={Georgi Georgiev}, pdftitle={Exam, SU, FMI, 29.08.2017}, pdfsubject={Discrete structures}, pdfstartview={FitH} ]{hyperref} \usepackage{mathtext} \usepackage[T1,T2A]{fontenc} \usepackage[utf8]{inputenc} \usepackage[english,bulgarian]{babel} \usepackage{setspace} %\usepackage{array} %\usepackage[chapter]{algorithm} %\usepackage[noend]{algpseudocode} %\usepackage{float} %\floatname{algorithm}{Алгоритъм} %\usepackage{myalg} \setlength{\parindent}{10pt} \setlength{\parskip}{1ex} \pagestyle{empty} \begin{document} \begin{center} \begin{spacing}{2} Поправителен изпит по\, ''Дискретни структури'' (задачи), СУ, ФМИ, 29.\,08.\,2017 г. \end{spacing} Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\; ФН: \_\_\_\_\_\; Спец.: \_\_\_\_\; Курс: \_\_\_ \end{center} \begin{center} \begin{tabular}{|l|c|c|c|c|c||c|} \hline Задача & 1 & 2 & 3 & 4 & 5 & Общо\\ \hline \hline получени точки & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & \\ \hline максимум точки & 16 & 16 & 16 & 16 & 16 & 80 \\ \hline \end{tabular} \end{center} %\emph{Забележка:}\; За отлична оценка са достатъчни 60 точки. \paragraph{Задача 1.} %Нека $x \in \mathbb{R}, x>0$, а $n \in \mathbb{N}, n>0$. Докажете, че $(1+x)^n\ge 1+nx$. Докажете, че числото $2n^3+n$ се дели на 3 за $\forall n \in \mathbb{N}$. \paragraph{Задача 2.} Нека $\mathbb{N}$ е множеството на естествените числа, а $2^\mathbb{N}$ е множеството от подмножествата му. % $\{0, 1, 2, \ldots\}$. Постройте биекция между множествата $2^\mathbb{N}$ и $2^\mathbb{N}\times 2^\mathbb{N}$. \paragraph{Задача 3.} В неориентиран граф от всеки връх излизат точно три ребра. Графът няма примки и триъгълници (цикли с дължина 3). (a - 8 точки) Докажете, че графът има поне 6 върха. (b - 8 точки) Има ли граф с 6 върха и исканите свойства? \paragraph{Задача 4.} При игра на табла играчите хвърлят 2 зарчета на всеки ход. Зарчето има 6 страни, на които са обозначени от една до шест точки. Комбинация на зарчетата наричаме двойката числа, която съответства на броя на точките върху горната страна на падналите зарчета.\\ Редът на числата няма значение, тоест двойките $(2,5)$ и $(5,2)$ представят една комбинация. (a - 8 точки) Колко са възможните комбинации? (b - 8 точки) На планетата Тралфамадор зарчетата имат $n$ страни. Колко са възможните комбинации там? \paragraph{Задача 5.} Двоичната функция $f(x,y,z)$ е определена с редицата стойности $f=(11111010)$. (a - 8 точки) Намерете минимална дизюнктивна нормална форма на $f(x,y,z)$. (b - 8 точки) Шеферова ли е функцията $f$? \pagebreak {\centering\textbf{РЕШЕНИЯ}\par} \vspace{-10pt} \paragraph{\mbox{Задача 1.}} \mbox{} Означаваме с $f(n)=2n^3+n$ изразът, който ни интересува. \emph{Първи начин} (индукция): Очевидно $f(0)=0$ се дели на 3. Нека $f(n)$ се дели на 3, тогава $f(n+1)=2(n+1)^3+(n+1)=2n^3+6n^2+6n+2+n+1=2n^3+n+3(2n^2+2n+1)$. Получаваме $f(n+1)=f(n)+3(2n^2+2n+1)$, което се дели на 3, защото двете събираеми се делят на 3. \emph{Втори начин} (делимост): Преобразуваме: $f(n)=2n^3+n=2(n^3-n)+3n=2n(n-1)(n+1)+3n$ Двете събираеми $2n(n-1)(n+1)$ и $3n$ се делят на 3, второто е кратно на 3. Събираемото $2n(n-1)(n+1)$ се дели на 3, защото от трите поредни числа $n-1, n$ и $n+1$, точно едно се дели на 3. \paragraph{Задача 2.} \mbox{} %\\ Нека $A\subset \mathbb{N}$ е произволно подмножество на естествените числа. Съпоставяме му характеристичната редица $\alpha=\alpha_0\alpha_1\alpha_2\ldots$, такава че $\alpha_i$ е $1$, когато $i\in A$ и $0$, когато $i\notin A$. От лекции знаем, че това съоветствие е биективно. Дефинираме функция $f(\alpha)=(\alpha_{e},\alpha_{o})$ така: $\alpha_{e}=\alpha_0\alpha_2\alpha_4\ldots$ се състои от четните битове на $\alpha$. $\alpha_{o}=\alpha_1\alpha_3\alpha_5\ldots$ се състои от нечетните битове на $\alpha$. Лесно се проверява, че $f$ е биекция от множеството на характеристичните редици към множеството от наредените двойки характеристични редици. Ако означим с $A_e$ и $A_o$ множествата от естествени числа, съответни на характеристичните редици $\alpha_{e}$ и $\alpha_{o}$, получаваме композиция от биекции: $A \to \alpha \to f(\alpha)=(\alpha_{e},\alpha_{o}) \to (A_e,A_o)$ Тази композиция е биекция между множествата $2^\mathbb{N}$ и $2^\mathbb{N}\times 2^\mathbb{N}$. \emph{Забележка:} На лекции обсъдихме факта, че мощността на $2^\mathbb{N}$ съвпада с мощността на множеството реални числа в интервала $(0,1)$, също и с мощността на континуума (множеството на всички реални числа, множеството от точките върху права линия). От представената задача следва, че същата мощност ще имат множествата от точки, разположени във вътрешността на единичен квадрат или пък всички точки в равнината или пространството, т.е. има биекция между отворения интервал $(0,1)$ и $\mathbb{R}^3$. \paragraph{Задача 3.} \mbox{} %\\ (a) Избираме произволен връх на графа и почваме обхождане в ширина (BFS) от този връх. Ще номерираме върховете по реда на обхождане. Нека началният връх на обхождането е $x_1$. От него достигаме 3 нови върха -- $x_2, x_3$ и $x_4$. От $x_2$ не излиза ребро към $x_3$ и $x_4$, ще се получи триъгълник. Освен ребро към $x_1$, от $x_2$ излизат две ребра към непосетени върхове -- $x_5$ и $x_6$, следователно графът има поне 6 върха. (b) Пълният двуделен граф $K_{3,3}$ има 6 върха, степента на всеки връх е 3 и не съдържа триъгълници. \newpage \paragraph{Задача 4.} \mbox{} %\\ \emph{Първи начин:} (a) Първо броим комбинациите с различни зарчета, те са $\binom{6}{2}=15$. Добавяме 6 комбинации за чифтове (случаите когато двете зарчета съвпадат). Получаваме общ брой 21. (b) Има $\binom{n}{2}$ случая на различни зарчета и $n$ случая на еднакви, общо $n(n-1)/2+n=n(n+1)/2$ или $\binom{n+1}{2}$. \vspace{5pt} \emph{Втори начин:} Търсим конфигурации без наредба, с повтаряне. Всяко хвърляне на зарче е избор на число от множеството $\{ 1, 2 \ldots n \}$. Избираме 2 пъти, като можем да повторим избора (да хвърлим чифт). Общата формула за избор на $k$ елемента от множество с $n$ елемента е $\binom{n+k-1}{k}$. В задачата $k=2$. (a) $n=6$, броят комбинации е $\binom{6+2-1}{2}=21$. (b) за произволно $n$ комбинациите са $\binom{n+2-1}{2}=\binom{n+1}{2}$. \paragraph{Задача 5.} \mbox{} (a) Таблицата на $f$ изглежда така: \begin{displaymath} \begin{array}{ccc|c} x & y & z & f\\ \hline 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} \end{displaymath} Построяваме елементарните конюнкции съгласно теоремата на Бул и ги поставяме в първата колона на таблицата на импликантите по-долу. След пресмятане на всички импликанти получаваме (със $*$ са отбелязани погълнатите имликанти): \begin{displaymath} \begin{array}{c|c|c} I_3 & I_2 & I_3 \\ \hline \overline{x}\overline{y}\overline{z}* & \overline{x}\overline{y}* & \overline{x} \\ \overline{x}\overline{y}z* & \overline{x}\overline{z}* & \overline{z} \\ \overline{x}y\overline{z}* & \overline{y}\overline{z}* & \\ \overline{x}yz* & \overline{x}z* & \\ x\overline{y}\overline{z}* & \overline{x}y* & \\ xy\overline{z}* & y\overline{z}* & \\ & x\overline{z}* & \\ \end{array} \end{displaymath} Простите импликанти са много прости -- $\overline{x}$ и $\overline{z}$. Сега строим таблица в която отбелязваме коя от тях покрива единица на $f$: \begin{displaymath} \begin{array}{c|c|c|c|c|c|c|c} N_f & \overline{x} & \overline{z} \\ \hline 000 & * & * \\ 001 & * & \\ 010 & * & * \\ 011 & * & \\ 100 & & * \\ 110 & & * \end{array} \end{displaymath} %Единиците $001$ и $110$ са покрити от единствените импликанти %$\overline{x}$ и $\overline{z}$, и двете са задължителни. Единицата на функцията $001$ е покрита само от импликантата $\overline{x}$, а единицата $110$ е покрита само от $\overline{z}$. Следователно и двете прости импликанти са задължителни, единствената минимална ДНФ е: \begin{align*} f(x,y,z) & = \overline{x} \lor \overline{z} \end{align*} (b) \emph{Първи начин:} Нека дефинираме $g(x,y)=f(x,y,y)$, ползваме минималната ДНФ и пресмятаме $g(x,y) = \overline{x} \lor \overline{y}$. Това е функцията на Шефер, тя е шеферова. \vspace{5pt} \emph{Втори начин:} Задачата може да се реши и с критерия на Пост. За да установим, че функцията $f$ е шеферова, достатъчно е да проверим, че тя не е самодвойнствена и не запазва нито нулата, нито единицата. Това лесно се вижда от таблицата на $f$. \end{document}