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)
А также другие работы, которые могут Вас заинтересовать | |||
| 41961. | Проектування засобів введення та редагування даних | 334.34 KB | |
| Теоретична частина: Форма один з об'єктів баз даних. Форма це бланк що підлягає заповненню або маска що накладається на набір даних. Існують такі види екранних форм: стовпцева рядкова таблична вільна таблична діаграмна субформа. | |||
| 41962. | Розроблення форм вихідних документів | 438.33 KB | |
| Вивчення послідовності та засобів розроблення вихідних документів в середовищі СУБД об'єктів звітів та їх властивостей виглядів звітів та застосування обчислюваних об'єктів. Можна скористатися майстром звітів і спроектувати звіт самостійно вручну використовуючи набір інструментів пропонованих конструктором звітів. Конструктор звітів це частина програми яка отримує на вхід потік даних і впорядковує їх у форму зручнішу для читання. Конструктор звітів надає такі можливості: групування записів за... | |||
| 41963. | Розроблення керуючого інтерфейсу інформаційної системи | 307.76 KB | |
| Теоретична частина: Макрос це такий самий об'єкт як і інші об'єкти в ccess таблиці запити форми і звіти. На відміну від макросів в електронних таблицях макроси в ccess зазвичай використовуються не для дублювання окремих натискань клавіш або руху миші а виконують певні завдання користувача наприклад відкривають форму або запускають звіт. ccess дає змогу вибрати і виконати за допомогою макросів 48 макрокоманд. Наприклад можна створити макрос який буде відкривати форму копіювати певне значення в інший елемент керування... | |||
| 41964. | Написать программу на языке C++, моделирующую поведение курицы (Hen) путём создания соответствующего класса | 14.17 KB | |
| Листинг программы: include iostrem include cstring include cmth include cstdlib using nmespce std; clss Chickhen { privte: chr nme; double w h f; Кормление урожай норма кормления sttic int e; норма яйценосности public: Chickhenvoid; Chickhenchr double; Chickhenconst Chickhen ; virtul Chickhen; double hrvest; double feeddouble; }; int Chickhen::e=10; Chickhen::Chickhen { w=0; h=0; f=0; nme=new chr[7]; strcpy nme nonme ; } Chickhen::Chickhen chrndouble F { nme=new chr[strlenn1]; strcpynmen; f=F; h=0; w=0;... | |||
| 41968. | Дослідження стійкості ланки другого порядку | 114.05 KB | |
| Для лінійних систем автоматичного керування, які описуються характеристичним рівнянням виду a0pn+a1pn-1+…+an-1p+an=0 стійкість не залежить від величини і вигляду збурення і визначається коренями характеристичного рівняння, яке залежить від параметрів системи Для зручності зафіксуємо L C та змінюватимемо R withinttrns; urovnenie:=TTpp2xiTp1; h:=k p urovnenie; l:=invlplcehpt; sol:=solveurovneniep: sol[1];sol[2]; Аперіодичний процес Вибираємо L=50мГн.05;C:=2010^6;R:=250;T:=sqrtLC;xi:=RsqrtC L 2;k:=1;p1:=sol[1];p2:=sol[2];задання параметрів для даного виду процесу l:=invlplcehpt;розрахунок зворотнього перетворення Лапласа plotlt=0.05;C:=2010^6;R:=100;T:=sqrtLC;xi:=RsqrtC L 2;k:=1;p1:=sol[1];p2:=sol[2]; l:=invlplcehpt:... | |||
| 41969. | ДОСЛIДЖЕННЯ ВЕКТОРНИХ ПЛОТТЕРІВ | 78.68 KB | |
| Все рассматриваемые здесь команды находятся в основной части языка HPGL 2. Первыми идут команды ини рйализации для установки размера изображения и другие параметры после них следуют команды для прорисовки линий фигур и трок символов а также одна или две команды для завершения процесса. Некоторые команды имеющие числовые аргументы требуют целых значений в то время как другие команды допускают наличие чисел с десятичной точкой. Некоторые команды передают результаты обратно хосткомпьютеру: например 01 сообщает идентификацию модели... | |||
