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


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


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


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


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


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


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


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


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


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



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

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

Приклад 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. Автоматизовані форми та системи обліку.




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

<== попередня сторінка | наступна сторінка ==>
За допомогою рівносильних перетворень | Зображення булевої функції многочленом Жегалкіна

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

 

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


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