Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2023-01-02 | 28 |
5.00
из
|
Заказать работу |
|
|
Любая функция переменных , полученная путем суперпозиции перечисленных элементарных булевых функций, также является булевой функцией, определенной на множестве наборов переменных . Таблица истинности в данном случае будет иметь следующий вид:
0 0.…..0 0 0 0.…..0 1 0 0.…..1 1 ………………… 1 1.…..1 1 | ……………… |
На основании теоремы о булеане, данная таблица будет иметь строк (т.к. мера множества переменных ), т.е. число всех наборов от переменных равно , а число всевозможных булевых функций, зависящих от переменных равно на основании той же теоремы.
Два набора и называются соседними по -ой компоненте, если они различимы только по значению переменной , т.е.
,
.
Набор называется предшествующим к набору и обозначается , если выполняется неравенство при всех значениях .
Переменная называется существенной, если на наборах, соседних по -ой компоненте, функция принимает различные значения, в противном случае переменная является фиктивной.
Замечание. Обнаружить фиктивные переменные некоторой функции можно не только по таблице истинности, но и аналитически: после всех элементарных преобразований функция содержит только существенные переменные.
Пример: ,
следовательно, переменная является фиктивной, а и - существенными.
Функции и называются равными, если они могут быть получены одна из другой путем добавления или исключения фиктивных переменных.
Функция называется монотонной, если для любых двух наборов и , таких что выполняется .
Теорема [2]: Какова бы ни была булева функция , она может быть представлена в следующем виде:
и данное представление называется разложением функции по -ой компоненте.
|
Рассмотрим функцию трех переменных и разложим ее последовательно по всем переменным:
где дизъюнкция берется по всем возможным наборам переменных . Аналогичное разложение может быть получено для большего числа переменных.
Приведенное разложение называется совершенной дизъюнктивной нормальной формой (СДНФ).
Данная форма называется совершенной, потому что каждое слагаемое в дизъюнкции включает все переменные, дизъюнктивной, потому что главная операция – дизъюнкция и нормальной, т.к. существует алгоритм проверки равносильности. При этом
Иными словами, для того, чтобы построить СДНФ, необходимо в таблице истинности рассмотреть те наборы, на которых функция равна 1 и навесить отрицания на те переменные, которые на данных наборах равны 0 (т.к. все остальные слагаемые будут равны 0 по тождеству 9).
Если в данном разложении учесть двойственность дизъюнкции и конъюнкции (см. ранее) и заменить все дизъюнкции на конъюнкции, а конъюнкции – на дизъюнкции, получаем следующее представление, имеющее название СКНФ (совершенная конъюнктивная нормальная форма):
Иными словами, для того, чтобы построить СДНФ, необходимо в таблице истинности рассмотреть те наборы, на которых функция равна 0 и навесить отрицания на те переменные, которые на данных наборах равны 1 (т.к. все остальные сомножители будут равны 1 по тождеству 5).
Если в разложении булевой функции заменить все дизъюнкции на функцию и учесть тождество 12 , получаем следующее представление, имеющее название СПНФ [3] (совершенная полиномиальная нормальная форма) или полином Жигалкина [4]:
,
где a,b,c,…,h – некоторые коэффициенты, которые могут быть найдены по таблице истинности.
СПНФ может быть также построена методом навешивания двойного отрицания. Основное необходимое тождество в данном случае - .
Пример: .
Функция называется линейной, если в ее разложении в СПНФ отсутствуют конъюнкции.
Теорема: Какова бы ни была булева функция , она может быть выражена через функции , которые являются базисом.
|
Доказательство: Если функция , то она может быть представлена в следующем виде: .
Если функция , то она может быть представлена в следующем виде: . В противном случае функция может быть представлена в виде СДНФ.
Теорема доказана.
|
|
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!