Курс лекцій для студентів спеціальностей, пов’язаних з інформаційними технологіями та


ФУНКЦІОНАЛЬНО ПОВНІ МНОЖИНИ БУЛЕВИХ ФУНКЦІЙ



Сторінка12/16
Дата конвертації27.01.2020
Розмір1,37 Mb.
ТипКурс лекцій
1   ...   8   9   10   11   12   13   14   15   16
ФУНКЦІОНАЛЬНО ПОВНІ МНОЖИНИ БУЛЕВИХ ФУНКЦІЙ

Множина булевих функцій Р називається функціонально повною, якщо будь-яка булева функція може бути подана як суперпозиція над Р.

Прикладами функціонально повних множин булевих функцій є множини {, , }, {, } та {, }. Це випливає з твердження 4 та з еквівалентностей ху = (ху), ху = (ху). Не кожна множина булевих функцій є функціонально повною. Наприклад, множина М не є функціонально повною, адже вона не містить немонотонних булевих функцій, й жодну немонотонну булеву функцію (а такі існують) не можна побудувати як суперпозицію над М.

Теорема Поста (критерій повноти множини булевих функцій). Множина булевих функцій Р є функціонально повною тоді й тільки тоді, коли не виконується жодне включення: РT0, PT1, PL, PS, PM (тобто Р містить принаймні одну булеву функцію, що не зберігає константу 0, принаймні одну булеву функцію, що не зберігає константу 1, принаймні одну нелінійну булеву функцію, принаймні одну несамодвоїсту булеву функцію, принаймні одну немонотонну булеву функцію).


Каталог: bitstream -> 123456789
123456789 -> Тема: Безпека вулиці: азбука дороги
123456789 -> Методичні вказівки до вивчення дисципліни сво «доктор філософії»
123456789 -> Регіональний підхід до дослідження формування ціннісних орієнтацій студентів мистецьких вишів україни н. Г. Тарарак
123456789 -> Методологічне підґрунтя дослідження формування ціннісних орієнтацій студентів вищих навчальних закладів мистецького профілю україни
123456789 -> Загальна характеристика роботи
123456789 -> Інформаційне суспільство в контексті політичної культури суспільства
123456789 -> Заліщицька районна державна адміністрація Відділ з питань освіти Районний методичний кабінет Використання активних та інноваційних технологій як засіб активізації
123456789 -> Україна тернопільська область опис досвіду роботи учителя біології


Поділіться з Вашими друзьями:
1   ...   8   9   10   11   12   13   14   15   16


База даних захищена авторським правом ©pedagogi.org 2019
звернутися до адміністрації

    Головна сторінка