Лекция 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-мерным кубом:

X1

 

Геометрическое представление булевой функции

 

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

Булевы функции от одной и двух переменных. Булеву функцию п переменных называют не полностью определенной или частичной, если она определена не на всех двоичных наборах длины п. Существует не более чем 2^{2 п} различных булевых функций п переменных.

Наиболее употребимыми булевыми функциями одной и двух переменных являются следующие. Функций одной переменной представлены в табл.6.3

 

Таблица 6.3

х	f0 f1 f2 f3
	0 0 1 1 0 1 0 1

 

 

где: f₀(x) =0-тождественный НОМ (константа 0);

f₁(x)=х-тождественная функция;

f₂(x)= отрицание х (инверсия);

f₃(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

 

На практике наиболее часто употребляются следующие функции:

f₀(x₁,х₂)=0-тождественный ноль (константа 0),

f₁(x₁,х₂)= x₁∙х₂= x₁&х₂= x₁Ùх₂. Эту функцию часто называют логическим произведением или логическим умножением;

f₃(x₁,х₂)= x₁ – повторение х₁;

f₅(x₁,х₂)= x₂-повторение x₂;

f₆(x₁,х₂)= x₁ +x₂-сложение по модулю 2 или сумма mod 2;

f₇(x₁,х₂)= x₁Úх₂ умножение или логическое сложение;

f₈(x₁,х₂)= x₁∙х₂-фнукция Вебба (стрелка Пирса)

f₉(x₁,х₂)= x₁ х₂-эквивалентность;

f₁₃(x₁,х₂)- x₁®х₂ импликация;

f₁₄(x₁,х₂)- штрих Шеффера;

f₁₅(x₁,х₂)=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с: ил.