Бульові функції

З наведених логічних елементів будуються складніші схеми, які в загальному випадку мають n входів і m виходів і реалізують набір з m функцій від n аргументів:

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

Приклади.

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

xy = xyxy.

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

xy = xyxy.

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

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

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

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

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

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

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

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

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

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

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

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

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

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