3. Расчёт мднф функции методом Квайна.

   1. Минимизация функции а по Квайну.

Таблица 3 – Таблица истинности для функций a и g

	a	g
0000	1	0
0001	0	0
0010	1	1
0011	1	1
0100	0	1
0101	1	1
0110	1	1
0111	1	0
1000	1	1
1001	1	1
1010	1	1
1011	1	1
1100	0	1
1101	0	1
1110	x	x
1111	x	x

Совершенная Дизъюнктивная Нормальная Форма функции a:

a =

М

ножества 0-кубов после разбиения и упорядочения записываются следующим образом (галочками отмечены кубы, на которые возможно воздействие операцией склеивания):

0	0	1	0	0	1	0	1	0	1	1	1
0	0	0	0	1	0	1	0	1	0	1	1
0	1	0	1	0	0	1	1	1	1	1	1
0	0	0	1	1	1	0	0	1	1	0	1

Столбцы, отмеченные символом – конституенты x-ов в таблице истинности для функции a.

Производя последовательно операцию склеивания кубов, получаем следующее множество 1-кубов:

0	x	0	0	x	1	1	0	x	0	1	0	x	1	1	x	1	1
0	0	0	x	0	0	0	x	0	1	0	1	1	0	x	1	x	1
x	0	1	1	1	0	x	1	1	x	x	1	1	1	1	1	1	1
0	0	x	0	0	x	0	1	1	1	1	x	0	x	0	1	1	x

Получаем следующее множество 2-кубов: Составим 3-куб:

x	0	x	x	1	x	x	1
0	x	0	x	0	x	1	x
x	1	1	1	x	1	1	1
0	x	x	0	x	1	x	x

x

x

1

x

ДНФ функции a:

Составим таблицу покрытий для a (таблица 4).

Таблица 4 – Таблица покрытий для функции a

	0000	0010	0011	0101	0110	0111	1000	1001	1010	1011	1110	1111
01x1
x0x0
10xx
xx1x

Видим, что все импликанты оказались вычеркнутыми, значит экстремалями являются: 01x1, x0x0, 10xx, xx1x.

МДНФ функции совпадает с ДНФ:

.

Совершенная Дизъюнктивная Нормальная Форма функции g:

g =

М

ножества 0-кубов после разбиения и упорядочения записываются следующим образом (галочками отмечены кубы, на которые возможно воздействие операцией склеивания):

0	0	1	0	0	1	0	1	1	1	1	1	1
0	1	0	0	1	0	1	0	1	0	1	1	1
1	0	0	1	0	0	1	1	0	1	0	1	1
0	0	0	1	1	1	0	0	0	1	1	0	1

Производя последовательно операцию склеивания кубов, получаем следующее множество 1-кубов (заметим, что нам понадобились оба столбца с переменными x):

0	0	x	0	0	x	1	1	1	x	x	1	1	x	1	1	1	1	1	1	1
0	x	0	1	1	1	0	0	x	0	1	0	x	1	0	x	1	1	x	1	1
1	1	1	0	x	0	0	x	0	1	0	x	0	1	1	1	0	x	1	x	1
x	0	0	x	0	0	x	0	0	1	1	1	1	0	x	0	x	0	1	1	x

Получаем следующее множество 2-кубов: Составим 3-куб:

1

x

x

x

x	x	x	x	1	1	1	1	1	1
0	x	1	1	0	x	x	x	x	1
1	1	0	x	x	0	x	x	1	x
x	0	x	0	x	x	0	1	x	x

ДНФ функции g:

Составим таблицу покрытий для g (таблица 4).

Таблица 4 – Таблица покрытий для функции g

	0010	0011	0100	0101	0110	1000	1001	1010	1011	1100	1101	1110	1111
x01x
xx10
x10x
x1x0
1xxx

Видим, что экстремалями оказались 3 из 5 конституент, а в дополнительную таблицу входят только две импликанты из столбца 0101, поэтому в качестве экстремали берём любую из них, например xx10, тогда МДНФ функции g: .