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.


 

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

82413. Неокантианство 36.93 KB
  Ничто в рамках мыслительных потенций университетской философии не указывало на возможность какойлибо продуктивной кооперации между Гегелем и скажем Г. Налицо оказывалась двоякая угроза: научно несостоятельной философии с одной стороны и философски беспризорной науки с другой. Если опасность научно не фундированной философии лежала в ее открытости мистическим соблазнам то опасность философски не защищенной науки заключалась в стихийных порывах наивно материалистического толкования. спор о материализме в результате которого...
82414. Неогегельянство 29.04 KB
  Стерлинга впервые познакомившего англичан с философией Гегеля Э. внеэмпирической реальности Брэдли; в тенденция к преодолению крайностей абсолютного идеализма Брэдли стремление отстоять права индивидуальности ее свободу: эта тенденция проявилась в умеренном персонализме Бозанкета и радикальном персонализме МакТаггарта которые пытались сочетать гегелевское учение об Абсолюте с утверждением метафизической...
82415. Неомарксизм 32.06 KB
  Первое что предлагают сделать неомарксисты это отказаться от положения марксизма о всемирноисторической роли пролетариата в качестве субъекта социалистической революции и могильщика капитализма. При господстве одномерного сознания одномерный человек этого общества не способен ни выработать ни даже воспринять то революционное социалистическое сознание которое согласно марксизмаленинизма является непременным условием и предпосылкой пролетарской социалистической революции. Второе субъектом революции могут стать лишь те кто еще...
82416. Философия жизни 46.62 KB
  Сознание дух только средства и орудия на службе у жизни. Метафизика это проектированиетотальности жизни на бытие. Все метафизические истолкования и интерпретации мира покоятся напереживании жизни.
82417. Психоанализ З. Фрейда. Фрейдизм, неофрейдизм 28.64 KB
  Классическая психология до Фрейда изучала явления сознания как они проявлялись у здорового человека. Фрейд как психопатолог исследуя характер и причины неврозов натолкнулся на ту область человеческой психики которая раньше никак не изучалась но которая имела большое значение для жизнедеятельности человека бессознательное. Особое значение Фрейд придает психосексуальному развитию человека влиянию его инстинктивной сексуальнобиологической энергии либидо на жизнь его чувств и поведение. В дальнейшем поведение ребенка а затем юноши и...
82418. Феноменология Э. Гуссерля: идейно-теоретические истоки, основные идеи, понятия, этапы развития 38.34 KB
  Феноменология Гуссерля широкое в потенции бесконечное поле методологических а также гносеологических онтологических этических эстетических социальнофилософских исследований любой темы философии через возврат к феноменам сознания и их анализу. Результатом исполнения феноменологической редукции является перемещение на исследовательскую почву чистого сознания; 4 чистое сознание есть смоделированное феноменологией сложное единство структурных элементов и сущностных взаимосвязей сознания. Оригинальность и теоретическая значимость...
82419. Особенности восприятия феноменологии Э. Гуссерля в современной зарубежной философии 34.99 KB
  Гуссерля в современной зарубежной философии Возникновение феноменологии как философского течения связано с творчеством Эдмунда Гуссерля 1859 1938. Однако постепенно происходит изменение его научных интересов в пользуфилософии. Гуссерль изложил в следующих работах: Логические исследования 1901 Философия как строгая наука 1911 Идеи чистой феноменологии и феноменологической философии 1913 Трансцендентальная логика и формальная логика 1921 Картезианские размышления 1931. Особенность философии Э.
82420. Немецкая философия экзистенциализма 29.08 KB
  Основная работа Бытие и время 1927 подчинена трем задачам: 1 выявить фундаментальную структуру здесьбытия как бытиявмире; 2 показать что бытиевмире является временным и историчным; 3 на основе временности здесьбытия осознать необходимую принадлежность времени к смыслу бытия. здесьбытие выступает основой его экзистенциальной онтологии. ставит вопрос о том что есть бытие само по себе и решает его через рассмотрение человеческого бытия поскольку только оно наделено возможностью понимания бытия. Человеческое бытие...
82421. Французская экзистенциальная философия 37.43 KB
  Экзистенциализм — возможно, наиболее популярное (наряду с психоанализом) философское течение нашего времени. Его название происходит от немецкого «existieren» и французского «exister» — существовать, и обращено не к выяснению сущности человека, а к его повседневному бытию