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

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

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

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

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

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

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Клас – клас всіх монотонних функцій.	\|	Теорема (Теорема про достатність чотирьох функцій.) З будь-якої повної в системи функцій можна виділити повну підсистему, яка складається не більше ніж з чотирьох функцій.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.