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)


 

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

10221. Реформы в области образования и просвещения 28.66 KB
  Реформы в области образования и просвещения В истории народного образования России петровская эпоха занимает особое место уже потому что в это время впервые были созданы светские учебные заведения. Однако потребность в светском образовании определилась ещё в семнадц
10222. Конструктор и деструктор 113 KB
  Конструктор и деструктор. При создании объектов одной из наиболее широко используемых операций которую выполняется в программах является инициализация элементов данных объекта. Единственным способом с помощью которого можно обратиться к частным элементам данн...
10223. Введение в Delphi 43.5 KB
  Введение в Delphi Delphi это мощная среда для скоростной разработки приложений RAD Rapid Application Development. В ее основу легли концепции объектно-ориентированного программирования на базе языка Object Pascal и визуального подхода к построению приложений. Первой средой разработки с...
10224. Среда программирования Delphi 97.5 KB
  Лабораторная работа № 1 Среда программирования Delphi Цель работы: изучить главные части рабочей среды программирования и основные части программы созданной в Delphi, научиться использовать компоненты библиотеки VCL в windowsприложении; познакомиться с компонентами классов...
10225. Стандартные компоненты Delphi 83.5 KB
  Лабораторная работа № 2 Стандартные компоненты Цель работы: изучить стандартные компоненты Delphi научиться использовать компоненты библиотеки VCL в windowsприложениях. В данной работе рассматриваются компоненты страницы Standard Палитры Компонент Delphi. В предыдущей работе...
10226. Работа с формами. Свойства TForm 166.5 KB
  Лабораторная работа № 3 Работа с формами. Свойства TForm Цель работы: изучить основные свойства класса TForm познакомится с некоторыми событиями форм; научиться использовать формы разных стилей в windowsприложениях. Форма представляет собой фундамент программы на котор