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.


 

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

73231. Обучение детей младшего школьного возраста анализу произведений изобразительного искусства 178.5 KB
  Тогда как именно знакомство со структурой художественного произведения и с законами восприятия искусства должно актуализировать исследовательскую позицию учащегося благодаря которой он сможет самостоятельно постигнуть смысл живописного или графического произведения освоить способы художественного мышления. Однако при обращении к произведениям искусства учитель чаще всего выступает в качестве всезнающего лектора ученик же в качестве пассивного зрителя и слушателя. До сих пор не существует технологий и методик благодаря которым учащиеся...
73232. Разработка международной стратегии продвижения товара 749.5 KB
  Теоретический анализ разработки международной стратегии продвижения товара; исследование особенностей международных стратегий ВЭД предприятий; анализ финансовой, хозяйственной, внешнеэкономической и маркетинговой деятельности предприятия; разработка стратегии выхода предприятия на зарубежный рынок.
73233. АНТРОПОЦЕНТРИЧЕСКАЯ ОЦЕНКА МОРАЛЬНОЙ РАСПУЩЕННОСТИ В СОВРЕМЕННОМ АНГЛИЙСКОМ ЯЗЫКЕ 36.85 KB
  Семантическая структура языка являет собой языковое воплощение всех нюансов восприятия действительности его носителями всех представлений и переживаний присущих народу создавшему язык. Поэтому каждый язык это своеобразное зеркало отражающее определённое видение мира неповторимое мироощущение народа сотворившего его сегментацию внутреннего и внешнего мира представленную отдельными структурами и...
73234. Механизм воздействия рекламы на потребителя на примере компании P and G 1.41 MB
  Определить содержание понятия «реклама». Выявить основные характеристики и функции рекламы. Проанализировать воздействие рекламы на потребителя. Выявить основные механизмы воздействия рекламы на потребителей используемые ведущими мировыми компаниями, в частности...
73235. Межпоколенная коммуникация 124 KB
  Семья – это общественная ячейка, в которой одновременно уживаются представители разных поколений. В связи с меняющимися ценностями и интересами, не редко возникают конфликты между членами семьи, потому как каждый пытается доказать свою точку зрения как единственно верную.
73236. Экономика электроснабжения 1.02 MB
  Электроэнергетика, ведущая область энергетики. Без которой невозможно стабильное развитие промышленности, сельского хозяйства, транспорта, коммунальных хозяйств, невозможно развитие средств связи, вычислительной и космической техники
73237. ДИНАМИКА КУЛИСНОГО МЕХАНИЗМА 391.45 KB
  Заданы массы звеньев механизма; величина вращающего момента; радиус инерции катка и радиусы его ступеней; радиус маховика представляющего собой сплошной однородный цилиндр. Определить: Угловую скорость маховика при его повороте на угол. Угловое ускорение маховика при его повороте на угол.
73238. Расчет цеха производства рыбных продуктов 119.83 KB
  Нежность мягкость рыбы острота вкусовых и ароматических ощущений обилие приправ и специй пряностей ароматических трав соусов все это способствует приготовлению широкого ассортимента вкусных блюд из рыбы. Наиболее богатыми белком видами рыб считаются лосось форель семга белуга другими словами все рыбы отрядов лососевые и осетровые. В наибольшей степени это касается жирных морских сортов рыбы лосось скумбрия сельдь форель семга и др. Естественно следует учитывать что при длительном хранении заморозке не говоря уже о...
73239. Коррекция страхов у детей дошкольного возраста 217.5 KB
  Страхи, эмоциональные нарушения поддаются коррекции и без последствий проходят у детей до десяти лет. Поэтому чрезвычайно важно своевременно обращаться к специалисту, принять меры по преодолению фобий у ребёнка.