Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2023-01-02 | 29 |
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 – некоторые коэффициенты, которые могут быть найдены по таблице истинности.
СПНФ может быть также построена методом навешивания двойного отрицания. Основное необходимое тождество в данном случае - .
Пример: .
Функция называется линейной, если в ее разложении в СПНФ отсутствуют конъюнкции.
Теорема: Какова бы ни была булева функция , она может быть выражена через функции , которые являются базисом.
|
Доказательство: Если функция , то она может быть представлена в следующем виде: .
Если функция , то она может быть представлена в следующем виде: . В противном случае функция может быть представлена в виде СДНФ.
Теорема доказана.
|
|
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!