Page 41 - 4496

1
де F - елементарна кон'юнкція рангу r ; i - номера наборів
i
1
(кортежів), на яких функція F дорівнює одиниці.
i
Означення 4. ДДНФ перемикальної функції називається
диз'юнкція тих конституент (мінтермів) одиниці, які
перетворюються в одиницю на тих самих наборах, що і сама
функція.
Будь-яка перемикальна функція має одну ДДНФ
(кількість її членів дорівнює кількості одиничних функцій на
значеннях наборів) і кілька ДНФ.
Будь-яку ДНФ можна утворити із ДДНФ внаслідок
скорочення останньої. Такий перехід називається
розгортанням.
f (x 0 , x 1 , x 2 , x 3 )  x 1 x 2  x 0 x 2  x 0 x 1 x 2  x 2  x 3 

x 1 x 2 (x  x 0 ) (x  x 3 )  x 0 x 2 (x  x 1 ) (x  x 3 ) + x 2 (x  x 0 )
0
3
3
0
1
(x  x 1 ) (x  x 3 ) + x 0 x 1 x 2 (x 3  x 3 )  x 3 (x  x 0 ) (x  x 1 )
0
3
1
1
(x  x 2 ) .
2
Властивості ДДНФ:
а) в неї немає однакових доданків;
б) жоден із доданків не вміщує однакових
співмножників;
в) жоден із доданків не вміщує змінну разом з її
запереченням;
г) в кожному окремому доданку є як співмножник або
змінна х і ,або заперечення для будь-якого х і i 1 n , .
Приклад: Задана логічна функція
f (x )  (x  x 2 )  x 2 x 3 . Для неї знайти ДДНФ.
1
Задамо функцію f (x ) у вигляді таблиці істиності
x 1 x 2 x 3 x 1  x 2 x x 3 f
2
0 0 0 0 0 1

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

38