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)


 

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

41657. Техника аудиовизуальных средств информации 17.18 MB
  Спецэффекты Для создания качественных видео фильмов в программе dobe Premiere имеется значительное количество различных спецэффектов. При этом существует два основных типа эффектов: статические и динамические. Перед тем как начать процесс редактирования клипов с помощью эффектов необходимо активировать соответствующие вкладки в окнах Medi Browser вкладка Effects и Source вкладка Effect Controls. На следующем этапе выделите нужный клип в монтажной области с помощью инструмента выделения в результате чего во вкладке Effect Controls...
41658. Защита информации, антивирусная защита. Эксплуатационные требования к компьютерному рабочему месту 185.58 KB
  Лист № докум. Подпись Дата Лист 1 Лабораторная работа № 3 Разраб. Листов 3 47Э1 Цель работы Ознакомиться с теоретическими аспектами защиты информации от вредоносных программ: разновидности вирусов способы заражения и методы борьбы. Лист № докум.
41659. РАБОТА В ПРОГРАММНОЙ СРЕДЕ MICROSOFT OUTLOOK 757.34 KB
  Программная среда Microsoft Outlook пришла на смену разнообразным видам бумажных носителей которые использовали руководители и секретари для организации своей работы. Сегодня для организации документов и отправки почты планирования задач встреч событий и собраний ведения списка контактов а также учета всех выполненных работ используется программа Microsoft Outlook. Информация в среде Outlook организована в виде папок аналогичных по назначению своим бумажным предшественникам.
41660. Поверка средств измерений 39.3 KB
  Поверка средств измерений Цели и задачи работы: Изучение правил организации и порядка проведения поверки средств измерения. Краткие сведения из теории: Поверкой средств измерений называют совокупность действий выполняемых для определения и оценки погрешностей средств измерений. Вид поверки определяют в зависимости от того какой метрологической службой проведена поверка от характера поверки инспекционная экспертная каков этап работы средства измерений первичная периодическая внеочередная. Организацию и поверку средств измерений...
41661. Косвенные измерения. Определение показателей точности косвенных измерений 587.13 KB
  Косвенные измерения. Определение показателей точности косвенных измерений Цели и задачи работы: изучение методов измерения при которых искомое значение физической величины находят путем согласованных наблюдений других величин определяемых опытным путем связанных с искомой физической величиной известной зависимостью; ознакомление с правилами оценивания погрешностей косвенных измерений. При выполнении работы необходимо практически ознакомиться с системой допусков и посадок требованиями к точности линейных и угловых параметров изделий...
41662. Вставка и редактирование формул в редакторе WORD 73.64 KB
  Вставка и редактирование формул. Вставка формул. Вставка формул в редакторе WORD осуществляется с помощью формульного редактора. Вызов формульного редактора Eqution Editor из Word можно осуществить следующей последовательностью действий: поместите курсор в то место где должна быть вставлена формула; в меню вставка выберите команду обьект ; выберите закладку создание ; В окне тип обьекта выберите Microsoft Eqution 3.
41663. Теория электрической связи 263.74 KB
  Получение характеристик частотного модулятора при воздействии на его вход моногармонического сигнала. Напряжение смещения Есм являющееся постоянной составляющей модулирующего сигнала позволяет установить несущую частоту модулированного сигнала а переменная составляющая т. сам модулирующий сигнал поданный на гнезда КТ1 обеспечивает девиацию частоты fmx зависящую от амплитуды модулирующего сигнала. В схеме модулятора имеется блок автоматической регулировки усиления поддерживающий постоянную амплитуду ЧМ сигнала на схеме не показан.
41664. Исследование зависимости выходного напряжения усилительного каскада от амплитуды и частоты входного сигнала 155.55 KB
  Цель: Научиться определять и анализировать зависимости выходного напряжения усилительного каскада от амплитуды и частоты входного сигнала. Лабораторная работа №6 Тема: Исследование зависимости выходного напряжения усилительного каскада от амплитуды и частоты входного сигнала. Лабораторная работа №6 Тема: Исследование зависимости выходного напряжения усилительного каскада от амплитуды и частоты входного сигнала.