ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2020
Просмотров: 179
Скачиваний: 1
Семинар 6. Общие принципы вычислений
6.1
Основные понятия алгебры логики
Алгебра логики
—
раздел математической логики, изучающий
высказывания
,
рассматриваемые со стороны их логических (истина или ложь) значений, и логические
операции над ними.
Алгебра логики возникла в середине 19 века в работах Дж. Буля и была развита Ч. Пирсом
(C.S. Peirs), П.С. Порецким, Б. Расселом (B. Russel), Д. Гильбертом (D. Hilbert) и др.
Высказыванием называются предложения, которые могут быть охарактеризованы
понятием
—
истина или ложь
. Использование логических связок "и", "или", "если
. . .
то",
"эквивалентно", частица "не" и т.д. позволяет строить новые, более сложные, высказывания
из заданных. Истинность или ложность сложных высказываний зависит от истинности или
ложности исходных высказываний. Для обозначения истинности вводятся тождественные
символы:
Истина
≡
И
≡
True
≡
T
≡
1
.
(6.1)
Для обозначения ложности высказывания вводятся следующие тождественные символы
Ложь
≡
Л
≡
False
≡
F
≡
0
.
(6.2)
Соответственно для логических связок приняты следующие обозначения:
"и" (конъюнкция)
≡
&
≡ ∧ ≡
AND
≡ ∩
"или" (дизъюнкция)
≡ ∨ ≡
OR
"если
. . .
то" (импликация)
≡→
"эквивалентность"
≡∼
"отрицание"
≡
черта над высказыванием
≡ ¬ ≡
NOT
(6.3)
Связки и частицы "не"
рассматриваются в алгебре логики как операции над
величинами, принимающие два значения 0 и 1, а высказывания с произвольными
высказываниями и связками образуют формулы. При этом высказывания, образующие
формулу, рассматриваются в качестве переменных, а связки в качестве функций. Формулы
A
и
B
называются равными
(
A
=
B
)
, если они реализуют равные функции.
Для
задания
функций
алгебры
логики,
используются
таблицы,
содержащие
все наборы значений переменных и значений функций: такие таблицы называются
таблицами истинности
. Пример таблицы истинности для NOT, AND, OR, импликации
и эквивалентности приведены ниже
a
b
NOT
a
a
∧
b
a
∨
b
a
→
b
a
∼
b
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
0
1
0
0
1
1
0
1
1
1
1
Сложные формулы в алгебре логики могут быть преобразованы. Для преобразования
формул основную роль играют следующие законы:
47
–
закон коммутативности
a
∨
b
=
b
∨
a
;
a
∧
b
=
b
∧
a
;
(6.4)
–
закон ассоциативности
(
a
∧
b
)
∧
c
=
a
∧
(
b
∧
c
);
(
a
∨
b
)
∨
c
=
a
∨
(
b
∨
c
);
(6.5)
–
закон поглощения
a
∧
(
a
∨
b
) =
a
;
a
∨
(
a
∧
b
) =
a
;
(6.6)
–
закон дистрибутивности
a
∧
(
b
∨
c
) = (
a
∧
b
)
∨
(
a
∧
z
);
a
∨
(
b
∧
c
) = (
a
∨
b
)
∧
(
a
∨
c
);
(6.7)
–
закон противоречия
a
∧
a
= 0;
(6.8)
–
закон исключения третьего
a
∨
a
= 1;
(6.9)
a
→
b
=
a
∨
b
;
a
∼
b
= (
a
∧
b
)
∨
(
a
∧
b
)
(6.10)
Множество всех формул, в построении которых учавствуют переменные высказывания,
символы
∧
,
∨
,
→
,
∼
,
¬
, константы 0 и 1 называются
языком
над данными символами.
Равенство (6.4)
–
(6.10) означают, что для всякой формулы в языке над
∧
,
∨
,
→
,
∼
,
¬
,
0
,
1
найдется равная ей формула в языке над
∧
,
∨
,
¬
,
0
,
1
.
Алгебра логики развивалась под влиянием прикладных задач, среди которых приложение
к теории электрических схем играет самое важное значение. В алгебре логики ставится задача
минимизации функции приводя заданную функцию к функции имеющей наименьшее число
сомножителей, то есть минимальную сложность. Такие функции называются минимальными.
В языке над
∧
,
∨
,
→
,
∼
,
0
,
1
,
⊕
, где
⊕
–
используется для обозначения сложения по модулю
2 устанавливаются следующие соотношения:
a
∨
b
= ((
a
∧
b
) +
a
) +
b
(6.11)
a
→
b
=
a
∧
b
;
a
∼
b
= (
a
+
b
) + 1;
(6.12)
a
+
b
= (
a
∧
b
)
∨
(
a
∧
b
);
1 =
a
∨
a.
(6.13)
48
6.2
Классические универсальные машины и логические гейты
Универсальный компьютер
—
это логическое устройство, реализованное в виде сложной
сети взаимосвязанных примитивных (основных) элементов. Для классического компьютера
можно представить, что взаимосвязь элементов осуществляется идеальными проводниками,
передающими одно из двух стандартных напряжений, представляющих локально один бит
информации
—
1 или 0. Сами примитивные элементы
—
или
гейты
реализуют функции
преобразования, использующиеся в алгебре логики.
Классический компьютер осуществляет вычисление функций по заданным входным
n
-битам, располагая результат вычисления в
m
-битах. Функция с
m
-битами значений
эквивалентна
m
-функциям, каждая из которых имеет однобитовое значение в качестве
результата. Вычисление каждой из этих функций может быть сведено к последовательности
элементарных логический операций (гейтов).
Символически гейты и биты, "соединенные проводами", изображаются рисунками.
Так на рисунке представлен примитивный элемент сети, в которой над битом выполняется
логическая операция отрицания (NOT)
На рисунке указано, что бит
a
проходит через гейт NOT, который переворачивает бит,
превращая 1 в 0 и 0 в 1. Линии до и после гейта NOT служат для переноса бита к гейту и
удаление его после преобразования. Данные линии (провода) могут представлять как перенос
бита из одной точки пространства в другую, так и развитие состояния бита во времени. Гейт
NOT имеет один входной бит и один бит на выходе. Фактически, выходной бит вычисляет
функцию
f
(
a
) = 1
⊕
a
.
При построении сети предполагается, что сеть не содержит замкнутых петель.
Имеется много иных элементарных логических гейтов, полезных для организации
процесса вычисления, которые имеют два бита в качестве исходных данных и один
результирующий бит. Геометрические изображения, алгебраические формулы в бинарной
арифметике и таблицы истинности, которых приведены ниже
а.
AND
–
гейт
;
c
≡
a
∧
b
=
a
·
b
a
b
c
0
0
0
0
1
0
1
0
0
1
1
1
б.
OR-гейт
;
c
≡
a
∨
b
=
a
+
b
−
a
·
b
a
b
c
0
0
0
0
1
1
1
0
1
1
1
1
49
в.
XOR-гейт
(исключающее или
≡
"или", но не оба)
;
c
≡
a XOR b
=
a
(1
−
b
) +
b
(1
−
a
)
a
b
c
0
0
0
0
1
1
1
0
1
1
1
0
г.
NAND-гейт
≡
(NOT AND-гейт)
;
c
= 1
−
a
·
b
a
b
c
0
0
1
0
1
1
1
0
1
1
1
0
д.
NOR-гейт
≡
(NOT OR-гейт)
;
c
= (1
−
a
)(1
−
b
)
a
b
c
0
0
1
0
1
0
1
0
0
1
1
0
Любое вычисление может быть записано в терминах булевского выражения, и любое
булевское выражение может быть построено из фиксированного набора логических гейтов.
Такой набор (например, AND, OR или NOT) называется универсальным. В действительности
можно обойтись только двумя гейтами, такими как AND и NOT, или OR и NOT, или AND и
XOR. Устройство, которое может исполнить произвольные комбинации логических гейтов из
универсального набора, является универсальным компьютером.
Хотя приведенные выше гейты достаточны для математического аппарата алгебры логики,
они недостаточны для реализации практической вычислительной машины. В реальном
устройстве требуются еще два гейта FANOUT (разворачивание) и ERASE (стирание).
FANOUT-гейт дублирует входной бит, а гейт ERASE
–
уничтожает входной бит. По сути
FANOUT-гейт требуется для организации вычислений, а ERASE для очистки ячеек памяти
компьютера.
В некоторых приложениях используется, помимо того, гейт EXCHANGE
a
b
a
0
b
0
0
0
0
0
0
1
1
0
1
0
0
1
1
1
1
1
50
Для примера рассмотрим цепь, которая суммирует два целых числа, имеющих длину
n
-
бит. Базовым элементом в этой цепи является "ячейка" сети известная как полусумматор
(half-adder
≡
HA). На вход полусумматора подаются два бита
x
и
y
, а на выходе получается
сумма битов
x
⊕
y
по модулю
2
и перенос (carry) бита в состоянии 1, если
x
и
y
оба 1, или 0 во
всех остальных случаях.
Схема сети полусумматора имеет вид:
Таблица истинности полусумматора:
x
y
перенос
x
⊕
y
двоичное число
0
0
0
0
00
0
1
0
1
01
1
0
0
1
01
1
1
1
0
10
Перенос бита позволяет перейти на следующий разряд, если складывается
1 + 1 = 0
. Каскад
из 2-х полусумматоров (HA) образует полный сумматор (full-adder
≡
FA)
Полный сумматор имеет три бита на входе, где
x
,
y
–
данные для сложения,
c
–
перенос бита с
предыдущего этапа вычислений и два бита на выходе. Один выходной бит является суммой по
модулю 2
x
⊕
y
⊕
c
всех трех входящих битов, а второй выходной бит
c
0
–
есть перенос бита,
который равен 1, если два или больше входных бита равны 1, и равен 0 в противном случае.
Таблица истинности полного сумматора:
x
y
c
x
y
c
x
y
c
перенос
x
⊕
y
⊕
c
число
0
0
0
0
0
0
0
0
0
0
0
00
0
1
0
0
1
0
0
0
1
0
1
01
1
0
0
0
1
0
0
0
1
0
1
01
1
1
0
1
0
0
1
0
0
1
0
10
0
0
1
0
0
1
0
0
1
0
1
01
0
1
1
0
1
1
0
1
0
1
0
10
1
0
1
0
1
1
0
1
0
1
0
10
1
1
1
1
0
1
1
0
1
1
1
11
51