ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16670
Скачиваний: 202
81
тины есть ложь. Запись (4.10): отрицание лжи есть истина. При помощи опера-
ции инверсии образуется новое высказывание:
.
A
Читается: «не A».
В дальнейшем будем различать прямые переменные и инверсные: прямые
переменные не содержат знаков инверсии, а в записи инверсных переменных
всегда ставится знак отрицания. Если к прямой переменной применить опера-
цию инверсии, то получим инверсную переменную. Если же операцию отрица-
ния применить к инверсной переменной, то получим прямую переменную (за-
кон инволюции):
.
A
A =
При помощи двоичных переменных, булевых констант и логических опе-
раций И, ИЛИ, НЕ строятся булевы формулы. Понятие формулы в пределах
операций дизъюнкции, конъюнкции и инверсии определяется следующим обра-
зом [4; 18]:
1) константы 0 и 1, а также двоичные переменные A, B, C, … являются
булевыми формулами;
2) если A – формула, то и A – формула;
3) если P и Q – булевы формулы, то и P + Q и PQ – формулы;
4) любые другие последовательности перечисленных знаков формулами
не являются.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1. Укажите номера формул из следующих выражений.
1)
;
A 2)
;
B
A
A +
3)
1 0;
A + +
4)
;
A
A
+ = + 5)
.
A A
⋅ +
2.
Какие из следующих выражений не являются булевыми
формулами?
1)
1 0;
A
+ + 2)
1 1
;
AA
B
+ − +
3) 1 + 1 + 0; 4) CCC +
⋅
C;
5) 1 + + 0.
3.
В нижеприведённом списке укажите номера булевых фор-
мул:
1) A + B + + C;
2) AB + AB + CС;
3)
;
AA
A
+
4) A – B + C;
5) + AB+ C.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
82
4.3 Нормальные формы булевых выражений
Булевы формулы могут быть представлены дизъюнкцией конъюнкций
переменных или констант (прямых или инверсных) либо конъюнкцией дизъ-
юнкций тех же переменных и констант. Такие формы называются нормальны-
ми.
Булева формула, представленная в виде дизъюнкции выражений, каждое
из которых есть константа, или отдельный аргумент (с инверсиями или без ин-
версий), или конъюнкция аргументов, где те или иные аргументы также могут
содержать знаки инверсии, называется дизъюнктивной нормальной формой
(ДНФ). Например, выражения
D
A
E
D
B
A
D
C
AB
+
+
+
⋅
+
+
+
0
1
;
1
;
представлены в ДНФ, а формула вида
)
(
D
C
B
A
+
+
к ДНФ не относится, так как второе слагаемое
)
(
D
C
B
+
не является ни
константой, ни отдельным аргументом, ни конъюнкцией переменных.
Булева формула, записанная в виде конъюнкции выражений, каждое из
которых представляет собой либо константу, либо отдельный аргумент (с ин-
версией или без инверсии), либо дизъюнкцию некоторых аргументов (также с
инверсиями или без инверсий), называется конъюнктивной нормальной формой
(КНФ). Например, выражения
(
)(
);
(
1
)
+
+ +
+ +
A
B C
A
D
AB C
E
записаны в КНФ, а формула
)
)(
(
E
D
C
B
A
+
+
конъюнктивной нормальной фор-
мой не является, поскольку в первой паре скобок содержится конъюнкция
.
C
B
Выражения вида 1 и 0, а также всякая формула, представленная отдель-
ным аргументом или его инверсией, либо дизъюнкцией или конъюнкцией не-
скольких прямых или инверсных переменных, одновременно входят в класс
ДНФ и КНФ. Например:
.
;
;
0
;
;
;
1
;
;
F
E
C
A
F
E
C
B
ABC
D
C
B
D
A
+
+
+
+
+
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Укажите номера формул, относящихся к классу ДНФ.
1)
;
+
A B
2)
;
D
3)
(1
) ;
+ A B
4)
(
) ;
+
+
B
C
D E
5)
;
ABC
6)
0;
7)
1 0 1.
+ +
2.
Укажите номера формул, представленных в ДНФ.
83
1)
)
(
C
B
A
A
+
+
; 2)
ABA
AB
+
; 3)
CA
B +
; 4)
)
(
A
A
A
A
+
+
;
5)
A
AA
+ .
3.
Какие формулы из следующего списка представлены в
КНФ?
1)
1
;
+ B
2)
;
D
3)
(1
) ;
+ A B
4)
(
) ;
+
+
B
C
D E
5)
;
ABC
6)
0;
7)
1 0 1.
+ +
4.
Укажите номера формул, представленных в КНФ.
1)
D
C
AB +
; 2)
C
B
A
+
+
; 3)
E
BC
A
+
+
; 4)
)
(
R
P
Q
P
+
+
;
5) A + A .
5.
Какие формулы из следующего списка относятся к обоим
классам ДНФ и КНФ?
1) ;
B 2)
(1
);
+
D
C 3)
(
) ;
+
C
A B
4)
1 (
) 0;
+
+
⋅
C
D
5)
;
ABC
6) 1 1;
⋅ 7)
(
0 1) 0.
+ + ⋅
A
6.
Укажите номера формул, относящихся одновременно к
ДНФ и КНФ.
1) A; 2) AA; 3) AB; 4)
A
A +
; 5) A + BC.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
4.4 Вычисление значений булевых формул
При помощи аксиом дизъюнкции, конъюнкции и инверсии можно найти
значение любой булевой формулы. При этом в ДНФ первыми выполняются
операции инверсии, если они стоят только над переменными. После инверсии
выполняются операции конъюнкции, а затем – дизъюнкции.
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 4.1
· · · · · · · · · · · · · · · · · · · · · · ·
На наборе 0110 найти значение формулы
.
C
B
A
BCD
B
A
+
+
(4.11)
Запишем переменные под знаками заданного набора, расположив буквы в
алфавитном порядке. Тогда значения переменных примут вид:
A = 0, B = 1, C = 1, D = 0.
Подставим эти значения в формулу (4.11):
.
1
1
0
0
1
1
1
0
⋅
⋅
+
⋅
⋅
+
⋅
Выполнив операции инверсии, а затем умножения и сложения, получим:
.
1
0
0
1
1
0
0
0
1
1
1
1
=
+
+
=
⋅
⋅
+
⋅
⋅
+
⋅
84
Таким образом, на наборе 0110 формула (4.11) принимает значение 1.
В КНФ первыми выполняются также операции инверсии, а после них –
дизъюнкции и затем – конъюнкции.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 4.2
· · · · · · · · · · · · · · · · · · · · · · ·
На наборе 1110 найти значение формулы
(
)(
)(
).
+ +
+ +
+ +
A
B
C B
C
D A C
D
Подставим в эту формулу значения переменных согласно набору 1110:
A = 1, B = 1, C = 1, D = 0.
В результате получаем:
.
0
1
0
1
)
0
1
1
)(
0
1
1
)(
1
1
1
(
=
⋅
⋅
=
+
+
+
+
+
+
На наборе 1110 заданная формула принимает нулевое значение.
В общем случае знаки инверсии в булевых формулах могут стоять не
только над отдельными переменными, но и над более сложными выражениями.
Такие знаки условимся называть длинными инверсиями. При вычислении зна-
чений формул, содержащих длинные знаки инверсии, необходимо учитывать
одну особенность: если в формуле имеется «длинная» инверсия, то сначала
необходимо найти значение выражения, находящегося под длинной чертой.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · ·
Пример 4.3
· · · · · · · · · · · · · · · · · · · · · · ·
На наборе 11100 найти значение формулы
.
E A
BCD
ABC
+
+
Согласно набору 11100 значения переменных равны:
A = 1, B = 1, C = 1, D = 0, E = 0.
Эти значения подставляем в заданную формулу:
.
1
1
1
0
1
1
1
0
⋅
⋅
+
⋅
⋅
+
⋅
Под длинной чертой выражение равно 1, следовательно:
.
0
1
1
1
1
0
=
⋅
⋅
+
⋅
Таким образом, на наборе 11100 заданное выражение равно нулю.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Различают три типа булевых формул в зависимости от результатов их
вычисления на всех возможных наборах значений переменных:
85
1) тождественно ложные. Эти формулы принимают нулевое значение
на всех наборах значений переменных [8; 11; 33]. В [20] их называют противо-
речиями, а в [22] – невыполнимыми. Например, выражение
)
)(
)(
)(
)(
(
C
B
A
C
B
C
B
C
A
B
A
+
+
+
+
+
+
на всех наборах равно нулю, следовательно, оно описывает тождественно лож-
ное высказывание;
2) тождественно истинные (общезначимые, тавтологии [22; 30]). В [20;
33] их называют логическими законами. Они описывают утверждения, прини-
мающие единичное значение на всех наборах значений переменных [9; 11; 33].
Примером может служить выражение вида
.
B
BC
C
A
C
B
A
+
+
+
Оно равно единице на всех восьми наборах значений переменных A, B, C,
т. е. это выражение есть тавтология;
3) выполнимые формулы – это такие формулы, которые равны нулю не на
всех наборах значений переменных [25]. Например, выражение
D
C
B
A
D
C
AB
BCD
A
+
+
79
равно единице на трёх наборах: 0101, 0111, 1101, а на остальных тринадцати
наборах равно нулю, следовательно, оно входит в класс выполнимых формул.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Найдите значения выражений:
1)
0 0 0 0 1 1 0;
⋅ + ⋅ + + ⋅
1 1 1 1 1 1 1 0 1 0;
⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅ ⋅
1 1 1 0 1 0 1 1;
⋅ ⋅ + ⋅ + ⋅ ⋅
2)
1
1
0
0
1
1
1
0
0
⋅
⋅
+
⋅
⋅
+
⋅
⋅
;
0 1 1 1 1 0 0 0 1;
⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅
1 1 0 0 1 0 0 1 1;
⋅ ⋅ + ⋅ ⋅ + ⋅ ⋅
3)
1
0
0
1
0
1
0
⋅
+
⋅
+
⋅
⋅
;
1
0
0
1
0
0
1
⋅
+
⋅
⋅
+
⋅
;
0
1
1
0
1
0
1
⋅
+
⋅
+
⋅
⋅
;
4)
1
1
0
0
1
1
1
0
0
⋅
⋅
+
⋅
⋅
+
⋅
⋅
;
1
0
0
0
1
1
1
1
0
⋅
⋅
+
⋅
⋅
+
⋅
⋅
;
1
1
0
0
1
0
0
1
1
⋅
⋅
+
⋅
⋅
+
⋅
⋅
.
2.
Найдите значения выражений:
1)
BD
C
B
A
+
на наборах 0010, 1010, 1110, 0110;
2)
D
C
B
A
+
+
на наборах 1011, 0010, 1000, 0100;
3)
D
B
A +
на наборах 0110, 1011, 1100, 0111;
4)
)
)(
(
C
A
B
A
+
+
на наборах 0101, 1001, 0001, 0111.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·