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.


 

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

52164. Зелений агресор – амброзія полинолиста 100 KB
  Цілі: На прикладі амброзії полинолистої показати роль рослин в екосистемах. Тип уроку: практична робота з елементами бесіди Обладнання: гербарій амброзії полинолистої мультимедійна презентація робочий зошит Організаційний момент Мотивація навчальної діяльності Учитель. На мультимедійній дошці з’являється слайд з зображенням амброзії полинолистої Як ви здогадалися це – амброзія полинолиста.Розглянути слайд презентації та гербарний екземпляр амброзії полинолистої.
52165. Північна Америка. Загальні відомості, особливості фізико-географічного положення, Історія відкриття та освоєння Північної Америки 46 KB
  Тема уроку: Північна Америка. Обладнання: атласи контурні карти стінні карти Північна Америка Карта півкуль підручник слайди для мультимедійної дошки. Отже ми починаємо вивчати материк Північна Америка. Розповідь вчителя За своєю площею 204 млн км2а з островами 244 млн км2 Північна Америка посідає третє місце серед континентів планети.
52166. ПІВНІЧНА АМЕРИКА 67 KB
  Завдання етапу: Назвіть і покажіть на карті крайні точки материка. За яким планом вивчають материк Розкажіть план характеристики географічного положення материка та поясніть чому опис материка починається з характеристики його географічного положення 4.Опишіть географічне положення материка.Яка площа Північної Америки Порівняйте з іншими материками.
52167. Населення та політична карта Північної Америки. Українська діаспора 69.5 KB
  Міхелі фізична карта світу політична карта світу атласи таблиці картини про США та Канаду. Найбільші країни – це США Канада Мексика а також на крайньому півдні та островах Карибського моря багато дрібних за площею держав та залежних територій.197 Виписати країни та їх столиці учні виписують к стовпчик за зразком США Вашингтон Канада – Оттава...
52168. Геологічна будова та рельєф Північної Америки. Корисні копалини 50 KB
  Мета: сформувати нові поняття; дати знання про особливості будови земної кори Північної Америки та залежність рельєфу від геологічної будови материки; сформувати знання про вплив на рельєф материка ендогенних і екзогенних сил; закріпити знання про зв'язок між складом гірських порід і розміщенням родовищ...
52169. Геологічна будова та рельєф Північної Америки. Корисні копалини 310.5 KB
  Мета: сформувати нові поняття; дати знання про особливості будові земної кори Північної Америки та залежність рельєфу від геологічної будови материка; ; сформувати знання про впив на рельєф материка ендогенних та екзогенних сил; закріпити знання про зв`язок між складом гірських пород і розміщення родовищ корисних копалин; продовжувати формування навичок аналізу тематичних карт; розвивати увагу спостередливість творчі здібності. Обладнання: фізична карта Північної Америки атлас підручник. Географічне положення Північної Америки.
52170. Население и политическая карта Северной Америки 121.5 KB
  Цель: дать характеристику населения Северной Америки численность неравномерность размещения по территории расовый состав и политической карты материка. Прерии Северной Америки расположены: а в Кордильерах; б на Великих и Центральных равнинах; в на побережье Атлантического океана; г на севере материка. Какие факторы нарушают зональность природы материка а морские течения; б рельеф; в изрезанность береговой линии. Кем и в каком году была открыта Америка Колонизация материка изменила состав населения.
52171. Географічне положення Північної Америки. Історія відкриття та освоєння материка 31 KB
  Історія відкриття та освоєння материка. Практична робота №8 продовження Мета: cформувати в учнів знання про основні риси географічного положення материка удосконалювати роботу з картами; розвивати пізнавальний інтерес вміння працювати в колективі аналізувати робити висновки; виховувати культуру спілкування самостійність розширювати кругозір дітей щодо історії відкриття та освоєння материка. Колумба план вивчення материка відео...
52172. Нові індустріальні країни Латинської Америки 667.5 KB
  Мета: узагальнення і систематизація знань по темі: Латинська Америка методом формування географічного мислення і творчих здібностей шляхом розвитку умінь самостійно працювати з географічним матеріалом; вирішення проблеми відторгнутих в класному колективі підвищення їх соціального статусу методом зацікавленості особи в участі в ігрових видах діяльності; виховання пізнавального інтересу пошани до народів інших країн самостійності і цивільної...