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)


 

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

64955. Письменные источники о Чингисхане 120.5 KB
  В первой части до описания времени Чингисхана почти дословно повторяется индийская история о проповеди Будды Шакьямуни в Магадхе3 двух учений тантры и сутры. У Джувейни дом Чингисхана находится в Куланбаши название которого нет в текстах...
64956. О времени основания Казани 48.5 KB
  Все гипотезы о времени основания Казани базируются на использовании: даты первого упоминания имени города в исторических источниках; этимологической интерпретации имени города; археологических эпиграфических и нумизматических материалов...
64957. Степные империи древней Евразии 204 KB
  История и культура енисейских кыргызов представлены в источниках неравномерно. В одних случаях доминируют письменные свидетельства, в других — данные археологии. Иногда они тесно коррелируют друг с другом, и эти периоды оказываются для изучения наиболее результативными.
64958. СУДЕБНАЯ СИСТЕМА МОНГОЛИИ В XIII В. ПО «ГОЛУБОЙ КНИГЕ» УКАЗОВ ЧИНГИСХАНА 56.5 KB
  Монгольского государства на рубеже XII-XIII веков означало прежде всего создание государственного аппарата формирование принципов управления и судопроизводства. издан указ о назначении Шихихутуга главным судьей во всей державе. Назначенный указом Чингисхана Бэлгудэй позже Шихихутуг имели статус главного судьи сам хан находился на вершине пирамиды.
64959. Белые пятна в этногенезе дэрбэт 91 KB
  Он покинул Тибет из-за начавшейся междоусобной войны и прибыл в страну Джад («чужой»). Это событие отнесено Лубсан Данзаном к VII в. Обосновавшись в урочище Бурхан-Халдун, Бортэ-Чино женился и основал свой род «монгол». С того времени минуло примерно 400 лет, когда после смерти Дува-Сохор...
64960. НЕКОТОРЫЕ ВОПРОСЫ НУМИЗМАТИКИ И ИСТОРИИ СТАРОГО ОРХЕЯ (ЗОЛОТООРДЫНСКИЙ ПЕРИОД) 143 KB
  Монеты являются одним из наиболее информативных и разнообразных источников по истории стран Средневековой Европы. Монеты выявленные на территории любого города являются своеобразным посланием к городу и миру. Бырни мне удалось ознакомиться с частью монет из Старого Орхея хранящихся в Музее Института археологии и этнографии...