ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16650
Скачиваний: 202
191
9.7 Теорема Поста о функциональной полноте
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Формулировка теоремы Поста: система булевых функций
называется функционально полной, если она содержит хотя бы од-
ну функцию:
1) не сохраняющую константу 1;
2) не сохраняющую константу 0;
3) несамодвойственную;
4) нелинейную;
5) немонотонную.
Доказательство теоремы приведено в [51, с. 152].
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
На первый взгляд может показаться, что функционально полная система
должна содержать не менее пяти функций. На самом деле это не так. Суще-
ствуют функции, обладающие одновременно несколькими свойствами из пере-
численных в теореме Поста. Например, функция
f = AB+CD
одновременно является нелинейной и несамодвойственной. Функция
C
B
A
BC
AC
B
A
f
+
+
+
=
несамодвойственна, нелинейна, немонотонна, не сохраняет нуль. А функция
Шеффера вида
C
B
A
f
+
+
=
одна образует функционально полную систему, так как она является несамод-
войственной, нелинейной, немонотонной, не сохраняющей нуль и не сохраня-
ющей единицу.
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 9.6
· · · · · · · · · · · · · · · · · · · · · · ·
Некто предлагает выпускать в массовых масштабах два типа микросхем,
реализующих булевы функции
1
2
;
,
f
ABD
BCD
ABD
BC D
f
ABCD
ABCD
ABD
BC D
AC D
=
+
+
+
=
+
+
+
+
обосновывая своё предложение тем, что, соединяя элементы последовательно,
можно реализовать любую булеву функцию. Выяснить, достаточно ли обосно-
ванно это предложение.
192
Определим, к каким замечательным классам относятся функции f
1
и f
2
:
1) обе они не сохраняют константу единица;
2) обе не сохраняют константу нуль;
3) обе являются самодвойственными;
4) обе нелинейны;
5) обе немонотонны.
Таким образом, система не удовлетворяет требованиям полноты теоремы
Поста: в ней нет несамодвойственной функции. Практически это значит, что
никакими способами, применяя только эти два элемента, реализовать несамод-
войственные функции не удастся.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 9.7
· · · · · · · · · · · · · · · · · · · · · · ·
Другой разработчик предлагает систему также из двух элементов: один
элемент реализует симметрическую функцию, второй – инверсию:
f
1
=
)
,
,
,
(
2
D
C
B
A
S
=
.
CD
B
A
D
C
B
A
D
C
B
A
D
C
B
A
D
C
B
A
D
C
AB
+
+
+
+
+
f
2
= .
A
Требуется выяснить, обладает ли функциональной полнотой эта система
логических элементов.
Функция f
1
не сохраняет единицу, сохраняет нуль, несамодвойственна,
нелинейна, немонотонна. Функция f
2
не сохраняет единицу, не сохраняет нуль,
самодвойственна, линейна, немонотонна. Очевидно, что эти логические эле-
менты образуют функционально полную систему, и если организовать их мас-
совый выпуск (например, в микросхемном исполнении), то инженеры получат
возможность строить любые электронные логические схемы, используя только
эти два элемента.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Завершим тему следующим замечанием. Функционально полные наборы
могут состоять из очень малого числа различных логических элементов.
Например, функционально полным является набор, построенный на основе
только одного элемента Шеффера, содержащего всего лишь два входа. Доста-
точно организовать его массовый выпуск, и появится возможность строить не
только комбинационные, но и многотактные автоматы, в которых для реализа-
ции памяти используются триггеры, состоящие из тех же элементов Шеффера.
Но всё это справедливо только в принципе. Практически же реализация схем на
193
элементах Шеффера во многих случаях является слишком громоздкой. Напри-
мер, для реализации простейшей булевой функции
)
)(
(
D
C
B
A
f
+
+
=
необходимы две схемы ИЛИ и одна схема И. Всего три элемента. Если же при-
менить двухвходовые схемы И-НЕ, то потребуется четыре элемента (при усло-
вии, что триггеры имеют парафазные выходы). Это видно из следующего вы-
ражения, подготовленного для построения схемы на элементах Шеффера:
.
D
C
B
A
f =
В связи с этим специалисты по цифровой технике хотя и учитывают по-
ложения теории, но ориентируются в основном на потребности практики и со-
здают системы из десятков элементов с многократной избыточностью по функ-
циональной полноте.
194
10 Автоматы с памятью
10.1 Вводные замечания
Понятию автомата в современной научно-технической литературе даётся
различное толкование в зависимости от того, к какой области оно относится: к
математике или технике. Примером публикации, где даётся математическое
определение понятию «автомат», можно назвать [51]. Её авторы пишут:
«Конечный автомат определяется как совокупность следующих пяти объ-
ектов:
1)
S – конечное множество состояний;
2)
I – конечное множество входных символов;
3)
O – конечное множество выходных символов;
4)
σ – отображение S × I в S; эта функция определяет по текущим состо-
янию и входу следующее состояние и называется функцией изменения
состояний или функцией переходов;
5)
δ – отображение S × I в O; эта функция определяет по текущим состо-
янию и входу текущее значение выхода и называется выходной функ-
цией» [51, с. 207].
В. М. Глушков к этим пяти добавляет шестой объект – начальное состоя-
ние [12, с. 36].
Н. И. Кондаков пишет: «Автомат (греч. automatos – самодействующий) –
устройство, самостоятельно выполняющее посредством внутреннего механизма
заданную человеком программу, т. е. действующее по программе без непосред-
ственного участия программиста в том или ином определённом процессе (в
промышленности, в науке, в сфере обслуживания) получения, преобразования и
использования информации, материалов, различных видов энергии» [25, с. 15].
Определение Н. И. Кондакова по объёму охватывает гораздо более широкий
класс объектов. Кроме тех, что описаны в [51], под него подходят и такие
устройства, как автомат Калашникова (стрелковое оружие), регулятор Уатта
[44, с. 1365], отбойный молоток и др. В [51] же изучаются только цифровые
устройства, из всего многообразия которых наиболее ярким представителем яв-
ляется цифровая вычислительная машина (компьютер). При этом основное
внимание уделяется не собственно устройствам, а их модели в виде конечного
автомата [39, с. 77], имеющего один вход, на который извне поступает инфор-
мация в виде последовательности букв входного алфавита, и один выход, куда
195
выводится переработанная информация в виде последовательностей букв вы-
ходного алфавита. Кроме того, так как автомат содержит внутреннюю память,
вводится понятие алфавита состояний.
Необходимо отметить, что прикладник всегда имеет дело не с теоретиче-
ской моделью автомата, а с некоторой технической задачей. Разобравшись с её
условием, он может сразу найти решение, не применяя никакой теории, если
задача достаточно проста. Но в более сложных случаях ему может помочь тео-
рия конечных автоматов. Если автомат содержит внутреннюю память, то его
работа состоит в переходе памяти под действием тактовых импульсов из одно-
го состояния в другое с последующим их преобразованием. Это можно пред-
ставить таблицей переходов и таблицей выходов, где для каждого входного
сигнала и состояния памяти указывается, в какое состояние должен перейти ав-
томат и что отправить на выход.
Любой автомат с внутренней памятью – это многотактное устройство, по-
разному реагирующее на одни и те же входные сигналы, в отличие от комбина-
ционной схемы, не содержащей внутренней памяти, вследствие чего её можно
назвать однотактным автоматом. В [58] об этом говорится следующим образом:
«Многотактные устройства (последовательностные устройства, конечные авто-
маты) отличаются от комбинационных тем, что значение их выходной величи-
ны зависит не только от комбинации значений входных переменных, но и со-
стояния устройства к моменту приложения входных воздействий. Иначе
говоря, подобные устройства обладают памятью».
В данной главе рассматриваются универсальные триггеры типов T, JK, D
и приводятся примеры синтеза на их основе простейших автоматов с памятью,
т. е. многотактных устройств дискретного действия.
10.2 Триггер типа Т
Триггер типа Т является одним из наиболее распространенных на практи-
ке. Он имеет два установочных входа R и S (как и в случае RS-триггеров), один
счетный вход Т и два выхода – прямой и инверсный.
Т-триггер меняет свое состояние на противоположное под действием
каждого импульса, поданного на вход Т. В электронной технике используются
самые разнообразные импульсы. Если их представить графически в системе де-
картовых координат U – t, где U – напряжение, t – время, то графики могут
быть различной формы – треугольные, прямоугольные, в виде трапеции и т. д.