47954 (Основы дискретной математики), страница 5

var i:byte;

P:string;

begin

for i:=1 to 16 do begin

if StringGrid2. Cells [5, i]='1' then begin

P:=StringGrid2. Cells [1, i]+StringGrid2. Cells [2, i]+

StringGrid2. Cells [3, i]+StringGrid2. Cells [4, i];

Label7. Caption:=Label7. Caption+' '+P;

end;

end;

for i:=1 to 16 do begin

if StringGrid2. Cells [6, i]='1' then begin

P:=StringGrid2. Cells [1, i]+StringGrid2. Cells [2, i]+

StringGrid2. Cells [3, i]+StringGrid2. Cells [4, i];

Label8. Caption:=Label8. Caption+' ' +P;

end;

end;

for i:=1 to 16 do begin

if StringGrid2. Cells [7, i]='1' then begin

P:=StringGrid2. Cells [1, i]+StringGrid2. Cells [2, i]+

StringGrid2. Cells [3, i]+StringGrid2. Cells [4, i];

Label9. Caption:=Label9. Caption+' '+P;

end;

end;

end;

end.

Рисунок 4.3 – Форма для примера 2

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

1) Чем отличается кортеж от обычного множества?

2) Приведите пример использования кортежей в программировании.

3. Какие операции над множествами Вы знаете?

4) Какой способ существует для графического изображения множеств?

5) Приведите пример универсального множества, которое используется в данной практической работе.

6) Какие операции (логические связки) из алгебры логики Вы знаете?

7) Возможно ли провести аналогию между операциями над множествами и логическими операциями?

8) Какое правило используется при построении СДНФ логической функции?

9) Какое правило используется при построении СКНФ логической функции?

10) Каков алгоритм перевода числа из десятичной системы счисления в двоичную систему счисления?

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

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

Практическая работа № 5. Исследование логических функций

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

Примечание: все теоретические сведения, необходимые для выполнения данной работы, содержатся в [25], в лекциях и в материалах семинарских занятий.

5.1 Задание к работе

1. Используя средства Excel и Delphi, построить таблицы истинности заданных логических функций, если требуется, то предварительно упростить выражения, используя законы алгебры логики и следствия из них.

2. Используя средства Excel и Delphi, построить арифметические модели заданных логических функций.

3. Представить заданные логические функции в виде СДНФ, СКНФ и СПНФ.

4. Построить логические функциональные схемы для заданных логических функций F1 и F2.

5. Сделать выводы.

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

5.2.1 Пример выполнения

Задание: Построить таблицу истинности, СДНФ, СКНФ, СПНФ и логические функциональные схемы для данных логических функций:

F1=

F2=

Код программы построения таблицы истинности логический функций:

Procedure TForml. ButtonlClick (Sender: TObject);

var xl, x2, x3:boolean; i:byte;

a1, a2, a3: string;

begin

Stringgridl. Cells [l, 0]:='xl';

Stringgridl. Cells [2,0]:='x2';

Stringgridl. Cells [3,0]:='x3';

Stringgrid1. Cells [4,0]:=F1';

Stringgridl. Cells [5,0]:='F2';

for i:=l to 8 do begin Stringgrid1. Cells [0, i]:=inttostr (i‑1);

if i<=4 then Stringgridl. Cells [l, i]:=’0’ else Stringgridl. Cells [l, i]:=1;

if (i<=2) or (i=5) or (i=6) then Stringgridl. Cells [2, i]:='0’ else Stringgridl. Cells [2, i]:=' 1';

if (i mod 2 >0) then Stringgridl. Cells [3, i]:='0' else Stringgridl. Cells [3, i]:=1; end;

for i:=l to 8 do begin

x1:=strtobool (Stringgrid 1. Cells [1, i]);

x2:=strtobool (Stringgridl. Cells [2, i]);

x3:=strtobool (Stringgridl. Cells [3, i]);

if (x2 and x3) or (not(xl) and not(x2)) or (x3 and not(xl)) then

Stringgridl. Cells [4, i]:=’1’ else Stringgridl. Cells [4, i]:='0';

if (x2 and x3) or (not(xl) and not(x2) and not(x3)) then Stringgridl. Cells [5, i]:=1 else Stringgridl. Cells [5, i]:='0'; end; end;

Рисунок 5.1 – Форма с результатами

МДНФ:

F1 =

F2 =

МКНФ:

F1 =

