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)


 

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

62825. Поведінка учня 22.99 KB
  Ну і мама Ну і тато Наче справжні дошкільнята Нічогісінько не знають Смішно і казать комусь Бо щодня мене питають Лиш одне: Чому й чому. Ти чому образив Віту Ти чому отримав двійку І чому прийшов так пізно І чому в шкарпетках різних Ти чому такий непослух...
62826. Письмовий твір-роздум на морально-етичну тему 44.74 KB
  Так сталося що у мене немає друзів. Я намагаюся бути з усіма доброзичливою допомагаю всім хто до мене звертається я не відмінниця але твердо знаю шкільні дисципліни проте списувати не даю нікому просто пояснюю.
62827. Повний звуковий аналіз слів. Урок-гра «Поле чудес» 16.26 KB
  До виконання завдання першого туру викликає трьох учнів які правильно підняли руку і назвали слова вірша з одним двома трьома складами. Завдання I туру У першому турі вам треба відгадати слово звукову схему якого записано на дошці.
62828. Укрепление и сохранение здоровья учащихся с помощью знаний о закаливаний полученных на этом уроке 303.13 KB
  Виды закаливания. Значение закаливания для здоровья человека; необходимо учитывать индивидуальные особенности организма; закаливание должно быть постепенным; закаливаться нужно систематически не пропуская ни одного дня; использовать любую возможность для закаливания.
62830. Окружающий мир и музыка. Что такое музыка? Сказки и легенды о музыке и музыкантах 110.9 KB
  Музыка - это прежде всего звуки,которые нас окружают. Это и пение птиц, и шум моря (ветра),и шелест листьев, вобщем то - что имеет звук. А рёв машин или сигнализация - это музыка? Да, это тоже музыка.
62831. МИР ДЕТСТВА В МУЗЫКЕ. МУЗЫКА И ЖИВОТНЫЙ МИР 69.47 KB
  Правильно А играться вы любите да А какие ваши любимые игрушки куклы солдатики машинки мячики и др. О куклах есть пьесы русского композитора Петра Ильича Чайковского музыка из детского альбома...
62832. СКАЗКА В МУЗЫКЕ 16.04 MB
  Ребята помните на уроке музыка и другие виды искусства мы уже говорили что музыка подобно краскам в живописи тоже может рисовать картины. картинка Ребята Сейчас я включу музыку русского композитора Римского Корсакова но название композиций...