67606

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

Лекция

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

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

Русский

2014-09-12

174.5 KB

8 чел.

Лекция №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)


 

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

85186. Новая экономическая политика, ее сущность и значение для развития хозяйства БССР 26.41 KB
  Ответом на эти вопросы стала новая экономическая политика НЭП. НЭП это система экономических социальных политических и культурных мер направленных на внедрение рыночных отношений в народном хозяйстве. В первые годы НЭПа практиковалось натуральная и денежная оплата труда. В сфере с х нэп проявилась в следующем: 1 Вместо продразвёрстки был введен продналог который был в два раза меньше.
85187. БССР в годы первых пятилеток. Форсированная индустриализация и принудительная коллективизация 26.78 KB
  Дальнейшее развитие металло-обрабатывающей химической торфяной и др. отраслей развитие энергетики и увеличение мощностей электростанций. Предусматривалось развитие лёгкой и продовольственной промышл.
85188. Духовная и культурная жизнь БССР в 1920-1930гг.: достижения и противоречия 25.66 KB
  Культуры вылученне белорусов на партыйую советскую профсоюзную и общественную работу перевод делопроизводства государственного партийного профессионального и кооперативного аппаратов на белорусский язык. Центральная место в мероприятиях в белорусизации отводилось проблеме языка так как в республике язык выполняла очень мизерны объем соц. Преобладала русский язык. При этом официально было заявлено что на территории БССР признаются равноправными языки белорусский русский еврейский и польский.
85189. Западная Беларусь в составе Польши 27.1 KB
  Было введено принятое в Польше административно-тер деление, созданы 4 воеводства: Виленское, Полесское, Новогрудское, Белостокское. Эти воеводства делились на 29 поветов аповеты на гимны.
85190. Начало второй мировой войны. Вхождение Западной Беларуси с состав БССР 26.28 KB
  Вхождение Западной Беларуси с состав БССР. Беларуси принял декларацию об установлении советской власти на всей освобожденной территории i высказался за вхождение в состав БССР. Приняты законы о включении Западной Беларуси в состав СССР i воссоединение с БССР. Единогласно делегаты высказались и за вхождение в БССР.
85191. Начало Великой Отечественной войны. Ход военных действий на советско-германском фронте в 1941-1942 годах 27.92 KB
  Для войны против СССР Гитлер сосредоточил подавляющую часть своих сухопутных сил. Однако основной причиной такого огромного успеха немцев в первые недели войны является то что Красная армия сама готовилась к наступлению. Сталин прекрасно понимал что войны с Германией не избежать но он не думал что Гитлер нарушит пакт МолотоваРибентропа о ненападении.
85192. Фашистский оккупационный режим на территории БССР 26.93 KB
  К концу августа 1941 г гитлеровцы оккупировали всю территорию Бел. На захваченной территории гитлеровцы установили оккупационный режим- систему политических, идеологических, экономических, и военных мер направленных на ликвидацию существующего общественного и гос. строя, грабёж нац. богатства, уничтожение населения
85193. Коренной перелом в ходе Великой Отечественной войны 29.96 KB
  Коренной перелом начатый под Сталинградом был завершен в ходе Курской битвы и сражениях за р. в ходе Киевской наступательной операции 6 ноября столица Украины была освобождена. В ходе оборонительных боев к концу декабря 1943 г.
85194. Партизанское и подпольное движение в БССР 28.28 KB
  Один из первых партизанских отрядов был организован уже на пятый день войны в Пинске под командованием Коржа насчитывал 60 чел. Полесской области действовал отряд под командованием Бумажкова и Павловского. В июле 41 начал боевые действия отряд пол командованием Шмырёва в Вит.