\documentclass[11pt,oneside,a4paper]{article} \usepackage[margin=2cm]{geometry} \usepackage{fancyhdr} \usepackage{amsmath,amsthm,amssymb} \usepackage{graphicx} \usepackage[pdftex, pdfauthor={Skelet}, pdftitle={DS, KN1, 29.08.2018}, pdfsubject={Discrete structures}, pdfstartview={FitH} ]{hyperref} \usepackage{mathtext} \usepackage[T1,T2A]{fontenc} \usepackage[utf8]{inputenc} \usepackage[english,bulgarian]{babel} \usepackage{setspace} \usepackage{verbatim} %\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.\,2018 г. \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$. Докажете, че числото $n^3-n$ се дели на 6 за $\forall n \in \mathbb{N}$. \paragraph{Задача 2.} Нека $A$ е множеството от всички безкрайни редици $\alpha=\alpha_0\alpha_1\alpha_2\ldots$, състоящи се от нули и единици ($\alpha_i \in \{0,1\}$) Определяме релацията $R \subseteq A\times A$ така -- две редици $\alpha=\alpha_0\alpha_1\alpha_2\ldots$ и $\beta=\beta_0\beta_1\beta_2\ldots$ са в релация, когато се различават на краен брой позиции. (a - 8 точки) Докажете, че $R$ е релация на еквивалентност. (b - 8 точки) Докажете, че класовете на еквивалентност, породени от $R$ са безкрайни изброими множества. %Нека $\mathbb{N}$ е множеството на естествените числа, а $2^\mathbb{N}$ е множеството от подмножествата му. \paragraph{Задача 3.} Нека $G$ е графът на Петерсен. (a - 8 точки) Докажете, че за произволно избрани 5 върха в $G$, поне два са съседни (свързани са с ребро). (b - 8 точки) Може ли да изберем 4 върха в $G$ така, че да няма ребра между тях? \paragraph{Задача 4.} Всеки от $n$ студента трябва да запише 2 избираеми дисциплини. Студентите могат да избират измежду $k$ дисциплини. Колко са възможните начини за записване от групата студенти? \paragraph{Задача 5.} Намерете минимална дизюнктивна нормална форма на булевата функция $f(x,y,z)=(\overline{x}\wedge z)\vee (x\oplus y)$. \pagebreak {\centering\textbf{РЕШЕНИЯ}\par} \vspace{-10pt} \paragraph{\mbox{Задача 1.}} \mbox{} Означаваме с $f(n)=n^3-n$ изразът, който ни интересува. \emph{Първи начин} (индукция): Очевидно $f(0)=0$ се дели на 6. Нека $f(n)$ се дели на 6, тогава $f(n+1)=(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=n^3-n+3(n^2+n)$. Получаваме $f(n+1)=f(n)+3n(n+1)$, което се дели на 6, защото двете събираеми се делят на 6 ($n(n+1)$ се дели на 2, защото или $n$ или $n+1$ е четно). \emph{Втори начин} (делимост): Преобразуваме: $f(n)=n^3-n=n(n-1)(n+1)$ $n(n-1)(n+1)$ се дели на 6, защото от трите поредни числа $n-1, n$ и $n+1$, точно едно се дели на 3, а едно или две се делят на 2. \paragraph{Задача 2.} \mbox{} %\\ Свойството $(\alpha,\beta) \in R$ можем да изкажем така -- съществува $n_0 \in \mathbb{N}$, такова че за всяко $i>n_0, \alpha_i=\beta_i$. Достатъчно е за $n_0$ да изберем най-големия номер на позиция, в която двете редици се различават. (a) Рефлексивността на $R$ следва от факта, че всяка редица се различава от себе си в нула позиции. Симетричността на $R$ също следва тривиално от симетричността на дефиницията на релацията. Транзитивност: нека $(\alpha,\beta) \in R, \quad (\beta,\gamma) \in R$. Съществуват номера $n_0,n_1$, такива, че за $i>n_0, \alpha_i=\beta_i$ и за $i>n_1, \beta_i=\gamma_i$. Нека $n_2=max(n_0,n_1)$, тогава за всяко $i>n_2, \alpha_i=\beta_i, \beta_i=\gamma_i$, следователно за $i>n_2, \alpha_i=\gamma_i$, тоест $(\alpha,\gamma) \in R$. (b) Нека $\alpha \in A$ е редица от нули и единици, а $[\alpha]$ е породеният от нея клас на еквивалентност относно релацията $R$. Построяваме биекция между $[\alpha]$ и $\mathbb{N}$ така: На $\alpha$ съпоставяме 0. Нека $\beta \neq \alpha, (\alpha,\beta) \in R$. Редиците $\alpha$ и $\beta$ се различават на поне една позиция, нека $n$ е най-големият номер на позиция, в която се различават. Стром двоично число $j$ с $n+1$ цифри, което има единици в позиции, където $\alpha$ и $\beta$ се различават, като броим позциите от $n$ към $0$, двоичният запис изглежда така: $j=(\alpha_n\oplus \beta_n)(\alpha_{n-1}\oplus \beta_{n-1})\ldots(\alpha_0\oplus \beta_0) $ Старшата цифра на $j$ е единица, тоест $j>0$. На $\beta$ съпоставяме числото $j$. Лесно се вижда, че построеното съпоставяне е биекция, следователно $[\alpha]$ е изброимо безкрайно множество. \begin{comment} Нека $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$. \end{comment} \begin{comment} \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 и не съдържа триъгълници. \end{comment} %\newpage \paragraph{Задача 4.} \mbox{} %\\ %Всеки от $n$ студента трябва да запише 2 избираеми дисциплини. %Студентите могат да избират измежду $k$ дисциплини. %Колко са възможните комбинации за записване от групата студенти? Всеки студент избира 2 от $k$ дисциплини, това става по $\binom{k}{2}$ начина. Комбинациите за записване са редици от избора на $n$-те студента. Тъй като всеки член на редицата има $\binom{k}{2}$ възможни стойности, броят на възможните комбинации е $\binom{k}{2}^n$. \newpage \paragraph{Задача 5.} \mbox{} %Намерете минимална дизюнктивна нормална форма на булевата функция %$f(x,y,z)=(\overline{x}\wedge z)\vee (x\oplus y)$. Изчисляваме $f$ в табличен вид: \begin{displaymath} \begin{array}{ccc|c|c|c} x & y & z & \overline{x}\wedge z & x\oplus y & f\\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \end{array} \end{displaymath} Построяваме елементарните конюнкции съгласно теоремата на Бул и ги поставяме в първата колона на таблицата на импликантите по-долу. След пресмятане на всички импликанти получаваме (със $*$ са отбелязани погълнатите имликанти): \begin{displaymath} \begin{array}{c|c|c} I_3 & I_2 & I_1 \\ \hline \overline{x}\overline{y}z* & \overline{x}z & \\ \overline{x}y\overline{z}* & \overline{y}z & \\ \overline{x}yz* & \overline{x}y & \\ x\overline{y}\overline{z}* & x\overline{y} & \\ x\overline{y}z* & & \\ & & \\ \end{array} \end{displaymath} Простите импликанти са $\overline{x}z, \overline{y}z, \overline{x}y$ и $x\overline{y}$. Сега строим таблица в която отбелязваме коя от тях покрива единица на $f$: \begin{displaymath} \begin{array}{c|c|c|c|c|c|c|c} N_f & \overline{x}z & \overline{y}z & \overline{x}y & x\overline{y} \\ \hline 001 & * & * & & \\ 010 & & & * & \\ 011 & * & & * & \\ 100 & & & & * \\ 101 & & * & & * \end{array} \end{displaymath} %Единиците $001$ и $110$ са покрити от единствените импликанти %$\overline{x}$ и $\overline{z}$, и двете са задължителни. Единицата на функцията $010$ е покрита само от импликантата $\overline{x}y$, а единицата $100$ е покрита само от $x\overline{y}$. Следователно и двете прости импликанти са задължителни. Те покриват и единици $011$ и $101$. Остава непокрита само $001$, за която имаме избор от другите 2 прости импликанти $\overline{x}z$ и $\overline{y}z$. Следователно има две минимални ДНФ и те са: \begin{align*} f(x,y,z) & = \overline{x}z \lor \overline{x}y \lor x\overline{y} \\ f(x,y,z) & = \overline{y}z \lor \overline{x}y \lor x\overline{y} \end{align*} \end{document}