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)


 

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

7784. Зарубежные педагогически теории конца 19- начала 20 веков 39.5 KB
  Зарубежные педагогически теории конца 19- начала 20 веков Дьюи. Прагматизм в педагогике. Цель воспитания, по Дьюи - формирование личности, умеющей приспособиться к различным ситуациям в условиях свободного предпринимательства. Д. Дьюи и его послед...
7785. История педагогики как наука 30 KB
  История педагогики как наука. Одним из важнейших аспектов развития человеческого общества на протяжении всей его истории является социализация подрастающего поколения, представляющая собой совокупность социальных и психологических процессов, в ходе...
7786. Ушинский о педагогической науке и искусстве воспитания 28 KB
  К. Д. Ушинский о педагогической науке и искусстве воспитания. Ушинский указывал, что теория педагогики должна быть основана на использовании законов анатомии, физиологии, психологии философии, истории и других наук. Она должна открывать законы...
7787. Антон Семенович Макаренко 32 KB
  Макаренко Антон Семенович Макаренко родился в г. Белополье, бывш. Харьковской губернии, в семье мастера малярного цеха железнодорожных мастерских. Макаренко подверг острой критике буржуазную и мелкобуржуазную педагогику. Он писал, ч...
7788. Педагогически взгляды представителей демократического движения в России в сер 19 века 43.5 KB
  Педагогически взгляды представителей демократического движения в России в сер 19 века Герцен. Педагогические взгляды Герцена определились философскими (атеизм и материализм), этическими (гуманизм) и политическими (революционный демократизм) убеждени...
7789. Педагогическая деятельность и взгляды Толстого Л.Н. 32 KB
  Педагогическая деятельность и взгляды Толстого Л.Н. Горячий протестант и страстный обличитель, как назвал его В.И. Ленин, подверг разрушительной критике постановку воспитания и образования в России и в Западной Европе, современные ему школы, утверж...
7790. Педагогическая система Ушинского 28 KB
  Педагогическая система Ушинского В основе педагогической системы Ушинского лежит идея народности. Под народностью Ушинский понимал своеобразие каждого народа, обусловленное его историческим развитием, географическими, природными условиями. В статье ...
7791. Педагогические Взгляды французских материалистов XVIII века 33 KB
  Педагогические Взгляды французских материалистов XVIII века Педагогические идеи Клода Адриана Гельвеция Гельвеций прославился как автор книги Об уме, которая вышла в 1758 г. и вызвала яростные нападки со стороны всех сил реакции, правя...
7792. Педагогическая технология Руссо 31.5 KB
  Педагогическая технология Руссо Основу педагогических взглядов Руссо составляет теория естественного воспитания, которая тесно связана с его социальными взглядами, с его учением о естественном праве Руссо утверждал, что человек родится совершенным, ...