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.


 

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

83731. Решение дробных рациональных уравнений 58.59 KB
  Цели урока: Обучающая: формирование понятия дробные рациональные уравнения; рассмотреть различные способы решения дробных рациональных уравнений; рассмотреть алгоритм решения дробных рациональных уравнений включающий условие равенства дроби нулю; обучить решению дробных рациональных уравнений по алгоритму...
83732. Какие бывают растения? 150.63 KB
  Древесные и травянистые жизненные формы растений и их отличительные признаки; лекарственные растения края; осенние изменения в жизни растений различать травянистые и древесные жизненные формы растений по их внешним признакам; распознавать растения края...
83733. Глобус – модель Земли 44.52 KB
  Цель: познакомить с глобусом моделью Земли; формировать понятия: глобус модель экватор полюса земная ось материки океаны. Планируемые результаты предметные: научатся: определять форму планеты Земля находить на глобусе полюса экватор земную ось материки океаны; иметь представление о накоплении...
83734. What do we name the Motherland? Что мы называем Родиной? 87 KB
  Teacher: Ok, you are right. The title of our lesson is our motherland and its power. Are you ready to find out more interesting information concerned this topic? If yes, let’s get the ball rolling. После ответов учащихся, учитель подводит итог ответам и объявляет тему и цель урока.
83735. Россия в эпоху Великих реформ 941.15 KB
  Здесь вы найдете статистические данные исторические документы воспоминания современников задания по карте. Кроме того вам надо на плакате графически изобразить с помощью линий и надписей Положительные и отрицательные последствия для сельского хозяйства страны...
83736. Свободное падение. Урок – решение задач 28.25 KB
  Цель урока: рассмотреть частный случай свободного падения движение тела брошенного горизонтально с начальной скоростью. Задачи урока: систематизировать и обобщить знания по теме Свободное падение; дать представление о движении тела брошенного горизонтально с начальной скоростью...
83737. Индустриализация СССР 30-х гг. ХХ века 73.93 KB
  Цели урока: Личностный результат - осознавать необходимость индустриализации СССР в 30-е годы ХХ века осмысливать сложность и историческую значимость модернизации страны воспитывать объективный подход к историческим событиям чувство гордости за достижения нашей страны...
83738. СОЮЗЫ СОЧИНИТЕЛЬНЫЕ И ПОДЧИНИТЕЛЬНЫЕ 46.77 KB
  Обучающий аспект: знакомство с группами сочинительных союзов и их ролью в речи с группами подчинительных союзов и их значением формирование умения разграничивать сочинительные и подчинительные союзы сложносочинённые и сложноподчинённые предложения.
83739. Конституция Российской Федерации – основной закон страны 64.78 KB
  Образовательная - закрепление и расширение знаний по теме «Конституция Российской Федерации. Конституционное право», характеризовать конституцию как основной закон государства, знать её содержание, подготовка к ЕГЭ по обществознанию.