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)


 

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

75880. Структурні та мовні особливості словникових статей словників-тезаурусів, двомовних, асоціативних, частотних словників 48 KB
  Идеографические словари. Словари-тезаурусы сделанные по конкретным проблемным областям например по электронике геологии торговле политике широко используются в системах автоматического поиска. Переводные словари. Франкорусские словари представлены в частности словарем К.
75881. Структурні та мовні особливості словникових статей словників історичних та етимологічних, словників мовних форм (орфографічних, орфоепічних, морфемних), словників мовленнєвого використання, ономастиконів 47 KB
  Щербой в статье Опыт общей теории лексикографии: Историческим в полном смысле этого термина был бы такой словарь который давал бы историю всех слов на протяжении определенного отрезка времени начиная с той или иной определенной даты или эпохи причем указывалось бы не только возникновение новых слов и новых значений но и их отмирание а также их видоизменение. С 1984 издается Словарь русского языка XVIII в. К числу наиболее полных словарей такого типа для русского языка принадлежит четырехтомный Этимологический словарь русского языка М. Не...
75883. Проблеми створення комп’ютерних систем розпізнавання усного мовлення. Методи виділення й упізнавання елементів мови при обробці усного мовлення 29.83 KB
  Задача распознавания речи состоит в автоматическом восстановлении текста произносимых человеком слов фраз или предложений на естественном языке. Только в последние десятилетия компьютерная техника достигла такого уровня когда стала осмысленной задача распознавания слитной или даже спонтанной устной речи. На этом этапе выяснилось что для решения задачи распознавания речи недостаточно уметь распознавать отдельные звуки и слова команды с надежностью сравнимой с надежностью распознавания отдельных команд человеком. Поэтому задачу...
75884. Структурні компоненти словників. Особливості словникових статей нетрадиційних лінгвістичних словників 282.5 KB
  Каждая зона содержит особый тип словарной информации. Первая зона лексический вход словарной статьи вокабула или лемма. Лексический вход обычно выделяют полужирным шрифтом и поэтому в жаргоне лексикографов и редакторов эта зона часто называется черным словом. В толковом словаре после лексического входа чаще всего следуют зона грамматической информации и зона стилистических помет.
75885. Структурні компоненти словників. Особливості словникових статей нетрадиційних лінгвістичних словників. Основные структурные компоненты словаря 37.09 KB
  Каждая зона содержит особый тип словарной информации. Первая зона лексический вход словарной статьи вокабула заголовок словарной статьи или лемма син. Поэтому в жаргоне лексикографов и редакторов эта зона часто называется черное слово. В толковом словаре после лексического входа чаще всего следует зона грамматической информации и зона стилистических помет.
75886. Гіпертекст. Базові функції гіпертексту. Види гіпертексту 28.87 KB
  Общеизвестным и ярко выраженным примером гипертекста служат вебстраницы документы HTML язык разметки гипертекста размещённые в Сети. Узлы связаны разнообразными отношениями типы которых задаются разработчиками программного обеспечения гипертекста или самим читателем. Компьютерные реализации гипертекста бывают иерархическими или сетевыми. Иерархическое древовидное строение гипертекста существенно ограничивает возможности перехода между его компонентами.
75887. Морфологічний та синтаксичний аналіз письмової сови. Кількісні характеристики морфем, граматичних категорій та синтаксичних конструкцій 25.93 KB
  МОРФОЛОГИЯ как часть грамматики это учение о слове о его грамматических классах частях речи морфологических категориях и формах. ЗНАМЕНАТЕЛЬНЫЕ ЧАСТИ РЕЧИ имя существительное имя прилагательное имя числительное местоимение глагол наречие категория состояния традиционно выделяют по совокупности признаков к которым относят: 1 обобщенное грамматическое частеречное значение отвлеченное от лексических и частных морфологических значений слов данной части речи; 2 характерный для каждого класса комплекс морфологических категорий и...
75888. Комп’ютерні технології і сучасна лексикографічна наука 26.72 KB
  Множество различных компьютерных лексикографических программ можно разделить на две больших группы: программы поддержки лексикографических работ и автоматические словари АС различных типов включающие лексикографические базы данных. Автоматические словари. Иными словами различаются автоматические словари конечного...