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.


 

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

32675. Понятие управления и педагогического менеджмента 127.5 KB
  Усложняются задачи управления. Отметим что в российской практике управления образовательными учреждениями а капитана корабля естественно сравнивать с руководителем школы или образовательного учреждения иного типа управленческие цели продолжают ставить чаще всего исходя из анализа состояния образовательного процесса то есть заказ является внутренним а не исходя из изменяющихся общественных потребностей внешний по отношению к учреждению заказ. На следующем этапе управления капитану необходимо построить уже конкретную программу...
32676. Эволюция управленческой мысли 55.5 KB
  Фредерик Уинслоу Тейлор опубликовал книгу Принципы научного управления. Выделяются 4 важнейших подхода: Подход с позиций выделения различных школ управления иначе его называют классическим или традиционным подходом Первая половина ХХ века 18851950 Школа научного управления 18851920 Административная школа 19201950 Школа психологии и человеческих отношений 19301950 Школа науки управления количественная школа 1950 1.Ситуационный подход 1960 Характеризуется тем что пригодность различных методов управления...
32677. Основные функции управления (педагогического менеджмента) 290.5 KB
  Планирование как функция управления Функция управления контроль. Процесс управления 1. Понятие функции управления Каждая система которая создаётся нужна для чегото.
32678. ИНФОРМАТИКА В 10 КЛАССЕ. КОНСПЕКТЫ УРОКОВ 986 KB
  Учебное методическое пособие предполагает наличие в школьном кабинете информатики IBM-совместимых компьютеров, организованных в локальную сеть, а также программного обеспечения: операционной системы Windows, системы программирования PascalABC, ЭТ Microsoft Excel, браузера Internet Explorer, программ Movie Maker, Net Meeting, Skype.
32679. РЕСТРУКТУРИЗАЦИЯ БИЗНЕСА В РОССИИ 98 KB
  В процессе реструктуризации может происходить совершенствование системы управления предприятием, изменение финансово-экономической политики, операционной деятельности, систем маркетинга, сбыта и управления персоналом
32680. Детальний маркетинговий аналіз препарату «Арбідол» 364.5 KB
  Інтерферон безпосередньо не інактивує віруси або їх нуклеїнові кислоти, не перешкоджає адсорбції і проникненню вірусу в клітину, а також його депротеїнізації. Інтерферон проявляє свою дію на внутрішньоклітинному етапі репродукції вірусу. Механізм взаємодії інтерферону з клітинами, в яких він індукує антивірусний стан
32681. Гемопоэз 102 KB
  Процесс образования и развития клеток крови гемопоэз кроветворение. Чтоб гемопоэз протекал нормально он должен быть обеспечен всем необходимым для построения клеток крови. Анемия состояние при котором снижается способность крови переносить кислород т. Железо адсорбируется главным образом в тонком кишечнике при дефиците Fe и его высокое содержание в крови уменьшает адсорбцию.
32682. Шляхи енергозбереження в навчальному закладі та вдома 358.5 KB
  Проблема енергозбереження для України є однією з найважливіших. Це пов’язане з тим, що енергетика України найбільш енерговитратна у світі. А в умовах переходу економіки на ринкові відносини та входження до світового економічного простору, в умовах гострої економічної кризи