Методы аппаратной и программной реализации алгоритмов логического управления технологическими процессами тема диссертации и автореферата по ВАК РФ 05.13.05, доктор технических наук Шалыто, Анатолий Абрамович

• Шалыто, Анатолий Абрамович
• доктор технических наук
• 1999

Оглавление диссертации доктор технических наук Шалыто, Анатолий Абрамович

Введение.

Глава 1. Булевы формулы и булевы функции. Классификация, табулирование, свойства.

1.1. Классификация бесповторных булевых формул в базисе

И, ИЛИ, НЕ.

1.2. Деревья из двухвходовых элементов.

1.2.1. Подсчет числа неизоморфных деревьев.

1.2.2. Покрывающие деревья.

1.2.3. Модули с простой структурой, универсальные в классе формул.

1.3. PN-классификация бесповторных формул в базисе И, ИЛИ, НЕРАВНОЗНАЧНОСТЬ, НЕ.

1.4. Свойства бесповторных формул в базисе И, ИЛИ, НЕ.

1. 4.1. Ранг бесповторных функций.

1.4.2. Вычисление числа единиц по формуле.

1.4.3. Свойства бесповторных пороговых формул.

1.5. Отношения покрытия.

1. 6. Метод совместной реализации булевых функций.

1.7. Новые соотношения для преобразований булевых функций.

Выводы.

Введение диссертации (часть автореферата) на тему «Методы аппаратной и программной реализации алгоритмов логического управления технологическими процессами»

АКТУАЛЬНОСТЬ ПРОБЛЕМЫ. В диссертации рассматриваются методы аппаратной и программной реализации алгоритмов логического управления, которое основано на истинности и ложности входных и выходных переменных.

Основные теоретические исследования в этой области были начаты в мире с конца 30-х годов этого века. В течение многих лет признанным лидером в этом направлении в СССР был член-корреспондент АН СССР Михаил Александрович Гаврилов (1903-1979), работавший в Институте проблем управления (Институте автоматики и телемеханики) АН СССР (Москва), создавший школу по теории релейных устройств и конечных автоматов.

Автор начал заниматься исследованиями в области логического управления в научно-производственном объединении (НПО) "Аврора" (Ленинград) с середины жизни этого научного направления - с 1971 года, после окончания Ленинградского электротехнического института им. В.И.Ульянова (Ленина). Это было время расцвета теоретических исследований в этой области и широкого внедрения комплексных систем управления сложными промышленными и транспортными объектами. При этом возникало много теоретических и практических задач, в решении которых автор принимал участие. Это привело автора к активным, почти тридцатилетним исследованиям в указанной области, результатом которых является настоящая диссертация.

За эти годы элементная база систем логического управления быстро изменялась, пройдя путь от релейно-контактных элементов, микросхем малого и среднего уровней интеграции к программным логическим устройствам, а затем к большим и сверхбольшим интегральным схемам, частным случаем которых являются микропроцессоры и микроконтроллеры, которые используются в качестве вычислительного ядра в том числе и в промышленных (управляющих) компьютерах и программируемых логических контрол

- и лерах.

При этом в настоящее время в крупных и долго существующих организациях весьма часто возникает ситуация, когда в одной и той же организации одновременно ведутся проектирование, модернизация и модификация различных поколений систем логического управления, в каждой из которых превалирует тот или иной тип элементов и устройств из указанного выше спектра.

Каждый тип элементной базы порождает свои критерии и ограничения, что, в свою очередь, приводит к постановке научных задач, решение которых позволяет выполнить выдвигаемые практикой требования.

Эти требования связаны с различными характеристиками систем логического управления, например такими, как надежность, живучесть, диагностика. Однако все эти годы научные интересы автора были связаны с другими аспектами построения систем этого класса, которые характеризуются такими терминами, как "логическое проектирование" или "логический синтез", и были посвящены разработке формализованных методов аппаратной и программной реализации алгоритмов логического управления, которые являлись актуальными на протяжении многих лет и являются актуальными в настоящее время.

Так, например, задача синтеза комбинационных схем в базисе априори заданных произвольных элементов, решаемая в настоящей работе, являлась актуальной при использовании логических элементов различной физической природы и сложности и не потеряла своей актульности в настоящее время применительно к сверх/большим интегральным схемам программируемой логики, базисом которых являются функциональные преобразователи различной сложности.

