ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.04.2021
Просмотров: 1346
Скачиваний: 1
8
2.2.
Найти число булевых функций от
n
переменных, которые на любой
паре соседних наборов принимают противоположные значения.
2.3.
Функция
f
(
x
1
, x
2
, x
3
)
определяется следующим образом: она равна
1 либо при
x
1
= 1
, либо если переменные
x
2
, x
3
принимают разные
значения, а значение переменной
x
1
меньше значения переменной
x
3
; в противном случае функция обращается в нуль. Построить таб-
лицу функции
f
(
x
1
, x
2
, x
3
)
и выписать наборы множества
N
f
.
2.4.
Функция
f
(
x
1
, x
2
, x
3
, x
4
)
задается так: она равна нулю только на
таких наборах
(
σ
1
, σ
2
, σ
3
, σ
4
)
, для которых справедливо неравенство
σ
1
+
σ
2
> σ
3
+2
σ
4
. Построить таблицу и выписать наборы множества
N
f
этой функции.
2.5.
Выяснить, какие из нижеперечисленных выражений являются фор-
мулами:
1)
x
↔
yz
;
5)
(
x
→
(
y
∧
(
¬
x
)))
;
2)
(
x
∧
)
¬
y
;
6)
(
x
⊕
y
)
¬
z
;
3)
xy
←
z
;
7)
(
¬
x
→
z
)
y
;
4)
(
y
→
(
xz
))
;
8)
((
x
⊕
y
)
→
z
)
∨
x
.
2.6.
Выяснить, какими способами можно расставить скобки в выраже-
нии
A
, чтобы всякий раз получалась формула, если:
1)
A
=
¬
x
→
y
∧
x
;
2)
A
=
x
∧
y
∧ ¬¬
z
∨
x
;
3)
A
=
x
→ ¬
y
→
z
∧ ¬
x
.
2.7.
Выяснить, какие из нижепривиденных формул являются тожде-
ственно истинными, тождественно ложными, выполнимыми или
опровержимыми:
1)
((
x
∨
¯
y
)
z
→
((
x
↔
z
)
⊕
y
))
xyz
;
2)
((
x
⊕
y
)
↔
z
)(
x
→
yz
)
;
3)
(
x
→
y
)
→
((
x
∨
z
)
→
(
y
∨
z
))
;
4)
((
x
∨
¯
y
)
↓
(
x
⊕
¯
y
))
⊕ ¬
((
x
→
¯
y
)
→
(¯
x
∨
y
))
;
5)
((
z
↔
y
)
→
xy
)
↔
¯
z
;
6)
(
y
¯
z
→
x
)
∧
(
y
↔
(
x
∧
z
))
;
7)
yz
→
(
xz
↔
(¯
x
∨
¯
y
))
;
8)
(¯
yx
→
z
)
↔
(
yx
∨
¯
z
)
;
9)
((¯
zy
→
x
)
↔
yx
)
∨
¯
z
;
9
10)
(¯
yz
→
x
)
∧
(
z
↔
(
x
∨
z
))
.
2.8.
Эквивалентны ли формулы
U
и
B
:
1)
U
=
¬
((
x
→
y
)
∨
(
x
→
z
)
y
)
,
B
=
x
¯
y
(¯
y
→
x
¯
z
)
;
2)
U
= ((
x
⊕
y
)
→
(
x
∨
y
))((¯
x
→
y
)
→
(
x
⊕
y
))
,
B
=
x
|
y
;
3)
U
= ((
x
⊕
y
)
→
(¯
x
∨
¯
y
))
,
B
= (
x
↔
y
)
∨
(
¬
(
xy
))
;
4)
U
= (
x
→
y
)
→
z,
B
=
x
→
(
y
→
z
)
;
5)
U
=
x
↔
z,
B
= ((
x
∨
y
)
∨
z
)
→
((
x
∨
y
)(
x
∨
z
))
;
6)
U
= (
x
→
y
)
→
(
x
¯
y
⊕
(
x
↔
¯
y
))
,
B
=
x
¯
y
∨
y
¯
x
;
7)
U
= (
x
|
y
→
z
)
∨
(
x
→
z
)
,
B
= (
x
→
y
)
∨
z
;
8)
U
= ((¯
z
∨
y
)
↓
x
)
↔
¯
xz,
B
=
xyz
⊕
yz
⊕
1
;
9)
U
= ((
z
↔
y
)
→
xy
)
↔
¯
z,
B
=
z
→
xy
;
10)
U
= (
xyz
→
¯
y
)
↔
(
xy
∨
¯
z
)
,
B
=
y
→
(
x
→
z
)
.
§3.
Основные эквивалентности алгебры высказываний.
Эквивалентное преобразование формул
При оперировании с функциями алгебры логики (булевыми функ-
циями) часто бывают полезными следующие эквивалентности, которые
в дальнейшем будем называть основными эквивалентностями:
x
◦
y
=
y
◦
x
(коммутативность связки
◦
, где символ
◦
является
общим обозначением для связок
∧
,
∨
,
⊕
,
↔
,
→
,
|
,
↓
);
(
x
◦
y
)
◦
z
=
x
◦
(
y
◦
z
)
(ассоциативность связки
◦
, где
◦
является
общим обозначением для связок
∧
,
∨
,
⊕
,
↔
);
x
∧
y
= ¯
x
∨
¯
y,
x
∨
y
= ¯
x
∧
¯
y
(правила де Моргана);
x
∨
xy
=
x,
x
(
x
∨
y
) =
x
(правила поглощения);
x
(
y
∨
z
) =
xy
∨
xz
(дистрибутивность конъюнкции относительно
дизъюнкции);
x
∨
yz
= (
x
∨
y
)(
x
∨
z
)
(дистрибутивность дизъюнкции относительно
конъюнкции);
x
(
y
⊕
z
) =
xy
⊕
xz
(дистрибутивность конъюнкции относительно
сложения по модулю 2);
x
∧
¯
x
=
x
∧
0 =
x
⊕
x
= 0;
x
∨
¯
x
=
x
∨
1 =
x
↔
x
= 1;
¯
x
=
x
⊕
1
,
x
↔
y
=
x
⊕
y
⊕
1;
x
⊕
y
=
x
¯
y
∨
¯
xy,
x
→
y
=
xy
⊕
x
⊕
1
.
10
Рассмотрим пример эквивалентного преобразования формулы с
применением приведенных в этом параграфе основных эквивалентно-
стей:
(
xy
↔
z
)
→
z
=
xy
↔
z
∨
z
= (
xy
⊕
z
)
∨
z
=
xy
¯
z
∨
xyz
∨
z
=
xy
¯
z
∨
z
=
= (
xy
∨
z
)(¯
z
∨
z
) =
xy
∨
z.
Упражнения
3.1.
Проверить справедливы ли следующие соотношения, построив таб-
лицы истинности:
1)
x
∨
(
y
↔
z
) = (
x
∨
y
)
↔
(
x
∨
z
)
;
2)
x
∨
(
y
⊕
z
) = (
x
∨
y
)
⊕
(
x
∨
z
)
;
3)
x
→
(
y
∨
z
) = (
x
→
y
)
∨
(
x
→
z
)
;
4)
x
→
(
y
∧
z
) = (
x
→
y
)
∧
(
x
→
z
)
;
5)
x
→
(
y
↔
z
) = (
x
→
y
)
↔
(
x
→
z
)
;
6)
x
∧
(
y
↔
z
) =
xy
↔
xz
;
7)
x
(
y
⊕
z
) =
xy
⊕
xz
;
8)
x
⊕
(
y
→
z
) = (
x
⊕
y
)
→
(
x
⊕
z
)
;
9)
x
→
(
y
→
z
) = (
x
→
y
)
→
(
x
→
z
)
;
10)
(
x
⊕
y
)(
x
⊕
¯
y
) = 0
.
3.2.
Используя основные равносильности, доказать эквивалентность
формул
U
и
B
, когда:
1)
U
=
y
→
(
x
→
z
)
,
B
=
x
→
(
xy
((
x
→
y
)
→
y
)
z
)
;
2)
U
= (
x
∨
y
)(¯
x
∨
¯
y
)
,
B
= (
x
→
y
)
→
(
x
¯
y
⊕
(
x
↔
¯
y
))
;
3)
U
= (
xy
→
z
)
↔
¯
z,
B
= ¯
x
¯
z
∨
¯
y
¯
z
;
4)
U
= ¯
xz
∨
x
¯
y
∨
x
¯
z,
B
=
x yz
∨ ¬
(
x
→
z
)
;
5)
U
= (
x
↔
y
)
↔
z,
B
=
x
(
y
↔
z
)
∨
¯
x
(
y
⊕
z
)
.
§4.
Дизъюнктивная и конъюктивная нормальные формы
В предыдущих параграфах были введены понятия булевой функции
и формулы, при этом открытым остался вопрос о представлении произ-
вольной булевой функции в виде формулы. Приводимые ниже факты
направлены на решение этого вопроса.
11
Пусть
x
– булева переменная. Введем обозначение:
x
σ
=
xσ
∨
¯
x
¯
σ,
где
σ
– параметр, равный 0 либо 1. Очевидно, что
x
σ
=
{
¯
x,
если
σ
= 0
,
x,
если
σ
= 1
.
Легко видеть, что
x
σ
= 1
тогда и только тогда, когда
x
=
σ
, т.е. значе-
ние "основания"равно значению "показателя"степени.
Любая формула вида
x
α
(
x
или
¯
x
), где
x
– произвольная булева
переменная, называется литералом.
Элементарной конъюнкцией,
составленной
из
переменных
x
1
,
x
2
, . . . , x
n
, называется логическое произведение (конъюнкция) различ-
ных булевых переменных в некоторых степенях
K
=
x
σ
1
i
1
x
σ
2
i
2
. . . x
σ
r
i
r
,
{
i
1
, i
2
, . . . , i
k
} ⊆ {
1
, . . . , n
}
.
(4
.
1)
Элементарной дизъюнкцией,
составленной
из
переменных
x
1
, x
2
, . . . , x
n
, называется логическая сумма (дизъюнкция) различ-
ных булевых переменных в некоторых степенях
D
=
x
σ
1
i
1
∨
x
σ
2
i
2
∨
. . .
∨
x
σ
r
i
r
,
{
i
1
, i
2
, . . . , i
k
} ⊆ {
1
, . . . , n
}
.
(4
.
2)
Число
r
в формулах (4.1) и (4.2) называется соответственно
рангом конъюнкции и дизъюнкции. В случае, когда
r
= 0
, полагается
K
= 1
и
D
= 0
.
Дизъюнктивной нормальной формой (днф) называется произволь-
ная дизъюнкция элементарных конъюнкций
D
=
K
1
∨
K
2
∨
. . .
∨
K
m
,
(4
.
3)
в которой все конъюнкции
K
j
различны. Число
m
называется
длиной днф. В случае
m
= 0
днф называется пустой и полагается рав-
ной нулю.
Конъюнктивной нормальной формой (кнф) называется конъюнк-
ция элементарных дизъюнкций
K
=
D
1
∧
D
2
∧
. . .
∧
D
m
,
(4
.
4)
в которых все дизъюнкции
D
j
различны.
Имеют место следующие утверждения:
1. Для каждой булевой функции
f
(
x
1
, x
2
, . . . , x
n
)
существует реали-
зующая её дизъюнктивная нормальная форма
D
=
f
(
x
1
, x
2
, . . . , x
n
);
12
2. Для каждой булевой функции
f
(
x
1
, x
2
, . . . , x
n
)
существует реали-
зующая её конъюнктивная нормальная форма
K
=
f
(
x
1
, x
2
, . . . , x
n
)
.
Если функция
f
(
x
1
, x
2
, . . . , x
n
)
реализована в виде формулы, по-
строения днф и кнф можно осуществить с помощью следующего алго-
ритма.
Во-первых, исключим знаки
→
,
↔
,
⊕
,
|
,
↓
; при этом используем сле-
дующие эквивалентности:
u
→
v
= ¯
u
∨
v,
(4
.
5)
u
↔
v
=
uv
∨
¯
u
¯
v
= (¯
u
∨
v
)(
u
∨
¯
v
)
,
(4
.
6)
u
⊕
v
=
¬
(
u
→
v
) = ¯
uv
∨
u
¯
v
= (
u
∨
v
)(¯
u
∨
¯
v
)
,
(4
.
7)
u
|
v
= ¯
u
∨
¯
v,
u
↓
v
= ¯
u
¯
v.
(4
.
8)
Во-вторых, преобразуем полученное после первого шага выражение
так, чтобы знак отрицания стоял только над булевыми переменными.
При этом используем формулы инверсии:
u
∨
v
= ¯
u
¯
v,
uv
= ¯
u
∨
¯
v.
(4
.
9)
В-третьих, при построении днф формула, полученная после второ-
го шага, преобразовывается с использованием первого дистрибутивного
закона:
u
(
v
∨
w
) =
uv
∨
uw,
(4
.
10)
при построении кнф используется второй дистрибутивный закон:
u
∨
vw
= (
u
∨
v
)(
u
∨
w
)
.
(4
.
11)
Изложенный
метод
построения
днф
и
кнф
назовем
методом
эквивалентных преобразований. Этот метод может быть применен
в том случае, когда исходная булева функция задана формулой.
При реализации этого метода кроме перечисленных выше эквива-
лентностей (4.5)-(4.11) часто используется закон двойного отрицания
¯
¯
u
=
u,
(4
.
12)
а также следующие очевидные свойства операций дизъюнкции и конъ-
юнкции:
u
∧
1 =
u,
u
∧
0 = 0
,
u
∧
¯
u
= 0
,
u
∨
1 = 1
,
u
∨
¯
u
= 1
,
u
∨
0 =
u.
(4
.
13)