|
|
выш мат. Алексеев-В.В.-Алгебра-логики. Инистерство образования и науки российской федерации
М
ИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Саровский физико-технический институт -
филиал федерального государственного автономного образовательного учреждения высшего профессионального образования «Национальный исследовательский ядерный университет «МИФИ»
(СарФТИ НИЯУ МИФИ)
Кафедра вычислительной и информационной техники
В.В. Алексеев
Элементы алгебры логики
Методическое пособие по курсу “ДИСКРЕТНАЯ МАТЕМАТИКА”
г. Саров
2015 г.
Логические основы цифровых автоматов.
Конечные цифровые автоматы.
(Общие сведения).
Все многообразие элементов, узлов, блоков, устройств, из которых состоит любая ЭВМ, является примером различных типов преобразователей информации - цифровых автоматов. Методы теории цифровых автоматов (ЦА), являющихся математической моделью цифровых устройств, используются в качестве теоретической базы для анализа и синтеза различных цифровых устройств ЭВМ.
Под цифровым автоматом будем понимать устройство предназначенное для преобразования цифровой (дискретной) информации, способное переходить под воздействием входных сигналов из одного состояния в другие и выдавать выходные сигналы. Отличительные особенности ЦА заключаются в том, что они имеют дискретное множество внутренних состояний и переход из одного в другое осуществляется скачкообразно.
Дискретность информации проявляется в том, что она представляется посредством набора слов конечной длины в некотором алфавите.
Реальные ЦА конечны, т. е. множество входных и выходных сигналов, а также число входных и выходных каналов и множество состояний автомата конечны.
ЦА функционируют в дискретные моменты времени, временной интервал между которыми Т называется тактом. В зависимости от того, чем определяется время Т, различают автоматы синхронного и асинхронного действия.
Для ЦА синхронного действия входные сигналы действуют в строго определенные моменты времени при Т = const, определенные генератором синхроимпульсов, в которые возможен переход из одного состояния в другое.
Для ЦА асинхронного действия Т const и работа ЦА определяется моментами поступления входных сигналов, а переход из одного состояния в другое осуществляется при неизменном состоянии входа.
Для идеализированных ЦА не учитывается переходные процессы в схемах и разница в фактических величинах Т для правильного функционирования не имеет значение. Для описания законов функционирования ЦА вводят абстрактное время.
По степени детализации описания ЦА различают автоматы абстрактные и структурные. В соответствии с этим различают абстрактную и структурную теорию ЦА.
Абстрактные ЦА рассматриваются как " черный ящик ", имеющий один вход и один выход, т. е. отвлекаются от структуры ЦА и его входных Х (t) и выходных Y (t) сигналов.
ЦА
X (t) Y(t)
Для задания абстрактного автомата необходимо задать три алфавита :
- входной X = { }
- выходной Y = { }
- состояний S = { }
Тогда закон функционирования абстрактного автомата может быть задан уравнениями:
1.1
где (s, x) - функция переходов автомата ;
(x, s) - функция выходов автомата ;
- начальное состояние автомата .
ЦА, закон функционирования которых определяется уравнениями (1.1), называются автоматами Мили.
ЦА, выходные сигналы в которых только от состояния автомата и не зависят от значения входных сигналов, называются автоматами Мура, т. е. для них уравнения (1.1) преобразуются в форму
1.2
где [ s (t) ] -сдвинутая функция выхода.
ЦА, имеющая более одного внутреннего состояния, называются автоматами с памятью. Частный случай абстрактных ЦА - автоматы с одним внутренним состоянием. Такие тривиальные автоматы называют автоматами без памяти или комбинационными схемами. Закон функционирования таких автоматов будет определяться одним уравнением :
Y (t) = [ x(t)] ,
т.е. каждому входному сигналу х(t) сопоставляется свой выходной сигнал y(t).
Наиболее распространенными стандартными способами задания абстрактных цифровых автоматов является задание их с помощью матриц, таблиц переходов и выходов или одной совмещенной таблицей, с помощью направленных графов, вершины которого отождествляются с состояниями автомата, а соединяющие их стрелки – с входными и выходными сигналами. Таблица переходов и выходов или граф цифрового автомата в явном виде задает функцию переходов и выходов и реализует отображение множества слов входного алфавита в множество слов выходного алфавита, т.е. любому входному слову из входного алфавита автомата будет соответствовать вполне определенное выходное слово из выходного алфавита. Наряду со стандартными способами задания абстрактных цифровых автоматов существуют так называемые начальные языки, с помощью которых цифровой автомат описывается на поведенческом уровне, т.е. могут быть заданы отображения последовательностей состояний входа в последовательность состояний выхода. Функция переходов и выходов с помощью таких языков в явном виде не задается. К таким языкам, например, относят языки регулярных выражений алгебры событий, предикатный, операторных схем алгоритмов и др. Одна из задач абстрактной теории цифровых автоматов – рассмотрение вопросов преобразования описания цифрового автомата на начальном языке в описание на одном из стандартных языков.
Структурный цифровой автомат в отличие от абстрактного является его дальнейшей детализацией, когда рассматривается как его внутренняя структура, так и структура входных и выходных сигналов. Это означает, что в теории таких автоматов изучаются методы построения автоматов из элементарных автоматов, способы кодирования внутренних состояний автомата, а также способы кодирования входных и выходных сигналов элементарными сигналами, подаваемыми по реальным физическим входным и выходным каналам. При решении вопросов кодирования каждому состоянию абстрактного автомата ставится в соответствие комбинации состояний элементарных автоматов, имеющих два внутренних состояния, а каждому входному (выходному) сигналу – комбинация элементарных двузначных сигналов.
Одна из основных задач теории цифровых автоматов, решаемых применительно к построению различных цифровых устройств ЭВМ, заключается в том, чтобы задачу анализа и синтеза таких устройств свести к задаче анализа и синтеза комбинационных схем. При этом в качестве основного математического аппарата используется аппарат алгебры логики, что связано с двоичным представлением структурного алфавита цифровых устройств ЭВМ.
1. Функции алгебры логики и их основные свойства.
Основные определения
Для формального описания цифровых автоматов (ЦА) широко применяют аппарат алгебры логики (АЛ), являющейся одним из разделов математической логики. Создатель алгебры логики - английский математик Джордж Буль (1815 - 1864).
Определение 1. Основное понятие АЛ - высказывание. Высказывание - некоторое предложение, о котором можно утверждать, что оно истинно или ложно. Любое высказывание можно обозначить символом, например, X и считать, что X=1, если высказывание истинно, X=0 если высказывание ложно.
Определение 2. Логическая (Булева) переменная - такая величина X, которая может принимать только два значения: X = { 0, 1 }.
Определение 3. Высказывание абсолютно истинно, если соответствующая ей логическая величина X принимает единичное значение при любых условиях.
Определение 4. Высказывание абсолютно ложно, если соответствующая ей логическая переменная X принимает нулевое значение при всех условиях.
Логическая функция ( функция алгебры логики - ФАЛ ) - функция , принимающая значение, равное нулю или единице на наборе логических переменных
Рассмотрим множество векторов , где - (координаты векторов) могут принимать значения 0 или 1. Таким образом, множество состоит из различных векторов. Совокупность координат некоторого фиксированного вектора из множества будем называть двоичным набором. Сопоставим каждому вектору из число 0 и 1, т. е. произведем однозначное отображение множества на множество Y { 0, 1}.
Определение 5 Функцией алгебры логики (ФАЛ) называется функция, дающая однозначное отображение X в Y.
Т. к. число различных наборов значений аргументов является конечным, то любая ФАЛ может быть полностью задана конечной таблицей. В левой части этой таблицы перечислены все наборы значений аргументов этой функции, а в правой части - значения функции на этих наборах.
-
Логические переменные
|
Функция
|
|
|
...
|
...
|
...
|
...
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
...
|
...
|
...
|
...
|
1
|
1
|
0
|
0
|
1
|
...
|
...
|
...
|
...
|
...
|
1
|
1
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
1
|
1
|
...
|
...
|
...
|
...
|
0
|
0
|
0
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
...
|
Определение 6. Если две ФАЛ ( ) и ( ) принимают на всех возможных наборах значений аргументов одинаковые значения, то функции и называются равносильными или равными, т.е.:
( ) = ( )
Определение 7. Функция ( ) существенно зависит от аргумента , если имеет место соотношение:
( ) ( )
В противном случае говорят, что от функция зависит несущественно и является фиктивным аргументом. ФАЛ не изменится, если к ее аргументам дописать любое число фиктивных аргументов, или зачеркнуть все фиктивные аргументы.
Теорема 1.1 Число различных ФАЛ, зависящих от n аргументов конечно и равно .
Для доказательства составим таблицу:
-
|
|
0 0 ... 0 0
|
|
0 0 ... 0 1
|
|
0 0 ... 1 0
|
|
...
|
...
|
1 1 ... 1 1
|
|
В этой таблице справа стоит одна из ФАЛ, зависящая от n аргументов. Задавая тот или иной конкретный двоичный набор < >, мы будем тем самым задавать одну из возможных функций алгебры логики. Но различное число таких наборов равно . Теорема доказана.
Значения функции могут быть заданы не на всех возможных наборах аргументов. На некоторых наборах значения ФАЛ могут быть не определены. Такие ФАЛ называют не полностью определенными или не- доопределенными. Функцию можно доопределить. Если ФАЛ не определена на m наборах аргументов, то путем ее произвольного доопределения можно получить различных полностью определенных функций.
1.2 Элементарные функции алгебры логики
В число ФАЛ, подсчитываемых с помощью теоремы 1.1 входят как функции существенно зависящие от всех n аргументов, так и функции, для которых часть из этих аргументов фиктивна. Например, для n=1 имеем =4 различных функций, приведенных в следующей таблице:
-
Из таблицы видно, что только и существенно зависят от , а для и этот единственный аргумент является фиктивным. Функция (x), повто-ряющая значение логической переменной - тождественная функция ((x) x ), а функция (x) - принимающая значения, обратные значениям x - логическое отрицание, илифункция отрицания, или инверсии, или функция НЕ ((x) = ).
Теорема 1.2. Число ФАЛ, существенно зависящих от n аргументов, определяется следующим рекуррентным соотношением:
, (1.3)
где - биномиальные коэффициенты. , - число ФАЛ, существенно зависящих от i аргументов.
Правая часть соотношения есть разность между числом всех ФАЛ и суммой всех ФАЛ, существенно зависящих от любого числа аргументов, меньших чем n.
Вместо рекуррентного соотношения 1.3 можно найти прямое выражение для значений . Как показал Крылов Г. А.
. (1.4)
Пример Найти число ФАЛ, существенно зависящих от 3-х переменных.
Имеем: =2.
Действительно
.
.
.
Итак, в случае n=0 имеем в силу теоремы 1.1 две функции, совпадающие с константами 0 и 1.
= 0; = 1 (1.5)
При n =1 имеем 2 функции, существенно зависящих от x
= x; = (не ' x '). (1.6)
Рассмотрим логические функции от переменных:
Функции
|
|
|
|
|
Примечание.
|
|
0 0
|
0 1
|
1 0
|
1 1
|
|
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
0
|
1
|
= ==& конъюнкция.
|
|
0
|
0
|
1
|
0
|
= (запрет )
|
|
0
|
0
|
1
|
1
|
= (тождественность )
|
|
0
|
1
|
0
|
0
|
= (запрет )
|
|
0
|
1
|
0
|
1
|
= (тождественность )
|
|
0
|
1
|
1
|
0
|
= ( ) (сложение по модулю 2)
|
|
0
|
1
|
1
|
1
|
= = + (дизъюнкция)
|
|
1
|
0
|
0
|
0
|
( Функция Пирса )
|
|
1
|
0
|
0
|
1
|
)(Равнозначность)
|
|
1
|
0
|
1
|
0
|
= (Отрицание )
|
|
1
|
0
|
1
|
1
|
= () (Импликация)
|
|
1
|
1
|
0
|
0
|
= (Отрицание )
|
|
1
|
1
|
0
|
1
|
= () (Импликация)
|
|
1
|
1
|
1
|
0
|
= (/) ( Функция Шеффера)
|
|
1
|
1
|
1
|
1
|
1
| |
|
|
Скачать 6.59 Mb.