ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16672
Скачиваний: 202
86
4.5 Основные теоремы алгебры логики
Сначала приведём список теорем одной переменной:
;
0
A
A
=
+
(4.12)
;
1
1 =
+
A
(4.13)
;
A
A
A
=
+
(4.14)
;
1
=
+ A
A
(4.15)
;
0
0 =
⋅
A
(4.16)
;
1 A
A
=
⋅
(4.17)
;
A
A
A
=
⋅
(4.18)
;
0
=
⋅ A
A
(4.19)
.
A
A =
(4.20)
При их доказательстве можно пользоваться аксиомами (4.1)–(4.10). Дока-
жем, например, теорему (4.15). Если принять A = 0, то получим 0 + 1 = 1, что
соответствует аксиоме (4.2). Если принять A = 1, то получим 1 + 0 = 1, что соот-
ветствует аксиоме (4.3). В обоих случаях отклонений от аксиом не наблюдает-
ся, следовательно, теорема (4.15) верна.
Из теорем большего числа переменных рассмотрим теоремы поглощения,
склеивания и де Моргана. Первые две теоремы позволяют уменьшить число букв в
записи формул. От применения теоремы де Моргана число букв не меняется.
Формы теоремы поглощения:
;
A
AB
A
=
+
(4.21)
.
)
(
A
B
A
A
=
+
(4.22)
В эти выражения входят по две переменные, а после упрощения осталось по
одной. Переменная B является фиктивной: если её заменить нулём или единицей,
то равенства (4.21) и (4.22) не изменятся.
Докажем теорему (4.21). Вынесем за скобки букву A:
).
1
(
B
A
AB
A
+
=
+
Согласно теореме (4.13), 1 + B = 1, следовательно,
.
1
)
1
(
A
A
B
A
=
⋅
=
+
Чтобы доказать теорему (4.22), раскроем скобки:
.
)
(
AB
A
AB
A
A
B
A
A
+
=
+
⋅
=
+
Получилось выражение, только что доказанное.
Рассмотрим несколько примеров на применение теоремы поглощения:
(
1)
;
+
=
+ =
ABC
BC
ВС A
BC
(1
)
;
+
=
+
=
ABC
AВCD
ABC
D
ABC
87
(1
)
;
+
+
= +
+
= +
=
A
AB
ABC
A
AB
C
A
AB
A
(
)
(1
)
;
+ +
= +
+
=
+ +
=
A A
B CD
A
AB
ACD
A
B
CD
A
(
)
(
1
)
.
+ +
=
+ +
=
+ +
=
B A
B CD
AB
B
BCD
B A
CD
B
Теорема склеивания также имеет две формы – дизъюнктивную и конъ-
юнктивную:
;
A
B
A
AB
=
+
(4.23)
.
)
)(
(
A
B
A
B
A
=
+
+
(4.24)
Докажем теорему (4.23):
,
1
)
(
A
A
B
B
A
B
A
AB
=
⋅
=
+
=
+
поскольку согласно теоремам (4.15) и (4.17)
1;
1
.
+ =
⋅ =
B
B
A
A
Чтобы доказать теорему (4.24), сначала раскроем скобки:
.
)
)(
(
B
B
AB
B
A
A
B
A
B
A
+
+
+
=
+
+
По теореме (4.19)
,
0
=
B
B
следовательно,
+
+
+
=
A
AB
AB
BB
.
= +
+
A
AB
AB
Согласно теореме поглощения,
.
)
1
(
A
B
B
A
AB
B
A
A
=
+
+
=
+
+
Приведём три примера на применение теоремы склеивания:
;
)
(
A
B
B
A
B
A
B
A
=
+
=
+
;
)
(
AC
B
B
AC
ABC
C
B
A
=
+
=
+
.
)
)(
(
AB
C
C
ABC
C
AB
AB
C
AB
C
AB
=
+
+
+
=
+
+
Две формы имеет и теорема де Моргана. Первая читается следующим
образом: инверсия конъюнкции есть дизъюнкция инверсий:
;
B
A
AB
+
=
.
ABC
A
B
C
= + +
(4.25)
Вторая: инверсия дизъюнкции есть конъюнкция инверсий:
;
B
A
B
A
=
+
.
C
B
A
C
B
A
=
+
+
(4.26)
Формулы (4.25) и (4.26) применимы и к более сложным выражениям:
(
)(
)(
)
;
+
+
+ +
=
+
+
A
B B
C A C
D
AB
BC
ACD
(
).
+ +
=
=
+
A
B CD
AB CD
AB C
D
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Примените теорему поглощения:
B
A
A +
;
.
KP
K +
88
2.
Упростите выражения, применив теорему поглощения:
1)
;
PQRST
SPQ
PQ
+
+
3)
;
ABC
ABCD
D
ABC
+
+
2)
;
XZV
XZ
XYZ
+
+
4)
.
D
C
B
A
AD
CD
B
A
+
+
3.
Упростите:
1)
;
)
(
AB
D
C
B
D
C
B
+
5)
;
C
B
A
C
B
A
+
+
+
2)
;
)
)(
(
D
C
B
A
C
A
B
C
B
A
+
+
+
+
6)
;
C
B
A
C
B
A
+
+
+
+
+
3)
C
B
D
C
B
C
A
C
B
A
+
+
+
+
+
; 7)
;
)
(
D
C
B
A
B
A
+
+
+
4)
;
+
+
+
+
A
AB
ABC
BC
B
8)
.
)
(
A
ABC
AB
A
+
+
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
4.6 Понятие булевой функции
В наиболее общем случае функция (лат. functio – исполнение, соответ-
ствие, отображение) – это некоторое правило (закон), в соответствии с которым
каждому элементу множества Х, представляющего собой область значений не-
зависимого переменного х, ставится в соответствие определенный элемент
множества F, под которым понимается область значений зависимого перемен-
ного f. В случае булевых функций
X = F = {0,1}.
В [14; 20] такие функции называются переключательными. Правилом,
при помощи которого задается булева функция, может служить любая булева
формула, например:
.
)
,
,
(
C
B
A
C
B
A
f
+
=
Это аналитический (алгебраический) способ задания булевой функции.
Символом f здесь обозначена функция, а буквами A, B, C – двоичные перемен-
ные, называемые логическими аргументами. Аргументы – независимые пере-
менные, они могут принимать одно из двух значений – либо 0, либо 1. Функция
же f зависимая переменная. Её значение полностью определяется значениями
переменных и логическими связями между ними.
Существует ещё один способ задания булевых функций – табличный.
В общем случае таблица содержит
n
2 строк, где n – число аргументов функции.
В таблице перечисляются все возможные наборы значений аргументов, и для
каждого набора указывается значение функции. Такую таблицу называют таб-
лицей соответствия (истинности). Если функция задана аналитически, то для
89
неё всегда можно построить таблицу истинности. Поясним это на примере
функции
.
C
B
A
C
A
B
A
f
+
+
=
Функция зависит от трёх аргументов A, B, C. Следовательно, в таблице
соответствия предусматриваем три колонки для значений аргументов и одну
колонку для значений функции (табл. 4.1). Для удобства работы с таблицей
слева от колонки A расположим вспомогательную колонку, обозначив её «№».
В ней будем записывать десятичные эквиваленты трёхразрядных наборов зна-
чений аргументов, записанных в строках таблицы.
Таблица 4.1
№ A B C f
0 0 0 0 0
1 0 0 1 1
2 0 1 0 1
3 0 1 1 1
4 1 0 0 1
5 1 0 1 1
6 1 1 0 0
7 1 1 1 0
Так как в данном случае n = 3, то в таблице содержится
8
2
3
=
строк. За-
полняем таблицу. В строке с номером 000 записано:
A = B = C = 0.
Значение функции на этом наборе равно нулю. В колонке f на пересече-
нии со строкой 000 записываем нуль.
Следующий набор 001:
.
1
,
0
=
=
=
C
B
A
На этом наборе:
.
1
1
0
0
1
0
0
0
=
⋅
⋅
+
⋅
+
⋅
=
f
Следовательно, в строке с номером 001 на пересечении с колонкой f запи-
сываем единицу. Аналогично вычисляем значения функции на всех остальных
наборах.
Для булевых выражений характерна двойственность, суть которой в том,
что всякой булевой формуле f можно поставить в соответствие формулу f
1
, по-
90
лучаемую заменой в f всех знаков дизъюнкции знаками конъюнкции и всех зна-
ков конъюнкции знаками дизъюнкции. Например, для выражения
F
ABE
ABD
C
B
A
f
+
+
=
двойственной является формула
).
)(
)(
(
1
F
E
B
A
D
B
A
C
B
A
f
+
+
+
+
+
+
+
=
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Функцию
C
B
B
A
C
B
A
f
+
=
)
,
,
(
представьте в виде таблицы
соответствия. Сколько единиц содержится в колонке f ? Сколько
нулей в колонке f ?
2.
Функция f = AB представлена в виде таблицы соответствия
трёх аргументов. Сколько единиц и сколько нулей содержится в
колонке f ?
3.
В таблице соответствия пяти аргументов колонка f содер-
жит 19 единиц. Сколько нулей в колонке f
?
4.
Найдите десятичные эквиваленты наборов, на которых
:
1
)
,
,
(
=
C
B
A
f
1)
;
)
,
,
(
C
AB
BC
A
C
B
A
f
+
=
3)
;
)
,
,
(
C
B
A
BC
C
B
A
f
+
=
2)
;
)
,
,
(
C
B
A
AB
C
B
A
f
+
=
4)
.
)
,
,
(
AC
AB
C
B
A
f
+
=
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
4.7 Совершенная дизъюнктивная нормальная форма
Существуют булевы функции, равные единице только на одном наборе
значений аргументов. В таблице соответствия эта единица может находиться в
любой строке, следовательно, таких функций существует
n
2 , столько же,
сколько строк в таблице истинности. Каждая из этих функций состоит из одной
конъюнкции n аргументов, инверсных, неинверсных или их сочетаний, причём
распределение инверсий находится в строгом соответствии с двоичной записью
набора. Например, пусть функция, зависящая от аргументов A, B, C, D, равна
единице на наборе 0101, а на всех остальных наборах равна нулю. Представим
функцию в аналитической форме. Для этого запишем аргументы в алфавитном
порядке, а под ними – цифры набора:
1
0
1
0
D
C
B
A