Основы дискретной математики (стр. 20 из 23)

6.3 Вопросы для самопроверки

1) Перечислите законы алгебры логики, которые наиболее часто используются при упрощении сложных логических выражений?

2) Перечислите правила (следствия), полученные из законов алгебры логики, которые обычно используются при упрощении сложных логических выражений?

3) Какое логическое выражение называется конституентой?

4) Какое логическое выражение называется импликантой?

5) В чём заключается задача минимизации логической функции? Основная операция, используемая при минимизации логической функции?

6) Как выглядит карта Карно для логической функции трёх переменных? Каков принцип её построения?

7) В чём заключается смысл метода карт Карно?

8) Если логическая функция не полностью определена, то каким образом можно задать формулу, описывающую данную функцию?

9) Требует ли метод Куайна этапа предварительной (аналитической) минимизации?

10) Каким образом строится таблица Куайна?

11) По какому принципу выбираются импликанты, образующие минимизированное представление логической функции в методе Куайна?

12) Кратко опишите принцип, на котором базируется метод сочетания индексов.

13) Перечислите известные Вам методы минимизации логических функций.

14) Обязательным ли является условие того, что исходное выражение, описывающее логическую функцию, которое требуется минимизировать, является дизъюнктивной нормальной формой?

15) Какой из методов минимизации логических функций, на Ваш взгляд, проще поддаётся алгоритмизации?

Практическая работа № 7. Моделирование работы узлов компьютера с помощью Еxcel

7.1 Теоретическая часть

В основе работы логических схем и устройств компьютера лежит специальный математический аппарат, называемый математической логикой [21].

Студентам предлагается при изучении данной темы не только спроектировать реальные узлы компьютера, но и смоделировать их работу с помощью электронной таблицы Excel. Это сделает изучение темы более интересным, полезным. Появится полное впечатление, что создана действующую модель реального узла компьютера.

Поскольку логическая функция осуществляет однозначное отображение множества наборов {(x1; x2;……; xn)}, в которых компоненты xi принимают значение из множества {0; 1}, в множество y={0; 1}, то для её реализации могут быть использованы переключательные или вентильные элементы. Переключательные элементы обладают двумя состояниями и двухсторонней проводимостью. Такими элементами являются выключатели, реле, ключи, коммутаторы и т. п. Вентильные элементы обладают также двумя состояниями, но, как правило, односторонней проводимостью. Такими элементами являются диоды, триоды, микросхемы и т. п. Интегральные микросхемы в одном корпусе реализуют большое число логических функций [13].

Чтобы упорядочить проектирование и разработку различных логических или переключательных устройств, разработаны международной и общероссийский стандарты для обозначения различных логических функций.

В таблице 7.1 приведены основные условные обозначения логических функций [2].

Схемы, формируемые вентильными элементами, называют комбинационными схемами. Если комбинационная схема реализует одну булеву функцию, то её называют одновыходовой комбинационной схемой, если несколько, то – многовыходовой комбинационной схемой.

Схема синтезируется из типовых логических элементов подобно тому, как сложная функция получается суперпозицией более простых функций.

Например, на рисунке 7.1 приведена комбинационная схема, реализующая функцию fmin.

Рисунок 7.1 – Комбинационная схема для fmin

Таблица 7.1 Стандартные обозначения логических элементов

Логическая функция(имя, значение)	обозначение поГОСТ 2.743–82
«ИЛИ», дизъюнкцияf (x1; x2)=(x1Úx2)
«И», конъюнкцияf (x1; x2)=(x1×x2)
«ИЛИ – НЕ», стрелка Пирсаf (x1; x2)= ÷ (x1Úx2)=(x1¯x2)
«И – НЕ», штрих Шеффераf (x1; x2)= ÷ (x1×x2)=(x1÷x2)
«НЕ – ИЛИ», импликацияf (x1; x2)=(x1Úx2)=(x1®x2)
Сложение по mod 2f (x1; x2)=(x1Åx2)

Понятие о синтезе логических схем

