Cтраница 4
Классическими подходами к описанию задания на проектирование устройства логического управления являются: таблицы автоматного графа, системы секвенций, логические схемы алгоритмов или логические схемы программ, а также описание на каком-либо алгоритмическом языке программирования. Возможны и другие формальные описания. Такое многообразие свидетельствует о том, что невозможно выбрать один единственный, пригодный для любого случая способ формализованного описания проектируемого устройства управления. Выбор того или иного способа во многих случаях определяется теми задачами, которые решаются при формализации, а также методом реализации. На алгоритмическом этапе проектирования устройства управления, когда создается описание алгоритма управления, прежде всего должны быть решены проблемы полноты и непротиворечивости задания. [46]
В предположении, что непротиворечивость некоторой теории доказана или хотя бы принята на веру, имеет смысл поставить проблему полноты этой теории. Теория называется полной, если она содержит достаточное для какой-нибудь цели количество теорем. Исходя из различных целей, которые мы ставим при построении теории, мы приходим к различным техническим значениям понятия полноты. Ограничимся следующим из возможных определений: теория Z называется полной, если для любого высказывания S этой теории либо S, либо - 5 есть теорема. Определение это исходит из того обстоятельства, что любое высказывание S теории Z9 будучи интерпретировано в некоторой модели, оказывается непременно либо истинным, либо ложным. Следовательно, в этом случае либо S, либо - 5 оказывается истинным и должно быть теоремой в теории Z. Теория, являющаяся одновременно непротиворечивой и полной, является максимальной в отношении непротиворечивости - в том смысле, что добавление к такой теории в качестве аксиомы любого предложения, которое можно в ней сформулировать, но не являющегося ее теоремой, приводит к противоречивой теории. Проблема полноты может быть лучше всего рассмотрена по отношению к таким аксиоматическим теориям, в которые явным образом включена используемая теория логического вывода. [47]
Постановка второй задачи - построения кода, приводящего к наиболее простой логической пасти устройства, принадлежит Дж. Предложенный им подход сводится к декомпозиции - разбиению исходного автомата на блоки; при этом состояния элементов памяти зависят только от выходов элементов памяти того же блока, что приводит к логическим функциям от меньшего числа переменных. Работа [112] посвящена одновременному решению обеих указанных задач кодирования состояний. В работе [113] впервые поставлена третья задача кодирования - построение кода, приводящего к структуре, устойчивой к d - оптибкам элементов памяти. Эта задача рассмотрена в разделе Теория структурной надежности настоящей статьи; здесь мы упомянем лишь о работах [114], в которых предложены методы одновременного решения первой и третьей задач. Оригинальное решение вопроса размещения состояний нашли в монографии [115], авторам которой был разработан метод синтеза асинхронных релейных устройств, основанный на реализации каждой внутренней переменной в виде инерционной подсхемы, реализующей как саму внутреннюю переменную, так и все переходы к нет. Этот метод дает размещение, обеспечивающее в некоторой степени простоту структуры и облегчающее устранение недопустимых состязаний. К вопросам абстрактного синтеза по своему содержанию ( но не по методам) примыкает группа работ, связанных с построением блочных структур из автоматов. Помимо упомянутых работ [78, 79] по блочному синтезу советским авторам принадлежит ряд важных результатов по исследованию проблемы полноты для различных базисов ( наборов) автоматов. В [116] доказана полнота одной системы автоматов без обратных связей; в [117] сформулированы условия полноты для автоматов Мура; п [118] доказана алгоритмическая неразрешимость проблемы полноты для произвольных систем автоматов, а в [119] даны асимптотические оценки числа неизоморфных автоматов. [48]
Постановка второй задачи - построения кода, приводящего к наиболее простой логической пасти устройства, принадлежит Дж. Предложенный им подход сводится к декомпозиции - разбиению исходного автомата на блоки; при этом состояния элементов памяти зависят только от выходов элементов памяти того же блока, что приводит к логическим функциям от меньшего числа переменных. Работа [112] посвящена одновременному решению обеих указанных задач кодирования состояний. В работе [113] впервые поставлена третья задача кодирования - построение кода, приводящего к структуре, устойчивой к d - оптибкам элементов памяти. Эта задача рассмотрена в разделе Теория структурной надежности настоящей статьи; здесь мы упомянем лишь о работах [114], в которых предложены методы одновременного решения первой и третьей задач. Оригинальное решение вопроса размещения состояний нашли в монографии [115], авторам которой был разработан метод синтеза асинхронных релейных устройств, основанный на реализации каждой внутренней переменной в виде инерционной подсхемы, реализующей как саму внутреннюю переменную, так и все переходы к нет. Этот метод дает размещение, обеспечивающее в некоторой степени простоту структуры и облегчающее устранение недопустимых состязаний. К вопросам абстрактного синтеза по своему содержанию ( но не по методам) примыкает группа работ, связанных с построением блочных структур из автоматов. Помимо упомянутых работ [78, 79] по блочному синтезу советским авторам принадлежит ряд важных результатов по исследованию проблемы полноты для различных базисов ( наборов) автоматов. В [116] доказана полнота одной системы автоматов без обратных связей; в [117] сформулированы условия полноты для автоматов Мура; п [118] доказана алгоритмическая неразрешимость проблемы полноты для произвольных систем автоматов, а в [119] даны асимптотические оценки числа неизоморфных автоматов. [49]