Если при построении схем ставились задачи минимизации аппаратуры (внешних выводов у настраиваемых модулей и модулей в схемах) и ее унификации, предельным случаем которой является однородность, то при программной реализации оптимизировались объем памяти и быстродействие при одних методах и "понятность" и "безошибочность" программ при других методах, что связано с большой ответственностью объектов, управляемых системами рассматриваемого класса. Последнее свойство было и остается актуальным и при построении схем любого уровня интеграции.

При разработке предлагаемых методов везде, где это было возможно, автором были получены оценки сложности предстоящих реализаций. Отметим также, что если некоторые классы схем и программ изоморфны и поэтому могут строиться одинаковыми методами, то возможность работы с целыми числами и арифметическими операциями позволяет предложить методы программной реализации алгоритмов логического управления, которые не имеют аналогов в аппаратуре.

При этом для аппаратных реализаций автором предложены методы построения только комбинационных схем, а для программных реализаций рассматривались также и автоматы с памятью. Это связано с тем, что "синхронность" программных реализаций резко упрощает построение этого класса автоматов по сравнению с построением асинхронных схем с памятью, синтез которых в настоящее время является отдельным направлением в логическом проектировании.

Специфика комбинационных схем, рассматриваемых в настоящей работе, состоит в том, что так как они в системах логического управления технологическими процессами в большинстве случаев воздействуют на инерционные исполнительные механизмы, то для них может не решаться проблема риска и не обеспечиваться высокое быстродействие. Другая особенность этих схем состоит в том, что они обычно реализуют булевы формулы с малой повторностью переменных. Такие формулы характерны также и для пометок дуг графов переходов, описывающих поведение автоматов с памятью, применяемых в системах этого класса.

В логическом проектировании кроме задач, непосредственно возникающих из потребностей практики, имеется также уже ставшая традиционной область теоретических задач, связанных с исследованиями как класса всех булевых функций, так и его подклассов. Большой интерес представляют также исследования булевых формул, являющихся одной из реализаций булевых функций, первичным заданием которых являются таблицы истинности. При этом, по мнению автора, особую важность имеют простейшие из булевых формул - бесповторные (в определенном базисе), свойства которых, как показано в настоящей работе, связаны с такими фундаментальными понятиями математики (в основном дискретной), как например эйлеровы графы, клики в графах, числа Фибоначчи и число "е". Кроме того в работ? показано, что для булевых формул (в определенных базисах) некоторые характеристики имеют линейные от числа букв оценки сложности.

ЦЕЛЬЮ ДИССЕРТАЦИОННОЙ РАБОТЫ является разработка методов аппаратной и программной реализации алгоритмов логического управления технологическими процессами, обеспечивающих повышение качества схем и программ, построенных на их основе.

ОСНОВНЫЕ ЗАДАЧИ ДИССЕРТАЦИИ, определяемые целью диссертации, состоят в следующем.

1. Исследование свойств и количественных характеристик булевых формул (БФ) (в основном бесповторных), двухместные операции в которых подчиняются сочетательному закону.

2. Разработка метода синтеза одновыходных комбинационных схем в произвольных априори заданных элементных базисах по БФ и получение оценок сложности предстоящих реализаций.

3. Разработка метода синтеза одновыходных комбинационных схем в произвольных априори заданных элементных базисах по булевым функциям (БФУ), заданным таблицами истинности (ТИ).

4. Разработка метода построения многофункциональных логических модулей (МЛМ) из функциональных элементов (элементов с односторонней проводимостью) с минимизированным числом внешних выводов.

5. Разработка МЛМ из элементов с двусторонней проводимостью и методов реализации комбинационных схем на их основе с оценками сложности предстоящих реализаций.

6. Оценка функциональных возможностей программируемых логических матриц

ПЛМ) в классе БФ.

7. Разработка различных типов однородных структур для реализации БФ и методов реализации последних с оценками сложности предстоящих реализаций.

8. Разработка метода реализации БФ линейными бинарными графами с оценками сложности предстоящих реализаций.

9. Разработка методов реализации систем БФУ с помощью арифметических полиномов.

10. Разработка методов программной реализации автоматов с памятью.

11. Разработка технологии алгоритмизации и программирования задач логического управления.

МЕТОДЫ ИССЛЕДОВАНИЙ базируются на булевой алгебре, теории переключательных схем и конечных автоматов, комбинаторике, теории графов, теоретическом программировании и линейной алгебре.

НАУЧНАЯ НОВИЗНА РАБОТЫ состоит в полученных теоретических результатах, перечисленных в заключении.

ДОСТОВЕРНОСТЬ научных положений, выводов и практических рекомендаций подтверждается корректным обоснованием постановок задач, точной формулировкой критериев, математическим доказательством, а также результатами практического использования решений, предложенных в диссертации. Результаты, которые не доказаны, но базируются на предположениях автора, основанных на интуиции и большом числе примеров, сформулированы как гипотезы.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ состоит в том, что все полученные результаты могут быть использованы, а некоторые используются, на практике. Они позволяют для аппаратных реализаций сократить элементную сложность, а для программных - объем памяти и время вычислений. Однако, главное их значение состоит в повышении достоверности проектных решений принимаемых на их основе. Они делают эти решения понятными для Специалистов различных областей знаний и квалификации. Формализованное^ предлагаемых методов позволяет их автоматизировать, что для некоторых из них выполнено.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Результаты работы внедрены в части:

- многофункциональных логических модулей во ВНИИ "Альтаир" при создани: микросборки ЛГ83, выпускавшейся в трех модификациях (ЛГ183, ЛГ283, ЛГ383), и при создании отраслевого стандарта 0СТ5.8354-74 "Микросхемы гибридные сложные - микросборки "Пакет". Руководство по применению", а также в НПО "Аврора" при создании унифицированных логических плат для систем управления типа "Корунд";

- однородных модулей из элементов с двусторонней проводимостью в НПО "Аврора" при создании унифицированных кассет логики для систем управления типа "Молибден";

- SWITCH-технологии в НПО "Аврора" при создании системы управления дизель-генератором ДГР-2А 500*500 для трех судов проекта 15640 на базе аппаратуры "Selma-2" фирмы "ABB Stromberg" (Финляндия); системы управления дизель-генератором того же типа для судна проекта 15967 на базе аппаратуры "Selma-2" фирмы "ABB Stromberg" (Финляндия); системы управления дизель-генератором того же типа для судна проекта 15760 на базе аппаратуры фирмы "Norcontrol" (Норвегия); комплексной системы управления техническими средствами пяти судов проекта 17310 на программируемых логических контроллерах (ПЛК) "Autolog" фирмы "FF-Automation 0Y" (Финляндия); комплекта "Авролог" для управления техническими средствами судна проекта "ПС 500" на ПЛК "Autolog"; АСУ ТП центральной подготовительной станции первичной обработки нефти "Авролог-НП1" на ПЛК "Autolog" (Северо-Ореховское месторождение); АСУ ТП дожимной насосной станции "Авролог-НП2" на ПЛК "Autolog" (Северо-Покурское месторождение системы управления турбокомпрессорным агрегатом. "Ларина" на основе микроэвм КР 1816 ВЕ51, используемой при производстве полиэтилена в ПО

Полимир" (Новополоцк); транслятора "Ядро языка СИ - язык инструкций ALPro" для ПЛК "Autolog".

Результаты работы использовались в учебном процессе в Институте повышения квалификации руководящих работников и специалистов судостроительной промышленности (Ленинград); Ленинградском элекротехническом институте им. В. И. Ульянова (Ленина); Ленинградском политехническом институте им. М.И. Калинина; Санкт-Петербургском институте точной механику и оптики (техническом университете).

АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертации докладывались на следующих основных конференциях, совещаниях и семинарах: III (Таганрог, 1972) и IV (Киев, 1975) Всесоюзных конференциях "Однородные вычислительные системы и среды"; II Всесоюзной межвузовской конференции "Алгоритмические методы проектирования цифровых систем" (Л., 1972); Советско-Болгарском семинаре "Теория автоматов и ее приложения" ( М., 1973); V (Севастополь, 1973), VI (Л., 1982) и VII (Л., 1989) Всесоюзных научно-технических конференциях "Проблемы создания систем управления судовыми техническими средствами"; симпозиуме ИФАК "Дискретные системы" (Рига, 1974); VI (М., 1974), IX (Ереван, 1983), X (Алма-Ата) и XI (Ташкент, 1989) Всесоюзных совещаниях по проблемам управления; III Всесоюзном совещании "Логический синтез в дискретных однородных средах" (Рязань, 1974); постоянно действующем семинаре "Конечные автоматы" Научного Совета по автоматизации научных исследований и проблемам кибернетики при Президиуме АН Латвийской ССР (Рига, 1975); XVI (Челябинск, 1976), XXI (Таллин, 1981), XXXII (М., Подлипки, 1993) и XXXV (М., Челюскинская, 1996) Всесоюзных школах-семинарах по теории автоматов им. М. А.Гаврилова; постоянно действующем семинаре "Теория автоматов" при НТО приборпром им. ак. С.И.Вавилова (Л., 1978, 1986); Всесоюзном семинаре "Однородные вычислительные структуры и малые ЭВМ" (М., Звенигород, 1979); III (Ташкент, 1984) и IV (Новосибирск, 1989)

Всесоюзных совещаниях "Методы и программы решения оптимизационных зада на графах и сетях"; школе-семинаре "Автоматизация логического проектирования" (Севастополь, 1982); VIII Всесоюзном симпозиуме "Логическое управление" (Куйбышев, 1985); научно-координационном совещании "Применение микропроцессорной техники в системах управления" секции "Техническая кибернетика" Минвуза СССР (Суздаль, 1986); Всесоюзном семинаре "Логические методы построения однородных и систолических структур" (М. Звенигород, 1988); постоянно действующем семинаре ВЦ СО АН СССР "Математическое и архитектурное обеспечение параллельных вычислений" (Новосибирск, 1989); постоянно действующем семинаре "Теория графов" Института математики СО АН СССР (Новосибирск, 1989); 10th IEEE International Symposium on Intelligent Control. ISIC Workshop "Architectures for Semiotic Modeling and Situation Analysis in Large Complex Systems" (Monterey, California, 1995); International Conferens on Informatics and Control (ICI&C97) (St. Petersburg, 1997); научно-техническом сове те НПО "Аврора" (СПб., 1998).

По теме диссертации опубликовано 114 основных работ, в том числе 2 монографии, 14 книжных изданий, 27 статей и 53 авторских свидетельства на изобретения.

Кроме того в Санкт-Петербургской издательской фирме "Наука" Российской Академии наук в работе находится монография автора "Логическое управление. Методы аппаратной и программной реализации алгоритмов" объемом 4.1,5 печатных листов, срок выпуска которой по договору - 1999 г. Монография кроме И глав, включенных практически полностью в диссертацию, содержит еще 10 глав, в которых приводятся результаты исследований автора, также относящиеся к теме диссертации, но не включенных в нее в виду большого объема. Эти главы имеют следующие наименования: реализация булевых функций схемами из мажоритарных элементов; реализация булевых функций схемами из мультиплексоров; использование мультиплексорного метода для реализации схем в различных элементных базисах; построение многофункциональных логических модулей; модули, универсальные в классе симметрических функций; модули универсальные в классе самодвойственных функций и в "близких" к ним классах; модули, универсальные в классе всех булевых функций; методы построения бинарных графов для автоматов без памяти; логические устройства для последовательного вычисления булевых функций; нетрадиционные методы вычисления булевых функций.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ. Диссертация состоит из оглавления, введения, одиннадцати глав и заключения. Список работ, составленный по главам, содержит 356 наименований. Объем работы - 392 страниц. Она содержит 144 рисунка, 22 таблицы и 141 пример.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Шалыто, Анатолий Абрамович

ВЫВОДЫ

1. Определено количество типов бесповторных булевых формул (ББФ) в базисе И, ИЛИ, НЕ в различных классификациях.

2. Выполнено табулирование представителей PN-типов этих формул при h <= 8.

3. Определено рекуррентное соотношение для подсчета неизоморфных деревьев из двухвходовых элементов.

4. Рассмотрены покрывающие деревья и на их основе предложены модули, универсальные в указанном классе формул с простой структурой.

5. Рассмотрена PN-классификация ББФ в базисе И, ИЛИ, НЕРАВНОЗНАЧНОСТЬ, НЕ и выполнено их табулирование при h <= 4.

6. Установлено, что ББФ в базисе И, ИЛИ, НЕ, существенно зависящие от всех переменных, имеют нечетный ранг.

7. Предложены методы подсчета числа единиц при формульном задании булевой функции.

8. Определены свойства бесповторных пороговых формул и установлена их связь с числами Фибоначчи.

9. Определены отношения покрытия, при выполнении которых булева формул в форме, аналогичной разложению Шеннона, не будет содержать переменных "разложения'1 с инверсиями.

10.Предложен метод совместной реализации булевых функций, обладающий меньшей трудоемкостью по сравнению с "гарвардским" методом.

11. Получены новые соотношения для преобразования булевых функций и на примерах показана целесообразность их применения при решении ряда задач логического проектирования.

Список литературы диссертационного исследования доктор технических наук Шалыто, Анатолий Абрамович, 1999 год

1. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979.

2. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.

3. Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Настраиваемые модули для управляющих логических устройств. Л.: Энергоиздат, 1981.

4. Лазарев В. Г., Наумчук-0. Ф., Саввин Г. Г., Сагалович Ю.Л. 0 переписи типовых релейно-контактных схем автоматической телефонии //Проблемы передачи информации. 1963. N8.

5. Шеннон К.Э. Работы по теории информации и кибернетике. М.: Изд-во иностр. лит., 1963.

6. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. М.: Мир, 1978.

7. Артюхов В.Л. Логические методы синтеза дискретных систем. Л.: Ин-т повышения квалификации руководящих работников и специалистов судостроительной промышленности (ИПК СП), 1974.

8. Риордан Дж. Введение в комбинаторный анализ. М.: Изд-во иностр. лит., 1963.

9. Артюхов В.Л., Розенблюм Л.Я., Шалыто А.А. Логические возможности некоторых типов каскадных структур //Сети связи и дискретные- 44 устройства управления. М.: Наука, 1976.

10. Ю.Артюхов В. Л, Копейкин Г. А., Шалыто А. А. О классификации бесповторных булевых функций //Теория автоматов и ее приложения. Материалы Советско-Болгарского семинара. М.: Институт проблем передачи информации, 1973.

11. И.Попов Ю.А., Воронин А.Т., Сладков А.Б. Вопросы проектирования схем с высоким уровнем интеграции на основе КНС технологии //Дискретные системы. Т.1. Симпозиум IFАС. Рига : Зинатне, 1974.

12. Артюхов В.Л., Копейкин Г. А., Шалыто А. А. Вопросы выбора и применения многофункциональных логических модулей //Дискретные системы.

13. Т. 1. Симпозиум IF АС. Рига: Зинатне, 1974.

14. Levy S.Y., Winder R., Mott Т.Н. A note on tributary switching networks //IEEE Trans, on Computers. 1964. N2.

15. Воробьев H.H. Числа Фибоначчи. M.: Наука, 1978.

16. Чистов В.П., Битюцкий В.П. Функциональная полнота в ленточных однородных структурах //Известия АН СССР. Техническая кибернетика.1971. N3.

17. Пупырев Е.И. Использование аксиомы теории вероятностей в задачах анализа булевых функций //Автоматика и телемеханика. 1976. N7.

18. Шалыто А. А. Реализация алгоритмов судовых управляющих логических систем при использовании микропроцессорной техники. Л.: ИПК СП, 1988.

19. Fridman A.D. ,Menon P.R. Theory & design of switching circuits, t Computer Science Press., Inc., 1975.

20. Кондратьев В. H., Шалыто А. А. Реализация булевых функций одним линейным арифметическим полиномом с маскированием //Автоматика и телемеханика. 1996. N1.

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

22. Шалыто А. А. Многофункциональный логический модуль. А.с. СССР N1283744 //Бал. изобр. 1987. N2.

23. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.

24. Артюхов В.Л., Шалыто А.А. Судовые управляющие логические системы. ИПК СП. Л.: 1983.

25. Артюхов В.Л., Шалыто А. А. Реализация булевых формул однородными мультиплексорными и мажоритарными каскадами //Известия Академии наук. Теория и системы управления. 1996. N5.

26. Артюхов В.Л., Шалыто А.А. Многофункциональный логический модуль. А. с. СССР N1149244 //Бюл. изобр. 1985. N13.

27. Мищенко В.А., Козюминский В.Д., Семашко А.Н. Многофункциональные автоматы и элементная база цифровых ЭВМ. М.: Радио и связь, 1981.

28. Шалыто А. А. Программная реализация алгоритмов логического управления судовыми системами. Л.: ИПК СП, 1989.

29. Шалыто А.А. Многофункциональный логический модуль. А. с. СССР ► N1290290 //Бюл. изобр. 1987. N6.

30. Шалыто А. А. Комбинационный двоичный сумматор вычитатель . А. с. СССР N1264166 //Бюл. изобр. 1986. N38.

31. Reed I.S. Class of multiple error correcting codes and decoding scheme //IRE Trans. Inform. Theory. 1954. IT-4.

32. ГЛАВА 2. ФОРМУЛЬНЫЙ МЕТОД СИНТЕЗА КОМБИНАЦИОННЫХ СХЕМ ИЗ ПРОИЗВОЛЬНЫХ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ

33. Одной из важнейших задач в области логического синтеза является задача построения комбинационных схем, реализующих булевы функции, из произвольных априори известных логических элементов.

34. Эта задача является достаточно сложной^ и поэтому рассмотрим вопрос о реализации одной булевой функции.

35. Возможны два подхода к построению комбинационных схем: от выхода к входам и от входов к выходу.

36. Рассматриваются два типа универсальных модулей. Модули первого типа названы настраиваемыми, а второго виртуальными.

37. СИНТЕЗ СХЕМ ИЗ МОДУЛЕЙ, УНИВЕРСАЛЬНЫХ В КЛАССЕ ФОРМУЛ 2.1.1. РЕАЛИЗАЦИЯ БУЛЕВЫХ ФОРМУЛ СХЕМАМИ ИЗ ПОЛОЖИТЕЛЬНО

38. В 91 показано, что эта стратегия обеспечивает выполнение следующего соотношения, определяющего число модулей в схеме:1. T h Т 1 г 201 1)гeL(h'q) <S .-q- . (2-П

39. Нижняя оценка числа шагов совпадает с нижней оценкой в соотношении (2.1), а верхняя оценка числа шагов равна верхней оценке в соотношении (2.1), умноженной на константу .q/2. Обратим внимание, что при q = 21.h, 2) = h 1.

40. П р и м е р 2.1. Реализовать на 3-универсальных модулях формулуf С С!х х v х !х )х v х х )(х v х ) v х . 12 1234567 8

41. Представим заданную БФ в виде полинома ((2+2)1 + 2)(1 +1) + 1.

42. Процедура реализации состоит в следующем.

43. Формула не содержит подформул из трех букв.

44. Выделяем подформулу 2. Остаток ((1 +2) + 2)(1 +1) +1.

45. Выделяем подформулу 1+2. Остаток (2 + 2)(1 + 1) + 1.

46. Остаточная формула не содержит подформул из трех букв.

47. Выделяем подформулу 2. Остаток (1 + 2)(1 +1) +1.

48. Выделяем подформулу 1+2. Остаток 1(1 + 1) + 1.

49. Выделяем подформулу 1(1 +1). Остаток -1+1.

50. Остаточная формула содержит менее трех букв.

51. Выделяем подформулу 1 +1. Остаток 1.

52. П р и м е р 2.2. Реализовать формулу, рассмотренную в предыдущем примере, на 4-универсальных модулях.х х х ! х х хх хх х1212 3 456781. Рис. 2.1

53. Заданная БФ реализуется в данном случае следующим образом.

54. Выделяем подформулу 2 + 2. Остаток (2 + 2)(1 + 1) +1.

55. Выделяем подформулу 2 + 2. Остаток 1(1 + 1) + 1.

56. Выделяем подформулу 1(1 + 1) + 1. Остаток 1.

57. П р и м е р 2.3. Реализовать БФ, рассмотренную в примере 2.1, на5.универсальных модулях.

58. Пример2.4. Расширим базис двухместных операций, введя в негооперацию НЕРАВНОЗНАЧНОСТЬ. При этом БФУ, рассмотренная в примере2.1, может быть представлена в виде:f ((х {+) х )х v х х Их v х ) v х .2 3 4 5 6 7 8

59. Выделяем подформулу (1 ©1)1. Остаток (2 + 2) (1 + 1) + 1.

60. Остаточная формула не содержит подформул из трех букв.

61. Выделяем подформулу 2. Остаток (1 + 2)(1 + 1) + 1.

62. Выделяем подформулу 1+2. Остаток 1(1 + 1) + 1.

63. Выделяем подформулу 1(1 + 1). Остаток -1+1.

64. Остаточная формула содержит менее трех букв.

65. Выделяем подформулу 1+1. Остаток 1.

66. В 11. показано, что для БФУ, заданной на t входных наборах, может быть построена БФ в указанном базисе с числом буквh <- (3/2) t 2 при t >» 2. (2.5)

67. Таким образом, из соотношений (2.1), (2.4), (2.5) следует, что01.<= rain (2(2t + t 1 0з:п 3(t 2)г • .—2.6)

68. П р и м е р 2. 5. Реализовать не полностью определенную БФУ, заданную табл.2.1, на 3-универсальных модулях.