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)
А также другие работы, которые могут Вас заинтересовать | |||
| 58472. | Listening | 85.5 KB | |
| But before we start our theme let’s find and match antonyms here (в презентации появляются слова, которые облегчат обучающимся понять смысл текста, они должны их просто назвать и соединить вместе: sell, buy, fresh, stale, young, old, always, expensive, cheap, never, finish, begin. | |||
| 58473. | SCHOOLS IN BRITAIN | 330.9 KB | |
| Listen to the dialogue about a typical day at American school and answer the questions. Alice. Ostap, would you like to school with me tomorrow? Ostap. Sure. I have never been in an American school, what is the typical day like at school? Alice. Well, first we go to our homeroom class. | |||
| 58474. | Tolerance | 58 KB | |
| Please open you work book at page fifty six exercise 1. Here you should fill in the gaps using these words: against, according to, of, without. I think 3 minutes on this work. Когда сделали, говорю: please read it one by one and then we will check the answers... | |||
| 58475. | Двомембранні органели і мітохондрії і пластиди. Фотосинтез, дихання | 35.5 KB | |
| Мета: познайомити з будовою та функціями двомембранних органел: мітохондріями та пластидами, фазами мітозу, з клітинним циклом, поняттями, каріотип, фотосинтез, дихання, мітохондрія, хлоропласт, хемосинтез з процесами фотосинтезу та дихання, вчити порівнювати ці два процеси між собою... | |||
| 58476. | Урок биологии | 165 KB | |
| Подготовка учителя к урокам. Постановка цели урока. Структура урока этапы комбинированного урока. Проведение урока биологии Перспективное и поурочное планирование Основой для планирования учебно-воспитательного образовательного процесса по биологии является анализ существующих нормативных требований программ учебных и дидактических пособий и опыта педагогической деятельности учителя. | |||
| 58477. | Вид. Критерии вида | 45.5 KB | |
| Цели урока: обучающие: сформулировать определения понятиям вид критерии вида; изучить критерии вида и их содержание; развивающие: продолжить развитие коммуникативных умений при работе в группах устной монологической речи учащихся... | |||
| 58478. | Уроки Чистоты на территории Пермского края | 3.73 MB | |
| Технологии сортировки отходов уже реализуются в некоторых российских городах. Для успешной организации сортировки очень важна первая ступень раздельный сбор отходов жителями. По статистике каждый из нас ежегодно образует 300 кг отходов. | |||
| 58479. | Рідна домівка, рідна сім’я – тут виростає доля моя. В.Гринько «Сім». В.Сухомлинський «Тетянка усміхається» | 73 KB | |
| Доброго здоровя всім В добрий день і в добрий час Рада всіх вітати вас. Який розділ ви почали вивчати на попередньому уроці Рідна домівкарідна сімятут виростає доля моя З якими піснями ви ознайомилися на минулому уроці Роде наш красний... | |||
| 58480. | Проектирование молодежного кафе – «KFC» | 752 KB | |
| Молодежное кафе, как организация является обществом с ограниченной ответственностью предприятие бытового обслуживания (ООО ПБО). Общество с ограниченной ответственностью является разновидностью объединения капиталов, не требующего личного участия своих членов в делах общества | |||
