1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J



страница1/29
Дата11.01.2018
Размер5.91 Mb.
  1   2   3   4   5   6   7   8   9   ...   29
1. Булеви функции. Теорема на Пост-Яблонски за пълнота.
Нека J2 = { 0, 1}. Всяка функция f : J2nJ2, n  , n ≥ 1 наричаме двоична (булева) функция.

Всяка функция f : J2nJ2 можем да разглеждаме като функция на 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 : J2nJ2 не зависи съществено от променливата 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:

База: За всяка функция fiF на 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, …, gnF2. 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.
Дефинираме двоична функция 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 е такова, че


  1. f (x) = x  F;

  2. за всяка функция 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.

Така T0F2 и T1F2.

Очевидно, |T0n| = = |T1n|, тъй като всяка функция запазваща коя да е от константите се дефинира по произволен начин върху всички вектори освен един.
Теорема: Множествата T0 и T1 са затворени множества от булеви функции.

Доказателство: Директно от критерия за затвореност.


Нека f (x1, …, xn)  F2. Функцията f *(x1, …, xn), определена по следния начин: за всеки вектор a1…anJ2n,

f *(a1, …, an) = наричаме двойнствена на f.


Векторите  = a1a2…an J2n и = J2n наричаме противоположни вектори.
Лема: В стандартната наредба на J2n, противоположните вектори са симетрично разположени относно средата на таблицата.
От тази лема получаваме следният алгоритъм за намиране на двойнствена функция, зададена със своя вектор-стълб:

  1. инвертираме всяка стойност в стълба;

  2. завъртаме симетрично стълба около средата.

Като непосредствено следствие от алгоритъма получаваме:

за всяка функция 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 не е самодвойнствена.

Така SF2.


Лема: Функцията 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, …, kJ2n,

такива че   1  … k   (допускаме k = 0).


Казваме, че функцията f (x1, …, xn)  F2 е монотонна, ако за всеки

,   J2n, такива че   имаме f ()  f ().

С M означаваме множеството от всички монотонни функции,

с Mn тези от тях, които са на n променливи.

Функциите x, xy, x  y, , са монотонни, докато не е монотонна, тъй като 0 1, но 1 = > = 0.

Така MF2.


Задачата за намиране на явна формула за броя на монотонните функции на n променливи не е решена.
Лема: Нека f  M. Тогава съществуват ,   J2n, такива че

   и f () > f ().

Доказателство: Тъй като f  M, то съществуват  ,   ,

такива че f () > f (), т.е. f () = 1, f () = 0. От горната лема съществуват 1, …, kJ2n, такива че   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.



  1   2   3   4   5   6   7   8   9   ...   29


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница