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)


 

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

52226. Проблема мусора 22.5 KB
  Цель урока: выяснить какие существуют группы отходов откуда берётся мусор сроки разложения различных видов мусора рассмотреть состав мусорной корзины найти пути решения проблемы отходов; учить детей взаимодействию в группе развивать умения делать выводы; воспитывать экологическую культуру. Образовательные задачи: учащиеся должны знать виды и проблемы мусора и предлагать пути их решения; самостоятельно искать пути решения проблемы и добывать знания из дополнительных источников; пользоваться приобретёнными знаниями для решения...
52228. Україна в геополітичних планах країн Антанти і Троїстого союзу 72 KB
  Розкрити причини та привід до початку першої світової війни. Війна; привід до війни світова війна ринки збуту воєннополітичний блок причини війни ультиматум імперіалізм. оформлення союзу Антанта; 28 червня 1914 року вбивство в Сараєво ерцгерцога Франца Фердинандаспадкоємця австрійського престолу; 10серпня 1914 року початок першої світової війни оголошення Німеччиною війни Росії. Після цього уроку учні зможуть: називати роки утворення...
52229. Географічне положення Антарктиди. Історія відкриття і дослідження 2.76 MB
  Мета уроку: сформувати e учнів систему знань про географічне положення Антарктиди; охарактеривувати своєрідність географічного положення материка; розповісти про історію відкриття і дослідження Антарктиди; удосконалювати вміння і навички роботи з картою; розвивати інтерес до предмету. Обладнання: карта Антарктиди контурні карти підручники портрети мандрівників презентація PowerPoint. Ми вирушаємо до Антарктиди слайд 1 Про цій материк полярник А.
52230. Антарктида – льодовий материк планети 93 KB
  Цілі: Виявити особливості унікальності і своєрідності географічного положення природи Антарктиди та Південного океану. Тип уроку: засвоєння нових знань Форма уроку: урок конференція Обладнання: фізична карта півкуль і Антарктиди атлас контурна карта мультимедійна презентація I. Майже в центрі материка розміщений Південний полюс тому всі береги Антарктиди дивляться на північ. Як бачимо географічне положення Антарктиди дуже відрізняється від географічного положення інших континентів.
52231. Античний світ: подорож у минуле 36 KB
  Перше завдання Візитки команд Домашнє завдання . Другим завданням нашої історичної подорожі є похід до керамічної майстерні. Завдання дітям: виконати малюнок на кольоровому папері чорним фломастером: Розпис амфор . Завдання: розіграти сценку давньогрецької комедії та трагедії з використанням масок.