Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 422
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
n
= hB
n
; ∧, ∨, , 0, 1i образует булеву алгебру функций алгебры логики от n переменных (алгебру булевых функций).
§ 6.3.
Эквивалентность формул
Как показано в примере 6.1.1, различные формулы могут иметь одинако- вые таблицы истинности. Так возникает понятие эквивалентности формул.
Формулы ϕ(x
1
, . . . , x
n
) и ψ(x
1
, . . . , x
n
) называются эквивалентными
(ϕ ∼ ψ), если совпадают их таблицы истинности, т. е. совпадают представ- ляемые этими формулами функции f
ϕ
(x
1
, . . . , x
n
) и f
ψ
(x
1
, . . . , x
n
).
Пример 6.3.1. Построив таблицы истинности формул x → y и y → x,
убеждаемся в том, что (x → y) ∼ (y → x). ¤
Легко видеть, что отношение ∼ является отношением эквивалентности,
т. е. оно рефлексивно (ϕ ∼ ϕ), симметрично (ϕ ∼ ψ ⇒ ψ ∼ ϕ) и транзитивно
(ϕ ∼ ψ, ψ ∼ χ ⇒ ϕ ∼ χ).
Отметим основные эквивалентности между формулами:
1) ((ϕ∧ψ)∧χ) ∼ (ϕ∧(ψ∧χ)), ((ϕ∨ψ)∨χ) ∼ (ϕ∨(ψ∨χ)) (ассоциативность
∧ и ∨);
2) (ϕ ∧ ψ) ∼ (ψ ∧ ϕ), (ϕ ∨ ψ) ∼ (ψ ∨ ϕ) (коммутативность ∧ и ∨);
3) (ϕ ∧ ϕ) ∼ ϕ, (ϕ ∨ ϕ) ∼ ϕ (идемпотентность ∧ и ∨);
4) (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ)), (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ)∧ ∧(ϕ ∨ χ))
(законы дистрибутивности);
5) (ϕ ∧ (ϕ ∨ ψ)) ∼ ϕ, (ϕ ∨ (ϕ ∧ ψ)) ∼ ϕ (законы поглощения);
6) ¬(ϕ ∧ ψ) ∼ ¬ϕ ∨ ¬ψ, ¬(ϕ ∨ ψ) ∼ ¬ϕ ∧ ¬ψ (законы де Моргана);
7) ¬¬ϕ ∼ ϕ (закон двойного отрицания);
6.3. ЭКВИВАЛЕНТНОСТЬ ФОРМУЛ
187 8) ϕ → ψ ∼ ¬ϕ ∨ ψ;
9) ϕ ↔ ψ ∼ ((ϕ → ψ) ∧ (ψ → ϕ)) ∼ ((¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ));
10) (ϕ ∨ ¬ϕψ) ∼ (ϕ ∨ ψ), (¬ϕ ∨ ϕψ) ∼ (¬ϕ ∨ ψ);
11) ϕ(¬ϕ ∨ ψ) ∼ ϕψ, ¬ϕ(ϕ ∨ ψ) ∼ ¬ϕψ.
Формула ϕ(x
1
, x
2
, . . . , x
n
) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула при- нимает значение 1 (соответственно 0).
Пример 6.3.2. Формула x∧y является одновременно выполнимой и опро- вержимой, поскольку 0 ∧ 0 = 0, а 1 ∧ 1 = 1. ¤
Формула ϕ(x
1
, . . . , x
n
) называется тождественно истинной, общезначи- мой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) при всех наборах зна- чений переменных, т. е. функция f является константой 1 (константой 0).
Пример 6.3.3. Формула x ∨ x является тождественно истинной, а фор- мула x ∧ x — тождественно ложной:
x x ∨ x x ∧ x
0 1
0 1
1 0
Если ϕ — тождественно истинная формула, то будем писать |= ϕ. В про- тивном случае пишем 6|= ϕ. Таким образом, |= x ∨ x, 6|= x ∧ y, и 6|= x ∧ x.
Очевидным является следующее
Замечание 6.3.1. 1. Формула ϕ тождественно ложна тогда и только
тогда, когда ¬ϕ тождественно истинна (|= ¬ϕ);
2. Формула ϕ опровержима тогда и только тогда, когда она не является
тождественно истинной (6|= ϕ);
3. Формула ϕ выполнима тогда и только тогда, когда она не является
тождественно ложной.
Отметим, что тождественно истинные (соответственно тождественно лож- ные) формулы образуют класс эквивалентности по отношению ∼.
Предложение 6.3.2. Если формула ϕ
1
тождественно истинна, ϕ
0
—
тождественно ложна, то для любых формул ϕ и ψ справедливы следующие
эквивалентности:
ϕ ∧ ϕ
1
∼ ϕ; ϕ ∧ ϕ
0
∼ ϕ
0
; ϕ ∨ ϕ
1
∼ ϕ
1
; ϕ ∨ ϕ
0
∼ ϕ; (ϕψ → ϕ) ∼ ϕ
1
;
(ϕ → ϕ ∨ ψ) ∼ ϕ
1
; ϕ ⊕ ϕ ∼ ϕ
0
; ϕ ⊕ ϕ
1
∼ ϕ; ϕ ⊕ ϕ
0
∼ ϕ.
188
Глава 6. АЛГЕБРА ЛОГИКИ
В заключение настоящего параграфа приведем список всевозможных бу- левых функций от двух переменных, а также основных формул, представ- ляющих эти функции:
0 0 1 1 x
0 1 0 1 y
0 0 0 0 x ∧ ¬x — константа 0 0 0 0 1 x ∧ y — конъюнкция
0 0 1 0 ¬(x → y) — запрет по y
0 0 1 1 x — повтор x
0 1 0 0 ¬(y → x) — запрет по x
0 1 0 1 y — повтор y
0 1 1 0 x ⊕ y — логическое сложение
0 1 1 1 x ∨ y — дизъюнкция
1 0 0 0 x ↓ y — стрелка Пирса
1 0 0 1 x ↔ y — эквивалентность
1 0 1 0 ¬y — отрицание y
1 0 1 1 y → x — обратная импликация
1 1 0 0 ¬x — отрицание x
1 1 0 1 x → y — прямая импликация
1 1 1 0 x | y — штрих Шеффера
1 1 1 1 x ∨ ¬x — константа 1.
§ 6.4.
Дизъюнктивные и конъюнктивные нормальные формы
Если x — логическая переменная, δ ∈ {0, 1}, то выражение
x
δ
=
(
x, если δ = 1,
x, если δ = 0
называется литерой. Литеры x и x называются контрарными.
Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнк- ция литер.
Пример 6.4.1. Формулы x ∨ y ∨ z и x ∨ y ∨ x ∨ x — дизъюнкты, формулы
x
1
x
2
x
3
и x
1
x
2
x
1
— конъюнкты, а x является одновременно и дизъюнктом,
и конъюнктом. ¤
6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
189
Дизъюнкция конъюнктов называется дизъюнктивной нормальной фор-
мой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормаль-
ной формой (КНФ).
Пример 6.4.2. Формула xy ∨ yz — ДНФ, формула (x ∨ z ∨ y)(x ∨ z)y —
КНФ, а формула xy является одновременно КНФ и ДНФ. ¤
Теорема 6.4.1. 1. Любая формула эквивалентна некоторой ДНФ.
2. Любая формула эквивалентна некоторой КНФ.
Опишем алгоритм приведения формулы к ДНФ.
1. Выражаем все логические операции, участвующие в построении фор- мулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалент- ности (ϕ → ψ) ∼ (¬ϕ ∨ ψ), (ϕ ↔ ψ) ∼ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ) и определения операций |, ↓ и ⊕.
2. Используя законы де Моргана, переносим все отрицания к пере- менным и сокращаем двойные отрицания по правилу ¬¬x ∼ x.
3. Используя закон дистрибутивности (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ) ∨ (ϕ∧ χ)),
преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъ- юнкций.
В результате применения пп. 1–3 получается ДНФ данной формулы. ¤
Пример 6.4.3. Приведем к ДНФ формулу ϕ = ((x → y) ↓ ¬(y → z)).
Выразим логические операции → и ↓ через ∧, ∨ и ¬:
ϕ ∼ (x ∨ y) ↓ ¬(y ∨ z) ∼ ¬((x ∨ y) ∨ ¬(y ∨ z)).
В полученной формуле перенесем отрицание к переменным и сократим двой- ные отрицания:
ϕ ∼ ¬(x ∨ y) ∧ ¬¬(y ∨ z) ∼ (x ∧ y) ∧ (y ∨ z) ∼ (x ∧ y) ∧ (y ∨ z).
Используя закон дистрибутивности, приводим формулу к ДНФ:
ϕ ∼ (x ∧ y ∧ y) ∨ (x ∧ y ∧ z). ¤
Приведение формулы к КНФ производится аналогично ее приведению к ДНФ, только вместо п. 3 применяется пункт
3
0
. Используя закон дистрибутивности (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ)),
преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.
190
Глава 6. АЛГЕБРА ЛОГИКИ
Пример 6.4.4. Приведем к КНФ формулу ϕ = (x → y) ∧ ((y → z) → x).
Преобразуем формулу ϕ к формуле, не содержащей →:
ϕ ∼ (x ∨ y) ∧ (¬(y → z) ∨ x) ∼ (x ∨ y) ∧ (¬(y ∨ z) ∨ x).
В полученной формуле перенесем отрицание к переменным и сократим двой- ные отрицания:
ϕ ∼ (x ∨ y) ∧ ((y ∧ z) ∨ x) ∼ (x ∨ y) ∧ ((y ∧ z) ∨ x).
По закону дистрибутивности получаем, что формула ϕ эквивалентна фор- муле (x ∨ y) ∧ (x ∨ y) ∧ (x ∨ z), являющейся КНФ. Упростим полученную формулу:
(x ∨ y) ∧ (x ∨ y) ∧ (x ∨ z)
(1)
∼ (x ∨ (y ∧ y)) ∧ (x ∨ z)
(2)
∼ x ∧ (x ∨ z)
(3)
∼ x
(для преобразования (1) использовался закон дистрибутивности, для (2) —
эквивалентность 4 предложения 6.3.2., для (3) — закон поглощения). Таким образом, формула ϕ из примера 6.1.1 эквивалентными преобразованиями приводится к формуле x (являющейся одновременно ДНФ и КНФ
формулы ϕ). ¤
Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают со- вершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).
Пусть (x
1
, . . . , x
n
) — набор логических переменных, ∆ = (δ
1
, . . . , δ
n
) —
набор нулей и единиц. Конституентой единицы набора ∆ называется конъ- юнкт K
1
(δ
1
, . . . , δ
n
) x
δ
1 1
x
δ
2 2
. . . x
δ
n
n
. Конституентой нуля набора ∆ на- зывается дизъюнкт K
0
(δ
1
, . . . , δ
n
) x
1−δ
1 1
∨ x
1−δ
2 2
∨ . . . ∨ x
1−δ
n
n
Отметим, что K
1
(δ
1
, δ
2
, . . . , δ
n
) = 1 (K
0
(δ
1
, δ
2
, . . . , δ
n
) = 0) тогда и только тогда, когда x
1
= δ
1
, x
2
= δ
2
, . . ., x
n
= δ
n
Совершенной ДНФ называется дизъюнкция некоторых конституент еди- ницы, среди которых нет одинаковых, а совершенной КНФ называется конъ- юнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт
(дизъюнкт) каждая переменная x
i
из набора {x
1
, . . . , x
n
} входит ровно один раз, причем входит либо сама x
i
, либо ее отрицание x
i
6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
191
Пример 6.4.5. Формула x
1
x
2
x
3
есть конституента единицы K
1
(1, 0, 1),
формула x ∨ y ∨ z есть конституента нуля K
0
(0, 0, 1), формула x
1
x
2
x
3
∨
∨x
1
x
2
x
3
— СДНФ, формула (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) — СКНФ,
а формула x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
не является СДНФ. ¤
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исход- ной формуле ϕ, предварительно рассмотрим разложения булевой функции
f (x
1
, x
2
, . . . , x
n
) по k переменным (для определенности по x
1
, x
2
, . . ., x
k
) —
разложения Шеннона.
Теорема 6.4.2 (первая теорема Шеннона). Любая
булева
функция
f (x
1
, x
2
, . . . , x
n
) представима в виде разложения Шеннона:
f (x
1
, x
2
, . . . , x
k
, x
k+1
, . . . , x
n
) =
=
_
по всем наборам
(δ
1
,...,δ
k
)
(
k
∧
i=1
x
δ
i
i
)f (δ
1
, δ
2
, . . . , δ
k
, x
k+1
, . . . , x
n
).
Доказательство. Прежде всего заметим, что x
δ
i
i
= 1 ⇔ x
i
= δ
i
. Под- ставим произвольно вместо первых k переменных их значения: x
1
= δ
∗
1
,
x
2
= δ
∗
2
, . . ., x
k
= δ
∗
k
. Тогда левая часть доказываемой формулы равна
f (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
, x
k+1
, . . . , x
n
). Правая часть представляет собой дизъюнкцию
2
k
конъюнкций вида x
δ
1 1
x
δ
2 2
. . . x
δ
k
k
f (δ
1
, δ
2
, . . . , δ
k
, x
k+1
, . . . , x
n
), которые этой подстановкой разбиваются на два класса. К первому классу относится конъ- юнкция, у которой набор (δ
1
, δ
2
, . . . , δ
k
) совпадает с набором (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
):
(δ
∗
1
)
δ
∗
1
(δ
∗
2
)
δ
∗
2
. . . (δ
∗
k
)
δ
∗
k
f (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
, x
k+1
, . . . , x
n
) =
= 1 · 1 · . . . · 1 · f (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
, x
k+1
, . . . , x
n
) =
= f (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
, x
k+1
, . . . , x
n
).
Эта конъюнкция равна левой части формулы. Ко второму классу относится
2
k
− 1 конъюнкций, у каждой из которых хотя бы в одной переменной x
i
,
i ∈ {1, 2, . . . , k} выполнено условие δ
∗
i
6= δ
i
. Следовательно, каждая из них равна нулю. Используя закон a ∨ 0 = a, получаем, что левая и правая части формул равны при любой подстановке переменных x
1
, x
2
, . . . , x
n
. ¤
В силу принципа двойственности для булевых алгебр справедлива
192
Глава 6. АЛГЕБРА ЛОГИКИ
Теорема 6.4.3 (вторая теорема Шеннона). Любая
булева
функция
f (x
1
, x
2
, . . . , x
n
) представима в виде разложения Шеннона:
f (x
1
, x
2
, . . . , x
k
, x
k+1
, . . . , x
n
) =
=
^
по всем наборам
(δ
1
,...,δ
k
)
(
k
∨
i=1
x
1−δ
i
i
∨ f (δ
1
, δ
2
, . . . , δ
k
, x
k+1
, . . . , x
n
)).
В предельном случае, когда k = n, для булевой функции f (x
1
, x
2
, . . . , x
n
),
не равной нулю, получаем ее представление в виде совершенной ДНФ:
f (x
1
, x
2
, . . . , x
n
) =
_
по всем наборам
(δ
1
,δ
2
,...,δ
n
),
на которых
f (δ
1
,...,δ
n
)=1
(
n
∧
i=1
x
δ
i
i
).
Аналогично для булевой функции f (x
1
, x
2
, . . . , x
n
), не равной единице,
получаем ее представление в виде совершенной КНФ:
f (x
1
, x
2
, . . . , x
n
) =
^
по всем наборам
(δ
1
,δ
2
,...,δ
n
),
на которых
f (δ
1
,...,δ
n
)=0
(
n
∨
i=1
x
1−δ
i
i
).
Приведенные формулы позволяют сформулировать следующую теорему.
Теорема 6.4.4 (о функциональной полноте). Для любой булевой функ-
ции f найдется формула ϕ, представляющая функцию f . Если f 6≡ 0
= hB
n
; ∧, ∨, , 0, 1i образует булеву алгебру функций алгебры логики от n переменных (алгебру булевых функций).
§ 6.3.
Эквивалентность формул
Как показано в примере 6.1.1, различные формулы могут иметь одинако- вые таблицы истинности. Так возникает понятие эквивалентности формул.
Формулы ϕ(x
1
, . . . , x
n
) и ψ(x
1
, . . . , x
n
) называются эквивалентными
(ϕ ∼ ψ), если совпадают их таблицы истинности, т. е. совпадают представ- ляемые этими формулами функции f
ϕ
(x
1
, . . . , x
n
) и f
ψ
(x
1
, . . . , x
n
).
Пример 6.3.1. Построив таблицы истинности формул x → y и y → x,
убеждаемся в том, что (x → y) ∼ (y → x). ¤
Легко видеть, что отношение ∼ является отношением эквивалентности,
т. е. оно рефлексивно (ϕ ∼ ϕ), симметрично (ϕ ∼ ψ ⇒ ψ ∼ ϕ) и транзитивно
(ϕ ∼ ψ, ψ ∼ χ ⇒ ϕ ∼ χ).
Отметим основные эквивалентности между формулами:
1) ((ϕ∧ψ)∧χ) ∼ (ϕ∧(ψ∧χ)), ((ϕ∨ψ)∨χ) ∼ (ϕ∨(ψ∨χ)) (ассоциативность
∧ и ∨);
2) (ϕ ∧ ψ) ∼ (ψ ∧ ϕ), (ϕ ∨ ψ) ∼ (ψ ∨ ϕ) (коммутативность ∧ и ∨);
3) (ϕ ∧ ϕ) ∼ ϕ, (ϕ ∨ ϕ) ∼ ϕ (идемпотентность ∧ и ∨);
4) (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ) ∨ (ϕ ∧ χ)), (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ)∧ ∧(ϕ ∨ χ))
(законы дистрибутивности);
5) (ϕ ∧ (ϕ ∨ ψ)) ∼ ϕ, (ϕ ∨ (ϕ ∧ ψ)) ∼ ϕ (законы поглощения);
6) ¬(ϕ ∧ ψ) ∼ ¬ϕ ∨ ¬ψ, ¬(ϕ ∨ ψ) ∼ ¬ϕ ∧ ¬ψ (законы де Моргана);
7) ¬¬ϕ ∼ ϕ (закон двойного отрицания);
6.3. ЭКВИВАЛЕНТНОСТЬ ФОРМУЛ
187 8) ϕ → ψ ∼ ¬ϕ ∨ ψ;
9) ϕ ↔ ψ ∼ ((ϕ → ψ) ∧ (ψ → ϕ)) ∼ ((¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ));
10) (ϕ ∨ ¬ϕψ) ∼ (ϕ ∨ ψ), (¬ϕ ∨ ϕψ) ∼ (¬ϕ ∨ ψ);
11) ϕ(¬ϕ ∨ ψ) ∼ ϕψ, ¬ϕ(ϕ ∨ ψ) ∼ ¬ϕψ.
Формула ϕ(x
1
, x
2
, . . . , x
n
) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула при- нимает значение 1 (соответственно 0).
Пример 6.3.2. Формула x∧y является одновременно выполнимой и опро- вержимой, поскольку 0 ∧ 0 = 0, а 1 ∧ 1 = 1. ¤
Формула ϕ(x
1
, . . . , x
n
) называется тождественно истинной, общезначи- мой или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соответственно 0) при всех наборах зна- чений переменных, т. е. функция f является константой 1 (константой 0).
Пример 6.3.3. Формула x ∨ x является тождественно истинной, а фор- мула x ∧ x — тождественно ложной:
x x ∨ x x ∧ x
0 1
0 1
1 0
Если ϕ — тождественно истинная формула, то будем писать |= ϕ. В про- тивном случае пишем 6|= ϕ. Таким образом, |= x ∨ x, 6|= x ∧ y, и 6|= x ∧ x.
Очевидным является следующее
Замечание 6.3.1. 1. Формула ϕ тождественно ложна тогда и только
тогда, когда ¬ϕ тождественно истинна (|= ¬ϕ);
2. Формула ϕ опровержима тогда и только тогда, когда она не является
тождественно истинной (6|= ϕ);
3. Формула ϕ выполнима тогда и только тогда, когда она не является
тождественно ложной.
Отметим, что тождественно истинные (соответственно тождественно лож- ные) формулы образуют класс эквивалентности по отношению ∼.
Предложение 6.3.2. Если формула ϕ
1
тождественно истинна, ϕ
0
—
тождественно ложна, то для любых формул ϕ и ψ справедливы следующие
эквивалентности:
ϕ ∧ ϕ
1
∼ ϕ; ϕ ∧ ϕ
0
∼ ϕ
0
; ϕ ∨ ϕ
1
∼ ϕ
1
; ϕ ∨ ϕ
0
∼ ϕ; (ϕψ → ϕ) ∼ ϕ
1
;
(ϕ → ϕ ∨ ψ) ∼ ϕ
1
; ϕ ⊕ ϕ ∼ ϕ
0
; ϕ ⊕ ϕ
1
∼ ϕ; ϕ ⊕ ϕ
0
∼ ϕ.
188
Глава 6. АЛГЕБРА ЛОГИКИ
В заключение настоящего параграфа приведем список всевозможных бу- левых функций от двух переменных, а также основных формул, представ- ляющих эти функции:
0 0 1 1 x
0 1 0 1 y
0 0 0 0 x ∧ ¬x — константа 0 0 0 0 1 x ∧ y — конъюнкция
0 0 1 0 ¬(x → y) — запрет по y
0 0 1 1 x — повтор x
0 1 0 0 ¬(y → x) — запрет по x
0 1 0 1 y — повтор y
0 1 1 0 x ⊕ y — логическое сложение
0 1 1 1 x ∨ y — дизъюнкция
1 0 0 0 x ↓ y — стрелка Пирса
1 0 0 1 x ↔ y — эквивалентность
1 0 1 0 ¬y — отрицание y
1 0 1 1 y → x — обратная импликация
1 1 0 0 ¬x — отрицание x
1 1 0 1 x → y — прямая импликация
1 1 1 0 x | y — штрих Шеффера
1 1 1 1 x ∨ ¬x — константа 1.
§ 6.4.
Дизъюнктивные и конъюнктивные нормальные формы
Если x — логическая переменная, δ ∈ {0, 1}, то выражение
x
δ
=
(
x, если δ = 1,
x, если δ = 0
называется литерой. Литеры x и x называются контрарными.
Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнк- ция литер.
Пример 6.4.1. Формулы x ∨ y ∨ z и x ∨ y ∨ x ∨ x — дизъюнкты, формулы
x
1
x
2
x
3
и x
1
x
2
x
1
— конъюнкты, а x является одновременно и дизъюнктом,
и конъюнктом. ¤
6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
189
Дизъюнкция конъюнктов называется дизъюнктивной нормальной фор-
мой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормаль-
ной формой (КНФ).
Пример 6.4.2. Формула xy ∨ yz — ДНФ, формула (x ∨ z ∨ y)(x ∨ z)y —
КНФ, а формула xy является одновременно КНФ и ДНФ. ¤
Теорема 6.4.1. 1. Любая формула эквивалентна некоторой ДНФ.
2. Любая формула эквивалентна некоторой КНФ.
Опишем алгоритм приведения формулы к ДНФ.
1. Выражаем все логические операции, участвующие в построении фор- мулы, через дизъюнкции, конъюнкции и отрицания, используя эквивалент- ности (ϕ → ψ) ∼ (¬ϕ ∨ ψ), (ϕ ↔ ψ) ∼ (¬ϕ ∨ ψ) ∧ (¬ψ ∨ ϕ) и определения операций |, ↓ и ⊕.
2. Используя законы де Моргана, переносим все отрицания к пере- менным и сокращаем двойные отрицания по правилу ¬¬x ∼ x.
3. Используя закон дистрибутивности (ϕ ∧ (ψ ∨ χ)) ∼ ((ϕ ∧ ψ) ∨ (ϕ∧ χ)),
преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъ- юнкций.
В результате применения пп. 1–3 получается ДНФ данной формулы. ¤
Пример 6.4.3. Приведем к ДНФ формулу ϕ = ((x → y) ↓ ¬(y → z)).
Выразим логические операции → и ↓ через ∧, ∨ и ¬:
ϕ ∼ (x ∨ y) ↓ ¬(y ∨ z) ∼ ¬((x ∨ y) ∨ ¬(y ∨ z)).
В полученной формуле перенесем отрицание к переменным и сократим двой- ные отрицания:
ϕ ∼ ¬(x ∨ y) ∧ ¬¬(y ∨ z) ∼ (x ∧ y) ∧ (y ∨ z) ∼ (x ∧ y) ∧ (y ∨ z).
Используя закон дистрибутивности, приводим формулу к ДНФ:
ϕ ∼ (x ∧ y ∧ y) ∨ (x ∧ y ∧ z). ¤
Приведение формулы к КНФ производится аналогично ее приведению к ДНФ, только вместо п. 3 применяется пункт
3
0
. Используя закон дистрибутивности (ϕ ∨ (ψ ∧ χ)) ∼ ((ϕ ∨ ψ) ∧ (ϕ ∨ χ)),
преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.
190
Глава 6. АЛГЕБРА ЛОГИКИ
Пример 6.4.4. Приведем к КНФ формулу ϕ = (x → y) ∧ ((y → z) → x).
Преобразуем формулу ϕ к формуле, не содержащей →:
ϕ ∼ (x ∨ y) ∧ (¬(y → z) ∨ x) ∼ (x ∨ y) ∧ (¬(y ∨ z) ∨ x).
В полученной формуле перенесем отрицание к переменным и сократим двой- ные отрицания:
ϕ ∼ (x ∨ y) ∧ ((y ∧ z) ∨ x) ∼ (x ∨ y) ∧ ((y ∧ z) ∨ x).
По закону дистрибутивности получаем, что формула ϕ эквивалентна фор- муле (x ∨ y) ∧ (x ∨ y) ∧ (x ∨ z), являющейся КНФ. Упростим полученную формулу:
(x ∨ y) ∧ (x ∨ y) ∧ (x ∨ z)
(1)
∼ (x ∨ (y ∧ y)) ∧ (x ∨ z)
(2)
∼ x ∧ (x ∨ z)
(3)
∼ x
(для преобразования (1) использовался закон дистрибутивности, для (2) —
эквивалентность 4 предложения 6.3.2., для (3) — закон поглощения). Таким образом, формула ϕ из примера 6.1.1 эквивалентными преобразованиями приводится к формуле x (являющейся одновременно ДНФ и КНФ
формулы ϕ). ¤
Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают со- вершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).
Пусть (x
1
, . . . , x
n
) — набор логических переменных, ∆ = (δ
1
, . . . , δ
n
) —
набор нулей и единиц. Конституентой единицы набора ∆ называется конъ- юнкт K
1
(δ
1
, . . . , δ
n
) x
δ
1 1
x
δ
2 2
. . . x
δ
n
n
. Конституентой нуля набора ∆ на- зывается дизъюнкт K
0
(δ
1
, . . . , δ
n
) x
1−δ
1 1
∨ x
1−δ
2 2
∨ . . . ∨ x
1−δ
n
n
Отметим, что K
1
(δ
1
, δ
2
, . . . , δ
n
) = 1 (K
0
(δ
1
, δ
2
, . . . , δ
n
) = 0) тогда и только тогда, когда x
1
= δ
1
, x
2
= δ
2
, . . ., x
n
= δ
n
Совершенной ДНФ называется дизъюнкция некоторых конституент еди- ницы, среди которых нет одинаковых, а совершенной КНФ называется конъ- юнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт
(дизъюнкт) каждая переменная x
i
из набора {x
1
, . . . , x
n
} входит ровно один раз, причем входит либо сама x
i
, либо ее отрицание x
i
6.4. ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
191
Пример 6.4.5. Формула x
1
x
2
x
3
есть конституента единицы K
1
(1, 0, 1),
формула x ∨ y ∨ z есть конституента нуля K
0
(0, 0, 1), формула x
1
x
2
x
3
∨
∨x
1
x
2
x
3
— СДНФ, формула (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) — СКНФ,
а формула x
1
x
2
x
3
∨ x
1
x
2
x
3
∨ x
1
x
2
x
3
не является СДНФ. ¤
Для решения задачи нахождения СДНФ и СКНФ, эквивалентных исход- ной формуле ϕ, предварительно рассмотрим разложения булевой функции
f (x
1
, x
2
, . . . , x
n
) по k переменным (для определенности по x
1
, x
2
, . . ., x
k
) —
разложения Шеннона.
Теорема 6.4.2 (первая теорема Шеннона). Любая
булева
функция
f (x
1
, x
2
, . . . , x
n
) представима в виде разложения Шеннона:
f (x
1
, x
2
, . . . , x
k
, x
k+1
, . . . , x
n
) =
=
_
по всем наборам
(δ
1
,...,δ
k
)
(
k
∧
i=1
x
δ
i
i
)f (δ
1
, δ
2
, . . . , δ
k
, x
k+1
, . . . , x
n
).
Доказательство. Прежде всего заметим, что x
δ
i
i
= 1 ⇔ x
i
= δ
i
. Под- ставим произвольно вместо первых k переменных их значения: x
1
= δ
∗
1
,
x
2
= δ
∗
2
, . . ., x
k
= δ
∗
k
. Тогда левая часть доказываемой формулы равна
f (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
, x
k+1
, . . . , x
n
). Правая часть представляет собой дизъюнкцию
2
k
конъюнкций вида x
δ
1 1
x
δ
2 2
. . . x
δ
k
k
f (δ
1
, δ
2
, . . . , δ
k
, x
k+1
, . . . , x
n
), которые этой подстановкой разбиваются на два класса. К первому классу относится конъ- юнкция, у которой набор (δ
1
, δ
2
, . . . , δ
k
) совпадает с набором (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
):
(δ
∗
1
)
δ
∗
1
(δ
∗
2
)
δ
∗
2
. . . (δ
∗
k
)
δ
∗
k
f (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
, x
k+1
, . . . , x
n
) =
= 1 · 1 · . . . · 1 · f (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
, x
k+1
, . . . , x
n
) =
= f (δ
∗
1
, δ
∗
2
, . . . , δ
∗
k
, x
k+1
, . . . , x
n
).
Эта конъюнкция равна левой части формулы. Ко второму классу относится
2
k
− 1 конъюнкций, у каждой из которых хотя бы в одной переменной x
i
,
i ∈ {1, 2, . . . , k} выполнено условие δ
∗
i
6= δ
i
. Следовательно, каждая из них равна нулю. Используя закон a ∨ 0 = a, получаем, что левая и правая части формул равны при любой подстановке переменных x
1
, x
2
, . . . , x
n
. ¤
В силу принципа двойственности для булевых алгебр справедлива
192
Глава 6. АЛГЕБРА ЛОГИКИ
Теорема 6.4.3 (вторая теорема Шеннона). Любая
булева
функция
f (x
1
, x
2
, . . . , x
n
) представима в виде разложения Шеннона:
f (x
1
, x
2
, . . . , x
k
, x
k+1
, . . . , x
n
) =
=
^
по всем наборам
(δ
1
,...,δ
k
)
(
k
∨
i=1
x
1−δ
i
i
∨ f (δ
1
, δ
2
, . . . , δ
k
, x
k+1
, . . . , x
n
)).
В предельном случае, когда k = n, для булевой функции f (x
1
, x
2
, . . . , x
n
),
не равной нулю, получаем ее представление в виде совершенной ДНФ:
f (x
1
, x
2
, . . . , x
n
) =
_
по всем наборам
(δ
1
,δ
2
,...,δ
n
),
на которых
f (δ
1
,...,δ
n
)=1
(
n
∧
i=1
x
δ
i
i
).
Аналогично для булевой функции f (x
1
, x
2
, . . . , x
n
), не равной единице,
получаем ее представление в виде совершенной КНФ:
f (x
1
, x
2
, . . . , x
n
) =
^
по всем наборам
(δ
1
,δ
2
,...,δ
n
),
на которых
f (δ
1
,...,δ
n
)=0
(
n
∨
i=1
x
1−δ
i
i
).
Приведенные формулы позволяют сформулировать следующую теорему.
Теорема 6.4.4 (о функциональной полноте). Для любой булевой функ-
ции f найдется формула ϕ, представляющая функцию f . Если f 6≡ 0
1 ... 17 18 19 20 21 22 23 24 ... 29