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


Теорема: Множеството M е затворено множество от булеви функции



страница2/29
Дата11.01.2018
Размер5.91 Mb.
#44141
1   2   3   4   5   6   7   8   9   ...   29

Теорема: Множеството M е затворено множество от булеви функции.


Доказателство: Прилагаме критерия за затвореност.
Всяка функция f (x1, …, xn)  F с полином на Жегалкин

от вида a0  a1x1  … anxn, наричаме линейна функция.

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

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

Например x, = x  L, но xy  L, x  y = x  y  xy  L.

Така LF2.

Очевидно |Ln| = 2n+1, тъй като в общия вид линейните полиноми на Жегалкин имат n+1 свободни коефициенти.
Теорема: Множеството L е затворено множество от булеви функции.

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


Теорема (Пост-Яблонски): Нека F  F2. Тогава F е пълно  F не е подмножество на нито едно от множествата T0, T1, S, M, L.

Доказателство:

Нека F е пълно и K  { T0, T1, S, M, L }. Да допуснем, че F  K.

Тогава [F]  [K]. От пълнотата на F имаме [F] = F2  [K] = F2.

От друга страна за множеството K вече показахме, че [K] = K  F2 – противоречие. Tака F не е подмножество на нито едно от

множествата T0, T1, S, M, L.

Нека F не е подмножество на нито едно от множествата

T0, T1, S, M, L. Тогава съществуват функции f0, f1, fs, fm, fl  F,

не непременно различни, такива че f0T0, f1T1, fsS,

fmM, flL. Да означим F = { f0, f1, fs, fm, fl}, F  F.

Ще покажем, че xy,  [F].

Функцията g0 (x) = f0 (x, x, …, x)  [F], тъй като във функцията

f0 сме заместили променливи. Имаме g0 (0) = f0 (0, 0, …, 0) = 1, тъй като f0T0. Функцията g1 (x) = f1 (x, x, …, x)  [F], тъй като във функцията f1 сме заместили променливи.

Имаме g1 (1) = f1 (1, 1, …, 1) = 0, тъй като f1T1.

За g0 (1) и g1 (0) имаме четири възможности:



  1. g0 (1) = 0 и g1 (0) = 0 – тогава g0 (x) = , g1 (x) =

и така  [F] и g0 (g1 (x)) =  [F];

  1. g0 (1) = 0 и g1 (0) = 1 – тогава g0 (x) = и g1 (x) =

и така  [F];

  1. g0 (1) = 1 и g1 (0) = 0 – тогава g0 (x) = и g1 (x) =

и така  [F],  [F];

  1. g0 (1) = 1 и g1 (0) = 1 – тогава g0 (x) = и g1 (x) =

и така g1 (g0 (x)) =  [F] и  [F].

Така в три от случаите получихме двете константи.

Да разгледаме втория случай, при който получихме само отрицанието.

Функцията fsS  съществува  = a1a2…anJ2n, така че

fs () = fs (). Функцията gs (x) = fs ()  [F]:

ако ai = 1, то = x и заместваме само променлива,

ако ai = 0, то = , но в този случай  [F] и заместваме променлива с формула над F, така че отново получаваме

формула над F.

Имаме gs (0) = fs () = fs () = fs (),

gs (1) = fs () = fs () = fs ().

Tака gs (0) = gs (1).

Aко gs (0) = gs (1) = 0, то gs (x) =  [F] и g1 (gs (x)) =  [F].

Aко gs (0) = gs (1) = 1, то gs (x) =  [F] и g1 (gs (x)) =  [F].

Така с формули над { f0, f1, fs } построихме константите и във всички случаи.

Функцията fmM и тогава от лемата по-горе съществуват вектори ,   J2n, такива че    и fm () = 1, fm () = 0.

Нека  = a1…ai-10ai+1…an,  = a1…ai-11ai+1…an.

Функцията gm (x) = fm (a1, …, ai-1, x, ai+1, …, an)  [F], тъй като заместваме променливи с вече получените формули , над F.

Имаме gm (0) = fm (a1, …, ai-1, 0, ai+1, …, an) = fm () = 1,