F2 =

_СПНФ:

F1 =

F2 =

Рисунок 5.2 – Логическая схема для МКНФ функции F1

5.2.2 Варианты заданий

1. Заданы логические функции: F1= 1 на наборах 0, 3 и

2. Заданы логические функции: F1= 1 на наборах 0, 1, 3 и

3. Заданы логические функции: F1= 1 на наборах 3, 7 и

4. Заданы логические функции: F1= 1 на наборах 0, 1, 3, 7 и

5. Заданы логические функции: F1= 1 на наборах 0,1,2,3,7 и

6. Заданы логические функции: F1= 1 на наборах 2,5,6 и

7. Заданы логические функции: F1= 1 на наборах 0, 2,5,7 и

8. Заданы логические функции: F1= 1 на наборах 0, 1,3 и

9. Заданы логические функции: F1= 1 на наборах 3,4,6,7 и

10. Заданы логические функции: и

11. Заданы логические функции: и

12. Заданы логические функции: и

13. Заданы логические функции: и

14. Заданы логические функции: и

15. Заданы логические функции: и

16. Заданы логические функции: и

17. Заданы логические функции: и

18. Заданы логические функции: и

19. Заданы логические функции: и

20. Заданы логические функции: и

21. Заданы логические функции: и

23. Заданы логические функции: и

24. Заданы логические функции: и

25. Заданы логические функции: и

26. Заданы логические функции: и

27. Заданы логические функции: и

28. Заданы логические функции: и

29. Заданы логические функции: и

30. Заданы логические функции: и

31. Заданы логические функции: и

32. Заданы логические функции: F1=1 на наборах 4,5,7 и

33. Заданы логические функции: F1=0 на наборах 2,4 и

34. Заданы логические функции: и

35. Заданы логические функции: и

36. Заданы логические функции: и

37. Заданы логические функции: и

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

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

2) В каких случаях, на Ваш взгляд, какие формы представления логических функций являются наиболее предпочтительными?

3) Изобразите общую схему таблицы истинности функции 4‑х переменных.

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

5) Какие логические функции есть в алгоритмическом языке Object Pascal?

6) Дайте определение логической функции многих переменных.

7) Приведите пример тождественно ложной логической функции. Можно ли для этой функции построить СДНФ?

8) Приведите пример тождественно истинной логической функции. Можно ли для этой функции построить СКНФ?

9) На основании каких замен можно построить арифметическую модель логической функции?

10) Перечислите законы алгебры логики.

11) Какие следствия из законов алгебры логики Вы знаете?

12) Назовите учёных, которые считаются основателями алгебры логики.

Практическая работа № 6. Изучение методов минимизации логических функций

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

6.1 Краткие теоретические сведения

Общая задача минимизации логических функций сводится к построению в базисе Буля функции, содержащей минимально возможное число двоичных переменных. Исходное выражение логической функции может быть представлено формулой в любом базисе. Поэтому на первом этапе осуществляется переход к нормальной форме формулы булевой функции, как правило, совершенной дизъюнктивной нормальной форме.

F 0={;; ^– ;;;;;} – сигнатура алгебры логики;

F 1={;;^–} – базис Буля;

F 2={;^–} – базис конъюнктивный;

F 3={;^–} – базис дизъюнктивный;

F 4={;; 1} – базис Жегалкина;

F 5={} – базис Вебба;

F 6={} – базис Шеффера;

F 7={;^–} – базис импликативный и т. д.

В таблицах 6.1–4 приведены формулы в некоторых базисах и для некоторых значений функции f (x1, x2).

Таблица 6.1 – Формулы, описывающие функции в базисах F0 и F5

fi	Формулы в базисах F 0 и F 5
f1	(x1x2)=(x1x2)(x1x2)
f6	(x1x2)=[(x1x1)(x2x2)](x1x2)
f7	(x1x2)=(x1x2)(x1x2)
f9	(x1x2)=[x1(x2x2)][x2(x1x1)]
f13	(x1x2)=[x2(x1x1)][x2(x1x1)]
f14	(x1x2)=[(x1x1)(x2x2)] [(x1x1)(x2x2)]

Таблица 6.2 – Формулы, описывающие функции в базисах F0 и F2

Fi	Формулы в базисах F 0 и F2
f6	(x1x2)=(x1x2)(x1x2)
f7	(x1x2)=(x1x2)
f8	(x1x2)=(x1x2)
f9	(x1x2)=(x1x2)(x1x2)
f13	(x1x2)=(x1x2)
f14	(x1x2)=(x1x2)

