Специальная математика (стр. 7 )

15. A | B ≡ A×B ≡ A Ú B

16. A ¯ B ≡A Ú B ≡A×B

17. Операция склеивания.

A×B Ú A×B ≡ A

2.1.4. Формы представления высказываний

1. Форма А1 Ú А2 Ú ... Ú Аn, где Аi, - элементарное высказывание или отрицание элементарного высказывания (литерал), называется элементарной дизъюнкцией.

2. Форма B1 × B2 × ... × Bn, где Bi - литерал, называется элементарной конъюнкцией.

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

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

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

f=X1×X2×X3Ú X1×X2×X3Ú X1×X2×X3Ú X1×X2×X3

0 1 2 4

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

f = X1×X2×X3Ú X1×X2×X3Ú X1×X2×X3Ú X1×X2×X3 ≡

≡ (X1ÚX2ÚX3)×(X1ÚX2ÚX3)×(X1ÚX2ÚX3)×(X1ÚX2ÚX3) – СКНФ (функции 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

2.1.6. Минимизация высказываний методом Квайна

1. Выражение из произвольной формы приводится к СДНФ.

2. Выполнив в СДНФ все возможные неполные склеивания, а затем все возможные поглощения мы получим Сокращенную ДНФ (СкДНФ). Конъюнкции в СкДНФ называются импликантами.