\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} Писмен изпит по ДС за минали години, 3.02.2016г. \end{spacing} Име: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, ФН:\_\_\_\_\_, Спец./курс:\_\_\_\_\_\_\_ \end{center} \begin{center} \begin{tabular}{|l|c|c|c|c|c|c||c|} \hline Задача & 1 & 2 & 3 & 4 & 5 & 6 & Общо \\ \hline \hline получени точки & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & $\quad \quad$ & \\ \hline максимум точки & 20 & 20 & 20 & 20 & 20 & 20 & 120 \\ \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 %, м.г., Лесева } В равнината е даден квадратът $S=\{(x,y)\;|\;0\leq x\leq 5,\; 0\leq y\leq 5\}$. Релацията $R\subset S\times S$ е определена по следния начин: \[ R=\{((x_1,y_1),(x_2,y_2)) \;|\; x_1=x_2, \quad y_1-y_2 \in \mathbb{Z}\} \] Да се докаже, че $R$ е релация на еквивалентност и да се определи класът на еквивалентност на точката $(2,4)$. \paragraph{Задача 2% , м.г., Лесева, Скелета } Дадено е множество $A$ и функции $f: A \to A$ и $g: A \to A$, които са биекции. Известно е, че $\exists x_0 \in A: f(x_0)\neq g(x_0)$. Докажете, че $\exists x_1 \in A: x_1 \neq x_0, \; f(x_1)\neq g(x_1)$. \paragraph{Задача 3} Нека $n \in N^{+}$ и $a_n = 2 + 8 + 24 + \ldots + n2^n$. Намерете формула за $a_n$, като съставите линейно рекурентно уравнение за $a_n$ и го решите при подходящи начални условия. %\paragraph{Задача 2, Емилия} Нека $n \in N^{+}$ и $U = {1, 2,\ldots, 2n}$. Да се докаже, че за всяко множество $A \subset U, \; |A| = n + 1$ съществува $k\in U, \; k < 2n$, %такова че $k\in A$ и $(k + 1) \in A$. \paragraph{Задача 4} Точките от една окръжност са оцветени в два цвята. Докажете, че съществува равнобедрен триъгълник с едноцветни върхове, лежащи на окръжността. \emph{Упътване:} Впишете правилен петоъгълник в окръжността и разсъждавайте за цветовете на върховете му. %\paragraph{Задача 4, Емилия} Докажете, че Съвършената ДНФ на двоичната функция %$f(x_1,x_2\ldots x_n) = x_1 \oplus x_2 \oplus \ldots \oplus x_n$ е единственото представяне на %тази функция чрез ДНФ. %\paragraph{Задача 5, Емилия} Нека $G(V,E)$ е краен неориентиран граф и $v \in V$ e негов срязващ връх (след отстраняването на $v$ и ребрата, инцидентни с него, броят на свързаните компоненти на $G$ се увеличава). Нека $G_1$ е графът, получен от $G$ чрез отстраняване на $v$ и ребрата, инцидентни с него. Докажете, че допълнителният граф на $G_1$ е свързан. \paragraph{Задача 5} Нека графът $B_n$ e $n$-мерният двоичен куб (върховете са всички $n$-мерни двоични вектори, два върха са свързани, ако векторите им се различават на точно една позиция). Дайте обосновани отговори на следните въпроси: а) Колко ребра има най-късият път от връх $\alpha=00\ldots 0$ до връх $\beta=11\ldots 1$? б) Какъв е броят на всички най-кратки пътища от връх $\alpha$ до връх $\beta$? \paragraph{Задача 6} Напишете съвършената ДНФ и полинома на Жегалкин на булевата функция\\ $f(x,y,z)=(x\to y)\land (x\oplus z)$. %\paragraph{Задача 8, Лесева} Да се намерят всички минимални дизюнктивни нормални форми на двоичната функция $f(x,y,z)$ с единично множество $N_f=\{0, 1, 2, 5, 6\}$. \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}