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)


 

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

82671. Понятие, виды, признаки преступлений против интеллектуальной собственности 67 KB
  Интеллектуальные права на результаты исполнительской деятельности (исполнения), на фонограммы, на сообщение в эфир или по кабелю радио- и телепередач (вещание организаций эфирного и кабельного вещания), на содержание баз данных, а также на произведения науки, литературы и искусства...
82672. Роль и значение биофабрик 17.71 KB
  Биофабрики располагают значительной территорией специальными производствами лабораторными корпусами и вспомогательными сооружениями. Государственный контроль выпускаемой продукции на её безвредность чистоту специфичность и активность осуществляет контрольная лаборатория Биофабрики возглавляемая...
82673. Особливості майнових прав авторів творів 51.78 KB
  Предмет дослідження – загальна характеристика майнових прав автора твору. Мета роботи зумовлює виконання таких завдань: 1 дати визначення основним майновим правам автора твору; 2 охарактеризувати основні майнові прав автора.
82674. Велик Вітчизняна війна 85.63 KB
  Міжнародна обстановка і зовнішня політика СРСР напередодні другої світової війни. У цій війні вирішувалася не тільки доля СРСР але і майбутнє світової цивілізації прогресу і демократії. У тих умовах спроби СРСР Великобританії та Франції створити систему повної безпеки в Європі з метою нейтралізації...
82675. Рекомендацій щодо поліпшення умов праці на виробництві 92.09 KB
  На сучасному етапі розвитку України спостерігається загострення проблем в області організації нормальних умов праці. Це зумовлено тим, що значна частина працівників працює у шкідливих або важких умовах. Тому проблема покращення умов праці для будь-якого підприємства є актуальною.
82676. Система правових засобів захисту права власності 48.59 KB
  Суспільство не може існувати без тих чи інших відносин власності: ці відносини визначають його економічну структуру, ідеологічне, моральне і політичне обличчя, тому даний аспект правового регулювання посідає важливе місце у загальній структурі суспільних правовідносин та є актуальним у процесі...
82677. Заболевания верхних дыхательных путей и их осложнения 31.46 KB
  Провоцируются эти заболевания как правило местным или общим переохлаждением на фоне ослабленного иммунитета или перенапряжения организма. Причиной заражения при этих заболеваниях может быть инфицирование от больного человека вирусной и бактериальной инфекцией.
82678. Our Homeland – Kazakstan 22.31 KB
  The Constitution defines the state system as a form of presidential republic considering it the most flexible version in conditions of today. The President ensures coordinated performance of all the branches of state power and accountability of power bodies to the people.
82679. Торговые и неторговые автоматы. Промышленные роботы и манипуляторы 25.61 KB
  Промышленный робот –- автономное устройство состоящее из механического манипулятора и перепрограммируемой системы управления которое применяется для перемещения объектов в пространстве и для выполнения различных производственных процессов.