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.


 

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

53108. ЗАСТОСУВАННЯ ІННОВАЦІЙНИХ ТЕХНОЛОГІЙ У НАВЧАННІ ГЕОГРАФІЇ 355.5 KB
  Мета: поглибити знання учнів про особливості природи океану; продовжити формування навичок роботи з картами; практично застосовувати знання з біології фізики хімії; розвивати критичне та логічне мислення; посилювати інтерес до знань. Які асоціації викликало у вас слово ОКЕАН Отже: Тихий океан складова частина Світового океану велетенська природна водойма. Запрошую вас до співпраці в експедиції з вивчення Тихого океану. Географічне положення розміри океану.
53109. Сучасний кабінет географії – простір співпраці вчителя та учня 156.5 KB
  Соціальним замовленням суспільства сьогодні є самоствердження та самореалізація особистості через ефективне навчання розвиток творчих здібностей учнів формування загальних та спеціальних вмінь та навичок. Навчання буде успішним якщо в учителя є можливість працювати в сучасному кабінеті де оптимально поєднано використання всіх видів навчального методичного забезпечення та технічного обладнання відповідно до вимог наукової організації праці вчителя і учня. Головною роллю кабінету визначаю необхідність його як місця спілкування...
53110. Південна Америка. Історія дослідження. Географічне положення 54 KB
  Мета: сформувати в учнів загальне уявлення про географічне положення площу та форму материка поглибити систему знань учнів про відкриття та дослідження Південної Америки; удосконалити практичні навички учнів характеризувати географічне положення материка. Чому важливо знати географічне положення материка 3. Мотивація навчальної і пізнавальної діяльності Колись Південну Америку з ласки мореплавця Америго Веспуччі назвали Новим Світом у джунглях цього материка блукали герої книги Жюля Верна Діти капітана Гранта. Сучасні уявлення про цю...
53111. Використання основних аспектів освіти для сталого розвитку та показано діяльнісну спрямованість уроків географії в системі ОСР 6.37 MB
  Обґрунтовано зміну ролі вчителя в моделі емпауерменту та визначено діяльність як основний засіб навчання і виховання людини спроможної до забезпечення сталого розвитку суспільства. Ми працюємо щоб зробити нове відкриття Єдиний шлях що веде до знань це діяльність.Шоу Будьяка діяльність або бездіяльність призведе до певного результатутільки якого. Тому входження в систему ОСР на уроках географії відбувається в двох площинах: перша площина забезпечує виховання здорової ціннісно орієнтованої толерантної полікультурної...
53112. Географія світових природних ресурсів 46.5 KB
  Сформувати у учнів систему знань про ресурсозабеспеченність окремих територій Землі певними видами ресурсів; систематизувати уявлення учнів про мінеральні земельні лісні водні рекреа ційні ресурси; розвивіти вміння учнів самостійно працювати з картографічним матеріалом і статестичним матеріалом;...
53113. Глобальное потепление. Начало развития геоинженерии 61 KB
  Учитель. Учитель В прессе идея глобального потепления мусируется давно. А рыбе понравится Учитель Можно запустить на орбиту 16 триллионов зеркал диаметром 70 см общим весом 20 млн тонн и они будут отражать солнечные лучи.
53114. ВІК І ПОШИРЕННЯ ГІРСЬКИХ ПОРІД. ЗМІНА ПРИРОДНИХ УМОВ ТЕРИТОРІЇ ПОЛТАВЩИНИ У РІЗНІ ЕРИ. ГЕОЛОГІЧНА КАРТА ПОЛТАВЩИНИ 394 KB
  Унаочнення: підручник геохронологічна таблиця географічний атлас Полтавська область зразки мінералогічної колекції скамянілостей описи відслонень гірських порід. Як визначається абсолютний і відносний вік гірських порід 3. До магматичних та метаморфічних порід протерозою приурочені поклади чорних та кольорових металів і нерудної сировини у південній частині області.
53115. УКРАЇНОЗНАВСТВО В ДОШКІЛЬНОМУ ЗАКЛАДІ 1018.5 KB
  Ряд орієнтовних конспектів занять з різних розділів програми, сценарії свят та розваг, опис ігор та додатковий художній матеріал, які можна використати в роботі. Заняття мають в основному комплексний характер, що позитивно впливає не тільки на ознайомлення з культурою, побутом свого народу, але і на розвиток мовлення дітей. Запропоновані конспекти занять та сценарії свят апробовані...