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)
А также другие работы, которые могут Вас заинтересовать | |||
| 8860. | Сценарий экологического праздника. И кошке доброе слово приятно. Сценарий экологического праздника | 63.5 KB | |
| Сценарий экологического праздника И кошке доброе слово приятно Цель: представить и обобщить результаты коллективной творческой деятельности учащихся в ходе реализации экологического проекта Кошкин дом. Задачи: обобщить и дополнить знания уча... | |||
| 8861. | Гуманному отношению к животным посвящается | 273 KB | |
| Гуманному отношению к животным посвящается Цель: Формирование системы ценностных ориентаций учащихся через осознание своей роли в экомире расширение положительных нравственных качеств личности, таких как гуманизм, сострадание, милосерди... | |||
| 8862. | С любовью к животным. Класный час | 69.5 KB | |
| Классный час, посвященный Всемирному Дню Защиты животных С любовью к животным ( 3 -7 кл) Цель: Воспитание учеников, как активных, отзывчивых людей. Воспитание гуманных общечеловеческих качеств у детей - забота, сострадание. Воспитание чув... | |||
| 8863. | Классный час на тему: Мы в ответе за тех, кого приручили | 46.5 KB | |
| Классный час на тему: Мы в ответе за тех, кого приручили! Цель: определить причины появления на улицах бездомных собак, обратить внимание жителей на эту проблему. Задачи: Узнать, как собака стала домашним животным, чем является собака для чело... | |||
| 8864. | Классный час: Собака - друг человека. А друзей не бросают в беде | 124 KB | |
| Классный час: Собака - друг человека. А друзей не бросают в беде Цель: воспитание гуманного отношения к бездомным животным и ответственности за домашних питомцев. Прогнозируемый результат: получение школьниками опыта переживан... | |||
| 8865. | Окружающий мир. Про кошек и собак | 118.5 KB | |
| Предмет - Мир вокруг нас Краткая аннотация проекта: Проект проводится в рамках предмета Мир вокруг нас для учеников 2 класса. Метод проектов при изучении тем Про кошек и собак, Как ухаживать за кошкой и собакой позволяет детям не только раскры... | |||
| 8866. | Собака - друг человека | 73.5 KB | |
| Тема: Собака - друг человека Продолжительность: Класс: 2 класс Технологии: компьютерная презентация Аннотация: Урок по теме Собака - друг человека проводится в рамках Года добрых дел. На этом уроке рассматривается произведение Б. Заходера Песн... | |||
| 8867. | Основи фізіології праці і комфортні умови праці | 153 KB | |
| Основи фізіології праці і комфортні умови праці Класифікація основних форм діяльності людини Шляхи підвищення ефективності трудової діяльності людини Класифікація основних форм діяльності людини Характер і організація трудової діяльності роблять сут... | |||
