Теорема Шенона про розкладання булевих функцій

Теорема Шенона. Будь-яка булева функція може бути зображеною у вигляді розкладання Шеннона за змінними:

(10.6)

де , , – первинні терми.

Наслідок. Граничне розкладання Шеннона при булевої функції має вигляд

(10.7)

і є ДДНФ функції .

Теорема Шеннона є справедлива й у кон’юнктивній формі:

(10.8)

які в межі при є ДКНФ функції:

. (10.9)

10.5 Контрольні запитання

1. Як визначається первинний терм?

2. Що являє собою елементарна кон’юнкція?

3. Що називається ДНФ функції?

4. Що таке елементарна диз’юнкція?

5. Що таке КНФ?

6. Як визначається ДДНФ?

7. Чим відрізняються ДНФ і КНФ?

8. Чим відрізняються ДНФ і СДНФ?

9. Як визначається ДКНФ?

10. Чим відрізняються КНФ і СКНФ?

11. Як складається ДДНФ за таблицею істинності?

12. Як можна одержати ДКНФ за таблицею істинності?

13. Як визначається складність формули?

14. Як визначається оцінка складності за Квайном?

15. Що являє собою розкладання Шеннона?

16. Що таке граничне розкладання Шеннона?

11 ЕЛЕМЕНТИ ЛОГІЧНИХ СХЕМ. БУЛЕВІ ФУНКЦІЇ

ВІД ДВОХ ЗМІННИХ

Розглядаються основні властивості, фізичний зміст і схемотехнічне зображення булевих функцій від двох змінних для застосування їх при синтезі логічних схем.