Преобразование СДНФ в СКНФ и наоборот.

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

Сложное высказывание, представленное в произвольном виде с помощью равносильностей с 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=X₁×X₂×X₃Ú X₁×X₂×X₃Ú X₁×X₂×X₃Ú X₁×X₂×X₃

3 5 6 7

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

Отрицание функци f получим выписыванием недостающих конституент (недостающих двоичных чисел).

f=X₁×X₂×X₃Ú X₁×X₂×X₃Ú X₁×X₂×X₃Ú X₁×X₂×X₃

0 1 2 4

А теперь применим отрицание к функции f.

f = X₁×X₂×X₃Ú X₁×X₂×X₃Ú X₁×X₂×X₃Ú X₁×X₂×X₃ ≡

≡ (X₁ÚX₂ÚX₃)×(X₁ÚX₂ÚX₃)×(X₁ÚX₂ÚX₃)×(X₁ÚX₂ÚX₃) – СКНФ (функции f).

Пример 2:

f=X×Y×ZÚ X×Y×ZÚ X×Y×ZÚ X×Y×ZÚ X×Y×ZÚ X×Y×Z

2 7 0 5 4 3

f= X×Y×ZÚ X×Y×Z≡(XÚYÚZ)×(XÚYÚZ)

6 1

Переход от СКНФ к СДНФ.

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

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

f=(XÚYÚZ)×(XÚYÚZ)

f=(XÚYÚZ)×(XÚYÚZ)×(XÚYÚZ)×(XÚYÚZ)×(XÚYÚZ)×(XÚYÚZ)≡

≡X×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×Z