Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-equiv-in-3knf — различия между версиями
Материал из DISCOPAL
Tsyganova (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Выразите логическое отношение эквивалентности в виде 3-КНФ формулы. | Выразите логическое отношение эквивалентности в виде 3-КНФ формулы. | ||
| − | |||
<latex> | <latex> | ||
| − | Отношение эквивалентности A | + | \textbf{Решение} |
| + | |||
| + | Отношение эквивалентности $A \Leftrightarrow B$ записывается следующей 3-КНФ формулой: $(\overline{A}\vee B)\wedge(A\vee\overline{B})$ | ||
</latex> | </latex> | ||
[[Category:На проверку]] | [[Category:На проверку]] | ||
Версия 16:55, 1 декабря 2014
Цыганова Светлана, 974гр.
Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.