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)
А также другие работы, которые могут Вас заинтересовать | |||
| 49074. | Применение нейронных сетей для принятия решений | 288.5 KB | |
| Существует множество областей применения искусственного интеллекта: принятие решений доказательства теорем игры творчество распознавание образов обработка данных на естественном языке обучающиеся сети нейросети и т. Мой выбор обусловлен стремлением узнать эффективно ли использовать нейросети при принятии решений об освобождении от оплаты за обучение учащихся детских школ искусств. Цель данной курсовой работы заключается в том чтобы показать... | |||
| 49075. | Крупные детали (коленчатые валы, муфты, промежуточные валы и др. детали должны иметь повышенную твёрдость 260-300 НВ) | 242 KB | |
| Конструкционные стали Улучшаемые стали. Конструкционные стали применяемые для изготовления валов Термическая обработка сталей. Выбор термической обработки стали марки 40ХНМА. | |||
| 49076. | Расчет термической обработки стали марки 5ХНМ | 275.5 KB | |
| Если обрабатывается мягкий материал (дерево, пластмассы, цветные металлы) или при обработке стали и чугуна применя ются малые скорости резания и стружка имеет малое сечение, то в единицу времени на процесс резания затрачивается мало энергии. Если обработка происходит при больших скоростях резания, обрабатываются твердые металлы и стружка имеет большое сечение | |||
| 49077. | ИССЛЕДОВАНИЕ ОРГАНА КОНТРОЛЯ ПОГАСАНИЯ ДУГИ | 136.5 KB | |
| Исследуемая модель линии При угле передачи 0 и переходном сопротивлении Rпер=30 Ом напряжение на зажимах реактора относительно земли в фазе А где первый график модуль напряжения а второй угол. Используя значения напряжения после t=0.02 с изменяя место короткого замыкания а также значение угла передачи можно получить зависимости: Рисунок 2 Зависимость напряжения на реакторе от места повреждения при угле передачи 30 Рисунок 3 Зависимость напряжения на реакторе от места повреждения при... | |||
| 49080. | ДАТЧИК ВЛАЖНОСТИ | 248.5 KB | |
| Описание физической величины Описание и выбор метода измерения влажности Метод высушивания Дистилляционный метод Экстракционные методы Химический метод Метод СВЧ-влагометрии Нейтронный метод Инфракрасные влагомеры Кондуктометрические датчики Выбор метода Выбор и описание датчика Влагомер ВП4 Влагомер для порошкообразных материалов Датчик влажности для формовочной смеси Датчик влажности для зерна Автоматическая... | |||
| 49081. | Разработка рациональной системы применения удобрений в конкретных почвенно-климатических условиях хозяйства | 1.06 MB | |
| Производственные показатели для составления системы применения удобрений Выход навоза заготовка хранение и технология внесения органических удобрений Составление системы применения удобрений в расчете на планируемый урожай при освоении севооборота Составление системы применения удобрений на планируемый урожай в освоенном севообороте | |||
