Информатика и программирование - Основы информатики, страница 9
Описание файла
Документ из архива "Информатика и программирование - Основы информатики", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "информатика" в общих файлах.
Онлайн просмотр документа "Информатика и программирование - Основы информатики"
Текст 9 страницы из документа "Информатика и программирование - Основы информатики"
f(1, 2, 4, 5, 6, 7) = 1.
Во втором случае перечисляются все наборы, на которых функция равна 0:
f(0, 3) = 0.
Все эти представления эквивалентны и описывают одну функцию. □
Правило 6.14. (переход от табличного к аналитическому представлению функции в ДНФ) Необходимо в тех строках таблицы истинности, где функция равна 1, выписать набор переменных и соединить их конъюнкцией. Причем, если переменная в наборе равна 0, то к переменной добавляется отрицание. Конъюнкции переменных соединить дизъюнкцией.
Пример 6.27. Функция задана таблично (табл. 6 .9).
Таблица 6.9. Таблица истинности некоторой функции
| Номер набора | X | Y | Z | f(X, Y, Z) |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 0 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 |
Записать функцию в аналитическом представлении ДНФ и числовом представлении.
Решение. Выпишем те наборы переменных, на которых функция принимает значение 1, и запишем их в виде конъюнкции переменных:
набор 3: X = 0, Y = 1, Z = 1 
YZ;
набор 6: X = 1, Y = 1, Z = 0 XY
;
набор 7: X = 1, Y = 1, Z = 1 XYZ.
Соединим полученные конъюнкции переменных дизъюнкцией и получим аналитическое представление функции:
f(X, Y, Z) = YZ + XY + XYZ.
Функция принимает значение 1 на наборах 3, 6, 7 и значение 0 на наборах 0, 1, 2, 4, 5, поэтому в числовом представлении функция будет иметь вид
f(3, 6, 7) = 1.
f(0, 1, 2, 4, 5) = 0. □
Правило 6.15. (переход от табличного к аналитическому представлению функции в виде КНФ) Необходимо в тех строках таблицы истинности, где функция равна 0, выписать набор переменных и соединить их дизъюнкцией. Причем, если переменная в наборе равна 1, то к переменной добавляется отрицание. Дизъюнкции переменных соединить конъюнкцией.
Пример 6.28. Функцию, заданную таблично в примере 6 .27, записать в аналитическом представлении КНФ.
Решение. Выпишем наборы, на которых функция принимает значение 0 и преобразуем их в дизъюнкции переменных:
набор 0: X = 0, Y = 0, Z = 0 X + Y + Z;
набор 1: X = 0, Y = 0, Z = 1 X + Y + ;
набор 2: X = 0, Y = 1, Z = 0 X + 
+ Z;
набор 4: X = 1, Y = 0, Z = 0 + Y + Z;
набор 5: X = 1, Y = 0, Z = 1 + Y + .
Запишем функцию в виде КНФ (произведения сумм):
f(X, Y, Z) = (X + Y + Z)(X + Y + )(X + + Z)
( + Y + Z)( + Y + ). □
6.3.2.Способы перевода логических функций
из одного базиса в другой
Рассмотрим способы перевода функции из одного базиса в другие.
Правило 6.16. (переход от булевого базиса к базису NOR) Алгоритм перехода включает следующие этапы.
1. Упростить функцию и преобразовать ее к произведению сумм произведений и т. д. по формуле ( 6 .0), причем в каждой сумме или произведении должно быть по два аргумента. Если невозможно свести формулу, где в каждой операции по два аргумента, то использовать следующие преобразования:
X+Y+Z=(X+Y+Z)(X+Y+Z)=((X+Y)(X+Y)+Z)((X+Y)(X+Y)+Z)=
=
;
XYZ=(XY+XY)Z=
=
=
.
2. Преобразовать конъюнкции по формуле (6.0):
XY=
.
3. Преобразовать отрицание над переменными по формуле (6.0):
=
.
4. Заменить полученные операции стрелкой Пирса по формуле (6.0):
=XY.
Пример 6.29. Привести упрощенную функцию из примера 6 .26 к базису NOR.
Решение. Приведем формулу к произведению сумм и т. д. по формуле ( 6 .0):
f(X, Y, Z) = X + Y + Z = (X + Y + )(X + Y + Z) =
= ((X + Y)(X + ) + )((X + Y)(X + ) + Z).
Преобразуем конъюнкции:
((X + Y)(X + ) + )((X + Y)(X + ) + Z) =
= 
.
Преобразуем отрицания над переменными:
=
= 
.
Заменим операции стрелкой Пирса:
=
= ((X Y)(X (Z Z)) (Y Y)) ((X Y)(X (Z Z)) Z).
Формула приведена к базису NOR. □
Правило 6.17. (переход от булевого базиса к базису NAND) Алгоритм перехода включает следующие этапы.
1. Упростить функцию и преобразовать ее к сумме произведений сумм и т. д. по формуле ( 6 .0), причем в каждой сумме или произведении должно быть по два аргумента. Если невозможно свести формулу, где в каждой операции по два аргумента, то использовать следующие преобразования:
X+Y+Z=(X+Y)(X+Y)+Z=
=
;
XYZ=XYZ+XYZ=(XY+XY)Z+(XY+XY)Z=
=
.
2. Преобразовать дизъюнкции формуле
X+Y=
. (6.0)
3. Преобразовать отрицание над переменными по формуле:
=
. (6.0)
4. Заменить полученные операции штрихом Шеффера по формуле:
=XY. (6.0)
Пример 6.30. Привести функцию из примера 6 .27 к базису NAND.
Решение. Упростим выражение и приведем к виду суммы произведений и т. д.:
f(X, Y, Z) = YZ + XY + XYZ = Y( Z + X + XZ) =
= Y( Z + X( + Z)) = Y( Z + X) = Y(Z + X) = YZ + YX.
Преобразуем дизъюнкции:
YZ + YX = 
.
Отрицания над переменными отсутствуют, поэтому приведем операции к штриху Шеффера:
= (Y Z) (Y X).
Формула приведена к базису NAND. □
6.3.3.Минимизация логических функций
Одна и та же функция может иметь несколько аналитических представлений. Функция называется минимальной, если ее аналитическое представление имеет минимальное количество слагаемых и минимальное количество переменных в каждом слагаемом. Таким образом, минимизация справедлива только для аналитического представления логической функции в виде ДНФ.
Существует несколько методов минимизации логических функций. Наиболее простым и эффективным является метод Блейка.
Правило 6.18. (метод Блейка) Алгоритм метода состоит из трех этапов:
1) привести формулу к ДНФ;
2) для всевозможных пар слагаемых, если это возможно, применить операцию склеивания:
Y + XZ = Y + XZ + YZ;
3) к исходным и полученным слагаемым применить операцию поглощения:
X + XY = X.
Пример 6.31. Минимизировать функцию из примера 6 .27.
Решение. Исходная функция имеет вид:
f(X, Y, Z) = YZ + XY + XYZ.
Выполним последовательно этапы метода Блейка. Применим операцию склеивания для всевозможных пар слагаемых:
YZ + XY = YZ + XY + YZY = YZ + XY + 0;
YZ + XYZ = YZ + XYZ + YZ;
YZ + XY = YZ + XY + XY;
XY + YZ = XY + YZ + YZ.
В результате выполнения второго этапа получено следующее выражение:
f(X, Y, Z) = YZ + XY + XYZ + YZ + XY.
Применим операцию поглощения:
f(X, Y, Z) = YZ + XY.
Таким образом, функция минимизирована. Сравните полученный результат с упрощением функции в примере 6 .30, то есть минимизация может быть достигнута преобразованиями над функцией. □
6.4.Логические элементы и логические схемы
Основным логическим операциям, используемым в ЭВМ, соответствуют следующие логические элементы, каждый из которых имеет два входа (слева) и один выход (справа).
| |
|
|
|
| дизъюнкция | конъюнкция | стрелка Пирса | штрих Шеффера |
Для отрицания отдельный элемент применяется редко, так как отрицание (обозначается кружком) может быть помещено как на входы
| | F = A |
так и на выходы логических элементов
|
| F = |
Логические элементы реализуются аппаратно с помощью транзисторов, резисторов и т. п. Значению «истина» соответствует наличие напряжения на входах и на выходах, значению «ложь» – его отсутствие.
Логические элементы соединяются между собой и подсоединяются к входам, соответствующим переменным X, Y, Z, и образуют логическую схему. Как правило, логическая схема имеет один выход.
