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.  Рассмотрим произвольный набор значений . Левая часть равенства имеет вид . Правая часть

(в сумме только одно произведение отлично от нуля: то в котором )

.

Теорема доказана.

Разложение по одной переменной

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
  Основи фізіології праці і комфортні умови праці Класифікація основних форм діяльності людини Шляхи підвищення ефективності трудової діяльності людини Класифікація основних форм діяльності людини Характер і організація трудової діяльності роблять сут...