K-конъюнктивная нормальная форма
- K-конъюнктивная нормальная форма
-
k-конъюнкти́вная норма́льная фо́рма (k-КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов, каждый из которых содержит ровно k литералов.
Например, следующая формула записана в 2-КНФ:
Задача выполнимости формулы в k-КНФ
В теории вычислительной сложности важную роль играет задача выполнимости булевых формул в k-конъюнктивной нормальной форме. Эта задача NP-полна, и в то же время, она зачастую сводится ко многим другим NP-полным задачам при помощи несложного полиномиального сведения.
См. также
Wikimedia Foundation.
2010.
Смотреть что такое "K-конъюнктивная нормальная форма" в других словарях:
конъюнктивная нормальная форма — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN conjunctive normal formCNF … Справочник технического переводчика
конъюнктивная нормальная форма (КНФ) — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN standard product of sums … Справочник технического переводчика
Конъюнктивная нормальная форма — (КНФ) в булевой логике нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к… … Википедия
Нормальная форма (математика) — У этого термина существуют и другие значения, см. Нормальная форма (значения). Нормальная форма в математике простейший либо канонический вид, к которому объект приводится эквивалентными преобразованиями[1]. Содержание 1 Жорданова… … Википедия
КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА — пропозициональная формула, имеющая вид (*) где каждое С ij, i=1, . . ., п;j=1, . . ., mi, есть либо переменная, либо отрицание переменной. К. н. ф. (*) является тавтологией тогда и только тогда, когда для любого iсреди С i1, . . ., Cimi.… … Математическая энциклопедия
Нормальная форма (значения) — Нормальная форма: Нормальная форма в базах данных свойство отношения в реляционной модели данных. Нормальная форма в математике в каком либо смысле простейший либо канонический вид, к которому объект приводится преобразованиями,… … Википедия
Дизъюнктивная нормальная форма — (ДНФ) в булевой логике нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон… … Википедия
СОВЕРШЕННАЯ НОРМАЛЬНАЯ ФОРМА — совершенная дизъюнктивная или совершенная конъюнктивная нормальная форма (см. Булевых функций нормальные формы) … Математическая энциклопедия
Булева функция — В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из за отсутствия сносок … Википедия
Булевы выражения — В теории дискретных функциональных систем булевой функцией называют функцию типа , где булево множество, а n неотрицательное целое число, которое называют арностью или местностью функции. Элементы 1 (единица) и 0 (ноль) стандартно интерпретируют… … Википедия
