Теоретическая часть
Методы, используемые при поиске и сортировке
Оценки времени исполнения
Приложение на Delphi, в котором представлена работа некоторых методов сортировки и поиска
Пример выполнения
Вопросы для самопроверки
Представление множеств и отношений в программах
Алгоритмы генерации множеств
Then
Варианты заданий
Теоретическая часть
Примеры выполнения
Вариантв заданий
Перевод даты рождения в двоичную систему
Вопросы для самопроверки
Вопросы для самопроверки
Процедура основного обработчика
Вопросы для самопроверки
Практическая часть
Дешифраторы
Навигация
Дешифраторы
Основы дискретной математики
179431
знак
27
таблиц
82
изображения
7.2.2 Дешифраторы
Дешифратором (избирательной схемой) называется комбинационная логическая схема, в которой определенная комбинация входных сигналов вызывает появление сигнала на одной определенной выходной шине.
Если количество двоичных разрядов дешифрируемого числа обозначить через n, то число выходов дешифратора равно К = 2n.
В компьютере с помощью дешифраторов осуществляется выборка необходимых ячеек запоминающих устройств, расшифровка кода операции с подачей управляющих сигналов на те элементы, узлы и устройства машины, которые связаны с выполнением данной операции.
Дешифратор на 2 входа
Функционирование дешифратора, имеющего 2 входа и 4 выхода, описывается таблицей истинности, представленной на рисунке 7.8.
Выражения для функций F1, F2, F3, F4 в виде СДНФ, реализуемые соответствующими выходами схемы: 
, 
, 
, 
.
Упрощение выражения не требуется, пункт 3 порядка проектирования логических схем отсутствует.
Схема имеет вид, представленный на рисунке 7.8.
Рисунок 7.8 – Дешифратор на 2 входа
Ячейки C13 и D13 отведены для ввода комбинации входных сигналов. Им присвоены имена а и b соответственно.
Установлена проверка данных на корректность (ввод только 0 и 1).
В ячейку J19 введена формула:
=И (НЕ(C13); НЕ(D13)).
В ячейку J26 введена формула:
=И (НЕ(C13); D13).
В ячейку J32 введена формула:
=И (НЕ(D13); C13).
В ячейку J38 введена формула:
=И (C13; D13).
В ячейки J20, J27, J33, J39 введены формулы для преобразования значения «ИСТИНА» в 1, а значения «ЛОЖЬ» в 0.
Лист защищен, за исключением ячеек, в которые вводится входной код.
На рисунке 7.8 показан вариант, когда на входы схемы а и b поступают 0 и 0 соответственно. Сигнал 1 появляется лишь на выходе F1.
Подавая на входы другие комбинации 0 и 1, можно увидеть, что схема работает точно так, как описывает таблица истинности. Можно дополнительно ввести формулы для проверки сигналов на выходах любых элементов схемы.
Для большей наглядности на рабочем листе снята сетка, для чего выполнена команда Сервис, Параметры и на вкладке Вид снят флажок Сетка.
С помощью данной схемы легко показать (безусловно, упрощенно) применение дешифратора для расшифровки кодов операций. Примите соглашение, что код 00 соответствует сложению, 01 – вычитанию, 10 – делению, 11 – умножению. Вместо обозначений выходов Fl, F2, F3 и F4 сделайте подписи «Сложение», «Вычитание», «Деление», «Умножение». Тогда при появлении определенной комбинации входных сигналов кода операции на входе дешифратора будет показано, какую операцию следует выполнять, так как 1 появится лишь на выходе, соответствующем этой операции. Безусловно, следует сказать, что, например, дешифратор на 8 входов, имеющий полный набор выходных шин, сможет расшифровать 28 = 256 различных кодов операций.
7.3 Задания к работе
1. Выполнить логическое проектирование дешифратора на четыре входа и четыре выхода по индивидуальному заданию, приведённому в таблице 7.3 [15].
2. Для одной из предложенных булевых функции системы:
Написать СКНФ по данным таблицы 7.3.
Написать СДНФ по данным таблицы 7.3.
Минимизировать булеву функцию методом Квайна.
Минимизировать булеву функцию, используя карты Карно.
3. Сравнить результаты минимизации.
4. Выполнить логическое проектирование схемы, реализующей минимальную булеву функцию, используя элементы на два входа и один выход.
5. Для системы частично определённых булевых функций (таблица 7.2): минимизировать их описание, используя карты Карно.
Выполнить логическое проектирование схемы, реализующей минимизированную систему булевых функций, используя элементы на два входа и один выход.
Таблица 7.2 – Значение частично определённых функций fi (x1; x2; x3; x4)
| Аргумент | Индекс i логической функции fi (x1; x2; x3; x4) | ||||||||||||||||||||||
| x1 | x2 | x3 | x4 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | * | * | * | * |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | * | * | * | * | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | * | * | 1 | 1 |
| 1 | 1 | 0 | 0 | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | * |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 1 | 1 | 1 | * | * |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 1 | * | * | * |
| Аргмент | Индекс i логической функции fi (x1; x2; x3; x4) | ||||||||||||||||||||||
| x1 | x2 | x3 | x4 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 0 | * | * | * | * | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | * | * | * | * | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 |
| 0 | 0 | 1 | 1 | * | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * |
| 1 | 0 | 1 | 1 | * | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * |
| 0 | 1 | 1 | 1 | * | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * |
| 1 | 1 | 1 | 1 | * | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * |
| Аргумент | Индекс i логической функции fi (x1; x2; x3; x4) | ||||||||||||||||||||||
| x1 | x2 | x3 | x4 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 0 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 | * | * | * | * | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | * | * | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | * | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | * | * | 0 | 0 | 0 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | * | * | * | 0 | 0 | 0 | 0 | * | * | * | * | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| Таблица 7.3 | |
| Вариант | Логические функции |
| 1 | (f2; f1; f3; f4) |
| 2 | (f4; f3; f5; f6) |
| 3 | (f6; f5; f7; f8) |
| 4 | (f8; f7; f9; f10) |
| 5 | (f10; f9; f11; f12) |
| 6 | (f12; f11; f13; f14) |
| 7 | (f14; f13; f15; f16) |
| 8 | (f16; f15; f17; f18) |
| 9 | (f18; f17; f19; f20) |
| 10 | (f20; f19; f21; f22) |
| 11 | (f22; f21; f23; f24) |
| 12 | (f24; f23; f25; f26) |
| 13 | (f26; f25; f27; f28) |
| 14 | (f28; f27; f29; f30) |
| 15 | (f30; f29; f1; f2) |
| 16 | (f1; f3; f5; f7) |
| 17 | (f3; f5; f7; f9) |
| 18 | (f5; f7; f9; f11) |
| 19 | (f7; f9; f11; f13) |
| 20 | (f9; f11; f13; f15) |
| 21 | (f11; f13; f15; f17) |
| 22 | (f13; f15; f17; f19) |
| 23 | (f15; f17; f19; f21) |
| 24 | (f17; f19; f21; f23) |
| 25 | (f19; f21; f23; f25) |
| 26 | (f21; f23; f25; f27) |
| 27 | (f23; f25; f27; f29) |
| 28 | (f25; f27; f29; f1) |
| 29 | (f27; f29; f1; f3) |
| 30 | (f29; f1; f3; f5) |
7.4 Вопросы для самопроверки
1) Вычисление по алгоритму можно рассматривать как некоторый процесс. Перечислите три в принципе различных процесса.
2) Какими множествами описывается конечный автомат?
3) С рядом каких упрощающих предположений связано понятие конечного автомата?
4) Какие вопросы рассматриваются в теории автоматов?
5) Математической моделью каких устройств является конечный автомат?
6) Приведите пример конечного и бесконечного автоматов.
7) Дайте определение логического конечного автомата.
8) Какие Вы знаете стандартные обозначения элементов, используемые при составлении логических схем?
9) Какие классы логических конечных автоматов Вы знаете?
10) Что такое такт логического конечного автомата?
11) Приведите пример конечного автомата без памяти.
12) Приведите пример конечного автомата с памятью.
13) Приведите пример конечного автомата с обратной связью по выходу.
14) В чём заключается задача минимизации числа состояний автомата?
Список литературы
1 Р. Хаггарти Дискретная математика для программистов Москва: Техносфера, 2003. – 320 с.
2 Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. – М.: ФОРУМ: ИНФРА‑М, 2004. -128 с.
3 Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. Издание 2‑е, исправленное, – СПб.: Невский диалект, 2000 г. -240 с., ил.
4 Д. Кнут Искусство программирования для ЭВМ, т. 2, М.: Мир, 2000.
5 Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001. – 304 с.: ил.
6 Ламуатье Ж.‑П. Упражнения по программированию на Фортране IV, М.-Мир, 1978. – 168 с.: ил.
7 Светозарова Г.И. и др. Практикум по программированию на языке Бейсик: Учеб. пособие для вузов. – М.: Наука. Гл. ред. физ.-мат. лит., 1988. – 368 с.
8 Зеленяк О.П. Практикум по программированию на Turbo Pascal. Задачи, алгоритмы и решения – К.: Издательство «ДиаСофт», 2001. – 320 с.
9 Абрамов С.А., Гнездилова Г.Г. и др., Задачи по программированию, М., Наука. Гл. ред. физ.-мат. лит., 1988. – 224 с.
10 Абрамов С.А., Зима Е.В. Начала информатики. – М., Наука. Гл. ред. физ.-мат. лит., 1989. – 224 с.
11 Юркин А.Г. Задачник по программированию. – СПб.: Питер, 2002. – 192 с.
12 Хаггарти Дискретная математика для программистов Москва: Техносфера, 2006. 350 с.
13 Шапорев С.Д. Математическая логика. Курс лекций и практических занятий – СПб.: БХВ-Петербург, 2005. – 415 с. 6 ил.
14 Вирт А. Алгоритмы и структуры данных: Пер. с англ., М.: Мир, 1989 – 360 с., ил.
15 Шестаков А.А., Дружинина О.В. Дискретная математика. Часть I, II. М. РГОТУПС, 1998. Часть III М. РГОТУПС, 1999.
16 Могилёв А.В. и др. Информатика: Учеб. Пособие для студентов пед. вузов под ред. Хённера Е.К. – М., 1999. – 816 с.
17 Коршунов Ю.М. Математические основы кибернетики: Учебное пособие для вузов – М., Энергоатомиздат, 1987. – 496 с.: ил.
18 Евстигнеев В.А. Применение теории графов в программировании, М.,: Наука, 1985.
19 Оре О. Теория графов. – М.: Наука, 1980.
20 Справочник по математике для экономистов под общ. ред. Ермакова – М.: Финансы и статистика, 1988
21 Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2003. – 280 с. – (Серия «Высшее образование»)
22 Емельянов В.И., Воробьёв В.И., Тюрина Т.П., Основы программирования на Delphi: Учебное пособие для вузов; Под ред. В.М. Чёрненького. – М.: Высш. шк., 2005.-231 с.: ил.
23 Тюрина Т.П., Емельянов В.И. Дискретная математика (часть 1). Учебное пособие, НИ РХТУ им. Д.И. Менделеева, Новомосковск, 2004, 94 с.
24 Тюрина Т.П., Емельянов В.И. Дискретная математика (часть 2). Учебное пособие, НИ РХТУ им. Д.И. Менделеева, Новомосковск, 2004, 34 с.
25 Тюрина Т.П., Емельянов В.И. Дискретная математика (часть 3). Учебное пособие, НИ РХТУ им. Д.И. Менделеева, Новомосковск, 2005, 60 с.
Похожие работы
... Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным. Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики … Если универсальное множество состоит из n элементов, то число подмножеств = 2n. Если , состоящее из элементов E, не принадлежащих А, называется дополненным. Множество можно задать: ...
в и формальных систем является центральной в дисциплине. В настоящие время от нее возникли ответвления, например, разработка алгоритмических языков программирования.Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно ...
... которой были разработаны в последней четверти 19 века Георгом Кантором. Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания. Задание 1 Представить с помощью кругов Эйлера множественное выражение . Используя законы и свойства алгебры множеств, упростить заданное ...
элементы теории нечетких множеств можно применять для решения экономических задач в условиях неопределённости. 1. применение Логических функций 1.1 Применение методов дискретной математики в экономике При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются методы формализированного представления, являющегося предметом ...
0 комментариев