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)


 

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

62797. Изготовление поздравительной открытки к 8 марта 12.91 KB
  Цель: изготовить открытку Задачи: формировать эстетический вкус развивать творческие способности воспитывать нежное отношение к маме Оборудование: альбомный лист, цветная бумага (зелёная, жёлтая, оранжевая, красная, розовая, клей, ножницы, карандаш).
62799. Лепка грибов из пластилина 52.58 KB
  Чем же люди занимаются осенью собирают грибы Сегодня на уроке мы будем лепить грибы из пластилина и соберем свое собственное лукошко осенних грибов. Какие грибы вы знаете ответы детей На какие 2 группы можно разделить грибы съедобные несъедобные...
62802. Плетение 57.45 KB
  Оборудование: образец закладки для книг метровая линейка. А какая из этих книг будет той о которой говорилось в начале стихотворения Почему вы так решили Значит как с этой книгой обращались Верно А что нужно делать для того чтобы книга на долгое время сохранялась...
62803. Приемы изготовления сюжетной композиции «Лодочка» по образцу 18.35 KB
  Я буду называть материалы и инструменты а вы будете хлопать в ладоши при их наличии. Выполняя эту аппликацию вы будете продолжать осваивать приемы работы с бумагой: разметку по шаблону резание наклеивание. Это значит что синюю полосу вы будете приклеивать последней.
62804. Игрушка на 23 февраля 23.48 KB
  Что такое цилиндр Сегодня мы будем делать вот таких военных человечков. Посмотрите внимательно и скажите какая фигура является основой нашей поделки цилиндр. А кто может сказать что такое цилиндр...