67606
Разложение булевых функций по переменным
Лекция
Математика и математический анализ
Это представление называется разложением функции по m переменным x1xm. Разложение по одной переменной 1 Разложение по всем n переменным 2 При Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции fx1xn.
Русский
2014-09-12
174.5 KB
9 чел.
Лекция №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)
А также другие работы, которые могут Вас заинтересовать | |||
| 37096. | Формирование советской политической системы. Временный блок большевиков с левыми эсерами. Разгон Учредительного собрания | 21.09 KB | |
| Для укрепления власти большевики стремились привлечь на свою сторону крестьянство. Большевики и левые эсеры полностью поддержали политику Советского правительства и выступили против передачи власти предстоящему Учредительному собранию. Вскоре новый исполком крестьянского съезда Советов в состав которого были избраны только большевики и левые эсеры присоединился к ВЦИКу.1917 большевики заключили официальный блок с левыми эсерами которые вошли в правительство и возглавили пятьнаркоматов. | |||
| 37097. | Белое движение | 15.26 KB | |
| Цель инициаторов Белого движения ген. Причинами поражения Белого движения являлись: недостаточно скоординированные действия разрозненность очагов антибольшевистского сопротивления отсутствие детальной политической программы поддержки широких слоев населения прежде всего крестьянства. Красное движение Состав красного движения: пролетариат бедное крестьянство солдаты часть интеллигенции и офицерства. Более однородный состав Представители красного движения:... | |||
| 37098. | ВОЕ́ННЫЙ КОММУНИ́ЗМ | 12.75 KB | |
| Политика военного коммунизма включала комплекс мероприятий затронувших экономическую и социальнополитическую сферу. Основой военного коммунизма были чрезвычайные меры в снабжении городов и армии продовольствием свертывание товарноденежных отношений национализации всей промышленности включая мелкую продразверстка снабжение населения продовольственными и промышленными товарами по карточкам всеобщая трудовая повинность и максимальная централизация управления народным хозяйством и страной в целом.... | |||
| 37099. | Причины перехода к НЭПу | 16.36 KB | |
| Массовые крестьянские восстания Падение промышленного производства Волнения городского населения в 7 раз Беспорядки в армии и на флоте Уменьшение валовой продукции Угроза разрыва между рабочим классом и крестьянством Необходимость создания механизма реализации материальных интересов всех слоев населения Обобщение предыдущей практики социалистического строительства Новая экономическая политика экономическая политика проводившаяся в Советской России и СССР в 1920е годы. Новая экономическая политика имела целью восстановление... | |||
| 37100. | Национальная политика советской власти. Образование Союза Советских Социалистических Республик | 20.49 KB | |
| Образование Союза Советских Социалистических Республик Объединительное движение по созданию Советского многонационального государства началось сразу после победы Октябрьской революции и распада империи и прошло три этапа. ознаменовался рождением Российской Советской Федеративной Социалистической Республики которая последовательно по мере реализации курса на равноправие народов превращалась в федерацию нового типа. На первом этапе на территории бывшей царской России возникли автономные республики территориальные автономии с учетом... | |||
| 37101. | Национальная политика первых лет Советской власти. Образование СССР | 17.32 KB | |
| Большевистская идея мировой революции и создания в будущем Всемирной Федеративной Республики Советов форсировала новый объединительный процесс. В связи с победой советской власти на основной территории бывшей Российской империи возникли и другие предпосылки для объединительного процесса единый характер политического строя диктатура пролетариата в форме республики Советов сходные черты организации государственной власти и управления. В большинстве республик власть принадлежала национальным коммунистическим партиям входившими в состав... | |||
| 37102. | Индустриализация | 36.5 KB | |
| Необходимость индустриализации: экономическая: крупная промть определяет экономическое развитие страны в целом. Военнополитическая без индустриализации невозможно обеспечить техникоэкономическую независимость страны и ее оборонную мощь. Проблемы создания индустриализации стали первоочередными в конце 1925г. Источники индустриализации: внутренние накопления: внутренние займы выкачивание средств из деревни доходы от внешней торговли дешевая рабочая сила энтузиазм трудящихся труд заключенных. | |||
| 37103. | Коллективизация сельского хозяйства и ее последствия | 19.56 KB | |
| Коллективиза́ция это процесс объединения единоличных крестьянских хозяйств в коллективные хозяйства колхозы в СССР. объединению подлежало 25 процентов крестьянских хозяйств. Основу аграрного сектора экономики страны составляли мелкие крестьянские хозяйства которые имели полунатуральный характер. | |||
| 37104. | Начальный период Великой Отечественной войны. Причины поражения Красной Армии на первом этапе войны | 15.43 KB | |
| Причины поражения Красной Армии на первом этапе войны. 22 июня 1941 года нацистская Германия вероломно нарушив договор о ненападении внезапно без объявления войны нанесла по Советскому Союзу мощный удар. Этот день вошел в историю нашей страны трагической датой стал днем начала неимоверно тяжелой войны советского народа против фашизма справедливо названной Великой Отечественной войной. | |||
