4.1.4. Выполнить подстановку: 247

a) _А ^BC(АB); 247

b) _(BA  ^(BC))_А ^{(BA)} (ABC); 247

c) _А^B (AB)  (BA). 247

Глава 5. Основы теории алгоритмов 252

5.1. Рекурсивные функции 253

5.1.1. Базовые функции 254

5.1.2. Элементарные операции 254

5.2. Машина Тьюринга 260

5.2.1. Описание машины Тьюринга 262

5.2.2. Примеры машин Тьюринга 264

5.2.3. Композиция машин Тьюринга 275

Алгоритм вычисления оператора суперпозиции: 276

T_h:q_о|^{g1(x1+1, x2+1,.. xn+1) +1} #...|^{gm(x1+1, x2+1,.. xn+1) +1} ²⁷⁶

T_f: q_о|^x+1# |^y+1#  q_k|^{f (x+1; y+1) +1} # . 276

Алгоритм вычисления оператора рекурсии: 276

5.3. Нормальные алгоритмы Маркова 279

Протокол. 282

Протокол. 282

Протокол. 283

Протокол. 284

Протокол. 285

5.4 Сложность вычислений 287

Вопросы и задачи 288

Глава 6. Конечные автоматы 289

6.1. Абстрактный автомат 289

6.1.1. Типы конечных автоматов 293

293

295

6.1.2. Описание автоматов 296

  Граф детерминированного автомата Мили. 299

Граф детерминированного автомата Мура. 301

Граф недетерминированного автомата Мили. 302

6.1.3. Автоматное моделирование алгоритмов 304

Рис. 6.7.. Компоненты блок-схемы алгоритма. 305

Рис. 6.8. Операционный и управляющий автоматы. 306

6.1.3.1. Автомат Мили - модель управляющего автомата 307

Множества входных и выходных сигналов управляющего автомата и его внутренних состояний: 309

6.1.3.2. Автомат Мура - модель управляющего автомата 310

6.1.3.3. Микропрограммный автомат 314

6.1.4. Эквивалентность автоматов 317

Анализ таблицы показывает, что 319

6.1.5. Эквивалентность внутренних состояний автомата 321

6.1.5.1. Детерминированный автомат 321

Анализ таблицы показывает, что 322

6.1.5.2. Недетерминированный автомат 333

Анализ таблицы показывает, что 335

6.2. Структурный автомат 343

6.2.1. Произведение автоматов 344

6.2.1.1. Последовательное соединение автоматов 344

6.2.1.2. Параллельное соединение автоматов 345

6.2.2. Обратная связь автоматов 348

6.2.3. Сумма автоматов 350

6.2.4. Структурный автомат и кодирование 351

6.3. Логическое проектирование автоматов 352

6.3.1. Кодирование алфавитов автомата 352

6.3.2. Автоматы без “памяти”. 353

6.3.2.1. Формирование оператора  353

6.3.2.2. Формирование системы операторов  357

6.3.2.3. Логическая схема комбинационного автомата 360

6.3.3. Автоматы с “памятью” 361

6.3.3.1. Формирование оператора  363

6.3.3.2. Формирование оператора  364

.3.3.3. Логическая схема автомата с “памятью” 367

Вопросы и задачи 368

Литература 370

Предметный указатель 371

“Теперь в математике остаются только целые числа и конечные...системы целых чисел...”

Анри Пуанкаре.

Введение

Основное отличие дискретной математики от классической заключается в отсутствии понятий предела и непрерывности, а основными носителями являются, например, целые числа и многочлены, векторы и матрицы, чертежи и рисунки, слова и команды и т. п. Элементы носителя формируют состав какой-либо системы, а отношения между ними – ее структуру. Отношения и элементы системы могут изменять свое значение в дискретные моменты времени.

Следовательно, состав и структура таких систем представляют дискретную модель, для описания которой привлекается аппарат дискретной математики.

В главе I – Алгебраические системы - изложены основные понятия теории множеств, отображений и отношений. Особенность данной главы заключается в том, что в ней приведены основные характеристики “четких” и “нечетких” объектов. Это – четкие и нечеткие множества, четкие и нечеткие отображения, четкие и нечеткие отношения. Такое построение главы позволяет глубже понять единство и различия “четких” и “нечетких” объектов, условия исполнения алгебраических операций над этими объектами. В главе приведены многочисленные примеры.

В главе 2 - Элементы комбинаторики - сформулированы основные требования к комбинаторным объектам, рассмотрены основные процедуры формирования упорядоченных и неупорядоченных выборок: размещения и перестановки, сочетания и разбиения. Все разделы главы подкреплены примерами на различных множествах.

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

В главе 4 – Основы математической логики – изложены основные понятия логик высказываний и предикатов, реляционной и нечеткой логик, показаны основные процедуры вывода заключений для дедуктивного метода и принципа резолюции. Кратко описаны возможности языков Prolog для программирования логических задач, SQL для формирования запросов. Описана также одна из экспертных систем –MYCIN, использующая правила нечеткой логики при выводе заключения.

В главе 5 – Основы теории алгоритмов - приведены три модели алгоритмов: рекурсивные функции, машины Тьюринга и нормальные алгоритмы Маркова. По каждой модели приведены вычислительные примеры. Показано, что любая частично рекурсивная функция может быть реализована на машине Тьюринга или нормальном алгоритме Маркова.

В главе 6 – Конечные автоматы – изложены основы формализации и классификации конечных автоматов, дано описание их характеристик. Изложены основные приемы минимизации детерминированного и частично определенного (или недетерминированного) абстрактного автомата, формирования структурного автомата при синхронном и асинхронном режимах работы и различных схемных соединениях элементарных автоматов. Для структурного автомата дано описание способов и приемов логического проектирования комбинаторного автомата и автомата с памятью. Приведены примеры минимизации преобразователя кода, рассмотрены проблемы автоматного моделирования алгоритмов и минимизации состава и структуры автомата с памятью.