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)


 

А также другие работы, которые могут Вас заинтересовать

82444. Феминизация лексических изменений в европейских языках 31.66 KB
  Под давлением некоторых организаций правительство Франции 23 февраля 2012 года приняло постановление об ограничении употребления слова mdemoiselle . В современной Франции обращение mdemoiselle воспринимается как комплименттак как подразумеваетчто женщина молода и свободна но существует также давняя театральная традиция обращаться к известным актрисам mdemoiselle . Представительницы феминисткой группы в сентябре 2011 года развернули активные кампании против слова mdemoiselle заявив что оно является оскорбительным и подразумевает...
82445. Место и роль гипер-гипонимических отношений в формировании языковой картины мира 34.75 KB
  Гиперонимы и гипонимы Синонимические ряды Большую роль в формировании ЯКМ играют гиперонимы и гипонимы. Гиперонимы – слова с широким родовым значением например véhicule m – транспортное средство передвижения Гипонимы – слова с конкретным точечным значение например слово рука в русском языке – это гипероним а во французском существуют гипонимы – min f – кисть руки brs m –рука от плеча до кисти.Спортивные мероприятия ctivités sportives Существуют гипонимы которые передаются целым предложением.
82446. Способы передачи французских фразеологизмов на русский язык 33.1 KB
  Возможность полноценной передачи фразеологизмов зависит в основном от соотношений между их единицами во французском и русском языках. При этом существуют 3 способа передачи французских фразеологизмов на русский язык: Французский фразеологизм имеет в русском языке точное независящее от контекста полноценное соответствие.
82447. Связь языка и культуры, характер связи 30.71 KB
  Язык – это явление культуры. Именно благодаря языку человек осознаёт себя как своё я выделяет себя из внешнего мира тем самым отличаясь от животных. Язык – единственное средство связи между разными поколениями именно благодаря ему мы усваиваем культуру прошлых поколений.
82448. Отражение национально-культурного различия в фразеологизмах 33.45 KB
  Хотя французы и говорят что одежда не делает монаха они встречают незнакомца нередко именно по одёжке hbillé comme un mnnequin манекен; 3. Понастоящему образованным считается тот кто в совершенстве владеет родным языком prler comme un livre un orcle un nge 4. Неслучайно имеются фразеологизмы с опорным словом rire rire comme une bleine кит comme un gmin gosse – ребенок ; 5.
82449. Вильгельм Гумбольдт о связи языка и культуры 30.64 KB
  Одним из первых учёных обратившихся к проблеме взаимоотношения языка и культуры был Вильгельм фон Гумбольдт17671835основатель учения о ЯКМ. Поражает его лингвистический кругозор: владел языками разных лингвистических семей венгерский санскрит китайский испанский французский языки американских индейцев. Высказал мнение что характер связи языка и мышления глубок и противоречив.
82451. Сепир и Уорф «Об отражении в языке национально-культурных особенностей его носителей» 24.24 KB
  Бенджамин ли Уорф 18971941 – ученик Эдуарда Сэпира.ли Уорф стремился обосновать свою гипотезу о влиянии языка не только на восприятие мира людей но и на их поведение. ли Уорф изучал языки американских индейцев.
82452. Практическая значимость знания и владения межкультурной коммуникации 32.55 KB
  Но в некоторых странах не принято пожимать руку женщинам а потому подождите пока женщина сама протянет вам руку. Во Франции и странах Средиземноморья распространены поцелуи в щеку в Латинской Америке объятия. Во многих странах религия оказывает влияние на деловую жизнь в том числе на распорядок дня и рабочие месяцы и дни. В других странах они могут иметь совсем иное не всегда приличное значение.