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

UptoLike

ВУЗ: 

ПНИПУ | Пермь

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

Рубрика: 

Отрицание функци 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
0 1 2 4
А теперь применим отрицание к функции 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
≡
≡ (X
1
X
2
X
3
)(X
1
X
2
X
3
)(X
1
X
2
X
3
)(X
1
X
2
X
3
) – СКНФ (функции f).
Пример 2:
f=XYZ XYZ XYZ XYZ XYZ XYZ
2 7 0 5 4 3
f= XYZ XYZ≡(XYZ)(XYZ)
6 1
Переход от СКНФ к СДНФ.
Возьмем логическую функцию f в СКНФ и построим отрицание этой функции, т.е.
функцию f, путем выписывания всех конституент нуля, не входящих в f.
Пусть f имеет вид
f=(XYZ)(XYZ)
f=(XYZ)(XYZ)(XYZ)(XYZ)(XYZ)(XYZ)≡
≡XYZXYZXYZXYZXYZXYZ
2.1.6. Минимизация высказываний методом Квайна
1. Выражение из произвольной формы приводится к СДНФ.
2. Выполнив в СДНФ все возможные неполные склеивания, а затем все возможные
поглощения мы получим Сокращенную ДНФ (С
к
ДНФ). Конъюнкции в С
к
ДНФ называются
импликантами.
Примечание: Склеивание: XY XY ≡ X
Неполное склеивание: XY XY ≡ X XY XY
3. На основании С
к
ДНФ и СДНФ строим импликантную матрицу и путем нахождения
минимального покрытия этой матрицы получаем минимальную дизъюнктивную
нормальную форму (МДНФ).
Пример 1:
f = XYZ XYZ XYZ XYZ XYZ
(I) (II) (III) (IV) (V)
— 25 —
Отрицание функци 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. Выполнив в СДНФ все возможные неполные склеивания, а затем все возможные
поглощения мы получим Сокращенную ДНФ (СкДНФ). Конъюнкции в СкДНФ называются
импликантами.

Примечание: Склеивание: XY  XY ≡ X
           Неполное склеивание: XY  XY ≡ X  XY  XY

3. На основании СкДНФ и СДНФ строим импликантную матрицу и путем нахождения
минимального покрытия этой матрицы получаем минимальную дизъюнктивную
нормальную форму (МДНФ).


Пример 1:

f = XYZ  XYZ  XYZ  XYZ  XYZ
     (I)     (II)     (III)   (IV)     (V)


                                          — 25 —

Страницы