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

Критерій повноти системи булевих функцій

Згадаємо, що система булевих функцій називається повною (функціонально повною), якщо будь-яка булева функція може бути записана як композиція функцій цієї системи.

Теорема (Теорема Поста про повноту). Для того, щоб система функцій =була повною, необхідно и достатньо, щоб вона не містилася цілком в жодному з класів , , , ,.

Наслідок. Будь-який замкнений клас функцій з Р₂, який не збігається з Р₂, міститься принаймні в одному з замкнених класів , , , ,.

Для перевірки функціональної повноти системи булевих функцій будується таблиця Поста, в якій відмічається належність функцій замкненим класам. Якщо у кожному стовпці таблиці Поста є хоча б один мінус – система повна, інакше – ні.

Приклад.Перевірити функціональну повноту системи булевихфункцій .

Розв’язання. Перевіримо належність замкненим класам функції . Побудуємо таблицю істинності даної функції:

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

1. I. Органи і системи, що забезпечують функцію виділення
2. I. Особливості аферентних і еферентних шляхів вегетативного і соматичного відділів нервової системи
3. II. Анатомічний склад лімфатичної системи
4. II. Критерій найбільших лінійних деформацій
5. IV. Критерій питомої потенціальної енергії деформації формозміни
6. IV. Розподіл нервової системи
7. IV. Система зв’язків всередині центральної нервової системи
8. IV. Філогенез кровоносної системи
9. POS-системи
10. ReM – модифікований критерій Рейнольда, який визначається за формулою
11. VI. Філогенез нервової системи
12. Автокореляційна характеристика системи

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