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

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

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

Приклад 1 повної системи. Система є повною.

Приклад неповної системи. Система не є повною.

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

,

,

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

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

, ,…,.

Підставимо ці формули в формулу . Отримаємо:

.

Останній вираз визначає формулу в системі , яка має структуру , тобто виразили у вигляді формули через функції системи .□

Отже, теорема дозволяє зводити питання про повноту одних систем до питання про повноту інших систем.

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

Доведення випливає з принципу двоїстості.

Спираючись на ці теореми, можна встановити повноту ще декількох систем і розширити список прикладів повних систем.

Приклади повних систем.

2. .

Дійсно, візьмемо за систему систему , а за систему – дану систему . Скористаємося рівносильністю . В результаті будь-яка булева функція, зображена формулою через функції системи виявиться зображеною формулою через функції системи , тобто система є повною.

3. .

4. .

5. .

6. .

7. Система , де – додавання за модулем 2, є повною.

З наведених прикладів видно, що існує ціла низка повних систем функцій. Кожна з цих систем може бути прийнята за множину основних елементарних функцій. Таким чином, для зображення булевої функції можна використовувати різні повні системи.

Означення. Система функцій називається базисом, якщо вона є повною, але будь-яка її підсистема не буде повною.

Приклад. Система є базисом, який прийнято називати стандартним.

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

1. I. Органи і системи, що забезпечують функцію виділення
2. I. Особливості аферентних і еферентних шляхів вегетативного і соматичного відділів нервової системи
3. II. Анатомічний склад лімфатичної системи
4. IV. Розподіл нервової системи
5. IV. Система зв’язків всередині центральної нервової системи
6. IV. Філогенез кровоносної системи
7. POS-системи
8. VI. Філогенез нервової системи
9. Автокореляційна характеристика системи
10. АВТОМАТИЗОВАНІ СИСТЕМИ ДИСПЕТЧЕРСЬКОГО УПРАВЛІННЯ
11. АВТОМАТИЗОВАНІ СИСТЕМИ УПРАВЛІННЯ ДОРОЖНІМ РУХОМ
12. Автоматизовані форми та системи обліку.

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