Таблица 6.3 – Формулы, описывающие функции в базисах F0 и F3

Fi	Формулы в базисах F 0 и F3
f6	(x1x2)=(x1x2)
f7	(x1x2)=(x1x2)(x1x2)
f8	(x1x2)=(x1x2)
f9	(x1x2)=(x1x2)(x1x2)
f13	(x1x2)=(x1x2)
f14	(x1x2)=(x1x2)

Таблица 6.4 – Формулы, описывающие функции в базисах F0 и F6

Fi	Формулы в базисах F 0 и F 6
f1	(x1x2)=(x1x2)(x1x2)
f6	(x1x2)=[x1(x2x2)][x2 (x1x1)]
f7	(x1x2)=(x1x2)(x1x2)
f8	(x1x2)=[(x1x1)(x2x2) (x2x2)]
f9	(x1x2)=[(x1x1)(x2x2)] (x1x2)]
f13	(x1x2)=(x1(x2x2).

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

6.2.1 Задание к работе

1. Минимизировать функции с помощью карт Карно или таблицы Куайна.

2. Используя средства Excel и Delphi, построить таблицы истинности заданных логических функций.

3. Сделать выводы.

6.2.2 Примеры выполнения

Пример 1.

Задание:

1. Минимизировать функции с помощью таблицы Куайна.

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

1 Минимизация с помощью таблицы Куайна:

Пусть функция F представлена в виде СДНФ

F1_СДНФ =

Таблица 6.5 – таблица Куайна

х1x2x3	001	101	110	111
0 0 1 1 – 1 1 1 –	1	1	1	1

Упростим F1_СДНФ, получим:

F1МДНФ =

Как мы видим, результат, полученный по таблице Куайна, совпадает с F1_МДНФ.

Рисунок 6.1 – Графический интерфейс

2 Процедура основного обработчика

procedure TForm1. BitBtn1Click (Sender: TObject);

Var i:byte;

x1, x2, x3:boolean;

begin

for i:=1 to 8 do begin

StringGrid1. Cells [0, i]:=IntToStr (i‑1);

If i<=4 then StringGrid1. Cells [1, i]:='0' else StringGrid1. Cells [1, i]:='1';

If (i=5) and (i<7)) then StringGrid1. Cells [2, i]:='0' else StringGrid1. Cells [2, i]:='1';

If (i mod 2>0) then StringGrid1. Cells [3, i]:='0' else StringGrid1. Cells [3, i]:='1';

If i<=4 then StringGrid1. Cells [4, i]:='1' else StringGrid1. Cells [4, i]:='0';

If (i=5) and (i<7)) then StringGrid1. Cells [5, i]:='1' else StringGrid1. Cells [5, i]:='0';

x1:=StrToBool (StringGrid1. Cells [1, i]);

x2:=StrToBool (StringGrid1. Cells [2, i]);

x3:=StrToBool (StringGrid1. Cells [3, i]);

if (not (x1) and not (x2) and x3) or (x1 and x3) or (x1 and x2)

then StringGrid1. Cells [6, i]:='1'

else StringGrid1. Cells [6, i]:='0';

end; end;

Пример 2. Пусть будут заданы номера наборов четырех переменных, на которых логическая функция принимает единичное значение: f (2,5,6,7,10,12,13,14)=1.

Выразим эту логическую функцию в СДНФ (символ конъюнкции писать не будем):

f (0010,0101, 0110, 0111, 1010, 1100, 1101, 1110) =

.

Таблица 6.6 – карта Карно для функции 4‑х переменных

	1100	1110	0110	0100
	1101	1111	0111	0101
	1001	1011	0011	0001
	1000	1010	0010	0000

Таблица 6.7 – заполненная карта

