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 е базис, ако:
-
F е пълно, т.е. [F] = F2.
-
F е минимално по включване с това свойство, т.е.
G F [G] F2.
Дефинираме двоична функция f (x, ) = x по следния начин:
x = x, ако = 1 и x = , ако = 0.
Лема: 0 = , 1 = .
Формули от вида , където при j s, j { 0, 1}, наричаме елементарни конюнкции.
Теорема (Бул): Множеството { x y, xy, } е пълно.
Доказателство: Ако f =, можем да представим f = x и тогава
f [{ x y, xy, } ].
Нека f . Тогава f (x1, x2, …, xn) = , което е формула над { x y, xy, }.
В означенията на доказателството, когато f , формулата се нарича съвършена дизюнктивна нормална форма на f.
Теорема: Нека F F2 е пълно множество, G F2 и за всяка функция f F имаме f [G]. Тогава G е пълно множество.
Следствие: { xy, } е пълно, { x y, } е пълно,
{ , , xy, x y } е пълно.
Доказателство: От теоремата на Бул и законите на Де Морган , и от = x .
Да се спрем на последното пълно множество от следствието.
Нека f F2. Тогава f има формула над { , , xy, x y }. Разкриваме скобите във формулата, като прилагаме дистрибутивния закон на конюнкцията спрямо събирането по модул 2, използваме идемпотентността на умножението (xx = x) и факта, че f f = . Накрая получаваме многократна сума по
модул 2 от елементарни конюнкции без отрицания, като една елементарна конюнкция участва най-много веднъж. При това, от аналогията на конюнкцията с умножението по модул 2, получената формула може да разглеждаме като полином над полето GF (2) (полето с два елемента). Наричаме я полином на Жегалкин.
Теорема: Всяка булева функция има и то единствен полином на Жегалкин.
Доказателство: Всяка функция има полином, различните функции имат различни полиноми и броят на полиномите е = |F2n|.
Казваме, че множеството F F2 е затворено, ако [F] = F.
Например F2 е затворено, тъй като [F2] = F2.
Множествата {}, {}, { x, } също са затворени.
Теорема (критерий за затвореност): Нека F F2 е такова, че
-
f (x) = x F;
-
за всяка функция f (x1, …, xn) F и g1, …, gn F имаме
h = f (g1, …, gn) F.
Тогава F е затворено множество.
Kазваме, че функцията f (x1, …, xn) F2 запазва нулата, ако
f (0, …, 0) = 0. Kазваме, че функцията f (x1, …, xn) F2 запазва единицата, ако f (1, …, 1) = 1.
Oзначаваме с T0 множеството от всички булеви функции, които запазват нулата. Tези от тях които са на n променливи
означаваме с T0n. Oзначаваме с T1 множеството от всички булеви функции, които запазват единицата и с T1n тези от тях, които са на n променливи.
Например xy T0, x y T0, xy T1, x y T1, x T0, x T1,
T0, T1, x y T0, x y T1.
Така T0 F2 и T1 F2.
Очевидно, |T0n| = = |T1n|, тъй като всяка функция запазваща коя да е от константите се дефинира по произволен начин върху всички вектори освен един.
Теорема: Множествата T0 и T1 са затворени множества от булеви функции.
Доказателство: Директно от критерия за затвореност.
Нека f (x1, …, xn) F2. Функцията f *(x1, …, xn), определена по следния начин: за всеки вектор a1…an J2n,
f *(a1, …, an) = наричаме двойнствена на f.
Векторите = a1a2…an J2n и = … J2n наричаме противоположни вектори.
Лема: В стандартната наредба на J2n, противоположните вектори са симетрично разположени относно средата на таблицата.
От тази лема получаваме следният алгоритъм за намиране на двойнствена функция, зададена със своя вектор-стълб:
-
инвертираме всяка стойност в стълба;
-
завъртаме симетрично стълба около средата.
Като непосредствено следствие от алгоритъма получаваме:
за всяка функция f F2, (f *)* = f.
С прилагане на алгоритъма можем да установим следните двойнствености: ()* = , (x)* = x, ()* = , (xy)* = x y.
Лема (двойнственост на сложна функция):
Ако h = f (g1, …, gn), то h* = f *(g1*, …, gn*).
Функцията f (x1, …, xn) F2 наричаме самодвойнствена,
ако f * = f. Със S означаваме множеството от всички самодвойнствени функции, със Sn тези от тях, които са на n променливи.
Например x, са самодвойнствени, xy не е самодвойнствена.
Така S F2.
Лема: Функцията f на n променливи е самодвойнствена
за всеки вектор J2n е в сила f () f ().
Вече е ясно, че |Sn| = , тъй като всяка самодвойнствена функция на n променливи се дефинира свободно точно върху един от всяка двойка противоположни вектори.
Теорема: Множеството S е затворено множество от булеви функции.
Доказателство: Прилагаме критерия за затвореност, като използваме лемата за двойнственост на сложна функция.
Въвеждаме нова релация в J2n:
ако = a1a2…an и = b1b2…bn, то a1 b1, …, an bn. Релацията очевидно е частична наредба, която не е линейна.
Въвеждаме релация в J2n:
ако = a1a2…an и = b1b2…bn, съществува
i { 1, 2, …, n }, такова че ai < bi (ai = 0, bi = 1) и aj = bj при j i.
Лема: Ако и , то съществуват 1, …, k J2n,
такива че 1 … k (допускаме k = 0).
Казваме, че функцията f (x1, …, xn) F2 е монотонна, ако за всеки
, J2n, такива че имаме f () f ().
С M означаваме множеството от всички монотонни функции,
с Mn тези от тях, които са на n променливи.
Функциите x, xy, x y, , са монотонни, докато не е монотонна, тъй като 0 1, но 1 = > = 0.
Така M F2.
Задачата за намиране на явна формула за броя на монотонните функции на n променливи не е решена.
Лема: Нека f M. Тогава съществуват , J2n, такива че
и f () > f ().
Доказателство: Тъй като f M, то съществуват , ,
такива че f () > f (), т.е. f () = 1, f () = 0. От горната лема съществуват 1, …, k J2n, такива че 1 … k .
Да означим 0 = , k+1 = . Да допуснем, че за всяко
i { 0, 1, …, k } имаме f (i) f (i+1).
Тогава 1 = f (0) f (1) … f (k) f (k+1) = 0 – противоречие.
Така съществува индекс i, такъв че f (i) > f (i+1) и i i+1.
Сподели с приятели: |