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)


 

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

59502. Свято української писемності і мови 51.5 KB
  Дав слово дотримай його. Дав слово держись не дав кріпись. Слово не горобець вилетить не впіймаєш. Шабля ранить голову а слово душу.
59503. Козацькі забави в літніх таборах 48.5 KB
  Ведуча: Ось подивіться це наші козаки. Ведуча: А зараз довгожданий момент козацька старшина виносить своє рішення. Ведуча: Ось тобі і козаки Цікаво а що потрібно робити щоб такими стати Ведучий: Потрібно мати велику силу а щоб її мати треба багато їсти.
59504. Така любов буває раз в ніколи... - конкурсна програма до Дня святого Валентина 50.5 KB
  Про кохання не говорять, про нього вже все сказано... Тож сьогодні будемо мовчки вдихати аромат закоханості, насолоджуватися захоплюючим видовищем, представленим на сцені, цікавими і веселими конкурсами, романтичною музикою.
59505. Виховний захід: Свято зустрічі весни 50.5 KB
  Мета. Дати поняття про свято Сорока Святих, актуалізувати знання учнів про обрядові пісні, хороводи. Актуалізувати знання про птахів, користь, яку вони приносять.
59506. Ой весела в нас пора, білосніжная зима (розвага для середньої групи дошкільного закладу) 34.5 KB
  Мета: за допомогою вправ та розвивальних ігор закріпити в дошкільнят навички виконання циклічних вправ: біг по колу один за одним, ходьби на носках і по обмеженій площі, стрибків з місця з просуванням уперед...
59507. Сценарій :“Сію, сію, посіваю...” (народні звичаї та обряди) 48.5 KB
  Урожай дорідний в полі і Христос роздається Рік новий йде новим кроком Всі вітаєм з Новим Роком Здоров’я міцного щастя багато чистої води з криниці в полі ярої пшениці Хліба солі на столі і погоди на душі €œСію вію посіваю. На щастя на здоров’я На Новий рік на нове літо...
59508. Сценарій. Останній дзвоник, святкова лінійка 60.5 KB
  Дорогі випускники! Вмийтеся ще раз у нашу шкільну родину, вслухайтеся востаннє в переспів дзвінка і збережіть у своїй пам’яті ці неповторні хвилини прощання зі школою.
59509. Сценарій: Екологічний “КВК” у дошкільному закладі 35.5 KB
  Хід заняття: Діти заходять в зал оформлений у вигляді лісу Вихователь: Доброго дня тобі Лісовичко а ми до тебе в гості прийшли. Лісовичок: В гості А хто вас кликав Я ще від минулих гостей не оговтався: насмітили все понищили звіряток моїх образили ні Закрита сюди дорога...
59510. Теренкур – ігрова програма 52.5 KB
  Карта маршрутів теренкуру вивішується на загальний огляд. Готуються до прийому дітей пункти теренкуру Кросвордист Астролябія Скаут Міфліказ Апачі Арічамі Посмішка Ноти Вигадувалки. Ведучий: Ласкаво просимо до нас на Теренкур...