Материал: Методичка Дзержинский

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МИРЭА – РОССИЙСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

Р.И. Дзержинский, A.A.Воронцов

Математическая логика

и

теория алгоритмов

УЧЕБНОЕ ПОСОБИЕ

Москва – 2019

1

УДК 532.78:548.5 ББК 22.317

А31

Р.И. Дзержинский, А.А. Воронцов. Математическая логика и теория алгоритмов [Электронный ресурс]: Учебно-методическое пособие / Р.И. Дзержинский, А.А. Воронцов — М.: Московский технологический университет (МИРЭА), 2019. — 1 электрон. опт. диск (CDROM).

В учебном пособии излагаются основные разделы дисциплины «Математическая логика и теория алгоритмов». Учебное пособие предназначено для студентов Института информационных технологий и может быть полезным также при изучении дисциплин «Дискретная математика» и «Математическая логика и теория алгоритмов.

Учебно-методическое пособие издается в авторской редакции.

Авторский коллектив: Р.И. Дзержинский, А.А.Воронцов

Рецензенты:

Минимальные системные требования:

Наличие операционной системы Windows, поддерживаемой производителем. Наличие свободного места в оперативной памяти не менее 128 Мб.

Наличие свободного места в памяти хранения (на жестком диске) не менее 30 Мб. Наличие интерфейса ввода информации.

Дополнительные программные средства: программа для чтения pdf-файлов (Adobe Reader). Подписано к использованию по решению Редакционно-издательского совета Московского технологического университета от ___ __________ 2019 г.

Тираж 10

©Р.И. Дзержинский, А.А. Воронцов.., 2019

©МИРЭА – РОССИЙСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ (РТУ МИРЭА),

2019

2

3

Определение и способы задания конечного автомата

Описательные определения: Конечный автомат – это устройство M имеющее входной и выходной канал и находящееся в каждой из дискретных моментов времени, называемых тактовыми моментами, в одном из конечных состояний. По входному каналу в каждый момент времени t = 1, 2… в устройство M поступают входные сигналы из некоторого конечного множества сигналов, указывается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния, в котором находится устройство. Выходной сигнал в каждый момент времени зависит от состояния устройства и входного сигнала в текущий момент времени.

Определение: Конечным автоматом называется система M = { A, Q, B,G , F }, где A = {a1,…,an} – входной алфавит. Q = {q1,…,qn} – множество состояний автомата. B = {b1,…,bn} – выходной алфавит. Функция F(a, q): (A×Q → B) называется функцией выходов. Если a A, q Q то F(a, q) B. Функция G(a, q) называется функцией переходов: G : A×Q → Q. Если a A, q Q то G(a, q) Q.

Если в момент времени t = 1, 2… на вход автомата последовательно подаются входные символы x(t) A и автомат находится в состоянии q(t-1) Q, то под воздействием символа x(t) автомат перейдёт в новое состояние q(t) и выдаст выходной символ z(t). Величины x(t), q(t-1), q(t), z(t) связанны между собой следующими уравнениями, называемыми канонические уравнения автомата.

q(t) = G(x(t), q(t-1))

z(t) = F(x(t), q(t-1))

Автоматная таблица. Из определения конечного автомата следует, что его всегда можно задать таблицей, содержащей, m – строк и n – столбцов

Таблица 1

4

Каждая строка таблицы однозначно соответствует некоторому входящему сигналу, а столбец – некоторому состоянию автомата M. В клетку таблицы, стоящей на пересечении строки, соответствующей входящему символу ai и столбца, соответствующего состоянию qj, записывается пара G(ai, qj); F(ai, qj).

Диаграмма Мура. На плоскости рисуем n кругов, каждый взаимнооднозначно соответствуют состояниям q1,…,qn автомата M. Внутри каждого круга записываются соответствующие состояния. Из каждого круга проводится m – стрелок, взаимнооднозначно соответствующих символам входного алфавита A = {a1,…,an}. стрелке, соответствующей букве aj A и входящей из круга qj Q, приписывается пара (ai; F(ai, qj)) эта стрелка ведёт в круг соответствующей состояния q’, если q’ = G(ai, qj).

Примеры: Элемент задержки

Опр. Автомат с выходным состоянием q0, именуемый начальным, называется инициальным автоматом. Инициальный автомат представляет собой систему Mq0 = {A, Q, B, G, F, q0}. Если инициальный автомат задан таблицей или диаграммой Мура, то начальное состояние q0 отмечается некоторым символом, например *. При задании инициального автомата каноническими уравнениями к уравнениям добавляется соответствующее начальное условие q(0) = q0. Из определения инициального автомата следует, что любой автомат M с n – состояниями задаёт n – инициальных автоматов. В то же время знание всех этих инициальных автоматов полностью определяет автомат M.

Опр. Конечный автомат называется логическим, если все его алфавиты представляют собой булевы кубы соответствующих размерностей. A=Be, Q=Br, B=Bs. Тогда функция переходов G является системой булевых функций осуществляющих отображение булева куба Be+r в булев куб Br. А функция F

является системой булевых функций осуществляющих отображение булева куба Be+r в булев куб Bs.

Задание конечного автомата системой булевых функций.

Пусть M = {A, Q, B, G, F} – конечный автомат, заданный таблицей или диаграммой Мура. Если автомат не является логическим, то его тоже можно задать системой булевых функций. Но для этого надо провести двоичное кодирование алфавитов.

Алгоритм задания автомата системой булевых функций.

1.Находим числа e, r, s, удовлетворяющие условиям

5