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)


 

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

84096. Демократический режим и его признакии 22.3 KB
  В демократическом государстве существует взаимная ответственность государства и личности.Предоставление широкой свободы личности предприятиям и организациям в сфере экономической деятельности которая при демократическом политическом режиме составляет основу материального благосостояния граждан.Реальная гарантированность прав и свобод личности и реальная возможность реализовать данные права и свободы.Наличие эффективной и квалифицированной судебной защиты прав и свобод личности от произвола и беззакония со стороны кого бы то ни было.
84097. Антидемократические государственно-правовые режимы 25.92 KB
  Основными чертами тоталитарного политического режима являются следующие: государство стремится к глобальному господству над всеми сферами общественной жизни к всеохватывающей власти; общество полностью отчуждено от политической власти но оно не осознает этого ибо в политическом сознании формируется представление о единстве слиянии власти и народа; господствует монопольный контроль над экономикой средствами массовой информации культурой религией и т. фактически устраняется плюрализм; происходит централизация государственной...
84098. Функции государства: понятие, признаки, содержание 20.68 KB
  Функции государства это основные направления внутренней и внешней деятельности государства в которых выражаются и конкретизируются его классовая и общечеловеческая сущность и социальное назначение. В этом определении выделены наиболее существенные признаки функций государства. Функции государства непосредственно выражают и предметно конкретизируют его классовую и общечеловеческую сущность.
84099. Внутренние функции государства современного государства и их содержание 22.02 KB
  Охранительная функция: Это функция государственной деятельности проявляется в обеспечении государством общественного и правового порядка защите и охране прав и интересов граждан и организаций защите конституционного строя и государства от противоправных посягательств. Обеспечение внутреннего мира и согласия в обществе урегулирования общественных отношений снятие социальных противоречий неизбежных в обществе состоящем из различных классов групп слоев это насущная необходимость одна из тех причин которые вызывали возникновение...
84100. Внешние функции государства современного государства и их содержание 23.61 KB
  Защита государства от вооруженных нападений других государств. Функция защиты из вне: Данная функция является важнейшим направлением деятельности государства ибо она нацелена на защиту мирного труда суверенитета и территориальной целостности государства. 30 Формы и методы осуществления функций государства Государство должно выполнять свои функции в присущих ему формах применять в своей деятельности различные методы.
84101. Механизм государства, государственный аппарат: понятие и их соотношение 21.97 KB
  Механизм государства есть та реальная организационная материальная сила располагая которой государство осуществляет власть. Механизм является структурным и предметным олицетворением государства представляет собой материальное вещество из которого оно состоит. Можно сказать что механизм суть деятельное постоянно функционирующее выражение государства.
84102. Понятие государственного органа. Классификация государственных органов 24.37 KB
  Классификация государственных органов Первичным и важнейшим структурным элементом механизма государства является орган государства. Государственный орган это звено элемент механизма государства участвующее в осуществлении функций государства и наделенное для этого властными полномочиями. Раскрытие понятия признаков данного органа позволяет глубже познать механизм государства в целом. Хотя орган государства и обладает определенной самостоятельностью автономией он служит частью единого механизма государства занимает в государственной...
84103. Государственные учреждения в механизме государства 22.34 KB
  Для обозначения этой системы обычно используют понятие механизм государства. Механизм государства это совокупность государственных органов осуществляющих государственную власти и обеспечивающих реализацию функций государства. Первичной ячейкой государства выступают его органы и учреждения.
84104. Принципы формирования и деятельности государственного аппарата 21.91 KB
  Они подразделяются на общие принципы относящиеся к механизму государства в целом и частные принципы действие которых распространяется лишь на некоторые звенья государственного механизма отдельные органы или группы органов. Общие принципы принято делить на две группы. К первой относятся принципы закрепленные в Конституции Российской Федерации ко второй принципы сформулированные в Федеральном законе Об основах государственной службы Российской Федерации и иных федеральных законах О Конституционном Суде Российской Федерации О...