gm (1) = fm (a1, …, ai-1, 1, ai+1, …, an) = fm () = 0.

Така gm (x) =  [F].

Нека xyz1z2…zk (k  0) е най-късият нелинеен член в полинома на Жегалкин за функцията fl. Такъв има, тъй като flL. Във формулата за fl заместваме променливите z1, …, zk с вече получената формула над F и всички останали променливи без

x и y с вече получената формула над F. Така получаваме функция gl (x, y)  [F]. Полиномът на Жегалкин за gl (x, y) има вида gl (x, y) = xy  ax  by  c, тъй като всички останали нелинейни членове съдържат поне една променлива, различна от

x, y, z1, …, zk и се анулират. Да направим следната смяна на променливите: x = u  b, y = v  a. Тя е позволена:

ако b = 0, то u  b = u и заместваме само променлива,

ако b = 1, то u  b =  [F] и заместваме променлива с формула над F, така че отново получаваме формула над F.

Tака получаваме функция

hl (u, v) = (u  b)(v  a)  a(u  b)  b(v  a)  c = uv  d,

където d = ab  c.

Ако d = 0, то hl (u, v) = uv,

ако d = 1, то hl (u, v) = и gm (hl (u, v)) = uv.

Получихме, че конюнкцията е формула над F.

Така { xy, }  [F]  [F] и { xy, } е пълно множество и от една теорема за пълни множества  F е пълно множество.


Казваме, че функцията f  F2 е Шеферова, ако [ { f } ] = F2.

Съгласно теоремата на Пост-Яблонски f е Шеферова 

f  T0, f  T1, f  S, f  M, f  L. Ще покажем едно достатъчно условие за Шеферовост.

Теорема: Нека f  F2 и f  T0, f  T1, f  S. Тогава f е Шеферова.

Доказателство:

Ще покажем, че f  M и f  L и тогава от теоремата на Пост-Яблонски функцията f e Шеферова.

Тъй като f  T0, то f (0, 0, …, 0) = 1.

Също от f  T1  f (1, 1, …, 1) = 0.

Но (0, 0, …0) (1, 1, …, 1) и f (0, 0, …, 0) > f (1, 1, …, 1),

така че f  M.

Да допуснем, че f  L, т.е. f = a0  … .

От f  T0  f (0, …, 0) = 1, т.е. a0 = 1. От f  T1  f (1, 1, …, 1) = 0, т.е. = 0  k е нечетно. Сега

f * = 1  (  1)  … (  1)  1 =  … =

= 1   … = f  f  S – противоречие. Tака f  L.
2. Крайни автомати. Регулярни изрази. Теорема на Клини.
Краен детерминиран автомат наричаме петорката

A = < Q, X, q0, , F >, където

Q е крайно множество от вътрешни състояния,

X е крайна входна азбука,

q0Q е начално състояние,

 : Q x XQ е частична функция на преходите,

FQ е множеството от заключителни състояния.
Представяме крайните детерминирани автомати с краен ориентиран мултиграф с върхове елементите от Q. В графа има ребро от qi до qj, надписано с x  X, ако (qi, x) = qj. Обикновено началното състояние е посочено със стрелка, а заключителните състояния се изобразяват с двойни кръгчета.
Дефинираме : Q x X*Qразширена функция на преходите по следния начин: (q, ) = q за всяко q  Q,

 (q, x) = ( (q, ), x), за всеки x  X, q  Q и   X*, за които

 ( (q, ), x) е дефинирана, недефинирана, ако ( (q, ), x) не е дефинирана.
Казваме, че автоматът A = < Q, X, q0, , F > разпознава думата

  X*, ако (q0, )  F. Езикът LA = {  |   X*, (q0, )  F } наричаме език, разпознаван от автомата А.


Ако функцията на преходите : Q x XQ не е тотална, то можем да разширим автомата A до A следния начин:

A = < Q  q*, X, q0, *, F >, където q*  Q,

* (q, x) = (q, x), ако (q, x) е дефинирана и

* (q, x) = q*, ако (q, x) не е дефинирана.

