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)
А также другие работы, которые могут Вас заинтересовать | |||
| 85186. | Новая экономическая политика, ее сущность и значение для развития хозяйства БССР | 26.41 KB | |
| Ответом на эти вопросы стала новая экономическая политика НЭП. НЭП это система экономических социальных политических и культурных мер направленных на внедрение рыночных отношений в народном хозяйстве. В первые годы НЭПа практиковалось натуральная и денежная оплата труда. В сфере с х нэп проявилась в следующем: 1 Вместо продразвёрстки был введен продналог который был в два раза меньше. | |||
| 85187. | БССР в годы первых пятилеток. Форсированная индустриализация и принудительная коллективизация | 26.78 KB | |
| Дальнейшее развитие металло-обрабатывающей химической торфяной и др. отраслей развитие энергетики и увеличение мощностей электростанций. Предусматривалось развитие лёгкой и продовольственной промышл. | |||
| 85188. | Духовная и культурная жизнь БССР в 1920-1930гг.: достижения и противоречия | 25.66 KB | |
| Культуры вылученне белорусов на партыйую советскую профсоюзную и общественную работу перевод делопроизводства государственного партийного профессионального и кооперативного аппаратов на белорусский язык. Центральная место в мероприятиях в белорусизации отводилось проблеме языка так как в республике язык выполняла очень мизерны объем соц. Преобладала русский язык. При этом официально было заявлено что на территории БССР признаются равноправными языки белорусский русский еврейский и польский. | |||
| 85189. | Западная Беларусь в составе Польши | 27.1 KB | |
| Было введено принятое в Польше административно-тер деление, созданы 4 воеводства: Виленское, Полесское, Новогрудское, Белостокское. Эти воеводства делились на 29 поветов аповеты на гимны. | |||
| 85190. | Начало второй мировой войны. Вхождение Западной Беларуси с состав БССР | 26.28 KB | |
| Вхождение Западной Беларуси с состав БССР. Беларуси принял декларацию об установлении советской власти на всей освобожденной территории i высказался за вхождение в состав БССР. Приняты законы о включении Западной Беларуси в состав СССР i воссоединение с БССР. Единогласно делегаты высказались и за вхождение в БССР. | |||
| 85191. | Начало Великой Отечественной войны. Ход военных действий на советско-германском фронте в 1941-1942 годах | 27.92 KB | |
| Для войны против СССР Гитлер сосредоточил подавляющую часть своих сухопутных сил. Однако основной причиной такого огромного успеха немцев в первые недели войны является то что Красная армия сама готовилась к наступлению. Сталин прекрасно понимал что войны с Германией не избежать но он не думал что Гитлер нарушит пакт МолотоваРибентропа о ненападении. | |||
| 85192. | Фашистский оккупационный режим на территории БССР | 26.93 KB | |
| К концу августа 1941 г гитлеровцы оккупировали всю территорию Бел. На захваченной территории гитлеровцы установили оккупационный режим- систему политических, идеологических, экономических, и военных мер направленных на ликвидацию существующего общественного и гос. строя, грабёж нац. богатства, уничтожение населения | |||
| 85193. | Коренной перелом в ходе Великой Отечественной войны | 29.96 KB | |
| Коренной перелом начатый под Сталинградом был завершен в ходе Курской битвы и сражениях за р. в ходе Киевской наступательной операции 6 ноября столица Украины была освобождена. В ходе оборонительных боев к концу декабря 1943 г. | |||
| 85194. | Партизанское и подпольное движение в БССР | 28.28 KB | |
| Один из первых партизанских отрядов был организован уже на пятый день войны в Пинске под командованием Коржа насчитывал 60 чел. Полесской области действовал отряд под командованием Бумажкова и Павловского. В июле 41 начал боевые действия отряд пол командованием Шмырёва в Вит. | |||
