Дискретные устройства без памяти

Введенное в предыдущем параграфе понятие автомата является достаточно общим. Накладывая ограничения на компоненты X, Y, Q, Ψ, Θ можно получить частные случаи автоматов. Одним из них являются автоматы без памяти, т.е. устройства, в которых не происходит фиксации внутреннего состояния. Очевидно, в этом случае из общего описания должны быть исключены компоненты Q и Ψ; автомат без памяти задается тройкой компонентов < X, Y, Θ>. Соотношение (9.2) принимает вид

т.е. выходной символ на данном такте определяется только входным символом и не зависит от ранее поступивших символов. Следовательно, каждый автомат без памяти реализует единственный преобразователь (оператор), который осуществляет «побуквенный перевод» входных последовательностей символов в выходные.

Пусть имеется дискретное устройство, имеющее п входов х₁.....х_п и т выходов y₁ ..., у_т. Если данное устройство не обладает памятью, то преобразование входных сигналов в выходные описывается системой уравнений:

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

Подобные устройства могут быть построены путем соединения некоторого набора элементарных компонентов (элементов). Эти элементы образуют конечный набор, называемый базисом, а входящие в него элементы - базисными. Базис имеет смысл совокупности элементарных (простейших) действий, о которых шла речь в теории алгоритмов, а базисный элемент можно рассматривать в качестве устройства, выполняющее элементарное действие. Если речь идет о двоичных дискретных устройствах, то базисы строятся из элементов, которые реализуют простейшие логические функции. Напомним, что к таким функциям относятся конъюнкция (логическое И - ^), дизъюнкция (логическое ИЛИ - v), импликация (→), сумма по модулю 2 (Å), эквивалентности (~) и отрицания (логическое НЕ - Ø,). Однако между простейшими функциями имеются соотношения эквивалентности (см. приложение), позволяющие выразить одни функции через другие. В результате оказывается, что нет необходимости включать в базис все элементы, реализующие простейшие логические функции - достаточно выбрать некоторое минимальное их подмножество. Этому условию удовлетворяет базис, построенных на элементах И, ИЛИ и НЕ - он называется простейшим, а входящие в него элементы - логическими элементами или (логическими вентилями). Схемы элементов приведены на рис. 9.1. Рассмотрим каждый их них по отдельности.

Элемент И (^) имеет два входа, на которые независимо могут подаваться сигналы x₁ и х₂; каждый из сигналов является двоичным, т.е. может принимать одно из двух значений - 1 или 0; элемент формирует единственный выходной сигнал у, значения которого определяются только входными сигналами. Функция выходов Q (x₁,x₂) согласно табл. Б.1 (см. приложение Б) принимает следующие значения:

Функция выходов элемента ИЛИ (V) принимает следующие значения:

Логический элемент НЕ (Ø) обеспечивает одноместное преобразование (с одним входным сигналом) в соответствии с правилами:

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

Со схемами связано решение двух классов задач - анализа и синтеза. В задачах анализа выявляется логическая функция, реализуемая заданной схемой. Синтез - это, наоборот, построение схемы по заданной конечной логической функции.

Проблема алгоритмической разрешимости

Пример 4.12

Вероятность какого-либо одного из двух исходов независимых и несовместных событий равна сумме их вероятностей

Особенности устройств хранения информации

Постановка задачи

Вернуться в оглавление: Теоретические основы информатики