15.4. Конструктивный подход к доказательству функциональной

полноты системы булевых функций

Подход базируется на следующей теореме булевой алгебры:

Теорема. Пусть система булевых функций {f₁, …, f_m} является функционально полной и любая из функций f₁, …, f_m может быть выражена с помощью суперпозиции через функции g₁, …, g_k. Тогда система булевых функций {g₁, …, g_k} также является функционально полной.

При этом в качестве исходной системы {f₁, …, f_m} обычно используется система S₁ (булев базис).

Пример: доказательство функциональной полноты системы S₅=- универсальный базис.

Л И Т Е Р А Т У Р А

О с н о в н а я

1. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз, 1962.– 476 с.

2. Миллер Р. Теория переключательных схем. Т.1. Комбинационные схемы: Пер. с англ. – М. Мир, 1970. – 416 с.

3. Савельев А.Я. Прикладная теория цифровых автоматов. – М.: Высш. шк., 1987. – 272 с.

4. Поспелов Д.А. Логические методы анализа и синтеза схем. – М.: “Энергия”, 1974. – 368 с.

5. Скорубский В.И. Арифметические и логические основы цифровых машин: учебн. пособие. – Л.: Лен. ин-т точной механики и оптики, 1980. – 60 с.

Д о п о л н и т е л ь н а я

1. Проектирование цифровых вычислительных машин / С.А. Майоров, Г.И.Новиков, О.Ф. Немолочнов и др.: Под ред. С.А. Майорова. – М.: Высш.шк., 1972. – 344с.

2. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. – Минск: Вышэйшая школа, 980. – 386с.

3. Майоров С.А., Новиков Г.И. Структура цифровых вычислительных машин. – Л.: Машиностроение, 1970. – 375с.

4. Баранов С.И. Синтез микропрограммных аппаратов. – Л.: “Энергия”, 1974. – 216с.

5. Новиков Ф.А. Дискретная математика для программистов: учебник для вузов. 2-е изд.- Питер, 2006.- 368 с.

7