\documentclass[11pt,oneside,a4paper]{article} \usepackage[margin=2cm]{geometry} \usepackage{fancyhdr} \usepackage{amsmath,amsthm,amssymb} \usepackage{graphicx} \usepackage{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} \begin{document} \begin{center} \begin{spacing}{2} Изпит по Дискретни структури, 16.02.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 максимум точки & 4 & 6 & 4 & 8 & 8 & 30 \\ \hline \end{tabular} \end{center} \paragraph{Задача 1.} %\mbox{}\\ Дадени са шест естествени числа.\\ Докажете, че разликата на две от тях се дели на 5. \paragraph{Задача 2.} Колко са различните цикли с дължина $4$ в пълния двуделен граф $K_{3,3}$?\\ Обосновете отговора си. %Дайте кратко описание на $R'$ и опишете класовете \`{и} на еквивалентност. \paragraph{Задача 3.} В една от групите на специалност Компютърни науки, втори поток, има 25 студенти. Изпита по алгебра издържали 14 студенти, по ДИС -- 11, по УП -- 14. След второ, по-подробно проучване било установено, че алгебра и ДИС издържали 8 студенти, алгебра и УП -- 9, ДИС и УП -- 7, а 5 студенти си взели и трите изпита. Колко студенти са скъсани и по трите учебни дисциплини ? \paragraph{Задача 4.} Даден е неориентиран граф $G(V,E)$ с върхове $V=\{1,2,\ldots ,10\}$ и ребра \\ $E=\{(1,2),(1,3),(1,9),(2,4),(2,6),(3,4),(3,5),(4,8),(5,6),(5,7),(6,10),(7,8),(7,9),(8,10),(9,10)\}$.\\ Дайте обоснован отговор на въпросите: (a - 4 точки) Двуделен ли е графът $G(V,E)$? (b - 4 точки) Има ли хамилтонов цикъл в $G(V,E)$? \paragraph{Задача 5.} %\mbox{} Двоичната функция $f(x,y,z)$ е определена с редицата стойности $f=(10111110)$. (a - 4 точки) Намерете минимална дизюнктивна нормална форма на $f(x,y,z)$. (b - 4 точки) Шеферова ли е функцията $f$? \newpage \end{document} \paragraph{Задача 6} Таблицата на $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 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} \end{displaymath} Построяваме елементарните конюнкции съгласно теоремата на Бул и ги поставяме в първата колона на таблицата на импликантите по-долу. %Импликантите ще записваме като 4-буквени поредици от символите $0,1,e$, като $e$ съответства на липсваща промелива, $0$ на отрицание на съответната промелива, а $1$ на промелива без отрицание. След пресмятане на всички импликанти получаваме (със $*$ са отбелязани погълнатите имликанти): \begin{displaymath} \begin{array}{c|c|c} I_3 & I_2 & \\ \hline \overline{x}\overline{y}\overline{z}* & \overline{x}\overline{y} & \\ \overline{x}\overline{y}z* & \overline{x}\overline{z} & \\ \overline{x}y\overline{z}* & \overline{y}z \\ x\overline{y}z* & y\overline{z} \\ xy\overline{z}* & \\ \end{array} \end{displaymath} Сега строим таблица в която отбелязваме коя проста имликанта покрива единица на $f$: \begin{displaymath} \begin{array}{c|c|c|c|c|c|c|c} N_f & \overline{x}\overline{y} & \overline{x}\overline{z} & \overline{y}z & y\overline{z} \\ \hline 000 & * & * & & \\ 001 & * & & * & \\ 010 & & * & & * \\ 101 & & & * & \\ 110 & & & & * \end{array} \end{displaymath} Единиците $101$ и $110$ са покрити от единствените импликанти $\overline{y}z$ и $y\overline{z}$, следователно те са задължителни. Те двете не покриват единствено единицата $000$, можем да я покрием с коя да е от импликантите $\overline{x}\overline{y}$ и $\overline{x}\overline{z}$. Те са с еднакъв брой букви, следователно има две минимални ДНФ: \begin{align*} f(x,y,z) & = \overline{x}\overline{y} \lor \overline{y}z \lor y\overline{z}\\ f(x,y,z) & = \overline{x}\overline{z} \lor \overline{y}z \lor y\overline{z}\\ \end{align*} \subsection*{Решения:} \paragraph{\mbox{Задача 1.}} \mbox{} Означаваме с $f(n)=n^3+2n$ изразът, който ни интерсува. Първи начин (индукция): Очевидно $f(0)=0$ се дели на 3. Нека $f(n)$ се дели на 3, тогава $f(n+1)=(n+1)^3+2(n+1)=n^3+3n^2+3n+1+2n+2=n^3+2n+3(n^2+n+1)$. Получаваме $f(n+1)=f(n)+3(n^2+n+1)$, което се дели на 3, защото двете събираеми се делят на 3. Втори начин (делимост): Разглеждаме 3 възможни случая за $n$, в зависимост от остатъка при делене на 3. (1) $n=3k$, тогава $f(n)=3k(n^2+2)$ се дели на 3. (2) $n=3k+1$, тогава $f(n)=27k^3+27k^2+9k+1+6k+2$ се дели на 3. (3) $n=3k+2$, тогава $f(n)=27k^3+54k^2+36k+8+6k+4$ се дели на 3. \paragraph{\mbox{Задача 2.}} \mbox{} %$R'$ е релация на еквивалентност, тъй като е рефлексивна, симетрична и транзитивна. Да вземем произволно цяло число $x$ и да определим класа му на еквивалентност, тоест кои други цели числа са свързани с него относно релацията $R'$: (1) От $R \subset R'$ следва, че $(x,x+5)\in R'$, тоест $x+5 \in [x]$. (2) Понеже $R'$ е рефлексивно затваряне, следва че $x \in [x]$. (3) Понеже $R'$ е симетрично затваряне, следва че $(y+5,y)\in R'$ за произволно $y$, заместваме $x=y+5$ и получаваме $x-5 \in [x]$. (4) $R'$ е транзитивно затваряне. Ще докажем по индукция, че $x+5k \in [x]$ за всяко естествено $k$: От (2) следва, че $x+5\times 0 \in [x]$. Нека $(x,x+5k) \in R'$. От (1) $(x+5к,x+5k+5)\in R'$, и от транзитивноста на $R'$ следва $(x,x+5(k+1))\in R'$. Аналогично доказваме, че $x-5k \in [x]$ за всяко естествено $k$. Получаваме, че класът на еквивалентност $[x]$ се състои от всички цели числа, които при делене на 5 имат същия остатък, както и $x$. Има 5 различни такива класове на еквивалентност -- множествата от цели числа, даващи съответно остатъци 0, 1, 2, 3 и 4 при делене на 5. \paragraph{\mbox{Задача 3.}} \mbox{} В множеството $I_{10}$ има точно 5 четни и точно 5 нечетни числа. Но $A$ има 6 елемента, то ще съдържа поне едно четно число $a$ и поне едно нечетно число $b$ Сумата на двете $a+b$ е нечетна. \paragraph{\mbox{Задача 4.}} \mbox{} (a) Ще записваме съкратено една пермутация $f$ като редица от стойностите $(f(1), f(2) \ldots f(n))$. При този съкратен запис $(2,3,4,1)$ означава $f(1)=2, f(2)=3, f(3)=4, f(4)=1$. Лесно се проверява, че $(2,3,4,1)$ е една от цикличните пермутации при $n=4$. Цикличните пермутации при $n=4$ са общо 6 на брой, те са: $(2,3,4,1)$, $(2,4,1,3)$, $(3,4,2,1)$, $(3,1,4,2)$, $(4,3,1,2)$, $(4,1,2,3)$ (b) Броят на цикличните пермутации за произволно $n$ е $(n-1)!$ (всички пермутации са $n!$). Има различни начини да се уверим в това, ето един от тях: Да си представим, че турист иска да посети $n$ музея за един ден. В началото на разходката си той посещава музей 1, който е близо до хотела, в който е отседнал. След разглеждането на всеки музей, туристът прави преход до друг музей, като всички посетени музеи са различни и накрая туристът се връща уморен в хотела. Нека с $a_0=a_n=1$ означим началния/крайния пункт на разходката на туриста (музей номер 1, или хотела на туриста). Нека $a_i$ е номерът на музея, посетен след $i$-тия преход. Множеството от двойки $(a_i,a_{i+1}), 0\le i 0$ следва $y_i\ge 0$. Търсим броя на редиците $y_1,y_2,\ldots,y_k$. Сумата на числата $\displaystyle\sum_{i=1}^{k}y_i=n-k$ и $y_i\ge 0$. Пак търсим броя на конфигурациите без наредба и с повторение. Сега броят на елементите е $n-k$, а броят на конфигурациите е $\binom{n-1}{k-1}$. В терминологията на низ от звездички и чертички, след изтриването на звездичка във всеки интервал, низът се скъсява (изтрили сме точно $k$ звезди). Дължината на низа става $n-1$, броят на '|' остава $k-1$, а броят начини по които можем да разположим чертичките в низа е $\binom{n-1}{k-1}$. \end{document}