КОНСПЕКТ
по дискретна математика
за II курс приложна математика, I поток
2002/2003 уч. година

  1. Крайни множества.
  2. Равномощност на множества.
  3. Теорема на Кантор за мощността на множеството на подмножествата. Сравняване на множествата по мощност.
  4. Изброими множества.
  5. Двоични функции. Теорема на Бул.
  6. Множеството {0,1} като поле. Теорема на Жегалкин.
  7. Изразимост на двоична функция чрез дадено множество от двоични функции.
  8. Пълни множества от двоични функции. Класове на Пост.
  9. Изразимост на константите чрез произволно множество от двоични функции, което не се съдържа в никой от класовете T0, T1 и S.
  10. Изразимост на отрицанието чрез произволно множество от двоични функции, което не се съдържа в никой от класовете T0, T1 и M.
  11. Критерий на Пост за пълнота на множество от двоични функции.
  12. Графи и пътища в тях. Дървета.
  13. Думи и езици над дадена азбука. Регулярни езици над дадена азбука.
  14. Крайни автомати. Граф и език на краен автомат. Премахване на недостижимите състояния на краен автомат.
  15. Еквивалентност на крайните автомати с произволни думи в преходите с такива крайни автомати, при които тези думи не са празни, и с такива крайни автомати, при които думите в преходите са еднобуквени.
  16. Детерминизация на краен автомат.
  17. Функция на преходите на тотален детерминиран автомат.
  18. Еквивалентни състояния на краен детерминиран автомат. Дефиниция за минимален автомат. Намиране на минимален автомат, еквивалентен на даден тотален детерминиран автомат.
  19. Дясна конгруентност относно даден език и нейното приложение към въпроса за минималните автомати, еквивалентни на даден тотален детерминиран автомат.
  20. Лема за разрастване за автоматните езици.
  21. Затвореност на класа на автоматните езици над дадена азбука относно обединение, допълнение и сечение.
  22. Доказателство, че регулярните езици са автоматни.
  23. Формални граматики и техните езици.
  24. Безконтекстни граматики и безконтекстни езици. Доказателство, че автоматните езици са безконтекстни.
  25. Алгоритъм за разпознаване на принадлежността към език, породен от нескъсяваща граматика.
  26. Затвореност на класа на безконтекстните езици над дадена азбука относно обединение, конкатенация и итерация.
  27. Лема за разрастване за безконтекстните езици.
  28. Доказателство, че класът на безконтекстните езици не е затворен относно сечение и относно допълнение.