Бульові функції, Детальна інформація

a2 b2

.

.

.

an bm

Тут bj=fj(a1, a2, …, an), j=1, 2, …, m..

Приклади.

1. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує функцію (. Виразимо її за допомогою функцій набору {(, (, (}:

x(y = x((y((x(y.

x

y

Звідси відповідна схема має вигляд:

2. Побудуємо схему з І- та (-елементів, яка реалізує функцію (. Виразимо її за допомогою функцій набору {(, (, 1}:

x(y = x(y(x(y.

Звідси відповідна схема має вигляд:

x

y

3. Побудуємо схему з І-, АБО- та НЕ-елементів, яка реалізує так званий "однорозрядний напівсуматор"[****] з двома симетричними входами x, y і двома виходами: s = x(y, d = x(y. З цих формул видно, що схема має реалізувати додавання двох однорозрядних чисел із переносом. Виразимо s за допомогою функцій набору {(, (, (}: s = x((y((x(y. Тоді схема має вигляд:

x s

d

y

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

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

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

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

({(, (, (}( = [{(, (, 1}] = P2.

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

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

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

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