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)


 

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

58472. Listening 85.5 KB
  But before we start our theme let’s find and match antonyms here (в презентации появляются слова, которые облегчат обучающимся понять смысл текста, они должны их просто назвать и соединить вместе: sell, buy, fresh, stale, young, old, always, expensive, cheap, never, finish, begin.
58473. SCHOOLS IN BRITAIN 330.9 KB
  Listen to the dialogue about a typical day at American school and answer the questions. Alice. Ostap, would you like to school with me tomorrow? Ostap. Sure. I have never been in an American school, what is the typical day like at school? Alice. Well, first we go to our homeroom class.
58474. Tolerance 58 KB
  Please open you work book at page fifty six exercise 1. Here you should fill in the gaps using these words: against, according to, of, without. I think 3 minutes on this work. Когда сделали, говорю: please read it one by one and then we will check the answers...
58475. Двомембранні органели і мітохондрії і пластиди. Фотосинтез, дихання 35.5 KB
  Мета: познайомити з будовою та функціями двомембранних органел: мітохондріями та пластидами, фазами мітозу, з клітинним циклом, поняттями, каріотип, фотосинтез, дихання, мітохондрія, хлоропласт, хемосинтез з процесами фотосинтезу та дихання, вчити порівнювати ці два процеси між собою...
58476. Урок биологии 165 KB
  Подготовка учителя к урокам. Постановка цели урока. Структура урока этапы комбинированного урока. Проведение урока биологии Перспективное и поурочное планирование Основой для планирования учебно-воспитательного образовательного процесса по биологии является анализ существующих нормативных требований программ учебных и дидактических пособий и опыта педагогической деятельности учителя.
58477. Вид. Критерии вида 45.5 KB
  Цели урока: обучающие: сформулировать определения понятиям вид критерии вида; изучить критерии вида и их содержание; развивающие: продолжить развитие коммуникативных умений при работе в группах устной монологической речи учащихся...
58478. Уроки Чистоты на территории Пермского края 3.73 MB
  Технологии сортировки отходов уже реализуются в некоторых российских городах. Для успешной организации сортировки очень важна первая ступень раздельный сбор отходов жителями. По статистике каждый из нас ежегодно образует 300 кг отходов.
58479. Рідна домівка, рідна сім’я – тут виростає доля моя. В.Гринько «Сім». В.Сухомлинський «Тетянка усміхається» 73 KB
  Доброго здоровя всім В добрий день і в добрий час Рада всіх вітати вас. Який розділ ви почали вивчати на попередньому уроці Рідна домівкарідна сімятут виростає доля моя З якими піснями ви ознайомилися на минулому уроці Роде наш красний...
58480. Проектирование молодежного кафе – «KFC» 752 KB
  Молодежное кафе, как организация является обществом с ограниченной ответственностью предприятие бытового обслуживания (ООО ПБО). Общество с ограниченной ответственностью является разновидностью объединения капиталов, не требующего личного участия своих членов в делах общества