67606

Разложение булевых функций по переменным

Лекция

Математика и математический анализ

Это представление называется разложением функции по m переменным x1xm. Разложение по одной переменной 1 Разложение по всем n переменным 2 При Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции fx1xn.

Русский

2014-09-12

174.5 KB

9 чел.

Лекция №15

Разложение булевых функций по переменным.

Возникают вопросы:

1) всякая ли функция может быть записана с помощью формулы?

2) как это сделать?

Совершенная дизъюнктивная нормальная форма.

Обозначим, где равен либо 0, либо 1. Тогда

.

Поскольку

,

то x=1   x=.

Теорема о разложении функции по переменным || Каждую функцию Булевой алгебры  при любом  можно представить в следующей форме:

,

где дизъюнкция берется по всем наборам значений переменных . ||

опр || Это представление называется разложением функции по m переменным x1,…xm.||

Доказательство.

  1.  Рассмотрим произвольный набор значений . Левая часть равенства имеет вид . Правая часть

(в сумме только одно произведение отлично от нуля: то в котором )

.

Теорема доказана.

Разложение по одной переменной

1)

Разложение по всем n переменным

2)

При

Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции f(x1,…,xn).

Теорема || Каждая функция алгебры логики может быть выражена в виде формулы, содержащей только отрицание, конъюнкцию и дизъюнкцию. ||

Доказательство ||

1) Если , то

2) Если  , то

Примеры

1)

x1

x2

f

0

0

1

0

1

1

1

0

0

1

1

1

(это СДНФ; теперь преобразуем)

2) Следующий пример. Дана таблица

x1

x2

x3

f

0

0

0

1

0

0

1

1

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

1

3) 

x1

x2

x3

x4

f

0

0

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

0

0

1

0

0

1

0

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

0

0

1

1

0

0

1

1

1

0

1

0

0

1

0

1

1

0

1

1

0

0

0

1

1

0

1

0

1

1

1

0

1

1

1

1

1

0

4) Аналитический способ

5)

Пусть . Согласно теореме двойственности

Это разложение называется совершенной конъюнктивной нормальной формой.

Примеры

1)

2)

x1

x2

f

0

0

0

0

1

1

1

0

1

1

1

0

3)

x1

x2

x3

f

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

0

1

1

0

1

1

1

1

1

4)

x1

x2

x3

x4

0

0

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

0

0

1

0

0

1

0

1

0

1

0

0

1

1

0

0

0

1

1

1

0

1

0

0

0

1

1

0

0

1

1

1

0

1

0

0

1

0

1

1

0

1

1

0

0

0

1

1

0

1

0

1

1

1

0

1

1

1

1

1

0

5)


 

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

37096. Формирование советской политической системы. Временный блок большевиков с левыми эсерами. Разгон Учредительного собрания 21.09 KB
  Для укрепления власти большевики стремились привлечь на свою сторону крестьянство. Большевики и левые эсеры полностью поддержали политику Советского правительства и выступили против передачи власти предстоящему Учредительному собранию. Вскоре новый исполком крестьянского съезда Советов в состав которого были избраны только большевики и левые эсеры присоединился к ВЦИКу.1917 большевики заключили официальный блок с левыми эсерами которые вошли в правительство и возглавили пятьнаркоматов.
37097. Белое движение 15.26 KB
  Цель инициаторов Белого движения ген. Причинами поражения Белого движения являлись: недостаточно скоординированные действия разрозненность очагов антибольшевистского сопротивления отсутствие детальной политической программы поддержки широких слоев населения прежде всего крестьянства. Красное движение Состав красного движения: пролетариат бедное крестьянство солдаты часть интеллигенции и офицерства. Более однородный состав Представители красного движения:...
37098. ВОЕ́ННЫЙ КОММУНИ́ЗМ 12.75 KB
  Политика военного коммунизма включала комплекс мероприятий затронувших экономическую и социальнополитическую сферу. Основой военного коммунизма были чрезвычайные меры в снабжении городов и армии продовольствием свертывание товарноденежных отношений национализации всей промышленности включая мелкую продразверстка снабжение населения продовольственными и промышленными товарами по карточкам всеобщая трудовая повинность и максимальная централизация управления народным хозяйством и страной в целом....
37099. Причины перехода к НЭПу 16.36 KB
  Массовые крестьянские восстания Падение промышленного производства Волнения городского населения в 7 раз Беспорядки в армии и на флоте Уменьшение валовой продукции Угроза разрыва между рабочим классом и крестьянством Необходимость создания механизма реализации материальных интересов всех слоев населения Обобщение предыдущей практики социалистического строительства Новая экономическая политика экономическая политика проводившаяся в Советской России и СССР в 1920е годы. Новая экономическая политика имела целью восстановление...
37100. Национальная политика советской власти. Образование Союза Советских Социалистических Республик 20.49 KB
  Образование Союза Советских Социалистических Республик Объединительное движение по созданию Советского многонационального государства началось сразу после победы Октябрьской революции и распада империи и прошло три этапа. ознаменовался рождением Российской Советской Федеративной Социалистической Республики которая последовательно по мере реализации курса на равноправие народов превращалась в федерацию нового типа. На первом этапе на территории бывшей царской России возникли автономные республики территориальные автономии с учетом...
37101. Национальная политика первых лет Советской власти. Образование СССР 17.32 KB
  Большевистская идея мировой революции и создания в будущем Всемирной Федеративной Республики Советов форсировала новый объединительный процесс. В связи с победой советской власти на основной территории бывшей Российской империи возникли и другие предпосылки для объединительного процесса единый характер политического строя диктатура пролетариата в форме республики Советов сходные черты организации государственной власти и управления. В большинстве республик власть принадлежала национальным коммунистическим партиям входившими в состав...
37102. Индустриализация 36.5 KB
  Необходимость индустриализации: экономическая: крупная промть определяет экономическое развитие страны в целом. Военнополитическая без индустриализации невозможно обеспечить техникоэкономическую независимость страны и ее оборонную мощь. Проблемы создания индустриализации стали первоочередными в конце 1925г. Источники индустриализации: внутренние накопления: внутренние займы выкачивание средств из деревни доходы от внешней торговли дешевая рабочая сила энтузиазм трудящихся труд заключенных.
37103. Коллективизация сельского хозяйства и ее последствия 19.56 KB
  Коллективиза́ция это процесс объединения единоличных крестьянских хозяйств в коллективные хозяйства колхозы в СССР. объединению подлежало 25 процентов крестьянских хозяйств. Основу аграрного сектора экономики страны составляли мелкие крестьянские хозяйства которые имели полунатуральный характер.
37104. Начальный период Великой Отечественной войны. Причины поражения Красной Армии на первом этапе войны 15.43 KB
  Причины поражения Красной Армии на первом этапе войны. 22 июня 1941 года нацистская Германия вероломно нарушив договор о ненападении внезапно без объявления войны нанесла по Советскому Союзу мощный удар. Этот день вошел в историю нашей страны трагической датой стал днем начала неимоверно тяжелой войны советского народа против фашизма справедливо названной Великой Отечественной войной.