Реферат: Бульові функції

3. Замкнені та повні набори функцій. Критерій Поста повноти набору функцій

У підрозділі 7.1 ми побачили, що будь-яку бульову функцію можна задати як суперпозицію функцій з набору {Ù, Ú, Ø} або з набору {Å, Ù, 1}.

Означення . Множина всіх функцій, що є суперпозиціями функцій деякого набору F, і лише їх, називається замиканням цього набору й позначається [F].

Таким чином, якщо P₂ позначає множину всіх бульових функцій, то

[{Ù, Ú, Ø}] = [{Å, Ù, 1}] = P₂ .

Означення . Множина функцій F називається функціонально повною , якщо [F]=P₂ .

Отже, множини {Ù, Ú, Ø} і {Å, Ù, 1} є функціонально повними.

Природним є питання про те, які властивості повинні мати функціонально повні множини функцій.

Видатний математик Еміль Пост сформулював і обгрунтував критерій повноти множини функцій у загальному випадку алгебри функцій з операцією суперпозиції. У цьому критерії, тобто необхідній і достатній умові, використовується поняття передповного класу. Розглянемо його.

Нехай F позначає множину всіх можливих функцій деякої алгебри функцій A з операцією суперпозиції.

Означення . Множина функцій S називається передповним класом алгебри A, якщо [S]¹F і за будь-якої функції f з множини F\S набір SÈ{f} є повним: [SÈ{f}]=F.

Критерій Поста . Нехай S₁ , S₂ , … – усі передповні класи алгебри функцій F. Множина функцій M є повною тоді й тільки тоді, коли для кожного передповного класу S_i множина M містить fÎM\S_i .

Приймемо це твердження без доведення.

Пост також дослідив передповні класи алгебри бульових функцій. Їх виявилося лише 5. Це множини всіх функцій:

що зберігають сталу 0,

що зберігають сталу 1,

самодвоїстих,

лінійних,

монотонних.

Означимо вказані функції.

Означення . Функція f⁽ⁿ⁾ зберігає сталу 0 , якщо на нульовому наборі має значення 0: f⁽ⁿ⁾ (0, 0, …, 0)=0.

Означення . Функція f⁽ⁿ⁾ зберігає сталу 1 , якщо на одиничному наборі має значення 1: f⁽ⁿ⁾ (1, 1, …, 1)=1.

Наприклад, тотожна функція f(x)=x зберігає сталі 0 і 1, функція f(x)=Øx не зберігає жодної.

****Двоїста до …

Означення . Функція f⁽ⁿ⁾ є самодвоїстою , якщо для всіх пар протилежних наборів вона приймає на них протилежні значення:

f⁽ⁿ⁾ (a₁ , a₂ , …, a_n ) = ****f⁽ⁿ⁾ (a₁ , a₂ , …, a_n ) зберігає сталу 0, якщо на нульовому наборі має значення 0: f⁽ⁿ⁾ (0, 0, …, 0)=0.

Означення . Функція f⁽ⁿ⁾ зберігає сталу 1, якщо на одиничному наборі має значення 1: f⁽ⁿ⁾ (1, 1, …, 1)=1.

Неважко переконатися, що множини означених функцій, позначені відповідно T₀ , T₁ , S, L, M, є замкненими класами.

Список рекомендованої літератури