Математический аппарат инженера
Шрифт:
Булевы функции одной переменной. Общая таблица соответствия для булевых функций одной переменной имеет вид (справа указаны обозначения функций):
x
|
0
1
|
y
– --
|
– --
– --
|
– --
y0
|
0
0
|
0
y1
|
0
1
|
x
y2
|
1
0
|
x
y3
|
1
1
|
1
Две функции у0 = 0 и у3 = 1 представляют собой функции-константы (тождественный нуль и тождественная единица), таккакони не изменяют своих значений при изменении аргумента. Функция y1 = х повторяет значения переменной х и потому просто совпадает с ней.
Единственной нетривиальной функцией является у2 = x , называемая отрицанием или инверсией ( x читается «не х»). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.
– !!!!!!!!!!!!!!!!!!!!!
–
– Продолжение следует...
–
– Содержание продолжения -
...
2. Алгебра логики
3. Контактные схемы
4. Логические схемы
5. Минимизация булевых функций
6. Конечные автоматы
1. Основные определения. В контактных и логических схемах значения выходных переменных определяются только комбинацией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значении входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи, с чем схемы с такими свойствами называют последовательностными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы.
Пусть Xi– алфавит входной переменной хi, а Yi – алфавит выходной переменной yi. Конечный автомат с n входами и m выходами характеризуется входным алфавитом Х = Х1 x Х2 x ... Хn и выходным алфавитом Y = Y1 x Y2 x ... Ym, причем символами входного алфавита служат слова x = (x1, x2, …, xn) длины n, а символами выходного алфавита - слова y = (y1, y2, …, ym) длины m, где xi Xi и yi Yi. Особого внимания заслуживают конечные автоматы с двузначным структурным алфавитом, зависимости между входными и выходными переменными которых выражаются булевыми санкциями. Их значение обусловлено тем, что любая информация может быть представлена в двоичных кодах (двоично-десятичные коды чисел, телетайпный код в технике
– 564 -
связи и т.п.). В то же время при технической реализации автоматов используются преимущественно двоичные элементы и двузначная логика.
В реальных условиях сигналы представляются непрерывными функциями времени, поэтому для надежного различения сигналов требуется, чтобы новые значения на входах появлялись после окончания переходных процессов, связанных с предыдущими значениями. При рассмотрении логической структуры автоматов обычно отвлекаются от существа этих процессов и считают, что переменные изменяются не непрерывно, а мгновенно в некоторые моменты времени, называемые тактами. Интервалы между тактами могут быть различными, но без потери общности их можно считать равными t . Предполагается, что тактовые моменты t + 1 =t + t определяются синхронизирующими сигналами. Таким образом, вводится понятие дискретного автоматного времени tn(n = 1, 2, ...), причем переменные зависят не от физического времени, а от номера такта , т. е. вместо непрерывных функций x(t) рассматриваются дискретные значения х.
2. Состояния. Кроме входных и выходных переменных, можно выделить некоторую совокупность промежуточных переменных, которые связаны с внутренней структурой автомата. В комбинационных схемах промежуточные переменные непосредственно не участвуют в соотношениях вход - выход. Напротив, выходные функции последовательностных схем в качестве своих аргументов, кроме входных переменных, обязательно содержат некоторую совокупность промежуточных переменных s1, s2, …, sk, характеризующих состояние схемы. Набор всех возможных состоянии, которые присущи данной схеме, называется множеством состояний. Если S1, S2, …, Sk– конечные алфавиты переменных состояния s1, s2, …, sk, то множество состояний S = S1 x S2 x … x Sk также является конечным множеством.
Строгое определение понятия состояния связывается с той ролью, которое оно играет при описании конечных автоматов. Во-первых, значения совокупности выходных переменных на -м такте у = (y1, y2, …, ym), однозначно определяется значениями входных переменных x = (x1, x2, …, xn) и состоянием s = (s1, s2, …, sk), на том же такте, т.е. у = (x, s). Во-вторых, состояние s( + 1) в следующем ( + 1)-м такте однозначно определяется входными переменными х и состоянием s в предыдущем такте, т.е. s( + 1) = (x, s).
Таким образом, состояние конечного автомата в любой тактовый момент характеризуется значениями такой совокупности переменных, которая вместе с заданными значениями входных переменных позволяет определить выходные переменные в данный тактовый момент и состояние в следующий тактовый момент.
– 565 -
Ясно, что последовательностные схемы должны обладать способностью сохранять предыдущее состояние до следующего такта, в связи с чем их называют также автоматами с памятью или последовательностными машинами. В качестве памяти могут использоваться элементы задержки, на выходах которых повторяются входные воздействия со сдвигом во времени на интервал между тактами Dt. Широко применяются также различные запоминающие элементы, например, триггеры, способные сохранять состояния на выходах до тех пор, пока оно не изменяется в результате воздействия на их входы.
3. Типы конечных автоматов. В технике с понятием автомата обычно связывается некоторое устройство, способное выполнять определенные функции без вмешательства человека или с его ограниченным участием. Однако такое понимание является слишком узким. В широком смысле конечный автомат - это математическая модель, отображающая физические или абстрактные явления самой разнообразной природы. Такая модель успешно используется как в технике (проектирование электронных вычислительных машин, систем управления и связи), так и в других областях - психологии и физиологии (исследование деятельности нервной системы человека и простейших видов поведения животных), лингвистике (анализ синтаксиса русского, английского или других языков, расшифровка древних рукописей), теории и практике административного управления и т.п. Универсальность теории автоматов позволяет рассматривать с единой точки зрения различные объекты, устанавливать связи и аналогии между ними, переносить результаты из одной области в другую.
Рис. 235. Блок-схема конечного автомата.
Конечный автомат М определяется как система с конечным входным алфавитом Х = { 1, 2, ... , p}, конечным выходным алфавитом Y = {v1, v2, …, vq}, конечным множеством состояний S = {1, 2, ..., i}, и двумя характеристическими функциями: