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)
А также другие работы, которые могут Вас заинтересовать | |||
| 52226. | Проблема мусора | 22.5 KB | |
| Цель урока: выяснить какие существуют группы отходов откуда берётся мусор сроки разложения различных видов мусора рассмотреть состав мусорной корзины найти пути решения проблемы отходов; учить детей взаимодействию в группе развивать умения делать выводы; воспитывать экологическую культуру. Образовательные задачи: учащиеся должны знать виды и проблемы мусора и предлагать пути их решения; самостоятельно искать пути решения проблемы и добывать знания из дополнительных источников; пользоваться приобретёнными знаниями для решения... | |||
| 52228. | Україна в геополітичних планах країн Антанти і Троїстого союзу | 72 KB | |
| Розкрити причини та привід до початку першої світової війни. Війна; привід до війни світова війна ринки збуту воєннополітичний блок причини війни ультиматум імперіалізм. оформлення союзу Антанта; 28 червня 1914 року вбивство в Сараєво ерцгерцога Франца Фердинандаспадкоємця австрійського престолу; 10серпня 1914 року початок першої світової війни оголошення Німеччиною війни Росії. Після цього уроку учні зможуть: називати роки утворення... | |||
| 52229. | Географічне положення Антарктиди. Історія відкриття і дослідження | 2.76 MB | |
| Мета уроку: сформувати e учнів систему знань про географічне положення Антарктиди; охарактеривувати своєрідність географічного положення материка; розповісти про історію відкриття і дослідження Антарктиди; удосконалювати вміння і навички роботи з картою; розвивати інтерес до предмету. Обладнання: карта Антарктиди контурні карти підручники портрети мандрівників презентація PowerPoint. Ми вирушаємо до Антарктиди слайд 1 Про цій материк полярник А. | |||
| 52230. | Антарктида – льодовий материк планети | 93 KB | |
| Цілі: Виявити особливості унікальності і своєрідності географічного положення природи Антарктиди та Південного океану. Тип уроку: засвоєння нових знань Форма уроку: урок конференція Обладнання: фізична карта півкуль і Антарктиди атлас контурна карта мультимедійна презентація I. Майже в центрі материка розміщений Південний полюс тому всі береги Антарктиди дивляться на північ. Як бачимо географічне положення Антарктиди дуже відрізняється від географічного положення інших континентів. | |||
| 52231. | Античний світ: подорож у минуле | 36 KB | |
| Перше завдання Візитки команд Домашнє завдання . Другим завданням нашої історичної подорожі є похід до керамічної майстерні. Завдання дітям: виконати малюнок на кольоровому папері чорним фломастером: Розпис амфор . Завдання: розіграти сценку давньогрецької комедії та трагедії з використанням масок. | |||
