Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

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

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

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

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

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

 


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

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




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

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

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

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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