67607

Полнота и замкнутость

Лекция

Математика и математический анализ

Система функций из P2 (множества всех булевых функций) называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы

Русский

2014-09-12

131.5 KB

1 чел.

Лекция № 16  (11.04.00)

Полнота и замкнутость

Опр || система функций  из P2 (множества всех булевых функций) называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Пример: 1) Само множество ;

2);

3) - не полна.

Теорема || Пусть даны две системы функций из

, (I)

. (II)

Известно, что система I полная и каждая функция системы I выражается через функции системы II. Тогда система II является полной.

Доказательство || Пусть . В силу полноты сист. I функцию h можно выразить в виде формулы . По условию теоремы

Поэтому

ч. и т.д.

Примеры ||

1)  - полная.

2)  - тоже полная, так как .

3)  - тоже полная.

4)  - тоже полная, так как

,

,

. ((2) – I)

5)  - неполная. Докажем это от противного.

Предположим, что .

Но . Противоречие.

6)  - неполная (сохраняет константу 0 – см. след лекц.).

7)  - неполная (сохраняет константу 1 – см. след лекц.).

6)  -  полная

8)  

тогда взяв в качестве сист. I сист. 2) можно заключить, сист. функций 8) – полная. Тем самым, справедлива

Теорема Жегалкина || Каждая функция из  может быть выражена при помощи полинома по модулю 2 – (полинома Жегалкина):

.

Имеем: число разных сочетаний  равно числу подмн-в мн-ва из n элементов. Каждое aik может принимать одно из 2-х значений {0,1}. Тогда число разных пол. Жег. равно , т.е. равно числу различных булевых функций.

Т. о. получаем единственность представления функций через пол. Жег.

Примеры

Следовательно,

Пока опустим

2 способ T-преобразов. вектора функции

X1

x2

x3

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

3 способ – алгебраических преобразований

Опр. Пусть M – некоторое подмножество функций из P2. Замыканием M называется мн-во всех булевых функций, представимых в виде формул через функции мн-ва M. Обозначается [M].

Замечание. Замыкание инвариантно относ. операций введения и удаления фиктивных перем.

Примеры.

1) M=P2, [M]=P2.

2) M={1,x1x2}, [M] – мн-во L всех линейных ф-й вида

,   (ci{0,1}).

Свойства замыкания:

  1.  [M]=M;
  2.  [[M]]=[M];
  3.  M1M2  [M1][M2];
  4.  [M1M2][M1][M1].

Опр. Класс (мн-во) M называется (функционально) замкнутым, если [M]=M.

Примеры.

  1.  Класс M=P2 функционально замкнут;
  2.  Класс {1,x1x2} не замкнут;
  3.  Класс L замкнут (линейное выражение, составленное из линейных выражений линейно).

Новое определение полноты. M – полная система, если [M]=P2.


 

А также другие работы, которые могут Вас заинтересовать

38422. Встановлення, налаштування і оптимізація операційної системи MS Windows 7 в покроковому режимі 2.88 MB
  Вміння налаштувати операційну систему, дозволить уникнути багатьох неприємностей і незручностей: елементарний захист комп’ютера від несанкціонованого доступу, неналежне налаштування роздільної здатності і частоти оновлення екрану, залишки деінстальованих програм, а також помилки в самій операційній системі, які можуть призвести до помітного зниження швидкодії комп'ютера і втрати даних на жорсткому диску і т.п.
38423. ОПТИМИЗАЦИЯ АВТОМАТИЗИРОВАННОГО УЧАСТКА ОБРАБОТКИ СТУПИЦЫ ВЕДОМОГО ДИСКА СЦЕПЛЕНИЯ 2.45 MB
  2 Определение количества и типа основного и вспомогательного технологического оборудования 45 3.4 Технологическое проектирование вспомогательных служб участка 50 Материалы и грузооборот участка 62...
38425. Проект строительства жилого комплекса трех 8- 9-этажных блок-секций в городе Кингисепп 151.23 KB
  Реализация инвестиционной политики требует повышения уровня индустриализации капитального строительства. Под нее предстоит подвести принципиально новую материально-техническую базу. Предусматривается увеличение числа объектов из элементов заводского изготовления, поставка средств ручной механизации, расширение применения новых строительных материалов.
38426. Разработка бета версии технологического цикла виртуального ателье по пошиву одежды 1.16 MB
  Техникоэкономическое обоснование работы 2. Целью данной работы является создание программного продукта с помощью которого можно будет упростить изучение машин. Это дает возможность создавать на основе данной работы широкий круг компьютерных моделей. Техникоэкономическое обоснование работы При компьютерном моделировании процессов изготовления швейных изделий одним из важных вопросов является выполнение экономических расчетов.
38427. Поліетилен та його основні хімічні властивості 193.76 KB
  0 обємна чаcтка суми метану з етаном не більше 010 обємна чаcтка суми вуглеводнів С3 і С4 ррm не більше 50 обємна чаcтка ацетилену ррm не більше 10 обємна частка окису вуглецю ррm не більше 5 обємна частка двоокису вуглецю ррm не більше 10 обємна частка водню ррm не більше 10 обємна чаcтка загальних карбонілів в перерахунку на МЕК ррm не більше 1 обємна чаcтка кисню ррm не більше 3 масова чаcтка загальної сірки ррm не більше 1 масова чаcтка хлору ррm не більше 1 обємна чаcтка води ррm не більше 10 обємна чаcтка...
38428. Топографо-геодезические работы в Янаульском и Татышлинском районе для прокладки оптово-волоконно-кабеля связи 609.49 KB
  Целью изысканий является получение топографических материалов необходимых и достаточных для разработки проекта строительства волоконнооптической линии связи. Более эффективно волоконнооптический кабель 9 125 с полимерными волокнами работает за счет способности не воспринимать влияние электромагнитных сигналов и радиоволн. При выполнение дипломного проекта нами были проведены топографогеодезические работы в Янаульском и Татышлинском районе по проходящем там линиям электропередач данные изыскания были основой для прокладки...
38429. Исследование теории робастного управления и применение ее методов к решению задачи стабилизации бокового движения ЛА 2.34 MB
  На современном этапе основными объектами управления являются системы работающие в условиях неопределенности т. Системы автоматического и полуавтоматического управления полетом относятся в настоящее время к числу наиболее важных и стремительно развивающихся систем летательных аппаратов ЛА. Системы управления самолетов вертолетов и других пилотируемых ЛА все в большой мере становятся комплексными обеспечивающими все основные этапы полета.
38430. Многокритериальный анализ решений по обеспечению безопасности техногенного объекта с расширенным понятием безопасности 735 KB
  Экспертные подходы многокритериальных принятий решений на основе сравнений многокритериальных альтернатив обеспечения социотехнической безопасности техногенного объекта ТО Определение наилучшей альтернативы. Методы ELECTRE ранжирования многокритериальных альтернатив. Применения МАИ для многокритериальных сравнений альтернатив оценки безопасности техногенного объекта