\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} Писмен поправителен изпит по ДС, 29.08.2016г. \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 максимум точки & 20 & 20 & 20 & 20 & 30 & 110 \\ \hline \end{tabular} \end{center} \emph{Забележка:} За отлична оценка са достатъчни 100 точки! %\paragraph{Задача 1 % , м.г., Скелета} %Нека $R_1$ и $R_2$ са двуместни релации над множеството $A$ и $R_1 \subset R_2$. Докажете че:\\ %(а) Ако $R_2$ е антисиметрична, то $R_1$ е антисиметрична.\\ %(б) Ако $R_1$ е рефлексивна, то $R_2$ е рефлексивна. \paragraph{Задача 1 %, м.г., Лесева } Точките в равнината можем да представим чрез техните координати като двойки реални числа: $R^2=\{(x,y)\;|\; x\in R,\; y\in R\}$. Релацията $P\subset R^2 \times R^2$ е определена по следния начин: \[ P=\{((x_1,y_1),(x_2,y_2)) \;|\; x_1^2+y_1^2=x_2^2+y_2^2 \} \] Да се докаже, че $P$ е релация на еквивалентност и да се определи класът на еквивалентност на точката $(3,4)$. \paragraph{Задача 2% , м.г., Лесева, Скелета } При провеждане на първата изпитна сесия от 80 студенти в специалност КН, първи поток, изпита по ДИС издържали 33 студенти, по ЛА -- 45 и по ДС -- 52. Било установено, че ДИС и ЛА едновременно издържали 20 студенти, ДИС и ДС -- 28 студенти. 15 студенти заявили покрусени, че не са взели нито един от трите изпита. Колко студенти са положили успешно изпитите по ЛА и ДС, ако броят на студентите, издържали успешно и трите изпита е 13 ? \paragraph{Задача 3} Обикновен неориентиран граф не съдържа триъгълници (цикли с дължина 3) и от всеки връх излизат точно 3 ребра. (а -- 10т.) Докажете че графът има поне 6 върха. (б -- 10т.) Ако има такъв граф с точно 6 върха, нарисувайте го. \paragraph{Задача 4} Нека точките с цели координати в равнината са оцветени с 8 цвята. Докажете, че има две едноцветни точки на разстояние по-малко от 3. %\emph{Упътване:} Ползвайте принципа на Дирихле. \paragraph{Задача 5} За двоичната функция $f(x,y,z)$, определена с таблицата по-долу, намерете:\\ а) съвършената дизюнктивна нормална форма;\hfill (5 точки)\linebreak б) минималната дизюнктивна нормална форма;\hfill (15 точки)\linebreak в) полинома на Жегалкин.\hfill (10 точки)\linebreak \emph{\textbf{БОНУС:}}\;\; Шеферова функция ли е $f$\hspace{2pt}?\hfill (15 точки)\linebreak \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 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} \end{displaymath} \end{document} \newpage \paragraph{Примерни решения} \paragraph{Задача 7} Таблицата на $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*} \end{document} \paragraph{Задача 1} Да означим израза с $f(n)=2^{3n}-7n-1$. Очевидно $f(0)=0$ се дели на $49$. Нека допуснем, че $f(n)$ се дели на $49$. \begin{align*} f(n+1)&=2^{3(n+1)}-7(n+1)-1\\ &=2^{3n+3}-7n-7-1\\ &=2^{3}2^{3n}-7n-8\\ &=8.2^{3n}-8(7n+1)+8(7n+1)-7n-8\\ &=8(2^{3n}-7n-1)+56n+8-7n-8\\ &=8f(n)+49n \end{align*} Представихме $f(n+1)$ като сума на $8f(n)$ и $49n$. Двете събираеми се делят на $49$, следователно и $f(n+1)$ се дели на $49$. Получихме, че ако $f(n)$ се дели на $49$, то $f(n+1)$ също се дели на $49$. От принципа на индукцията следва, че за всяко $n\geq 0$ изразът $f(n)=2^{3n}-7n-1$ се дели на $49$. \paragraph{Задача 2} Оставяме на читателя тази лесна задача $\ldots$ \paragraph{Задача 3} Нека $f, g$ и $h$ са функции от $F$. $\forall x\in \{a,b,c,d\} \quad f(x) \equiv f(x) \pmod 2$, следователно $fRf$, тоест $R$ е рефлексивна. $\forall x\in \{a,b,c,d\} \quad (f(x) \equiv g(x) \pmod 2) \to (g(x) \equiv f(x) \pmod 2)$, следователно $fRg \to gRf$, тоест $R$ е симетрична. $\forall x\in \{a,b,c,d\} \quad ((f(x) \equiv g(x) \pmod 2) \land (g(x) \equiv h(x) \pmod 2)) \to (f(x) \equiv h(x) \pmod 2)$, следователно $(fRg)\land(gRh) \to fRh$, тоест $R$ е транзитивна. От трите разсъждения по-горе следва, че $R$ е релация на еквивалентност. Нека съпоставим на $f\in F$ редицата $B(f)=\alpha_1 \alpha_2 \alpha_3 \alpha_4$, където $\alpha_1=f(a) \pmod 2, \; \alpha_2=f(b) \pmod 2, \; \alpha_3=f(c) \pmod 2, \; \alpha_4=f(d) \pmod 2$. Очевидно $B(f)$ е редица от нули и единици. Произволни $f\in F, \; g\in F$ имат съвпадащи редици $B(f)$ и $B(g)$ точно когато $fRg$. Следователно изображението $B$ съпоставя една и съща булева редица $\alpha_1 \alpha_2 \alpha_3 \alpha_4$ на всички функции от един клас на еквивалентност на $R$ и различни булеви редици на функции от различни класове. Изображението $B$ поражда биекция между класовете на еквивалентност на $R$ и булевите редици с дължина 4, следователно броят на класовете е $2^4$. Броят на функциите $f\in F$ е $7^4$ (това са всички редици от 4 елемента, като всеки елемент има 7 възможни стойности). \paragraph{Задача 4} Нека с $A_k$ означим множеството от поредици, съвпадащи с отключващата поредица на точно $k$ места. Очевидно ще можем да отключим повредения сейф само с поредица от $A_4, A_5, A_6$ или $A_7$ и тия множества не се пресичат. Следователно броят на отключващите поредици е $n=|A_4|+|A_5|+|A_6|+|A_7|$. Броят на елементите на $A_4$ е $\binom{7}{4}9^3$, защото можем по $\binom{7}{4}$ начина да изберем 4-те позиции, за които знаем кода, и по $9^3$ начина да сбъркаме в останалите 3 позиции. Аналогично $A_5$ има $\binom{7}{5}9^2$ елемента, $A_6$ има $\binom{7}{6}9$ елемента, $A_7$ има $\binom{7}{7}=1$ елемент. Броят на всички отключващи поредици е: \[n=\binom{7}{4}9^3+\binom{7}{5}9^2+\binom{7}{6}9+1\] Оставяме на читателя да пресметне конкретната числова стойност на $n$. Има хипотеза, че $n=27280$, но не съм го пресмятал, един приятел ми го каза. \paragraph{Задача 5} Да означим с $A_1, A_2, A_3$ множествата студенти, спортуващи съответно плуване, бягане и волейбол. Прилагаме принципа за включване и изключване: $|A_1 \cup A_2 \cup A_3|=|A_1|+|A_2|+|A_3|-|A_1 \cap A_2|-|A_1 \cap A_3| - |A_2 \cap A_3|+|A_1 \cap A_2 \cap A_3|$ От условието на задачата знаем всички събираеми в дясната част на горното равенство, заместваме: $|A_1 \cup A_2 \cup A_3|=23+26+24-16-15-17+9=34$ Следователно от всички $35$ студенти $34$ спортуват поне един от трите вида спорт, а един не спортува (възможно е да играе шах или бридж). \paragraph{Задача 6} Очевидно $R_1=F_1=1$ и $R_2=F_2=1$. За $n>2$ можем да опростим рекурентното равенство за $R_n$: \begin{align*} R_n&=R_0+\ldots+R_{n-2}\\ R_n&=(R_0+\ldots+R_{n-3})+R_{n-2}\\ R_n&=R_{n-1}+R_{n-2} \end{align*} Опростяването следва от равенството $R_{n-1}=R_0+\ldots+R_{n-3}$, валидно за $n>2$ (то се получава като заменим $n$ с $n-1$ в рекурентното равенство за $R_n$). Следователно редиците $R_n$ и $F_n$ имат еднакви рекурентни равенства за $n>2$. Очевидно, след като имаме равенство в двете редици на членове с номера $1$ и $2$ и изчисляваме следващите членове с еднакви рекурентни равенства, ще получаваме еднакви членове и за номера $3,\; 4$ и т.н. Формалното доказателство на равенството на всички членове с номера над $1$ следва да се извърши с индукция: Ползваме равенствата $R_1=F_1=1$ и $R_2=F_2=1$ като база за индукция. От равенствата $R_n=R_{n-1}+R_{n-2}$ и $F_n=F_{n-1}+F_{n-2}$, верни за $n>2$, следва твърдението: \[(\forall k \; (n>k>0) \to (R_k=F_k)) \to R_n=F_n\] Разказано с думи, то изглежда така: Ако за $k=1,2\ldots n-1$ има съвпадение на $R_k$ и $F_k$, от рекурентните равенства следва, че $R_n=F_n$. От принципа на пълната индукция следва твърдението на задачата $\forall n \; (n>0) \to (R_n=F_n)$. \end{document}