Тук са всички теми за теоретичната част на държавния изпит за специалност информатика. Написани са от мен, Иван Димитров Георгиев (вече завършил) студент по информатика, електронната ми поща е [email protected]
Материалът е съобразен изцяло с конспекта и съответните анотации, издадени и одобрени през май 2007 година. Лично аз съм се подготвял по тези материали.
За два въпроса (6 и 8) не съм сигурен, че изложението е пълно, т.е. ако ползвате този въпрос може да се допитате до съответния преподавател дали не трябва да се добави нещо. За въпрос 6 това е сигурно, тъй като ми се падна на изпита и на него имам 5 .
Пропуснато е изложението на въпрос номер 25, но за него има подходяща книга на доц. Черногорова, която се разпространява свободно в мрежата и може да бъде изтеглена от сайта на факултета.
Добре е да имате инсталиран MathType, за да нямате проблеми при разчитането. От този линк http://www.dessci.com/en/dl/MTW6.exe може да изтеглете trial версия за един месец.
1. Булеви функции. Теорема на Пост-Яблонски за пълнота.
Нека J2 = { 0, 1}. Всяка функция f : J2n J2, n , n ≥ 1 наричаме двоична (булева) функция.
Всяка функция f : J2n J2 можем да разглеждаме като функция на n независими променливи x1, x2, …, xn.
С F2n ще означаваме множеството на всички двоични функции на n променливи. Очевидно е, че |F2n| = .
Означаваме F2 = - множеството на всички двоични функции.
Въвеждаме стандартна (лексикографска) наредба на J2n:
= a1a2…an предшества = b1b2…bn, ако съществува
i { 1, 2, .., n}, такова че a1 = b1, a2 = b2, …, ai-1 = bi-1,
ai < bi (ai = 0, bi = 1). При стандартно подредени вектори от J2n всяка булева функция се задава еднозначно с двоичен
вектор-стълб с размерност 2n. Това означава, че i-тата компонента на вектора-стълб е стойността на функцията за i-тия вектор от J2n в стандартната наредба.
Нека f (x1, x2, …, xn) F2n, gi (y1, y2, …, ym) F2m, i = 1, 2, ..., n.
Функцията h (y1, y2, …, ym) = f (g1 (y1, …, ym), g2 (y1, …, ym), …,
gn (y1, …, ym)) наричаме суперпозиция на g1, g2, …, gn във f.
Казваме, че функцията f : J2n J2 не зависи съществено от променливата xi, ако f (x1, …, xi-1, 0, xi+1, …, xn) = f (x1, …, xi-1, 1, xi+1, …, xn). Още казваме, че xi е фиктивна променлива.
Ясно е, че към всяка двоична функция на n променливи можем да добавим колкото искаме фиктивни променливи. Така можем да считаме, че суперпозицията на g1, g2, …, gn във f е дефинирана дори когато g1, g2, …, gn са функции на различен брой променливи.
Нека F = { f0, f1, …} F2. Нека X = { f, x, 0, 1, (, ), <запетая> }.
По-нататък ще записваме думите f, x, където , { 0, 1}+ като
fi, xj, където е двоичното представяне на числото i, е двоичното представяне на числото j. Дефинираме индуктивно понятието формула над множеството от функции F:
База: За всяка функция fi F на n променливи думата
fi (x1, x2, …, xn) X* е формула над F.
Предположение: Нека fi F е функция на n променливи и
1, 2, …, n X* са формули над F или променливи, т.е. от вида xk.
Стъпка: Тогава думата fi (1, 2, …, n) X* е формула над F.
Функция от вида f (x1, …, xn) = xk наричаме идентитет.
Нека F = { f0, f1, …} F2. На всяка формула над F съпоставяме функция f F2 по следния начин:
База: Ако = fi (x1, …, xn), то определяме f = fi F.
Предположение: Нека fi F е функция на n променливи и
1, 2, …, n са формули или променливи и съответните им функции са g1, g2, …, gn F2. Aко j е променливата xk, то съответната функция gj е идентитетът xk.
Стъпка: Тогава на формулата = fi (1, …, n) съпоставяме суперпозицията f = fi (g1, …, gn).
С [F] ще означаваме множеството от всички двоични функции, съпоставени на формулите над F и ще го наричаме затваряне на F (относно суперпозицията).
Множеството от функции F F2 е пълно в F2, ако [F] = F2.
Очевидно е, че [ F2 ] = F2, но съществуването на пълни множества, различни от F2 не е очевидно.
Нека F F2. Казваме, че F е базис, ако:
1. F е пълно, т.е. [F] = F2.
2. F е минимално по включване с това свойство, т.е.
G F [G] F2.
Редактор: Снежина Стоянова
