Специальная математика. Соловьев А.Е. - 24 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

3. Форма D
1
D
2
... D
n
, где D
j
- элементарная дизъюнкция, называется конъюнктивной
нормальной формой (КНФ).
4. Форма K
1
K
2
... K
n
, где K
j
- элементарная конъюнкция, называется дизъюнктивной
нормальной формой (ДНФ).
Всегда истинное (на любых наборах значений входящих в него элементарных
высказываний) сложное высказывание называется тавтологией.
Всегда ложное (на любых наборах значений входящих в него элементарных высказываний)
высказывание называется противоречием.
Совершенной КНФ (СКНФ) называется такая КНФ, что каждая входящая в нее
элементарная дизъюнкция содержит все элементарные высказывания прямо или с инверсией
строго по одному разу. Нет повторяющихся дизъюнкций. Любое сложное высказывание,
кроме тавтологии, имеет единственную СКНФ.
Совершенной ДНФ (СДНФ) называется такая ДНФ, что каждая входящая в нее
элементарная конъюнкция содержит все элементарные высказывания прямо или с
инверсией строго по одному разу. Нет повторяющихся конъюнкций. Любое сложное
высказывание, кроме противоречия, имеет единственную СДНФ.
2.1.5. Преобразование высказываний
Сложное высказывание, представленное в произвольном виде с помощью
равносильностей с 11 по 16, а также с использованием законов Де Моргана могут быть
преобразованы к нормальной форме.
Преобразование КНФ в СКНФ.
Схематично основную идею преобразования можно представить так:
X Y ≡ X Y 0 ≡ X Y ZZ ≡ (X Y Z)(X Y Z)
Преобразование ДНФ в СДНФ.
Схематично основную идею преобразования можно представить так:
XY ≡ XY1 ≡ XY(Z Z) ≡ XYZ XYZ
Преобразование СДНФ в СКНФ и наоборот.
Рассмотрим на примере:
Возьмем логическую функцию f (сложное высказывание) в СДНФ и построим отрицание
этой функции, т.е. функцию f, путем выписывания всех конституент единицы, не входящих в
f.
Примеры:
Пусть f имеет вид
f=X
1
X
2
X
3
X
1
X
2
X
3
X
1
X
2
X
3
X
1
X
2
X
3
3 5 6 7
(мнемонический прием – приписать конституентам числа, которые получаются, если
посмотреть на конституенты как на двоичные числа)
— 24 —
3. Форма D1  D2  ...  Dn, где Dj - элементарная дизъюнкция, называется конъюнктивной
нормальной формой (КНФ).
4. Форма K1  K2  ...  Kn, где Kj - элементарная конъюнкция, называется дизъюнктивной
нормальной формой (ДНФ).

Всегда истинное (на любых наборах значений входящих в него элементарных
высказываний) сложное высказывание называется тавтологией.
Всегда ложное (на любых наборах значений входящих в него элементарных высказываний)
высказывание называется противоречием.

    Совершенной КНФ (СКНФ) называется такая КНФ, что каждая входящая в нее
элементарная дизъюнкция содержит все элементарные высказывания прямо или с инверсией
строго по одному разу. Нет повторяющихся дизъюнкций. Любое сложное высказывание,
кроме тавтологии, имеет единственную СКНФ.

    Совершенной ДНФ (СДНФ) называется такая ДНФ, что каждая входящая в нее
элементарная конъюнкция содержит все элементарные высказывания прямо или с
инверсией строго по одному разу. Нет повторяющихся конъюнкций. Любое сложное
высказывание, кроме противоречия, имеет единственную СДНФ.

                       2.1.5. Преобразование высказываний

      Сложное высказывание, представленное в произвольном виде с помощью
равносильностей с 11 по 16, а также с использованием законов Де Моргана могут быть
преобразованы к нормальной форме.

Преобразование КНФ в СКНФ.
Схематично основную идею преобразования можно представить так:

X  Y ≡ X  Y  0 ≡ X  Y  ZZ ≡ (X  Y  Z)(X  Y  Z)

Преобразование ДНФ в СДНФ.
Схематично основную идею преобразования можно представить так:

XY ≡ XY1 ≡ XY(Z  Z) ≡ XYZ  XYZ

Преобразование СДНФ в СКНФ и наоборот.
Рассмотрим на примере:
Возьмем логическую функцию f (сложное высказывание) в СДНФ и построим отрицание
этой функции, т.е. функцию f, путем выписывания всех конституент единицы, не входящих в
f.

Примеры:

Пусть f имеет вид

f=X1X2X3 X1X2X3 X1X2X3 X1X2X3
     3         5         6          7

(мнемонический прием – приписать конституентам числа, которые получаются, если
посмотреть на конституенты как на двоичные числа)

                                           — 24 —

Страницы