19
правок
Изменения
ДНФ
,Добавил англ. терминов; поправил аббревиатуры; убрал скобки в формулировке теоремы; выделил жирным шрифтом в определениях то, что нужно.
{{Определение
|definition =
'''Простой конъюнкцией ''' (англ. ''inclusive conjunction'') или '''конъюнктом ''' (англ. ''conjunct'') называется конъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая конъюнкция
{{Определение
|definition =
'''Дизъюнктивная нормальная форма, ДНФ ''' (Дизъюнктивная Нормальная Формаангл. ''disjunctive normal form, DNF'') — {{---}} нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид дизъюнкции нескольких простых конъюнктов.
}}
Пример ДНФ:
{{Определение
|definition =
'''Совершенная дизъюнктивная нормальная форма, СДНФ ''' (Совершенная Дизъюнктивная Нормальная Форма)англ. ''perfect disjunctive normal form, PDNF'' ) — это такая ДНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых конъюнкций
* каждая простая конъюнкция полная
{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec {x})</tex>, не равной тождественному нулю (), существует СДНФ, ее задающая.
|proof =
Для любой булевой функции выполняется следующее соотношение, называемое '''разложением Шеннона'''.
