NP-полнота задачи о выполнимости булевой формулы в форме КНФ — различия между версиями
| Строка 1: | Строка 1: | ||
====Определения==== | ====Определения==== | ||
* ''Литералом'' является переменная или отрицание переменной. Например, <tex>x</tex> или <tex>\neg y</tex>. | * ''Литералом'' является переменная или отрицание переменной. Например, <tex>x</tex> или <tex>\neg y</tex>. | ||
| + | * ''Дизъюнктом'' называется логическое '''ИЛИ''' одного или нескольких литералов. Например, <tex>x \vee \neg y \vee z</tex> | ||
Версия 14:11, 17 марта 2010
Определения
- Литералом является переменная или отрицание переменной. Например, или .
- Дизъюнктом называется логическое ИЛИ одного или нескольких литералов. Например,
