• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Приведення булевих функцій до досконалих диз’юнктивних і кон’юнктивних нормальних форм

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

Якщо булева функція задана таблицею, то мають місце формули, які дають зображення булевої функції досконалою диз’юнктивною або кон’юнктивною нормальною формою.

Теорема (про зображення булевих функцій досконалими нормальнимиформами).

1. Будь-яку булеву функцію, відмінну від константи нуль: (), можна єдиним чином з точністю до перестановки диз’юнктивних доданків зобразити ДДН формою:

, де

2. Будь-яку булеву функцію, відмінну від константи одиниця (), можна єдиним чином з точністю до перестановки кон’юнктивних доданків зобразити ДКН формою:

, де

Наслідок. Будь-яка булева функція може бути зображена у вигляді формули через .

Дана теорема носить конструктивний характер, оскільки вона дозволяє для кожної булевої функції фактично побудувати формулу, яка її реалізує (у вигляді ДДНФ або ДКНФ). Відзначимо, що ДДНФ (ДКНФ) формули містить стільки кон’юнкцій (диз’юнкцій), скільки одиниць (нулів) в таблиці істинності функції.

З теореми випливає

Читайте також:

1. Аденогіпофіз, його гормони, механізм впливу, прояви гіпер- та гіпофункцій.
2. Аутентифікація з використанням односторонніх функцій
3. Будинків іспоруді забезпечення нормальних умов їх будівництва й експлуатації
4. Важкість праці: Динамічні, статичні навантаження. Напруженість праці. Увага, напруженість аналізаторних функцій, емоційна та інтелектуальна напруженість, монотонність праці.
5. Види договорів і контрактів. Розподіл функцій учасників проекту
6. Види приведення даних
7. Види функцій державного управління
8. Визначення нормальних напружень
9. Визначення нормальних напружень при згинанні
10. Виконання лінійної регресії за допомогою функцій Excel
11. Вона є важливим органом, який виконує ряд функцій
12. Вона є важливим органом, який виконує ряд функцій

Переглядів: 1216