Элементы математической логики. Фролов И.С. - 22 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

§3. Нормальные формы
1. Дизъюнктивная нормальная форма
Вновь обратимся к формулам логики высказываний для изуче-
ния, помимо совершенных дизъюнктивных и конъюнктивных нормаль-
ных форм, аналогичных, но более компактных видов представления
логических функций.
Определение 1. Литералом называется атом или отрицание
атома (т.е. A, ¬B, . . . ). Конъюнктом (или элементарной конъюнкци-
ей) называется формула вида L
1
∧ . . . ∧ L
n
(n > 1), где L
1
, . . . , L
n
—
литералы (например, A ∧ B, ¬A ∧ B ∧ ¬C, ¬B ∧ C).
Говорят, что формула находится в дизъюнктивной нормальной
форме (сокращенно ДНФ), если она имеет вид K
1
∨. . . ∨K
m
(m > 1),
где K
1
, . . . , K
m
— конъюнкты (например, (A ∧ B) ∨ (¬A ∧ B ∧ ¬C)∨
∨(¬B ∧ C)).
Теорема 1. Любая формула эквивалентна некоторой формуле в
дизъюнктивной нормальной форме.
/ Пусть дана некоторая формула. Будем проводить эквивалентные
преобразования в определенном порядке. Прежде всего, мы всегда мо-
жем
1) устранить двойные отрицания (с помощью закона двойно-
го отрицания), т.е. заменить каждую часть формулы, имеющую вид
¬. . . ¬F , где F — произвольная формула, с помощью эквивалентности:
¬. . . ¬
| {z }
n
F ∼
½
F если n четно,
¬F если n нечетно;
2) устранить все знаки, отличные от пяти стандартных логиче-
ских связок ¬, ∧, ∨, ⇒, ⇔, т.е. |, ↓, ⊕, . . . и т.д. с помощью эквива-
лентностей:
A | B ∼ ¬(A ∧ B), A ↓ B ∼ ¬(A ∨ B), A ⊕ B ∼ ¬(A ⇔ B);
3) устранить все знаки эквиваленции и импликации (с помощью
закона эквиваленции и закона импликации) — для удобства приведем
их здесь вместе с некоторыми следствиями:
A ⇒ B ∼ ¬A ∨ B, ¬(A ⇒ B) ∼ A ∧¬B,
A ⇔ B ∼ (A ⇒ B) ∧ (B ⇒ A) ∼
∼ (A ∧ B) ∨ (¬A ∧ ¬B) ∼ (A ∨ ¬B) ∧ (¬A ∨ B)
21

Страницы