\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}
Поправителен изпит по Дискретни структури, 10.09.2020 г.
\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+5n$ се дели на 6 за $\forall n \in \mathbb{N}$.

\paragraph{Задача 2.}
%Фрагмент от теорема на Берж за максималното покритие 

Даден е неориентирания граф $G(V,E)$. 

Ребрата са боядисани в два цвята -- син и червен, като от всеки връх излиза най-много едно синьо и най-много едно червено ребро. 

Сините ребра са повече от червените.

Докажете, че в $G$ има път със следните свойства:

(1) От крайните върхове на пътя излиза точно по едно ребро.

(2) Крайните ребра в пътя са сини.



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

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

Играта спортен бридж започва с раздаване на тесте от 52 карти.
Четирите играча получават по 13 карти от тестето, което съдържа 4 вида карти (цвята) - трефи, кари, купи, пики. Всеки цвят в тестето съдържа 13 карти, означавани със символите $2,3,\ldots,9,T,J,D,K,A$.

Разпределение наричаме редицата от числа $(c,d,h,s)$, 
която задава броя на трефите, карите, купите и пиките, които играчът е получил при раздаването. 

Колко са разпределенията, при които играчът има поне два цвята с точно 4 карти във всеки от тях?


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

Колко са всички разпределения в играта спортен бридж?

\emph{Упътване:} Дефиниция на разпределение е дадена в предната задача.

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

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

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

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


\newpage

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


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

Разглеждаме свързаните компоненти на графа.

Тъй като от всеки връх излизат най-много 2 ребра, тези компоненти са цикли, прости пътища или изолирани върхове.

Изолираните върхове не са интересни.

Циклите се състоят от редуващи се сини и червени ребра. За да няма съседни едноцветни ребра, трябва циклите да са с четен брой ребра. Следователно броят на червените и сини ребра във всички цикли е еднакъв. 

Остават простите пътища, те също се състоят от редуващи се сини и червени ребра.
Ако единия край на път е червен, броят на червените ребра е равен на сините (при друг син край) или по-голям (при друг червен край).

След като общия брой на сините ребра е по-голям от червените, нужно е да има поне една компонента с повече сини ребра. Единствената възможност е прост път с два сини края.


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


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

\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 & 1 \\
1 & 0 & 1 & 0 \\
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|c}
 I_3  &  I_2 & I_1 & \\
\hline
\overline{x}\overline{y}\overline{z}* & \overline{x}\overline{y} & \overline{z} \\
\overline{x}\overline{y}z* & \overline{x}\overline{z}*  & \\
\overline{x}y\overline{z}* & \overline{y}\overline{z}* & \\
x\overline{y}\overline{z}* & y\overline{z}* & \\
xy\overline{z}* &  x\overline{z}* & \\
\end{array}
\end{displaymath}

Сега строим таблица в която отбелязваме коя проста имликанта покрива единица на $f$:

\begin{displaymath}
\begin{array}{c|c|c|c}
 N_f & \overline{x}\overline{y} & \overline{z} & \\
\hline
000 & *    & *       \\
001 & *    &         \\
010 &      & *       \\
100 &      & *         \\
110 &      & *      
\end{array}
\end{displaymath}
 
Единиците $001$ и $010$ са покрити от единствените импликанти 
$\overline{x}\overline{y}$ и $\overline{z}$, следователно те са задължителни. 

Следователно, функцията има единствена минимална ДНФ:

\begin{displaymath}
f(x,y,z) = \overline{x}\overline{y} \lor \overline{z}
\end{displaymath}

%\newpage

Условие (b):

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

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

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

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



\end{document}