\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}
Поправителен изпит по Дискретни структури, 25.08.2019г.
\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}

\paragraph{Задача 1.} %\mbox{}\\
% индукция

Докажете, че числото $n^3+2n$ се дели на 3 за $\forall n \in \mathbb{N}$.

\paragraph{Задача 2.}
% Дирихле 

Нека $G(V,E)$ е неориентиран свързан граф с поне два върха. 

Докажете, че в $G$ има върхове с еднаква степен.


\paragraph{Задача 3.}  

% комбинаторика

При играта "генерал" играчите хвърлят 5 зарчета при започване на всеки ход.
Зарчето има 6 страни, на които са обозначени от една до шест точки.
Комбинация на зарчетата наричаме петорката числа, която съответства на броя на точките върху горната страна на падналите зарчета.\\
Редът на числата няма значение, тоест петорките $(2,5,1,6,5)$ и $(6,5,5,2,1)$ представят една комбинация.

Колко са възможните комбинации?


\paragraph{Задача 4.} 

% графи

В неориентиран граф от всеки връх излизат точно три ребра.

(a - 8 точки) Докажете, че графът има четен брой върхове.

(b - 8 точки) Докажете, че в графа има цикъл.

\paragraph{Задача 5.} %\mbox{}

% булева функция

Двоичната функция $f(x,y,z)$ е определена с редицата стойности $f=(11100110)$.

% Да се намерят всички минимални дизюнктивни нормални форми на двоичната функция $f(x,y,z)$ с единично множество $N_f=\{0, 1, 2, 5, 6\}$.

(a - 10 точки) Намерете всички минимални дизюнктивни нормални форми на $f(x,y,z)$.

(b - 6 точки) Шеферова ли е функцията $f$ ?

\newpage

\section*{Решения}


\paragraph{Задача 2.}

Нека графът има $n$ върха и степените им са $d_1, d_2, \ldots d_n$.

Най-голямата степен не превишава $n-1$, а най-малката е поне $1$, защото $G$ e свързан.
Следователно, множеството от степените на върховете има най-много $n-1$ елемента.

Прилагаме принципа на Дирихле, като предметите са $n$-те върха на графа, а чекмеджетата са степените им.
Тъй като възможните степени са най-много $n-1$, ще има два върха с еднакви степени.

Твърдението на задачата е вярно и за несвързан граф.
Ако $G$ не е свързан, може да има връх със степен $0$, но най-голямата степен не надвишава $n-2$.
И в този слугай множеството от степените има по-малко от $n$ елемента. 

\paragraph{Задача 3.}  

Търсим конфигурации без наредба, с повтаряне.
Всяко хвърляне на зарче е избор на число от множеството $\{ 1, 2 \ldots 6 \}$.
Избираме 5 пъти, като можем да повторим избора (да има еднакви числа на хвърлените зарчета).

Общата формула за избор на $k$ елемента от множество с $n$ елемента е $\binom{n+k-1}{k}$.
В задачата $k=5, n=6$.

Следователно, броят комбинации е $\binom{6+5-1}{5}=\binom{10}{5}=252$.


\paragraph{Задача 4.} 

Условие (a):

Нека $n$ е броят на върховете, а $m$ е броят на ребрата на графа.
Щом от всеки връх излизат по три ребра, то всички ребра са $m=3n/2$,
защото всяко ребро е броено два пъти --- по веднъж за всеки от двата върха,
които свързва. 

Следователно числото $3n$ е четно, тогава и $n$ е четно.

Условие (b):

\textbf{Първи начин:}

Нека $v_{_1}$ е произволен връх на графа.
От $v_{_1}$ излизат три ребра.
По някое от тях преминаваме към друг връх $v_{_2}$.
Но и от $v_{_2}$ излизат три ребра.
По едно от тях току-що сме пристигнали във $v_{_2}$,
по някое от другите две продължаваме към друг връх $v_{_3}$
и тъй нататък.
Получава се път $v_1, v_2, v_3, \ldots$,
който не може да е безкраен.

Следователно на някоя стъпка върхът, в който отиваме,
ще съвпада с някой от вече посетените върхове,
т.е. ще открием цикъл в графа.

\textbf{Втори начин:}

Допускаме противното: че графът не съдържа цикъл.

Тогава графът е гора. Няма изолирани върхове в гората, защото от всеки връх излизат ребра.
Всяко дърво в гората ще има поне едно листо.

Но листата са върхове, от които излиза единствено ребро,
което е противоречие: 
по условие от всички върхове на дадения граф излизат по три ребра.

Следователно, графът съдържа цикъл.


% \newpage

\paragraph{Задача 5.} 

Условие (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 & 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*}

Условие (b):

Функцията $f$ е шеферова, защото сама образува пълно множество.
Това може да се докаже, като изразим чрез $f$ друго множество от булеви функции,
за което знаем, че е пълно:

Функцията на Шефер $x|y$, която сама образува пълно множество се изразява така:\\
$x|y=f(x,x,y)$

Горното тъждество може да бъде проверено по табличния метод.

Задачата може да се реши и с критерия на Пост.
За да установим, че $f$ е шеферова,
достатъчно е да проверим, че тя не е самодвойнствена
и не запазва нито нулата, нито единицата.
Това лесно се вижда от таблицата на $f$.



\end{document}