- •Математическая логика и теория алгоритмов
- •11. Понятие об алгоритмах. Схемы алгоритмов
- •11.1. Понятие об алгоритме и теории алгоритмов
- •11.2. Схемы алгоритмов
- •11.3. Рекурсивные функции
- •11.4. Машина Тьюринга
- •11.5. Машина Поста
- •11.6. Нормальные алгорифмы а.А. Маркова
- •11.7. Универсальная абстрактная машина
- •11.8. Разрешимость в теории алгоритмов. Проблема самоприменимости
- •11.9. Сложность алгоритма
- •11.10. Представление схемы алгоритма эквивалентным автоматом
- •11.11. Представление схемы алгоритма микропрограммой с двумя типами микрокоманд
- •12. Элементы формальной логики
- •12.1. Предмет формальной логики
- •12.2. Понятие и его виды
- •12.3. Отношения между понятиями
- •12.4. Операции над понятиями
- •12.5. Суждение и его характеристика
- •Модальные и категорические суждения.
- •Простые категорические суждения.
- •Виды простых категорических суждений.
- •Распределение терминов в простом категорическом суждении.
- •Логический квадрат.
- •13. Умозаключение
- •13.1. Виды умозаключений
- •13.2. Непосредственное умозаключение
- •Умозаключения путем противопоставления предикату.
- •13.3. Опосредованное дедуктивное умозаключение. Фигуры силлогизма
- •Фигуры пкс.
- •Модусы пкс.
- •13.4. Дополнительные виды силлогизмов
- •13.5. Индуктивные умозаключения. Математическая индукция
- •14. Логика высказываний
- •14.1. Семантика логики высказываний
- •I закон – тождества.
- •14.3. Формализация высказываний
- •14.4. Интерпретации, разрешимость, выполнимость, общезначимость
- •14. 5. Логическая равносильность. Законы логики
- •14.6. Формы представления формул логики высказываний
- •14.7. Проблема дедукции в логике высказываний
- •15. Проверка правильности логических выводов. Метод резолюций
- •15.1. Закон контрапозиции
- •15.2. Логическое следование. Проверка правильности логических выводов
- •15.3. Силлогизмы в логике высказываний
- •Разделительно-категоричные силлогизмы.
- •16. Синтаксис и семантика языка логики предикатов
- •16.1. Понятие предиката
- •16.2. Кванторы и связанные переменные
- •16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
- •16.4. Семантика формул логики предикатов
- •Общезначимость, выполнимость, невыполнимость.
- •17. Тождественные преобразования формул логики предикатов
- •17.1. Операции над предикатами
- •17.2. Основные равносильности логики предикатов
- •Отрицание предложений с кванторами.
- •17.3. Тождественные преобразования формул
- •17.4. Универсум Эрбрана
- •18. Использование метода резолюций в логике предикатов
- •18.1. Подстановка и унификация
- •18.2. Резольвенция и факторизация
- •18.3. Метод резолюций в логике предикатов
- •18.4. Принцип логического программирования
- •19. Логические исчисления
- •19.1. Понятие о формальных теориях
- •19.2. Исчисление высказываний
- •19.3. Исчисление предикатов
- •19.4. Система натурного вывода
- •19.5. Понятие о математической лингвистике
- •19.6. Формальный язык
- •19.7. Формальные грамматики и их свойства
- •19.8. Теоремы Гёделя
- •20. Неклассические логики
- •20.1. Современные модальные логики
- •20.2. Понятие о теории неопределенности
- •20.3. Элементы теории нечетких множеств и нечеткая логика
- •20.4. Нечеткие алгоритмы
- •Литература
- •Приложение 1 Варианты контрольных заданий по дисциплине «Дискретная математика»
- •Приложение 2 Варианты контрольных заданий по дисциплине «Математическая логика»
11.11. Представление схемы алгоритма микропрограммой с двумя типами микрокоманд
Дальнейшее углубление в область программного обеспечения заключается в сопоставлении каждому блоку ГСА некоторой микрокоманды, которая, в простейшем случае формируется из микрокоманд двух типов [31]: 1) операционной (рис. 101) и 2) специальной или перехода (рис. 102).
-
Признак микрокоманды ПМ=1
Микрооперации
Рис. 101. Операционная микрокоманда: ПМ=1
-
Признак микрокоманды ПМ=0
Код логического условия
Адрес перехода
Рис. 102. Специальная, или переходов: ПМ=0
Если выполняется операционная микрокоманда, то последовательно выбираются адреса постоянного запоминающего устройства (ПЗУ) и последовательно выдаются микрооперации в операционное устройство. Это может быть реализовано путем перебора состояний счетчика по счетному входу +1 (рис. 103).
Рис. 103. Условное графическое обозначение счетчика
со счетным входом +1
Такой счетчик будет называться счетчиком микрокоманд. Конечно, для задач реальной размерности он должен иметь достаточное число состояний в отличие от счетчика, изображенного на рис. 103.
В случае выполнения специальной микрокоманды (рис. 102), если логическое условие равно единице, – производится переход по указанному адресу с использованием входа предустановки РЕ по указанным в поле адреса данным Di. Если логическое условие равно нулю, то выбирается следующий адрес. Если номер логического условия равен нулю, то это безусловный переход, и производится передача управления по указанному адресу (на входах Di).
Такая логика управления реализуется блоком управления – счетчик микрокоманд, который адресует память микропрограмм.
Получим микропрограмму реализации алгоритма, изображенного на рис. 98 для автомата с двумя типами микрокоманд (табл. 77).
Таблица 77
Микропрограмма с двумя типами микрокоманд
Метка |
Адрес микрокоманды |
Микрокоманда |
Комментарий | ||||||||||
ПМ |
1 |
2 |
3 |
4 |
5 |
6 |
7 | ||||||
M0: |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
Переход, если х1=1 на адрес 1100 |
|
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
Переход, если х2=1 к блоку 3 ГСА по адресу 0111 (метка М2) |
|
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
Выдача z4=1 (A4) |
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Возврат в 0000 безусловно к метке М0 |
|
0 |
1 |
0 |
0 |
- |
- |
- |
- |
- |
- |
- |
- |
Не используется |
|
0 |
1 |
0 |
1 |
- |
- |
- |
- |
- |
- |
- |
- |
Не используется |
|
0 |
1 |
1 |
0 |
- |
- |
- |
- |
- |
- |
- |
- |
Не используется |
M2: |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
Выдача z1=1 (A1) |
|
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
Выдача z2,z3=1 (A2) |
M3: |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Ожидание х3=1. Переход к метке М4, если х3=1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
Если х3=0, то А и безусловный переход к проверке х3 (метка М3) |
|
1 |
0 |
1 |
1 |
- |
- |
- |
- |
- |
- |
- |
- |
Не используется |
M1: |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
z4=1 (А4) |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Безусловный переход на начало к метке М0 |
M4: |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
z5=1 (А3) |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Безусловный переход на начало к метке М0 |
Таким образом, из табл. 77 следует, что необходимо всего 12 ячеек памяти по 8 бит, то есть всего 96 бит.
В рассмотренном автомате, если микрокоманда специальная (ПМ=0), разряды 1-2 используются для кодирования логического условия (значения указаны курсивом): 00 – безусловный переход, т.е. нет условия; 01 – х1; 10 – х2; 11 – х3. Если микрокоманда операционная, то разряды 1-5 отводятся для микроопераций z1-z5 соответственно. Особенность микропрограммы – возврат в исходное состояние после окончания работы.