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)


 

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

9896. Примеры простейших задач вариационного исчисления 214.5 KB
  Примеры простейших задач вариационного исчисления Исторически первой задачей, известной в глубокой древности и отнесенной впоследствии к задачам вариационного исчисления, явилась так называемая задача Дидо. Легенда говорит, что Дидо - царица од...
9897. Вариация функционала 278.5 KB
  Вариация функционала Вариация одно из центральных понятий при изучении нелинейных функционалов, оно играет ту же роль, что понятие дифференциала при изучении нелинейных функций. Дифференциал нелинейной функции равен главной линейно...
9898. Вторая вариация и достаточные условия экстремума 178 KB
  Вторая вариация и достаточные условия экстремума Вспоминая о глубокой аналогии между дифференциальным и вариационным исчислениями, естественно ожидать, что при переходе к достаточным условиям экстремума функционалов будет введено понятие, иг...
9899. Классификация задач оптимизации 70 KB
  Классификация задач оптимизации оптимизируемая функция (целевая функция, целевой функционал, критерий качества и т.п.), численно выражает степень достижения целей функционирования оптимизиру...
9900. Динамическая оптимизация 97 KB
  Динамическая оптимизация Статическая задача распределения ограниченных ресурсов для достижения комплекса конкурирующих целей в некоторый определенный момент времени математически формализуется в виде математической задачи выбора из заданного до...
9901. Динамическое программирование 224 KB
  Динамическое программирование Динамическое программирование является еще одним из двух современных направлений в теории задач управления. Метод динамического управления может применяться непосредственно при решении общей задачи управления...
9902. Линейное программирование 383.5 KB
  Линейное программирование Линейное программирование (ЛП) - это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения 1930 г., А.Н. Толстой - составление оптим...
9903. Симплекс-метод решения задач ЛП 86.5 KB
  Симплекс-метод решения задач ЛП Симплекс-метод предложен Дж. Данцигом в 1947 г. непосредственно применяется к общей задаче ЛП в канонической форме: Z = CTX min, при ограничениях X0, AX = B, B > 0, Любое неотрицательное решение...
9904. Двойственность в линейном программировании 47 KB
  Двойственность в линейном программировании Для любой задачи ЛП можно сформулировать двойственную задачу, являющуюся зеркальным отражением исходной задачи, т.к. она использует те же параметры, а ее решение может быть получено одновременно с решение...