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.


 

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

20334. Античный театр 435.5 KB
  Поэтому драматическая поэзия все без исключения трагедии и комедии в Греции писались стихами смогла отодвинуть на второй план другие литературные жанры и на целый век стать жанром господствующим. Давали обязательно три трагедии и одну сатировскую драму т. Если эпоха архаики наиболее плотно выразила себя в лирике то классическая Греция проявила себя в аттической трагедии – жанре в наибольшей степени отвечающем духу античной культуры. В греческой трагедии нашла выражение такая эстетическая категория как катарсис то есть очищение...
20335. АКТУАЛЬНОСТЬ И ПРОБЛЕМАТИЧНОСТЬ ИССЛЕДОВАНИЯ ТЕХНИКИ. ОБЩИЕ ЗАДАЧИ, МЕТОДОЛОГИЧЕСКИЕ И ИДЕЙНЫЕ ОСНОВЫ ФИЛОСОФИИ ТЕХНИКИ. ФИЛОСОФИЯ ТЕХНИКИ В ВЫСШЕМ УЧЕБНОМ ЗАВЕДЕНИИ 54 KB
  ОБЩИЕ ЗАДАЧИ МЕТОДОЛОГИЧЕСКИЕ И ИДЕЙНЫЕ ОСНОВЫ ФИЛОСОФИИ ТЕХНИКИ. ФИЛОСОФИЯ ТЕХНИКИ В ВЫСШЕМ УЧЕБНОМ ЗАВЕДЕНИИ. Причины современного повышенного акцентированного внимания к феномену техники.
20336. ПОНЯТИЙНЫЕ ОСНОВЫ ФИЛОСОФИИ ТЕХНИКИ. ПРОБЛЕМА ОБЪЕДИНЯЮЩЕГО ПОНИМАНИЯ ТЕХНИКИ. УЗКОЕ И ШИРОКОЕ ПОНИМАНИЕ ТЕХНИКИ И ФИЛОСОФИИ ТЕХНИКИ. ПРОБЛЕМА ФУНКЦИЙ ТЕХНИКИ И ОБЪЕКТА ТЕХНИЧЕСКИХ ИЗМЕНЕНИЙ. ОБЪЕДИНЯЮЩЕЕ ПОНИМАНИЕ ТЕХНИКИ 72 KB
  ПРОБЛЕМА ОБЪЕДИНЯЮЩЕГО ПОНИМАНИЯ ТЕХНИКИ. УЗКОЕ И ШИРОКОЕ ПОНИМАНИЕ ТЕХНИКИ И ФИЛОСОФИИ ТЕХНИКИ. ПРОБЛЕМА ФУНКЦИЙ ТЕХНИКИ И ОБЪЕКТА ТЕХНИЧЕСКИХ ИЗМЕНЕНИЙ.
20337. ПОНЯТИЙНЫЕ ОСНОВЫ ФИЛОСОФИИ ТЕХНИКИ. ОПРЕДЕЛЕНИЕ ТЕХНОЛОГИИ. ТЕХНИЧЕСКИЙ ИЛИ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ? ОПРЕДЕЛЕНИЕ ТЕХНОСФЕРЫ. ОБЪЕКТ И ПРЕДМЕТ ФИЛОСОФИИ ТЕХНИКИ 65.5 KB
  ОБЪЕКТ И ПРЕДМЕТ ФИЛОСОФИИ ТЕХНИКИ. Философия техники или философия технологии Технический или технологический университет Философия техники как философия техносферы. Объект и предмет философии техники.
20338. Объективная и субъективная диалектика. Теоретическое и обыденное сознание и диалектика. Софистика, эклектика, релятивизм и диалектика 62.5 KB
  Но поскольку человек только часть бесконечного объективного мира то это богатство именно относительно. Беднее – поскольку отражение объективного в субъективной форме не есть тождественное отражение. Ее всеобщность уже была Вам представлена поскольку изложение начальных вопросов философии ее предмета основных философских направлений не обошлось без диалектики например практически вечная борьба в философии материализма и объективного идеализма. релятивизме относительности даже полном релятивизме когда на каждое да возможно нет...
20339. ФИЛОСОФИЯ И МИРОВОЗЗРЕНИЕ. РАЗДЕЛЫ ФИЛОСОФСКОГО ЗНАНИЯ. ФУНКЦИИ ФИЛОСОФИИ В ДУХОВНОЙ КУЛЬТУРЕ ЧЕЛОВЕКА И ЧЕЛОВЕЧЕСТВА 43 KB
  ФУНКЦИИ ФИЛОСОФИИ В ДУХОВНОЙ КУЛЬТУРЕ ЧЕЛОВЕКА И ЧЕЛОВЕЧЕСТВА. Какой из возможных видов сравнения взять за начало Сравнение философии с другими видами мировоззрений. Это позволит с одной стороны показать специфику философии на фоне других мировоззрений с другой стороны выйти на разделы философского знания. Темы раздела: диалектика противоположности законы диалектики качество количество Вопросы: отличие диалектики от метафизики специфика диалектического снятия История философии – собрание всей мудрости.
20340. СОЦИАЛЬНО-ИСТОРИЧЕСКИЕ УСЛОВИЯ И ПРЕДПОСЫЛКИ ВОЗНИКНОВЕНИЯ ФИЛОСОФИИ. ОСНОВНЫЕ ЭТАПЫ РАЗВИТИЯ ФИЛОСОФСКОЙ КУЛЬТУРЫ 50 KB
  Социальноисторические условия и предпосылки возникновения философии. Необходимым условием возникновения философии выступает рост производительных сил общва техники трудовых умений и знаний. Из истории вы должны знать какие причины видят в основании греческого чуда которое в частности привело к возникновению философии.
20341. ОБЩАЯ ХАРАКТЕРИСТИКА ИСТОРИЧЕСКИХ ЭТАПОВ ВЗАИМООТНОШЕНИЯ ФИЛОСОФИИ И НАУКИ. СОВРЕМЕННОЕ ПОНИМАНИЕ ФИЛОСОФИИ КАК НАУКИ, ЕЕ МЕСТА В СИСТЕМЕ НАУЧНОГО ЗНАНИЯ. НАУКА, ФИЛОСОФИЯ, ЦЕННОСТЬ 44 KB
  СОВРЕМЕННОЕ ПОНИМАНИЕ ФИЛОСОФИИ КАК НАУКИ ЕЕ МЕСТА В СИСТЕМЕ НАУЧНОГО ЗНАНИЯ. Наука в это время в целом входит в лоно философии. Одни социальноэкономические условия способствовали появлению философии и науки – атмосфера демократии возможность существования теоретического абстрактного знания.
20342. ПРИЧИНЫ И ЗНАЧЕНИЕ ПЛЮРАЛИЗМА ФИЛОСОФСКИХ УЧЕНИЙ. ОСНОВНОЙ ВОПРОС ФИЛОСОФИИ И ОСНОВНЫЕ ФИЛОСОФСКИЕ НАПРАВЛЕНИЯ. ОПРЕДЕЛЕНИЕ ФИЛОСОФИИ КАК НАУКИ 38 KB
  ОСНОВНОЙ ВОПРОС ФИЛОСОФИИ И ОСНОВНЫЕ ФИЛОСОФСКИЕ НАПРАВЛЕНИЯ. ОПРЕДЕЛЕНИЕ ФИЛОСОФИИ КАК НАУКИ. Для многих это признак слабости философии. В философии сегодня наиболее полно представлена самобытность человека.