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)
А также другие работы, которые могут Вас заинтересовать | |||
| 35843. | Математические методы анализа экономики | 565 KB | |
| Этот метод называют также методом последовательного улучшения решения плана. Решить задачу методом больших штрафов РЕШЕНИЕ: Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных переход к канонической форме. Из уравнений выражаем искусственную переменную: которую подставим в целевую функцию: Или Базисные переменные х4 х6 Свободные переменные х1 х2 х3 х5 Полагая что свободные переменные равны 0 получим первый опорный план: X1 = 0008010 Базисное... | |||
| 35844. | Функция полезности: определения свойства | 538.06 KB | |
| Самая распространенная функция КоббаДугласа: g = fLK = 0 Одна из задач фирмы заключается в определении количества продукции и в расчете необходимых для ее выпуска затрат с учетом технологической связи между ними и заданными ценами на затраты и продукцию. Модель фирмы в условиях совершенной конкуренции. Неоклассическая теория фирмы построена на предположении что цель фирмы заключается в максимизации прибыли путем выбора вида затрат при заданной ПФ и заданных ценах на продукцию и затраты. Модель фирмы в условиях олигополии. | |||
| 35847. | СРАВНИТЕЛЬНЫЙ АНАЛИЗ ТЕХНОЛОГИЙ РАСШИРЕНИЯ WEB-СЕРВЕРОВ | 236 KB | |
| Диаграммы Use Cse =диаграммы прецедентов диаграммы вариантов использования Диаграмма Use Cse определяет поведение системы с точки зрения пользователя. Диаграмма Use Cse рассматривается как главное средство для первичного моделирования динамики системы используется для выяснения требований к разрабатываемой системе фиксации этих требований в форме которая позволит проводить дальнейшую разработку. Вершинами в диаграмме Use Cse являются актеры и элементы Use Cse. Элементы Use Cse представляют действия выполняемые системой в интересах... | |||
| 35848. | ОБЩИЕ СВЕДЕНИЯ О ЦИФРОВЫХ АВТОМАТАХ. Функционирование цифрового автомата в дискретном времени | 213.5 KB | |
| ОБЩИЕ СВЕДЕНИЯ О ЦИФРОВЫХ АВТОМАТАХ. функционирование цифрового автомата в дискретном времени. Отличительной особенностью дискретного автомата является дискретное множество внутренних состояний и скачкообразность перехода из одного состояния в другое. В реальных автоматах множество внутренних состояний всегда конечно поэтому дискретные автоматы часто называют конечными автоматами или просто автоматами. | |||
| 35849. | Коммутаторы: принцип работы. Основные и дополнительные характеристики | 192 KB | |
| Эту информацию записывает в кадр станцияисточник кадра с помощью своего сетевого адаптера который реализует алгоритм маршрутизации от источника source routing. На данный момент обеспечиваются скорости от нескольких десятков кбит с например GPRS 115 кбит с Протоколы маршрутизации. Протоколы маршрутизации например RIP OSPF NLSP следует отличать от собственно сетевых протоколов например IP IPX. Протоколы маршрутизации используют сетевые протоколы как транспортное средство. | |||
| 35851. | Конституційне право України | 193.5 KB | |
| До таких актів належать: Конституція України основне джерело права; конституційні закони закони що вносять зміни й доповнення до Конституції або скасовують її окремі норми; органічні закони закони прийняття яких передбачено в Конституції; поточні закони що містять конституційноправові принципи й норми; інші акти Верховної Ради України та акти Всеукраїнського референдуму; певні нормативні акти Президента України; деякі нормативні постанови Кабінету Міністрів України; рішення та висновки Конституційного Суду... | |||
