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)
Разложение по всем 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 | |
| Они подразделяются на общие принципы относящиеся к механизму государства в целом и частные принципы действие которых распространяется лишь на некоторые звенья государственного механизма отдельные органы или группы органов. Общие принципы принято делить на две группы. К первой относятся принципы закрепленные в Конституции Российской Федерации ко второй принципы сформулированные в Федеральном законе Об основах государственной службы Российской Федерации и иных федеральных законах О Конституционном Суде Российской Федерации О... | |||
