Булеви функции. Теорема на Пост-Яблонски за пълнота


Категория на документа: Информатика


Тук са всички теми за теоретичната част на държавния изпит за специалност информатика. Написани са от мен, Иван Димитров Георгиев (вече завършил) студент по информатика, електронната ми поща е ivandg@yahoo.com.
Материалът е съобразен изцяло с конспекта и съответните анотации, издадени и одобрени през май 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.




Сподели линка с приятел:





Яндекс.Метрика
Булеви функции. Теорема на Пост-Яблонски за пълнота 9 out of 10 based on 2 ratings. 2 user reviews.