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)


 

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

35843. Математические методы анализа экономики 565 KB
  Этот метод называют также методом последовательного улучшения решения плана. Решить задачу методом больших штрафов РЕШЕНИЕ: Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных переход к канонической форме. Из уравнений выражаем искусственную переменную: которую подставим в целевую функцию: Или Базисные переменные х4 х6 Свободные переменные х1 х2 х3 х5 Полагая что свободные переменные равны 0 получим первый опорный план: X1 = 0008010 Базисное...
35844. Функция полезности: определения свойства 538.06 KB
  Самая распространенная функция КоббаДугласа: g = fLK = 0 Одна из задач фирмы заключается в определении количества продукции и в расчете необходимых для ее выпуска затрат с учетом технологической связи между ними и заданными ценами на затраты и продукцию. Модель фирмы в условиях совершенной конкуренции. Неоклассическая теория фирмы построена на предположении что цель фирмы заключается в максимизации прибыли путем выбора вида затрат при заданной ПФ и заданных ценах на продукцию и затраты. Модель фирмы в условиях олигополии.
35847. СРАВНИТЕЛЬНЫЙ АНАЛИЗ ТЕХНОЛОГИЙ РАСШИРЕНИЯ WEB-СЕРВЕРОВ 236 KB
  Диаграммы Use Cse =диаграммы прецедентов диаграммы вариантов использования Диаграмма Use Cse определяет поведение системы с точки зрения пользователя. Диаграмма Use Cse рассматривается как главное средство для первичного моделирования динамики системы используется для выяснения требований к разрабатываемой системе фиксации этих требований в форме которая позволит проводить дальнейшую разработку. Вершинами в диаграмме Use Cse являются актеры и элементы Use Cse. Элементы Use Cse представляют действия выполняемые системой в интересах...
35848. ОБЩИЕ СВЕДЕНИЯ О ЦИФРОВЫХ АВТОМАТАХ. Функционирование цифрового автомата в дискретном времени 213.5 KB
  ОБЩИЕ СВЕДЕНИЯ О ЦИФРОВЫХ АВТОМАТАХ. функционирование цифрового автомата в дискретном времени. Отличительной особенностью дискретного автомата является дискретное множество внутренних состояний и скачкообразность перехода из одного состояния в другое. В реальных автоматах множество внутренних состояний всегда конечно поэтому дискретные автоматы часто называют конечными автоматами или просто автоматами.
35849. Коммутаторы: принцип работы. Основные и дополнительные характеристики 192 KB
  Эту информацию записывает в кадр станцияисточник кадра с помощью своего сетевого адаптера который реализует алгоритм маршрутизации от источника source routing. На данный момент обеспечиваются скорости от нескольких десятков кбит с например GPRS 115 кбит с Протоколы маршрутизации. Протоколы маршрутизации например RIP OSPF NLSP следует отличать от собственно сетевых протоколов например IP IPX. Протоколы маршрутизации используют сетевые протоколы как транспортное средство.
35851. Конституційне право України 193.5 KB
  До таких актів належать: Конституція України основне джерело права; конституційні закони закони що вносять зміни й доповнення до Конституції або скасовують її окремі норми; органічні закони закони прийняття яких передбачено в Конституції; поточні закони що містять конституційноправові принципи й норми; інші акти Верховної Ради України та акти Всеукраїнського референдуму; певні нормативні акти Президента України; деякі нормативні постанови Кабінету Міністрів України; рішення та висновки Конституційного Суду...