Файл: Основы бортовых вычислительных машин.pdf

38
Из множества наборов принято выделять нулевой и единичный – это соответственно наборы (0…0) (номер набора равен нулю) и (1…1)
(номер набора равен
1 2
−
n
). Два набора (
1 0
,...,
−
n
d
d
) и (
1 0
,...,
−
n
d
d
) на- зываются противоположными, если значения одноименных перемен- ных в наборах взаимно противоположны
)
1
(
i
i
d
d
−
=
. Два набора
(
1 0
0
−
n
d
d
) и (
1 0
1
−
n
d
d
), различающиеся значениями только од- ной переменной, называют соседними.
Таблица 1.2 Таблица наборов длины 3
Значение аргументов (набор)
Номер набора
D
2
d
1
d
0
d
0 0
0 0
1 0
0 1
2 0
1 0
3 0
1 1
4 1
0 0
5 1
0 1
6 1
1 0
7 1
1 1
Поскольку область определения и область значений функции конечны, то она может быть задана таблицей, в которой каждому на- бору с номером D сопоставляют значение функции
D
f . Такие табли- цы называют таблицами истинности (таблица 1.3).
Таблица 1.3 Пример задания различных функций таблицей истинно- сти
Пример функций
Номер
набора
Набор
0 1
d
d
Значения функции
)
(
0 1
d
d
f
)
(
*
0 1
d
d
f
)
(
0 1
d
d
ϕ
0 0 0 0
f
0 0
1 1
0 1 1
f
1 1
0 2
1 0 2
f
1
*
1 3
1 1 3
f
0
*
0
Значениям функций
1 2
0
−
n
f
f
можно сопоставить двоичный код
)
2
(
F
, такой что
)
2
(
F
1 2
1 0
−
=
n
f
f
f

39
Множество W наборов аргументов области определения функ- ции можно разбить на два подмножества
1
W и
0
W :
W =
1
W
∪
0
W , где
1
W и
0
W - подмножества наборов, на которых функция принимает значения 1 и 0 соответственно.
В частности, для
)
,
(
0 1
d
d
f
из таблицы 1.3 находим:
}
)}.
11
(
),
00
{(
,
)
10
(
),
01
{(
0 1
=
=
W
W
На части наборов функция может быть не определена, такие функции называют частичными и помечают звездочками. Наборы, на которых функция может принимать одновременно противоположные значения, называют запрещенными, значения функции на таких набо- рах также отмечают звездочками. Например, функция
)
,
(
*
0 1
d
d
f
не определена на наборах с номерами 2 и 3 (см. таблицу 1.3).
На практике частичные функции на запрещенных наборах дооп- ределяют для того, чтобы полученная функция имела более простую формулу, либо допускала бы более простую схемную реализацию.
Количество
n
N различных наборов длины п в точности равно количеству различных
n
2 - разрядных двоичных чисел, а количество
f
N различных функций – количеству различных наборов
n
N :
n
N =
n
2 ,
f
N =
n
n
N
2 2
2
=
Для п = 1 количество различных значений
n
N = 2, а
f
N = 2 2
= 4
(таблица 1.4). Как следует из таблицы 1.4, значения функций
0
F ,
3
F
- постоянны и не зависят от изменения входной переменной, а функ- ция
1
F совпадает с
0
d . Единственной нетривиальной функцией явля- ется функция
2
F (
0
d ) =
0
d
- инверсия переменной
0
d
Таблица 1.4 - Функции одной переменной
D
0
d
0
F
1
F
2
F
3
F
0 0
0 0
1 1
1 1
0 1
0 1
Для п = 2 количество различных наборов
n
N
= 4, а количество различных функций
f
N
= 2 4
= 16 (таблица 1.5).

40
Таблица 1.5- Логические функции двух переменных
На-
бор
F
0
F
1
F
2
F
3
F
4
F
5
F
6
F
7
F
8
D
d
1 d
0 0
1 0
d
d
∨
1 0
d
d
⊕
1 0
& d
d
1 0
& d
d
0 0 0 0 1
0 1
0 1
0 1
0 1 0 1 0 0
1 1
0 0
1 1
0 2 1 0 0 0
0 0
1 1
1 1
0 3 1 1 0 0
0 0
0 0
0 0
1
Продолжение таблицы 1.5
D Набор
F
9
F
10
F
11
F
12
F
13
F
14
F
15
d
1 d
0 1
0
d
d
⊕
1 0
d
d
→
1 0
d
d
∨
1 0 0 0
1 0
1 0
1 0
1 1 0 1
0 1
1 0
0 1
1 2 1 0
0 0
0 1
1 1
1 3 1 1
1 1
1 1
1 1
1
Количество различных функций с увеличением числа аргумен- тов растет чрезвычайно быстро, достаточно быстро растет и число различных наборов. Так для п = 2,
n
N = 4,
f
N = 16, но для п = 5 уже
n
N = 32,
f
N > 4000000000, поэтому табличное задание функций ста- новится громоздким, и функции предпочитают задавать алгебраиче- ски формулами через простейшие (элементарные) функции – опера- ции.
В качестве операций обычно выбирают следующие функции од- ного и двух аргументов (см. таблицы 1.4, 1.5): инверсия (операция
НЕ:
x
y
=
), конъюнкция (операция И:
0 1
& x
x
y
=
), дизъюнкция (опе- рация ИЛИ:
0 1
x
x
y
∨
=
), штрих Шеффера (операция И-НЕ:
0 1
& x
x
y
=
), стрелка Пирса (операция ИЛИ-НЕ:
0 1
x
x
y
∨
=
), сумма по модулю два (операция М2:
0 1
x
x
y
⊕
=
).

41
Инверсия, отрицание или операция НЕ реализуется инвертором или логическим элементом (ЛЭ) НЕ (рисунок 1.3,а).
Рисунок 1.3- Логические элементы
Конъюнкция, логическое произведение (умножение) или опера- ция И – это функция
y
x &
, совпадающая с арифметическим произве- дением двоичных переменных. Конъюнкцию обозначают также через
y
x
y
x
xy
∧
⋅
,
,
. Аргументы функции часто называют сомножителями.
Элемент, реализующий конъюнкцию, называют конъюнктором или логическим элементом И (см. рисунок 1.3,б). Говорят (см. табли- цу 1.5), что элемент И всегда пропускает нули со входов на выход
(действительно, если хоть один из сомножителей равен нулю, то и произведение равно нулю).
Дизъюнкция, логическая сумма (сложение) иначе операция ИЛИ
– это функция
y
x
∨
, которая равна нулю тогда и только тогда, когда все ее аргументы равны нулю. Аргументы дизъюнкции часто назы- вают слагаемыми. Элемент, реализующий дизъюнкцию, называют дизъюнктором или логическим элементом ИЛИ (см. рисунок 1.3,в).
Говорят, что элемент ИЛИ всегда пропускает единицы со входов на выход.
Сумма или операция сложения по модулю два – это функция
y
x
⊕
, которая равна единице тогда и только тогда, когда сумма зна- чений аргументов есть число нечетное. Элемент, реализующий эту функцию, называют сумматором по модулю два и отмечают симво- лом М2 (см. рисунок 1.3,г).

42
В математической логике широко используют функцию «им- пликация». Импликация – это функция
)
(
y
x
y
x
y
x
∨
=
→
→
, кото- рая равна единице, если выполняется неравенство
y
x
≤
(см. таблицу
1.5). Элемент, реализующий импликацию, называют импликатором
(см. рисунок 1.3,ж).
Функцию, противоположную конъюнкции, называют функцией штрих Шеффера или операцией И-НЕ и обозначают через
)
&
/
(
/
y
x
y
x
y
x
=
. Логический элемент, реализующий эту функцию, называют элементом Шеффера или элементом И-НЕ (см. рисунок
1.3,д).
Функцию, противоположную дизъюнкции, называют функцией стрелка Пирса или операцией ИЛИ-НЕ и обозначают через
)
(
y
x
y
x
y
x
∨
=
↑
↑
. Элемент, реализующий эту функцию, называют элементом Пирса или элементом ИЛИ-НЕ (см. рисунок 1.3,е). Все пе- речисленные функции за исключением функций инверсии и имплика- ции справедливы для любого числа (
>
n
2) аргументов.
1.4.2 Основные законы и правила алгебры логики
Основные тождества булевой алгебры, используемые для преоб- разования формул функций, получили название законов и правил.
После определения операций алгебры эти тождества являются след- ствиями этих определений и могут быть доказаны.
Законы коммутативности (переместительные) для дизъюнкции и конъюнкции
x
y
y
x
x
y
y
x
⋅
=
⋅
∨
=
∨
;
Законы ассоциативности (сочетательные) для дизъюнкции и конъюнкции
z
y
x
z
y
x
z
y
x
z
y
x
⋅
⋅
=
⋅
⋅
∨
∨
=
∨
∨
)
(
)
(
;
)
(
)
(
Первый и второй законы дистрибутивности (распределитель- ные)
)
(
)
(
)
(
;
)
(
z
х
y
x
z
y
x
z
х
y
x
z
y
x
∨
⋅
∨
=
⋅
∨
⋅
∨
⋅
=
∨
⋅
Законы идемпотентности (повторения) для дизъюнкции и конъ- юнкции
х
х
х
х
х
х
х
х
=
⋅
⋅
⋅
=
∨
∨
∨
;
Законы отрицания (инверсии)
х
х
х
х
х
х
=
=
⋅
=
∨
;
0
;
1

43
Законы двойственности или «правило де Моргана»
у
х
у
х
у
х
у
х
⋅
=
⋅
⋅
=
∨
;
Правило свертки
у
х
у
х
х
∨
=
⋅
∨
Правила поглощения
х
у
х
х
х
у
х
х
=
∨
⋅
=
⋅
∨
)
(
;
Правила полного склеивания
х
у
х
у
х
х
у
х
у
х
=
∨
⋅
∨
=
⋅
∨
⋅
)
(
)
(
;
Правило неполного склеивания
у
х
у
х
х
у
х
у
х
⋅
∨
⋅
∨
=
⋅
∨
⋅
Правило Порецкого
z
у
у
х
z
x
z
у
у
х
⋅
∨
⋅
=
⋅
∨
⋅
∨
⋅
Правила операций с константами
0 0
0 0
0 0
0 0
=
⋅
=
∨
=
⋅
x
x
x
=
⋅
=
∨
=
⋅
1 1
1 0
0 1
0
x
x
=
∨
=
∨
=
⋅
0 1
0 1
0 0
1 1
1 1
1 1
1 1
1
=
∨
=
∨
=
⋅
x
Доказательство большинства законов и правил алгебры логики очевидны.
Например,
)
1
(
0
)
(
)
(
;
1
)
(
;
1
)
1
(
x
y
x
y
x
x
y
x
x
y
y
y
x
y
x
x
x
y
x
y
x
x
x
y
y
x
y
x
y
x
x
x
y
x
y
x
x
=
∨
⋅
=
⋅
∨
=
=
∨
⋅
∨
=
⋅
∨
⋅
∨
⋅
∨
⋅
=
∨
⋅
∨
=
⋅
=
∨
⋅
=
⋅
∨
⋅
=
⋅
=
∨
⋅
=
⋅
∨
В других случаях доказательство тождества может быть выпол- нено сравнением значений правой и левой части тождества на всех возможных наборах переменных.
Например, необходимо доказать справедливость тождества:
у
х
у
х
⋅
=
∨
Зададим таблицей (таблица 1.6) значения выражений
у
х
∨
и
у
х
⋅
Значения обоих выражений (см. таблицу 1.6) на всех наборах значе- ний аргументов совпадают, следовательно, они задают одну и ту же функцию. Тождество доказано.

44
Таблица 1.6
Номер набора
Набор
)
(ху
у
х
∨
у
х
⋅
0 0 0 1
0 0
0
=
=
∨
1 1
1 0
0
=
⋅
=
⋅
1 0 1 0
1 1
0
=
=
∨
0 0
1 1
0
=
⋅
=
⋅
2 1 0 0
1 0
1
=
=
∨
0 1
0 0
1
=
⋅
=
⋅
3 1 1 0
1 1
1
=
=
∨
0 0
0 1
1
=
⋅
=
⋅
Логические выражения могут быть использованы и в обычной жизни.
Например. Три девушки – Аня (А), Валя (В), Клава (К) ходили на танцы в военное училище. Одна из них была в красном платье, другая – в синем, третья в белом. Курсант Иванов был в наряде и на танцы не попал, а его друзья (сослуживцы) Новиков, Петров и Сидо- ров после танцев сообщили:
Аня надела красное платье (Ак)
Валя – не красное ( к
В )
Клава – не синее ( с
К )
Стало известно, что только одно из сообщений истинно. Как оп- ределить в каком платье была каждая из девушек.
Решение: Из трех вариантов ответа порождаемых сообщением кКс
В
к
А
;
с
К
кВк
А
;
АкВкКс
:
с
К
к
В
Ак только один истинный, а именно
1
с
К
кВк
А
=
поэтому Аня была в синем, Валя была в крас- ном платье, Клава в белом.
1.4.3 Алгебры Жегалкина, Шеффера и Пирса
Помимо булевой алгебры, в теории функций алгебры логики и, особенно, в приложениях этой теории к задачам синтеза и анализа схем ЭВМ используют и другие алгебраические системы, в том числе алгебры Жегалкина, Шеффера и Пирса.
Кроме того, при выборе оптимальных схем по сложности, а так- же при переходе от одной системы элементов ЭВМ к другой возника- ет необходимость в использовании систем операций, принадлежащих различным алгебрам.
Алгебра Жегалкина – это множество всех функций, рассматри- ваемое совместно с операциями конъюнкция, сумма по модулю 2 и

45 константа единицы. В алгебре Жегалкина любую функцию рассмат- ривают (записывают) только в виде суперпозиции упомянутых выше операций.
Для алгебры Жегалкина действуют следующие законы: коммутативности
1 2
2 1
х
х
х
х
⊕
=
⊕
, ассоциативности
3 2
1 3
2 1
)
(
)
(
х
х
х
х
х
х
⊕
⊕
=
⊕
⊕
, дистрибутивности
3 1
2 1
3 2
1
)
(
х
х
х
х
х
х
х
⊕
=
⊕
Действия с константами:
0
;
1
=
⊕
=
⊕
х
х
х
х
Алгебра Шеффера – это множество всех функций, рассматри- ваемое совместно с операцией штрих Шеффера. Функция Шеффера не подчиняется закону ассоциативности (сочетательному)
/
)
/
(
)
/
/(
&
)
&
(
)
&
(
&
3 2
1 3
2 1
3 2
1 3
2 1
x
x
x
x
x
x
x
x
x
x
x
х
≠
≠
Доказательство этого высказывания может быть выполнено сравнением таблиц истинности логических выражений левой и пра- вой части неравенства (таблица 1.7).
Функция Шеффера подчиняется переместительному закону
(коммутативности):
1 2
2 1
1 2
2 1
/
/
&
&
x
x
x
x
x
x
x
х
=
=
Таблица 1.7 1
х
2
х
3
х
1
у
2
у
0 0
0 0
1 1
1 1
0 0
1 1
0 0
1 1
0 1
0 1
0 1
0 1
1 1
1 1
0 0
0 1
1 0
1 0
1 0
1 1

46
Функция Шеффера тождественно равна инверсии конъюнкций или дизъюнкции инверсии аргументов
n
n
n
x
x
x
x
x
x
х
х
х
∨
∨
∨
=
=
&
&
&
/
/
/
2 1
2 1
2 1
Действия с константами
&
/
1
&
1
/
1 0
&
0
/
1 1
1 1
1 1
1 1
1 1
x
x
x
x
x
x
x
x
x
x
=
=
=
=
=
=
Алгебра Пирса – это множество всех функций, рассматриваемое совместно с операцией стрелка Пирса.
Функция Пирса тождественно равна инверсии дизъюнкции ар- гументов или конъюнкции инверсий аргументов:
n
n
n
x
x
x
x
x
x
х
х
х
&
&
&
2 1
2 1
2 1
=
∨
∨
∨
=
↑
↑
↑
Для алгебры Пирса выполняется переместительный закон:
1 2
2 1
1 2
2 1
x
x
x
x
x
x
x
x
∨
=
∨
↑
=
↑
Также как и для алгебры Шеффера, сочетательный закон не вы- полняется. Действия с константами:
0 1
1 0
0
x
x
x
x
x
x
x
x
x
x
=
∨
=
↑
=
∨
=
↑
=
∨
=
↑
Алгебры Жегалкина, Шеффера и Пирса позволяют существенно упрощать решение задач проектирования логических схем ЭВМ на интегральных микросхемах, среди которых важное место занимают элементы Шеффера (И-НЕ) и Пирса (ИЛИ-НЕ), а также для реализа- ции контроля по четности используются сумматоры по модулю 2, со- ставляющие базис алгебры Жегалкина.
1.4.4 Элементарные конъюнкции и дизъюнкции
Функции в булевой алгебре записываются только в виде супер- позиции операций конъюнкции, дизъюнкции, инверсии, то есть в ви- де формул из символов операций И, ИЛИ, НЕ. При выполнении опе- раций в булевой алгебре следует соблюдать определенную очеред- ность. Сначала выполняют операции инверсии, затем операции конъ-

47 юнкции и в последнюю очередь операции дизъюнкции. При наличии скобок в первую очередь выполняются операции в скобках.
Пример. Вычислить значение функции
)
(
)
(
)
,
,
(
0 2
0 1
0 2
0 1
2
x
x
x
x
x
x
x
x
x
f
∨
∨
⋅
∨
⋅
=
на шестом наборе.
Решение. Для шестого набора
2
x = 1,
1
x =1,
0
x = 0. Подставив эти значения в формулу функции и выполнения последовательно опера- ции, получаем:
1 0
1 0
1 1
1 1
)
0 1
1
(
)
0 1
(
0
)
1 0
1
(
)
0
,
1
,
1
(
=
∨
=
∨
⋅
=
∨
⋅
∨
⋅
=
∨
∨
⋅
∨
⋅
=
f
Вычисляя значения функции на каждом наборе, можно легко по- строить таблицу истинности и тем самым осуществить переход от за- дания функции формулой к заданию ее таблицей.
Важную роль в булевой алгебре играют функции называемые элементарными конъюнкциями и элементарными дизъюнкциями.
Элементарная конъюнкция (ЭК) – это логическое произведение попарно различных отрицаемых или неотрицаемых аргументов (со- множителей).
Очевидно, ЭК равна единице тогда и только тогда, когда все ее сомножители с учетом признака отрицания равны единице. ЭК назы- вают полной относительно п аргументов или конституентой едини- цы, если в нее входит каждый из этих аргументов. Конституенту еди- ницы обозначают через
)
( j
K
, где
j
- номер единственного набора, на котором конституента равна единице. Если в наборе значение цифры двоичного кода набора равно 0, то переменная в записи конституенты инвертируется, если значение цифры – единица, то переменная запи- сывается без инверсии.
Пример,
1 1
0 3
)
3
(
0 1
2
=
⋅
⋅
=
j
x
x
x
K
На всех наборах, кроме j -го значение конституенты единицы
)
( j
K
=0.
Элементарная дизъюнкция (ЭД) – это логическая сумма отри- цаемых и неотрицаемых аргументов (слагаемых). Очевидно, ЭД равна нулю тогда и только тогда, когда каждый из ее слагаемых, с учетом признака отрицания, равен нулю.
ЭД, полную относительно п аргументов, называют конституен- той нуля и обозначают через
)
( j
М
, где
j - номер единственного на- бора аргументов, на котором конституента равна нулю. Если в j -м