Карта Карно для четырех переменных представлена в виде таблицы 6.6. Каждая клетка карты соответствует конституенте. Заполненная карта представлена таблицы 6.7. Согласно закону склеивания, две смежные конституенты с единичными значениями всегда можно объединить для получения соответствующей импликанты. Причем смежными считаются и те, которые лежат на границах карты. Какие именно единицы требуется объединить для получения подходящей импликанты, легко определить визуально [5]. В соответствии с законом идемпотентности одна и та же единица таблицы 6.7 может склеиваться с двумя или тремя смежными единицами.

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)=(x1x2)
«И», конъюнкция f (x1; x2)=(x1x2)
«ИЛИ – НЕ», стрелка Пирса f (x1; x2)= (x1x2)=(x1x2)
«И – НЕ», штрих Шеффера f (x1; x2)= (x1x2)=(x1 x2)
«НЕ – ИЛИ», импликация f (x1; x2)=(x1x2)=(x1x2)
Сложение по mod 2 f (x1; x2)=(x1x2)

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

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

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

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

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

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

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

Среди логических узлов компьютера широкое распространение получили комбинационные автоматы (схемы). Такой автомат в общем случае представляются в виде многополюсника, имеющего 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.

Значение q1 функции виде СДНФ: .

Рисунок 7.3 – Образец выполнения работы

Упрощение выражения не требуется, пункт 3 порядка проектирования логических схем отсутствует.

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

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

Ячейки C14 и D14 отведены для ввода сравниваемых одноразрядных двоичных чисел. Им присвоены имена а и b соответственно.

Установлена проверка данных на корректность (ввод только 0 и 1). (рисунки 7.4 – 7.5.)

Рисунок 7.4 – Подсказка при вводе значений

Рисунок 7.5 – Сообщение об ошибке, в случае ввода некорректных данных

Для этого ячейки C14 и D14 выделены и выполнена команда Данные, Проверка. В диалоговом окне Проверка вводимых значений установить нужные параметры (рисунки 7.6, а-в).

Рисунок 7.6 а – Настройка проверки вводимых значений

Рисунок 7.6 б – Настройка проверки вводимых значений

Рисунок 7.6 в-Настройка проверки вводимых значений

В ячейку K22 введена формула:

=ЕСЛИ (ИЛИ(И (НЕ(C14); НЕ(D14)); И (C14; D14))=ИСТИНА; 1; 0).

Функция ЕСЛИ используется лишь для преобразования значения «ИСТИНА» в 1, а значения «ЛОЖЬ» в 0.

В ячейку K23 введена формула:

=ЕСЛИ (K22=1; «Числа равны»; «Числа не равны»).

Для того чтобы случайно что-то не испортить на листе, лист защищен, кроме ячеек, в которые вводятся сравниваемые числа. Эти ячейки выделены, и выполнена команда Формат, Ячейка, на вкладке Защита снят флажок Защищаемая ячейка. Затем выполнена команда Сервис, Защита, Защитить лист.

На рисунке 7.3 показан вариант, когда на входы схемы аi, и bi поступают два нуля, на выходе схемы имеем q1 (числа равны). Подавая на входы другие комбинации 0 и 1, можно увидеть, что схема работает точно так, как описывает таблица истинности. Можно дополнительно ввести формулы для проверки сигналов на выходах любых элементов схемы.

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

Признак равенства двухразрядных чисел q принимает значение 1, если выполняется попарно равенство всех разрядов двоичных чисел.

Для примера приведена двухразрядная схема (рисунок 7.7), что связано лишь с тем, что неудобно рассматривать работу схемы, если она выходит за пределы экрана. Двухразрядная схема состоит из двух одноразрядных схем.

Ячейки C7 и D7 отведены для поразрядного ввода первого числа, им присвоены имена a1 и а0 соответственно. Ячейки E7 и F7 отведены для ввода второго числа, им присвоены имена b1 и b0 соответственно.

В ячейку L7 введена формула для выдачи результата сравнения старших разрядов чисел:

=ИЛИ (И(НЕ(C7); НЕ(E7)); И (C7; E7)).

В ячейку L46 введена формула для выдачи результата сравнения младших разрядов чисел:

=ИЛИ (И(НЕ(F7); НЕ(D7)); И (F7; D7)).

В ячейку O22 введена формула для выдачи признака равенства чисел:

=ЕСЛИ (И(L46; L7)=ИСТИНА; 1; 0).

В ячейку O23 введена формула для выдачи сообщения о результате сравнения чисел:

=ЕСЛИ (O22=1; «Числа равны»; «Числа не равны»).

Рисунок 7.7 – Двухразрядная схема сравнения кодов

На рисунке 7.7 представлен результат сравнения чисел 10 и 11. На экране результат сравнения равен 0 и выдано сообщение «Числа не равны».

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 входов, имеющий полный набор выходных шин, сможет расшифровать 2⁸ = 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 с.