Логические устройства компьютера выполняют необходимые преобразования поступающей на вход цифровой информации. При синтезе таких устройств большое применение находит математический аппарат алгебры логики.

Обычно процесс синтеза логических устройств состоит из следующих основных этапов:

o На основании анализа функций, которые должны выполняться данным устройством, формируются логические условия его функционирования в виде соответствующей таблицы истинности.

o По построенной таблице истинности записывается аналитическое выражение логической функции в виде СДНФ или в СКНФ.

o Производится минимизация логической функции.

o По упрощенной логической формуле строится функциональная схема устройства, причем предпочтение отдается минимальному числу и однородности логических элементов.

Среди логических узлов компьютера широкое распространение получили комбинационные автоматы (схемы). Такой автомат в общем случае представляются в виде многополюсника, имеющего r входов т1, т2,…, тr и l выходов k1, k2,…, kl. Поступающая на вход автомата информация задается набором сигналов М (т1, т2,…, тr), образующим входное слово. При этом в любой дискретный момент времени t. совокупность выходных сигналов – выходное слово K (k1, k2,…, kl) – полностью определяется входным словом М, поступившим в тот же момент времени. При изменении набора входных сигналов М меняется набор выходных сигналов K. Таким образом, выходные сигналы комбинационного автомата полностью определяются входными сигналами и не зависят от внутреннего состояния автомата. Эти автоматы не имеют памяти. Именно о синтезе таких комбинационных автоматов (схем) и пойдет речь далее.

Построение компьютера ведется по следующей цепочке:

элементы → узлы → устройства.

Элементы по своему назначению делятся на следующие группы: логические; запоминающие; вспомогательные.

Нас интересуют логические элементы – на их основе строятся комбинационные схемы. К числу основных логических элементов, применяемых в ЭВМ и образующих функционально полный набор (т. е. такой набор элементов, с помощью которого может быть реализована любая сложная логическая функция), относятся логические элементы И (конъюнктор), ИЛИ (дизъюнктор), НЕ (инвертор). Хотя в ряде случаев некоторые логические выражения могут быть проще реализованы с помощью более сложных логических элементов, таких, как И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ, ограничимся использованием первой группы элементов.

Узел – это совокупность функционально связанных между собой элементов. Узлы компьютера по своему функциональному назначению делятся на следующие группы: регистры; дешифраторы; шифраторы; схемы сравнения кодов; электронные счетчики; сумматоры.

7.2 Практическая часть

Спроектируем некоторые из узлов. Вся работа от построения таблиц истинности соответствующего узла до вычерчивания его схемы будет представлена непосредственно в Excel. Все соответствующие этапы синтеза будут иметь на рабочих листах соответствующую нумерацию (см. выше). Для того чтобы не загромождать рабочий лист, в большинстве случаев не приводится минимизация функций, введены сразу упрощенные логические выражения.

Excel имеет в своем арсенале логические функции, представленные в окне Мастера функций, показанном на рисунке 7.2.

Рисунок 7.2 – Иллюстрация к использованию Мастера функций

В качестве аргументов логические функции И, ИЛИ, НЕ одинаково трактуют значения «0» и «ЛОЖЬ», 1 и «ИСТИНА», а в качестве результата выдают только значения «ЛОЖЬ» или «ИСТИНА». Поэтому для перехода от значений «ЛОЖЬ» и «ИСТИНА» к привычным 0 и 1 используется функция ЕСЛИ.

7.2.1 Схемы сравнения кодов

Организация сравнения двух двоичных чисел заключается в выработке признака равенства (равнозначности) или признака неравенства (неравнозначности) двух сравниваемых чисел. Ограничимся признаком равенства.

Одноразрядная схема сравнения кодов

Значение признака равенства q при сравнении одноразрядных переменных описывается таблицей истинности, представленной на рисунке 7.3.

В ячейку в E7 введена формула: =ЕСЛИ (C7=D7; 1; 0), которая затем скопирована в ячейки D8:D10.