Лекция 6. Основы теории логического проектирования ЭВМ.
План: 1 Основы булевой алгебры.
2. Логические функции.Основы булевой алгебры. Устройства, выполняющие различные операции над двойными числами, можно рассматривать, как функциональные преобразователи двойных чисел. Математический аппарат для анализа и синтеза устройств, производящих операции над двоичными цифрами, представляет алгебра логики, основоположником которой является английский математик Дж.Буль. В соответствии с этим алгебра логики стала именоваться булевой алгеброй.
Функция f, зависящая от п переменных называется булевой, если функция и любой из ее аргументов хi принимает значение только из множеств . Аргументы булевой функции называется булевыми. Булева функция задается одним из трех способов: матричным (табличным), геометрическим и аналитическим.
Матричная булева функция задается таблицами, называемыми таблицами истинности. Пример задания булевой функции приведен в таблице 6.1. В таблице 6.2 приведено табличное задание этой же функции, где вместо двоичных наборов приводится их десятичный эквивалент.
Таблица 6.1
х1, х2, х3 | f |
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
Таблица 6.2
Номер набора | f |
Графическом способом булева функция задается посредством п-мерного куба. В геометрическом смысле каждый двоичный набор есть п-мерный вектор, определяющий точку п-мерного пространства. Все множество наборов, на которых определена функция п переменных, представляется вершинами п-мерного куба. Отмечая точками вершины куба, в которых функция, принимая единичные (либо нулевые) значения, получим геометрические пространственные функции. К примеру, булева функция, заданная таблице 6.1, геометрически представляется 3-мерным кубом:
|
Геометрическое представление булевой функции
Аналитически булева функция задается формулами, построенными на основе операций булевой алгебры.
Булевы функции от одной и двух переменных.Булеву функцию п переменных называют не полностью определенной или частичной, если она определена не на всех двоичных наборах длины п. Существует не более чем 22 п различных булевых функций п переменных.
Наиболее употребимыми булевыми функциями одной и двух переменных являются следующие. Функций одной переменной представлены в табл.6.3
Таблица 6.3
х | f0 f1 f2 f3 |
0 0 1 1 0 1 0 1 |
где: f0(x) =0-тождественный НОМ (константа 0);
f1(x)=х-тождественная функция;
f2(x)= отрицание х (инверсия);
f3(x)=1-тождественая единица (константа 1).
В таблице 6.4 приведены булевы функции двух переменных.
Таблица 6.4
x1, x2 | f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 |
0 0 0 1 1 0 1 1 |
На практике наиболее часто употребляются следующие функции:
f0(x1,х2)=0-тождественный ноль (константа 0),
f1(x1,х2)= x1∙х2= x1&х2= x1Ùх2. Эту функцию часто называют логическим произведением или логическим умножением;
f3(x1,х2)= x1 – повторение х1;
f5(x1,х2)= x2-повторение x2;
f6(x1,х2)= x1 +x2-сложение по модулю 2 или сумма mod 2;
f7(x1,х2)= x1Úх2 умножение или логическое сложение;
f8(x1,х2)= x1∙х2-фнукция Вебба (стрелка Пирса)
f9(x1,х2)= x1 х2-эквивалентность;
f13(x1,х2)- x1®х2 импликация;
f14(x1,х2)- штрих Шеффера;
f15(x1,х2)=1-тождественная единица (константа 1)
Для булевой алгебры справедливы три аксиомы:
Закон коммутативности- xÚy= yÚх, x∙y=y ∙х;
Закон ассоциативности – (xÚy)Úz=xÚ(yÚz), (x∙y) ∙z=x∙(y ∙z);
Закон дистрибутивности - x∙(yÚz)=x∙yÚх∙z, xÚy ∙z=(xÚy) ∙(хÚz);
Для упрощения формул используются специальные соотношения. В частности:
Литература:
1.Пятибратов А.П. и др. Вычислительные машины системы и сети. – М.:Статистика, 1991-400с. .
2.Тынымбаев С.Т. Вычислительные машины, системы, комплексы и сети. Учебник для вузов. 2-ое издание. – Алматы:: Рауан, 1997-366с.
3.Таненбаум Э. Архитектура компьютера. СПб.: Питер, 2003 – 704с : ил.