Сега, ако A разпознава думата , то очевидно A разпознава . Обратното също е вярно, тъй като q* F= . И така без да изменяме езика на автомата можем, ако е необходимо, да додефинираме функцията на преходите до тотална функция.


Теорема: За всеки краен детерминиран автомат

A = < Q, X, q0, , F > съществува автоматна граматика Г, такава че LГ = LA.

Доказателство: Построяваме граматиката Г = < Q, X, q0, P >, където P = { qi xqj | ако (qi, x) = qj }  { qi x, ако (qi, x)  F }.

Изчистваме Г от аксиома в дясна част на правило и ако   LA

(q0F), добавяме правилото q0 . Лесно се вижда, че получената граматика поражда езика LA.


Краен недетерминиран автомат наричаме петорката

A = < Q, X, q0, , F >, където

Q е крайно множество от вътрешни състояния,

X е крайна входна азбука,

q0Q е начално състояние,

 : Q x X2Q е функция на преходите,

FQ е множеството от заключителни състояния.
Дефинираме : Q x X*2Qразширена функция на преходите по следния начин: (q, ) = { q } за всяко q  Q,

 (q, x) =  (q, x) за всяко x  X, (q, x) =,

където (q, ) = { ,, …, }.
Kазваме, че автоматът A разпознава думата   X*, ако

 (q0, )  F  . Eзикът LA = {  |   X*, (q0, )  F   } наричаме език, разпознаван от автомата А.


Теорема: За всяка автоматна граматика Г = < N, T, S, P > съществува краен недетерминиран автомат А, такъв че LA = LГ.

Доказателство: Без ограничение на общността можем да считаме, че в Г няма преименуващи правила. Нека E  NT. Конструираме автомата A по следния начин:



A = < N  { E }, T, S, , F >, където

 (A, x) = { B | AxB  P}  { E}, ако Ax  P и



F = { E }, ако   LГ и F = { S, E }, ако   LГ.

Тривиално се проверява, че LA = LГ.


Теорема: За всеки краен недетерминиран автомат

A = < Q, X, q0, , F > съществува краен детерминиран автомат A, такъв че = .

Доказателство: Построяваме крайният детерминиран автомат A по следния начин: A = < Q, X, { q0}, , F >, където



Q2Q е множеството от всички M  Q, такива че съществува дума   X*, такава че (q0, ) = M. Функцията  : Q x XQ е дефинирана по следния начин:  ({ ,, …, }, x) = и F = { M|M  Q, M  F   }.

С индукция по дължината на  ще покажем, че

 (q0, ) =  ({ q0 }, ).

База: Нека  = , т.е. d () = 0. Имаме (q0, ) = { q0 } и

 ({ q0}, ) = { q0}  (q0, ) =  ({ q0 }, ).

Предположение: Нека твърдението е изпълнено за думата .

Стъпка: Ще покажем, че (q0, x) =  ({ q0}, x).

Нека  ({ q0}, ) = { ,, …, }. Тогава по дефиницията на 

имаме  ({ q0}, x) =  ({ ,, …, }, x) = .

От индукционното предположение имаме

 (q0, ) =  ({ q0 }, ) = { ,, …, } 

 (q0, x) = =  ({ q0}, x).

Имаме (q0, )  F     ({ q0}, )  F     ({ q0}, )  F.

И така = .


Като комбинираме трите теореми получаваме, че автоматните езици (тези които се разпознават от автоматни граматики), са точно тези езици, които се разпознават от крайни детерминирани (недетерминирани) автомати.
Оттук нататък считаме, че всички автомати са навсякъде дефинирани.
Крайните детерминирани автомати A и A наричаме еквивалентни, ако = .

Крайният детерминиран автомат A0, който разпознава автоматния език L се нарича минимален за този език L, ако за всеки автомат A, който е еквивалентен на A0 имаме |Q0|  |Q|, където Q0 и Q са множествата от състоянията съостветно на A0 и на A.


Нека X е произволна азбука. Релацията R  X* x X* наричаме



Сподели с приятели:
1   2   3   4   5   6   7   8   9   ...   29




©obuch.info 2024
отнасят до администрацията

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